Удаление общих подвыражений (англ. 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).
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .