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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Удаление общих подвыражений (англ. 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).

Примечания[править | править исходный текст]

Литература[править | править исходный текст]