Математическая энциклопедия - программ оптимизирующие преобразования

применяемые при трансляции направленные преобразования программы, представленной в иек-рой ее промежуточной форме, с целью улучшения рабочих характеристик программы, связанных с использованием ею ресурсов ЭВМ, главными из к-рых являются время выполнения и объем занимаемой памяти.

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

Различают машинно-зависимые П. о. п., к-рые определяются особенностями машинного языка или другими характеристиками конкретной ЭВМ, и универсальные П. о. п. (такие, напр., как удаление из программы операторов, недостижимых от начала), к-рые определяются только семантикой, вкладываемой в исходную запись алгоритма, и применимы для широкого класса ЭВМ.

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

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

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

Только для узких классов программ таких, как, напр., класс линейных программ, можно построить конечный полный набор П. о. п. Поэтому в конкретных трансляторах набор П. о. п. в значительной степени строится на эвристич. основе и существенно зависит от класса задач, для к-рых предназначен транслятор. Важным является выбор последовательности применений П. о. п., поскольку, как правило, используемые наборы II. о. п. не являются системами Чёрча Россера, в к-рых результат не зависит от порядка применения преобразований.

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

Лит.:[1] Ахо А., Ульман Дж., Теория синтаксического анализа, перевода и компиляции, пер. с англ., т. 2, М., 1978; [2] Бабецкий Г. И. и др., Альфа-система автоматизации программирования, Новосиб., 1967; [3] Касьянов В. Н., Поттосин И. В., Технология трансляции, Новосиб., 1979. В. Н. Касьянов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985