Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 18
Текст из файла (страница 18)
Вовтором случае представление проще и унифицированней.Некоторые формы промежуточного представления лучше годятсядля различного рода оптимизаций (например, косвенные тройки - дляперемещения кода), некоторые - хуже (например, префиксная запись дляэтого плохо подходит).114Глава 8. Генерация кодаЗадача генератора кода - построение эквивалентной машинной программыпо программе на входном языке. Обычно в качестве входного длягенератора кода служит некоторое промежуточное представлениепрограммы.
В свою очередь, генерация кода состоит из рядаспецифических, относительно независимых подзадач: распределениепамяти (в частности, распределение регистров), выбор команд, генерацияобъектного (или загрузочного) модуля. Конечно, независимость этихподзадач относительна: например, при выборе команд нельзя не учитыватьсхему распределения памяти, и, наоборот, схема распределения памяти(регистров, в частности) необходимо ведет к генерации той или инойпоследовательности команд. Однако удобно и практично эти задачи все жеразделять и при этом особо обращать внимание на их взаимодействие.В какой-то мере схема генератора кода зависит от формыпромежуточного представления.
Ясно, что генерация кода из дереваотличается от генерации кода из троек, а генерация кода из префикснойзаписи отличается от генерации кода из ориентированного графа. В то жевремя все генераторы кода имеют и много общего и основныеприменяемые алгоритмы отличаются, как правило, только в деталях,связанных с используемым промежуточным представлением.В дальнейшем в качестве промежуточного представления мы будемиспользовать префиксную нотацию и алгоритмы генерации кода будемизлагать в виде атрибутных схем со входным языком Лидер.8.1. Модель машиныПри изложении алгоритмов генерации кода мы будем следовать некотороймодели машины, в основу которой положена система командмикропроцессора Motorola 68020.В системе команд используются следующие способы адресации:D - значение находится в регистре данных;А - значение находится в адресном регистре;POST - пост-инкрементная адресация (А)+: исполнительный адрес естьзначение адресного регистра и после исполнения команды значениеэтого регистра увеличивается на длину операнда;115PRE - пре-инкрементная адресация -(А): перед исполнением операциисодержимое адресного регистра уменьшается на длину операнда,исполнительный адрес равен новому содержимому адресногорегистра;DIRECT - прямая адресация через регистры: исполнительный адресравензначениювыраженияADDREG+INDEXREG*SCALE+ADDRDISP - содержимое адресного регистра + содержимоеиндексного регистра, умноженное на SCALE+адресное смещение;INDPPRE - пре-косвенная через память: (ADDREG+INDEXREG*SCALE+ADDRDISP)+INDEXDISP - выражение в скобках дает адресячейки, содержимое которой + индексное смещение даетисполнительный адрес;INDPOST - пост-косвенная через память: (ADDREG+ADDRDISP)+INDEXREG*SCALE+INDEXDISP - выражение в скобках даетадрес ячейки, содержимое которой + содержимое индексногорегистра, умноженное на SCALE + индексное смещение, даетисполнительный адрес;DIRPC - прямая через PC (счетчик команд): исполнительный адресопределяется выражением PC+INDEXREG*SCALE+ADDRDISP;INDPREPC - пре-косвенная через PC: (PC+INDEXREG* SCALE+ADDRDISP)+INDEXDISP - то же, что INDPRE, но в качествеадресного регистра исползуется PC;INDPOSTPC - пост-косвенная через PC: (PC+ADDRDISP)+INDEXREG*SCALE+INDEXDISP то же, что и INDPOST, но в качествеадресного регистра используется PC;ABS - абсолютная;IMM - непосредственный операнд.В дальнейшем изложении будут использованы следующие команды:MOVEA ИА,А - загрузить содержимое по исполнительному адресу ИАна адресный регистр А;MOVE ИА1,ИА2 - содержимое по исполнительному адресу ИА1переписать по исполнительному адресу ИА2;MOVEM список регистров,ИА - сохранить указанные регистры в памятипо адресу ИА;MOVEM ИА,список регистров - восстановить указанные регистры изпамяти по адресу ИА;116LEA ИА,А - загрузить исполнительный адрес ИА на адресный регистрА;MUL ИА,D - умножить содержимое по исполнительному адресу ИА насодержимое регистра данных D и результат разместить в D;ADD ИА,D - сложить содержимое по исполнительному адресу ИА ссодержимым регистра данных D и результат разместить в D;SUB ИА,D - вычесть содержимое по исполнительному адресу ИА изсодержимого регистра данных D и результат разместить в D;CMP ИА,D - содержимое регистра данных D вычитается изсодержимого по исполнительному адресу ИА, при этомформируется признак результата, но содержимое регистра D неменяется;TST ИА - выработать код условия по значению, находящемуся поисполнительному адресу ИА;BNE ИА - условный переход по признаку NE (не равно) поисполнительному адресу ИА;BEQ ИА - условный переход по признаку EQ (равно) поисполнительному адресу ИА;BLE ИА - условный переход по признаку LE (меньше или равно) поисполнительному адресу ИА;BGT ИА - условный переход по признаку GT (больше) поисполнительному адресу ИА;BLE ИА - условный переход по признаку KE (меньше или равно) поисполнительному адресу ИА;BLT ИА - условный переход по признаку LT (меньше) поисполнительному адресу ИА;BR ИА - безусловный переход по адресу ИА;JSR ИА - переход с возвратом на подпрограмму по адресу ИА;JMP ИА - безусловный переход по исполнительному адресу;RTD размер локальных - возврат из подпрограммы с указанием размералокальных;LINK A,размер локальных - в стеке сохраняется значение регистра А, врегистр А заносится указатель на это место в стеке и указатель стекапродвигается на размер локальных;UNLK A - стек сокращается на размер локальных и регистр Авосстанавливается из стека.1178.2.
Динамическая организация памятиРассмотрим схему реализации магазина периода выполнения дляпростейшего случая (как, например, в языке Паскаль), когда всепеременные в магазине (фактические параметры и локальные переменные)имеют известные при трансляции смещения. Магазин служит дляхранения локальных переменных (и параметров) и обращения к ним вязыках, допускающих рекурсивные определения процедур.
Еще однойзадачей, которую необходимо решать при трансляции языков с блочнойструктурой - обеспечение реализации механизмов статическойвложенности. Рассмотрим рекурсивную программу рис. 8.1.PROCEDURE P1;VAR V1;PROCEDURE P2;VAR V2;BEGIN P2;V1:=...V2:=...END P2;BEGIN P2;END P1;Рис. 8.1P2V2P2V2P1V1Рис. 8.2В процессе выполнения этой программы в магазине может сложитьсяситуация, изображенная на рис. 8.2. Находясь в процедуре P2, мы должныиметь доступ к последнему экземпляру значений переменных процедурыP2 и к экземляру значений переменных процедуры P1, из которой былавызвана P2.
Кроме того, необходимо обеспечить восстановлениесостояния программы при завершении выполнения процедуры.Мы рассмотрим две возможные схемы динамической организациипамяти: схему со статической цепочкой и с дисплеем в памяти. В первомслучае все статические контексты связаны в список, который называетсястатической цепочкой; в каждой записи для процедуры в магазинехранится указатель на запись статически охватывающей процедуры(помимо, конечно, указателя динамической цепочки - указателя на "базу"динамически предыдущей процедуры).
Использование той или инойсхемы определяется, помимо прочих условий, прежде всего числомадресных регистров.1188.2.1. Организация магазина со статической цепочкойМинимальный адресСохраненныерегистрыТекущийстатическийуровеньЛокальныеОбластьDisp последнейBP вызваннойпроцедурыDispПредыдущий BPТочка возвратаФакт. параметрыСохраненныерегистрыПредыдущий LPПредыдущийстатическийуровеньLPЛокальныеПредыдущий BP.............etaDlМаксимальный адресРис. 8.3Итак, в случае статической цепочки магазин организован, какэто изображено на рис.
8.3.Таким образом, на запись текущей процедуры в магазине указываетрегистр BP (Base pointer), с которого начинается динамическая цепочка.На статическую цепочку указывает регистр LP (Link Pointer). В качестверегистров BP и LP в различных системах команд могут использоватьсяуниверсальные, адресные или специальные регистры. Локальныепеременные отсчитываются от регистра BP вверх, фактические параметры- вниз с учетом памяти, занятой точкой возврата и самим сохраненнымрегистром BP.Вызов подпрограмм различного уровня производится несколько поразному. При вызове подпрограммы того же статического уровня, что ивызывающая подпрограмма, выполняются следующие команды:Занесение фактических параметров в магазинJSR AКоманда JSR A продвигает указатель SP, заносит PC на верхушку магазинаи осуществляет переход по адресу A.
После выполнения этих команд119состояние магазина становится таким, как это изображено на рис. 8.4.Занесение BP, отведение локальных, сохранение регистров делаетвызываемая подпрограмма.Точка возвратаSPФакт. параметрыСохраненныерегистрыLPПредыдущий LPПредыдущийстатическийуровеньЛокальныеBPПредыдущий BP................Рис. 8.4При вызове локальной подпрограммы необходимо установить указательстатического уровня на текущую подпрограмму, а при выходе восстановить его на старое значение (охватывающей текущую). Для этогоисполняются следующие команды:Занесение фактических в магазинMOVE BP,LPSUB Delta,LPJSR AЗдесь Delta - размер локальных вызывающей подпрограммы плюс двойнаядлина слова. Магазин после этого принимает состояние, изображенное нарис.
8.5. Предполагается, что регистр LP уже сохранен среди сохраняемыхрегистров, причем самым первым (сразу после локальных переменных).После выхода из подпрограммывыполняется командаввызывающейподпрограммеMOVE (LP),LPкоторая восстанавливает старое значение статической цепочки. Есливыход осуществлялся из подпрограммы 1-го уровня, эту командувыполнять не надо, поскольку для 1-го уровня нет статической цепочки.120Точка возвратаФакт. параметрыСохраненныерегистрыПредыдущий LPПредыдущийстатическийуровеньЛокальныеПредыдущий BPLPDetal.................Рис. 8.5При вызове подпрограммы меньшего, чем вызывающая, уровнявыполняются следующие команды:Занесение фактических параметров в магазинMOVE (LP),LP /*столько раз, какова разностьуровней вызывающей и вызываемой ПП*/JSR AТем самым устанавливается статический уровень вызываемойподпрограммы.
После выхода из подпрограммы выполняется командаMOVE -Delta(BP),LPвосстанавиливающая статический уровень вызывающей подпрограммы.Тело подпрограммы начинается со следующих команд:LINK BP,-размер локальныхMOVEM -(SP)Команда LINK BP,размер локальных эквивалентна трем командам:MOVE BP,-(SP)MOVE SP,BPADD -размер локальных,SPКоманда MOVEM сохраняет в магазине регистры.В результате выполнения этих команд магазин приобретает вид,изображенный на рис. 8.3.121Выходизподпрограммыпоследовательностью команд:осуществляетсяследующейMOVEM (SP)+UNLK BPRTD размер фактическихКоманда MOVEM восстанавливает регистры из магазина. После еевыполнения магазин выглядит, как это изображено на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
