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

Применяемые при трансляции направленные преобразования программы, представленной в иек-рой ее промежуточной форме, с целью улучшения рабочих характеристик программы, связанных с использованием ею ресурсов ЭВМ, главными из к-рых являются время выполнения и объем занимаемой памяти. Обычно каждое применение П. о. п. изменяет локальную семантику фрагментов программы, но сохраняет семантику программы в целом — результирующая программа либо эквивалентна исходной, либо является ее доопределением на более широкое множество входов. Различают машинно-зависимые П. о. п., к-рые определяются особенностями машинного языка или другими характеристиками конкретной ЭВМ, и универсальные П. о. п. (такие, напр., как удаление из программы операторов, недостижимых от начала), к-рые определяются только семантикой, вкладываемой в исходную запись алгоритма, и применимы для широкого класса ЭВМ. Основные способы улучшения машинной программы при П. о. п. заключаются в удалении вычислений или объектов из процессов выполнения программы или в замене в них сложных вычислений на более простыв (на основе априорных оценок сложности вычислений). Это требует учета управляющих, информационных и частотных отношений, возникающих в этих процессах между операторами и объектами программы. П. о. п. по существу включает в себя: нахождение необходимых ему отношений указанного типа по локальной семантике операторов программы — т. н. потоковый анализ программы; проверку нек-рых свойств собранной информации — т. н. контекстных условий; преобразование фрагмента программы в случае удовлетворения этих свойств — собственно трансформация данного П. о. п. По величине той части программы (т. н. участка экономии), к-рая обрабатывается П. о. п. независимо от окружения, П. о. п. разделяются на локальные, участок экономии к-рых не более оператора; глобальные, участком экономии к-рых является вся программа; квазилокальные, где участок экономии — нек-рый фрагмент программы, имеющий фиксированную внутреннюю структуру,- напр., луч (линейная последовательность операторов), зона (нетривиальный сильно связный подграф управляющего графа программы), не содержащая других зон, или гамак (подграф, связанный с остальной частью управляющего графа в точности двумя вершинами — входной и выходной; входная вершина принадлежит гамаку, а выходная нет), не содержащий других гамаков и зон. Для уменьшения временной и емкостной сложности глобального П. о. п. часто используется факторизация — замена глобального П. о. п. серией квазилокальных, применяемых к фрагментам программы в соответствии с их вложенностью. Только для узких классов программ таких, как, напр., класс линейных программ, можно построить конечный полный набор П. о. п. Поэтому в конкретных трансляторах набор П. о. п. в значительной степени строится на эвристич. основе и существенно зависит от класса задач, для к-рых предназначен транслятор. Важным является выбор последовательности применений П. о. п., поскольку, как правило, используемые наборы II. о. п. не являются системами Чёрча — Россера, в к-рых результат не зависит от порядка применения преобразований. Набор П. о. п. для трансляторов с наиболее распространенных проблемно-ориентированных языков (таких, напр., как алгол, фортран, ПЛ/I).является хорошо исследованным и позволяет получать машинные программы, сравнимые по качеству с программами, написанными вручную. Он содержит преобразования по удалению повторных вычислений с одинаковым результатом, частичному выполнению программы при трансляции, по чистке программы от бесполезных объектов и действий, замене сложных вычислений на более простые, уменьшению суммарного размера одновременно существующих объектов, сокращению размера программы. Лит.:[1] Ахо А., Ульман Дж., Теория синтаксического анализа, перевода и компиляции, пер. с англ., т. 2, М., 1978; [2] Бабецкий Г. И. и др., Альфа-система автоматизации программирования, Новосиб., 1967; [3] Касьянов В. Н., Поттосин И. В., Технология трансляции, Новосиб., 1979. В. Н. Касьянов.