В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 26
Текст из файла (страница 26)
Действительно, если ближайшей общей вершинойявляется AND, то в левого потомка передается NodeLab правого потомка в качестве TrueLab и одновременно Sign правого потомка равен true.Если же ближайшей общей вершиной является OR, то в левого потомкапередается NodeLab правого потомка в качестве FalseLab и одновременноSign правого потомка равен f alse.
Во все же правые потомки значенияTrueLab, FalseLab и Sign передаются из предка (за исключением правиладля NOT, в котором TrueLab и FalseLab меняются местами, но одновременно на противоположный меняется и Sign).9.8. ВЫДЕЛЕНИЕ ОБЩИХ ПОДВЫРАЖЕНИЙ165Эти два утверждения (3 и 4) позволяют заменить последнее правилоатрибутной грамматики следующим образом:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" +(Sign<0>? "if (" + Val<1> + "==T) GOTO" + TrueLab<0>: "if (" + Val<1> + "==F) GOTO" + FalseLab<0>).В свою очередь, при генерации машинных команд это правило можно заменить на следующее:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" + "TST" + Val<1> +(Sign<0>? "BNE" + TrueLab<0>: "BEQ" + FalseLab<0>).Таким образом, для выражения A OR ( B AND C AND D ) OR E получимследующий код на командах перехода:1:7:TST ABNE True2:8:4:9: TST BBEQ 35:10: TST CBEQ 36:TST DBNE True3:TST EBEQ FalseTrue: ...False: ...Если элементом логического выражения является сравнение, то генерируется команда, соответствующая знаку сравнения (BEQ для =, BNEдля <>, BGE для >= и т.д.), если атрибут Sign соответствующей вершиныимеет значение true, и отрицание (BNE для =, BEQ для <>, BLT для >= и т.д.),если атрибут Sign имеет значение f alse.9.8Выделение общих подвыраженийВыделение общих подвыражений относится к области оптимизации программ.
В общем случае трудно (или даже невозможно) провести грани-166ГЛАВА 9. ГЕНЕРАЦИЯ КОДАцу между оптимизацией и “качественной трансляцией”. Оптимизация- это и есть качественная трансляция. Обычно термин “оптимизация”употребляют, когда для повышения качества программы используютее глубокие преобразования такие, например, как перевод в графовуюформу для изучения нетривиальных свойств программы.В этом смысле выделение общих подвыражений – одна из простейших оптимизаций. Для ее осуществления требуется некоторое преобразование программы, а именно построение ориентированного ациклического графа, о котором говорилось в главе, посвященной промежуточным представлениям.Линейный участок – это последовательность операторов, в которуюуправление входит в начале и выходит в конце без остановки и переходаизнутри.Рассмотрим дерево линейного участка, в котором вершинами служат операции, а потомками – операнды.
Будем говорить, что две вершины образуют общее подвыражение, если поддеревья для них совпадают, т.е. имеют одинаковую структуру и, соответственно, одинаковыеоперации во внутренних вершинах и одинаковые операнды в листьях.Выделение общих подвыражений позволяет генерировать для них кододин раз, хотя может привести и к некоторым трудностям, о чем вкратце будет сказано ниже.Выделение общих подвыражений проводится на линейном участке иосновывается на двух положениях.1.
Поскольку на линейном участке переменной может быть несколько присваиваний, то при выделении общих подвыражений необходиморазличать вхождения переменных до и после присваивания. Для этогокаждая переменная снабжается счетчиком. Вначале счетчики всех переменных устанавливаются равными 0. При каждом присваивании переменной ее счетчик увеличивается на 1.2. Выделение общих подвыражений осуществляется при обходе дерева выражения снизу вверх слева направо. При достижении очередной вершины (пусть операция, примененная в этой вершине, есть бинарная op; в случае унарной операции рассуждения те же) просматриваем общие подвыражения, связанные с op.
Если имеется выражение,связанное с op и такое, что его левый операнд есть общее подвыражениес левым операндом нового выражения, а правый операнд - общее подвыражение с правым операндом нового выражения, то объявляем новое выражение общим с найденным и в новом выражении запоминаемуказатель на найденное общее выражение.
Базисом построения служитпеременная: если операндами обоих выражений являются одинаковыепеременные с одинаковыми счетчиками, то они являются общими подвыражениями. Если выражение не выделено как общее, оно заноситсяв список операций, связанных с op.Рассмотрим теперь реализацию алгоритма выделения общих подвыражений. Поддерживаются следующие глобальные переменные:Table – таблица переменных; для каждой переменной хранится ее счет-9.8.
ВЫДЕЛЕНИЕ ОБЩИХ ПОДВЫРАЖЕНИЙ167чик (Count) и указатель на вершину дерева выражений, в которой переменная встретилась в последний раз в правой части (Last);OpTable – таблица списков (типа LisType) общих подвыражений, связанных с каждой операцией. Каждый элемент списка хранит указательна вершину дерева (поле Addr) и продолжение списка (поле List).С каждой вершиной дерева выражения связана запись типа NodeType,со следующими полями:Left – левый потомок вершины,Right – правый потомок вершины,Comm – указатель на предыдущее общее подвыражение,Flag – признак, является ли поддерево общим подвыражением,Varbl – признак, является ли вершина переменной,VarCount – счетчик переменной.Выделение общих подвыражений и построение дерева осуществляютсяприведенными ниже правилами.
Атрибут Entry нетерминала Variable дает указатель на переменную в таблице Table. Атрибут Val символа Op даеткод операции. Атрибут Node символов IntExpr и Assignment дает указательна запись типа NodeType соответствующего нетерминала.RULEAssignment ::= Variable IntExprSEMANTICSTable[Entry<1>].Count=Table[Entry<1>].Count+1.// Увеличить счетчик присваиваний переменнойRULEIntExpr ::= VariableSEMANTICSif ((Table[Entry<1>].Last!=NULL)// Переменная уже была использована&& (Table[Entry<1>].Last->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.// Выражение - переменная168ГЛАВА 9.
ГЕНЕРАЦИЯ КОДАRULEIntExpr ::= Op IntExpr IntExprSEMANTICSLisType * 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;//Указатель на предыдущее общее подвыражение или NULLif (L!=NULL){Node<0>->Flag=true; //Общее подвыражениеNode<0>->Left=Node<2>;// Указатель на левое поддеревоNode<0>->Right=Node<3>;// Указатель на правое поддерево}else {Node<0>->Flag=false;// Данное выражение не может рассматриваться как общее// Если общего подвыражения с данным не было,// включить данное в список для операцииL=alloc(sizeof(struct LisType));L->Addr=Node<0>;L->List=OpTable[Val<1>];OpTable[Val<1>]=L;}.Рассмотрим теперь некоторые простые правила распределения регистров при наличии общих подвыражений.
Если число регистров ограничено, можно выбрать один из следующих двух вариантов.1. При обнаружении общего подвыражения с подвыражением в ужепросмотренной части дерева (и, значит, с уже распределенными регистрами) проверяем, расположено ли его значение на регистре. Если да,и если регистр после этого не менялся, заменяем вычисление поддерева9.9. ГЕНЕРАЦИЯ ОПТИМАЛЬНОГО КОДА МЕТОДАМИ СИНТАКСИЧЕСКОГО АНАЛИЗА169на значение в регистре. Если регистр менялся, то вычисляем подвыражение заново.2. Вводим еще один проход.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
