Участок экономии

Участок экономии (Economy region) — фрагмент программы, который содержит все изменяемые части программы и семантика которого гарантирует корректность и целесообразность данной оптимизации по отношению ко всей программе. По существу, оптимизирующее преобразование, рассмотренное как преобразование участка экономии, является бесконтекстным.

Понятно, что ограничение на размер участка экономии сужает возможности улучшения программы (в этом случае говорят о глобальной оптимизации), и поэтому наилучшим участком экономии является вся программа. Однако глобальность оптимизации, как правило, не только приводит к существенному увеличению объема рассматриваемой информации, но и не позволяет разработать обоснованный и эффективный алгоритм реализации этой оптимизации. Поэтому на практике обычно рассматривают следующие участки экономии.

Оператор. Арифметические операции — основной источник оптимизации в операторе.

Линейный участок, или луч. Свойства луча быть последовательностью операторов, выполняемых в порядке их перечисления, существенно упрощает выполнение большинства оптимизаций.

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

Совершенное гнездо циклов. Гнездом циклов является множество циклов, вложенных один в другой. Гнездо называется совершенным, если тело каждого следующего цикла, отличного от самого внутреннего, состоит только из следующего цикла гнезда.

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

Процедура. Ряд оптимизаций (в частности, экономия памяти и другие оптимизации, связанные с перераспределением памяти) требует для своего эффективного применения рассмотрения управляющего графа процедуры, кодирующего передачи управления между лучами ее тела. Для того чтобы упростить алгоритмы оптимизирующего преобразования и (или) уменьшить объем одновременно рассматриваемой информации, часто используется прием, получивший название факторизации. При факторизации процедура представляется в виде иерархии вложенных фрагментов специального вида, последовательно обрабатываемых (в укрупненном виде) в соответствии с их вложенностью.

Иерархия вложенных интервалов. Фрагмент, называемый интервалом, моделирует правила композиции структурного программирования в терминах управляющего графа. Многие алгоритмы глобальной оптимизации упрощаются, если программа регуляризуема — представима в виде иерархии вложенных интервалов.

Иерархия вложенных альтов. Не менее естественной единицей факторизации является альт — фрагмент с единственной начальной вершиной. Если программа регуляризуема, то подмножество ее альтов образует зонно-интервальное представление программы, выявляющее как циклическую, так и интервальную ее структуру. Любая программа представима в виде иерархии альтов, являющихся гамаками. Такое представление не требует изменения алгоритма оптимизации при его факторизации и выделяет фрагменты, являющиеся обобщенными преобразователями.

Группа процедур. Совместное рассмотрение процедур часто предоставляет дополнительные возможности для оптимизации, например позволяет выявить процедуры, не являющиеся рекурсивными, или осуществить открытую подстановку тел процедур на места их вызовов. При этом помимо уграфов, кодирующих потоки управления между лучами внутри тел процедур, рассматриваются межпроцедурные связи, например в виде графа вызовов процедур.

Литература

• Векторизация программ: теория, методы, реализация. — М.: Мир, 1991.

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Касьянов В.Н. Оптимизация программ // Прикладная информатика. — М.: Финансы и статистика, 1983. — Вып. 2.

• Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

• Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.