Лекции по конструированию компиляторов. В.А. Серебряков (1134687), страница 22

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 22)

Действительно, по правилам наследования атрибутов TrueLab и FalseLab, в правилах для дизъюнкции и конъюнкции либо FalseLab, либо TrueLab принимает значение метки следующего поддерева. Кроме того, как значение FalseLab, так и значение TrueLab, передаются в правое поддерево от предка. Таким образом, самый правый потомок всегда имеет одну из меток TrueLab или FalseLab, равную метке правого брата соответствующего поддерева. Учитывая порядок генерации команд, получаем утверждение.

Дополним теперь атрибутную грамматику следующим образом:

RULE
Expr ::= BoolExpr
SEMANTICS
FalseLab<1>=False; TrueLab<1>=True;
Sign<1>=false;
Code<0>=Code<1>.

RULE
BoolExpr ::= BoolExpr 'AND' BoolExpr
SEMANTICS
FalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;
FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;
Sign<1>=false; Sign<3>=Sign<0>;
Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.

RULE
BoolExpr ::= BoolExpr 'OR' BoolExpr
SEMANTICS
TrueLab<1>=TrueLab<0>; FalseLab<1>=NodeLab<3>;
FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;
Sign<1>=true; Sign<3>=Sign<0>;
Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.

RULE
BoolExpr ::= NOT BoolExpr
SEMANTICS
FalseLab<1>=TrueLab<0>; TrueLab<1>=FalseLab<0>;
Sign<1>=! Sign<0>;
Code<0>=Code<1>.

RULE
BoolExpr ::= F
SEMANTICS
Code<0>=”GOTO FalseLab<0>”.

RULE
BoolExpr ::= T
SEMANTICS
Code<0>=”GOTO TrueLab<0>”.

RULE
BoolExpr ::= Ident
SEMANTICS
Code<0>=”if (Val<1>==T) GOTO TrueLab<0>
else GOTO FalseLab<0>”.

Правила наследования атрибута Sign приведены на рис. 8.24.

f alse | 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
Code<0>=Sign<0>
? ”if (Val<1>==T) GOTO TrueLab<0>”
: ”if Val<1>==F) GOTO FalseLab<0>”.

В свою очередь, при генерации машинных команд это правило можно заменить на следующее:

RULE
BoolExpr ::= Ident
SEMANTICS
<TST Ident>;
Code<0>=Sign<0>
? ”BNE TrueLab<0>”
: ”BEQ FalseLab<0>”.

Если элементом логического выражения является сравнение, то генерируется команда, соответствующая знаку сравнения (beq для =, bne для <>, bge для >= и т.д.), если атрибут sign соответствующей вершины имеет значение true, и отрицание (bne для =, beq для <>, blt для >= и т.д.), если атрибут sign имеет значение false.

Приведем несколько примеров. Выражение A AND (B OR C) транслируется в последовательность команд рис. 8.25. Выражение (NOT((A==B)OR(!=D)))AND(NOT((E<F)AND(G>H))) транслируется в последовательность команд рис. 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).

OP

Рис.8.27

Рассмотрим теперь реализацию алгоритма выделения общих подвыражений. Поддерживаются следующие глобальные переменные:

Table - таблица переменных; для каждой переменной хранится ее номер (Count) и указатель на вершину дерева выражений, в которой переменная встретилась в последний раз в правой части (Last);

OpTable - таблица списков общих подвыражений, связанных с каждой операцией (Addr - указатель на вершину дерева, List - продолжение списка);

С каждой вершиной дерева выражения связана запись (Тип LisType):

struct NodeType {
Left -- левый потомок вершины;
Right -- правый потомок вершины;
Comm -- указатель на предыдущее общее подвыражение;
Flag -- признак, является ли поддерево
общим подвыражением;
Varbl -- признак, является ли вершина переменной;
VarCount -- счетчик переменной;
}

Все общие подвыражения собраны в список (с типом элемента LisType), начинающийся с OpTable[Op], как это изображено на рис. 8.28.

OpTable

OP

Рис. 8.28

Выделение общих подвыражений и построение дерева осуществляются приведенными ниже правилами. Атрибут Entry нетерминала Variable дает указатель на переменную в таблице Table. Атрибут Val символа Op дает код операции. Атрибут Node символов IntExpr и Assignment дает указатель на запись типа NodeType соответствующего нетерминала.

RULE
Assignment ::= Variable IntExpr
SEMANTICS
Table[Entry<1>].Count=Table[Entry<1>].Count+1.
//Увеличить счетчик присваиваний переменной

RULE
IntExpr ::= Variable
SEMANTICS
if ((Table[Entry<1>].Last!=NULL)
// Переменная уже была использована
&& (Table[Entry<1>].Last->Node<0>->VarCount
== Table[Entry<1>].Count ))
//С тех пор переменной не было присваивания
{Node<0>->Flag=true;
//Переменная - общее подвыражение
Node<0>->Comm= Table[Entry<1>].Last;
//Указатель на общее подвыражение
}
else Node<0>->Flag=false;
Table[Entry<1>].Last=Node<0>;
//Указатель на последнее использование переменной
Node<0>->VarCount= Table[Entry<1>].Count;
//Номер использования переменной
Node<0>->Varbl=true. //Выражение – переменная

RULE
IntExpr ::= Op IntExpr IntExpr
SEMANTICS
LisType * L; //Тип списков операции
if ((Node<2>->Flag) && (Node<3>->Flag))
// И справа, и слева - общие подвыражения
{L=OpTable[Val<1>];
// Начало списка общих подвыражений для операции
while (L!=NULL)
if ((Node<2>==L->Left)
&& (Node<3>==L->Right))
// Левое и правое поддеревья совпадают
break;
else L=L->List;//Следующий элемент списка
}
else L=NULL; //Не общее подвыражение

Node<0>->Varbl=false; //Не переменная
Node<0>->Comm=L;
//Указатель на предыдущее общее подвыражение или NULL
if (L!=NULL)
{Node<0>->Flag=true; //Общее подвыражение
Node<0>->Left=Node<2>;
// Указатель на левое поддерево
Node<0>->Right=Node<3>;
// Указатель на правое поддерево
}
else {Node<0>->Flag=false;
// Данное выражение не может рассматриваться как общее
// Если общего подвыражения с данным не было,
// включить данное в список для операции
L=new LisType();
L->Addr=Node<0>;
L->List=OpTable[Val<1>];
OpTable[Val<1>]=L;
}.

Рассмотрим теперь некоторые простые правила распределения регистров при наличии общих подвыражений. Если число регистров ограничено, можно выбрать один из следующих двух вариантов.

1. При обнаружении общего подвыражения с подвыражением в уже просмотренной части дерева (и, значит, с уже распределенными регистрами) проверяем, расположено ли его значение на регистре. Если да, и если регистр после этого не менялся, заменяем вычисление поддерева на значение в регистре. Если регистр менялся, то вычисляем подвыражение заново.

2. Вводим еще один проход. На первом проходе распределяем регистры. Если в некоторой вершине обнаруживается, что ее поддерево общее с уже вычисленным ранее, но значение регистра потеряно, то в такой вершине на втором проходе необходимо сгенерировать команду сброса регистра в рабочую память. Выигрыш в коде будет, если стоимость команды сброса регистра + доступ к памяти в повторном использовании этой памяти не превосходит стоимости заменяемого поддерева. Поскольку стоимость команды MOVE известна, можно сравнить стоимости и принять оптимальное решение: то ли метить предыдущую вершину для сброса, то ли вычислять полностью поддерево.

Характеристики

Список файлов лекций