Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 21
Текст из файла (страница 21)
Распределение регистров при вычисленииарифметических выраженийОдной из важнейших задач при генерации кода является распределениерегистров. Рассмотрим хорошо известную технику распределениярегистров при трансляции арифметических выражений, называемуюалгоритмом Сети-Ульмана.Пусть система команд машины имеет неограниченное числоуниверсальных регистров, в которых выполняются арифметическиекоманды. Рассмотрим, как можно сгенерировать код, используя дляданного арифметического выражения минимальное число регистров.R1R2RnLRLRРис.
8.13Предположим сначала, что распределение регистров осуществляется попростейшей схеме слева-направо, как изображено на рис. 8.13. Тогда кмоменту генерации кода для поддерева LR занято n регистров. Пустьподдерево L требует nl регистров, а поддерево R - nr регистров. Если nl=nr,то при вычислении L будет использовано nl регистров и под результатбудет занят n+1-й регистр. Еще nr (=nl) регистров будет использовано привычислении R. Таким образом, общее число использованных регистровбудет равно n+nl+1.Если nl>nr, то при вычислении L будет использовано n l регистров.При вычислении R будет использовано nr<nl регистров, и всего будетиспользовано не более чем n+nl регистров.Если nl<nr, то после вычисления L под результат будет занят одинрегистр (предположим n+1-й) и nr регистров будет использовано для135вычисления R. Всего будет использовано n+nr+1 регистров.Видно, что для деревьев, совпадающих с точностью до порядкапотомков каждой вершины, минимальное число регистров прираспределении их слева-направо достигается на дереве, у которого вкаждой вершине слева расположено более "сложное" поддерево,требующее большего числа регистров.Таким образом, если дерево таково, что в каждой внутреннейвершине правое поддерево требует меньшего числа регистров, чем левое,то, обходя дерево слева направо, можно оптимально распределитьрегистры.Без перестройки дерева это означает, что если в некоторой вершинедерева справа расположено более сложное поддерево, то сначаласгенерируем код для него, а затем уже для левого поддерева.Алгоритм работает следующим образом.
Сначала осуществляетсяразметка синтаксического дерева по следующим правилам.Правила разметки:1) если вершина - правый лист или дерево состоит из единственнойвершины, помечаем эту вершину числом 1, если вершина - левый лист,помечаем ее 0 (рис. 8.14).R (ll)01а)б)Рис. 8.14R (lr)lllrlllrR+1RRR+1а) ll<lrб) ll>lrR (ll+1)RR+1в)ll=lrРис. 8.152) если вершина имеет прямых потомков с метками l 1 и l2, то вкачестве метки этой вершины выбираем большее из чисел l 1 или l2 либочисло l1+1, если l1=l2 (рис.
8.15).Эта разметка позволяет определить, какое из поддеревьев требуетбольшего количества регистров для своего вычисления.Затем осуществляется распределение регистров для результатовопераций.Правила распределения регистров.1) Корню назначается первый регистр.2) Если метка левого потомка меньше метки правого, то левомупотомку назначается регистр на единицу больший, чем предку, а правому с тем же номером (сначала вычисляется правое поддерево и его результат136помещается в регистр R), так что регистры занимаются последовательно.Если же метка левого потомка больше или равна метке правого потомка,то наоборот, сначала вычисляется левое поддерево и его результатпомещается в регистр R (рис.
8.15), а правому потомку – R+1. После этогоформируется код по следующим правилам.Правила генерации кода:1) если вершина - правый лист с меткой 1, то ей соответствует кодLOAD X,R, где R - регистр, назначенный этой вершине, а X - адреспеременной, связанной с вершиной (рис. 8.16.б);2) если вершина внутренняя и ее левый потомок - лист с меткой 0, тоей соответствует код (рис. 8.16а)Код правого поддереваOp X,Rгде снова R - регистр, назначенный этой вершине, X - адрес переменной,связанной с вершиной, а Op - операция, примененная в вершине (рис.8.16.а);3) если непосредственные потомки вершины не листья и меткаправой вершины больше метки левой, то вершине соответствует кодКод правого поддереваКод левого поддереваOp R+1,Rгде R - регистр, назначенный внутренней вершине, и операция Op, вообщеговоря, не коммутативная (рис.
8.17 б)).RRRRRRXRR+1R+1RX(0)(1)а)б)а)Рис. 8.16б)Рис. 8.17Если метка правой вершины меньше или равна метке левой вершины, товершине соответствует кодКод левого поддереваКод правого поддереваOp R,R+1MOVE R+1,R137Последняя команда генерируется для того, чтобы получить результат внужном регистре (в случае коммутативной операции операнды операцииможно поменять местами и избежать дополнительной пересылки)(рис.8.17 а)).Рассмотрим атрибутную грамматику, реализующую эти правилагенерации кода.
В этой атрибутной грамматике генерация кодапроисходит не непосредственно в процессе обхода дерева, как раньше, аиз-за необходимости переставлять поддеревья код строится в виде текста спомощью операции конкатенации. Практически, конечно, этонецелесообразно: разумнее управлять обходом дерева непосредственно,однако для простоты мы будем пользоваться конкатенацией.RULEExpr ::= IntExprSEMANTICSReg<1>=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>+ Reg<3> + "," + 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)RULEIntExpr ::= IdentSEMANTICSLabel<0>=(Left<0>) ? 0 : 1;Code<0>=(!Left<0>)138? "LOAD" + Reg<0> + "," + Val<1>: Val<1>.RULEOp ::= '+'SEMANTICSCode<0>="ADD".RULEOp ::= '-'Code<0>="SUB".RULEOp ::= '*'SEMANTICSCode<0>="MUL".RULEOp ::= '/'SEMANTICSCode<0>="DIV".Атрибутированное дерево для выражения A*B+C*(D+E) приведено нарис.
8.18. При этом будет сгенерирован следующий код:LOAD E,R1ADD D,R1MUL C,R1LOAD B,R2MUL A,R2ADD R2,R1139Expr|IntExprTermLeft=falseLabel=2Reg=1IntExprAddOpLeft=trueLeft=falseLabel=1Label=2Reg=2+FactorMultOpTermFactorMultOp TermLeft=true Left=false Left=trueLeft=falseLabel=0 Label=1 Label=0Label=1Reg=2Reg=3Reg=1*Reg=1Ident*FactorIdentFactorA Left=falseCLeft=falseLabel=1Label=1Reg=3Reg=1IdentB( IntExpr )Left=falseLabel=1Reg=1Term AddOp IntExprLeft=trueLeft=falseLabel=0+Label=1Reg=2Reg=1FactorTermLeft=trueLeft=falseLabel=0Label=1Reg=2Reg=1IdentFactorDLeft=falseLabel=1Reg=1IdentEРис. 8.18.Приведенная атрибутная схема требует двух проходов по деревувыражения.
Рассмотрим теперь другую атрибутную схему, в которойдостаточно одного обхода для генерация программы для выражений соптимальным распределением регистров [9].Пусть мы произвели разметку дерева разбора так же, как и впредыдущем алгоритме. Назначение регистров будем производить всоответствии со схемой рис.
8.19.Левому потомку всегда назначается регистр, равный его метке, аправому - его метке, если она не равна метке его левого брата, и метке +1,140если метки равны. Поскольку более сложное поддерево всегдавычисляется раньше более простого, его регистр результата имеетбольший номер, чем любой регистр, используемый при вычислении болеепростого поддерева, что гарантирует правильность использованиярегистров.LabelLeft=0LabelLeftReg<0>= ((Left<0>==Label<0>)&&(Left<0>!=0))? Label<0>+1: Label<0>Рис. 8.19.Приведенные соображения реализуются следующей атрибутной схемой:RULEExpr ::= IntExprSEMANTICSCode<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>);Code<0>=(Label<3> > Label<1>)? (Label<1>==0)?Code<3> + Code<2> + Code<1>+ "," + Label<3>: Code<3> + Code<1> + Code<2> +Label<1> + "," + Label<3>: (Label<3> < Label<1>)?Code<1> + Code<3> + Code<2> +Label<1> + "," + Label<3> +"MOVE" + Label<3> + "," +Label<1>: //Label<3>==Label<1>Code<3> + "MOVE" + Label<3> +141"," + Label<3>+1 + Code<1> +Code<2> + Label<1> + "," +Label<1>+1.RULEIntExpr ::= IdentSEMANTICSLabel<0>=(Left<0>) ? 0 : 1;Code<0>=(Left<0>) ? Val<1>: "LOAD" + Val<1> + "R1".RULEOp ::= '+'SEMANTICSCode<0>="ADD".RULEOp ::= '-'SEMANTICSCode<0>="SUB".RULEOp ::= '*'SEMANTICSCode<0>="MUL".RULEOp ::= '/'SEMANTICSCode<0>="DIV".Команды пересылки требуются для согласования номеров регистров, вкоторых осуществляется выполнение операции, с регистрами, в которыхдолжен быть выдан результат.
Это имеет смысл, когда эти регистрыразные. Получиться это может из-за того, что по приведенной схемерезультат выполнения операции всегда находится в регистре с номеромметки, а метки левого и правого поддеревьев могут совпадать.Для выражения A*B+C*(D+E) будет сгенерирован следующий код:LOAD E,R1 - загрузить E на 1 регистрADD D,R1 - сложить D и E и результат заслать в 1регистрMUL C,R1 - умножить C на D+E с результатом в 1регистреMOVE R1,R2 - переслать результат в регистр R2LOAD B,R1- загрузить B в 1 регистр142MUL A,R1 - умножить A на B с результатом в 1 регистреADD R1,R2 - сложить A*B и C*(D+E) и результат заслатьво регистрВ приведенных атрибутных схемах предполагалось, что регистровдостаточно, чтобы правильно странслировать любое выражение. Если этоне так, приходится усложнять схему трансляции и при необходимостисбрасывать содержимое регистров в память (или магазин).1438.7.
Трансляция логических выраженийЛогические выражения, включающие логическое умножение, логическоесложение и отрицание, можно вычислять как непосредственно, используятаблицы истинности, так и с помощью условных выражений, пользуясьочевидными правилами:A AND B эквивалентно if A then B else False,A OR B эквивалентно if A then True else B.Если в качестве компонент выражений могут входить функции спобочным эффектом, то, вообще говоря, результат вычисления можетзависеть от способа вычисления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
