А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 127
Текст из файла (страница 127)
Мы также полагаем, что были выявлены все синтаксические и статические семантические ошибки, выполнены все необходимые проверки типов, так что необходимые операторы преобразования типов находятся на своих местах. Таким образом, стадия генерации кода может работать в предположении, что ее вход не содержит ошибок. бЛО Глава 8. Генерация кода 8.1.2 Целевая программа Архитектура набора команд целевой машины существенно влияет на сложность разработки хорошего генератора кода, дающего высококачественный машинный код. Наиболее распространенными архитектурами являются К1ЯС (гедисед 1пьчгнсбоп зе[ сошрцгег — компьютер с сокращенным набором команд), СБС (сотр1ех 1пз1гцсбоп зеГ сошриГег — компьютер со сложным набором команд) и стековая. КБС-машина обычно имеет много регистров, трехадресные команды, простые режимы адресации и относительно простой набор команд.
С1БС-машины, напротив, имеют мало регистров, двухадресные команды, множество режимов адресации, несколько классов регистров, команды переменной длины и команды с побочными действиями. В стековых машинах операции выполняются путем внесения операндов в стек с последующим выполнением операций над операндами на вершине стека. Для достижения высокой производительности вершина стека обычно хранится в регистрах.
Стековых машин практически не осталось, поскольку стековая организация слишком ограничена и требует слишком большого количества операций обмена и копирования. Однако стековая архитектура ожила с появлением виртуальной машины )ага ()ача Ч)гша! МасЬ)пе — 1ЧМ). УЧМ представляет собой программный интерпретатор байт-кода 5ача, промежуточного языка, выдаваемого компиляторами 1ача.
Интерпретатор обеспечивает многоплатформенную совместимость программ, основной фактор успеха 1ака. Для преодоления снижения производительности из-за интерпретации, которое может достигать 10 раз, были созданы оперативные 1)цзг-1пмппе — ЛТ) компиляторы 1ача.
Такие компиляторы во время выполнения программы транслируют байткод в машинные команды целевого компьютера. Еще один способ повышения производительности 1ака состоит в создании компилятора, который выполняет компиляцию непосредственно в машинные команды, минуя стадию байт-кода. Генерация абсолютной программы на машинном языке имеет то преимущество, что она может быть помещена в фиксированное место в памяти и тут же выполнена.
Программа может быть быстро скомпилирована и выполнена. Генерация переносимой программы на машинном языке (часто именуемой объектным модулем (оЬ)есг шобц!е)) обеспечивает возможность раздельной компиляции подпрограмм. Набор переместимых объектных модулей может быть скомпонован в одно целое и загружен для выполнения. Ценой дополнительных действий по компоновке и загрузке объектных модулей мы получаем ~ибкое решение, которое допускает раздельную компиляцию подпрограмм и вызов из объектного модуля других ранее скомпилированных программ. Если целевая машина не обрабатывает перемещение автоматически, компилятор должен явно предоставить 621 8.!.
Вопросы проектирования генератора кода необходимую информацию загрузчику для компоновки отдельно скомпилированных модулей. Несколько проще получение в качестве выхода генератора программы на языке ассемблера. При этом можно генерировать символьные команды и использовать возможности макросов ассемблера при генерации кода. Платой за эту простоту является дополнительный шаг ассемблирования по окончании генерации кода. В этой главе мы будем рассматривать в качестве целевой машины очень простой К1БС-образный компьютер.
Мы добавим к нему некоторые С1ЯС-образные режимы адресации, чтобы иметь возможность одновременно рассмотреть и методы генерации кода для СБС-машин. Для удобочитаемости в качестве целевого будет использован язык ассемблера. Поскольку адреса могут быть вычислены из смещений и другой информации, хранящейся в таблице символов, генератор кода может производить переносимые или абсолютные адреса для имен так же легко, как и символьные адреса. 8.1.3 Выбор команд Генератор кода должен отобразить программу в промежуточном представлении на последовательность машинных команд, которые могут быть выполнены целевой машиной.
Сложность этого отображения определяется такими факторами, как ° уровень промежуточного представления; ° природа архитектуры набора команд; ° требуемое качество генерируемого кода. Если используется высокоуровневое промежуточное представление, то генератор кода может транслировать каждую инструкцию промежуточного представления в последовательность машинных команд с использованием шаблонов кода.
Однако генерация кода инструкция за инструкцией зачастую дает низкокачественный код, требующий дальнейшей оптимизации. Если промежуточное представление отражает некоторые низкоуровневые особенности машины, то генератор кода может использовать эту информацию для генерации более эффективной последовательности команд.
Природа набора команд целевой машины сильно влияет на сложность выбора инструкций. Например, важными факторами являются единообразие и полнота набора команд. Если целевая машина не поддерживает единообразно все типы данных, то каждое исключение из общего правила требует отдельной обработки.
На некоторых машинах, например, операции с числами с плавающей точкой выполняются с использованием отдельных регистров. 622 Глава 8. Генерация кода Другими важными факторами являются скорость выполнения команд и идиомы языка целевой машины. Если мы не беспокоимся об эффективности целевой программы, выбор инструкций достаточно прост.
Для каждого типа трехадресных инструкций можно разработать шаблон целевого кода, генерируемого для данной конструкции. Например, каждая трехадресная инструкция вида х=у+я, где х, у и я распределяются статически, может быть транслирована в следующий код. //КО=у // КО = КО -ь я КО, у КО, КО, я (загрузка у в регистр КО) (прибавление я х КО) (сохранение КО в х) АРР //х=КО ЯТ х, КО Такая стратегия часто приводит к избыточным сохранениям и загрузкам. Например, последовательность трехадресных инструкций а = Ъ+ с с(= а+е будет транслирована в //КО=Ь // КО = КО + с // а = КО // КО = а // КО = КО + е // с(= КО 1Р КО, Ь АРР КО, КО, с ЯТ а, КО 1Р КО, а АРР КО, КО, е ЯТ д, КО // КО = а // КО = КО + 1 // а = КО 1Р КО, а АРР КО, КО, ()1 ЯТ а, КО Четвертая команда в данном случае совершенно излишня, поскольку она загружает значение, которое только что было сохранено; если в дальнейшем а не используется, то излишня и третья команда.
Качество сгенерированного кода обычно определяется его скоростью выполнения и размером. На большинстве машин заданная программа в промежуточном представлении может быть реализована множеством различных последовательностей кодов, существенно отличающихся друг от друга. Непосредственная простейшая трансляция промежуточного кода может, таким образом, давать корректный, но неприемлемо неэффективный код. Например, если целевая машина имеет команду инкремента (1МС), то трехадресная инструкция а=а+1 может быть более эффективно реализована одной командой 1ЫС а вместо обычной последовательности, состоящей из загрузки а в регистр, прибавления к регистру 1 и сохранения результата в а: 623 8,1. Вопросы проектирования генератора кода Для получения эффективной последовательности команд необходимо знать стоимость каждой команды; к сожалению, получить точную информацию зачастую весьма сложно.
Принятие решения о том, какая именно последовательность машинных команд наилучшим образом подходит для данной трехадресной конструкции, может потребовать также знания контекста, в котором появляется эта конструкция. В разделе 8.9 мы увидим, что такой выбор команд может быть смоделирован с использованием представления машинных команд и инструкций промежуточного представления в виде деревьев. Затем мы пытаемся "покрыть" дерево промежуточного представления множеством поддеревьев, соответствующих машинным командам.
Если каждому поддереву машинной команды назначить стоимость, то для генерации оптимальной последовательности команд можно использовать динамическое программирование. 8.1.4 Распределение регистров Ключевой проблемой при генерации кода является принятие решения о том, какие значения в каких регистрах должны храниться. Регистры представляют собой наиболее быстрые вычислительные модули целевой машины, но обычно их слишком мало, чтобы хранить все значения.
Значения, которые не хранятся в регистрах, должны находиться в памяти. Команды, использующие в качестве операндов регистры, обычно короче и выполняются быстрее, чем команды, работающие с операндами, расположенными в памяти. Следовательно, эффективное использование регистров — еще одна важная составляющая генерации хорошего целевого кода. Использование регистров часто разделяется на две подзадачи.
1. В процессе распределения регистров (ге81з1ег а!1осабоп) мы выбираем множество переменных, которые будут находиться в регистрах в каждой точке программы. 2. В последующей фазе назначения регистров (ге81а1ег аагййпгпеп1) мы выбираем конкретные регистры для размещения в них переменных. Поиск оптимального назначения регистров переменным представляет собой сложную задачу даже на машине с единственным регистром. Математически эта задача — 1ЧР-полная. Проблема усложняется еще и тем, что аппаратное обеспечение н/нлн операционная система целевой машины может накладывать дополнительные ограничения по использованию регистров.
Пример 8.1. Некоторые машины требуют для некоторых операндов и результатов операций пар регистров (регистра с четным номером и регистра со следующим за ним нечетным номером). Например, на некоторых машинах целочисленные 624 Глава 8. Генерация кода умножение и деление требуют использования пар регистров. Команда умножения, например, имеет вид М х, у Здесь сомножитель х представляет собой нечетный регистр пары, состоящей из четного и нечетного регистров, а сомножитель у может храниться в любом ре- гистре.
Произведение занимает пару из четного и нечетного регистров. Команда деления имеет вид 0 х, у Здесь делимое занимает пару регистров, четный регистр которой — х; у представляет собой делитель. После деления в четном регистре хранится остаток, а в нечетном — частное. Рассмотрим теперь две последовательности трехадресных кодов на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
