В теории компиляторов , устранение общего подвыражения ( CSE ) является оптимизация компилятор , который ищет экземпляры одинаковых выражений (то есть, все они оценивают по той же стоимости), а также анализ стоит ли заменить их одной переменной , содержащей вычисляемое значение. [1]
Пример [ править ]
В следующем коде:
а = b * c + g;d = b * c * e;
возможно, стоит преобразовать код в:
tmp = b * c;а = tmp + g;d = tmp * e;
если стоимость хранения и извлечения tmpменьше, чем затраты b * cна дополнительное время.
Принцип [ править ]
Возможность выполнения CSE основана на доступном анализе выражений ( анализе потока данных ). Выражение b*cдоступно в точке p в программе, если:
- каждый путь от начального узла до p оценивается
b*cдо достижения p , - и нет заданий до
bилиcпосле оценки, но до p .
Анализ затрат / выгод, выполняемый оптимизатором, рассчитает, tmpменьше ли стоимость магазина, чем стоимость умножения; на практике также имеют значение другие факторы, например, какие значения хранятся в каких регистрах.
Авторы компилятора различают два вида CSE:
- устранение локальных общих подвыражений работает в рамках одного базового блока
- глобальное исключение общего подвыражения работает для всей процедуры,
Оба типа основаны на анализе потока данных, который определяет, какие выражения доступны в каких точках программы.
Преимущества [ править ]
 | Этот раздел, возможно, содержит оригинальные исследования . ( Сентябрь 2017 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Преимущества выполнения CSE достаточно велики, поэтому это часто используемая оптимизация.
В простых случаях, как в примере выше, программисты могут вручную исключить повторяющиеся выражения при написании кода. Самый большой источник CSE - это промежуточные кодовые последовательности, генерируемые компилятором, например, для вычислений индексации массивов , в которые разработчик не может вмешаться вручную. В некоторых случаях языковые функции могут создавать множество повторяющихся выражений. Например, макросы C , в которых расширения макросов могут приводить к общим подвыражениям, не видимым в исходном исходном коде.
Компиляторы должны быть осторожны с количеством временных файлов, созданных для хранения значений. Чрезмерное количество временных значений создает давление в регистрах , что может привести к сбросу регистров в память, что может занять больше времени, чем просто пересчет арифметического результата, когда это необходимо.
См. Также [ править ]
Ссылки [ править ]
- ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Продвинутая реализация проекта компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2.
Исключение общего подвыражения.
- Стивен С. Мучник , 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.
