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

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

RETURN
    CALL f
        ARGS x, y, ...

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

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

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

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

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

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

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

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

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