Содержание к диссертации
Введение
ГЛАВА І. Анализ основных методов оптимизации программ 18
1.1. Оптимизация циклов 18
1.1.1. Циклы - ключевые места при оптимизации программы IS
1.1.2. Основные виды , оптимизации циклов 19
1.1.2.1. Вынос инвариантов из тела цикла 19
1.1.2.2. Оптимизация индуктивных вычислений 19
1.1.2.3. Уменьшение числа параметров в цикле 20
1.1.2.4. Расширение возможностей итеративного цикла в Паскале 20
1.1.2.5. Буферизация циклов 21
1.1.2.6. Использование команды "Конец цикла" 21
1.2. Сравнительная характеристика локальной и
глобальной оптимизаций .21
1.2.1. Основные методы экономии памяти программы 1.2.2. Характеристика линейной оптимизации 22
1.2.3. Характеристика методов глобальной оптимизации 22
1.2.3.1. Анализ потока управления и анализ потока данных 22
1.2.3.2. Нахождение доступных выражений 23
1.2.3.3. Оценка времени сходшлости алгоритмов АПД 25
1.2.3.4. Оценка влияния глобальной оптимизации 25"
1.3. Оптимизация в рамках регулярного графа 26
1.3.1. Абстрактные циклы 26
1.3.2. Переход от абстрактного УТЛ к синтаксическому УТЛ гг
1.3.3. Последовательный вынос инвариантных вычислений из вложенных циклов <2 7
1.4. Виды оптимизирующих компиляторов 28
1.4.1. Оптимизирующий компилятор с промежуточным 9 кодом 28
1.4.2. Оптимизация на исходном языке 28
1.4.3. Синтаксический оптимизатор 29
1.4.4. Покадровая оптимизация 30
1.5. Выбор схемы для построения оптимизирующего
Паскаль-компилятора 30
1.5.1. Классическая методика реализации Паскаль-компилятора 30
1.5.2. Компилятор с универсальным промежуточным
кодом 31
1.5.3. Схема реализации Паскаль-компилятора для ЦП 32
ГЛАВА 2. Методо машинно-независимой оптимизации программ .
2.1. Представление линейного блока в виде ориентированного ациклического графа 3
2.2. Основные виды линейной оптимизации 36
2.2.1. Экономия эквивалентных вычислений 36
2.2.2. Свертка вычислений, состоящих из одних констант 37
2.2.3. Устранение избыточных операторов присваивания . 3?
2.2.4. Оптимизации, опирающиеся на конкретные значения операндов 36
2.2.5. Выделение постоянной составляющей в индексном выражении 38
2.2.6. Экономия эквивалентных вычислений с учетом использования операций отношения
2.2.7. Оптимизация эквивалентных вычислений функций 33
2.2.8. Влияние побочных эффектов при обращениях к процедурам/функциям 40
2.3. Обзор методов линейной оптимизации 40
2.3.1. Метод нумерации значений 40
2.3.2. Линейная оптимизация в компиляторе ФОРЕКС
2.3.3. Использование коммутативно-ассоциативных законов для упорядочивания выражения 45
2.4. Внутренее представление линейного блока 44
2.4.1. Структура триады 45
2.4.2. Описание эквивалентных вычислений с помощью триад 46
2.4.3. Преобразование триад в переменные и константы 4?
2.4.4. Инвариантные триады 7
2.4.5. Индуктивные триады 4?
2.4.6. Вынесенные триады 4?
2.4.7. Особенности оптимизации операций отношения. 4?
2.4.8. Структура адресных триад 43
2.4.9. Представление переменных в рамках промежуточного кода 51
2.4.10. Представление констант в промежуточном коде 52
2.5. Оптимизация регулярных циклов 54
2.5.1. Структура синтаксического УТЛ 5
2.5.2. Вынос инвариантных триад из тела регулярного цикла 55
2.5.3. Оптимизация индуктивных вычислений
2.5.3.1. Описатель итеративного цикла в промежуточном коде 58
2.5.3.2. Преобразование индуктивных вычислений 53
ГЛАВА 3. Комплексная линейнм оптимизация 6І
3.1. Описание оптимизирующих преобразований выражений Паскаля 6І
3.1.1. Представление выражения в виде ассоциативного дерева 6І
3.1.2. Перестановка констант 62.
3.1.3. Перестановка вещественных и целых операндов б 5
3.1.4. Перестановка SET - операндов о о
3.1.5. Упорядочивание операндов в ассоциативной кисти 63
3.2. Описание алгоритма линейной оптимизации 6
3.2.1. Основные и вспомогательные структуры линейного оптимизатора 64
3.2.2. Структура стека вычислений и его использование для поиска эквивалентных триад 66
3.2.3. Назначение и структура TABVAR .64
3.2.4. Особенности поиска эквивалентных адресных триад 6%
3.2.5. Особенности поиска эквивалентных обращений к стандартным функциям 63
3.2.6. Обработка операторов присваивания простым.. 41 переменным ?i
3.2.7. Обработка триад присваивания структурным переменным ?2
3.2.8. Обработка операторов присваивания вариантным полям записей 7с2
3.2.9. Обработка триад присваивания массовым и динамическим переменным ?к
3.2.10. Устранение избыточных триад присваивания ?б
3.2.11. Особенности использования констант 7?
3.2.12. Грубая оценка влияния побочного эффекта 7&
3.2.13. Описание первого прохода оптимизации SO
3.2.14. Описание второго прохода оптимизации 6І
ГЛАВА 4. Методы машинно
4.1. Обзор методов машинно-зависимой оптимизации S2
4.1.1. Метод распределения регистров с помощью счетчиков использований &2
4.1.2. Распределение индекс-регистров в линейном блоке и простых циклах 2
4.1.3. Алгоритм глобального распределения регистров 845
4.1.4. Генерация команд для линейных блоков в компиляторе ФОРЖС 84
4.2. Связь между машинно-независимой и машинно-зависимой оптимизацией 85
4.3. Краткие сведения о ЦП
4.3.1. Структура регистров в ЦП S6
4.3.2. Скрытый стек и программный магазин 88
4.4. Представление простых паскалевских типов через машинные типы ЦП ЬЗ
4.5. Оптимизации, связанные с распределением памяти для размещения переменных 91
4.6. Оптимизации, связанные с распределением регистров в линейном блоке 94
4.6.1. Задачи подготовки операндов и распределение регистров 3 -
.6.2. Описатель состояний операндов 9S
4.6.3. Структура полного описателя операнда триады 98
4.6.4. Структура таблицы регистров 9&
4.6.5. Генерация команд из триад линейного блока 400
4.6.6. Алгоритм распределения регистров (процедура GETRE6 ) ^02
4.7 Глобальное распределение регистров для FOR -циклов iOS
4.8. Эффективная реализация CASE, -оператора.. 105
4.9. Покадровые оптимизации
4.10. Характеристика ЦП как Паскаль-машины 106
ГЛАВА 5. Анализ работы оптишзирующего
5.1. Оценка качества откомпилированных программ 108
5.2. Исследование влияния оптимизации на ускорение программ 109
5.2.1. Измерение временных характеристик Паскаль-тестов 109
5.2.2. Буферизация циклов ІІ2
5.2.3. Особенности оптимизации условных циклов 112
5.2.4. Дополнительные особенности оптимизации циклов 1 13
5.3. Измерение качества межпроцедурных взаимодействий 11*3
5.4. Оценка эффективности реализации CASE - операторов И^
5.5. Анализ эффективности обработки упакованных данных ІІ 5"
5.6. Оценка эффективности алгоритмов распределения регистров 116
5.7. Оценка эффективности алгоритмов экономии памяти
5.7.1. Экономия программного кода
5.7.2. Экономия памяти, занимаемой переменными
5.8. Введение в компилятор средств анализа
статического и динамического профилей программ
ГЛАВА 6. Эффективная реажзащя расширений паскаля
6.1. Параметризация типов 12.0
6.2. Использование новых возможностей итеративного цикла 22
Заключение
- Уменьшение числа параметров в цикле
- Устранение избыточных операторов присваивания
- Перестановка вещественных и целых операндов
- Генерация команд для линейных блоков в компиляторе ФОРЖС
Введение к работе
Диссертационная работа посвящена вопросам разработки основных оптимизирующих алгоритмов и их использования при создании оптимизирующего компилятора с расширенного варианта языка Паскаль [5] для центрального процессора (ЦП) многомашинного комплекса АС-6 [2І.
Актуальность темы. Языки высокого уровня находят все более широкое применение во всех областях программирования. Однако их использованию часто препятствует низкая эффективность откомпилированных программ в сравнении с соответствующими программами на автокоде.
Для повышения эффективности рабочих программ на всех промышленных компиляторах применяется технология оптимизации. Поэтому актуальной задачей является создание таких методов оптимизации программ, которые, с одной стороны, дают большой вклад в увеличение эффективности рабочих программ, а, с другой стороны, просты при их реализации в оптимизирующем компиляторе.
Кроме того, важной задачей является создание для отечественной ЭВМ ЦП АС-6 оптимизирующего Паскаль-компилятора. Это связано с тем, что язык Паскаль, созданный первоначально в основном для учебных целей, получил широкое распространение и часто используется в качестве основного инструмента при создании больших систем программирования.
Необходима также разработка методов оценки качества оптимизирующей компиляции и аттестации транслятора в целом.
Сущность оптимизации. Исходная программа, поступающая на вход компилятора, представляет собой описание на языке программирования некоторых вычислений и действий. Задача компилятора состоит в преобразовании исходной программы в объектную програм- -40-му, которая специфицирует заданные вычисления и действия на языке объектной машины.
Для каждой исходной программы можно получить бесконечное множество объектных программ. Эти объектные программы могут быть лучше или хуже относительно друг друга по разным параметрам, прежде всего по времени их выполнения на машине или по объему занимаемой ими памяти.
Оптимизацией программы называется используемая компилятором технология для получения объектной программы, превосходящей по оптимизационным параметрам такую объектную программу, которая наиболее просто и естественно получается из исходной программы. В общих чертах процесс оптимизации заключается в обнаружении и замене программных конструкций на более эффективные.
Основные виды оптимизаций. Все оптимизации разделяются на глобальные и локальные. Глобальные оптимизации проводятся в рамках всей программы с учетом всех составляющих ее частей. Локальные оптимизации выполняются только в пределах отдельных фрагментов программы.
В качестве элементарного фрагмента программы для проведения локальной оптимизации обычно выбирается линейный блок. Линейный блок имеет один вход и один выход и состоит из последовательно выполняемых элементарных операторов.
В программах блок представляет собой линейную последовательность операторов присваивания и операторов процедур. Эта последовательность операторов не должна содержать внутри себя меток. Начало такого блока может быть помечено, а в конце блока может стоять оператор перехода или оператор LXI !
Кроме того, отдельные блоки образуют следующие компоненты структурных операторов: определяющее выражение оператора CASE : выражения для вычисления предельных значений параметра FOR - цикла; - условные выражения операторов IF, WHILE и REPEAT.
Для проведения глобальной оптимизации необходимо знание управляющего графа программы (УГП), отражающего все пути (без учета межпроцедурных взаимодействий), по которым распространяется поток управления во время выполнения программы. Исследуя УШ, можно узнать, какая информация поступает к каждому узлу графа. Узлами УШ являются линейные блоки, а ребра УШ соответствуют распространению потока управления между блоками. Блоку, с которого начинается выполнение программы, соответствует начальный узел УШ.
Оптимизации программ разделяют также на два вида: машинно-независимый и машинно-зависимый.
К первому виду относятся такие оптимизации, которые одинаковы для всех машин, например, вычисление константных конструкций программы.
Машинно-зависимые оптимизации связаны с улучшением объектного кода для конкретной машины. К этому виду оптимизаций относится, например, распределение регистров машины для размещения операндов.
Основная проблематика. Известно много методов улучшения программ, начиная от покадровых и кончая глобальными оптимизациями. В зависимости от языка, объектной машины и способа реализации их применение дает разный эффект.
Так, например, сравнительно простая технология локальной оптимизации, используемая в компиляторе сущест- венно ускоряет рабочие программы. Использование же в компиляторе с языка SIM PL [26] достаточно сложной глобальной оптимизации мало способствует улучшению откомпилированных программ.
Поэтому главная задача при создании промышленного компилятора заключается в том, чтобы сконструировать такие оптимизирующие алгоритмы, которые, с одной стороны, дают большой вклад в увеличение эффективности рабочих программ, а, с другой стороны, достаточно просты в реализации.
Важно также исследовать работу готового компилятора при трансляции типовых программ и сделать обобщающие выводы о способах оптимизации программ для некоторого класса исходных языков и объектных машин.
Кроме того, промышленный компилятор должен удовлетворять противоречивым требованиям на разных этапах создания программного обеспечения.
В процессе отладки пользовательской программы необходима ее частая и, следовательно, быстрая компиляция, а качество получаемого кода не имеет большого значения. И, наоборот, после отладки программы важно получить в результате ее компиляции эффективную рабочую программу.
Так как оптимизация компилируемой программы требует дополнительных расходов машинного времени и памяти, то целесообразно иметь два режима компиляции: яеоптимизирующий (с быстрой компи-ляцией) и оптимизирующий (с получением эффективного рабочего кода).
В диссертационной работе обсуждаются также вопросы эффективной реализации основных расширений языка Паскаль [б]. Введение этих расширений не затрагивает реализацию традиционной части языка.
Стоит отметить, что некоторые расширения Паскаля, прежде всего явная спецификация шага итеративного цикла, помимо придания языку новых качеств и улучшения наглядности программы, дают возможность компилятору получать более эффективные рабочие программы.
Цели работы. Основными целями диссертационной работы были разработка оптимизирующих алгоритмов и их использование при создании Паскаль-компилятора для ЦП.
К быстродействию вычислительных систем, работающих на ЦП, предъявляются повышенные требования. Поэтому основным показателем степени оптимизируемости рабочей программы было выбрано время ее выполнения.
Наибольший эффект при минимизации времени выполнения программы дает оптимизация циклов. В Паскаль-компиляторе применялись следующие виды оптимизации циклов: вынос инвариантов из циклов; оптимизация индуктивных вычислений; буферизация циклов; использование команды "конец цикла".
Следующим по значимости параметром оптимизации для ЦП является экономия памяти, занимаемой кодом и переменными программы. Для экономии программного кода использовались следующие оптимизации: однократное программирование эквивалентных вычислений; вычисление константных конструкций; устранение избыточных операторов присваивания и ряд других оптимизаций [15].
Алгоритм распределения переменных в памяти построен таким образом, чтобы экономия памяти достигалась не за счет потерь в эффективности работы. Этому способствовала четырехформатная адресация ЦП [2]. -14-Обычно Паскаль-компилятор для быстродействующей ЭВМ с большой памятью реализуют по однопроходовой схеме [39] . В этом случае достигается высокая скорость компиляции за счет минимизации числа обращений ко вторичной памяти. Что касается качества кода, то предполагается, что на большинстве ЭВМ реализация конструкций Паскаля будет достаточно эффективной, и не потребуется интенсивной оптимизации для улучшения кода.
Очевидно, что компилятор, построенный по однопроходовой схеме, будет отличаться высокой скоростью трансляции, но, в общем случае, невысоким качеством объектного кода. Поскольку при создании Паскаль-компилятора для ЦП ставилась задача получить оптимизирующий компилятор, то для реализации этого компилятора была выбрана нестандартная трехпроходовая схема с промежуточным кодом, которая включает в себя следующие фазы работы компилятора: синтаксический анализ, машинно-независимую оптимизацию и генерацию объектного кода (последняя фаза проводится совместно с машин-но-зависимой оптимизацией).
В терминах промежуточного кода производится машинно-независимая оптимизация. Этот же код поступает на вход генератора объектного кода. Поэтому структура промежуточного кода максимально приспособлена для проведения фаз оптимизации и генерации объектного кода.
Указанная схема позволяет разделить машинно-независимую и машинно-зависимую оптимизации, а также легко организовать в компиляторе оптимизирующий и неоптимизирующий режимы трансляции (в последнем случае фаза машинно-независимой оптимизации отсутст-вует).
Выбор такой схемы компиляции объясняется еще одной причиной: предполагается в дальнейшем использовать отлаженный синтаксический оптимизатор и машинно-независимый оптимизатор при реализации -15-їїаскаль-компиляторов для других машин. В этом случае дополнительно потребуется создание лишь генератора объектного кода для конкретной ЭВМ.
Методы исследования. При разработке Паскаль-компилятора широко использовались результаты теории компиляции и теории графов [8,9,63]. Употреблялись также такие методы программирования, как методы поиска, организации информационных структур и т.д.
Большое значение имели принципы структурного программирования, использовавшиеся как при проектировании компилятора в целом, так и при детальной разработке его отдельных частей.
Научная новизна.
Предложена и реализована в Паскаль-компиляторе для ЦП АС-6 схема смешанной оптимизации программ: синтаксическая оптимизация регулярных циклов, внутри которых отсутствуют операторы перехода и EXIT , и локальная оптимизация программы.
Предложен универсальный промежуточный код, приспособленный для оптимизации и генерации объектного кода. Этот код представляет собой композицию синтаксического графа потока управления программы и списков триад линейных блоков и отличается компактностью, что способствует компиляции больших программ. Кроме того, структура этого кода лучше отвечает требованиям оптимизации, чем Паскаль-код (псевдокод для виртуальной Паскаль-машины, часто используемый в качестве выходного кода мобильных Паскаль-компиляторов) .
Предложены и реализованы методы эффективной реализации расширений языка Паскаль, таких как: параметризация типов данных; введение шага в итеративном цикле. -16-4. Введены в язык Паскаль машинно-зависимые структурные типы данных: MACHINE RECORD и MACHINE ARRАУ для реализации машинно-зависимых процедур компилятора, например, подпрограммы генерации загрузочного модуля. Это позволило свыше 95$ объема компилятора написать на Паскале и тем самым облегчило его перенос с одной ЭВМ на другую.
Практическая ценность. Разработан и реализован Паскаль-компилятор для ЦП АС-6, который обеспечивает получение рабочих программ, не уступающих программам, тщательно составленным вручную на автокоде. Компилятор прошел испытания и в настоящее время находится в эксплуатации в ИПМ АН СССР, в/ч 73790 и ЦНИИМАШ.
Опыт разработки, а также методы оптимизации могут быть использованы при разработке компиляторов для современных ЭВМ.
Апробация. Результаты диссертационной работы докладывались на следующих конференциях и семинарах: на Конференции молодых ученых и специалистов НИИ "Дельта", 1981; на 2-ой Всесоюзной Конференции "Автоматизация производства и проектирования прикладных программ и трансляторов", апрель 1983, г.Таллин; на семинаре "Архитектуры ЭВМ и численные методы", отдел вычислительной математики АН СССР, март 1984.
Диссертация состоит из 6 глав.
В первой главе анализируются основные методы оптимизации программ. Описывается структура Паскаль-компилятора для ЦП.
Вторая глава посвящена рассмотрению вопросов машинно-независимой оптимизации.
В третьей главе описывается алгоритм комплексной линейной оптимизации, реализованный в Паскаль-компиляторе для ЦП.
Четвертая глава содержит основные сведения о машинно-зависимых оптимизациях. Там же описывается алгоритм машинно-зависимой оптимизации, использованный в Паскаль-компиляторе.
В пятой главе анализируются результаты исследования работы компилятора при компиляции типовых тестов.
Шестая глава посвящена описанию реализации расширений Паскаля.
В заключении излагаются вывода, полученные на основе реализации и эксплуатации Паскаль-компилятора для ЦП АС-б.
Публикации. На тему диссертации опубликовано 4 работы.
ГМВА ПЕРВАЯ АНАЛИЗ ОСНОВНЫХ МЕТОДОВ ОПТИМИЗАЦИИ ПРОГРАММ
I.I. Оптимизация циклов.
I.I.I. Циклы - ключевые места при оптимизации программы.
К быстродействию больших вычислительных систем типа "ЦП + программное обеспечение" предъявляются повышенные требования. Увеличение быстродействия программных компонент, написанных, например, на Паскале, достигается с помощью их олтшлизации. Поэтому представляется необходимым выделить такие способы оптимизации, которые дают наибольший вклад в ускорение выполнения программ.
Очевидно, что ключевыми местами программы по уменьшению времени ее выполнения являются циклы. Исследования динамики выполнения ФОРТРАН-программ [14] показали, что 4$ кода потребляют 50$ времени выполнения программ. Основную долю от этих 4% кода составляют внутренние циклы.
Действительно, устранение избыточных вычислений или замена медленных вычислений на более быстрые в многократно повторяющихся участках программы резко ускоряет программу. Это подтверждает следующая статистика:
I. В компиляторе ФОРЕКС [II] реализована линейная оптимизация и оптимизация только внутренних циклов, каждый из которых целиком состоит из одного линейного блока. Кроме того, оптимизации подвергаются только явные циклы.
Тем не менее, такая сравнительно ограниченная оптимизация циклов дает существенный выигрыш в ускорении счета программ на типовых тестах (см.Приложение la). На указанных тестах коэффициент ускорения достигает 6. 8 при сравнении времен выполнения оптимизированных и неоптимизированных вариантов этих тестов.
2. Кнут исследовал влияние различных способов оптимизации на 17 типовых фортраяовских программах [ 14 J . Эти программы оп тимизировались вручную в соответствии со следующими уровнями оптимизации: - неоптимизирующий уровень; - локальная оптимизация; - машинно-независимая глобальная оптимизация и оптимизация циклов; - машинно-зависимая оптимизация применительно к IDm- 360; - максимально возможный уровень оптимизации.
В Приложении 16 приведена таблица относительных ускорений выполнения тестов для каждого уровня опттшзации. Из этой таблицы видно, что большое ускорение дает оптимизация 2-го уровня, которая включает в себя оптимизации циклов.
3. Исследование работы описываемого компилятора в оптимизи рующем режиме показало (см.главу 5), что оптимизация циклов вно сит существенный вклад в ускорение рабочих программ.
I.I.2. Основные виды оптимизации циклов.
1.1.2.1. Вынос инвариантов из тела цикла. Вычисления, вхо дящие в состав тела цикла, называются инвариантными, если их значения не изменяются на протяжении всего действия цикла.
Для ускорения работы цикла эти вычисления могут быть вынесены из тела цикла в так называемый предзаголовок. В этом пред-заголовке вынесенные вычисления будут проведены один раз, а внутри тела цикла результаты этих вычислений будут многократно использоваться.
1.1.2.2. Оптимизация индуктивных вычислений. Индуктивными называются такие вычисления в итеративном цик ле, которые имеют вид: где I - параметр цикла; СІ, 02 - инварианты цикла.
Так как индуктивные вычисления изменяются в цикле по закону арифметической прогрессии, то можно ввести новый индуктивный параметр цикла Л . В предзаголовке цикла этому параметру присваивается начальное значение ± CI Io + С2, а в конце цикла он увеличивается на инвариантное значение + CI J (Io - начальное значение параметра цикла, Ь - шаг цикла).
Существо такой оптимизации состоит в замене относительно медленной операции умножения на более быструю операцию сложения. Эта оптимизация используется для ускорения обращений к массивам в теле итеративного цикла, так как для вычисления индексного смещения элемента массива необходима операция умножения.
Стоит заметить также, что такая оптимизация приводит к экономии команд перезагрузок регистров в Щ, так как для индекс-регистров, с помощью которых осуществляется индексация в ЦП, есть команды сложения и вычитания, но нет команды умножения.
Основные виды оптимизаций циклов: вынос инвариантов и устранение индуктивных вычислений - были введены Жиром в 1965 году [16] . Более сложные формы подобных оптимизаций описываются ілленом [Ї7] , Лоури и Медлоком [18] , Алленом, Коком и Кеннеди
I.1.2.3. Уменьшение числа параметров в цикле.
Если в теле итеративного цикла используется только новый индуктивный параметр, то целесообразно заменить собственный параметр цикла на этот индуктивный параметр. В этом случае уменьшается количество вычислений в..теле цикла. І.І.2.4. Расширение возможностей итеративного цикла в
Паскале. В стандартном Паскале шаг изменения параметра итеративного цикла должен быть равен ± I. Такое ограничение в Паскале необосновано, так как очень часто удобно использовать другой шаг изменения параметра. Поэтому в качестве расширения языка предлагается следующая спецификация шага параметра в заголовке итеративного цикла [53 : FOR П«2 ТО 10 5ТЕР I DO
В этом цикле параметр будет принимать значения от 2 до 10 с шагом 2.
Описываемое расширение Паскаля,помимо придания языку новых качеств, дает возможность компилятору получать более эффективные рабочие программы.
1.1.2.5. Буферизация циклов. Многие вычислительные машины имеют быстрый буфер команд. Если цикл целиком помещается в этом буфере, то при его выполнении не требуется сравнительно медлен ная выборка команд из памяти.
К сожалению, в ЦП размер буфера команд составляет всего 4 слова, поэтому буферизации могут подвергаться только короткие циклы.
1.1.2.6. Использование команды "конец цикла". В ЦП итера тивные циклы целесообразно реализовывать с помощью команда "конец цикла" с целью уменьшения числа выполняемых команд в цикле [II] .
1.2. Сравнительная характеристика локальной и глобальной оптимизаций.
I.2.I. Основные методы экономии памяти программы. Вторым по значению параметром оптимизации (применительно к ЦП) является объем памяти, занимаемой кодом программы и ее переменными. Экономия программного кода приводит также к уменьшению времени выполнения программы пропорционально размеру этого кода, если считать, что все команда выполняются за одинаковое время и в программе нет циклов.
Приведем перечень основных видов машинно-независимых оптимизаций для экономии программного кода: однократное программирование эквивалентных вычислений [Ю, 15] ; вычисление во время компиляции программных конструкций, состоящих из одних констант; распространение констант [10, 15] ; устранение избыточных операторов присваивания [10] ; вынос эквивалентных вычислений из разветвляющихся конструкций [15] и некоторые другие виды оптимизаций [15, 55].
Машинно-зависимые оптимизации по уменьшению кода применительно к регистровым машинам, например, ЦП основываются прежде всего на экономии команд перезагрузок регистров. Правильно выбранная стратегия распределения регистров приводит к существенному уменьшению размера кода, а также к экономии времени выполнения программы [15].
Кроме того, для каждой машины имеются вспомогательные виды оптимизаций (см.4.9).
1.2.2. Характеристика линейной оптимизации.
Все известные алгоритмы линейной оптимизации отличаются простотой и малыми накладными расходами [10, 15].
В главе 3 будет показано, что рассматриваемая линейная оптимизация является быстрым однопроходовым процессом преобразования промежуточного представления программы. Дополнительно используются две программные структуры, небольшие по объему, так как размеры линейного блока, как правило, невелики.
1.2.3. Характеристика методов глобальной оптимизации. 1.2.3.1. Анализ потока управления и анализ потока данных. Анализ потока управления (АПУ) заключается в построении улравлягащего графа программы (ЯП) и его последующем анализе с целью: выявления абстрактных циклов [15, 17, 18, 20] ; упорядочения УІЇЇ для проведения итеративных алгоритмов анализа потока данных [12, 15] ; разбиения УІЇЇ на последовательность производных графов для проведения интервальных алгоритмов анализа потока данных [15, 20, 22, 23] .
Анализ потока данных (АІЇД) выявляет зависимость между данными в различных точках УГЇЇ. Примером задачи АПД является нахождение доступных выражений [12, 15, 24],
Выражение называется доступным в некоторой точке программы, если на любом пути от начального узла УІЇЇ до этой точки содержится вычисление этого выражения, причем значение выражения не меняется с момента последнего вычисления на этом пути. ^^^1^^^ начальный узел УҐЛ нет переопределений А и В
Подобная информация используется для экономии эквивалентных вычислений.
1.2.3.2. Нахождение доступных выражений.
Для иллюстрации методов АПД кратко рассматривается задача нахождения доступных выражений. Все определения, обозначения и алгоритм взяты из [12, 15] .
Будем считать, что линейный блок отбрасывает выражение А ор В, если в этом блоке имеется изменение А или В и нет последующего перевычисления А ор В. Кроме того, блок генерирует выражение А ор В, если в этом блоке имеется вычисление А ор В и нет последующих переопределений А и В.
Пусть.U - множество всех выражений, используемых в программе. Вводятся следующие множества для каждого блока:
INU - множество выражений из и , доступных в начале блока; оиты - множество выражений, доступных в конце блока; KILLCnl - множество выражений, отбрасываемых блоком;
6ENCK1 - множество выражений, генерируемых блоком.
Если выражения в U пронумеровать, то указанные множества можно представлять в виде битовых строк. Множества KILLLnl и 6ENM целесообразно определять во время линейной оптимизации для каждого блока.
Тогда решение задачи нахождения доступных.выражений сводится к решению сП уравнений, где П - число узлов в УТЛ;
01Я№Мп1 -KILLLnl +(з№пЪ(ам всех шов,
Ткіг -I л лі ітг -і КРОМЕ НАЧАЛЬНОГО) INLnl» ПОЫТСр];
ДА* &СЄХ УЗЛОв, ПРЕДШЕСТВУЮЩИ* УЗЛУ Я начальный узел
Итеративное решение этой системы уравнений состоит в проходе по всем узлам графа (начиная с начального) и применении к ним указанных уравнений. Stot процесс продолжается до тех пор, пока значение множества IN L Л J для каждого узла УГП не перестанет меняться.
В [I5~i показывается, что этот процесс всегда приводит к максимальному решению системы. Скорость сходимости этого процесса зависит от вида графа и порядка его обхода.
Кроме итеративных методов, существуют еще и интервальные метода ІШД [Ї5, 20, 22, 23] . Интервальные методы применимы только к сводимым графам. Для несводимых графов имеется технология расщепления узлов, чтобы преобразовать их к сводимым [9,25].
1.2.3.3. Оценка времени сходимости алгоритмов ІШД.
Время работы алгоритмов АПД зависит от числа проходов по . УШ, необходимых для достижения сходимости.
Пусть УШ - сводимый граф. Если из этого графа удалить все обратные ребра (см.определение в I.3.I.), то граф останется без циклов. Для такого графа в [12] вводится параметр зацеплеяяости как наибольшее число обратных ребер в пути без циклов в УШ.
В [24] показано, что для такого графа простой итеративный алгоритм требует не более d+i проходов по УШ, причем еще один проход необходим для того, чтобы убедитьоя в сходимости.
1.2.3.4. Оценка влияния глобальной оптимизации.
В [26] описан оптимизирующий компилятор с языка SIM PL, в котором отсутствует оператор перехода. Измерения уменьшения кода при проведении глобальной оптимизации для этого компилятора дали всего I * 4% (см. Приложение 2).
В [26] это объясняется тем, что программирование на структурном языке дисциплинирует пользователя. Связи между блоками программы становятся очевидными, и программисты сами устраняют избыточные вычисления.
Но, наверное, главная причина, объясняющая полученные результаты, заключается в другом. SIM PL является процедурно-ориентированным языком, а все обращения к процедурам, которых много в программе, оцениваются грубо (учитываются только побочные эффекты). Лишь глобальная оптимизация в рамках всей программы вместе с решением задач межпроцедурного АЇЇД дадут необходимый -26-вклад в увеличение эффективности рабочих программ [31, 32, 60]
В свете результатов, полученных для языка SIM PL , можно сделать такие выводы: для Паскаля, который является также процедурно-ориентированным языком и допускает использование оператора перехода, глобальная оптимизация в рамках всей программы очень сложна, а глобальная оптимизация в рамках одной подпрограммы недостаточно эффективна. Поэтому при реализации Паскаль-компилятора для ЦП было решено ограничиться локальной оптимизацией и оптимизацией структурных циклов. Эти оптимизации просты в реализации и дают существенный вклад в ускорение программ.
1.3. Оптимизация в рамках регулярного графа.
I.3.I. Абстрактные циклы.
Оптимизация циклов имеет большое значение (см.1.1). Но какой фрагмент программы можно считать циклом? Неформально, циклом является любой многократно повторяющийся участок программы.
В [15] предлагается формализация понятия цикла на базе следующих определений: узел п доминирует над узлом р , если всякий путь в УШ от начального узла до р проходит через п ; если п доминирует над р , то ребро р-»п называется обратным.
Тогда абстрактный цикл для обратного ребра -*п определяется как множество узлов в УШ, над которыми доминирует узел П , причем любой путь от этих узлов к р не проходит через П.. Узел п называется заголовком цикла.
Алгоритм обнаружения в УШ таких циклов описан в [15, 18] и используется в компиляторе ФОРТРАН-Н . Важно отметить, что обнаружение абстрактных циклов и особенно их оптимизация достаточно трудоемки и тесно связаны с задачами АПД в рамках всей прог- раммы. Поэтому целесообразно найти пути упрощения задачи оптимизации циклов.
1.3.2. Переход от абстрактного ЯП к синтаксическому УТЛ.
Паскаль является структурированным языком, так как синтаксическая структура Паскаль-процедуры достаточно полно специфицирует граф потока управления этой процедуры. Так, например, все структурные циклы FOR, WHILE и REPEAT - выявляются на этапе синтаксического анализа и могут быть отмечены в УТЛ.
Кроме того, в УГП могут быть отображены и другие структурные операторы. Такой УГП называется синтаксическим.
В синтаксическом УГП циклы, организованные с помощью оператора перехода, не учитываются.
1.3.3. Последовательный вынос инвариантных вычислений из вложенных циклов.
Регулярным графом называется такой подграф синтаксического УГП, который не содержит внутри себя операторов Шх EXIT. Отсутствие этих операторов значительно упрощает решение задач МД [26, 28, 29, 30] .
Структурированность Паскаля и правильно выбранная дисциплина программирования позволяют писать программы с минимальным количеством нерегулярностей. Поэтому частота появления регулярных циклов в правильно составленных программах должна быть большой.
Для всякого линейного блока можно составить список выражений, операнды которых не меняются в этом блоке. Такие выражения называются инвариантами блока.
Определив затем множество инвариантных выражений для самых вложенных подграфов, можно, используя интервальный метод АЩ и переходя от более вложенных подграфов к менее вложенным, опреде- лить инвариантные выражения для всего регулярного графа.
Таким способом можно выносить инвариантные выражения из вложенных циклов, что должно привести к значительному ускорению работы программы.
Для графов, не являющихся циклами, такое перемещение кода приводит к экономии эквивалентных вычислений. В более общем виде задача выноса общих выражений из разветвляющихся структур как обратная задача АИД решается в [15] .
1.4. Виды оптимизирующих компиляторов.
1.4.1. Оптимизирующий компилятор с промежуточным кодом. Фазы синтаксического анализа, оптимизации и генерации объектного кода в компиляторе могут быть как совмещены, так и разъединены. Наиболее удачной представляется такая схема работы компилятора: I) синтаксический анализ; 2) оптимизация; 3) генерация объектного кода.
В этой схеме исходная программа во время синтаксического анализа преобразуется в некоторое внутреннее представление, называемое промежуточным кодом. Структуру этого кода можно сделать максимально удобной для проведения любого вида оптимизации.
В терминах промежуточного кода проводится машинно-независимая оптимизация. Машинно-зависимая оптимизация обычно совмещается с фазой генерации кода.
Такая схема позволяет построить компилятор, который может воспринимать программы, написанные на разных языках и генерировать объектный код для разных машин. Авторы компилятора ФОРТРАН-ЇЇ рекомендуют для многоязыковой системы использовать машинно-зависимый промежуточный код для проведения более тщательной оптимизации на всех уровнях [18] .
1.4.2. Оптимизация на исходном языке.
Оптимизатор на исходном языке и принимает на вход, и выдает на выход программы, составленные на исходном языке. Разделение фаз оптимизации и трансляции дает ряд следующих преимуществ: не требуется разработка специального промежуточного языка; разработка и реализация оптимизатора и компилятора могут проводиться раздельно; результат работы оптимизатора на исходном языке легко анализировать, что упрощает отладку как самого оптимизатора, так и готовых программ; оптимизатор на исходном языке можно перенести на другую машину, на которой уже имеется компилятор с исходного языка.
Но подобный оптимизатор имеет и существенные недостатки: с машинно-независимой оптимизацией в терминах исходного языка трудно увязать последующие машинно-зависимые оптимизации, в первую очередь, экономию команд перезагрузки регистров; пара "оптимизатор + компилятор" работает медленнее, чем оптимизирующий компилятор, что связано с двукратным проведением лексического и синтаксического анализа программы.
Характеристика оптимизаторов на исходном языке основывается на опытных данных по их реализации [12, 33] .
1.4.3. Синтаксический оптимизатор.
Существует два уровня оптимизации программ: низкий'(абстракт-ный) и высокий (синтаксический) [28, 29, 30, 58] .
Абстрактный оптимизатор оперирует с абстрактным УШ, причем различают глобальную и локальную оптимизации [15] . Абстрактная оптимизация была создана прежде всего для улучшения ФОРТРАН-лрограмм, в которых часто используется оператор перехода, например, для образования условных циклов.
Для структурированных языков, в которых запрещен оператор перехода, применяется синтаксическая оптимизация [26] . Исходным материалом для синтаксического оптимизатора является дерево грамматического разбора, или синтаксический УТЛ. Процесс синтаксической оптимизации напоминает синтаксический разбор программы методом рекурсивного спуска и состоит из двух проходов по УГП[26].
Оптимизирующие подпрограммы применяются к соответствующим узлам УШ, начиная с программы и кончая ее подвыражениями. Благодаря такой технологии, локальная и глобальная оптимизации объединяются в один процесс.
Дяя языков, в которых разрешен оператор перехода, но предполагается его редкое использование, созданы новые методы синтаксической оптимизации, например, метод атрибутов [30]. В этом случае глобальная оптимизация носит итеративный характер и приближается к абстрактной.
1.4.4. Покадровая оптимизация.
При покадровой оптимизации преобразованиям подвергаются обособленные фрагменты программы. Назначение такой оптимизации-использовать дополнительные возможности улучшения кода, которые могут быть упущены в обобщенных алгоритмах оптимизации. При покадровой оптимизации в основном учитываются особенности объектных машин. Типичными примерами покадровых оптимизаций являются: - экономия команд переходов, генерируемых при компиляции структурных операторов; - замена возведения в квадрат на умножение и т.д. 1.5. Выбор схемы для построения оптимизирующего
Паскаль-компилятора.
I.5.I. Классическая методика реализации Паскаль-компилятора.
В [39] (1971г.) автор языка Паскаль Н.Вирт утверждал, что для эффективного Паскаль-компилятора на быстродействующей ЭВМ с большой памятью наиболее приемлема однопроходовая схема кдмпиля-ции. В этом случае достигается высокая скорость компиляции за счет минимизации числа обращений ко вторичной памяти.
Дяя обеспечения однопроходовой компиляции Вирт ввел специальные директивы предопределений [7]
Что касается качества кода, то Вирт считал, что на большинстве ЭВМ реализация конструкций Паскаля будет достаточно эффективной, и не потребуется интенсивной оптимизации для улучшения кода. В первом компиляторе Паскаля проводятся лишь вычисления константных выражений и отдельные покадровые оптимизации [39] .
В настоящее время Паскаль получил очень широкое распространение, и для многих больших систем он является базовым языком. На всех промышленных Паскаль-компиляторах используется сложная технология оптимизации [45, 46, 47} .
1.5.2. Компилятор с универсальным промежуточным кодом.
Мобильные Паскаль-компиляторы обычно используют в качестве выходного кода универсальный Паскаль-код (П-код). П-код является псевдокодом в форме обратной польской записи и рассчитан для выполнения на виртуальной стековой Паскаль-машине [41, 42, 43, 44] .
П-код спроектирован таким образом, что программу на этом коде можно легко перевести на язык загрузки любой известной ЭВМ [41] .
С течением времени П-код модифицировался. Известны три версии этого кода: П-4-код (стандарт), П-код университета в Сан-Диего (используется для малых ЭВМ) и П-код Лос-Аламосской лаборатории (спроектирован как промежуточный язык для Крей-1) [45] .
В [4б] обосновывается необходимость расширения П-кода для его использования в качестве промежуточного языка оптимизации. Этот язык назван универсальным П-кодом (УП-код).
УП-код используется в Лос-Аламосской лаборатории (для Крей-1) и в Лоуренсовской лаборатории (для Стар-ІОО). В последнем случае УП-код является промежуточным языком и для ФОРТРАН- компилятора.
В [46] утверждается (без доказательств), что УП-код лучше триадного промежуточного кода и годится для проведения всех известных оптимизаций.
При реализации Паскаль-компиляторов успешно используют и другие виды промежуточного кода. Так, например, в [47] описан многопроходовой оптимизирующий компилятор для расширенного Паскаля, который генерирует код для трех машин: 1иП - 370, J 1 990 и II 980 и в качестве промежуточного кода использует мультиплеты.
1.5.3. Схема реализации Паскаль-компилятора для Ш.
Паскаль-компилятор для ЦП проектировался как промышленный компилятор. Такой компилятор должен удовлетворять противоречивым требованиям на разных этапах создания программного обеспечения.
В процессе отладки программы необходима ее частая и, следовательно, быстрая компиляция, а качество кода не имеет большого значения. И, наоборот, после отладки важно получить эффективную рабочую программу.
Так как при оптимизации программы требуются дополнительные расходы времени и памяти, то целесообразно иметь два режима работы компилятора: яеоптимизирующий (с быстрой компиляцией) и оптимизирующий (с получением эффективной рабочей программы).
Поэтому для Паскаль-компилятора на ЦП выбрана 3-х проходовая схема с промежуточным кодом рис.1. Схема Паскаль-компилятора для ЦП
Стандартный Паскаль допускает использование оператора перехода, поэтому к Паскаль-программам нельзя применять обычную синтаксическую оптимизацию. В рассматриваемом компиляторе выбрана смешанная стратегия оптимизации: локальная оптимизация для всех блоков и синтаксическая оптимизация для регулярных циклов.
По этой причине промежуточный код представляет собой композицию синтаксического графа потока управления и описателей блоков в виде списков триад. Стоит отметить, что структура этого промежуточного кода лучше отвечает поставленным задачам оптимизации, чем машинно-зависимый П-код.
Уменьшение числа параметров в цикле
Основные виды оптимизации циклов. Вынос инвариантов из тела цикла. Вычисления, вхо дящие в состав тела цикла, называются инвариантными, если их значения не изменяются на протяжении всего действия цикла.
Для ускорения работы цикла эти вычисления могут быть вынесены из тела цикла в так называемый предзаголовок. В этом пред-заголовке вынесенные вычисления будут проведены один раз, а внутри тела цикла результаты этих вычислений будут многократно использоваться.
Оптимизация индуктивных вычислений. Индуктивными называются такие вычисления в итеративном цик ле, которые имеют вид: где I - параметр цикла; СІ, 02 - инварианты цикла.
Так как индуктивные вычисления изменяются в цикле по закону арифметической прогрессии, то можно ввести новый индуктивный параметр цикла Л . В предзаголовке цикла этому параметру присваивается начальное значение ± CI Io + С2, а в конце цикла он увеличивается на инвариантное значение + CI J (Io - начальное значение параметра цикла, Ь - шаг цикла).
Существо такой оптимизации состоит в замене относительно медленной операции умножения на более быструю операцию сложения. Эта оптимизация используется для ускорения обращений к массивам в теле итеративного цикла, так как для вычисления индексного смещения элемента массива необходима операция умножения.
Стоит заметить также, что такая оптимизация приводит к экономии команд перезагрузок регистров в Щ, так как для индекс-регистров, с помощью которых осуществляется индексация в ЦП, есть команды сложения и вычитания, но нет команды умножения.
Основные виды оптимизаций циклов: вынос инвариантов и устранение индуктивных вычислений - были введены Жиром в 1965 году [16] . Более сложные формы подобных оптимизаций описываются ілленом [Ї7] , Лоури и Медлоком [18] , Алленом, Коком и Кеннеди
Уменьшение числа параметров в цикле. Если в теле итеративного цикла используется только новый индуктивный параметр, то целесообразно заменить собственный параметр цикла на этот индуктивный параметр. В этом случае уменьшается количество вычислений в..теле цикла.
Расширение возможностей итеративного цикла в Паскале. В стандартном Паскале шаг изменения параметра итеративного цикла должен быть равен ± I. Такое ограничение в Паскале необосновано, так как очень часто удобно использовать другой шаг изменения параметра. Поэтому в качестве расширения языка предлагается следующая спецификация шага параметра в заголовке итеративного цикла [53 : FOR П«2 ТО 10 5ТЕР I DO В этом цикле параметр будет принимать значения от 2 до 10 с шагом 2. Описываемое расширение Паскаля,помимо придания языку новых качеств, дает возможность компилятору получать более эффективные рабочие программы.
Буферизация циклов. Многие вычислительные машины имеют быстрый буфер команд. Если цикл целиком помещается в этом буфере, то при его выполнении не требуется сравнительно медлен ная выборка команд из памяти.
К сожалению, в ЦП размер буфера команд составляет всего 4 слова, поэтому буферизации могут подвергаться только короткие циклы. Использование команды "конец цикла". В ЦП итера тивные циклы целесообразно реализовывать с помощью команда "конец цикла" с целью уменьшения числа выполняемых команд в цикле [II] . Сравнительная характеристика локальной и глобальной оптимизаций.
Основные методы экономии памяти программы. Вторым по значению параметром оптимизации (применительно к ЦП) является объем памяти, занимаемой кодом программы и ее переменными. Экономия программного кода приводит также к уменьшению времени выполнения программы пропорционально размеру этого кода, если считать, что все команда выполняются за одинаковое время и в программе нет циклов.
Устранение избыточных операторов присваивания
Эквивалентными называются вычисления, которые имеют одинаковую форму представления в языке и все операнды которых не изменяются на участке между этими вычислениями.
В примере I эквивалентными вычислениями являются вычисления фактических параметров А + В. После их обнаружения ОАГ трансформируется таким образом, чтобы вычисление А + В проводились один раз, а ссылки на это вычисление были из двух мест графа (см.рис.2б).
Для поиска эквивалентных вычислений типа А + В и В + А нужно но время синтаксического анализа программы проводить лереупо-рядочивание операндов выражения, используя коммутативные и ассоциативные законы, причем в некотором определенном порядке. Тогда в промежуточном коде, в рамках которого проводится оптимизация, форма представления этих вычислений будет одинаковой.
Если возможная перестановка операндов выражения может привести к разным результатам вычислений на объектной машине, то программист должен заключать непереставляемое вычисление в скобки, например, (А-С) + В. Поэтому Паскаль-компилятор для ЦП не раскрывает скобки в выражениях, тем самым предоставляя программистам возможность строить свои вычисления на пределе точности объектной машины.
Указаяный способ отключения оптимизирующих преобразований заимствован из ФОРТРАНА: "Процессор может использовать любую математически эквивалентную форму, однако целостность скобок не должна нарушаться" [34] .
В 1959 г. Шеридан [6Ї] предлагал выделять сегменты в выражении, в которых можно переставлять операнды.
Свертка вычислений, состоящих из одних констант. Вычисление, состоящее из одних констант, может быть проведено во время компиляции программы с целью экономии времени ее выполнения.
В примере I вычисление 12 х 13 можно заменить на константу 156. Подобная оптимизация называется сверткой вычисления. Свертка позволяет также не делать некоторых вычислений вручную, а возложить их на компилятор. Устранение избыточных операторов присваивания. Если в блоке имеется оператор присваивания, а переменная, которая стоит в левой части этого оператора, используется в последующих операторах блока, то полезно произвести такую трансформацию ОАГ - а: в каждом операторе, следующем за указанным оператором присваивания, заменить все использования изменяемой переменной на значения присваиваемого операнда.
Такая трансформация ОАГ - а способствует поиску эквивалентных вычислений в блоке. Проиллюстрируем это на примере:
В Как видно из примера 2, после замены использования переменной Т на переменную А, появляются два эквивалентных вычисления А В в первом и третьем операторах.
Более того, если далее в блоке имеется еще оператор присваивания той же переменной, то предыдущий оператор присваивания после указанной трансформации становится избыточным и, следовательно, может быть устранен из блока (как, например, второй one-ратор присваивания из примера 2). Заметим, что при такой оптимизации исключается лишь занесение результата вычисления правой части оператора присваивания в переменную.
Оптимизации, опирающиеся на конкретные значения операндов. Существуют оптимизации, опирающиеся на конкретные значения операндов и свойства операций. Приведем примеры подобных оптимизаций: Выделение постоянной составляющей в индексном выражении.
Во время синтаксического анализа любое выражение упорядочивается таким образом, чтобы выделить переменную и постоянную его части, например: в примере I.
Если выражение является индексом при выборе элемента массива, то постоянная часть выражения после вычисления может быть добавлена в смещение объектной команды. Экономия эквивалентных вычислений с учетом использования операций отношения.
Особый интерес представляют оптимизации операций отношения, которые входят в состав выражений Паскаля. Любой операции отно -39 шения соответствуют два действия: сравнение операндов и выделение соответствующего признака отношения как результата сравнения этих операндов.
Для операций отношения результаты выполнения команд сравнения являются ненужными. Но если, например, после операции отношения в блоке следует другая операция, эквивалентная по семантике действию сравнения тех же операндов, что и в операции отношения, то вместо выполнения последней операции можно использовать готовый результат сравнения операндов.
Перестановка вещественных и целых операндов
В промежуточном коде используются адресные триады 4-х видов: ADRARR.ADRPOINT.VAL.FADR. Для триады выборки элемента массива, имеющей оператор -63 ADRARR f содержимое переменной - базы массива несущественно, так как формируемый адрес определяется только: - предыдущей адресной выборкой; - относительным смещением базы массива; - значением индексного выражения.
Поэтому вычисление в jiL для такой триады содержит оператор ADRARR, порядковые номера предыдущей адресной триады и индексного выражения, а также ссылку на базу массива (поля PNRSTR , PNRVAR первого операнда вычисления). Значения этих полей учитываются при поиске эквивалентных триад.
Для триад ADR POINT и VAL содержимое переменной определяет значение соответственно устанавливаемого адреса или выбираемого значения. Следовательно, вычисление для такой триады содержит оператор и порядковые номера предыдущей адресной выборки и переменной.
Для формирования адреса переменной при передаче ее в качестве параметра по ссылке используется триада с оператором Г A UK. Вычисление такой триады содержит оператор, порядковый номер предыдущей адресной триады, а также ссылку на описатель переменной в TABSTR (во втором операнде вычисления).
Особенности поиска эквивалентных обращений к стандартным функциям. Обращение к функции в рамках промежуточного кода представляется следующей последовательностью триад: - триада начала обращения: D Г/1 D С / ссылка на описание ч, DtU YV , \ функции в TABSTR ; (этой триаде в Ш соответствуют команды формирования базы параметров и установки маски сохранения всех регистров); последовательность триад вычисления значений фактических параметров и триад присваивания, которые соответствуют в ІЩ командам записи значений фактических параметров в программный магазин; - триада конца обращения: R AI DF / ссылка на описание v DnLrr » Хфункции в TABSTR (для этой триады генерируется команда передачи управления подпрограмме - функции с запоминанием адреса возврата).
В данной работе рассматривается поиск только эквивалентных обращений к стандартным функциям. Для каждого такого обращения формируется вычисление, которое имеет следующие атрибуты: - оператор BALPF и ссылку на описание функции в TABSTR в поле PNRSTR ; - перечень порядковых номеров фактических параметров указан ного обращения. При нахождении эквивалентного вычисления в jI С последняя триада обрабатываемого обращения к функции увязывается в цепочку эквивалентных триад (см.2.4.2).
Остальные триады обращения к функции уничтожаются (переходят в состояние "пусто" При этом необходима коррекция цепочек эквивалентностей, в которые могли быть увязаны эти триады и другие триады блока,
В случае же отсутствия эквивалентного вычисления производится запись в J ГС вычисления, соответствующего данному обращению к функции.
Заметим, что в Паскале соответствие между фактическими и формальными параметрами в обращении к подпрограмме всегда позиционное. Это обстоятельство облегчает поиск эквивалентных обращений к функциям.
Обработка операторов присваивания простым переменным. При первом использовании переменной в блоке (в этом случае значение порядкового номера переменной меньше минимально допусти мого для данного блока) производится ее нормализация. С перемен ной связывается очередной порядковый номер, чтобы отличать ее от других переменных. В поле ТА65Т описателя переменной за писывается значение 51 Г J I , что соответствует исходному сос тоянию переменной. В этом состоянии значение переменной не опре делено. . Поле BIТCHANuL описателя переменной принимает значение FALSE . Это означает, что переменная пока не меняла свое значение в блоке. В поле 5ETTR записывается 0.
Состояние переменной изменяется, если ей присваивается некоторое значение. В промежуточном коде оператор присваивания представляется группой триад, причем последней в этой группе является триада присваивания:
При обработке триады присваивания простой переменной производится перенос состояния присваиваемого операнда изменяемой переменной. В этом случае с переменной связывается порядковый номер присваиваемого операнда, а описатель переменной принимает состояние присваиваемого операнда.
Генерация команд для линейных блоков в компиляторе ФОРЖС
При запросе арифметического регистра может оказаться, что свободного регистра соответствующего формата нет. В этом случае один из занятых регистров освобождается путем выталкивания его содержимого во временную память.
Какого бы формата не был запрашиваемый регистр, во временную лаглять всегда выталкивается весь словный регистр,в состав которого входит запрашиваемый регистр.При этом свободным объявляется только запрашиваемый регистр,а для остальных операндов,расположенных на словном регистре, образуются дополнительные состояния-"временная память".Выталкивание производится одной командой.
Длина блока, как правило, невелика, поэтому избыточность в использовании временной памяти не должна сказываться.
2. Чем больше операндов содержит регистр, тем менее он пред почтителен для освобождения путем выталкивания его содержимого во временную память. Это объясняется тем, что в этом случае для всех операндов освобождаемого регистра более приоритетное регистровое состояние заменяется на "временную память". И, наоборот, из двух регистров, имеющих формат меньше слов-ного и содержащих одинаковое число операндов, предпочтение для освобождения отдается тому регистру, который расположен на слов-ном регистре с большим числом операндов. В этом случае при выталкивании во временную память всего словного регистра образуются дополнительные состояния "временная память" для большего числа операндов, не входящих в состав освобождаемого регистра.
3. При реализации простого и достаточно эффективного на практике алгоритма распределения регистров удобно ввести универ сальную характеристику занятости регистра операндами - вес регист ра. Вес регистра зависит от следующих величин: - количества операндов на регистре; - числа использования этих операндов в последующих триадах блока; - форматов регистровых операндов. Для простоты предлагается определять вес регистра как сумму всех использований операндов на регистре в последующих триадах блока.
4. Если арифметический регистр занят сверху, то есть другим операндом большего формата, то он не совсем удобен для освобожде ния, так как в этом случае требуется освобождать регистр большего формата.
5. Описание алгоритма.
1. Если при запросе регистра окажется, что один из регистров запрашиваемого формата свободен (или, в случае запроса конкретного регистра, свободен именно запрашиваемый регистр), то этот регистр и выделяется для использования.
2. Если требуемого свободного регистра нет, то производится разбор отдельных ситуаций:
а) если запрашиваемый регистр - словный арифметический, то освобождается (путем выталкивания его содержимого во временную память) либо конкретно запрашиваемый регистр, либо регистр с ми нимальным весом. Заметим, что из двух регистров с одинаковым ми нимальным весом и одним операндом выбирается тот, операнд которо го не используется в блоке наиболее долгое время (принцип Биледи);
б) в случае запроса арифметического регистра-сумматора не словного формата сначала выбирается соответствующий регистр с максимальным весом (либо конкретно запрашиваемый регистр).
Затем делается попытка освободить выбранный регистр путем его выталкивания в свободный дополнительный регистр (именно поэтому и выбирался регистр с максимальным весом, чтобы сохранить побольше регистровых состояний).
Если свободного дополнительного регистра нет, то выбирается регистр-сумматор с минимальным весом для последующего выталкивания в память содержимого всего словного регистра.
Для ускорения работы алгоритма поиск всех видов регистров производится за один проход. 3. Если производится запрос дополнительного арифметического регистра, то выбирается среди всех доступных регистров дополни тельный регистр искомого формата с минимальным весом.
