Удаление общего подвыражения
В теории компиляторов исключение общего подвыражения ( CSE ) — это оптимизация компилятора , которая ищет экземпляры идентичных выражений (т. е. все они оценивают одно и то же значение) и анализирует, стоит ли заменять их одной переменной, содержащей вычисленное значение. [ 1 ]
Пример
[ редактировать ]В следующем коде:
a = b * c + g; d = b * c * e;
возможно, стоит преобразовать код так:
tmp = b * c; a = tmp + g; d = tmp * e;
если стоимость хранения и извлечения tmp меньше стоимости расчета b * c дополнительное время.
Принцип
[ редактировать ]Возможность выполнения CSE основана на доступном анализе выражений ( анализе потока данных ). Выражение b*c доступен в точке p программы, если:
- каждый путь от начального узла до p оценивает
b*cдо достижения р , - и нет никаких заданий
bилиcпосле оценки, но до p .
Анализ затрат/выгод, выполняемый оптимизатором, позволит рассчитать, будет ли стоимость магазина tmp меньше стоимости умножения; на практике другие факторы, например, какие ценности хранятся в каких регистрах, также имеют значение.
Авторы компиляторов различают два типа CSE:
- локальное исключение общего подвыражения работает в пределах одного базового блока
- глобальное исключение общих подвыражений работает для всей процедуры,
Оба типа основаны на анализе потока данных , позволяющем определить, какие выражения доступны в каких точках программы.
Преимущества
[ редактировать ] | Возможно, этот раздел содержит оригинальные исследования . ( сентябрь 2017 г. ) |
Преимущества выполнения CSE настолько велики, что это широко используемая оптимизация.
В простых случаях, как в приведенном выше примере, программисты могут вручную удалять повторяющиеся выражения во время написания кода. Основным источником CSE являются промежуточные последовательности кода, генерируемые компилятором, например, для вычислений индексации массива , когда разработчик не может вмешаться вручную. В некоторых случаях особенности языка могут создавать множество повторяющихся выражений. Например, C макросы , где раскрытие макросов может привести к появлению общих подвыражений, не видимых в исходном исходном коде.
Составители должны разумно подходить к количеству временных объектов, созданных для хранения значений. Чрезмерное количество временных значений создает нагрузку на регистры , что может привести к утечке регистров в память, что может занять больше времени, чем простое перевычисление арифметического результата, когда это необходимо.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Стивен Мучник; Мучник и партнеры (15 августа 1997 г.). Расширенная реализация проекта компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2 .
Удаление общего подвыражения.
- Стивен С. Мучник , Расширенное проектирование и реализация компилятора ( Морган Кауфманн , 1997), стр. 378–396.
- Джон Кок . «Глобальное устранение общих подвыражений». Труды симпозиума по созданию компиляторов , ACM SIGPLAN Notifications 5 (7), июль 1970 г., страницы 850–856.
- Бриггс, Престон, Купер, Кейт Д. и Симпсон, Л. Тейлор. « Нумерация значений ». Программное обеспечение, практика и опыт , 27 (6), июнь 1997 г., страницы 701–724.