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



Back-end - это транслятор промежуточного представления в код конкретной машины.

Прежде чем начинать разговор про сам back-end необходимо определиться с архитектурой и системой команд машины, для которой он создается.

Стековая архитектура

Преимуществом (а может быть недостатком :) стековой архитектуры является то, что она является безадресной, т.е. все команды используются без операндов. Например, команды SUB (вычесть) берет с вершины стека два числа, вычитает первое из второго и результат вталкивает в стек. Разумеется, до этого необходимо положить в стек соответствующие значения. Отдельной команды, которая кладет в стек значение переменной, или константу нет. Переменная или константа сама является командой: "положите меня на стек". Вот пример кода для выражения a*(b-10) (действие команды MUL аналогично SUB, только вместо вычитания она перемножает значения в стеке):

   a
   b
   10
   SUB
   MUL      

Таким образом, стековая система команд для выражения - это ни что иное, как обратная польская запись.

Ниже приведен перечень системы команд стековой машины для выражения.

Команда Действие
ADD Взять два числа из стека, сложить их и положить результат обратно в стек
SUB Взять два числа из стека, вычесть из второго первое, результат положить обратно в стек
MUL Взять два числа из стека, перемножить и положить результат обратно в стек
DIV Взять два числа из стека, найти целую часть от деления второго числа на первое и положить результат обратно в стек
MOD Взять два числа из стека, найти остаток от деления второго числа на первое и положить результат обратно в стек
NEG Взять число из стека и положить обратно в стек противоположное по знаку

Ниже приведен On-Line компилятор выражений в мнемонический код машины с рассмотренной выше стековой архитектурой.

Если синтаксическое дерево разбора построено (это делает процедура Expression модуля Parser), то сгенерировать мнемокод не составляет никакого труда: нужно просто обойти рекурсивно дерево снизу вверх и сгенерировать для каждого узла и листа соответсвующую команду. Вот Oberon-листинг вышесказанного:

(*Кодогенератор в мнемокод стековой машины*)
(*                       (C)2004, pm_kas  *)
MODULE StackMachine;
IMPORT
   Tree,Scan,Out,Error;

(*Сгенерировать команду загрузки числа на вершину стека*)
   PROCEDURE GenNUM(Num : INTEGER);
   BEGIN
      Out.Int(Num,0);
      Out.Ln;
   END GenNUM;

(*Сгенерировать команду загрузки переменной в стек*)
   PROCEDURE GenNAME(Name : Scan.tName);
   BEGIN
      Out.Char(Name);
      Out.Ln;
   END GenNAME;

(*****Сгенерировать команду ADD***************************)
   PROCEDURE GenADD;
   BEGIN
      Out.String("ADD");
      Out.Ln;
   END GenADD;

(*****Сгенерировать команду SUB***************************)
   PROCEDURE GenSUB;
   BEGIN
      Out.String("SUB");
      Out.Ln;
   END GenSUB;

(*****Сгенерировать команду MUL***************************)
   PROCEDURE GenMUL;
   BEGIN
      Out.String("MUL");
      Out.Ln;
   END GenMUL;

(*****Сгенерировать команду DIV***************************)
   PROCEDURE GenDIV;
   BEGIN
      Out.String("DIV");
      Out.Ln;
   END GenDIV;

(*****Сгенерировать команду MOD***************************)
   PROCEDURE GenMOD;
   BEGIN
      Out.String("MOD");
      Out.Ln;
   END GenMOD;

(*****Сгенерировать команду NEG***************************)
   PROCEDURE GenNEG;
   BEGIN
      Out.String("NEG");
      Out.Ln;
   END GenNEG;

(*****Сгенерировать код для дерева Expr*******************)
   PROCEDURE GenCode*(Expr:Tree.pTree);
   BEGIN
      IF Expr#NIL THEN
         GenCode(Expr.Left);
         GenCode(Expr.Right);
         CASE Expr.Oper OF
             Scan.lexNum  : GenNUM(Expr.Value);
         |   Scan.lexName : GenNAME(Expr.Name);
         |   Scan.lexPlus : GenADD;
         |   Scan.lexMinus: GenSUB;
         |   Scan.lexMult : GenMUL;
         |   Scan.lexMOD  : GenMOD;
         |   Scan.lexDIV  : GenDIV;
         ELSE
            Error.Error("Неизвестная операция");
         END;
         IF Expr.Neg THEN
            GenNEG;
         END;
      END;
   END GenCode;

END StackMachine.

Процедуры GenADD, GenNUM, GenMUL и т.д. генерируют код конкретной команды. Вызовы Out... внутри их служат для вывода на консоль мнемокоманд. Вместо их можно записать генерацию байт-кода для виртуальной стековой машины. Процедура GenCode() генерирует код для дерева разбора, переданного в качестве параметра по принципу, описанному выше. В остальном модуль StackMachine пояснений не требует.

Регистровая архитектура

Для регистровой машины, в отличии от стековой, в качестве хранилища промежуточных результатов вычислений используется не стек, а регистры общего назначения. В данной главе для простоты изложения предполагается, что регистров бесконечно много (обозначаются R1, R2, R3 ...). Случай ограниченного числа регистров рассматривается в главе "Оптимизация".

Сиcтема команд регистровой машины - это набор двухадресных и одноадресных инструкций вида:

OP получатель, источник

и

OP получатель

OP - это мнемокод операции. Вкачестве источника может быть либо регистр, либо переменная, либо число. Получателем является только регистр. Результат операции помещается в получателя. Вот пример команды MOV (загрузить) с различными источниками:

MOV R1, S  (загрузить значение переменной S в регистр R1)
MOV R2, 24 (загрузить число 24 в регистр R2)
MOV R1, R5 (загрузить значение из регистра R5 в регистр R1)

Ниже приведен перечень команд регистровой машины.

Команда Действие
Двухадресные команды
MOV Загрузить в получателя значение источника.
ADD Сложить источник с получателем
SUB Вычесть источник из получателя
MUL Перемножить источник с получателем
DIV Поместить в получателя целую часть от деления источника на получателя.
MOD Поместить в получателя остаток от деления источника на получателя.
Одноадресные команды
NEG Сменить знак получателя на противоположный
PUSH Поместить значение получателя на вершину стека
POP Извлечь из стека значение в получателя

Теперь самое время перейти к On-Line компилятору выражений в мнемокод регистровой машины

Код, генерируемый аплетом, крайне не эффективен. Можно заметить, что, если удалить все команды MOV с первым операндом (приемником), а у остальных команд убрать операнды, то получится ни что иное, как мнемокод стековой машины. Пример генерации более качественного кода с оптимальным распределением регистров будет рассмотрен в главе "Оптимизация".

Алгоритм процедуры, генерирующей такой нискокачественный код, почти не отличается от алгоритма генерации в код стековой машины: дерево разбора обходится рекурсивно снизу вверх; для листа гененируется команда MOV в текущий регистр, после чего номер текущего регистра увеличивается на единицу; для каждого узла генерируется соответствюющая команда с текущим регистром и регистром, номер которого на единицу меньше текущего, после чего номер текущего регистра уменьшается на единицу.

Словесное описание алгоритма звучит дико. На самом деле все просто:

(*Кодогенератор в мнемокод регистровой машины*)
(*                          (C)2004, pm_kas  *)
MODULE RegMachine;
IMPORT
   Tree,Scan,Out,Error;
VAR
   Reg : INTEGER; (*номер текущего регистра***)

(*Проверка на лист*)
   PROCEDURE isLeaf(Expr:Tree.pTree):BOOLEAN;
   BEGIN
      RETURN ((Expr.Left=NIL)&(Expr.Right=NIL))
   END isLeaf;

(*Сгенерировать команду NEG регистр***********)
   PROCEDURE GenNEGReg;
   BEGIN
      Out.String("NEG R");
      Out.Int(Reg,0);
      Out.Ln;
   END GenNEGReg;

(*Сгенерировать команду MOV регистр, лист*****)
   PROCEDURE GenMOVRegLeaf(Expr:Tree.pTree);
   BEGIN
      INC(Reg);
      Out.String("MOV R");
      Out.Int(Reg,0);
      Out.String(", ");
      IF Expr.Oper=Scan.lexName THEN
         Out.Char(Expr.Name);
      ELSIF Expr.Oper=Scan.lexNum THEN
         Out.Int(Expr.Value,0);
      ELSE
         Error.Error("InternalError (GenMOVRegLeaf)")
      END;
      Out.Ln;
      IF Expr.Neg THEN
         GenNEGReg;
      END;
   END GenMOVRegLeaf;

(*Сгенерировать команду ADD регистр1, регистр2*)
   PROCEDURE GenADDRegReg;
   BEGIN
      DEC(Reg);
      Out.String("ADD R");
      Out.Int(Reg,0);
      Out.String(", R");
      Out.Int(Reg+1,0);
      Out.Ln;
   END GenADDRegReg;

(*Сгенерировать команду SUB регистр1, регистр2*)
   PROCEDURE GenSUBRegReg;
   BEGIN
      DEC(Reg);
      Out.String("SUB R");
      Out.Int(Reg,0);
      Out.String(", R");
      Out.Int(Reg+1,0);
      Out.Ln;
   END GenSUBRegReg;

(*Сгенерировать команду MUL регистр1, регистр2*)
   PROCEDURE GenMULRegReg;
   BEGIN
      DEC(Reg);
      Out.String("MUL R");
      Out.Int(Reg,0);
      Out.String(", R");
      Out.Int(Reg+1,0);
      Out.Ln;
   END GenMULRegReg;

(*Сгенерировать команду DIV регистр1, регистр2*)
   PROCEDURE GenDIVRegReg;
   BEGIN
      DEC(Reg);
      Out.String("DIV R");
      Out.Int(Reg,0);
      Out.String(", R");
      Out.Int(Reg+1,0);
      Out.Ln;
   END GenDIVRegReg;

(*Сгенерировать команду MOD регистр1, регистр2*)
   PROCEDURE GenMODRegReg;
   BEGIN
      DEC(Reg);
      Out.String("MOD R");
      Out.Int(Reg,0);
      Out.String(", R");
      Out.Int(Reg+1,0);
      Out.Ln;
   END GenMODRegReg;

(*Сгенерировать код для дерева Expr************)
   PROCEDURE GenCode*(Expr:Tree.pTree);
   BEGIN
      IF isLeaf(Expr) THEN (*лист*)
         GenMOVRegLeaf(Expr);
      ELSE
         GenCode(Expr.Left);
         GenCode(Expr.Right);
         CASE Expr.Oper OF
             Scan.lexPlus : GenADDRegReg;
         |   Scan.lexMinus: GenSUBRegReg;
         |   Scan.lexMult : GenMULRegReg;
         |   Scan.lexMOD  : GenMODRegReg;
         |   Scan.lexDIV  : GenDIVRegReg;
         ELSE
            Error.Error("Неизвестная операция");
         END;
         IF Expr.Neg THEN
            GenNEGReg;
         END;
      END;
   END GenCode;

BEGIN
   Reg:=0;
END RegMachine.
(C) 2004, PM_KAS