В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 33
Текст из файла (страница 33)
Она описывается следующим правилом (Number — это Лидер-номер описания поля):174Глава 9. Генерация кодаRULEVarTail ::= ’FIL’ Number VarTailSEMANTICSif (Address<0>.AddrMode==Abs){Address<3>.AddrMode=Abs;Address<3>.AddrDisp=Address<0>.AddrDisp+Table[Val<2>];}else{Address<3>=Address<0>;if (Address<0>.AddrMode==Index)Address<3>.AddrDisp=Address<0>.AddrDisp+Table[Val<2>];elseAddress<3>.IndexDisp=Address<0>.IndexDisp+Table[Val<2>];}.9.5.
Трансляция целых выраженийТрансляция выражений различных типов управляется синтаксически благодаря наличию указателя типа перед каждой операцией. Мы рассмотримнекоторые наиболее характерные проблемы генерации кода для выражений.Система команд МС68020 обладает двумя особенностями, сказывающимися на генерации кода для арифметических выражений (то же можно сказать и о генерации кода для выражений типа «множества»):1) один из операндов выражения (правый) должен при выполнении операции находиться на регистре, поэтому если оба операнда не на регистрах,то перед выполнением операции один из них надо загрузить на регистр;2) система команд довольно «симметрична», т.
е. нет специальных требований к регистрам при выполнении операций (таких, например, как парырегистров или требования четности и т. п.).Поэтому выбор команд при генерации арифметических выражений определяется довольно простыми таблицами решений. Например, для целочисленного сложения такая таблица приведена в табл. 9.1.Здесь имеется в виду, что R — операнд на регистре, V — переменная иликонстанта. Такая таблица решений должна также учитывать коммутативностьопераций.RULEIntExpr ::= ’PLUS’ IntExpr IntExprSEMANTICSif (Address<2>.AddrMode!=D) &&9.6.
Трансляция арифметических выражений175(Address<3>.AddrMode!=D){Address<0>.AddrMode=D;Address<0>.Addreg=GetFree(RegSet<Block>);Emit2(MOVE,Address<2>,Address<0>);Emit2(ADD,Address<2>,Address<0>);}elseif (Address<2>.AddrMode==D){Emit2(ADD,Address<3>,Address<2>);Address<0>:=Address<2>);}else {Emit2(ADD,Address<2>,Address<3>);Address<0>:=Address<3>);}.Т а б л и ц а 9.1Правый операнд А2ЛевыйоперандA1RRVADD A1,A2ADD A2, A1V ADD A1, A2 MOVE A1, RADD A2, R9.6.
Трансляция арифметических выраженийОдной из важнейших задач при генерации кода является распределениерегистров. Рассмотрим хорошо известную технику распределения регистровпри трансляции арифметических выражений, называемую алгоритмом Сети–Ульмана.Замечание. Для большей наглядности в данном разделе мы немногоотступаем от семантики арифметических команд MC68020 и предполагаем,что командаOp Arg1, Arg2выполняет действие Arg2:=Arg1 Op Arg2.Пусть система команд машины имеет неограниченное число универсальных регистров, в которых выполняются арифметические команды.
Рассмотрим, как можно сгенерировать код, используя для данного арифметическоговыражения минимальное число регистров.Пусть имеется синтаксическое дерево выражения. Предположим сначала, что распределение регистров осуществляется по простейшей схеме176Глава 9. Генерация кодаРис. 9.4сверху-вниз слева-направо, как изображено на рис. 9.4. Тогда к моментугенерации кода для поддерева LR занято n регистров. Пусть поддерево Lтребует nl регистров, а поддерево R — nr регистров. Если nl = nr , то привычислении L будет использовано nl регистров и под результат будет занят(n + 1)-й регистр. Еще nr (= nl ) регистров будет использовано при вычислении R.
Таким образом, общее число использованных регистров будет равноn + nl + 1.Если nl > nr , то при вычислении L будет использовано nl регистров. Привычислении R будет использовано nr < nl регистров, и всего будет использовано не более чем n + nl регистров. Если nl < nr , то после вычисления L подрезультат будет занят один регистр (предположим, (n + 1)-й), а nr регистровбудет использовано для вычисления R.
Всего будет использовано n + nr + 1регистров.Видно, что для деревьев, совпадающих с точностью до порядка потомков каждой вершины, минимальное число регистров при распределении ихслева-направо достигается на дереве, у которого в каждой вершине слева расположено более «сложное» поддерево, требующее большего числа регистров.Таким образом, если в каждой внутренней вершине дерева правое поддеревотребует меньшего числа регистров, чем левое, то, обходя дерево слева направо, можно оптимально распределить регистры. Без перестроения дереваэто означает, что если в некоторой вершине дерева справа расположено болеесложное поддерево, то сначала сгенерируем код для него, а затем уже длялевого поддерева.Алгоритм работает следующим образом. Сначала осуществляется разметка синтаксического дерева.
Разметка позволяет определить для каждогоподдерева, сколько регистров потребуется для его вычисления. Разметкаосуществляется по следующим правилам.9.6. Трансляция арифметических выражений177Правила разметки:1. Если вершина — правый лист или дерево состоит из единственнойвершины, то помечаем эту вершину числом 1 (рис. 9.5, б); если вершина —левый лист, то помечаем ее нулем (рис.
9.5, а).Рис. 9.52. Если вершина имеет прямых потомков с метками l1 и l2 , то в качествеметки этой вершины выбираем наибольшее из чисел l1 , l2 либо число l1 + 1,если l1 = l2 (рис. 9.6).Рис. 9.6Далее осуществляется распределение регистров для результатов операций. Распределение регистров основывается на следующих рассуждениях.Пусть корню поддерева назначен регистр с номером n. Индуктивное утверждение заключается в том, что к моменту вычисления поддерева все регистрыс номерами 1, . . .
, n заняты под промежуточные результаты уже вычисленныхподдеревьев, и, возможно, при вычислении данного поддерева используютсярегистры с номерами, бо́льшими n. После завершения вычислений в данномподдереве значение хранится в регистре с номером n. Назначение регистровосуществляется по следующим правилам:1) Корню назначается первый регистр.2) Если метка левого потомка меньше или равна метке правого, то левомупотомку назначается регистр на единицу больший, чем предку, а правому —с тем же номером (сначала вычисляется правое поддерево и его результатпомещается в регистр R — рис. 9.6, а, в), так что регистры занимаются последовательно.
Если же метка левого потомка больше метки правого потомка,то наоборот, правому потомку назначается регистр на единицу больший, чем178Глава 9. Генерация кодапредку, а левому — с тем же номером (сначала вычисляется левое поддеревои его результат помещается в регистр R — рис. 9.6, б).После этого формируется код по следующим правилам.1. Если вершина — правый лист с меткой 1, то ей соответствует кодMOVE X, Rгде R — регистр, назначенный этой вершине, а X — адрес переменной,связанной с вершиной (рис. 9.7, б).Рис. 9.72. Если вершина внутренняя и ее левый потомок — лист с меткой 0, то ейсоответствует кодКод правого поддереваOp X, Rгде R — регистр, назначенный этой вершине, X — адрес переменной,связанной с вершиной, а Op — операция, примененная в вершине (рис.
9.7, а).3. Если непосредственные потомки вершины — не листья и метка правойвершины больше или равна метке левой, то вершине соответствует кодКод правого поддереваКод левого поддереваOp R+1, Rгде R — регистр, назначенный внутренней вершине, а операция Op, вообщеговоря, — не коммутативная (рис. 9.8, б);Рис. 9.84. Если непосредственные потомки вершины — не листья и метка правойвершины меньше метки левой вершины, то вершине соответствует кодКод левого поддереваКод правого поддереваOp R, R+1MOVE R+1, R9.6. Трансляция арифметических выражений179Последняя команда генерируется для того, чтобы получить результат в нужном регистре (в случае коммутативной операции ее операнды можно поменятьместами и избежать дополнительной пересылки — рис.
9.8, а).Рассмотрим атрибутную схему, реализующую эти правила генерации кода(для большей наглядности входная грамматика соответствует обычной инфиксной записи, а не Лидер-представлению). В этой схеме генерация кодане происходит непосредственно в процессе обхода дерева, как раньше, а из-занеобходимости переставлять поддеревья код строится в виде текста с помощью операции конкатенации. Практически, конечно, это нецелесообразно:разумнее управлять обходом дерева непосредственно, однако для простотымы будем пользоваться конкатенацией.RULEExpr ::= IntExprSEMANTICSReg<1>=1; Code<0>=Code<1>; Left<1>=true.RULEIntExpr ::= IntExpr Op IntExprSEMANTICSLeft<1>=true; Left<3>=false;Label<0>=(Label<1>==Label<3>)? Label<1>+1: Max(Label<1>,Label<3>);Reg<1>=(Label<1> <= Label<3>)? Reg<0>+1: Reg<0>;Reg<3>=(Label<1> <= Label<3>)? Reg<0>: Reg<0>+1;Code<0>=(Label<1>==0)? Code<3> + Code<2>+ Code<1> + "," + Reg<0>: (Label<1> < Label<3>)? Code<3> + Code<1> + Code<2> +(Reg<0>+1) + "," + Reg<0>: Code<1> + Code<3> + Code<2> +Reg<0> + "," + (Reg<0>+1)+ "MOVE" + (Reg<0>+1) + "," + Reg<0>.RULEIntExpr ::= IdentSEMANTICSLabel<0>=(Left<0>) ? 0 : 1;Code<0>=(!Left<0>)? "MOVE" + Reg<0> + "," + Val<1>180Глава 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
