Вопросы по оптимизации компилятора

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

2. Я не совсем уверен в этом, но взгляните на этот список проходов LLVM. LLVM — это оптимизирующий IR для компиляторов, который зачастую даже быстрее, чем GCC. К каждому проходу есть небольшое пояснение. Если вам нужна дополнительная информация, посмотрите исходный код LLVM для этих проходов. Он написан на C++, но достаточно чист и понятен.

Редактировать: кстати, если вы разрабатываете компилятор, я настоятельно рекомендую LLVM, он очень прост в использовании и генерирует оптимизированный код.

Для 1 имя оптимизации, которую вы ищете, — устранение общего подвыражения (CSE). В зависимости от вашего представления это может быть довольно легко. Обычно компилятор будет иметь некое промежуточное представление программы, в котором операции максимально разбиты и линеаризованы. Так, например, выражение c = a * b + a * b можно разбить следующим образом:

v1 = a * b
v2 = a * b
c = v1 + v2

Таким образом, вы можете выполнять CSE на очень низком уровне, ища операции с одним и тем же оператором и операндами. Когда вы сталкиваетесь с дубликатом (в данном случае v2), вы заменяете все его экземпляры оригиналом. Таким образом, мы могли бы упростить приведенный выше код:

v1 = a * b
c = v1 + v1

Обычно это предполагает, что вы назначаете каждую переменную только один раз (одна форма статического назначения), но вы можете реализовать что-то подобное без этого ограничения. Это становится более сложным, когда вы пытаетесь выполнить эту оптимизацию между ветвями. Как упоминает Zifre, посмотрите на устранение частичной избыточности.

В любом случае вы получаете некоторое базовое улучшение, и все, что вам нужно отслеживать, — это базовые выражения. Возможно, вы захотите пойти дальше и поискать арифметические тождества. Например, a * b совпадает с b * a. Кроме того, x * (y + z) = x * y + x * z. Это усложняет вашу оптимизацию, и неясно, даст ли это вам такое значительное улучшение производительности. Как ни странно, большая часть преимуществ от оптимизации CSE исходит от вычислений адресов, таких как доступ к массиву, и вам не понадобятся сложные идентификаторы, подобные приведенным выше.

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

Я настоятельно рекомендую две печатные ссылки по этим темам:

1. Проектирование и реализация расширенного компилятора Стивена С. Мучника
2. Создание оптимизирующего компилятора Роберта Моргана

Книга Мучника носит формальный характер, но она очень удобочитаема и содержит хорошее описание всех важных методов оптимизации. Книга Моргана имеет гораздо более практический характер и могла бы стать отличной основой для проекта компилятора, ориентированного на методы оптимизации. Ни в одной из книг мало что говорится о лексическом анализе или синтаксическом анализе, предполагается знание этих предметов.

Чтобы добавить еще одну книгу в список рекомендаций, проверьте " Восторг хакера" Генри С. Уоррена. Это отличный сборник методов оптимизации общих операций, таких как преобразование целочисленных делений в умножения.

Вы ищете устранение частичной избыточности (PRE). И CSE (из других ответов), и движение кода, не зависящее от цикла, включены в PRE. (Разновидностью PRE является Lazy Code Motion, который я считаю оптимальным).

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

НЕ используйте SSAPRE. Насколько мне известно, для этого требуется особая форма SSA, известная как HSSA, которая имеет несколько недостатков:

• Это довольно сложно
• Для этого требуется глобальная нумерация значений (поэтому SSAPRE не обеспечивает нумерацию значений, поскольку ожидается, что она уже существует).
• Он ничего не дает, если ваш язык не поддерживает указатели на переменные стека (а если поддерживает, прекратите писать собственный анализ и используйте LLVM или gcc).
• gcc некоторое время использовал HSSA, но они отошли от него.
• LLVM экспериментировал с ним, но, насколько мне известно, они его больше не используют.

РЕДАКТИРОВАТЬ:

В книге Мучника есть подробное описание, ссылка на которое есть в другом ответе.