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

Листинг П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.

Оглавление книги