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

Question

1. Каковы некоторые из способов, которыми компилятор устраняет повторные вычисления подвыражений?Как вы отслеживаете подвыражения?И как вы определяете повторяющиеся из них?
2. Помимо использования побитовых операторов, каковы некоторые методы уменьшения сложности, используемые обычными компиляторами?

Answer 1

<Ол>

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

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

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

Answer 2

Для 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 достигается за счет вычислений адресов, таких как доступ к массиву, и вам не понадобятся сложные идентификаторы, подобные приведенным выше.

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

Answer 3

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

<Ол>

Усовершенствованный дизайн компилятора и разработка; Реализация Стивена С. Мучника

Создание оптимизирующего компилятора Роберта Моргана

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

Answer 4

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

Answer 5

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

Проверьте Конспекты лекций Кита Купера, которые, по-видимому, очень хорошо описывают методы.

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

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

Редактировать:

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