Текст книги "Системное программное обеспечение. Лабораторный практикум"

Модуль, реализующий алгоритмы оптимизации списков триад

Листинг П3.11. Оптимизация списков триад

unit TrdOpt;

interface

{ Модуль, реализующий два алгоритма оптимизации:

– оптимизация путем свертки объектного кода;

– оптимизация за счет исключения лишних операций. }

uses Classes, TblElem, LexElem, TrdType, Triads;

type {Информационная структура для таблицы идентификаторов,

предназначенная для алгоритма свертки объектного кода}

TConstInfo = class(TAddVarInfo)

protected

iConst: longint; { Поле для записи значения переменной }

{ Конструктор для создания структуры }

constructor Create(iInfo: longint);

public { Функции для чтения и записи информации }

function GetInfo(iIdx: integer): longint; override;

procedure SetInfo(iIdx: integer; iInf: longint);

override;

end;

{Информационная структура для таблицы идентификаторов,

предназначенная для алгоритма исключения лишних операций}

TDepInfo = class(TAddVarInfo)

protected

iDep: longint; { Поле для записи числа зависимости }

{ Конструктор для создания структуры }

constructor Create(iInfo: longint);

public { Функции для чтения и записи информации }

function GetInfo(iIdx: integer): longint; override;

procedure SetInfo(iIdx: integer; iInfo: longint);

override;

end;

{ Процедура оптимизации методом свертки объектного кода }

procedure OptimizeConst(listTriad: TTriadList);

{ Процедура оптимизации путем исключения лишних операций }

procedure OptimizeSame(listTriad: TTriadList);

implementation

uses SysUtils, FncTree, LexType, TrdCalc;

constructor TConstInfo.Create(iInfo: longint);

{ Создание структуры для свертки объектного кода }

begin

inherited Create; {Вызываем конструктор базового класса}

iConst:= iInfo; { Запоминаем информацию }

end;

procedure TConstInfo.SetInfo(iIdx: integer; iInf: longint);

{ Функция записи информации }

begin iConst:= iInfo; end;

function TConstInfo.GetInfo(iIdx: integer): longint;

{ Функция чтения инфоримации }

begin Result:= iConst; end;

function TestOperConst(Op: TOperand; listTriad: TTriadList;

var iConst: integer): Boolean;

{ Функция проверки того, что операнд является константой

и получения его значения в переменную iConst }

var pInfo: TConstInfo;

begin

Result:= False;

case Op.OpType of { Выборка по типу операнда }

OP_CONST: { Если оператор – константа, то все просто }

begin

iConst:= Op.ConstVal; Result:= True;

end;

OP_VAR: { Если оператор – переменная, }

begin { тогда проверяем наличие у нее

информационной структуры, }

pInfo:= TConstInfo(Op.VarLink.Info);

if pInfo <> nil then {и если такая структура есть,}

begin {берем ее значение}

iConst:= pInfo[0]; Result:= True;

end;

end;

OP_LINK: { Если оператор – ссылка на триаду, }

begin { то он является константой,

если триада имеет тип «CONST» }

if listTriad[Op.TriadNum].TrdType = TRD_CONST

then begin

iConst:= listTriad[Op.TriadNum][1].ConstVal;

Result:= True;

end;

end;

end{case};

end;

procedure OptimizeConst(listTriad: TTriadList);

{ Процедура оптимизации методом свертки объектного кода }

var

i,j,iCnt,iOp1,iOp2: integer;

Ops: TOpArray;

Trd: TTriad;

begin

{ Очищаем информационные структуры таблицы идентификаторов }

ClearTreeInfo; { Заполняем операнды триады типа «CONST» }

Ops[1].OpType:= OP_CONST;

Ops[2].OpType:= OP_CONST;

Ops[2].ConstVal:= 0;

iCnt:= listTriad.Count-1;

for i:=0 to iCnt do { Для всех триад списка }

begin { выполняем алгоритм }

Trd:= listTriad[i];

if Trd.TrdType in TriadLineSet then

begin { Если любой операнд линейной триады ссылается

на триаду «CONST», берем и запоминаем ее значение }

for j:=1 to 2 do

if (Trd[j].OpType = OP_LINK)

and (listTriad[Trd.Links[j]].TrdType = TRD_CONST)

then begin

Trd.OpTypes[j]:= OP_CONST;

Trd.Values[j]:=

listTriad[Trd.Links[j]][1].ConstVal;

end;

end

else

if Trd.TrdType = TRD_IF then

begin { Если первый операнд условной триады ссылается

на триаду «CONST», берем и запоминаем ее значение }

if (Trd[1].OpType = OP_LINK)

and (listTriad[Trd.Links[1]].TrdType = TRD_CONST)

then begin

Trd.OpTypes[1]:= OP_CONST;

Trd.Values[1]:=

listTriad[Trd.Links[1]][1].ConstVal;

end;

end

else

if Trd.TrdType = TRD_ASSIGN then

begin { Если второй операнд триады присвоения ссылается

на триаду «CONST», берем и запоминаем ее значение }

if (Trd[2].OpType = OP_LINK)

and (listTriad[Trd.Links[2]].TrdType = TRD_CONST)

then begin

Trd.OpTypes[2]:= OP_CONST;

Trd.Values[2]:=

listTriad[Trd.Links[2]][1].ConstVal;

end;

end;{ Если триада помечена ссылкой, то линейный участок

кода закончен – очищаем информационные структуры идентификаторов}

if Trd.IsLinked then ClearTreeInfo;

if Trd.TrdType = TRD_ASSIGN then { Если триада имеет }

begin { тип «присвоение» }

{ и если ее второй операнд – константа, }

if TestOperConst(Trd[2],listTriad,iOp2) then

{запоминаем его значение в информационной структуре переменной}

Trd[1].VarLink.Info:= TConstInfo.Create(iOp2);

end

else { Если триада – одна из линейных операций, }

if Trd.TrdType in TriadLineSet then

begin { и если оба ее операнда – константы, }

if TestOperConst(Trd[1],listTriad,iOp1)

and TestOperConst(Trd[2],listTriad,iOp2) then

begin { тогда вычисляем значение операции, }

Ops[1].ConstVal:=

CalcTriad(Trd.TrdType,iOp1,iOp2);

{ запоминаем его в триаде «CONST», которую

записываем в список вместо прежней триады }

listTriad.Items[i]:= TTriad.Create(TRD_CONST,Ops);

{Если на прежнюю триаду была ссылка, сохраняем ее}

listTriad[i].IsLinked:= Trd.IsLinked;

Trd.Free; { Уничтожаем прежнюю триаду }

end;

end;

end;

end;

constructor TDepInfo.Create(iInfo: longint);

{ Создание информационной структуры для чисел зависимости }

begin

inherited Create; {Вызываем конструктор базового класса}

iDep:= iInfo; { Запоминаем число зависимости }

end;

procedure TDepInfo.SetInfo(iIdx: integer; iInfo: longint);

{ Функция записи числа зависимости }

begin iDep:= iInfo; end;

function TDepInfo.GetInfo(iIdx: integer): longint;

{ Функция чтения числа зависимости }

begin Result:= iDep; end;

function CalcDepOp(listTriad: TTriadList;

Op: TOperand): longint;

{Функция вычисления числа зависимости для операнда триады}

begin

Result:= 0;

case Op.OpType of { Выборка по типу операнда }

OP_VAR: { Если это переменная – смотрим ее информационную

структуру, и если она есть, берем число зависимости }

if Op.VarLink.Info <> nil then Result:=

Op.VarLink.Info.Info[0];

OP_LINK: { Если это ссылка на триаду,

то берем число зависимости триады }

Result:= listTriad[Op.TriadNum].Info;

end{case};

end;

function CalcDep(listTriad: TTriadList;

Trd: TTriad): longint;

{ Функция вычисления числа зависимости триады }

var iDepTmp: longint;

begin

Result:= CalcDepOp(listTriad,Trd[1]);

iDepTmp:= CalcDepOp(listTriad,Trd[2]);

{ Число зависимости триады есть число на единицу большее,

чем максимальное из чисел зависимости ее операндов }

if iDepTmp > Result then Result:= iDepTmp+1

else Inc(Result);

Trd.Info:= Result;

end;

procedure OptimizeSame(listTriad: TTriadList);

{ Процедура оптимизации путем исключения лишних операций }

var

i,j,iStart,iCnt,iNum: integer;

Ops: TOpArray;

Trd: TTriad;

begin { Начало линейного участка – начало списка триад }

iStart:= 0;

ClearTreeInfo; { Очищаем информационные структуры

таблицы идентификаторов }

Ops[1].OpType:= OP_LINK; { Заполняем операнды }

Ops[2].OpType:= OP_CONST; { для триады типа «SAME» }

Ops[2].ConstVal:= 0;

iCnt:= listTriad.Count-1;

for i:=0 to iCnt do { Для всех триад списка }

begin { выполняем алгоритм }

Trd:= listTriad[i];

if Trd.IsLinked then {Если триада помечена ссылкой, }

begin { то линейный участок кода закончен – очищаем }

ClearTreeInfo; { информационные структуры идентификаторов и }

iStart:= i; { запоминаем начало линейного участка }

end;

for j:=1 to 2 do { Если любой операнд триады ссылается

if Trd[j].OpType = OP_LINK then { на триаду «SAME», }

begin { то переставляем ссылку на предыдущую, }

iNum:= Trd[j].TriadNum;{ совпадающую с ней триаду }

if listTriad[iNum].TrdType = TRD_SAME then

Trd.Links[j]:= listTriad[iNum].Links[1];

end;

if Trd.TrdType = TRD_ASSIGN then { Если триада типа }

begin { «присвоение» – запоминаем число зависимости

связанной с нею переменной }

Trd[1].VarLink.Info:= TDepInfo.Create(i+1);

end

else { Если триада – одна из линейных операций }

if Trd.TrdType in TriadLineSet then

begin { Вычисляем число зависимости триады }

CalcDep(listTriad,Trd);

for j:=iStart to i-1 do { На всем линейном участке }

begin { ищем совпадающую триаду с таким же }

if Trd.IsEqual(listTriad[j]) { числом зависимости }

and (Trd.Info = listTriad[j].Info) then

begin { Если триада найдена, запоминаем ссылку }

Ops[1].TriadNum:= j;

{ запоминаем ее в триаде типа «SAME», которую

записываем в список вместо прежней триады }

listTriad.Items[i]:=

TTriad.Create(TRD_SAME,Ops);

listTriad[i].IsLinked:= Trd.IsLinked; { Если на

прежнюю триаду была ссылка, сохраняем ее }

Trd.Free; { Уничтожаем прежнюю триаду }

Break; { Прерываем поиск }

end;

end;

end{if};

end{for};

end;

end.

Модуль создания списка триад на основе дерева разбора

Листинг П3.12. Создание списка триад на основе дерева разбора

unit TrdMake; {!!! Зависит от входного языка!!!}

interface

{ Модуль, обеспечивающий создание списка триад на основе

структуры синтаксического разбора }

uses LexElem, Triads, SyntSymb;

function MakeTriadList(symbTop: TSymbol;

listTriad: TTriadList): TLexem;

{ Функция создания списка триад начиная от корневого

символа дерева синтаксического разбора.

Функция возвращает nil при успешном выполнении, иначе

она возвращает ссылку на лексему, где произошла ошибка }

implementation

uses LexType, TrdType;

function GetLexem(symbOp: TSymbol): TLexem;

{ Функция, проверяющая, является ли операнд лексемой }

begin

case symbOp.Rule of

0: Result:= symbOp.Lexem; {Нет правил – это лексема!}

27,28: Result:= symbOp[0].Lexem; { Если дочерний

символ построен по правилу № 27 или 28, то это лексема }

19,26: Result:= GetLexem(symbOp[1]) { Если это

арифметические скобки, надо проверить,

не является ли лексемой операнд в скобках }

else Result:= nil; { Иначе это не лексема }

end;

end;

function MakeTriadListNOP(symbTop: TSymbol;

listTriad: TTriadList): TLexem;

{ Функция создания списка триад начиная от корневого

символа дерева синтаксического разбора

(без добавления триады NOP в конец списка) }

var

Opers: TOpArray; { массив операндов триад }

iIns1,iIns2,iIns3: integer; { переменные для запоминания

индексов триад в списке }

function MakeOperand(

iOp{номер операнда},

iSymOp{порядковый номер символа в синтаксической конструкции},

iMin{минимальная позиция триады в списке},

iSymErr{номер лексемы, на который

позиционировать ошибку}: integer;

var iIns: integer{индекс триады в списке}): TLexem;

{ Функция формирования ссылки на операнд }

var lexTmp: TLexem;

begin

lexTmp:= GetLexem(symbTop[iSymOp]); { Проверяем, }

if lexTmp <> nil then { является ли операнд лексемой }

with lexTmp do { Если да, то берем имя операнда }

begin { в зависимости от типа лексемы }

if LexType = LEX_VAR then

begin

if VarInfo.VarName = NAME_RESULT then

begin{Убеждаемся, что переменная имеет допустимое имя}

Result:= lexTmp;

Exit;

end; { Если это переменная, то запоминаем ссылку

на таблицу идентификаторов }

Opers[iOp].OpType:= OP_VAR;

Opers[iOp].VarLink:= VarInfo;

end

else

if LexType = LEX_CONST then

begin { Если это константа, то запоминаем ее значение }

Opers[iOp].OpType:= OP_CONST;

Opers[iOp].ConstVal:= ConstVal;

end

else begin { Иначе это ошибка, возвращаем лексему }

Result:= lexTmp; { как указатель на место ошибки }

Exit;

end;

iIns:= iMin; Result:= nil;

end

else { иначе это синтаксическая конструкция }

begin {Вызываем рекурсивно функцию создания списка триад}

Result:= MakeTriadListNOP(symbTop[iSymOp],listTriad);

if Result <> nil then Exit; {Ошибка – прерываем алгоритм}

iIns:= listTriad.Count; { Запоминаем индекс триады }

if iIns <= iMin then {Если индекс меньше минимального —}

begin { это ошибка }

Result:= symbTop[iSymErr].Lexem;

Exit;

end;

Opers[iOp].OpType:= OP_LINK;{Запоминаем ссылку на}

Opers[iOp].TriadNum:= iIns-1; {предыдущую триаду }

end;

end;

function MakeOperation(

Trd: TTriadType{тип создаваемой триады}): TLexem;

{ Функция создания списка триад для линейных операций }

begin { Создаем ссылку на первый операнд }

Result:= MakeOperand(1{op},0{sym},listTriad.Count,

1{sym err},iIns1);

if Result <> nil then Exit; {Ошибка – прерываем алгоритм}

{ Создаем ссылку на второй операнд }

Result:= MakeOperand(2{op},2{sym},iIns1,

1{sym err},iIns2);

if Result <> nil then Exit; {Ошибка – прерываем алгоритм}

{ Создаем саму триаду с двумя ссылками на операнды }

listTriad.Add(TTriad.Create(Trd,Opers));

end;

begin { Тело главной функции }

case symbTop.Rule of { Начинаем с выбора типа правила }

5:{'if(B)EelseE'} { Полный условный оператор }

begin { Запоминаем ссылку на первый операнд

(условие «if(B)») }

Result:= MakeOperand(1{op},2{sym},listTriad.Count,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

Opers[2].OpType:= OP_LINK; { Второй операнд – }

Opers[2].TriadNum:= 0; {ссылка на триаду, номер

которой пока не известен}

{ Создаем триаду типа «IF» }

listTriad.Add(TTriad.Create(TRD_IF,Opers));

{ Запоминаем ссылку на второй операнд (раздел «(B)E») }

Result:= MakeOperand(2{op},4{sym},iIns1,

3{sym err},iIns2);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

Opers[1].OpType:= OP_CONST; {Заполняем операнды}

Opers[1].ConstVal:= 1; { для триады типа «JMP»,

которая должна быть в конце раздела «(B)E»}

Opers[2].OpType:= OP_LINK; { Второй операнд – }

Opers[2].TriadNum:= 0; {ссылка на триаду, номер

которой пока не известен}

{ Создаем триаду типа «JMP» }

listTriad.Add(TTriad.Create(TRD_JMP,Opers));

{ Для созданной ранее триады «IF» ставим ссылку

в конец последовательности триад раздела «(B)E» }

listTriad[iIns1].Links[2]:= iIns2+1;

{ Запоминаем ссылку на третий операнд (раздел «elseE») }

Result:= MakeOperand(2{op},6{sym},iIns2,

5{sym err},iIns3);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Для созданной ранее триады «JMP» ставим ссылку

в конец последовательности триад раздела «elseE» }

listTriad[iIns2].Links[2]:= iIns3;

end;

6:{'if(B)E'} { Неполный условный оператор }

begin { Запоминаем ссылку на первый операнд

(условие «if(B)») }

Result:= MakeOperand(1{op},2{sym},listTriad.Count,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

Opers[2].OpType:= OP_LINK; { Второй операнд – }

Opers[2].TriadNum:= 0; {ссылка на триаду, номер

которой пока не известен}

{ Создаем триаду типа «IF» }

listTriad.Add(TTriad.Create(TRD_IF,Opers));

{ Запоминаем ссылку на второй операнд (раздел «(B)E») }

Result:= MakeOperand(2{op},4{sym},iIns1,

3{sym err},iIns2);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Для созданной ранее триады «IF» ставим ссылку

в конец последовательности триад раздела «(B)E» }

listTriad[iIns1].Links[2]:= iIns2;

end;

8:{'while(B)doE'} { Оператор цикла «while» }

begin { Запоминаем ссылку на первый операнд

(условие «while(B)») }

iIns3:= listTriad.Count;

Result:= MakeOperand(1{op},2{sym},iIns3,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

Opers[2].OpType:= OP_LINK; { Второй операнд – }

Opers[2].TriadNum:= 0; {ссылка на триаду, номер

которой пока не известен}

{ Создаем триаду типа «IF» }

listTriad.Add(TTriad.Create(TRD_IF,Opers));

{ Запоминаем ссылку на второй операнд (раздел «doE») }

Result:= MakeOperand(2{op},5{sym},iIns1,

4{sym err},iIns2);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

Opers[1].OpType:= OP_CONST; {Заполняем операнды}

Opers[1].ConstVal:= 1; { для триады типа «JMP»,

которая должна быть в конце раздела «doE» }

{ Второй операнд – ссылка на начало списка триад }

Opers[2].OpType:= OP_LINK;

Opers[2].TriadNum:= iIns3;

{ Создаем триаду типа «JMP» }

listTriad.Add(TTriad.Create(TRD_JMP,Opers));

{ Для созданной ранее триады «IF» ставим ссылку

в конец последовательности триад раздела «doE» }

listTriad[iIns1].Links[2]:= iIns2+1;

end;

9:{'a:=E'} { Оператор присвоения }

begin { Если первый операнд не является переменной,

то это ошибка }

if symbTop[0].Lexem.LexType <> LEX_VAR then

begin

Result:= symbTop[0].Lexem; Exit;

end; { Если имя первого операнда совпадает с именем

параметра, то это семантическая ошибка }

if (symbTop[0].Lexem.VarName = NAME_INPVAR)

or (symbTop[0].Lexem.VarName = NAME_RESULT) then

begin

Result:= symbTop[0].Lexem; Exit;

end;

{ Создаем ссылку на первый операнд – переменную }

Opers[1].OpType:= OP_VAR;

Opers[1].VarLink:= symbTop[0].Lexem.VarInfo;

{ Создаем ссылку на второй операнд }

Result:= MakeOperand(2{op},2{sym},listTriad.Count,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Создаем триаду типа «присваивание» }

listTriad.Add(TTriad.Create(TRD_ASSIGN,Opers));

end;

{ Генерация списка триад для линейных операций }

10:{'BorB'} Result:= MakeOperation(TRD_OR);

11:{'BxorB'} Result:= MakeOperation(TRD_XOR);

13:{'BandB'} Result:= MakeOperation(TRD_AND);

15:{'E<E'} Result:= MakeOperation(TRD_LT);

16:{'E>E'} Result:= MakeOperation(TRD_GT);

17:{'E=E'} Result:= MakeOperation(TRD_EQ);

18:{'E<>E'} Result:= MakeOperation(TRD_NEQ);

21:{'E-E'} Result:= MakeOperation(TRD_SUB);

22:{'E+E'} Result:= MakeOperation(TRD_ADD);

20:{not(B)}

begin { Создаем ссылку на первый операнд }

Result:= MakeOperand(1{op},2{sym},listTriad.Count,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

Opers[2].OpType:= OP_CONST; {Второй операнд для}

Opers[2].ConstVal:= 0; { NOT не имеет значения }

{ Создаем триаду типа «NOT» }

listTriad.Add(TTriad.Create(TRD_NOT,Opers));

end;

24:{uminE}

begin { Создаем ссылку на второй операнд }

Result:= MakeOperand(2{op},1{sym},listTriad.Count,

0{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

Opers[1].OpType:= OP_CONST; {Первый операнд для}

Opers[1].ConstVal:= 0; { унарной операции "-"

должен быть 0 }

{ Создаем триаду типа «UMIN» }

listTriad.Add(TTriad.Create(TRD_UMIN,Opers));

end;

{ Для логических, арифметических или операторных скобок

рекурсивно вызываем функцию для второго символа }

1,7,19,26:{'progEend.,'beginEend', (E), (B) }

Result:= MakeTriadListNOP(symbTop[1],listTriad);

3:{E;E Для списка операторов нужно рекурсивно вызвать}

begin { функцию два раза }

Result:= MakeTriadListNOP(symbTop[0],listTriad);

if Result <> nil then Exit;

Result:= MakeTriadListNOP(symbTop[2],listTriad);

end;

27,28: Result:= nil; { Для лексем ничего не нужно }

{ Во всех остальных случаях нужно рекурсивно вызвать

функцию для первого символа }

else Result:= MakeTriadListNOP(symbTop[0],listTriad);

end{case Rule};

end;

function MakeTriadList(symbTop: TSymbol;

listTriad: TTriadList): TLexem;

{ Функция создания списка триад начиная от корневого

символа дерева синтаксического разбора }

var

i: integer;

Opers: TOpArray;

Trd: TTriad;

begin { Создаем список триад }

Result:= MakeTriadListNOP(symbTop,listTriad);

if Result = nil then {Если ошибка, прерываем выполнение}

with listTriad do

begin { Создаем пустую триаду «NOP» в конце списка }

Opers[1].OpType:= OP_CONST;

Opers[1].ConstVal:= 0;

Opers[2].OpType:= OP_CONST;

Opers[2].ConstVal:= 0;

Add(TTriad.Create(TRD_NOP,Opers));

for i:=Count-1 downto 0 do

begin {Для всех триад в списке расставляем флаг ссылки}

Trd:= Triads[i];

if Trd.TrdType in [TRD_IF,TRD_JMP] then

begin { Если триада «переход» («IF» или «JMP»)

ссылается на другую триаду,}

if Trd.OpTypes[2] = OP_LINK then

listTriad[Trd.Links[2]].IsLinked:= True;

{ то ту триаду надо пометить }

end;

end;

end;

end;

end.

Модуль построения ассемблерного кода по списку триад

Листинг П3.13. Построение ассемблерного кода по списку триад

unit TrdAsm;

{!!! Зависит от целевой вычислительной системы!!! }

interface

{ Модуль распределения регистров и построения ассемблерного

кода по списку триад }

uses Classes, TrdType, Triads;

const { Префикс наименования временных переменных }

TEMP_VARNAME = _Tmp';

NUM_PROCREG = 6; { Количество доступных регистров }

{ Функция распределения регистров и временных переменных

для хранения промежуточных результатов триад }

function MakeRegisters(listTriad: TTriadList): integer;

{ Функция построения ассемблерного кода по списку триад }

function MakeAsmCode(listTriad: TTriadList;

listCode: TStrings;

flagOpt: Boolean): integer;

implementation

uses SysUtils;

function MakeRegisters(listTriad: TTriadList): integer;

{ Функция распределения регистров и временных переменных

для хранения промежуточных результатов триад.

Результат: количество необходимых временных переменных }

var

i,j,iR,iCnt,iNum: integer;{Счетчики и переменные циклов}

{ Динамический массив для запоминания занятых регистров }

listReg: TList;

begin { Создаем массив для хранения занятых регистров }

listReg:= TList.Create;

Result:= 0;

if listReg <> nil then

try { Обнуляем информационное поле у всех триад }

for i:=listTriad.Count-1 downto 0 do

listTriad[i].Info:= 0;

{ Цикл по всем триадам. Обязательно с конца списка! }

for i:=listTriad.Count-1 downto 0 do

for j:=1 to 2 do { Цикл по всем (2) операндам }

{ Если триада – линейная операция, или «IF»

(первый операнд), или присвоение (второй операнд) }

if ((listTriad[i].TrdType in TriadLineSet)

or (listTriad[i].TrdType = TRD_IF) and (j = 1)

or (listTriad[i].TrdType = TRD_ASSIGN) and (j = 2))

{ и операндом является ссылка на другую триаду }

and (listTriad[i][j].OpType = OP_LINK) then

begin { Запоминаем номер триады, на которую направлена ссылка }

iNum:= listTriad[i][j].TriadNum;

{ Если триаде еще не назначен регистр и если это

не предыдущая триада – надо ей назначить регистр }

if (listTriad[iNum].Info = 0) and (iNum <> i-1) then

begin { Количество назначенных регистров }

iCnt:= listReg.Count-1;

for iR:=0 to iCnt do

begin{ Цикл по массиву назначенных регистров }

{ Если область действия регистра за пределами

текущей триады, то его можно использовать }

if longint(listReg[iR]) >= i then

begin { Запоминаем область действия регистра }

listReg[iR]:= TObject(iNum);

{ Назначаем регистр триаде с номером iNum }

listTriad[iNum].Info:= iR+1;

Break; { Прерываем цикл по массиву регистров }

end;

end; { Если ни один из использованных регистров

не был назначен, надо брать новый регистр }

if listTriad[iNum].Info = 0 then

begin { Добавляем запись в массив регистров,

указываем ей область действия iNum }

listReg.Add(TObject(iNum));

{ Назначаем новый регистр триаде с номером iNum }

listTriad[iNum].Info:= listReg.Count;

end;

end;

end;{ Результат функции: количество записей в массиве

регистров -1, за вычетом числа доступных регистров}

Result:= listReg.Count – (NUM_PROCREG-1);

finally listReg.Free;

end;

end;

function GetRegName(iInfo: integer): string;

{ Функция наименования регистров процессора }

begin

case iInfo of

0: Result:= 'eax';

1: Result:= 'ebx';

2: Result:= 'ecx';

3: Result:= 'edx';

4: Result:= 'esi';

5: Result:= 'edi';

{ Если это не один из регистров – значит,

даем имя временной переменной }

else Result:=

Format(%s%d',[TEMP_VARNAME,iInfo-NUM_PROCREG]);

end{case};

end;

function GetOpName(i: integer; listTriad: TTriadList;

iOp: integer): string;

{ Функция наименования операнда триады

i – номер триады в списке;

listTriad – список триад;

iOp – номер операнда триады }

var iNum: integer; {номенр триады по ссылке}

Triad: TTriad; {текущая триада}

begin

Triad:= listTriad[i]; { Запоминаем текущую триаду }

{ Выборка наименования операнда в зависимости от типа }

case Triad[iOp].OpType of

{ Если константа – значение константы }

OP_CONST: Result:= IntToStr(Triad[iOp].ConstVal);

{ Если переменная – ее имя из таблицы идентификаторов }

OP_VAR:

begin

Result:= Triad[iOp].VarLink.VarName;

{ Если имя совпадает с именем функции,

заменяем его на Result функции }

if Result = NAME_FUNCT then Result:= NAME_RESULT;

end; { Иначе – это регистр }

else { для временного хранения результатов триады }

begin { Запоминаем номер триады }

iNum:= Triad[iOp].TriadNum;

{ Если это предыдущая триада, то операнд не нужен }

if iNum = i-1 then Result:=

else

begin {Берем номер регистра, связанного с триадой}

iNum:= listTriad[iNum].Info;

{ Если регистра нет, то операнд не нужен }

if iNum = 0 then Result:=

{ Иначе имя операнда – это имя регистра }

else Result:= GetRegName(iNum);

end;

end;

end{case};

end;

function MakeMove(const sReg,{имя регистра}

sPrev,{предыдущая команда}

sVal{предыдущая величина в eax}: string;

flagOpt: Boolean{флаг оптимизации}): string;

{ Функция, генерящая код занесения значения в регистр eax }

begin { Если операнд был только что выгружен из eax

или необходимое значение уже есть в аккумуляторе,

нет необходимости записывать его туда снова }

if (Pos(Format(#9'mov'#9 %s,eax',[sReg]), sPrev) = 1)

or (sVal = sReg) then

begin

Result:= ; Exit;

end;

if flagOpt then { Если оптимизация команд включена }

begin

if sReg = 0 then { Если требуемое значение = 0, }

begin{его можно получить из –1 и 1 с помощью INC и DEC}

if sVal = -1 then Result:= #9'inc'#9'eax'

else

if sVal = 1 then Result:= #9'dec'#9'eax'

else Result:= #9'xor'#9'eax,eax'

end {иначе – с помощью XOR}

else

if sReg = 1 then { Если требуемое значение = 1, }

begin{его можно получить из –1 и 0 с помощью NEG и INC}

if sVal = -1 then Result:= #9'neg'#9'eax'

else

if sVal = 0 then Result:= #9'inc'#9'eax'

else

Result:= #9'xor'#9'eax,eax'#13#10#9'inc'#9'eax';

end {иначе – двумя командами: XOR и INC }

else

if sReg = -1 then { Если требуемое значение = -1, }

begin{его можно получить из 1 и 0 с помощью NEG и DEC}

if sVal = 1 then Result:= #9'neg'#9'eax'

else

if sVal = 0 then Result:= #9'dec'#9'eax'

else

Result:= #9'xor'#9'eax,eax'#13#10#9'dec'#9'eax';

end {иначе – двумя командами: XOR и DEC }

{ Иначе заполняем eax командой MOV }

else Result:= Format(#9'mov'#9'eax,%s',[sReg]);

end { Если оптимизация команд выключена,

всегда заполняем eax командой MOV }

else Result:= Format(#9'mov'#9'eax,%s',[sReg]);

end;

function MakeOpcode(i: integer;{номер текущей триады}

listTriad: TTriadList;{список триад}

const sOp,sReg,{код операции и операнд}

sPrev,{предыдущая команда}

sVal{предыдущая величина в eax}: string;

flagOpt: Boolean{флаг оптимизации}): string;

{ Функция, генерящая код линейных операций над eax }

var Triad: TTriad;{текущая триада}

begin { Запоминаем текущую триаду }

Triad:= listTriad[i];

if flagOpt then { Если оптимизация команд включена }

begin

if sReg = 0 then { Если операнд = 0 }

begin

case Triad.TrdType of

TRD_AND: { Для команды AND результат всегда = 0 }

Result:= MakeMove(0 ,sPrev,sVal,flagOpt);

{ Для OR, "+" и «-» ничего не надо делать }

TRD_OR,TRD_ADD,TRD_SUB: Result:= #9#9;

{ Иначе генерируем код выполняемой операции }

else Result:= Format(#9 %s'#9'eax,%s',[sOp,sReg]);

end{case};

end

else

if sReg = 1 then { Если операнд = 1 }

begin

case Triad.TrdType of

TRD_OR: { Для команды OR результат всегда = 1 }

Result:= MakeMove(1 ,sPrev,sVal,flagOpt);

{ Для AND ничего не надо делать }

TRD_AND: Result:= #9#9;

{ Для "+" генерируем операцию INC }

TRD_ADD: Result:= #9'inc'#9'eax';

{ Для «-» генерируем операцию DEC }

TRD_SUB: Result:= #9'dec'#9'eax';

{ Иначе генерируем код выполняемой операции }

else Result:= Format(#9 %s'#9'eax,%s',[sOp,sReg]);

end{case};

end

else

if sReg = -1 then { Если операнд = -1 }

begin

case Triad.TrdType of

{ Для "+" генерируем операцию DEC }

TRD_ADD: Result:= #9'dec'#9'eax';

{ Для «-» генерируем операцию INC }

TRD_SUB: Result:= #9'inc'#9'eax';

{ Иначе генерируем код выполняемой операции }

else Result:= Format(#9 %s'#9'eax,%s',[sOp,sReg]);

end{case};

end { Иначе генерируем код выполняемой операции }

else Result:= Format(#9 %s'#9'eax,%s',[sOp,sReg]);

end { Если оптимизация команд выключена,

всегда генерируем код выполняемой операции }

else Result:= Format(#9 %s'#9'eax,%s',[sOp,sReg]);

{ Добавляем к результату информацию о триаде

в качестве комментария }

Result:= Result + Format(#9 { %s },

[Triad.MakeString(i)]);

end;

function MakeAsmCode(

listTriad: TTriadList;{входной список триад}

listCode: TStrings;{список строк результирующего кода}

flagOpt: Boolean{флаг оптимизации}): integer;

{ Функция построения ассемблерного кода по списку триад }

var i,iCnt: integer;{счетчик и переменная цикла}

sR: string;{строка для имени регистра}

sPrev,sVal: string;

{строки для хранения предыдущей команды и значения eax}

procedure TakePrevAsm;

{ Процедура, выделяющая предыдущую команду и значение eax

из списка результирующих команд }

var j: integer;

begin

j:= listCode.Count;

if j > 0 then

begin

sPrev:= listCode[j-1];

sVal:= StrPas(PChar(listCode.Objects[j-1]));

end

else

begin

sPrev:= ; sVal:= ;

end;

end;

procedure MakeOper1(const sOp,{код операции}

sAddOp: string;{код дополнительной операции}

iOp: integer{номер операнда в триаде});

{ Функция генерации кода для унарных операций }

var sReg{строка для имени регистра}: string;

begin

TakePrevAsm; {Берем предыдущую команду и значение из eax}

{ Запоминаем имя операнда }

sReg:= GetOpName(i,listTriad,iOp);

if sReg <> then { Если имя пустое, операнд уже есть в

регистре eax от выполнения предыдущей триады,}

begin { иначе его нужно занести в eax }

{ Вызываем функцию генерации кода занесения операнда }

sReg:= MakeMove(sReg,sPrev,sVal,flagOpt);

if sReg <> then listCode.Add(sReg);

end; { Генерируем непосредственно код операции }

listCode.Add(Format(#9 %s'#9'eax'#9 { %s },

[sOp,listTriad[i].MakeString(i)]));

if sAddOp <> then { Если есть дополнительная операция,

генерируем ее код }

listCode.Add(Format(#9 %s'#9'eax,1,[sAddOp]));

if listTriad[i].Info <> 0 then { Если триада связана с

begin { регистром, запоминаем результат в этом регистре }

sReg:= GetRegName(listTriad[i].Info);

{ При этом запоминаем, что сейчас находится в eax }

listCode.AddObject(Format(#9'mov'#9 %s,eax',[sReg]),

TObject(PChar(sReg)));

end;

end;

procedure MakeOper2(const sOp,{код операции}

sAddOp: string{код дополнительная операции});

{ Функция генерации кода для бинарных арифметических

и логических операций }

var sReg1,sReg2{строки для имен регистров}: string;

begin

TakePrevAsm; {Берем предыдущую команду и значение из eax}

{ Запоминаем имена первого и второго операндов }

sReg1:= GetOpName(i,listTriad,1);

sReg2:= GetOpName(i,listTriad,2);

{ Если имя первого операнда пустое, значит, он уже

есть в регистре eax от выполнения предыдущей триады -

вызываем функцию генерации кода для второго операнда }

if (sReg1 = ) or (sReg1 = sVal) then

listCode.Add(MakeOpCode(i,listTriad,sOp,sReg2,

sPrev,sVal,flagOpt))