Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 23
Текст из файла (страница 23)
Поддерживаются следующие глобальные переменные:152Table - таблица переменных; для каждой переменной хранится ееномер (Count) и указатель на вершину дерева выражений, в которойпеременная встретилась в последний раз в правой части (Last);OpTable - таблица списков общих подвыражений, связанных скаждой операцией (Addr - указатель на вершину дерева, List продолжение списка);С каждой вершиной дерева выражения связана запись (Тип LisType):struct NodeType {Left -- левый потомок вершины;Right -- правый потомок вершины;Comm -- указатель на предыдущее общееподвыражение;Flag -- признак, является ли поддеревообщим подвыражением;Varbl -- признак, является ли вершина переменной;VarCount -- счетчик переменной;}Все общие подвыражения собраны в список (с типом элементаLisType), начинающийся с OpTable[Op], как это изображено на рис. 8.28.OpTableOPРис.
8.28Выделениеобщихподвыраженийипостроениедереваосуществляются приведенными ниже правилами. Атрибут Entryнетерминала Variable дает указатель на переменную в таблице Table.Атрибут Val символа Op дает код операции. Атрибут Node символовIntExpr и Assignment дает указатель на запись типа NodeTypeсоответствующего нетерминала.RULEAssignment ::= Variable IntExprSEMANTICSTable[Entry<1>].Count=Table[Entry<1>].Count+1.153//Увеличить счетчик присваиваний переменнойRULEIntExpr ::= VariableSEMANTICSif ((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.
//Выражение – переменная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>;154// Указатель на левое поддерево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 известна, можно сравнить стоимости и принятьоптимальное решение: то ли метить предыдущую вершину для сброса, толи вычислять полностью поддерево.1558.9. Генерация оптимального кода методами синтаксическогоанализа8.9.1. Сопоставление образцовТехника генерации кода, рассмотренная выше, основывалась наоднозначном соответствии структуры промежуточного представления иописывающей это представление грамматики.
Для генерации болеекачественного кода может быть применен подход, изложенный внастоящей главе.Этот подход основан на понятии "сопоставления образцов":командам машины сопоставляются некоторые "образцы", вхождениякоторых ищутся в промежуточном представлении программы, и делаетсяпопытка "покрыть" промежуточную программу такими образцами. Еслиэто удается, то по образцам восстанавливается программа уже в кодах.=++const(a) const(x)@const(5)++const(b)@const(y) +const(i)const(z)Рис.
8.29На рис. 8.29 показано промежуточное дерево для оператора a=b[i]+5, гдеa,b,i - локальные переменные, хранимые со смещениями x,y,z в областяхданных с одноименными адресами.Элемент массива b занимает память в одну машинную единицу. 0местная операция const возвращает значение атрибута соответствующей156вершины промежуточного дерева, указанного на рисунке в скобках послеоператора.
Одноместная операция '@' означает косвенную адресацию ивозвращает содержимое регистра или ячейки памяти, имеющей адрес,задаваемый аргументом оператора.157НоОбразецСтоимермость1232Машинная командаПравило грамматикиconst(c)MOV #c,RiReg->Const=4MOVE Rj,c(Ri)+reg(j)reg(i)const(c)Stat->'=' '+' RegConst Reg@MOVE c(Rj),Ri4+reg(j)4+3reg(i)5ADD #c,Riconst(c)reg(i)4ADD Rj,Rireg(j)ADD c(Rj),Ri@|+reg(j)2Reg -> '+' Reg Reg+reg(i)7Reg -> '+' Reg Const+26Contents -> '@' '+' RegConstconst(c)@|RegReg -> '+' Reg '@''+' Reg Constconst(c)MOVE (R),RReg -> ContentsРис.
8.30На рис.8.30 показан пример сопоставления образцов машинным158командам. Приведены два варианта задания образца: в виде дерева и ввиде правила контекстно-свободной грамматики. Для каждого образцауказана машинная команда, реализующая этот образец, и стоимость этойкоманды. Стоимость может определяться различными способами, и здесьмы не рассматриваем этого вопроса. На рис. 8.31 приведен примерпокрытия промежуточного дерева рис.
8.29 образцами рис. 8.30. В рамкизаключены фрагменты дерева, сопоставленные образцу правила, номеркоторого указывается в левом верхнем углу рамки. В квадратных скобкахуказаны результирующие вершины.[stat]=2+reg(Ra) const(x)const(a)4[reg(Rb)]+const(5)7[reg(Rb)]@6[reg(Rb)]+4[reg(Rb)]+@reg(Rb) const(y)const(b)+reg(Ri) const(z)const(i)Рис. 8.31Приведенное покрытие дает такую последовательность команд:MOVE b,RbADD #y,RbMOVE i,RiADD z(Ri),Rb159MOVE (Rb),RbADD #5,RbMOVE a,RaMOVE Rb,#x(Ra)Как правило, одни и те же конструкции исходной (илипромежуточной)программыможнореализоватьразличнымипоследовательностями машинных команд. Это соответствует тому, чтоимеются различные покрытия промежуточного представления.
Задачавыбора команд состоит в том, чтобы выбрать наилучший способреализации того или иного действия или последовательности действий, т.е. выбрать в некотором смысле оптимальное покрытие.Для выбора оптимального покрытия было предложено несколькоинтересных алгоритмов, в частности использующих динамическоепрограммирование [10,11]. Мы здесь рассмотрим алгоритм [12],комбинирующий возможности синтаксического анализа и динамическогопрограммирования, в основу которого положен синтаксический анализнеоднозначных грамматик (модифицированный алгоритм Кока, Янгера иКасами [13,14]) более эффективный в реальных приложениях.
Этот жеметод может быть применен и тогда, когда в качестве промежуточногопредставления используется дерево.8.9.2. Синтаксический анализ для T-грамматикОбычно код генерируется из некоторого промежуточного языка сдовольно жесткой структурой. В частности, для каждой операции известнаее размерность (число операндов). Назовем грамматики, удовлетворяющиеэтим ограничениям, T-грамматиками.Образцы, соответствующие машинным командам, задаютсяправилами грамматики (вообще говоря, неоднозначной).
Генератор кодаанализирует входное префиксное выражение и строит одновременно всевозможные деревья разбора. После окончания разбора выбирается деревос наименьшей оценкой. Затем по этому единственному оптимальномудереву генерируется код.Для T-грамматик все цепочки, выводимые из любого нетерминала A,являются префиксными выражениями с фиксированной арностьюопераций. Длины всех выражений из входной цепочки a 1...an можнопредварительно вычислить (под длиной выражения имеется ввиду длинаподстроки, начинающейся с символа кода операции и заканчивающейсяпоследним символом, входящим в выражение для этой операции).Поэтому можно проверить, сопоставимо ли некоторое правило сподцепочкой ai...ak входной цепочки a1...an, проходя слева-направо по160ai...ak.
В процессе прохода по цепочке предварительно вычисленныедлины префиксных выражений используются для того, чтобы перейти отодного терминала к следующему терминалу, пропуская подцепочки,соответствующие нетерминалам правой части правила.Цепные правила не зависят от операций, следовательно, ихнеобходимо проверять отдельно. Применение одного цепного правиламожет зависеть от применения другого цепного правила. Следовательно,применение цепных правил необходимо проверять до тех пор, пока нельзяприменить ни одно из цепных правил.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
