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

Question

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

Answer 1

Оптимизация, которую проще всего выполнить в 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 может понадобиться специальный узел, который может дать указание последующему проходу перезаписать текущий кадр стека аргументами и перейти соответственно.

Answer 2

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

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

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

Инструментарий реинжиниринга программного обеспечения DMS - это система, которая преобразовывает AST с использованием всех эти другие представления, чтобы включить анализ, необходимый для преобразования.

Answer 3

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

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