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

Удаление общих подвыражений (англ. Common subexpression elimination или CSE) — оптимизация компилятора, которая ищет в программе вычисления, выполняемые более одного раза на рассматриваемом участке, и удаляет вторую и последующие одинаковые операции, если это возможно и эффективно. Данная оптимизация требует проведения анализа потока данных[англ.] для нахождения избыточных вычислений и практически всегда улучшает время выполнения программы в случае применения[1].

Обобщенное описание задачи

Подвыражение в программе называется общим подвыражением, если существует другое такое же подвыражение, которое всегда вычисляется перед данным, и операнды не изменяются в промежутке между вычислениями. Например, в рассматриваемом ниже примере выражение b * c является общим подвыражением.

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

Рассмотрим следующий фрагмент кода: 

a = b * c + g;
d = b * c * d;

К нему применимо следующее преобразование: 

tmp = b * c;
a = tmp + g;
d = tmp * d;

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

Различают два вида данной оптимизации:

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

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

Принцип

Применение оптимизации основано на анализе доступных выражений. Выражение x + y является доступным в некоторой точке p программы, если:[2]

  • вдоль любого пути от начального узла к p выражение x + y вычисляется до достижения точки p;
  • между вычислениями выражений и достижением точки p нет изменения значений переменных x и y.

Эффективность преобразования главным образом определяется тем, что суммарное время записи и нескольких чтений новой переменной "tmp" оказывается меньше, чем суммарное время, затрачиваемое на вычисление выражения "b * c" каждый раз, когда оно встречается в коде. На практике на итоговую эффективность влияет также ряд других факторов, в частности распределение переменных по регистрам.

Выгода

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

В случае глобального применения оптимизации на выгоду влияют дополнительные критерии. Например, надо учитывать счётчики исполнения базовых блоков, так как, сократив статическое количество вычислений выражения, можно увеличить динамическое, что влияет отрицательно на кол-во выполненных операций в программе. Это приводит к тому, что может быть выгодна обратная оптимизация, относящаяся к классу PRE (partial redundancy elimination).

Примечания

  1. ↑ Advanced Compiler Design and Implementation, 1997, с. 377.
  2. ↑ Компиляторы: принципы, технологии и инструменты, 2008, с. 735.

Литература

  • Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.
  • Steven S. Muchnick. Advanced Compiler Design and Implementation. — 5-е издание. — San Francisco: Morgan Kaufmann Publishers, 1997. — С. 378-396. — 856 с. — ISBN 1-55860-320-4.
  • John Cocke. "Global Common Subexpression Elimination." Proceedings of a Symposium on Compiler Construction, ACM SIGPLAN Notices 5(7), July 1970, pages 850-856.
  • Briggs, Preston, Cooper, Keith D., and Simpson, L. Taylor. "Value Numbering." Software-Practice and Experience, 27(6), June 1997, pages 701-724.