По следам этой темы: http://www.wasm.ru/forum/viewtopic.php?id=25102 Вчера еще немного поразмышлял над возможными алгоритмами прохода по всем инструкциям. Рассматриваем случаи, когда итерация одновременно по всем узлам (=инструкциям) по какой-либо причине нежелательна (например в случае эмуляции выполнения). То есть нужно именно пройти по коду. Пусть у нас есть функция Код (Text): int func(boolean flag) { int a,b,с; if(flag){a=1;}else{a=2;} if(flag){b=2;}else{b=a+3;} if(flag){c=3;}else{c=3;} return a+b+c; } Задание - определить, какие переменные будут иметь в конце функции постоянное значение, которым их можно заместить. Как такое решать? (Понятно, что в данном конкретном случае есть более эффективный способ - построение data flow graph. Взял просто для наглядности примера.) В упомянутой выше теме был предложен такой метод: проходить по одному случайному пути до конца, ответвления запоминать и потом возвращаться к ним. То есть здесь это будет выглядеть так (по умолчанию первой всегда берем ветку if): Проходим первую, вторую и третью if-ветки. Проходим первую else-ветку, видим, что на слиянии значение a изменилось - значит начинаем отсюда заново. Проходим вторую и третью if-ветки. Проходим вторую else-ветку, видим, что на слиянии значение b изменилось. Проходим третью if-ветку. Проходим третью else-ветку. То есть вторая и третья if-ветки были пройдены несколько раз - явно избыточная работа, хорошо бы от нее избавиться. Интуитивно видно, что здесь мы были бы в выигрыше, если бы останавливались не в конце функции, а после каждого блока if - т.е. проход: первый if, первый else, второй if, второй else и так далее. Значит задача сводится к нахождению таких точек в коде, на которых мы можем остановиться и обработать накопившиеся ответвления. Но что из себя представляют эти точки - тоже очевидно. Это постдоминаторы (postdominators). Если a "постдоминирует"(есть такое слово?) b, то любое ответвление в b пройдет через a. А для вычисления постдоминаторов есть стандартные методы - итеративный или Lengauer-Tarjan с модификациями. Можно пойти дальше и вычислить пары доминатор - постдоминатор, они будут прямо соответствовать естественным блокам программы (if, while..). Таким образом получим своего рода Hierarchical Control Flow Graph. Затраты на вычисление немного возрастут(менее чем в два раза), но получим более строгую и полную структуру. Будет ли этот алгоритм работать или кто-то видит недочеты? Или есть еше лучший? Как например работают сегодняшние эмуляторы? Не может быть, чтобы мне первому пришла в голову такая тривиальщина, наверняка все это где-то уже описано?
Разве в "Компиляторы. Принципы, технологии, инструменты" в главе Оптимизация не то же самое рассматривается?
Строится дерево разбора, затем оптимизируется (объединяются одинаковые поддеревья), в итоге получается граф. И собственно достаточно пройти его любым способом (LR, RL) с анализом операций. Все очень просто. В Компиляторах рассматриваются очень похожие вещи. Особенно при распределении переменных по регистрам.
maxdiver Ага, читаю.. там похожие вещи разбираются (не удивительно, так как я читал естественно те же самые работы, что и авторы книги ), но как мне кажется не совсем то. Они упоминают структурирование графа по операторам(10.5): The portion of a flow graph corresponding to a statement S is a region that obeys the further restriction that control can flow to just one outside block when it leaves the region. Это и есть в других терминах блочные пары доминатор-постдоминатор. Но все это определяется в контексте data flow equations, а я беру как раз другой случай - когда нельзя определить такую систему уравнений. В 10.10 описывается алгоритм посещения узлов в принципе с той же целью, что и у меня, но через regions общего вида и опять же для data flow. а не прямого выполнения. Xerx Боюсь не совсем понимаю, дерево разбора чего? AST и CFG - совсем разные вещи..
