Ваша любимая оптимизация абстрактного синтаксического дерева - PullRequest
Новая
       6

Ваша любимая оптимизация абстрактного синтаксического дерева

4 голосов
/ 01 декабря 2009

Если бы вы строили компилятор, какую оптимизацию на уровне AST было бы лучше всего иметь?

Ответы [ 3 ]

8 голосов
/ 02 декабря 2009

В основном вы не можете делать интересные оптимизации на уровне AST, потому что вам нужна информация о том, как данные передаются из одной части программы в другую. Хотя поток данных подразумевается в значении AST, его нелегко определить, проверяя только AST, поэтому люди, строящие компиляторы и оптимизаторы, строят другие представления программ (включая таблицы символов, графики потоков управления, достижения определений, поток данных). формы SSA и т. д.).

Наличие синтаксического анализатора для языка является легкой частью анализа / манипулирования этим языком. Вам нужны все эти другие вещи, чтобы сделать хорошую работу.

Если у вас есть все эти другие представления, вы можете подумать об оптимизации на уровне AST. Большинство людей, строящих компиляторы, не беспокоятся; они преобразуются в представление потока данных и просто оптимизируют это. Но если вы хотите воспроизвести исходный код с изменениями, вам нужен AST. Вам также понадобится симпатичный принтер, чтобы вы могли восстановить исходный код. Если вы зайдете так далеко, вы в конечном итоге с источником к источнику система преобразования программ.

DMS Software Reengineering Toolkit - это система, которая преобразует AST, используя все эти другие представления для проведения анализа, необходимого для преобразований.

5 голосов
/ 09 декабря 2009

Оптимизация, которую проще всего выполнить в AST (а не, скажем, в CFG), это оптимизация хвостового вызова: если вы видите поддерево в форме: 

RETURN
    CALL f
        ARGS x, y, ...

Вы можете заменить его прыжком на f. Если f(a, b) является функцией, в которой появляется хвостовой вызов, замена выполняется так же просто: 

a = x; b = y
JUMP to root of tree

Я считаю, что проще всего представить этот переход как специальный оператор "restart", который перевод AST-> CFG обрабатывает как ребро назад к первому узлу. Переход к другим функциям немного сложнее, поскольку вы не можете просто установить локальные переменные, вам нужно заранее продумать, как им передаются аргументы, и подготовиться к переводу этого на более низкий уровень. Например, для AST может потребоваться специальный узел, который может дать команду последующему проходу перезаписать текущий кадр стека аргументами и перейти соответственно.

1 голос
/ 17 декабря 2014

Одним из преимуществ применения оптимизаций в AST является то, что это может сократить время выполнения некоторого прохода внутренней оптимизации. Тем не менее, я считаю, что эти оптимизации должны быть выполнены с помощью скупости, потому что вы можете препятствовать дальнейшей оптимизации в коде.

При этом, IMO, одной простой, но интересной оптимизацией, которая должна применяться на уровне AST или при генерации IR, является упрощение логического выражения в форме (1 || 2) или (2 <3 || A) и т. Д. к их чистому результату. Я полагаю, что некоторые простые оптимизации глазка также могут быть полезны. </p>

...