В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 35
Текст из файла (страница 35)
В общем случае трудно (или даже невозможно) провести границумежду оптимизацией и «качественной трансляцией». Оптимизация — этои есть качественная трансляция. Обычно термин «оптимизация» употребляют, когда для повышения качества программы используют ее глубокие преобразования, например, такие, как перевод в графовую форму для изучениянетривиальных свойств программы.В этом смысле выделение общих подвыражений — одна из простейшихоптимизаций. Для ее осуществления требуется некоторое преобразованиепрограммы, а именно, построение ориентированного ациклического графа,о котором говорилось в главе 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 {.
. .}A : public virtual L {. . .}B : public virtual L {. . .}C : public A, public B {. . .}Это можно изобразить диаграммой классов, изображенной на рис. 9.14.Рис. 9.14 Диаграмма классовКаждый из объектов A и B будет содержать L, но в объекте C будетсуществовать лишь один объект класса L. Ясно, что представление объектавиртуального базового класса L не может быть в одной и той же позицииотносительно и A, и B для всех объектов. Следовательно, во всех объектахклассов, которые включают класс L как виртуальный базовый класс, долженхраниться указатель на L. Реализация объектов A, B и C могла бы выглядетьтак, как показано на рис. 9.15.Рис.
9.15 Реализация объектов A, B и C9.9. Трансляция объектно-ориентированных свойств языков программирования1959.9.2. Множественное наследование. Имея два классаclass A {. . .af (int);},class B {. . .bf (int);},можно объявить третий класс с этими двумя в качестве базовых:class C : public A, public B {. . .}.Объект класса C может быть размещен как непрерывный объект(рис. 9.16).Рис. 9.16Как и в случае с единичным наследованием, здесь не гарантируетсяпорядок выделения памяти для базовых классов, поэтому объект класса Cможет выглядеть и так, как показано на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
