Исследование методов оптимизации программ м разработка оптимизирующего компилятора с языка паскаль для центрального процессора АС-6

Диссертационная работа посвящена вопросам разработки основных оптимизирующих алгоритмов и их использования при создании оптимизирующего компилятора с расширенного варианта языка Паскаль [5] для центрального процессора (ЦП) многомашинного комплекса АС-б [2].

Актуальность темы

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

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

Кроме того, важной задачей является создание для отечественной ЭВМ ЦП АС-6 оптимизирующего Паскаль-компилятора. Это связано с тем, что язык Паскаль, созданный первоначально в основном для учебных целей, получил широкое распространение и часто используется в качестве основного инструмента при создании больших систем программирования.

Необходима также разработка методов оценки качества оптимизирующей компиляции и аттестации транслятора в целом.

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

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

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

Основные виды оптимизаций. Все оптимизации разделяются на глобальные и локальные. Глобальные оптимизации проводятся в рамках всей программы с учетом всех составляющих ее частей. Локальные оптимизации выполняются только в пределах отдельных фрагментов программы.

В качестве элементарного фрагмента программы для проведения локальной оптимизации обычно выбирается линейный блок. Линейный блок имеет один вход и один выход и состоит из последовательно выполняемых элементарных операторов.

В программах блок представляет собой линейную последовательность операторов присваивания и операторов процедур. Эта последовательность операторов не должна содержать внутри себя меток. Начало такого блока может быть помечено, а в конце блока может стоять оператор перехода или оператор EXIT.

Кроме того, отдельные блоки образуют следующие компоненты структурных операторов:

— iiопределяющее выражение оператора CASE :

— выражения для вычисления предельных значений параметра.

FOR — цикла;

— условные выражения операторов IF, WHILE и REPEAT.

Для проведения глобальной оптимизации необходимо знание управляющего графа программы (УГП), отражающего все пути (без учета межпроцедурных взаимодействий), по которым распространяется поток управления во время выполнения программы. Исследуя УШ, можно узнать, какая информация поступает к каждому узлу графа. Узлами УШ являются линейные блоки, а ребра УШ соответствуют распространению потока управления между блоками. Блоку, с которого начинается выполнение программы, соответствует начальный узел УШ,.

Оптимизации программ разделяют также на два вида: машинно-независимый и машинно-зависимый.

К первому виду относятся такие оптимизации, которые одинаковы для всех машин, например, вычисление константных конструкций программы.

Машинно-зависимые оптимизации связаны с улучшением объектного кода для конкретной машины. К этому виду оптимизаций относится, например, распределение регистров машины для размещения операндов.

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

Так, например, сравнительно простая технология локальной оптимизации, используемая в компиляторе.

ФОРЕКССп], существенно ускоряет рабочие программы. Использование же в компиляторе с языка достаточно сложной глобальной оптимизации мало способствует улучшению откомпилированных программ.

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

Ваяно также исследовать работу готового компилятора при трансляции типовых программ и сделать обобщающие выводы о способах оптимизации программ для некоторого класса исходных языков и объектных машин.

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

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

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

В диссертационной работе обсуждаются также вопросы эффективной реализации основных расширений языка Паскаль [б" ].

Введение

этих расширений не затрагивает реализацию традиционной части языка.

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

Цели работы. Основными целями диссертационной работы были разработка оптимизирующих алгоритмов и их использование при создании Паскаль-компилятора для ЦП.

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

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

— вынос инвариантов из циклов;

— оптимизация индуктивных вычислений;

— буферизация циклов;

— использование команды «конец цикла» .

Следующим по значимости параметром оптимизации для ЦП является экономия памяти, занимаемой кодом и переменными программы. Для экономии программного кода использовались следующие оптимизации:

— однократное программирование эквивалентных вычислений;

— вычисление константных конструкций;

— устранение избыточных операторов присваивания и ряд других оптимизаций [15].

Алгоритм распределения переменных в памяти построен таким образом, чтобы экономия памяти достигалась не за счет потерь в эффективности работы. Этому способствовала четырехформатная адресация ЦП [2].

Обычно Паскаль-компилятор для быстродействующей ЭВМ с большой памятью реализуют по однопроходовой схеме [39]. В этом случае достигается высокая скорость компиляции за счет минимизации числа обращений ко вторичной памяти. Что касается качества кода, то предполагается, что на большинстве ЭВМ реализация конструкций Паскаля будет достаточно эффективной, и не потребуется интенсивной оптимизации для улучшения кода.

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

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

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

Выбор такой схемы компиляции объясняется еще одной причиной: предполагается в дальнейшем использовать отлаженный синтаксический оптимизатор и машинно-независимый оптимизатор при реализации.

Паскаль-компиляторов да других машин. В этом случае дополнительно потребуется создание лишь генератора объектного кода для конкретной ЭВМ.

Методы исследования. При разработке Паскаль-компилятора широко использовались результаты теории компиляции и теории графов [8,9,63]. Употреблялись также такие методы программирования, как методы поиска, организации информационных структур и т. д.

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

Научная новизна.

I. Предложена и реализована в Паскаль-компиляторе для ЦП АС-6 схема смешанной оптимизации программ: синтаксическая оптимизация регулярных циклов, внутри которых отсутствуют операторы.

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

3. Предложены и реализованы методы эффективной реализации расширений языка Паскаль, таких как:

— параметризация типов данных;

— введение шага в итеративном цикле. перехода и и локальная оптимизация программы.

— 164. Введены в язык Паскаль машинно-зависимые структурные типы данных: MACHINE RECORD и MACHINE.

ARR, А У ДОШ реализации машинно-зависимых процедур компилятора, например, подпрограммы генерации загрузочного модуля. Это позволило свыше 95 $ объема компилятора написать на Паскале и тем самым облегчило его перенос с одной ЭВМ на другую.

Практическая ценность. Разработан и реализован Паскаль-компилятор для ЦП АС-6, который обеспечивает получение рабочих программ, не уступающих программам, тщательно составленным вручную на автокоде. Компилятор прошел испытания и в настоящее время находится в эксплуатации в ИПМ АН СССР, в/ч 73 790 и ЦНИИМАШ.

Опыт разработки, а также методы оптимизации могут быть использованы при разработке компиляторов для современных ЭВМ.

Апробация. Результаты диссертационной работы докладывались на следующих конференциях и семинарах:

— на Конференции молодых ученых и специалистов НИИ «Дельта» ,.

1981;

— на 2-ой Всесоюзной Конференции «Автоматизация производства и проектирования прикладных программ и трансляторов», апрель 1983, г. Таллин;

— на семинаре «Архитектуры ЭВМ и численные методы», отдел вычислительной математики АН СССР, март 1984.

Диссертация состоит из 6 глав.

В первой главе анализируются основные методы оптимизации программ. Описывается структура Паскаль-компилятора для ЦП.

Вторая глава посвящена рассмотрению вопросов машинно-независимой оптимизации.

В третьей главе описывается алгоритм комплексной линейной оптимизации, реализованный в Паскаль-компиляторе для ЦП.

Четвертая глава содержит основные сведения о машинно-зависимых оптимизациях. Там же описывается алгоритм машинно-зависимой оптимизации, использованный в Паскаль-компиляторе.

В пятой главе анализируются результаты исследования работы компилятора при компиляции типовых тестов.

Шестая глава посвящена описанию реализации расширений Паскаля.

В заключении излагаются выводы, полученные на основе реализации и эксплуатации Паскаль-компилятора дои ЦП АС-6.

Публикации. На тему диссертации опубликовано 4 работы.

ЗШЮЧЕНИЕ.

1 * *.

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

Для достижения поставленных целей оптимизации была выполнена следующая работа:

1. Исследованы методы линейной оптимизации программ. Разработан и реализован алгоритм комплексной линейной оптимизации, который включает в себя оптимизирующие переупорядочивания выражений и локальную оптимизацию методом нумерации значений. В тех местах программы, где это возможно, диапазон применения локальных оптимизаций увеличивается.

2. Исследованы методы оптимизации циклов. Разработан и реализован алгоритм глобальной оптимизации регулярных циклов. Этот алгоритм включает в себя вынос инвариантов в предзаголовки циклов и свертку индуктивных вычислений.

3. Исследованы методы генерации объектного кода. Разработан и реализован алгоритм оптимального распределения регистров для размещения параметров циклов и операндов линейных блоков.

4. Разработан универсальный промежуточный код, приспособленный для оптимизации и генерации объектного кода.

5. Осуществлена эффективная реализация основных расширений языка Паскаль [б! .

6. Разработаны и реализованы средства анализа статического и динамического профилей компилируемых программ.

В работе над созданием оптимизирующего компилятора с расширенного варианта языка Паскаль совместно с автором принимали участие Гуслистый В. П. и Абрамян A.A. Автором написаны и отлажены основные семантические и оптимизирующие подпрограммы компилятора, а также разработана общая схема компиляции. Общий объем программ, написанных автором, составляет примерно 10 000 строк.

Создание Паскаль-компилятора для ЦП производилось в два этапа. Сначала этот компилятор, написанный на Паскале, был отлажен на БЭСМ-6, где имеется компилятор с Паскаля. Затем была проведена «раскрутка» компилятора, то есть компилятор оттранслировал свой собственный текст на БЭСМ-6, а полученный код был перенесен на ЦП.

Стоит отметить, что для отладки компилятора на БЭСМ-6 использовался интерпретатор ЦП.

Паскаль-компилятор прошел испытания в 1982 г. и в настоящее время эксплуатируется в следующих организациях: ИПМ Ш СССР, в/ч 73 790 и ЦНИИМАШ. Общий объем компилятора составляет 50 К слов, а скорость компиляции — 9000 строк в минуту.

Опыт разработки, а также используемые методы оптимизации могут быть применены при разработке компиляторов для современных ЭВМ.

Разработаны практические рекомендации для программирования на Паскале, используя которые пользователь может способствовать оптимизации своих программ [5].

По теме диссертационной работы были сделаны доклады на следующих конференциях и семинарах:

— на Конференции молодых ученых и специалистов НИИ «Дельта» ,.

— 1 251 981 г.;

— на второй Всесоюзной Конференции «Автоматизация производства и проектирования прикладных программ и трансляторов», апрель 1983 г., г. Таллин;

— на семинаре «Архитектуры ЭВМ и численные метода», отдел вычислительной математики АН СССР, март 1984 г.

Подводя окончательные итоги диссертационной работы, можно сделать следующие выводы:

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

— разработан универсальный промежуточный код, приспособленной для проведения оптимизации и генерации объектного кода;

— предложены методы эффективной реализации расширений Паскаля;

— создан и внедрен в опытную эксплуатацию оптимизирующий Паскаль-компилятор для ЦП АС-6;

— исследование работы готового Паскаль-компилятора подтвердило правильность выбранного подхода к оптимизации программ;

— внесены предложения по способам аттестации оптимизирующих компиляторов.

ПРИДОЖЕНИВ 1а. Сводная таблица относительных времен выполнения тестов (за единицу принято время рабочей программы транслятора ФОРЕКС, в котором реализована тщательная оптимизация внутренних циклов). тест гране-лятор I 2 3 4 5 6 7 8.

ФОРЕКС 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00.

Фортран-ДУБНА 6.80 5.88 6.62 4.14 3.19 1.44 1.33 1.30.

•Фортран-ГДР 7.72 1.00 1.00 — 2.60 1.62 1.11 1.95.

Форшаг 5.75 6.38 7.50 3.21 3.61 2.31 2.67 1.10.

Алгол-ГДР 1.00 2.00 2.00 1.00 1.73 1.56 1.45 4.35.

Компл.Алгол 8.45 5.25 8.50 4.57 5.39 3.30 3.45 1.00.

Алгамс 8.35 5.50 7.50 4.21 5.00 2.81 3.22 2.00 тест транслятор ^^ 9 10 II 12 13 14 15 16.

ФОРЕКС 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00.

Фортран-ДУБНА 2.78 1.67 1.31 3.22 2.60 1.00 1.00 2.60.

Фортран-ГДР 1.12 — 1.44 2.33 1.14 1.20 1.00 2.40.

Форшаг 2.62 1058 2.50 5.45 2.25 0.88 0.96 3.37.

Замечания: I. Указанные измерения производились на БЭСМ-6.

2. Подробное описание тестов и трансляторов имеется в [II] .