В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 35
Текст из файла (страница 35)
Генерация кодаCode<0>=Code<1>.RULEBoolExpr ::= BoolExpr ’AND’ BoolExprSEMANTICSFalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Sign<1>=false; Sign<3>=Sign<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= BoolExpr ’OR’ BoolExprSEMANTICSFalseLab<1>=NodeLab<3>; TrueLab<1>=TrueLab<0>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Sign<1>=true; Sign<3>=Sign<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= ’NOT’ BoolExprSEMANTICSFalseLab<2>=TrueLab<0>; TrueLab<2>=FalseLab<0>;Sign<2>=! Sign<0>;Code<0>=Code<2>.RULEBoolExpr ::= FSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + FalseLab<0>.RULEBoolExpr ::= TSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + TrueLab<0>.RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" + "if (" + Val<1> +") GOTO"+ TrueLab<0> + "else GOTO" + FalseLab<0>.Правила наследования атрибута Sign приведены на рис.
9.13.Программу желательно сформировать таким образом, чтобы else-меткабыла как раз меткой следующей вершины. Это можно сделать исходя из следующего утверждения.9.7. Трансляция логических выражений189Рис. 9.13Утверждение 9.4. В каждой терминальной вершине метка ближайшего правого для нее поддерева равна значению атрибута FalseLab этойвершины тогда и только тогда, когда значение атрибута Sign этойвершины равно true, а метка ближайшего правого для нее поддерева равназначению атрибута TrueLab этой вершины тогда и только тогда, когдазначение атрибута Sign равно false.Д о к а з а т е л ь с т в о . Действительно, если ближайшей общей вершиной является AND, то в левого потомка передается NodeLab правого потомкав качестве TrueLab, причем Sign правого потомка равен true.
Если жеближайшей общей вершиной является OR, то в левого потомка передаетсяNodeLab правого потомка в качестве FalseLab, тогда Sign правого потомкаравен f alse. Во все же правые потомки значения TrueLab, FalseLab и Signпередаются из предка (за исключением правила для NOT, в котором TrueLabи FalseLab меняются местами, но одновременно меняется на противоположное и значение Sign).Эти два утверждения (3 и 4) позволяют заменить последнее правилоатрибутной грамматики следующим образом:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" +(Sign<0>? "if (" + Val<1> + ") GOTO" + TrueLab<0>: "if (" + Val<1> + ") GOTO" + FalseLab<0>).В свою очередь, при генерации машинных команд это правило можнозаменить на следующее:RULEBoolExpr ::= IdentSEMANTICSCode<0>="TST" + Val<1> +(Sign<0>? "BNE" + TrueLab<0>: "BEQ" + FalseLab<0>).Таким образом, для выражения A OR (B AND C AND D) OR E получимследующий код на командах перехода:1901:7:Глава 9.
Генерация кодаTSTBNE2:8:4:9: TSTBEQ5:10:TSTBEQ6:TSTBNE3:TSTBEQTrue: ...False: ...ATrueB3C3DTrueEFalseЕсли элементом логического выражения является сравнение, то генерируется команда, соответствующая знаку сравнения (BEQ для =, BNE для <>, BGEдля >= и т. д.), если атрибут Sign соответствующей вершины имеет значениеtrue, или команда, соответсвующая противоположному знаку (BNE для =, BEQдля <>, BLT для >= и т. д.), если атрибут Sign имеет значение f alse.Реализация этой атрибутной схемы приведена в программном приложениив пакете Bool.9.8. Выделение общих подвыраженийВыделение общих подвыражений относится к области оптимизации программ. В общем случае трудно (или даже невозможно) провести границумежду оптимизацией и «качественной трансляцией».
Оптимизация — этои есть качественная трансляция. Обычно термин «оптимизация» употребляют, когда для повышения качества программы используют ее глубокие преобразования, например, такие, как перевод в графовую форму для изучениянетривиальных свойств программы.В этом смысле выделение общих подвыражений — одна из простейшихоптимизаций. Для ее осуществления требуется некоторое преобразованиепрограммы, а именно, построение ориентированного ациклического графа,о котором говорилось в главе 8.Линейный участок — это последовательность операторов, в которуюуправление входит в начале и выходит в конце без остановки и переходаизнутри.Рассмотрим дерево линейного участка, в котором вершинами служат операции, а потомками — операнды.
Будем говорить, что две вершины образуютобщее подвыражение, если поддеревья для них совпадают, т. е. имеют одинаковую структуру и, соответственно, одинаковые операции во внутренних вершинах и одинаковые операнды в листьях. Выделение общих подвыражений9.8. Выделение общих подвыражений191позволяет генерировать для них код один раз, хотя может привести и к некоторым трудностям, о чем вкратце будет сказано ниже.Выделение общих подвыражений проводится на линейном участке и основывается на двух положениях.1. Поскольку на линейном участке переменная может получать несколькоприсваиваний, то при выделении общих подвыражений необходимо различать вхождения переменных до и после присваивания.
Для этого каждаяпеременная снабжается счетчиком. Вначале счетчики всех переменных устанавливаются равными 0. При каждом присваивании переменной ее счетчикувеличивается на 1.2. Выделение общих подвыражений осуществляется при обходе деревавыражения снизу-вверх слева-направо. При достижении очередной вершины(пусть операция, примененная в этой вершине, есть бинарная op; в случаеунарной операции рассуждения те же) просматриваем общие подвыражения,связанные с op. Если имеется выражение, связанное с op и такое, что еголевый операнд есть общее подвыражение с левым операндом нового выражения, а правый операнд - общее подвыражение с правым операндом новоговыражения, то объявляем новое выражение общим с найденным и в новомвыражении запоминаем указатель на найденное общее выражение.
Базисомпостроения служит переменная: если операндами обоих выражений являютсяодинаковые переменные с одинаковыми счетчиками, то они являются общимиподвыражениями. Если выражение не выделено как общее, то оно заноситсяв список операций, связанных с op.Рассмотрим теперь реализацию алгоритма выделения общих подвыражений. Поддерживаются следующие глобальные переменные:Table — таблица переменных; для каждой переменной хранится ее счетчик (Count) и указатель на вершину дерева выражений, в которой переменная встретилась в последний раз в правой части (Last);OpTable — таблица списков (типа LisType) общих подвыражений, связанных с каждой операцией.
Каждый элемент списка хранит указательна вершину дерева (поле Addr) и продолжение списка (поле List).С каждой вершиной дерева выражения связана запись типа NodeTypeсо следующими полями:Left — левый потомок вершины,Right — правый потомок вершины,Comm — указатель на предыдущее общее подвыражение,Flag — признак, указывающий, является ли поддерево общим подвыражением,Varbl — признак, указывающий, является ли вершина переменной,VarCount — счетчик переменной.192Глава 9.
Генерация кодаВыделение общих подвыражений и построение дерева осуществляются приведенными ниже правилами. Атрибут 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.// Выражение - переменная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))// Левое и правое поддеревья совпадают9.8.
Выделение общих подвыражений193break;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=new LisType();L.Addr=Node<0>;L.List=OpTable[Val<1>];OpTable[Val<1>]=L;}.Рассмотрим теперь некоторые простые правила распределения регистровпри наличии общих подвыражений. Если число регистров ограничено, можновыбрать один из следующих двух вариантов.1.
При обнаружении подвыражения, общего с подвыражением в ужепросмотренной части дерева (и, значит, с уже распределенными регистрами)проверяем, расположено ли его значение на регистре. Если да и если регистрпосле этого не менялся, то заменяем вычисление поддерева на значениев регистре. Если регистр менялся, то вычисляем подвыражение заново.2. Вводим еще один проход. На первом проходе распределяем регистры.Если в некоторой вершине обнаруживается, что ее поддерево — общее с ужевычисленным ранее, но значение регистра утрачено, то в такой вершинена втором проходе необходимо сгенерировать команду сброса регистра в рабочую память. Выигрыш в коде будет, если стоимость команды сброса регистра+ доступ к памяти в повторном использовании этой памяти не превосходитстоимости заменяемого поддерева.
Поскольку стоимость команды MOVE известна, можно сравнить стоимости и принять оптимальное решение: пометитьпредыдущую вершину для сброса либо вычислять поддерево полностью.7 В.А. Серебряков194Глава 9. Генерация кода9.9. Трансляция объектно-ориентированных свойствязыков программированияВ этом разделе будут рассмотрены механизмы трансляции базовых конструкций объектно-ориентированных языков программирования, а именно,наследования и виртуальных функций на примере языка С++.9.9.1. Виртуальные базовые классы. К описателю базового классаможно добавить ключевое слово virtual. В этом случае единственный подобъект виртуального базового класса разделяется каждым базовым классом,в котором тот (исходный) базовый класс определен как виртуальный.Пусть мы имеем следующую иерархию наследования:classclassclassclassL {.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
