Главная страница Выбор входного языка Промежуточное представление Разработка Front-end'а Разработка Back-end'а Пара слов про оптимизацию



В даной главе рассматриваются два вида оптизизации: оптимизация константных выражений и алгоритм оптимального распределения регистров.

Оптимизация константных выражений

Вычисление константных выражений - это даже не оптимизация. Этот алгоритм должен быть реализован в любом компиляторе. Например, для выражения "(3+1*4)*a" нет необходимости генегировать дерево:

Достаточно вычислить константное выражение (3+1*4) и сгенерировать дерево:

Для этого необходимо перед созданием нового узла проверить, не являются ли правое и левое поддеревья листьями-константами и если да, то применить к значениям этих листьев операцию, для которой создается узел. Далее необходимо просто создать лист-константу с полученным значением. Вот эскиз такой процедуры:

PROCEDURE AddToTree(Op:Scan.Lex; Left, Right: Tree.pTree);
VAR
   Expr : Tree.pTree;
BEGIN
   IF (КонстЛист(Left)&(КонстЛист(Right)) THEN
      IF Left.Neg THEN
         Left.Value:=-Left.Value;
      END;
      IF Right.Neg THEN
         Right.Value:=-Right.Value;
      END;

      NEW (Expr);
      Expr.Left:=NIL;
      Expr.Right:=NIL;
      Expr.Regs:=-1;    
      Expr.Oper:=Scan.lexNum;
   
      CASE Op OF
          Scan.lexPlus : 
               Expr.Value:=Left.Value+Right.Value;
      |   Scan.lexMinus: 
               Expr.Value:=Left.Value-Right.Value;
      |   Scan.lexMult : 
               Expr.Value:=Left.Value*Right.Value;
      |   Scan.lexMOD  : 
               Expr.Value:=Left.Value MOD Right.Value;
      |   Scan.lexDIV  : 
               Expr.Value:=Left.Value DIV Right.Value;
      ELSE
         Error.Error("Неизвестная операция");
      END;
      IF Expr.Value<0 THEN
         Expr.Value:=-Expr.Value
         Expr.Neg:=TRUE;
      ELSE
         Expr.Neg:=FALSE;
      END;
      IF была ошибка переполнения THEN
         Error.Error("Переполнение в константном выражении");
      END;
      RETURN (Expr);
   ELSE
      Expr:=Tree.AddToTree(Left,Right);
      Expr.Oper:=Op;
      RETURN (Expr);
   END;
END AddToTree;

Для вычисления константных выражений необходимо приведенный выше эскиз (доработанный, разумеется) использовать в парсере вместо стандартной процедуры AddToTree модуля Tree.

Надо отметить, что приведенный эскиз не оптимизирует следующее выражение (и ему подобные): "12+s+23". Для его оптимизации необходимо составить несложную рекурсивную процедуру. Реализовать ее предлагаю самостоятельно.

Оптимальное распределение регистров

В алгоритме генерации кода, рассмотренном в главе "back-end", совсем не предусматривалось использование команд, у которых в качестве источника выступают числа и переменные. Например, для выражения "a*b+c" генерируется код:

MOV R1, a
MOV R2, b
MUL R1, R2
MOV R2, C
ADD R1, R2

Очевидно, такой код можно заменить на эквивалентный ему оптимизированный, использующий меньшее число регистров и команд:

MOV R1, a
MUL R1, b
ADD R1, c

Экономное использование регистров обусловлено тем, что в реальных процессорах регистров общего назначения постоянно не хватает. Например, в семействе 86 процессоров их всего 4. При этом команда MUL использует аж три из четырех возможных.

Поэтому, пусть в рассмотренной выше архитектуре регистровой машине число регистров ограничено константой MaxReg. Когда число регистров, необходимых для трансляции выражения, превысит MaxReg, потребуются команды PUSH/POP для временного хранения значений используемых регистров. Пример кода для выражения "(a+b)*(c-d)-(e-4)/(x+y)" при MaxReg=2:

MOV  R1, a
ADD  R1, b
MOV  R2, c
SUB  R2, d
MUL  R1, R2
PUSH R1
MOV  R1, e
SUB  R1, 4
MOV  R2, x
ADD  R2, y
DIV  R1, R2
POP  R2
SUB  R2, R1

Очевидно, для генерации такого кода недостаточно рекурсивно обойти синтаксическое дерево разбора снизу вверх, как это делалось в главе back-end. Необходимо в первую очередь генерировать код для поддеревьев, использующих большее число регистров. Для этого перед непосредственной генерацией кода в таинственное поле Regs каждого узла заносится число регистров, необходимых для трансляции подвыражения (поддерева). Число регистров вычисляется при рекурсивном обходе дерева следующим образом:

  1. Если узел -это левый лист, то Regs:=1 (необходим 1 регистр для команды MOV регистр, лист )
  2. Если правое поддерево узла - это лист, то Regs:=Left^.Regs (необходимо столько же регистров, сколько и при трансляции левого поддерева, т.к команда OP регистр, лист не требует загрузки нового регистра)
  3. Если число регистров необходимых для транляции левого и правого поддеревьев равны (Left^.Regs=Right^.Regs), то Regs:=Left^.Regs+1 (или Regs:=Right^.Regs+1)
  4. В противном случае (при различных значениях полей Regs правого и левого поддеревьев) Regs:=MAX(Left^.Regs,Right^.Regs)

Надо отметить, что пометка узла (заполнение поля Regs), выполняется только после пометки его левого и правого поддеревьев.

Вот OBERON-эскиз процедуры, помечающей дерево Expr:

PROCEDURE MarkTree(Expr : Tree.pTree);
BEGIN
   IF Expr является листом THEN
      Expr^.Regs:=1;
   ELSIF Expr^.Right является листом THEN
      MarkTree(Expr^.Left);
      Expr^.Regs:=Expr^.Left^.Regs;
   ELSE
      MarkTree(Expr^.Left);
      MarkTree(Expr^.Right);
      IF Expr^.Left^.Regs=Expr^.Right^.Regs THEN
         Expr^.Regs:=Expr^.Left^.Regs+1;
      ELSE
         Expr^.Regs:=MAX(Expr^.Left^.Regs,Expr^.Right^.Regs)
      END;
   END;
END MarkTree;

Ниже приведен пример помеченного дерева для выражения "a*b+(e-c/d)"

Для распределения регистров при генерации кода по размеченному дереву необходимо завести вспомогательную структуру - стек регистров (RegiStack), который перед генерацией заполнен значениями R1, R2, R3, ...,R(MaxReg). А также четыре подпрограммы:

  • функция TOP(RegStack) возвращает регистр на вершине RegStack (текущий регистр);
  • функция POP(RegStack) возвращает регистр, снятый с вершины RegStack;
  • процедура PUSH(RegStack, Reg) вталкивает в RegStack регистр Reg;
  • процедура SWAP(RegStack) переставляет два верхних регистра в RegStack;

Ниже приведен эскиз OBERON-процедуры, генерирующей код по помеченному дереву (не для слабонервных:)

PROCEDURE TreeWalk(Expr:Tree.pTree);
VAR
   Reg : tReg;
BEGIN
   IF Expr является листом THEN
      GenMOVRegLeaf(TOP(RegStack), Expr);
(*MOV текущий_регистр, лист*)
      IF Expr^.Neg THEN
         GenNEGReg(TOP(RegStack));
(*NEG текущий_регистр*)
      END
   ELSIF Expr^.Right является листом THEN
      TreeWalk(Expr^.Left);
      GenOPRegLeaf(Expr^.Oper, TOP(RegStack), Expr^.Right);
(*OP текущий_регистр, левый_лист*)
      IF Expr^.Neg THEN
         GenNEGReg(TOP(RegStack));
(*NEG текущий_регистр*)
      END
   ELSIF (Expr^.Left^.Regs>=Expr^.Right^.Regs)&
             (Expr^.Left^.Regs < MaxReg) THEN
      TreeWalk(Expr^.Left);
      Reg:=POP(RegStack);
      TreeWalk(Expr^.Right);      
      GenOPRegReg(Expr^.Oper, Reg,TOP(RegStack));
(*OP Reg, текущий_регистр*)
      IF Expr^.Neg THEN
         GenNEGReg(Reg);
(*NEG текущий_регистр*)
      END
      PUSH(RegStack,Reg);
   ELSIF (Expr^.Left^.Regs < Expr^.Right^.Regs)&
             (Expr^.Left^.Regs < MaxReg) THEN
      SWAP(RegStack);
      TreeWalk(Expr^.Right);      
      Reg:=POP(RegStack);
      TreeWalk(Expr^.Left);
      GenOPRegReg(Expr^.Oper, Reg,TOP(RegStack));
(*OP Reg, текущий_регистр*)
      IF Expr^.Neg THEN
         GenNEGReg(Reg);
(*NEG Reg*)
      END
      PUSH(RegStack,Reg);
      SWAP(RegStack);
   ELSE
      TreeWalk(Expr^.Left);
      GenPUSHReg(TOP(RegStack));
(*PUSH текущий_регистр*);
      TreeWalk(Expr^.Right);      
      Reg:=POP(RegStack);
      GenPOPReg(TOP(RegStack));
(*POP текущий_регистр*);
      GenOPRegReg(Expr^.Oper, TOP(RegStack), Reg);
(*OP текущий_регистр, Reg*)
      IF Expr^.Neg THEN
         GenNEGReg(TOP(RegStack));
(*NEG текущий_регистр*)
      END
      PUSH(RegStack,Reg);
      SWAP(RegStack);
   END
END TreeWalk;

Более подробно про оптимальное распределение регистров и многое другое можно прочитать в знаменитой "Книге дракона" (А. Ахо, Р. Сети, Д. Ульман. "Компиляторы: принципы, технологии, инструменты").

Процедура генерации кода с оптимальным распределнием регистров:

PROCEDURE GenCode*(Expr:Tree.pTree);
BEGIN
     MarkTree(Expr);
     TreeWalk(Expr);
END GenCode;

Заключение

Компилятор написан!! Осталось привести листинг главного модуля, собирающего отдельные части (сканер, парсер, кодогенерптор) в единое целое.

(*Компилятор выражений*)
(*     (C)2004, pm_kas*)
MODULE Compiler;
IMPORT
    Scan, 
    Text, 
    Error, 
    RegMachine, 
(*для стековой архитектуры StackMachine*)
    Parser,
    Tree;
VAR
   Expr : Tree.pTree;
BEGIN
   Text.ResetText;
   Scan.InitScan;
   Parser.Expression(Expr);
   IF Scan.Lex=Scan.lexEOT THEN
      RegMachine.GenCode(Expr);
(*для стековой архитектуры StackMachine.GenCode(Expr)*)
   ELSE
      Error.Error("Ожидается конец текста");
   END;
   Text.CloseText;
END Compiler.            
(C) 2004, PM_KAS