Устранение общих подвыражений

В теории компиляции исключение общих подвыражений ( CSE ) — это оптимизация компилятора , которая ищет экземпляры идентичных выражений (т. е. все они имеют одинаковое значение) и анализирует, стоит ли заменять их одной переменной, содержащей вычисленное значение. ^[1]

В следующем коде:

а = б * с + г;г = б * в * е;

возможно, стоит преобразовать код в:

тмп = б * с;а = тмп + г;d = tmp * e;

если стоимость хранения и извлечения tmpменьше стоимости расчета b * cдополнительного времени.

Возможность выполнения CSE основана на анализе доступного выражения ( анализ потока данных ). Выражение b*cдоступно в точке p в программе, если:

• каждый путь от начального узла до p оценивается b*cдо достижения p ,
• и нет никаких заданий до bили cпосле оценки, но до с .

Анализ затрат и выгод, выполняемый оптимизатором, вычисляет, меньше ли стоимость сохранения tmp, чем стоимость умножения; на практике также важны другие факторы, такие как то, какие значения хранятся в каких регистрах.

Разработчики компиляторов различают два вида CSE:

• локальное устранение общих подвыражений работает в пределах одного базового блока
• глобальное исключение общих подвыражений работает во всей процедуре,

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

Этот раздел, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его, проверив сделанные заявления и добавив встроенные цитаты . Заявления, состоящие только из оригинальных исследований, должны быть удалены. ( Сентябрь 2017 г. ) ( Узнайте, как и когда удалять это сообщение )

Преимущества применения CSE настолько велики, что это широко используемая оптимизация.

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

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

• Глобальная нумерация значений
• Циклически-инвариантное кодовое движение

• Стивен С. Мучник , Advanced Compiler Design and Implementation ( Morgan Kaufmann , 1997) стр. 378–396
• Джон Кок . «Глобальное устранение общих подвыражений». Труды симпозиума по построению компиляторов , ACM SIGPLAN Notices 5(7), июль 1970 г., страницы 850–856.
• Бриггс, Престон, Купер, Кит Д. и Симпсон, Л. Тейлор. «Нумерация значений». Software-Practice and Experience , 27(6), июнь 1997 г., страницы 701-724.