Компиляция. 6: промежуточный код

Первый этап — разбор синтаксиса нашего джей-скрипа — пройден; подбираемся к генерации кода.

Начнём с генерации п-кода (промежуточного переносимого псевдокода) — нечто вроде «абстрактного машинного языка». Его выбирают так, чтобы

• его было легко генерировать;
• его было легко обрабатывать.

Обработка п-кода — это, как правило, его переработка в исполнимый машинно-зависимый код. Тем не менее, можно ограничиться лишь генерацией п-кода, и объявить его готовой скомпилированной программой. Запуск такой программы будет, по сути, интерпретацией п-кода. У этого подхода всё больше и больше сторонников; так что и мы для начала ограничимся компиляцией в п-код.

Далее в посте:

1. Выбор кода
2. Компиляция
3. Выполнение
4. Backpatching

Выбор кода

Часто п-код делают стековым (например, MSIL): вообразим себе процессор, внутри которого нет пронумерованных регистров, а есть один большой стек, и все действия выполняются с верхними значениями на стеке. (Те, кому довелось программировать для х87, с такой моделью знакомы.) Стековый код действительно удобно генерировать и удобно выполнять, но не слишком удобно обрабатывать — например, в нём тяжело отслеживать зависимости между командами.

О выборе между стековым и регистровым промежуточным кодом выразительно отзывается создатель языка Beep:

Регистровый без вариантов:

Упрощение рантайма. Меньше манипуляций с указателями. Отсутствует понятие переполнения стека. Меньше кода, меньше работы с памятью — меньше места для критических ошибок.
Увеличивается сложность компиляции: появляется фаза выделения регистров. В случе исполнения на виртуальной машине нам не важно количество регистров, можем сделать их достаточное количество для того, что бы вообще не делать аллокацию, а просто маппить все параметры и переменные функции на регистры (см. Lua). Если количество параметров будет превышать количество регистров, то можно выделять часть activation record в хипе, но проще сделать так, что бы компилятор предлагал автору такого кода лечить голову.
В любом случае, если стоит вопрос упрощения рантайма ценой усложнения компилятора, так и следует поступать.
Возможность оптимизации: маппинг N регистров виртуальной машины на регистры процессора. На стековой машине это сделать значительно сложнее.

Так что и мы вместо стекового возьмём трёхадресный код в духе MIPS:

• Все команды равной длины (у нас — по 4 байта)
• Первый байт — номер команды (по отдельному опкоду под каждую возможную операцию)
• Второй байт — номер регистра для результата (256 регистров достаточно любому!)
• Остаток — либо два номера регистров-операндов, либо непосредственное значение—операнд.

Регистр №0 зарезервируем для хранения нуля: он нам пригодится. Вообще, полезно имено зарезервированный «недействительный» номер регистра, чтобы обозначать «отсутствие регистра вообще».

Кроме команд, соответствующих вычислительным операциям, нужны также:

• загрузка непосредственного значения в регистр;
• чтение из памяти в регистр;
• запись из регистра в память;
• условный переход;
• вывод строки или числа;
• ввод числа;
• остановка.

Все вычислительные команды принимают по два регистра, а все остальные — непосредственное значение.

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

Упорядочим опкоды так, чтобы команды похожей структуры (в плане используемых регистров) шли подряд, и вынесем определение структуры команды в отдельный файл jsk.h: она потребуется и компилятору, и интерпретатору.
typedef unsigned char regnum;

struct command {
    enum opcodes {
        hlt,
        store, // dst>
        jz,    // dst>
        echo,  // dst>
        mov,   // >dst
        load,  // >dst
        input, // >dst
        add,   // src>dst
        sub,   // src>dst
        mul,   // src>dst
        div,   // src>dst
        eq,    // src>dst
        ne,    // src>dst
        ge,    // src>dst
        le,    // src>dst
        gt,    // src>dst
        lt     // src>dst
    };

    opcodes opcode;
    regnum dest;
    union {
        struct {
            regnum src1, src2;
        };
        short imm;
    };
    command(opcodes opcode, regnum dest, regnum src1, regnum src2) :
                opcode(opcode), dest(dest), src1(src1), src2(src2) {}
    command(opcodes opcode, regnum dest, short imm) :
                opcode(opcode), dest(dest), imm(imm) {}
};

Чтобы под опкод действительно выделялся один байт, при компиляции придётся указывать ключ -fshort-enums

Компиляция

Строки для echo будем хранить вместе с кодом программы, в самом конце; одинаковые строки объединим, чтобы хранилась только одна копия. Для этого будем хранить map всех строк, где значением будет «идентификатор» строки (её порядковый номер в программе).

Все переменные в джей-скрипе — глобальные. В отдельном map будем хранить по имени переменной номер выделенного ей регистра.

В общем, идея та же, что с форматированной распечаткой; только теперь в каждом узле дерева храним не текст, а список команд. Для элементов выражения также храним номер регистра, в котором результат вычисления.

Берём парсер, и поехали: заменяем метод print() на аналогичный по сути emit(), склеивающий списки команд дочерних узлов в один большой список.

(340 строк кода вынесены на http://tyomitch.net.ru/jsk.y.html, чтобы сохранить размер поста в пределах допустимого.)

Как видим, понадобилось «расщепить» узел value на три разных типа: литерал-число, литерал-строка, и ссылка на переменную. При форматировании кода различия между ними были несущественны, но при генерации уже понадобилось их различать.

Выполнение

Отобразим файл с п-кодом в память, и будем работать с ним, как с массивом структур command. Собственно выполнение — это цикл из 4 строк, и реализация функций-команд; большая же часть кода — вспомогательная шелуха.

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include "jsk.h"

int pc = 0;     // индекс команды (не смещение)
bool halted = false;
int mem[1000];  // размер не важен: всё равно пока не пользуемся

typedef int (*op)(int src1, int src2, int dest, int imm); // все возможные входные значения

const char* fdata = NULL; // весь прочитанный п-код

extern op ops[]; // объявлен ниже

int main(int argc, char** argv) {

    if(argc!=2) {
        printf("Missing pcode file name.\n");
        exit(1);
    }

    int fd = open(argv[1], O_RDONLY);
    if (fd<0) {
        printf("Cannot open pcode file.\n");
        exit(1);
    }
    struct stat finfo;
    fstat(fd, &finfo);
    fdata = (const char*)mmap(0, finfo.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    if (!fdata) {
        printf("Cannot read pcode file.\n");
        exit(1);
    }

    const command* pcode = (const command*) fdata;

    int r[256] = {0}; // registers

    while (!halted) {
        command next = pcode[pc++];
        r[next.dest] = ops[next.opcode](r[next.src1], r[next.src2], r[next.dest], next.imm);
    }

    munmap((void*)fdata, finfo.st_size);
    close(fd);
    return 0;
}

int hlt(int src1, int src2, int dest, int imm) { halted = true; return dest; }
int store(int src1, int src2, int dest, int imm) { mem[imm] = dest; return dest; }
int jz(int src1, int src2, int dest, int imm) { if (!dest) pc+=imm; return dest; }
int echo(int src1, int src2, int dest, int imm) { if (imm) printf("%s", fdata+imm); else printf("%d", dest); return dest; }
int mov(int src1, int src2, int dest, int imm) { return imm; }
int load(int src1, int src2, int dest, int imm) { return mem[imm]; }
int input(int src1, int src2, int dest, int imm) { int d; scanf(" %d", &d); return d; }
int add(int src1, int src2, int dest, int imm) { return src1+src2; }
int sub(int src1, int src2, int dest, int imm) { return src1-src2; }
int mul(int src1, int src2, int dest, int imm) { return src1*src2; }
int div(int src1, int src2, int dest, int imm) { return src1/src2; }
int eq(int src1, int src2, int dest, int imm) { return src1==src2; }
int ne(int src1, int src2, int dest, int imm) { return src1!=src2; }
int ge(int src1, int src2, int dest, int imm) { return src1>=src2; }
int le(int src1, int src2, int dest, int imm) { return src1<=src2; }
int gt(int src1, int src2, int dest, int imm) { return src1>src2; }
int lt(int src1, int src2, int dest, int imm) { return src1<src2; }

op ops[] = {hlt, store, jz, echo, mov, load, input, add, sub, mul, div, eq, ne, ge, le, gt, lt};


Фанфары! Запускаем первую в мире программу на джей-скрипе:

[tyomitch@home ~]$ bison jsk.y
[tyomitch@home ~]$ c++ -fshort-enums jsk.tab.c lex.yy.c -o jskc
[tyomitch@home ~]$ c++ -fshort-enums jsk.c -o jsk
[tyomitch@home ~]$ ./jskc < test.jsk > pcode
[tyomitch@home ~]$ hexdump -C pcode
00000000 04 01 00 00 04 02 e8 03 03 00 26 01 03 01 00 00 |..........&.....|
00000010 03 00 a0 00 03 02 00 00 03 00 a7 00 0e 03 01 02 |................|
00000020 02 03 1d 00 07 04 01 02 04 05 02 00 0a 06 04 05 |................|
00000030 03 00 62 01 03 06 00 00 03 00 cc 00 06 07 00 00 |..b.............|
00000040 04 08 01 00 0b 09 07 08 02 09 04 00 04 0a 01 00 |................|
00000050 08 0b 06 0a 07 02 0b 00 02 00 0e 00 04 0c 02 00 |................|
00000060 0b 0d 07 0c 02 0d 04 00 04 0e 01 00 07 0f 06 0e |................|
00000070 07 01 0f 00 02 00 07 00 04 10 03 00 0b 11 07 10 |................|
00000080 02 11 03 00 03 00 46 01 00 00 00 00 02 00 01 00 |......F.........|
00000090 03 00 6a 01 02 00 e1 ff 03 00 ff 00 00 00 00 00 |..j.............|
000000a0 20 d0 b4 d0 be 20 00 2c 20 d0 b0 20 d1 8f 20 d0 | .... ., .. .. .|
000000b0 b1 d1 83 d0 b4 d1 83 20 d1 83 d0 b3 d0 b0 d0 b4 |....... ........|
000000c0 d1 8b d0 b2 d0 b0 d1 82 d1 8c 0a 00 3f 20 20 28 |............?  (|
000000d0 31 3d d0 bc d0 b5 d0 bd d1 8c d1 88 d0 b5 2c 20 |1=............, |
000000e0 32 3d d0 b1 d0 be d0 bb d1 8c d1 88 d0 b5 2c 20 |2=............, |
000000f0 33 3d d0 bf d0 be d0 bf d0 b0 d0 bb 29 20 00 d0 |3=..........) ..|
00000100 92 d1 80 d1 91 d1 88 d1 8c 2c 20 d1 82 d0 b0 d0 |........., .....|
00000110 ba 20 d0 bd d0 b5 20 d0 b1 d1 8b d0 b2 d0 b0 d0 |. .... .........|
00000120 b5 d1 82 21 0a 00 d0 97 d0 b0 d0 b4 d1 83 d0 bc |...!............|
00000130 d0 b0 d0 b9 20 d1 87 d0 b8 d1 81 d0 bb d0 be 20 |.... .......... |
00000140 d0 be d1 82 20 00 d0 a3 d1 80 d0 b0 21 20 d0 af |.... .......! ..|
00000150 20 d0 bc d0 be d0 bb d0 be d0 b4 d0 b5 d1 86 21 | ..............!|
00000160 0a 00 d0 ad d1 82 d0 be 20 00 d0 af 20 d0 bd d0 |........ ... ...|
00000170 b8 d1 87 d0 b5 d0 b3 d0 be 20 d0 bd d0 b5 20 d0 |......... .... .|
00000180 bf d0 be d0 bd d1 8f d0 bb 21 0a 00             |.........!..|
0000018c
[tyomitch@home ~]$ ./jsk pcode
Задумай число от 0 до 1000, а я буду угадывать
Это 500? (1=меньше, 2=больше, 3=попал) 2
Это 750? (1=меньше, 2=больше, 3=попал) 2
Это 875? (1=меньше, 2=больше, 3=попал) 2
Это 938? (1=меньше, 2=больше, 3=попал) 1
Это 906? (1=меньше, 2=больше, 3=попал) 1
Это 890? (1=меньше, 2=больше, 3=попал) 2
Это 898? (1=меньше, 2=больше, 3=попал) 2
Это 902? (1=меньше, 2=больше, 3=попал) 1
Это 900? (1=меньше, 2=больше, 3=попал) 1
Это 899? (1=меньше, 2=больше, 3=попал) 1
Врёшь, так не бывает!

Если приглядеться к дампу, то можно заметить, что первые 0xa0 байт занимает п-код (четвёрки байтов), а остаток файла — строки в UTF-8.

Backpatching

Сейчас в каждом узле дерева хранится список всех соответствующих ему команд, и каждая реализация emit включает в себя объединение команд из дочерних узлов — в том самом порядке (слева направо), в котором эти узлы создавались во время парсинга. Можно сэкономить и память на хранение команд, и код на их объединение, если все генерируемые команды сразу же сваливать в результат, а в символах хранить только «метаинформацию» типа номеров регистров.

Самая резкая разница — что теперь нам вообще не потребуется дерево: для каждого символа оказывается достаточно хранить один скаляр. Более того: у символов операторов теперь вовсе нет значения — весь результат их разбора немедленно сваливается в вектор готового п-кода; поэтому свёртках, где не генерируется код, даже наследовать ничего не нужно.

Небольшая проблема возникает в конструкциях типа if и while, где после проверки условия нужно вставить прыжок вперёд, если условие не выполняется; и до конца разбора конструкции неизвестно, на сколько нужно прыгать. Придётся оставить на месте прыжка команду-пустышку, и заполнять её в конце разбора. Такая система однопроходной генерации кода с пустышками, и их последующего «залатывания», называется backpatching. Она весьма универсальна, и не только позволяет компилировать все привычные управляющие конструкции, но и упрощает реализацию операторов типа break, прыгающих вперёд на неизвестное расстояние.

Чтобы вставить прыжок-пустышку после проверки условия в if и while, добавим в грамматику маркер — «пустой символ»:

OP: 'if' '(' EXPR ')' M OP 'else' M OP ;
  | 'while' '(' EXPR ')' M OP ;
M : ;

Трюк в том, что свёртка M выполнится после свёртки EXPR (которая сгенерирует код проверки условия) и перед свёрткой OP, так что в код свёртки M как раз и сможем добавить генерацию пустышки. Когда будем сворачивать конструкцию целиком, заполним пустышку прыжком до следующей пустышки (после if) либо до конца всего сгенерированного кода (после else и while).

Расстояние для прыжка вперёд теперь знаем; а как для while узнать расстояние для прыжка назад в конце цикла? Ведь раз нет списков команд, значит в коде свёртки не сможем узнать, сколько команд заняла вся конструкция. Придётся завести ещё один маркер N, который не генерирует код, а просто запоминает адрес нужного места:

OP: 'while' N '(' EXPR ')' M OP ;
M : ;
N : ;

Дополнительное преимущество новой системы — что для каждой генерируемой команды сразу известен её адрес, так что для строк сможем хранить не временные «идентификаторы», а списки всех ссылок. Это упростит подстановку адресов строк на заключительном этапе генерации п-кода.

%{
    #include <iostream>
    #include <vector>
    #include <list>
    #include <map>
    extern int yylineno;
    extern int yylex();
    void yyerror(char *s) {
      std::cerr << s << ", line " << yylineno << std::endl;
      exit(1);
    }
    #include "jsk.h"
    struct arg_t {
        regnum dest;     // if numeric
        std::string str; // if literal
    };
    typedef struct {
        std::string str;         // tokens
        regnum dest;             // expr
        arg_t arg;
        std::list<arg_t> args;
        int addr;                // markers
        char null;               // op (no data)
    } YYSTYPE;
    #define YYSTYPE YYSTYPE
    #define TOKENPASTE(x, y) x ## y
    #define TOKENPASTE2(x, y) TOKENPASTE(x, y)
    #define foreach(i, list) typedef typeof(list) TOKENPASTE2(T,__LINE__); \
                        for(TOKENPASTE2(T,__LINE__)::iterator i = list.begin(); i != list.end(); i++)
    template<typename L>
    inline void append(L& list1, L& list2) {
        list1.splice(list1.end(), list2, list2.begin(), list2.end());
    }

    std::vector<command> pcode;
    std::map<std::string,regnum> vars;
    std::map<std::string,std::list<int> > strings;
    regnum lastreg = 0;
    inline regnum newreg() {
        if (!++lastreg)
            yyerror("Too many registers used.");
        return lastreg;
    }

    inline int emit(const command& cmd) {
        pcode.push_back(cmd);
        return pcode.size()-1;
    }
    inline int emit(command::opcodes opcode, regnum dest, regnum src1, regnum src2) {
        return emit(command(opcode, dest, src1, src2));
    }
    inline int emit(command::opcodes opcode, regnum dest, short imm) {
        return emit(command(opcode, dest, imm));
    }
    inline void fix(int index, command::opcodes opcode, regnum dest, short imm) {
        pcode[index] = command(opcode, dest, imm);
    }
%}

%token IF ELSE WHILE EXIT
%token EQ LE GE NE
%token STRING NUM ID

%type<str> ID NUM STRING
%type<dest> EXPR EXPR1 EXPR2 TERM VAL
%type<arg> ARG
%type<args> ARGS
%type<null> OPS OP1 OP2 OP
%type<addr> M N

%%

PROGRAM: OPS    { emit(command::hlt, 0,0); }
;

OPS:    OP      // no action
|       OPS OP  // no action
;

OP1:    '{' OPS '}'                     {}
|       EXPR ';'                        {}
|       IF '(' EXPR ')' M OP1 ELSE M OP1{ fix($5, command::jz, $3, $8-$5);
                                          fix($8, command::jz, 0, pcode.size()-1-$8);
                                        }
|       WHILE N '(' EXPR ')' M OP1      { fix($6, command::jz, $4, emit(command::jz,0,$2-pcode.size()-1) -$6); }
|       EXIT ';'                        { emit(command::hlt, 0,0); }
;

OP2:    IF '(' EXPR ')' M OP            { fix($5, command::jz, $3, pcode.size()-$5); }
|       IF '(' EXPR ')' M OP1 ELSE M OP2{ fix($5, command::jz, $3, $8-$5);
                                          fix($8, command::jz, 0, pcode.size()-1-$8);
                                        }
|       WHILE N '(' EXPR ')' M OP2      { fix($6, command::jz, $4, emit(command::jz,0,$2-pcode.size()-1) -$6); }
;

OP:     OP1 | OP2 ;             // no action

M:                              { $$ = emit(command::hlt, 0,0); } // dummy
;

N:                              { $$ = pcode.size(); }
;

EXPR:   EXPR1                   // inherit
|       ID '=' EXPR             { $$ = $3;
                                  if(vars[$1])
                                        emit(command::add, vars[$1], $3, 0);
                                  else
                                        vars[$1] = $3; // new var
                                }
EXPR1:  EXPR2                   // inherit
|       EXPR1 EQ EXPR2          { $$ = newreg(); emit(command::eq, $$, $1, $3); }
|       EXPR1 LE EXPR2          { $$ = newreg(); emit(command::le, $$, $1, $3); }
|       EXPR1 GE EXPR2          { $$ = newreg(); emit(command::ge, $$, $1, $3); }
|       EXPR1 NE EXPR2          { $$ = newreg(); emit(command::ne, $$, $1, $3); }
|       EXPR1 '>' EXPR2         { $$ = newreg(); emit(command::gt, $$, $1, $3); }
|       EXPR1 '<' EXPR2         { $$ = newreg(); emit(command::lt, $$, $1, $3); }
;

EXPR2:  TERM                    // inherit
|       EXPR2 '+' TERM          { $$ = newreg(); emit(command::add, $$, $1, $3); }
|       EXPR2 '-' TERM          { $$ = newreg(); emit(command::sub, $$, $1, $3); }
;

TERM:   VAL                     // inherit
|       TERM '*' VAL            { $$ = newreg(); emit(command::mul, $$, $1, $3); }
|       TERM '/' VAL            { $$ = newreg(); emit(command::div, $$, $1, $3); }
;

VAL:    NUM                     { $$ = newreg(); emit(command::mov, $$, atoi($1.c_str())); }
|       '-' VAL                 { $$ = newreg(); emit(command::sub, $$, 0, $2); }
|       '!' VAL                 { $$ = newreg(); emit(command::eq, $$, 0, $2); }
|       '(' EXPR ')'            { $$ = $2; }
|       ID                      { if(vars[$1])
                                        $$ = vars[$1];
                                  else
                                        yyerror("Undefined variable");
                                }
|       ID '(' ARGS ')'         { if(!$1.compare("input")) {
                                    if($3.size())
                                        yyerror("Input: too many arguments");
                                    $$ = newreg();
                                    emit(command::input, $$, 0);
                                  } else if (!$1.compare("echo")) {
                                    if(!$3.size())
                                        yyerror("Input: too many arguments");
                                    $$ = 0;
                                    foreach(i, $3)
                                        if(!i->dest) // string
                                            strings[i->str].push_back(emit(command::echo, 0, 0));
                                        else
                                            emit(command::echo, i->dest, 0);
                                  } else
                                        yyerror("Undefined function");
                                }
;

ARGS:                           { $$.clear(); }
|       ARG                     { $$.clear(); $$.push_back($1); }
|       ARGS ',' ARG            { $$ = $1; $$.push_back($3); }
;

ARG:    EXPR                    { $$.dest = $1; }
|       STRING                  { $$.str=$1; $$.dest=0; }
;

%%

int main() {
        yyparse();
        int offset = pcode.size()*sizeof(command);
        foreach(i, strings) {
                foreach(j, i->second) // all refs
                        pcode[*j].imm = offset;
                offset += i->first.length();
                offset++;
        }
        foreach(i, pcode)   // dump code
                write(1, &*i, sizeof(*i));
        foreach(i, strings) // dump strings
                write(1, i->first.c_str(), i->first.length()+1);

}

Код компилятора сократился почти вдвое, а компилирует он точно так же, как и прежде.
Если нет разницы, зачем писать больше?