WikiDer > Исключение общего подвыражения

Common subexpression elimination

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

Пример

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

а = b * c + g; d = b * c * e;

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

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

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

Принцип

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

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

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

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

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

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

Преимущества

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

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

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

Смотрите также

Рекомендации

  1. ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Расширенная реализация проекта компилятора. Морган Кауфманн. ISBN 978-1-55860-320-2. Исключение общего подвыражения.