Программ Оптимизирующие Преобразования

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

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

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

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

Набор П. О. П. Для трансляторов с наиболее распространенных проблемно-ориентированных языков (таких, напр., как алгол, фортран, ПЛ/I).является хорошо исследованным и позволяет получать машинные программы, сравнимые по качеству с программами, написанными вручную. Он содержит преобразования по удалению повторных вычислений с одинаковым результатом, частичному выполнению программы при трансляции, по чистке программы от бесполезных объектов и действий, замене сложных вычислений на более простые, уменьшению суммарного размера одновременно существующих объектов, сокращению размера программы. Лит.:[1] Ахо А., Ульман Дж., Теория синтаксического анализа, перевода и компиляции, пер. С англ., т. 2, М., 1978. [2] Бабецкий Г.

И. И др., Альфа-система автоматизации программирования, Новосиб., 1967. [3] Касьянов В. Н., Поттосин И. В., Технология трансляции, Новосиб., 1979. В. Н. Касьянов.