В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 24
Текст из файла (страница 24)
Рассмотрим хорошо известную технику распределения ре-ГЛАВА 9. ГЕНЕРАЦИЯ КОДА150гистров при трансляции арифметических выражений, называемую алгоритмом Сети-Ульмана. (Замечание: в целях большей наглядности, вданном параграфе мы немного отступаем от семантики арифметическихкоманд MC68020 и предполагаем, что командаOp Arg1, Arg2выполняет действие Arg2:=Arg1 Op Arg2.)Пусть система команд машины имеет неограниченное число универсальных регистров, в которых выполняются арифметические команды.Рассмотрим, как можно сгенерировать код, используя для данного арифметического выражения минимальное число регистров.5RS5RS5QRS/5/RS5Рис. 9.5:Пусть имеется синтаксическое дерево выражения.
Предположим сначала, что распределение регистров осуществляется по простейшей схеме сверху-вниз слева-направо, как изображено на рис. 9.5. Тогда к моменту генерации кода для поддерева 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. ТРАНСЛЯЦИЯ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ151лении их слева-направо достигается на дереве, у которого в каждой вершине слева расположено более “сложное” поддерево, требующее большего числа регистров.
Таким образом, если дерево таково, что в каждой внутренней вершине правое поддерево требует меньшего числа регистров, чем левое, то, обходя дерево слева направо, можно оптимальнораспределить регистры. Без перестройки дерева это означает, что если внекоторой вершине дерева справа расположено более сложное поддерево, то сначала сгенерируем код для него, а затем уже для левого поддерева.Алгоритм работает следующим образом. Сначала осуществляется разметка синтаксического дерева по следующим правилам.Правила разметки:1) если вершина – правый лист или дерево состоит из единственнойвершины, помечаем эту вершину числом 1, если вершина – левый лист,помечаем ее 0 (рис. 9.6).RSRSZ[Рис. 9.6:2) если вершина имеет прямых потомков с метками l1 и l2 , то в качестве метки этой вершины выбираем наибольшее из чисел l1 или l2 либочисло l1 + 1, если l1 = l2 (рис. 9.7).55ORSOOZ O O555ORSOO[ O!OРис.
9.7:555ORSO O\ O O5ГЛАВА 9. ГЕНЕРАЦИЯ КОДА152Эта разметка позволяет определить, какое из поддеревьев требует большего количества регистров для своего вычисления. Далее осуществляется распределение регистров для результатов операций по следующимправилам:1) Корню назначается первый регистр.2) Если метка левого потомка меньше метки правого, то левому потомку назначается регистр на единицу больший, чем предку, а правому– с тем же номером (сначала вычисляется правое поддерево и его результат помещается в регистр R), так что регистры занимаются последовательно.
Если же метка левого потомка больше или равна метке правогопотомка, то наоборот, правому потомку назначается регистр на единицубольший, чем предку, а левому – с тем же номером (сначала вычисляется левое поддерево и его результат помещается в регистр R – рис. 9.7).После этого формируется код по следующим правилам:1) если вершина – правый лист с меткой 1, то ей соответствует кодMOVE X, Rгде R – регистр, назначенный этой вершине, а X – адрес переменной, связанной с вершиной (рис.
9.8, б);5;RS5ZRS[;5Рис. 9.8:2) если вершина внутренняя и ее левый потомок – лист с меткой 0,то ей соответствует кодКод правого поддереваOp X, Rгде R – регистр, назначенный этой вершине, X – адрес переменной, связанной с вершиной, а Op – операция, примененная в вершине (рис. 9.8,а);3) если непосредственные потомки вершины не листья и метка правой вершины больше метки левой, то вершине соответствует кодКод правого поддереваКод левого поддереваOp R+1, R9.6.
ТРАНСЛЯЦИЯ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ153где R – регистр, назначенный внутренней вершине, и операция Op, вообще говоря, не коммутативная (рис. 9.9, б);55RS55 5 ZRS5[Рис. 9.9:4) если непосредственные потомки вершины не листья и метка правой вершины меньше или равна метке левой вершины, то вершине соответствует кодКод левого поддереваКод правого поддереваOp R, R+1MOVE R+1, RПоследняя команда генерируется для того, чтобы получить результат внужном регистре (в случае коммутативной операции операнды операции можно поменять местами и избежать дополнительной пересылки –рис.
9.9, а).Рассмотрим атрибутную схему, реализующую эти правила генерации кода (для большей наглядности входная грамматика соответствуетобычной инфиксной записи, а не Лидер-представлению). В этой схемегенерация кода происходит не непосредственно в процессе обхода дерева, как раньше, а из-за необходимости переставлять поддеревья кодстроится в виде текста с помощью операции конкатенации. Практически, конечно, это нецелесообразно: разумнее управлять обходом дереванепосредственно, однако для простоты мы будем пользоваться конкатенацией.RULEExpr ::= IntExprSEMANTICSReg<1>=1; Code<0>=Code<1>; Left<1>=true.RULEIntExpr ::= IntExpr Op IntExpr154SEMANTICSLeft<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>: Val<1>.RULEIntExpr ::= ’(’ IntExpr ’)’SEMANTICSLabel<0>=Label<2>;Reg<2>=Reg<0>;Code<0>=Code<2>.RULEOp ::= ’+’SEMANTICSCode<0>="ADD".RULEOp ::= ’-’SEMANTICSCode<0>="SUB".ГЛАВА 9.
ГЕНЕРАЦИЯ КОДА9.6. ТРАНСЛЯЦИЯ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ155RULEOp ::= ’*’SEMANTICSCode<0>="MUL".RULEOp ::= ’/’SEMANTICSCode<0>="DIV".([SUODEHO ,QW([SU UHJ ODEHO UHJ ODEHO UHJ ,QW([SU,GHQW$2S,QW([SU2S,QW([SU ODEHOUHJ ODEHO ODEHO UHJ UHJ ,QW([SU,QW([SU,GHQW%,GHQW&2S,QW([SU ODEHOUHJ ,QW([SU ODEHO 2SODEHO UHJ ,QW([SU,GHQW'UHJ ,QW([SU ODEHO UHJ ,GHQW(Рис. 9.10:Атрибутированное дерево для выражения A*B+C*(D+E) приведено нарис. 9.10.
При этом будет сгенерирован следующий код:MOVE B, R1MUL A, R1MOVE E, R2ADD D, R2MUL C, R2156ГЛАВА 9. ГЕНЕРАЦИЯ КОДАADD R1, R2MOVE R2, R1Приведенная атрибутная схема требует двух проходов по дереву выражения. Рассмотрим теперь другую атрибутную схему, в которой достаточно одного обхода для генерация программы для выражений с оптимальным распределением регистров [7].Пусть мы произвели разметку дерева разбора так же, как и в предыдущем алгоритме.
Назначение регистров будем производить следующим образом.Левому потомку всегда назначается регистр, равный его метке, а правому – его метке, если она не равна метке его левого брата, и метке + 1,если метки равны. Поскольку более сложное поддерево всегда вычисляется раньше более простого, его регистр результата имеет больший номер, чем любой регистр, используемый при вычислении более простогоподдерева, что гарантирует правильность использования регистров.Приведенные соображения реализуются следующей атрибутной схемой: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>: // метки равныCode<3> + "MOVE" + Label<3> +"," + Label<3>+1 + Code<1> +Code<2> + Label<1> + "," +Label<1>+1.9.6.
ТРАНСЛЯЦИЯ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ157RULEIntExpr ::= IdentSEMANTICSLabel<0>=(Left<0>) ? 0 : 1;Code<0>=(Left<0>) ? Val<1>: "MOVE" + Val<1> + "R1".RULEIntExpr ::= ’(’ IntExpr ’)’SEMANTICSLabel<0>=Label<2>;Code<0>=Code<2>.RULEOp ::= ’+’SEMANTICSCode<0>="ADD".RULEOp ::= ’-’SEMANTICSCode<0>="SUB".RULEOp ::= ’*’SEMANTICSCode<0>="MUL".RULEOp ::= ’/’SEMANTICSCode<0>="DIV".Команды пересылки требуются для согласования номеров регистров,в которых осуществляется выполнение операции, с регистрами, в которых должен быть выдан результат. Это имеет смысл, когда эти регистрыразные. Получиться это может из-за того, что по приведенной схеме результат выполнения операции всегда находится в регистре с номеромметки, а метки левого и правого поддеревьев могут совпадать.Для выражения A*B+C*(D+E) будет сгенерирован следующий код:MOVE E, R1ADD D, R1MUL C, R1MOVE R1, R2ГЛАВА 9.
ГЕНЕРАЦИЯ КОДА158MOVE B, R1MUL A, R1ADD R1, R2В приведенных атрибутных схемах предполагалось, что регистровдостаточно для трансляции любого выражения. Если это не так, приходится усложнять схему трансляции и при необходимости сбрасыватьсодержимое регистров в память (или магазин).9.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}
