CodeNet / Приложения / Алгоритмы / Разбор выражений. Компиляторы и интерпретаторы. / Лекции по конструированию компиляторов
Лекции по конструированию компиляторов - Глава 8. Генерация кода
Задача генератора кода - построение эквивалентной машинной
программы по программе на входном языке. Обычно в качестве
входного для генератора кода служит некоторое промежуточное
представление программы. В свою очередь, генерация кода
состоит из ряда специфических, относительно независимых
подзадач: распределение памяти (в частности, распределение
регистров), выбор команд, генерация объектного (или
загрузочного) модуля. Конечно, независимость этих подзадач
относительна: например, при выборе команд нельзя не учитывать
схему распределения памяти, и, наоборот, схема распределения
памяти (регистров, в частности) необходимо ведет к генерации
той или иной последовательности команд. Однако удобно и
практично эти задачи все же разделять и при этом особо
обращать внимание на их взаимодействие.
В какой-то мере схема генератора кода зависит от формы
промежуточного представления. Ясно, что генерация кода из
дерева отличается от генерации кода из троек, а генерация кода
из префиксной записи отличается от генерации кода из
ориентированного графа. В то же время все генераторы кода
имеют и много общего и основные применяемые алгоритмы
отличаются, как правило, только в деталях, связанных с
используемым промежуточным представлением.
В дальнейшем в качестве промежуточного представления мы
будем использовать префиксную нотацию и алгоритмы генерации
кода будем излагать в виде атрибутных схем со входным языком
Лидер.
8.1. Модель машины
При изложении алгоритмов генерации кода мы будем следовать
некоторой модели машины, в основу которой положена система
команд микропроцессора Motorola 68020.
В системе команд используются следующие способы адресации:
D - значение находится в регистре данных;
А - значение находится в адресном регистре;
POST - пост-инкрементная адресация (А)+: исполнительный
адрес есть значение адресного регистра и после исполнения
команды значение этого регистра увеличивается на длину
операнда;
PRE - пре-инкрементная адресация -(А): перед исполнением
операции содержимое адресного регистра уменьшается на
длину операнда, исполнительный адрес равен новому
содержимому адресного регистра;
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 ИА,список регистров - восстановить указанные регистры
из памяти по адресу ИА;
LEA ИА,А - загрузить исполнительный адрес ИА на адресный
регистр А;
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 - стек сокращается на размер локальных и регистр А
восстанавливается из стека.
8.2. Динамическая организация памяти
Рассмотрим схему реализации магазина периода выполнения для
простейшего случая (как, например, в языке Паскаль), когда все
переменные в магазине (фактические параметры и локальные
переменные) имеют известные при трансляции смещения. Магазин
служит для хранения локальных переменных (и параметров) и
обращения к ним в языках, допускающих рекурсивные определения
процедур. Еще одной задачей, которую необходимо решать при
трансляции языков с блочной структурой - обеспечение
реализации механизмов статической вложенности. Рассмотрим
рекурсивную программу рис. 8.1.
PROCEDURE P1; +----+
VAR V1; P2 | V2 |
PROCEDURE P2; |----|
VAR V2; |....|
BEGIN P2; |----|
V1:=... P2 | V2 |
V2:=... |----|
END P2; P1 | V1 |
BEGIN P2; +----+
END P1;
Рис. 8.1 Рис. 8.2
В процессе выполнения этой программы в магазине может
сложиться ситуация, изображенная на рис. 8.2. Находясь в
процедуре P2, мы должны иметь доступ к последнему экземпляру
значений переменных процедуры P2 и к экземляру значений
переменных процедуры P1, из которой была вызвана P2. Кроме
того, необходимо обеспечить восстановление состояния программы
при завершении выполнения процедуры.
Мы рассмотрим две возможные схемы динамической организации
памяти: схему со статической цепочкой и с дисплеем в памяти. В
первом случае все статические контексты связаны в список,
который называется статической цепочкой; в каждой записи для
процедуры в магазине хранится указатель на запись статически
охватывающей процедуры (помимо, конечно, указателя
динамической цепочки - указателя на "базу" динамически
предыдущей процедуры). Использование той или иной схемы
определяется, помимо прочих условий, прежде всего числом
адресных регистров.
8.2.1. Организация магазина со статической цепочкой
Минимальный адрес
+-----------------+| Предыдущий BP |-----+
v +-----------------+
................. Максимальный адрес
Рис. 8.3
Итак, в случае статической цепочки магазин организован, как
это изображено на рис. 8.3.
Таким образом, на запись текущей процедуры в магазине
указывает регистр BP (Base pointer), с которого начинается
динамическая цепочка. На статическую цепочку указывает регистр
LP (Link Pointer). В качестве регистров BP и LP в различных
системах команд могут использоваться универсальные, адресные
или специальные регистры. Локальные переменные отсчитываются
от регистра BP вверх, фактические параметры - вниз с учетом
памяти, занятой точкой возврата и самим сохраненным регистром
BP.
Вызов подпрограмм различного уровня производится несколько
по-разному. При вызове подпрограммы того же статического
уровня, что и вызывающая подпрограмма, выполняются следующие
команды:
Занесение фактических параметров в магазин
JSR A
Команда JSR A продвигает указатель SP, заносит PC на верхушку
магазина и осуществляет переход по адресу A. После выполнения
этих команд состояние магазина становится таким, как это
изображено на рис. 8.4. Занесение BP, отведение локальных,
сохранение регистров делает вызываемая подпрограмма.
+---------------+
|Точка возврата || Предыдущий BP |
|------------------|
|..................|
Рис. 8.8
Запоминание и восстановление DISPLAY[i] можно не выполнять,
если процедура не имеет локальных переменных и параметров или
если из процедуры нет вызовов описанных в ней процедур.
Структура магазина при использовании дисплея изображена на
рис. 8.8. Дисплей может быть реализован либо через регистры
(если их достаточно), либо через массив в памяти.
|----------------------| уровня |
| | Дисплей .......| BP 1-го статического уровня |
| | x---+---------> |
| |----------------| |
| | Точка возврата | |
| |----------------| |
| | Фактические | |
| |--+----------------+--|| Предыдущий BP |
|----------------|
| Дисплей |
|----------------|
| Точка возврата |
|----------------|
|--+ Фактические +--|
Рис. 8.9.
Иногда используется комбинированная схема - дисплей в магазине
(рис 8.9). Дисплей хранится в магазине. При вызове процедуры
текущего статического уровня он просто копируется в новую
область активации. При вызове процедуры более глубокого
статического уровня в дисплей добавляется указатель BP
вызывающей процедуры.
Отдельного рассмотрения требует вопрос о технике передачи
фактических параметров. Конечно, в случае простых параметров
(например, чисел) проблем не возникает. Однако передача
массивов по значению - операция довольно дорогая, поэтому с
точки зрения экономии памяти целесообразнее сначала в
подпрограмму передать адрес массива, а затем уже из
подпрограммы по адресу передать в магазин сам массив. В связи
с передачей параметров следует упомянуть еще одно
обстоятельство.
Рассмотренная схема организации магазина допустима только
для языков со статически известными размерами фактических
параметров. Однако, например, в языке Модула-2 по значению
может быть передан гибкий массив, и в этом случае нельзя
статически распределить память для параметров. Обычно в таких
случаях заводят так называемый "паспорт" массива, в котором
хранится вся необходимая информация, а сам массив размещается
в магазине в рабочей области выше сохраненных регистров.
8.3. Назначение адресов
Назначение адресов переменным, параметрам и полям записей
происходит при обработке соответствующих объявлений. В
однопроходном трансляторе это может производиться вместе с
построением основной таблицы символов и соответствующие адреса
(или смещения) могут храниться в этой же таблице. В
промежуточном представлении Лидер объявления сохранены, что
делает это промежуточное представление машинно-независимым.
Напомним, что в Лидер-представлении каждому описанию
соответствует некоторый номер. В процессе работы генератора
кодов поддерживается таблица Table, в которой по этому номеру
(входу) содержится следующая информация:
- для типа - его размер;
- для переменной - адрес;
- для поля записи - смещение внутри записи;
- для процедуры - размер локальных;
- для диапазона индексов массива - значение левой границы.
Функция IncTab вырабатывает указатель (вход) на новый элемент
таблицы, проверяя при этом наличие свободной памяти.
Таблица LevelTab - это таблица уровней процедур, содержащая
указатели на последовательно вложенные процедуры (см. рис.
4.9).
Для вычисления адресов определим для каждого объявления два
синтезируемых атрибута: DISP будет обозначать смещение внутри
области процедуры (или единицы компиляции), а SIZE - размер.
Тогда семантика правила для списка объявлений принимает вид
RULE
DeclPart ::= ( Decl )
SEMANTICS
Disp:=0;
1A: Disp:=Disp+Size;
Size:=Disp.
Это можно следующим образом изобразить на дереве объявлений
(рис. 8.10).
DeclPart | Size Disp--------->Disp
+ Size + Size + Size
^ ^ ^
| | |
Рис. 8.10
Все объявления, кроме объявлений переменных, имеют нулевой
размер. Размер объявления переменной определяется следующим
правилом:
RULE
Decl ::= 'VAR' TypeDes
SEMANTICS
var Entry:Tablentry;
0: Entry:=IncTab;
Size:=((Table[VAL]+1) DIV 2)*2;
{ Выравнивание на границу слова }
Table[Entry]:=Disp+Size.
В качестве примера трансляции определения типа рассмотрим
обработку описания записи:
RULE
TypeDes ::= 'REC' ( TypeDes ) 'END'
SEMANTICS
var Disp:word;
Temp:Tablentry;
0: Entry:=IncTab;
Disp:=0;
2A: begin Temp:=IncTab;
Table[Temp]:=Disp;
Disp:=Disp+Table[Entry]+1) div 2)*2;
{ Выравнивание на границу слова }
end;
Table[Entry]:=Disp.
8.4. Трансляция переменных.
Переменные отражают все многообразие механизмов доступа в
языке. Переменная имеет синтезированный атрибут ADDRESS - это
запись, описывающая адрес в команде МС68020. Этот атрибут
сопоставляется всем нетерминалам, представляющим значения. В
системе команд МС68020 много способов адресации, и они
отражены в структуре значения атрибута ADDRESS, имеющего
следующий тип:
Register=
(D0,D1,D2,D3,D4,D5,D6,D7,A0,A1,A2,A3,A4,A5,A6,SP,NO);
AddrType=record
AddrMode:(D,A,Post,Pre,Direct,IndPre,IndPost,
DirPC,IndPrePC,IndPostPC,Abs,Imm);
Addreg,IndexREG:Register;
IndexDisp,AddrDisp:cardinal;
Scale:1..8;
end;
Значение регистра NO означает, что соответствующий регистр в
адресации не используется.
Доступ к переменным осуществляется в зависимости от их
уровня: глобальные переменные адресуются с помощью абсолютной
адресации; переменные процедуры текущего уровня адресуются
через регистр базы А6.
Если стек организован с помощью статической цепочки, то
переменные предыдущего статического уровня адресуются через
регистр статической цепочки А5; переменные остальных уровней
адресуются "пробеганием" по статической цепочке с
использованием вспомогательного регистра. Адрес переменной
формируется при обработке структуры переменной слева направо и
передается сначала сверху вниз как наследуемый атрибут
нетерминала VarTail, а затем передается снизу-вверх как
глобальный атрибут нетерминала Variable. Таким образом,
правило для обращения к переменной имеет вид (первое вхождение
Number в правую часть - это уровень переменной, второе - ее
Лидер-номер):
RULE
Variable ::= VarMode Number Number VarTail
SEMANTICS
var Temp:integer;
AddrTmp1,AddrTmp2:AddrType;
3: if (Val=0) then { Глобальная переменная }
Address.AddrMode:=Abs;
Address.AddrDisp:=0;
else { Локальная переменная }
Address.AddrMode:=Direct;
if (Val=Level) then
{ Переменная текущего уровня }
Address.Addreg:=A6
elsif (Val=Level-1) then
{ Переменная предыдущего уровня }
Address.Addreg:=A5;
else Address.Addreg
:=GetFree(RegSet);
with AddrTmp1 do
AddrMode=Direct;
Addreg=A5;
IndexReg=No;
AddrDisp=0;
end;
Emit2(MOVEA,AddrTmp1,Address.Addreg);
AddrTmp1.Addreg;=Address.Addreg;
AddrTmp2.AddrMode=A;
AddrTmp2.Addreg=Address.Addreg;
for Temp:=Level-Val do
Emit2(MOVEA,AddrTmp1,AddrTmp2)
end end;
if (Val=Level) then
Address.AddrDisp:=Table[Val]
else Address.AddrDisp:=Table[Val]
+Table[LevelTAB[Val]].
end end.
Функция GetFree выбирает очередной свободный регистр (либо
регистр данных, либо адресный регистр) и отмечает его как
использованный в атрибуте RegSet нетерминала Block. Процедура
Emit2 генерирует двухадресную команду. Первый параметр этой
процедуры - код команды, второй и третий параметры имеют тип
Address и служат операндами команды (здесь для упрощения
изложения в качестве параметров этой процедуры используются
контрукции типа '(А)'; имеется в виду косвенная адресация
через адресный регистр). Смещение переменной текущего уровня
отсчитывается от базы (А6), а других уровней - от указателя
статической цепочки, поэтому оно определяется как
алгебраическая сумма LOCALSize и величины смещения переменной
(отрицательного!).
Если стек организован с помощью дисплея, то трансляция для
доступа к переменным может быть осуществлена следующим
образом:
RULE
Variable ::= VarMode Number Number VarTail
SEMANTICS
var Temp:integer;
3: if (Val=0) then { Глобальная переменная }
Address.AddrMode:=Abs;
Address.AddrDisp:=0;
else { Локальная переменная }
Address.AddrMode:=Direct;
if (Val=Level) then
{ Переменная текущего уровня }
Address.Addreg:=A6;
Address.AddrDisp:=Table[Val]
else with Address do
AddrMode=IndPost; Addreg:=NO; IndexREG:=NO;
AddrDisp:=DispLAY[Val];
IndexDisp:=Table[Val]
end end end.
Рассмотрим трансляцию доступа к полям записи. Она описывается
следующим правилом (Number - это Лидер-номер описания поля):
RULE
VarTail ::= 'FIL' Number VarTail
SEMANTICS
if (Address.AddrMode=Abs) then
Address.AddrMode:=Abs;
Address.AddrDisp
:=Address.AddrDisp+Table[Val];
else Address:=Address;
if (Address.AddrMode=Direct)
then Address.AddrDisp
:=Address.AddrDisp+Table[Val]
else Address.IndexDisp
:=Address.IndexDisp+Table[Val]
end end.
Смещение в случае абсолютной и прямой адресации определяется
полем AddrDisp, а в остальных случаях - полем IndexDisp. Таким
образом, видно, что при обработке полей записей идет только
накопление смещения поля без генерации каких-либо команд.
Атрибутные зависимости для этого правила могут быть
изображены следующим образом (рис. 8.11):
VarTail | Disp---------------+
| |
/ \ |
/ \ |
/ \ |
+--------Number VarTail | Disp | Disp |----------------+
|-------|
Рис. 8.11
Рассмотрим теперь выборку элемента массива. Лидер-синтаксис
обращения к элементу массива следующий:
VarTail ::= 'ARR' Number Typexpr VarTail
Здесь Number - Лидер номер описания диапазона индексов;
Typexpr - индексное выражение. По адресу левой части правила,
представляющей переменную-массив, от которого берется индекс,
и по индексному выражению, представленному нетерминалом
Typexpr, мы должны сформировать адрес элемента массива. В
приведенной ниже таблице решений функция GetAddr выбирает
очередной свободный адресный регистр.
Тип адресации VarTail левой части:
IndPre or Direct (IndPost or Abs) or
IndexReg=NO ((Direct or IndPre)
& (IndexRegNO))
---------------------------------------------------------
ElSize= | AddrDisp:= |AddrDisp:=
1,2,4,8 | AddrDisp |-Left*ElSize
AddrMode=D | -Left*ElSize |AddrMode:=IndPost
| Addreg:=Addreg|Addreg:=
| IndexReg:= |if Addreg рабочий
| Addreg |then Addreg
| AddrMode:=IndPost|else GetAddr
| Scale:=ElSize |IndexReg:=
| | Addreg
| |Scale:=ElSize
| |-------------------
| |LEA Address,
| | Address
---------------------------------------------------------
---------------------------------------------------------
ElSize | AddrDisp:= | AddrDisp:=
1,2,4,8 | AddrDIP- | -Left*ElSize
AddrMode=D| Left*ElSize | AddrMode:=IndPost
| Addreg:=Addreg| Addreg:=
| IndexReg:= | if Addreg рабочий
| Addreg | then Addreg
| Scale:=1 | else GetAddr
| AddrMode:=IndPost| IndexReg:=
|---------------------| Addreg
| MUL ElSize, | Scale:=1
| Addreg |-------------------
| | LEA Address,
| | Address
| | MUL ElSize,
| | IndexReg
---------------------------------------------------------
---------------------------------------------------------
ElSize= |AddrDisp:= | AddrDisp:=
1,2,4,8 |AddrDisp- | -Left*ElSize
AddrModeD|Left*ElSize | AddrMode:=IndPost
|Addreg:=Addreg| Addreg:=
|IndexReg:=GetFree| if Addreg рабочий
|AddrMode:=IndPost| then Addreg
|Scale:=ElSize | else GetAddr
|--------------------| IndexReg:=GetFree
|MOVE Address, | Scale:=ElSize
| IndexReg |-------------------
| | LEA Address,
| | Address
| | MOVE Address,
| | IndexReg
--------------------------------------------------------
---------------------------------------------------------
ElSize |AddrDisp:= | AddrDisp:=
1,2,4,8 |AddrDisp- | -Left*ElSize
AddrModeD|Left*ElSize | AddrMode:=IndPre
|Addreg:=Addreg| Addreg:=
|IndexReg:=GetFree| if Addreg рабочий
| AddrMode:=IndPre| then Addreg
| Scale:=ElSize| else GetAddr
|--------------------| IndexReg:=GetFree
|MOVE Address, | Scale:=1
| IndexReg |----------------
| MUL ElSize, | LEA Address,
| IndexReg | Address
| | MOVE Address,
| | IndexReg
| | MUL ElSize,
| | IndexReg
--------------------------------------------------------
Под "рабочим" регистром в таблице решений имеется в виду
регистр, значение которого может быть испорчено (примером "не
рабочего" регистра может служить регистр А6 или регистр А5,
если он используется как указатель процедуры предыдущего
статического уровня).
MaxReg - максимальный номер адресного регистра, которым
можно пользоваться как рабочим. Все адресные регистры
разделены на два множества: имеющие номера, большие MaxReg,
заняты предварительным распределением, остальные - рабочие.
Функция GetAddr выдает очередной свободный рабочий адресный
регистр. Приведенная таблица реализуется следующим правилом:
RULE
VarTail ::= 'ARR' Number Typexpr VarTail
SEMANTICS
Size:integer;
Flag:boolean;
AddrTmp1,AddrTmp2:AddrType;
Flag:= ((Address.AddrMode=IndPre)
or (Address.AddrMode=Direct))
and (Address.IndexReg=NO);
Size:=Table[Val];
if (Address.AddrMode=D)
then IndexReg:=Addreg
else IndexReg:=GetFree;
end;
AddrMode:=IndPre;
if Flag then
Address.AddrDisp
:=Address.AddrDisp
-Table[Val]*Size;
Addreg:=Addreg;
else Address.AddrDisp:=
-Table[Val]*Size;
if (Address.Addreg:=Addreg
else Addreg:=GetAddr;
end end;
if (Size in [2,4,8])
then Address.Scale:=Size)
else Address.Scale:=1;
end;
AddrTmp1.AddrMode:=D; AddrTmp1.Addreg:=IndexReg;
if Flag then Emit2(LEA,Address,Address) end;
if (Address.AddrModeD)
then Emit2(MOVE,Address,AddrTmp1);
end;
AddrTmp2.AddrMode:=IMM; AddrTmp2.AddrDisp:=ElSize;
if not (Size IN [1,2,4,8])
then Emit2(MUL,AddrTmp2,AddrTmp1);
end.
8.5. Трансляция целых выражений
Трансляция выражений различных типов управляется синтаксически
благодаря наличию указателя типа перед каждой операцией. Мы
рассмотрим некоторые наиболее характерные проблемы генерации
кода для выражений.
Система команд МС68020 обладает двумя особенностями,
сказывающимися на генерации кода для арифметических выражений
(то же можно сказать и о генерации кода для выражений типа
"множества"):
1) один из операндов выражения (правый) должен при
выполнении операции находиться на регистре, поэтому если оба
операнда не на регистрах, то перед выполнением операции один
из них надо загрузить на регистр;
2) система команд довольно "симметрична", т.е. нет
специальных требований к регистрам при выполнении операций
(таких, например, как пары регистров или требования четности и
т.д.).
Поэтому выбор команд при генерации арифметических выражений
определяется довольно простыми таблицами решений. Например,
для целочисленного сложения такая таблица приведена на
рис.8.12.
Правый операнд А2
R V
+-----------------------------+
Левый | R | ADD A1,A2 | ADD A2,A1 |
операнд |-----+-----------+-----------|
A1 | V | ADD A1,A2 | MOVE A1,R |
| | | ADD A2,R |
+-----------------------------+
Рис. 8.12
Здесь имеется в виду, что R - операнд на регистре, V - операнд
- переменная или константа. Такая таблица решений должна также
учитывать коммутативность операций. Эта таблица решений
реализуется следующим правилом:
RULE
IntExpr ::= 'PLUS' IntExpr IntExpr
SEMANTICS
if (Address.AddrModeD)
and (Address.AddrModeD) then
Address.AddrMode:=D;
Address.Addreg:=GetFree(RegSet);
Emit2(MOVE,Address,Address);
Emit2(ADD,Address,Address);
else if (Address.AddrMode=D) then
Emit2(ADD,Address,Address);
Address:=Address);
else Emit2(ADD,Address,Address);
Address:=Address);
end end.
8.6. Распределение регистров при вычислении арифметических
выражений
Одной из важнейших задач при генерации кода является
распределение регистров. Рассмотрим хорошо известную технику
распределения регистров при трансляции арифметических
выражений, называемую алгоритмом Сети-Ульмана.
Пусть система команд машины имеет неограниченное число
универсальных регистров, в которых выполняются арифметические
команды. Рассмотрим, как можно сгенерировать код, используя
для данного арифметического выражения минимальное число
регистров.
|
/ \
R1 /\ \
-- /\
R2 /\ \
-- /\
Rn /\ \
-- \
/\LR
L/\/\R
----
Рис. 8.13
Предположим сначала, что распределение регистров
осуществляется по простейшей схеме слева-направо, как
изображено на рис. 8.13. Тогда к моменту генерации кода для
поддерева LR занято n регистров. Пусть поддерево L требует nl
регистров, а поддерево R - nr регистров. Если nl=nr, то при
вычислении L будет использовано nl регистров и под результат
будет занят n+1-й регистр. Еще nr (=nl) регистров будет
использовано при вычислении R. Таким образом, общее число
использованных регистров будет равно n+nl+1.
Если nl>nr, то при вычислении L будет использовано nl
регистров. При вычислении R будет использовано nr=lr
Рис. 8.14 Рис. 8.15
2) если вершина имеет прямых потомков с метками l1 и l2, то
в качестве метки этой вершины выбираем большее из чисел l1 или
l2 либо число l1+1, если l1=l2.
Эта разметка позволяет определить, какое из поддеревьев
требует большего количества регистров для своего вычисления.
Затем осуществляется распределение регистров для результатов
операций.
Правила распределения регистров:
1) Корню назначается первый регистр.
2) Если метка левого потомка меньше метки правого, то левому
потомку назначается регистр на единицу больший, чем предку, а
правому - с тем же номером (сначала вычисляется правое
поддерево и его результат помещается в регистр R). Если же
метка левого потомка больше или равна метке правого потомка,
то наоборот, сначала вычисляется левое поддерево и его
результат помещается в регистр R (рис. 8.15). После этого
формируется код по следующим правилам.
Правила генерации кода:
1) если вершина - правый лист с меткой 1, то ей
соответствует код LOAD X,R, где R - регистр, назначенный этой
вершине, а X - адрес переменной, связанной с вершиной (рис.
8.16.б);
2) если вершина внутренняя и ее левый потомок - лист с
меткой 0, то ей соответствует код
Код правого поддерева
Op X,R
где снова R - регистр, назначенный этой вершине, X - адрес
переменной, связанной с вершиной, а Op - операция, примененная
в вершине (рис. 8.16.а);
3) если непосредственные потомки вершины не листья и метка
правой вершины больше метки левой, то вершине соответствует
код
Код правого поддерева
Код левого поддерева
Op R+1,R
где R - регистр, назначенный внутренней вершине, и операция
Op, вообще говоря, не коммутативная (рис. 8.17 б)).
R R R R
| | | |
/ \ / \ / \ / \
/ \R R / \ R/ \R+1 R+1/ \R
X /\ /\ X /\ /\ /\ /\
(0) -- -- (1) -- -- -- --
а) б) а) б)
Рис. 8.16 Рис. 8.17
Если метка правой вершины меньше или равна метке левой
вершины, то вершине соответствует код
Код левого поддерева
Код правого поддерева
Op R,R+1
MOVE R+1,R
Последняя команда генерируется для того, чтобы получить
результат в нужном регистре (в случае коммутативной операции
операнды операции можно поменять местами и избежать
дополнительной пересылки)(рис. 8.17 а)).
Рассмотрим атрибутную грамматику, реализующую эти правила
генерации кода. В этой атрибутной грамматике генерация кода
происходит не непосредственно в процессе обхода дерева, как
раньше, а из-за необходимости переставлять поддеревья код
строится в виде текста с помощью операции конкатенации.
Практически, конечно, это нецелесообразно: разумнее управлять
обходом дерева непосредственно, однако для простоты мы будем
пользоваться конкатенацией.
RULE
Expr ::= IntExpr
SEMANTICS
Reg:=1; Left:=true.
RULE
IntExpr ::= Term AddOp IntExpr
SEMANTICS
Left:=true; Left:=false;
Label:=if Label=Label
then Label+1
else Max(Label,Label);
Reg:=if Label
then Reg+1
else Reg;
Reg:=if Label
then Reg
else Reg+1;
Code:=if Label=0
then Code||Code
||Code||","||Reg
else if Label
then Code||Code||Code||
Reg+1||","||
Reg
else Code||Code||Code||
Reg||","||Reg+1
||"MOVE"||Reg+1
||","||Reg.
IntExpr ::= Term =>
Left:=Left; Code:=Code;
Label:=Label; Reg:=Reg.
RULE
Term::= Factor MultOp Term
SEMANTICS
Left:=true; Left:=false;
Label:=if Label=Label
then Label+1
else Max(Label,Label);
Reg:=if Label
then Reg+1
else Reg;
Reg:=if Label
then Reg
else Reg+1;
Code:=if Label=0
then Code||Code
||Code||",""||Reg
else if Label
then Code||Code||Code||
Reg+1||","||
Reg
else Code||Code||Code||
Reg||","||Reg+1
||"MOVE"||Reg+1
||","||Reg.
RULE
Term ::= Factor
SEMANTICS
Left:=Left; Code:=Code;
Label:=Label; Reg:=Reg.
RULE
Factor ::= Ident
SEMANTICS
Label:=if Left then 0 else 1;
Code:=if not Left then
"LOAD"||Reg||","||Val
else Val.
RULE
Factor ::= ( IntExpr )
SEMANTICS
Left:=Left; Code:=Code;
Label:=Label; Reg:=Reg.
RULE
AddOp ::= '+'
SEMANTICS
Code:="ADD".
RULE
AddOp ::= '-'
Code:="SUB".
RULE
MultOp ::= '*'
SEMANTICS
Code:="MUL".
RULE
MultOp ::= '/'
SEMANTICS
Code:="DIV".
Expr
|
IntExpr
/ | \ Left=true
/ | \Label=2
/ | \Reg=1
Term AddOp IntExpr
/ | \ Left=true| / | \ Left=false
/ | \Label=1 | / | \Label=2
/ | \Reg=2 | / | \
/ | \ + / | \
Factor MultOp Term Factor MultOp Term
|Left=true | |Left=false |Left=true | |Left=false
|Label=0 | |Label=1 |Label=0 | |Label=1
|Reg=2 * |Reg=3 |Reg=1 * |Reg=1
Ident Ident Ident Factor
A B C | Left=false
| Label=1
----------------- Reg=1
/|\
( | )
IntExpr
/ | \ Left=false
/ | \Label=1
/ | \Reg=1
Term AddOp IntExpr
|Left=true | | Left=false
|Label=0 | | Label=1
|Reg=2 + | Reg=1
Factor Term
|Left=true | Left=false
|Label=0 | Label=1
|Reg=2 | Reg=1
Ident Factor
D | Left=false
| Label=1
| Reg=1
Ident
E
Рис. 8.18.
Атрибутированное дерево для выражения A*B+C*(D+E) приведено на
рис. 8.18. При этом будет сгенерирован следующий код:
LOAD E,R1
ADD D,R1
MUL C,R1
LOAD B,R2
MUL A,R2
ADD R2,R1
Приведенная атрибутная схема требует двух проходов по дереву
выражения. Рассмотрим теперь другую атрибутную схему, в
которой достаточно одного обхода для генерация программы для
выражений с оптимальным распределением регистров [9].
Пусть мы произвели разметку дерева разбора так же, как и в
предыдущем алгоритме. Назначение регистров будем производить в
соответствии со схемой рис. 8.19.
Левому потомку всегда назначается регистр, равный его метке,
а правому - его метке, если она не равна метке его левого
брата, и метке +1, если метки равны. Поскольку более сложное
поддерево всегда вычисляется раньше более простого, его
регистр результата имеет больший номер, чем любой регистр,
используемый при вычислении более простого поддерева, что
гарантирует правильность использования регистров.
| ^
| | Label
/ \
/ \
/ \
Left=0 /Label-->Left\
/\ /\ Reg:=if (Left=Label)
/ \ / \ &(Left#0)
/ \ / \ then Label+1
/ \ /\ /\ else Label
/ \ / \ / \
---------- ---- ----
Рис. 8.19.
Приведенные соображения реализуются следующей атрибутной
схемой:
RULE
Expr ::= IntExpr
SEMANTICS
Code:=Code; Left:=true.
RULE
IntExpr ::= Term AddOp IntExpr
SEMANTICS
Left:=true; Left:=false;
Label:=if Label=Label
then Label+1
else Max(Label,Label);
Code:=if Label > Label then
if Label=0 then
Code||Code||Code
||","||Label
else Code||Code||Code||
Label||","||Label
else if Label then
Code||Code||Code||
Label||","||Label||
"MOVE"||Label||","||
Label
else {Label=Label}
Code||"MOVE"||Label||
","||Label+1||Code||
Code||Label||","||
Label+1.
RULE
IntExpr ::= Term
SEMANTICS
Left:=Left; Code:=Code;
Label:=Label.
RULE
Term ::= Factor MultOp Term
SEMANTICS
Left:=true; Left:=false;
Label:=if Label=Label
then Label+1
else Max(Label,Label);
Code:=if Label > Label then
if Label=0 then
Code||Code||Code
||","||Label
else Code||Code||Code||
Label||","||Label
else if Label then
Code||Code||Code||
Label||","||Label||
"MOVE"||Label||","||
Label
else {Label=Label}
Code||"MOVE"||Label||
","||Label+1||Code||
Code||Label||","||
Label+1.
RULE
Term ::= Factor
SEMANTICS
Left:=Left; Code:=Code;
Label:=Label.
RULE
Factor ::= Ident
SEMANTICS
Label:=if Left then 0 else 1;
Code:=if Left then Val
else "LOAD"||Val||"R1".
RULE
Factor ::= ( IntExpr )
SEMANTICS
Left:=Left; Code:=Code;
Label:=Label.
RULE
AddOp ::= '+'
SEMANTICS
Code:="ADD".
RULE
AddOp ::= '-'
SEMANTICS
Code:="SUB".
RULE
MultOp ::= '*'
SEMANTICS
Code:="MUL".
RULE
MultOp ::= '/'
SEMANTICS
Code:="DIV".
Команды пересылки требуются для согласования номеров
регистров, в которых осуществляется выполнение операции, с
регистрами, в которых должен быть выдан результат. Это имеет
смысл, когда эти регистры разные. Получиться это может из-за
того, что по приведенной схеме результат выполнения операции
всегда находится в регистре с номером метки, а метки левого и
правого поддеревьев могут совпадать.
Для выражения A*B+C*(D+E) будет сгенерирован следующий код:
LOAD E,R1 - загрузить E на 1 регистр
ADD D,R1 - сложить D и E и результат заслать в 1 регистр
MUL C,R1 - умножить C на D+E с результатом в 1 регистре
MOVE R1,R2 - переслать результат в регистр R2
LOAD B,R1- загрузить B в 1 регистр
MUL A,R1 - умножить A на B с результатом в 1 регистре
ADD R1,R2 - сложить A*B и C*(D+E) и результат заслать во 2
регистр
В приведенных атрибутных схемах предполагалось, что регистров
достаточно, чтобы правильно странслировать любое выражение.
Если это не так, приходится усложнять схему трансляции и при
необходимости сбрасывать содержимое регистров в память (или
магазин).
8.7. Трансляция логических выражений
Логические выражения, включающие логическое умножение,
логическое сложение и отрицание, можно вычислять как
непосредственно, используя таблицы истинности, так и с помощью
условных выражений, пользуясь очевидными правилами:
A & B эквивалентно if A then B else False,
A v B эквивалентно if A then True else B.
Если в качестве компонент выражений могут входить функции с
побочным эффектом, то, вообще говоря, результат вычисления
может зависеть от способа вычисления. В некоторых языках
программирования не оговаривается, каким способом должны
вычисляться логические выражения (например, в Паскале), в
некоторых требуется, чтобы вычисления производились тем или
иным способом (например, в Модуле-2 требуется, чтобы выражения
вычислялись по приведенным формулам), в некоторых языках есть
возможность явно задать способ вычисления (Си, Ада).
Вычисление логических выражений непосредственно по таблицам
истинности аналогично вычислению арифметических выражений,
поэтому мы не будем их рассматривать отдельно. Рассмотрим
подробнее способ вычисления с помощью приведенных выше формул
(будем называть его "вычисления с условными переходами").
Иногда такой способ рассматривают как оптимизацию вычисления
логических выражений.
Рассмотрим следующую атрибутную грамматику со входным языком
логических выражений:
RULE
Expr ::= BoolExpr
SEMANTICS
FalseLab:=False; TrueLab:=True.
RULE
BoolExpr ::= BoolExpr '&' BoolExpr
SEMANTICS
FalseLab:=FalseLab; TrueLab:=NodeLab;
FalseLab:=FalseLab; TrueLab:=TrueLab.
RULE
BoolExpr ::= BoolExpr 'V' BoolExpr
SEMANTICS
TrueLab:=TrueLab; FalseLab:=NodeLab;
FalseLab:=FalseLab; TrueLab:=TrueLab.
RULE
BoolExpr ::= F
SEMANTICS
GOTO FalseLab.
RULE
BoolExpr ::= T
SEMANTICS
GOTO TrueLab.
Здесь предполагается, что все вершины дерева занумерованы и
номер вершины дает атрибут NodeLab. Метки вершин передаются,
как это изображено на рис. 8.20.
TrueLab TrueLab
FalseLab\ FalseLab\
/ | \\ /| \\
/ / \ \\ // \ \\
/ / & \ \\ // V \ \\
/ / \ \\ // \ \\
FalseLab / \ \TrueLab TrueLab/ \ \TrueLab
/ \FalseLab / \ FalseLab
TrueLab, в
вершине T - GOTO значение атрибута TrueLab. Например, для
выражения F V ( F & T & T ) V T получим атрибутированное
дерево и трансляцию, изображенные на рис. 8.21 и 8.22.:
F V ( F & T & T ) V T
| FalseLab=False
1 TrueLab=True
/
TrueLab=True / V \
FalseLab=2 / \ FalseLab=False
F 2 TrueLab=True
/ \
TrueLab=True / V \
FalseLab=3 / \
/ \
4 3
/ \ |
TrueLab=5 / & \ T
FalseLab=3 / \ TrueLab=True
/ \ FalseLab=3
F 5
/ \
TrueLab=6 / & \ 1: GOTO 2
FalseLab=3 / \ TrueLab=True 2:
/ \ FalseLab=3 4: GOTO 3
T 6 5: GOTO 6
| 6: GOTO True
T 3: GOTO True
Рис. 8.21 Рис. 8.22
Эту линеаризованную запись можно трактовать как программу
вычисления логического значения: каждая строка может быть
помечена номером вершины и содержать либо переход на другую
строку, либо переход на True или False, что соответствует
значению выражения true или false, либо пусто. Будем говорить,
что полученная программа вычисляет (или интерпретирует)
значение выражения, если в результате ее выполнения (от первой
строки) мы придем к строке, содержащей GOTO True или GOTO
False.
Утверждение 1. Для каждого набора входных данных любого
логического выражения программа, полученная в результате
обхода дерева этого выражения, завершается со значением
логического выражения в обычной интерпретации, т.е.
осуществляется переход на True для значения, равного T, и
переход на метку False для значения F.
Это утверждение является частным случаем следующего.
Утверждение 2. В результате интерпретации поддерева с
некоторыми значениями атрибутов FalseLab и TrueLab в его корне
выполняется команда GOTO TrueLab, если значение выражения
истинно, и команда GOTO FalseLab, если значение выражения
ложно.
Доказательство можно провести индукцией по высоте дерева.
Для деревьев высоты 1, соответствующих правилам BoolExpr ::= F
и BoolExpr ::= T, утверждение очевидно из правил грамматики.
Пусть дерево имеет высоту n>1. Зависимость атрибутов для
дизъюнкции и конъюнкции приведена на рис. 8.23
| FalseLab0
| TrueLab0
/ \
/ & \
FalseLab1=FalseLab0 / \ FalseLab2=FalseLab0
TrueLab1=NodeLab2 / \ TrueLab2=TruLab0
/\ /\
/ \ / \
---- ----
147
| FalseLab0
| TrueLab0
/ \
/ V \
FalseLab1=NodeLab2 / \ FalseLab2=FalseLab0
TrueLab1=TruLab0 / \ TrueLab2=TruLab0
/\ /\
/ \ / \
---- ----
Рис. 8.23
Если для конъюнкции значение левого поддерева ложно и по
индукции вычисление левого поддерева завершается командой GOTO
FalseLab1, то и интерпретация всего дерева завершается
командой GOTO FalseLab0 (=FalseLab1). Если значение левого
поддерева истинно, то его интерпретация завершается командой
GOTO TrueLab1 (=NodeLab2). Если значение правого поддерева
ложно, то интерпретация всего дерева завершается командой GOTO
FalseLab0 (=FalseLab2). Если же оно истинно, интерпретация
всего дерева завершается командой GOTO TrueLab0 (=TrueLab2).
Аналогично - для дизъюнкции.
Доказательство утверждения 1 следует из того, что метками
вершины дерева логического выражения являются TrueLab=True и
FalseLab=False.
Добавим теперь новое правило в предыдущую грамматику:
BoolExpr ::= Ident
SEMANTICS
else GOTO FalseLab>;
Тогда, например, для предыдущего выражения получим следующую
программу:
1: if Ident=T then GOTO True else GOTO 2
2:
4: if Ident=T then GOTO 5 else GOTO 3
5: if Ident=T then GOTO 6 else GOTO 3
6: if Ident=T then GOTO True else GOTO 3
3: if Ident=T then GOTO True else GOTO False
При каждом конкретном наборе данных эта программа превращается
в программу вычисления логического значения.
Утверждение 3. В каждой строке программы, сформированной
предыдущей атрибутной схемой, одна из меток совпадает с меткой
следующей строки.
Действительно, по правилам наследования атрибутов TrueLab и
FalseLab, в правилах для дизъюнкции и конъюнкции либо
FalseLab, либо TrueLab принимает значение метки следующего
поддерева. Кроме того, как значение FalseLab, так и значение
TrueLab, передаются в правое поддерево от предка. Таким
образом, самый правый потомок всегда имеет одну из меток
TrueLab или FalseLab, равную метке правого брата
соответствующего поддерева. Учитывая порядок генерации команд,
получаем утверждение.
Дополним теперь атрибутную грамматику следующим образом:
RULE
Expr ::= BoolExpr
SEMANTICS
FalseLab:=False; TrueLab:=True;
Sign:=false.
RULE
BoolExpr ::= BoolExpr & BoolExpr
SEMANTICS
FalseLab:=FalseLab; TrueLab:=NodeLab;
FalseLab:=FalseLab; TrueLab:=TrueLab;
Sign:=false; Sign:=Sign.
RULE
BoolExpr ::= BoolExpr V BoolExpr
SEMANTICS
TrueLab:=TrueLab; FalseLab:=NodeLab;
FalseLab:=FalseLab; TrueLab:=TrueLab;
Sign:=true; Sign:=Sign.
RULE
BoolExpr ::= not BoolExpr
SEMANTICS
FalseLab:=TrueLab; TrueLab:=FalseLab;
Sign:=not Sign.
RULE
BoolExpr ::= F
SEMANTICS
GOTO FalseLab.
RULE
BoolExpr ::= T
SEMANTICS
GOTO TrueLab.
RULE
BoolExpr ::= Ident
SEMANTICS
if Sign
then else GOTO FalseLab>
else else GOTO TrueLab>;
Правила наследования атрибута Sign приведены на рис. 8.24.
false | true | false | true |
or or and and
/\ /\ /\ /\
/ \ / \ / \ / \
/ \ / \ / \ / \
true false true true false false false true
true | false |
| |
not not
| |
| |
false true
Рис. 8.24
Программу желательно сформировать таким образом, чтобы else-
метка была как раз меткой следующей вершины. Как это можно
сделать, следует из утверждения 4.
Утверждение 4. В каждой терминальной вершине, метка ближайшего
правого для нее поддерева равна значению атрибута FalseLab
этой вершины, тогда и только тогда, когда значение атрибута
Sign этой вершины равно true, и наоборот, метка ближайшего
правого для нее поддерева равна значению атрибута TrueLab этой
вершины, тогда и только тогда, когда значение атрибута Sign
равно false.
Эти два утверждения позволяют заменить последнее правило
атрибутной грамматики следующим образом:
RULE
BoolExpr ::= Ident
SEMANTICS
if Sign
then >
else >.
В свою очередь, при генерации машинных команд это правило
можно заменить на следующее:
RULE
BoolExpr ::= Ident
SEMANTICS
;
if Sign then >
else >.
Если элементом логического выражения является сравнение, то
генерируется команда, соответствующая знаку сравнения (beq для
=, bne для , bge для >= и т.д.), если атрибут sign
соответствующей вершины имеет значение true, и отрицание (bne
для =, beq для , blt для >= и т.д.), если атрибут sign имеет
значение false.
Приведем несколько примеров. Выражение A AND (B OR C)
транслируется в последовательность команд рис. 8.25. Выражение
(NOT((A=B)OR(CD)))AND(not((EH))) транслируется в
последовательность команд рис. 8.26.
TST A CMP A,B
BEQ False BEQ False
TST B CMP C,D
BNE True BNE False
TST C CMP E,F
BEQ False BGE False
True: CMP G,H
False:. . . BGT False
True:
False:
Рис. 8.25 Рис. 8.26
8.8. Выделение общих подвыражений
Выделение общих подвыражений проводится на линейном участке и
основывается на двух положениях.
1. Поскольку на линейном участке переменной может быть
несколько присваиваний, то при выделении общих подвыражений
необходимо различать вхождения переменных до и после
присваивания. Для этого каждая переменная снабжается номером.
Вначале номера всех переменных устанавливаются равными 0. При
каждом присваивании переменной ее номер увеличивается на 1.
2. Выделение общих подвыражений осуществляется при обходе
дерева выражения снизу вверх слева направо. При достижении
очередной вершины (пусть операция, примененная в этой вершине,
есть бинарная 'op'; в случае унарной операции рассуждения те
же) просматриваем общие подвыражения, связанные с op. Если
имеется выражение, связанное с op и такое, что его левый
операнд есть общее подвыражение с левым операндом нового
выражения, а правый операнд - общее подвыражение с правым
операндом нового выражения, то объявляем новое выражение общим
с найденным и в новом выражении запоминаем указатель на
найденное общее выражение. Базисом построения служит
переменная: если операндами обоих выражений являются
одинаковые переменные с одинаковыми номерами, то они являются
общими подвыражениями. Если выражение не выделено как общее,
оно заносится в список операций, связанных с op (рис. 8.27).
|/\ /\].Count:=Table[Entry].Count+1.
{Увеличить счетчик присваиваний переменной}
RULE
IntExpr ::= Variable
SEMANTICS
with Node^ do with Table[Entry] do
if LastNIL
{ Переменная уже была использована }
and Last^.VarCount = Count then
{ С тех пор переменной не было присваивания }
Flag:=true;
{ Переменная - общее подвыражение }
Comm:=Last;
{ Указатель на общее подвыражение }
else Flag:=false;
end;
Last:=^Node; {Указатель на последнее
использование переменной}
VarCount:=Count; {Номер использования переменной}
Varbl:=true; {Выражение - переменная}
end end.
RULE
IntExpr ::= Op IntExpr IntExpr
SEMANTICS
var L:pointer to Listype; {Тип списков операции}
if Node^.Flag and Node^.Flag then
{ И справа, и слева - общие подвыражения }
L:=OpTable[Val];
{ Начало списка общих подвыражений для операции }
while Lnil do
if (Node=L^.Left)
and (Node=L^.Right)
{ Левое и правое поддеревья совпадают }
then exit
else L:=L^.List;{Следующий элемент списка}
end end
else L:=nil; {Не общее подвыражение}
end;
with Node^ do
Varbl:=false; { Не переменная }
Comm:=L;
{Указатель на предыдущее общее подвыражение или nil}
if Lnil then
Flag:=true; {Общее подвыражение}
Left:=Node;
{ Указатель на левое поддерево }
Right:=Node;
{ Указатель на правое поддерево }
else Flag:=false;
{ Данное выражение не может рассматриваться как общее }
{ Если общего подвыражения с данным не было,
включить данное в список для операции }
new(L);
L^.Addr:=^Node;
L^.List:=OpTable[Val];
OpTable[Val]:=L;
end end.
Рассмотрим теперь некоторые простые правила распределения
регистров при наличии общих подвыражений. Если число регистров
ограничено, можно выбрать один из следующих двух вариантов.
1. При обнаружении общего подвыражения с подвыражением в уже
просмотренной части дерева (и, значит, с уже распределенными
регистрами) проверяем, расположено ли его значение на
регистре. Если да, и если регистр после этого не менялся,
заменяем вычисление поддерева на значение в регистре. Если
регистр менялся, то вычисляем подвыражение заново.
2. Вводим еще один проход. На первом проходе распределяем
регистры. Если в некоторой вершине обнаруживается, что ее
поддерево общее с уже вычисленным ранее, но значение регистра
потеряно, то в такой вершине на втором проходе необходимо
сгенерировать команду сброса регистра в рабочую память.
Выигрыш в коде будет, если стоимость команды сброса регистра +
доступ к памяти в повторном использовании этой памяти не
превосходит стоимости заменяемого поддерева. Поскольку
стоимость команды MOVE известна, можно сравнить стоимости и
принять оптимальное решение: то ли метить предыдущую вершину
для сброса, то ли вычислять полностью поддерево.
8.9. Генерация оптимального кода методами синтаксического
анализа
8.9.1. Сопоставление образцов
Техника генерации кода, рассмотренная выше, основывалась на
однозначном соответствии структуры промежуточного
представления и описывающей это представление грамматики. Для
генерации более качественного кода может быть применен подход,
изложенный в настоящей главе.
Этот подход основан на понятии "сопоставления образцов":
командам машины сопоставляются некоторые "образцы", вхождения
которых ищутся в промежуточном представлении программы, и
делается попытка "покрыть" промежуточную программу такими
образцами. Если это удается, то по образцам восстанавливается
программа уже в кодах.
:=
|
-------------
/ \
+ +
/ \ / \
/ \ / \
const(a) const(x) @ const(5)
|
|
+
/ \
/ \
+ @
/ \ |
/ \ |
const(b) const(y) +
/ \
/ \
const(i) const(z)
Рис. 8.29
На рис. 8.29 показано промежуточное дерево для оператора
a:=b[i]+5, где a,b,i - локальные переменные, хранимые со
смещениями x,y,z в областях данных с одноименными адресами.
Элемент массива b занимает память в одну машинную единицу.
0-местная операция const возвращает значение атрибута
соответствующей вершины промежуточного дерева, указанного на
рисунке в скобках после оператора. Одноместная операция '@'
означает косвенную адресацию и возвращает содержимое регистра
или ячейки памяти, имеющей адрес, задаваемый аргументом
оператора.
+------------------------------------------------------+
|Но-| Образец |Машинная команда |Стоимость|
|мер| |Правило грамматики| |
|---+---------------------+----------------------------|
| 1 | const(c) | MOV #c,Ri | 2 |
| | | Reg->Const | |
|---+---------------------+-----------------------+----|
| 2 | := | MOV Rj,c(Ri) | 4 |
| | / \ | | |
| | / \ | | |
| | + reg(j) | | |
| | / \ | Stat->':=' '+' Reg | |
| |reg(i) const(c) | Const Reg | |
|---+---------------------+-----------------------+----|
| 3 | @ | MOV c(Rj),Ri | 4 |
| | | | | |
| | + | | |
| | / \ | | |
| | / \ |Contents -> '@' '+' Reg| |
| | reg(j) const(c) | Const | |
|---+---------------------+-----------------------+----|
| 4 | + | ADD #c,Ri | 3 |
| | / \ | | |
| | / \ | | |
| | reg(i) const(c) |Reg -> '+' Reg Const | |
|---+---------------------+-----------------------+----|
| 5 | + | ADD Rj,Ri | 2 |
| | / \ | | |
| | / \ | | |
| | reg(i) reg(j) | Reg -> '+' Reg Reg | |
|---+---------------------+-----------------------+----|
| 6 | + | ADD c(Rj),Ri | 4 |
| | / \ | | |
| | / \ | | |
| |reg(i) @ | | |
| | | | Reg -> '+' Reg '@' | |
| | + | '+' Reg Const | |
| | / \ | | |
| | reg(j) const(c) | | |
|---+---------------------+-----------------------+----|
| 7 | @ | MOV (R),R | 2 |
| | | | | |
| | Reg | Reg -> Contents | |
+------------------------------------------------------+
Рис. 8.30
----------[stat]----------------------------------
|2 := |
| / \ |
| + \ |
| / \ \ |
|reg(Ra) const(x) \ |
|const(a) \ |
| ------------------[reg(Rb)]------------------ |
| | 4 + | |
| | / \ | |
| | / const(5) | |
| | / | |
| | ---------------[reg(Rb)]------------------ | |
| | | 7 @ | | |
| | | | | | |
| | | -------------[reg(Rb)]---------------- | | |
| | | |6 + | | | |
| | | | / \ | | | |
| | | | / \ | | | |
| | | | ------[reg(Rb)]---- \ | | | |
| | | | |4 + | @ | | | |
| | | | | / \ | | | | | |
| | | | | / \ | | | | | |
| | | | | reg(Rb) const(y)| + | | | |
| | | | | const(b) | / \ | | | |
| | | | ------------------- / \ | | | |
| | | | / \ | | | |
| | | | reg(Ri) const(z) | | | |
| | | | const(i) | | | |
| | | -------------------------------------- | | |
| | ------------------------------------------ | |
| ---------------------------------------------- |
--------------------------------------------------
Рис. 8.31
На рис.8.30 показан пример сопоставления образцов машинным
командам. Приведены два варианта задания образца: в виде
дерева и в виде правила контекстно-свободной грамматики. Для
каждого образца указана машинная команда, реализующая этот
образец, и стоимость этой команды. Стоимость может
определяться различными способами, и здесь мы не рассматриваем
этого вопроса. На рис. 8.31 приведен пример покрытия
промежуточного дерева рис. 8.29 образцами рис. 8.30. В рамки
заключены фрагменты дерева, сопоставленные образцу правила,
номер которого указывается в левом верхнем углу рамки. В
квадратных скобках указаны результирующие вершины. Приведенное
покрытие дает такую последовательность команд:
MOVE b,Rb
ADD #y,Rb
MOVE i,Ri
ADD z(Ri),Rb
MOV (Rb),Rb
ADD #5,Rb
MOVE a,Ra
MOV Rb,x(Ra)
Как правило, одни и те же конструкции исходной (или
промежуточной) программы можно реализовать различными
последовательностями машинных команд. Это соответствует тому,
что имеются различные покрытия промежуточного представления.
Задача выбора команд состоит в том, чтобы выбрать наилучший
способ реализации того или иного действия или
последовательности действий, т. е. выбрать в некотором смысле
оптимальное покрытие.
Для выбора оптимального покрытия было предложено несколько
интересных алгоритмов, в частности использующих динамическое
программирование [10,11]. Мы здесь рассмотрим алгоритм [12],
комбинирующий возможности синтаксического анализа и
динамического программирования, в основу которого положен
синтаксический анализ неоднозначных грамматик
(модифицированный алгоритм Кока, Янгера и Касами [13,14])
более эффективный в реальных приложениях. Этот же метод может
быть применен и тогда, когда в качестве промежуточного
представления используется дерево.
8.9.2. Синтаксический анализ для T-грамматик
Обычно код генерируется из некоторого промежуточного языка с
довольно жесткой структурой. В частности, для каждой операции
известна ее размерность (число операндов). Назовем грамматики,
удовлетворяющие этим ограничениям, T-грамматиками.
Образцы, соответствующие машинным командам, задаются
правилами грамматики (вообще говоря, неоднозначной). Генератор
кода анализирует входное префиксное выражение и строит
одновременно все возможные деревья разбора. После окончания
разбора выбирается дерево с наименьшей оценкой. Затем по этому
единственному оптимальному дереву генерируется код.
Для T-грамматик все цепочки, выводимые из любого нетерминала
A, являются префиксными выражениями с фиксированной арностью
операций. Длины всех выражений из входной цепочки a1...an
можно предварительно вычислить. Поэтому можно проверить,
сопоставимо ли правило с подцепочкой ai...ak входной цепочки
a1...an, проходя слева-направо по ai...ak. В процессе прохода
по цепочке предварительно вычисленные длины префиксных
выражений используются для того, чтобы перейти от одного
терминала к следующему терминалу, пропуская подцепочки,
соответствующие нетерминалам правой части правила.
Цепные правила не зависят от операций, следовательно, их
необходимо проверять отдельно. Применение одного цепного
правила может зависеть от применения другого цепного правила.
Следовательно, применение цепных правил необходимо проверять
циклически до тех пор, пока нельзя применить ни одно из цепных
правил. Мы предполагаем, что в грамматике нет циклов в
применении цепных правил. Тип Titem в алгоритме 8.1 ниже
служит для описания ситуаций (т.е. правил вывода и позиции
внутри правила). Тип Tterminal - это тип терминального символа
грамматики, тип Tproduction - тип для правила вывода.
r[i]={A->aiV1...Vm}
| /\
| / \
| 1 /\ /\m
| / \ / \
|---------|----------------|-----|
ai l[i]
Рис. 8.32
Алгоритм 8.1:
var
a:array[1..n] of Tterminal;
r:array[1..n] of set of Tproduction;
l:array[1..n] of INTEGER;
(* l[i] - длина a[i]-выражения*)
h:Titem;
(* используется при поиске правил, сопоставимых с
текущей подцепочкой*)
begin (* Предварительные вычисления *)
Для каждой позиции i вычислить длину a[i]-выражения l[i];
(* Распознование входной цепочки *)
for i:=n downto 1 do
for для каждого правила A -> a[i] y из P do
if l[i]>0 then
j:=i+1;
if l[i]>1 then (*Первый терминал a[i] уже проверен*)
h:=[A->a[i].y];
repeat (*Сопоставимы ли a[i]y и a[i]..a[i+l[i]-1]*)
Пусть h=[A->u.Xv]
if X в T then
if X=a[j] then j:=j+1 else exit end
else (* X в N *)
if X->w в r[j] then j:=j+l[j] else exit end
end;
h:=[A->uX.v]; (* Перейти к следующему символу*)
until j=i+l[i];
end (*l[i]>1*);
end (*l[i]>0*);
if j=i+l[i] then r[i]:=r[i]+{(A->a[i]y)} end
end (*for*);
(* Проверить цепные правила *)
while существует правило C->A из P такое, что
имеется некоторый элемент (A->w) в r[i]
и нет элемента (C->A) в r[i]
do r[i]:=r[i]+{(C->A)}
end
end; (* for i *)
Проверить, принадлежит ли (S->w) множеству r[1]
end
Работа алгоритма иллюстрируется рис. 8.32. Множества r[i]
имеют размер O(|P|). Очевидно, что алгоритм имеет временную и
емкостную сложность O(n).
Рассмотрим вновь пример рис. 8.29. В префиксной записи
приведенный фрагмент программы записывается следующим образом:
:= + a x + @ + + b y @ + i z 5
На рис. 8.33 приведен результат работы алгоритма. Правила
вычисления стоимости приведены в разделе 8.9.3.
+-----------------------------+
|Операция|Длина| Правила |
| | | (стоимость) |
|--------+-----+--------------|
| := | 14 | 2(22) |
| + | 2 | 4(5) 5(6) |
| a | 0 | 1(2) |
| x | 0 | 1(2) |
| + | 9 | 4(16) 5(17)|
| @ | 8 | 7(13) |
| + | 7 | 5(15) 6(11)|
| + | 2 | 4(5) 5(6) |
| b | 0 | 1(2) |
| y | 0 | 1(2) |
| @ | 3 | 3(6) 7(7) |
| + | 2 | 4(5) 5(6) |
| i | 0 | 1(2) |
| z | 0 | 1(2) |
| 5 | 0 | 1(2) |
+-----------------------------+
Рис. 8.33
Пусть G - это T-грамматика. Для каждой цепочки z из L(G) можно
построить дерево выражения. Мы можем переписать алгоритм так,
чтобы он работал с деревьями выражений, а не с префиксными
выражениями. Этот вариант алгоритма приведен ниже. В этом
алгоритме дерево выражения обходится сверху вниз и в нем
ищутся поддеревья, сопоставимые с правыми частями правил из G.
Обход дерева осуществляется процедурой PARSE. После обхода
поддерева данной вершины в ней применяется процедура MATCHED,
которая пытается найти все образцы, сопоставимые поддереву
данной вершины. Для этого каждое правило-образец разбивается
на компоненты в соответствии с встречающимися в нем
операциями. Дерево обходится справа налево только для того,
чтобы иметь соответствие с порядком вычисления в алгоритме
8.1. Очевидно, что можно обходить дерево вывода и слева
направо.
Структура данных, представляющая вершину дерева, имеет
следующую форму:
PTnode=^Tnode;
Tnode=record
op:Tterminal;
son:array[1..MaxArity] of PTnode;
rules:set of Tproduction
end;
В комментариях указаны соответствующие фрагменты алгоритма 8.1.
Алгоритм 8.2:
var root:PTnode;
procedure PARSE(n:PTnode);
procedure MATCHED(n:PTnode; h:Titem);
var matching:boolean;
begin
пусть h=[A->u.Xvy], v= v1 v2 ... vm,
m=Arity(X)
if X in T then (* сопоставление правила *)
if m=0 then (*if l[i]=0*)
if X=n^.op (*if X=a[j]*)
then return(true) else return(false) end
else (* m>0 *) (*if l[i]>0*)
if X=n^.op then (*if X=a[j]*)
matching:=true;
for i:=1 to m do (*j:=j+l[j] *)
matching:=matching and (*until j=i+l[i]*)
MATCHED(n^.son[i],[A->uXv'.vi v"y])
end;
return(matching) (*h:=[A->uX.v]*)
else return(false) end
end
else (*X in N*) (* поиск подвывода *)
if в n^.rules имеется правило X->w in
then return(true) else return(false) end
end
end (* match *)
begin (*PARSE*)
for i:=Arity(n^.op) downto 1 do (*for i:=n downto1*)
PARSE(n^.son[i]) end;
n^.rules:={};
for каждого правила A->bu из P такого, что b=n^.op do
if MATCHED(n,[A->.bu]) (*if j=i+l[i]*)
then n^.rules:=n^.rules+{(A->bu)} end
end;
(* Сопоставление цепных правил *)
while существует правило C->A из P такое, что
некоторый элемент (A->w) в n^.rules
и нет элемента (C->A) в n^.rules
do n^.rules:=n^.rules+{(C->A)}
end
end;(*PARSE*)
begin
(* Предварительные вычисления *)
Построить дерево выражения для входной цепочки z;
root:= указатель дерева выражения;
(* Распознать входную цепочку *)
PARSE(root);
Проверить, принадлежит ли S->w множеству root^.rules;
end
Выходом алгоритма является дерево выражения для z, вершинам
которого сопоставлены применимые правила. Если T-грамматика
неоднозначная, то можно построить несколько различных выводов
для заданной входной цепочки.
Алгоритмы 8.1 и 8.2 "универсальные" в том смысле, что
конкретные грамматики выражений и образцов являются, по-
существу, параметрами этих алгоритмов. Для каждой конкретной
грамматики можно написать свой алгоритм поиска образцов.
Например, в случае нашей грамматики выражений и приведенных на
рис. 8.30 образцов алгоритм 8.2 может быть представлен
атрибутной грамматикой, приведенной ниже. Для каждого правила
имеется два типа образцов: "внутренние", соответствующие
правилам-образцам, и "внешние", приходящие сверху через
атрибут Match предка. Атрибут Match представлен как вектор
образцов вида . Каждый из образцов
имеет вид либо , где op - оперция в данной
вершине, а op-list - список ее операндов, либо образец - это
нетерминал N. В первом случае op-list "распределяется" по
потомкам вершины для дальнейшего сопоставления, во втором
сопоставление считается успешным, если есть правило N->w, где
w - состоит из образцов, успешно сопоставленных потомкам
данной вершины. Помимо атрибута Match, образцы могут
задаваться и в соответствии с правилами, возможно применимыми
в данной вершине. Эти два множества образцов могут
пересекаться. Синтезируемый атрибут Pattern (также вектор)
дает результат сопоставления по вектору-образцу Match.
Rule
Stat ::= Expr ':=' Expr
Этому правилу соответствует один образец 2. Поэтому в качестве
образцов потомков через их атрибуты Match передаются,
соответственно, и .
Semantics
Match:=:
Match:=;
Pattern[1]:=Pattern[1]&Pattern[1].
Rule
Expr ::= '+' Expr Expr
Образцы, соответствующие этому правилу, следующие:
(4) Reg -> '+' Reg Const
(5) Reg -> '+' Reg Reg
(6) Reg -> '+' Reg '@' '+' Reg Const.
Атрибутам Match второго и третьего символов в качестве
образцов при сопоставлении могут быть переданы векторы и >, соответственно.
Из анализа других правил можно заключить, что при
сопоставлении образцов предков левой части данного правила
атрибуту Match символа левой части может быть передан образец
(из образцов 2,3,6) или образец Reg.
Semantics
Match:=;
Match:=>;
P:=Pattern&Pattern;
if Match содержит образец в i-й позиции
Pattern[i]:=Pattern[1]&Pattern[1];
if Match[0] содержит Reg в j-й позиции
Pattern[j]:=(Pattern[1]&Pattern[1])
|(Pattern[2]&Pattern[2])
|(Pattern[3]&Pattern[3]);
Остальным значениям Pattern присвоить false.
Rule
Expr ::= '@' Expr
Образцы, соответствующие этому правилу, следующие:
(3) Reg -> '@' '+' Reg Const
(7) Reg -> '@' Reg
Соответственно, атрибуту Match второго символа в качестве
образцов при сопоставлении могут быть переданы
(образец 3) или (образец 7).
Из анализа других правил можно заключить, что при
сопоставлении образцов предков левой части данного правила
атрибуту Match могут быть переданы образцы
(из образца 6) и Reg.
Semantics
Match:=,Reg>;
if Match содержит в i-й позиции
Pattern[i]:=Pattern[1];
if Match содержит Reg в j-й позиции
Pattern[j]:=Pattern[1]|Pattern[2];
Остальным значениям Pattern присвоить false.
Rule
Expr ::= Const
Semantics
if Pattern содержит Const в j-й позиции
Pattern[j]:=true;
Остальным значениям Pattern присвоить false.
Для дерева рис. 8.29 получим значения атрибутов, приведенные
на рис. 8.34. Здесь M обозначает Match, P - Pattern, C -
Const, R - Reg.
8.9.3. Выбор дерева вывода наименьшей стоимости
T-грамматики, описывающие системы комад, обычно являются
неоднозначными. Чтобы сгенерировать код для некоторой входной
цепочки, необходимо выбрать одно из возможных деревьев вывода.
Это дерево должно представлять желаемое качество кода,
например размер кода и/или время выполнения.
Для выбора дерева из множества всех построенных деревьев
вывода можно использовать атрибуты стоимости, атрибутные
формулы, вычисляющие их значения, и критерии стоимости,
которые оставляют для каждого нетерминала единственное
применимое правило. Атрибуты стоимости сопоставляются всем
нетерминалам, атрибутные формулы - всем правилам T-грамматики.
M= :=
P= |
------------- M=,
/ \ ,
+ + >
/ \ / \P=
/ \ / \
const(a) const(x) @ const(5)
M= M=>
'+' R C>> | P=
P= P= |
|
|M=, | >
, |P=
>|
P= +
/ \
/ \
M= / \ M= + @ >
> / \ |
P= / \ |
const(b) const(y) | M=,
M= M=,
P= >+ >
P= / \P=
/ \
const(i) const(z)
M= M=>
P= P=
Рис. 8.34
Предположим, что для вершины n обнаружено применимое правило
p:A::=z0 X0 z1...Xk zk, где zi из T* для 0bu из P такого, что b=n^.op do
if MATCHED(n,[A->.bu]) then
ВычислитьАтрибутыСтоимостиДля(A,n,(A->bu));
ПроверитьКритерийДля(A,n^.nonterm[A].CostAttr);
if (A->bu) лучше, чем ранее обработанное
правило для A then
Модифицировать(n^.nonterm[A].CostAttr)
n^.nonterm[A].production:=(A->bu)
end
end
end;
(* Сопоставить цепные правила *)
while существует правило C->A из P, которое
лучше, чем ранее обработанное правило для A
do
ВычислитьСатрибутыДля(C,n,(C->A));
ПроверитьКритерийДля(C,n^.nonterm[C].CostAttr);
if (C->A) is better then
Модифицировать(n^.nonterm[C].CostAttr)
n^.nonterm[C].production:=(C->A)
end
end
end;
Когда выбрано дерево вывода "наименьшей" стоимости,
вычисляются значения атрибутов, сопоставленных вершинам дерева
вывода, и генерируются соответствующие машиннные команды.
Вычисление значений атрибутов, генерация кода осуществляются в
процессе обхода выбранного дерева вывода сверху вниз, слева
направо. Обход выбранного дерева вывода выполняется процедурой
вычислителя атрибутов, на вход которой поступают корень дерева
выражения и аксиома грамматики. Процедура использует правило
p:A::=z0 X0 z1...Xk zk, связанное с указанной вершиной n, и
заданный нетерминал A, чтобы определить соответствующие им
вершины n1,...,nk и нетерминалы X1,...,Xk. Затем вычислитель
рекурсивно обходит каждую вершину ni, имея на входе нетерминал
Xi.