Вопросы по оптимизации компилятора
- Каким образом компилятор устраняет повторные вычисления подвыражений? Как вы отслеживаете подвыражения? И как вы идентифицируете повторяющиеся?
- Помимо использования побитовых операторов, какие методы снижения прочности используются обычными компиляторами?
5 ответов
Я полагаю, что многие компиляторы используют SSAPRE (Устранение частичного избыточного статического одиночного назначения) для устранения повторяющихся выражений. Для этого требуется, чтобы код был в форме SSA, что позволяет проводить еще большую оптимизацию.
Я не совсем уверен в этом, но посмотрите на этот список пропусков 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
Обычно это предполагает, что вы назначаете каждую переменную только один раз (одна статическая форма назначения), но вы можете реализовать что-то подобное без этого ограничения. Это становится более сложным, когда вы пытаетесь выполнить эту оптимизацию в разных филиалах. Как упоминает Зифре, посмотрите на устранение частичной избыточности.
В любом случае, вы получаете некоторые базовые улучшения, и все, что вам нужно отслеживать, это базовые выражения. Вы можете пойти дальше и искать арифметические тождества. Например, a * b такой же как b * a, Также, x * (y + z) = x * y + x * z, Это делает вашу оптимизацию более сложной, и не ясно, что это даст вам значительное улучшение производительности. Как ни странно, большая часть преимуществ оптимизации CSE обеспечивается вычислениями адресов, такими как доступ к массиву, и вам не понадобятся сложные идентификаторы, подобные приведенным выше.
Во-вторых, какое снижение прочности полезно, действительно зависит от архитектуры, для которой вы компилируете. Обычно это включает в себя преобразование умножения и деления в сдвиги, сложения и вычитания.
Я очень рекомендую две печатные ссылки на эти темы:
- Усовершенствованный дизайн и реализация компилятора Стивена Мучника
- Создание оптимизирующего компилятора Роберта Моргана
Книга Мучника находится на формальной стороне, но очень удобочитаема и имеет хорошее описание всех важных методов оптимизации. Книга Моргана гораздо более практична и станет отличной основой для проекта компилятора, ориентированного на методы оптимизации. Ни одна книга не может сказать много о лексическом анализе или разборе, знание этих предметов предполагается.
Чтобы добавить еще одну книгу в список рекомендаций, ознакомьтесь с "Восторгом хакера" Генри С. Уоррена. Это отличный сборник методов для оптимизации общих операций, таких как преобразование целочисленных делений в умножения.
Вы ищете устранение частичной избыточности (PRE). И CSE (из других ответов), и движение с инвариантным циклом кодируются в PRE. (Разновидностью PRE является Lazy Code Motion, который я считаю оптимальным).
Посмотрите лекционные заметки Кейта Купера, которые, кажется, очень хорошо описывают методы.
НЕ используйте SSAPRE. AFAIK, это требует особой формы SSA, известной как HSSA, которая имеет несколько недостатков:
- Это довольно сложно
- Требуется глобальная нумерация значений (и поэтому SSAPRE не обеспечивает нумерацию значений, поскольку ожидается, что она уже существует).
- Он ничего не дает, если ваш язык не поддерживает указатели для суммирования переменных (и если это так, прекратите писать свой собственный анализ и используйте LLVM или gcc).
- Некоторое время gcc использовал HSSA, но они отошли от него.
- LLVM экспериментировал с этим, но AFAIK они больше не используют это.
РЕДАКТИРОВАТЬ:
Книга Мучника имеет подробное описание, оно связано в другом ответе.