А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 126
Текст из файла (страница 126)
611-612. 8. Ргейе, б., "Вейп(узсЬг!й, а Топни!а !апйиайе, шог!е!ег! ирои йа! огай!)плебс, Гог риге 1Ьои8Ьг", (1879). 1п Я. чап Не!)епоогг, Ргот Рге8е го бог1е1, Нагчап1 (1п!ч. Ргеза, СашЪПг!Ке МА, 1967. 9. Ниг!зоп, К. 1,. апд 1. Е. В. Мова, "1псгешепга1 Сойесйоп оГ Мапзге ОЬ]есгз", Ргос. Тлг!.
Ког)сгйор оп Метогу Мала8етелй Ьесшге Ыогез !п СогприГег Яс]епсе 637 (1992), рр. 388-403. !О. 1оЬпзоп, Б. С. апг()3. М. К!ГсЬ)е, "ТЬе С !апйиайе сайш8 аейиепсе", Согприбпй Яс!епсе ТесЬп!са! Керог! 102, Вей ЬаЬогагойез, Мштау НП1 Ы, 1981. 616 Глава 7. Среды времени выполнения 11. Кппй, Р.
Е., Агг о7' Сотригег Рго8гаттт8, )Ъ!ите 1г Рипг1атеига! А18ог)йтю, АгМ)воп-%ев!еу, Вон!оп МА, 1968. 12. 1леЬеппап, Н. апд С. Нее)18 "А геа1-гппе 8агЬа8е со!!есгог Ьавег! оп йе Иег)гнев оГ оЬ!есгв", Сотт. АСМ 26;6 ()ппе, ! 983), рр. 419-429. 13. МсСагйу, У., "Кеснгяче йпсВопз оГ вугпЬо11с ехргевяопв апд гЬе)г согпрпгаЬоп Ьу гпасЬ!пе'*, Сотт. АСМ 3:4 (Арг., 1960), рр. 184 — 195. 14. МсСагйу, У., "Н!вГогу оГ1!вр.*' Бее рр. 173-185 !п К.
1..%ехе!Ыа1 (ест.), Оюхгогу о3 Рго8гаттт8 2ап8иа8ез, Асаг!епг!с Ргевв, Ыевг Уог1г, 1981. 15. М!пв!гу, М., "А 1.18Р 8агЬа8е со11есгог а18ог!1Ьгп пяп8 весопдагу яога8е", А. 1. Мепю 58, М1Т Рго!есГ МАС, СагпЬг)г!8е МА, 1963. 16. Капг!е11, В. апг! 1.. 1. Канве!1, А18о1 60!тр1етенгагГоп, Асаг!егп!с Ргевв, меч Уог)г, 1964. 17. %!!акоп, Р. К., "Ип)ргосеавог 8агЬа8е со!1есйоп гесЬпщпев'*, гср: Оггр. са. псехаа.ес!и/рпЫдагЬаде/Ьйдапгч.ра. ГЛАВА 8 Генерация кода Последней стадией нашей модели компиляции является генератор кода. Он получает на вход промежуточное представление исходной программы от начальной стадии компилятора и выводит эквивалентную целевую программу, как показано на рис. 8.1.
Исходная Начальная Промеауточнмй ' Оимимиаамир ' Про программа стадия код ходи Целевая рограмма Рнс. 8.1. Положение генератора кода в модели компилятора К генератору кода предъявляются жесткие требования. Получаемый код должен сохранять семантическое значение исходной программы и быть высококачественным, что означает эффективное использование доступных ресурсов целевой машины. Кроме того, эффективно должен работать и сам генератор кода. Математически проблема генерации оптимальной целевой программы для данной исходной является неразрешимой; многие из подзадач, встречающихся при генерации кода, таких как распределение регистров, вычнслительно трудноразрешимы.
На практике мы вынуждены довольствоваться эвристическими методами, генерирующими хороший, но не обязательно оптимальный код. К счастью, эти эвристики достаточно стары и проверены, так что тщательно разработанный генератор может давать код в несколько раз более быстрый, чем получаемый от простейшего генератора без их применения. Компиляторы, которые должны давать эффективные целевые программы, перед началом генерации кода включают фазу оптимизации. Оптимизатор превращает одно промежуточное представление в другое, из которого может быть сгенерирован более эффективный код. В общем случае фазы оптимизации и генерации кода, известные как заключительная стадия компилятора, могут выполнять несколько проходов по промежуточному представлению перед генерацией целевой программы.
Подробнее оптимизация кода рассматривается в главе 9. Представленные в данной главе методы могут как использовать оптимизацию перед началом генерации целевого кода, так и обходиться без нее. Перед генератором кода стоят три основные задачи: выбор команд, распределение и назначение регистров н упорядочение команд. Важность этих задач рассмат- 618 Глава 8. Генерация кода ривается в разделе 8.1. Выбор команд означает выбор машинных команд целевой машины для реализации инструкций промежуточного представления.
Распределение и назначение регистров означает принятие решения о том, какие значения в каких регистрах будут храниться. Упорядочение команд предусматривает принятие решения о том, в каком порядке должны выполняться сгенерированные команды. В этой главе приведены алгоритмы, которые генератор кода может использовать для трансляции промежуточного представления в последовательность команд целевого языка простой регистровой машины. Алгоритмы иллюстрируются с использованием описанной в разделе 8.2 модели машины.
В главе 10 проблема генерации кода рассматривается в применении к сложным современным машинам, поддерживающим параллельность на уровне отдельных инструкций. После основных вопросов разработки генераторов кода мы рассмотрим, какой целевой код должен генерироваться компилятором для поддержки абстракций, воплощенных в типичном исходном языке. В разделе 8.3 будут описаны реализация статических областей данных и выделение памяти для данных в стеке, а также показано, как имена в промежуточном представлении могут быть преобразованы в адреса в целевом коде. Многие генераторы кода разделяют команды промежуточного представления на базовые блоки (оаз1с Ыоск), состоящие из последовательности команд, которые всегда выполняются совместно. Разделение промежуточного представления на базовые блоки является темой раздела 8.4.
В следующем разделе приведены простые локальные преобразования, которые могут использоваться для превращения базовых блоков в модифицированные базовые блоки, из которых может генерироваться более эффективный код. Эти преобразования представляют собой рудиментарную форму оптимизации кода; более глубоко теория оптимизации не будет затрагиваться до главы 9. Примером практичной локальной трансформации может служить выявление общих подвыражений на уровне промежуточного кода, приводящее к замене арифметических операций более простыми операциями копирования. В разделе 8.6 представлен простой алгоритм генерации кода, который поочередно генерирует код для каждой инструкции, храня операнды в регистрах до тех пор, пока это возможно.
Выход такого генератора кода легко улучшается при помощи методов локальной оптимизации, подобных рассматриваемым в разделе 8.7. Оставшиеся разделы посвящены выбору команд и распределению регистров. 619 8.1. Вопросы проекгирования генератора кода 8.1 Вопросы проектирования генератора кода Такие задачи, как выбор команд, распределение регистров и упорядочение команд, стоят практически перед всеми генераторами кода, в то время как их конкретные детали зависят от промежуточного представления, целевого языка и системы времени выполнения.
Наиболее важным критерием оценки генератора кода является корректность получаюшегося кода. Корректность приобретает особую важность в связи с наличием массы частных случаев, с которыми может столкнуться генератор. При сверхприоритетности корректности получающегося кода генераторы кода должны проектироваться так, чтобы их можно было легко реализовывать, тестировать и поддерживать.
8.1.1 Вход генератора кода Входной поток генератора кода — это промежуточное представление исходной программы, полученное на начальной стадии компиляции, вместе с информацией в таблице символов, которая используется для определения адресов времени выполнения объектов данных, обозначаемых в промежуточном представлении именами. Имеется много вариантов промежуточных представлений, включая такие трех- адресные представления, как четверки, тройки, косвенные тройки; представление виртуальной машины, такое как байт-код или код стековой машины; линейное представление, например постфиксная запись; и графическое представление в виде синтаксических деревьев и ориентированных графов.
Многие алгоритмы в этой главе излагаются с использованием представлений, рассмотренных в главе 6,— трехадресных кодов, деревьев и графов. Методы, которые мы рассмотрим, применимы и к другим промежуточным представлениям. В этой главе мы считаем, что перед генерацией кода начальной стадией компиляции были выполнены сканирование, разбор и трансляция исходной программы в относительно низкоуровневое промежуточное представление, так что значения имен в промежуточном языке могут быть представлены величинами, с которыми целевая машина может работать непосредственно, такими, например, как целые числа и числа с плавающей точкой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
