Pull to refresh

Компиляция. 7: назначение регистров

Programming
File names are infinite in length, where infinity is set to 255 characters.
--Peter Collinson: The Unix File System

Итак, у нас есть программа на п-коде, и в её распоряжении неограниченное количество регистров (т.е. 255). Число регистров у реального процессора куда меньше (предположим, четыре). Что будем делать?

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

  1. Разбор п-кода
  2. Время жизни
  3. Реализация
  4. Простые оптимизации
  5. Расщепление версий
  6. Работа с памятью
  7. Что получилось?

Разбор п-кода


В прошлом посте был дамп скомпилированной программы. Её 40 команд несложно расшифровать:
00 mov   r01, 0
01 mov   r02, 0x3e8
02 echo  0x126
03 echo  r01
04 echo  0xa0
05 echo  r02
06 echo  0xa7
07 le    r03, r01, r02
08 jz    r03, +0x1d (=0x26)
09 add   r04, r01, r02
0a mov   r05, 2
0b div   r06, r04, r05
0c echo  0x162
0d echo  r06
0e echo  0xcc
0f input r07
10 mov   r08, 1
11 eq    r09, r07, r08
12 jz    r09, +4 (=0x17)
13 mov   r0a, 1
14 sub   r0b, r06, r0a
15 add   r02, r0b, 0
16 jz    0,   +e (=0x25)
17 mov   r0c, 2
18 eq    r0d, r07, r0c
19 jz    r0d, +4 (=0x1e)
1a mov   r0e, 1
1b add   r0f, r06, r0e
1c add   r01, r0f, 0
1d jz    0,   +7 (=0x25)
1e mov   r10, 3
1f eq    r11, r07, r10
20 jz    r11, +3 (=0x24)
21 echo  0x146
22 hlt
23 jz    0,   +1 (=0x25)
24 echo  0x16a
25 jz    0,   -0x1f (=7)
26 echo  0xff
27 hlt

Видно, что не все регистры используются одновременно: большинство хранят промежуточные значения, которые нужны только для следующей команды. Например, r03 используется только в командах 07-08, а r0f только в командах 1b-1c. Значит, нет никаких препятствий задействовать для хранимых значений один и тот же физический регистр: в командах 07-08 он будет использоваться для одного значения, а в 1b-1c — для другого. Любые два регистра, которые не используются одновременно для разных значений, можно объединить в один физический регистр.

Есть небольшая тонкость по поводу определения «используются одновременно для разных значений». Во-первых, нельзя считать временем жизни регистра просто промежуток от его первого упоминания до последнего: код может содержать прыжки во все стороны, например:
   ...
10 mov  r, 42
11 jz   0, 20
12 echo r
   ...
20 ...
   ...
30 jz   0, 12
   ...

Даже хотя r упоминается только в командах 10-12, он неявно используется и в команде 20, потому что после неё возможен прыжок обратно на 12; и значит, r нельзя объединять с другими регистрами, используемыми в команде 20.

Вторая тонкость:
   ...
10 mov  r, 42
11 echo r
   ...
20 ...
   ...
30 mov  r, 24
31 echo r
   ...

В команде 20 регистр r на самом деле не используется, хотя упоминается и перед этим (10-11), и после этого (30-31). Можем хранить в нём любые другие значения, потому что перед следующим использованием (31) значение ему будет присвоено по-новой. В принципе, мы даже можем назначить разные физические регистры для r в 10-11 и в 31-31, потому что значения всё равно будут храниться разные. Но для этого нужно обнаружить, что у r две независимые «версии», и обрабатывать их по-отдельности.

Время жизни


Определить набор команд, в которых регистр используется, можно итеративно:
  • регистр нужен команде, которая читает его значение;
  • если из команды A можно перейти на B (непосредственно или прыжком), и регистр нужен B, то он нужен и А;
  • регистр не нужен команде, которая задаёт его значение.
Для каждой команды определяем набор регистров, которые нужны ей «на входе» и «на выходе», и применяем три правила до тех пор, пока эти наборы не установятся. Вот что получим для нашей программы:
             номер итерации: 1(вход/вых) 2(вход/выход)       3(вход/выход)       4(вход/выход)     ...    итог(вход/выход)
00 mov   r01, 0                                                                                                    /r01
01 mov   r02, 0x3e8                                                                    /r01                     r01/r01,r02
02 echo  0x126                                 /r01             r01/r01             r01/r01                 r01,r02/r01,r02
03 echo  r01                    r01/        r01/                r01/                r01/r02                 r01,r02/r01,r02
04 echo  0xa0                                  /r02             r02/r02             r02/r02                 r01,r02/r01,r02
05 echo  r02                    r02/        r02/                r02/                r02/r01,r02             r01,r02/r01,r02
06 echo  0xa7                                  /r01,r02     r01,r02/r01,r02     r01,r02/r01,r02             r01,r02/r01,r02
07 le    r03, r01, r02      r01,r02/    r01,r02/r03         r01,r02/r03         r01,r02/r01,r02,r03         r01,r02/r01,r02,r03
08 jz    r03, +0x1d (=0x26)     r03/        r03/r01,r02 r01,r02,r03/r01,r02 r01,r02,r03/r01,r02         r01,r02,r03/r01,r02
09 add   r04, r01, r02      r01,r02/    r01,r02/            r01,r02/            r01,r02/r04                 r01,r02/r01,r02,r04
0a mov   r05, 2                                /r04,r05         r04/r04,r05         r04/r04,r05         r01,r02,r04/r01,r02,r04,r05
0b div   r06, r04, r05      r04,r05/    r04,r05/            r04,r05/            r04,r05/r06         r01,r02,r04,r05/r01,r02,r06
0c echo  0x162                                 /r06             r06/r06             r06/r06             r01,r02,r06/r01,r02,r06
0d echo  r06                    r06/        r06/                r06/                r06/                r01,r02,r06/r01,r02,r06
0e echo  0xcc                                                                                           r01,r02,r06/r01,r02,r06
0f input r07                                                                           /r07             r01,r02,r06/r01,r02,r06,r07
10 mov   r08, 1                                /r07,r08         r07/r07,r08         r07/r07,r08     r01,r02,r06,r07/r01,r02,r06,r07,r08
11 eq    r09, r07, r08      r07,r08/    r07,r08/r09         r07,r08/r09         r07,r08/r09     r01,r02,r06,r07,r08/r01,r02,r06,r07,r09
12 jz    r09, +4 (=0x17)        r09/        r09/                r09/                r09/r06,r07 r01,r02,r06,r07,r09/r01,r02,r06,r07
13 mov   r0a, 1                                /r06,r0a         r06/r06,r0a         r06/r06,r0a             r01,r06/r01,r06,r0a
14 sub   r0b, r06, r0a      r06,r0a/    r06,r0a/r0b         r06,r0a/r0b         r06,r0a/r0b             r01,r06,r0a/r01,r0b
15 add   r02, r0b, 0            r0b/        r0b/                r0b/                r0b/                    r01,r0b/r01,r02
16 jz    0,   +e (=0x25)                                                                                    r01,r02/r01,r02
17 mov   r0c, 2                                /r07,r0c         r07/r07,r0c         r07/r07,r0c     r01,r02,r06,r07/r01,r02,r06,r07,r0c
18 eq    r0d, r07, r0c      r07,r0c/    r07,r0c/r0d         r07,r0c/r0d         r07,r0c/r0d     r01,r02,r06,r07,r0c/r01,r02,r06,r07,r0d
19 jz    r0d, +4 (=0x1e)        r0d/        r0d/                r0d/                r0d/r06,r07 r01,r02,r06,r07,r0d/r01,r02,r06,r07
1a mov   r0e, 1                                /r06,r0e         r06/r06,r0e         r06/r06,r0e             r02,r06/r02,r06,r0e
1b add   r0f, r06, r0e      r06,r0e/    r06,r0e/r0f         r06,r0e/r0f         r06,r0e/r0f             r02,r06,r0e/r02,r0f
1c add   r01, r0f, 0            r0f/        r0f/                r0f/                r0f/                    r02,r0f/r01,r02
1d jz    0,   +7 (=0x25)                                                               /r01,r02             r01,r02/r01,r02
1e mov   r10, 3                                /r07,r10         r07/r07,r10         r07/r07,r10         r01,r02,r07/r01,r02,r07,r10
1f eq    r11, r07, r10      r07,r10/    r07,r10/r11         r07,r10/r11         r07,r10/r11         r01,r02,r07,r10/r01,r02,r11
20 jz    r11, +3 (=0x24)        r11/        r11/                r11/                r11/                r01,r02,r11/r01,r02
21 echo  0x146
22 hlt
23 jz    0,   +1 (=0x25)                                                               /r01,r02             r01,r02/r01,r02
24 echo  0x16a                                                                         /r01,r02             r01,r02/r01,r02
25 jz    0,   -0x1f (=7)                       /r01,r02     r01,r02/r01,r02     r01,r02/r01,r02             r01,r02/r01,r02
26 echo  0xff
27 hlt
По поводу отдельных итераций:
  1. На входе каждой команды — используемые ей регистры; (правило №1)
  2. На выход каждой команды копируем вход достижимых из неё команд; (правило №2)
  3. На вход каждой команды копируем её выход, исключая записанный командой регистр; (правило №3)
  4. На выход каждой команды копируем вход достижимых из неё команд; (правило №2)
Далее правила №2 и №3 повторяются поочерёдно.

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

Что делать, если для очередного п-регистра не окажется свободного физического? Например, в нашем коде есть команды (10-12, 17-19), использующие по 5 п-регистров: как минимум одному из них места не хватит. Понятно, что придётся хранить его в памяти.
Но просто сказать регистру «тебе не повезло, ты будешь храниться в памяти» мало: ведь команды нашего п-кода не умеют работать со значениями из памяти, равно как и команды большинства реальных процессоров. Необходимо на время использования доставать значение из памяти в регистр. Только в какой? Ведь потому и убрали значение в память, что все регистры заняты!

На этом месте выученная мной теория заканчивается, и идут догадки и эвристики. Я решил перед командой, на которую не хватает регистров, «выливать в память» лишние регистры, а после — читать их из памяти обратно. Тем самым, во «времени жизни» вылитых регистров появится дырка на месте этой команды, и в этой дырке сможем использовать освободившиеся регистры для других целей.

Чтобы можно было «раздвигать» код и вставлять в него команды чтения/записи в память, придётся чуточку поменять промежуточный формат: теперь это будет связанный список, и цель прыжка будет храниться не как смещение, а как указатель (превращая список в орграф). Во время генерации п-кода, для бэкпатчинга нам понадобится обращаться к командам и по индексу; для этого заведём отдельный вектор смещений.
    typedef std::list<struct commandn>::iterator pcommandn;
    struct commandn {
        command cmd;
        pcommandn tgt; // цель прыжка
        commandn(const command& cmd) : cmd(cmd), tgt(NULL) {}
    };

    std::list<commandn> pcode;
    std::vector<pcommandn> pcodeidx;

    inline int emit(const command& cmd) {
        pcodeidx.push_back(pcode.insert(pcode.end(), commandn(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) {
        *pcodeidx[index] = commandn(command(opcode, dest, imm));
    }

Указатели на цель прыжка сложно заполнять во время генерации п-кода: в момент создания прыжков уже известен индекс цели, но ещё неизвестно, какая там будет стоять команда; ставить указатель на ещё не созданную команду проблематично. Поэтому после конца разбора и генерации п-кода обойдём сгенерированный код, и расставим указатели прыжков; потом выполним всю нужную работу с распределением регистров; и в конце, перед дампом p-кода в файл, нужно будет его «сериализовать» — определить окончательный индекс каждой команды, и заполнить смещения прыжков. Ради этого, добавим в struct commandn поле int index;

int main() {
    yyparse();
    // расставить цели прыжков
    for(int i=0; i<pcode.size(); i++)
       if(pcodeidx[i]->cmd.opcode==command::jz)
            pcodeidx[i]->tgt = pcodeidx[i+1+pcodeidx[i]->cmd.imm];

    // обработка / оптимизация
    // ...

    // сериализация / расстановка смещений
    int index = 0;
    foreach(i, pcode) i->index = index++;
    foreach(i, pcode)
        if (i->cmd.opcode==command::jz)
            i->cmd.imm = i->tgt->index-i->index-1;

    // запись п-кода в файл
    // ...
}

Дело за малым: реализовать «обработку / оптимизацию». Займёт она, как и можно ожидать, большую часть всего кода компилятора.

Реализация


Для назначения регистров будем хранить для каждой команды (прямо в struct commandn) множества живых на входе и на выходе регистров: отдельно — регистров п-кода, для определения времени жизни; и отдельно — физических регистров, для определения сочетаемости при собственно назначении.
    typedef std::set<regnum> aliveset;
    enum physreg { firstp = 1, lastp = 4 };
    typedef std::set<physreg> alivesetp;
    struct commandn {
        // ...
        aliveset onenter, onexit;       // liveness check
        alivesetp onenterp, onexitp;    // phys reg allocation
        // ...
    };

Ещё одна полезная вещь — определение по опкоду, какие регистры используются командой:
    inline bool hasnext(pcommandn cmd) {
        return (cmd->cmd.opcode!=command::hlt &&!
                (cmd->cmd.opcode==command::jz && !cmd->cmd.dest));
    }
    inline bool has2src(pcommandn cmd) {
        return cmd->cmd.opcode>=command::add;
    }
    inline bool writesdest(pcommandn cmd) {
        return cmd->cmd.opcode>=command::mov;
    }
    inline bool readsdest(pcommandn cmd) {
        return cmd->cmd.opcode>=command::store &&
                cmd->cmd.opcode<=command::echo;
    }

После этого, по приведённой выше схеме, рассчитываем для каждой команды множество нужных на входе и на выходе регистров; заодно считаем, сколько раз нужен каждый регистр, для жадного назначения.
std::vector<int> liveness() { // returns usecount
    std::vector<int> usecount(lastreg+1);
    bool changed = false;
    // rule 1
    foreach(i, pcode) {
        i->onenter = i->onexit = aliveset();
        if (has2src(i)) {
            if (i->cmd.src1) {
                usecount[i->cmd.src1]++;
                i->onenter.insert(i->cmd.src1);
            }
            if (i->cmd.src2) {
                usecount[i->cmd.src2]++;
                i->onenter.insert(i->cmd.src2);
            }
        } else if (readsdest(i) && i->cmd.dest) {
            usecount[i->cmd.dest]++;
            i->onenter.insert(i->cmd.dest);
        }
        if (i->onenter.size())
            changed = true;
    }
    while (changed) {
        changed = false;
        foreach2(i, pcode, next) {
            int oldsize = i->onenter.size()+i->onexit.size();
            // rule 2 (next command)
            if (hasnext(i))
                i->onexit.insert(next->onenter.begin(), next->onenter.end());
            // rule 2 (jmp target)
            if (i->cmd.opcode==command::jz)
                i->onexit.insert(i->tgt->onenter.begin(), i->tgt->onenter.end());
            // rule 3
            i->onenter.insert(i->onexit.begin(), i->onexit.end());
            if (writesdest(i))
                i->onenter.erase(i->cmd.dest);

            if (i->onenter.size()+i->onexit.size() != oldsize)
                changed = true;
        }
    }
    return usecount;
}

Использованный макрос foreach2 позволяет в теле цикла смотреть и на текущий, и на следующий за ним элемент:
#define foreach2(i, list, next) typedef typeof(list) TOKENPASTE2(T,__LINE__); \
        for(TOKENPASTE2(T,__LINE__)::iterator next = list.begin(), i=next++; i != list.end(); i=next, next++)

В принципе, можно было сократить общее число итераций, если обходить команды не «сверху вниз», а «снизу вверх», потому что нужность «распространяется» от каждой команды к предыдущим; обход «сверху вниз» выбран ради упрощения кода. В самом худшем случае, для кода длиной N команд потребуется 2N итераций (на каждой итерации нужность распространяется на расстояние полкоманды). Для test.jsk хватило 35 итераций, потому что прыжки сокращают расстояния.

Наконец, то, зачем мы всё это делали:
    // обработка / оптимизация:
    while(1) { // пока все регистры не уложатся в физические

        // предварительная обработка
        // ...

        std::vector<int> usecount = liveness();
        std::vector<physreg> physmap(lastreg+1);
        foreach(i, pcode)
            i->onenterp = i->onexitp = alivesetp();
        while(1) {
            // самый нужный регистр
            std::vector<int>::iterator max = std::max_element(usecount.begin(), usecount.end());
            if (!*max) break; // все регистры размещены
            *max = 0;
            regnum r = max - usecount.begin();
            // поищем физ. регистр для п-регистра №r
            std::vector<int> collisions(lastp); // 0-based
            for (physreg p=firstp; p<=lastp; p=(physreg)(p+1)) { // error: ISO C++ forbids incrementing an enum
                foreach(i, pcode) {
                    if (contains(i->onenter, r) && contains(i->onenterp, p))
                        collisions[p-1]++;
                    if (contains(i->onexit, r) && contains(i->onexitp, p))
                        collisions[p-1]++;
                }
                if (collisions[p-1]) continue; // попробовать другой физ. рег
                physmap[r] = p;
                // разместили п-регистр №r в физическом №p
                foreach(i, pcode) {
                    if (contains(i->onenter, r))
                        i->onenterp.insert(p);
                    if (contains(i->onexit, r))
                        i->onexitp.insert(p);
                }
                break; // успешное назначение
            }
            if (physmap[r]) continue; // нашлось куда разместить
            // не хватило физ. регистра для п-регистра №r
            // эвристика: найдём команду, в которой не хватает регистров
            foreach2(i, pcode, next)
                if ((i->cmd.opcode!=command::load && i->cmd.opcode!=command::store) &&
                        ((contains(i->onenter, r) && i->onenterp.size()==lastp) ||
                         (contains(i->onexit, r) && i->onexitp.size()==lastp))) {
                    // найдём, какой регистр можно вылить, и выльем
                    // ...
                    goto afterspill;
                }
            // эвристика не сработала: что же делать?
            yyerror("don't know how to proceed");
        }
        // все регистры размещены; переименовываем
        foreach(i, pcode) {
            i->cmd.dest = physmap[i->cmd.dest];
            if (has2src(i)) {
                i->cmd.src1 = physmap[i->cmd.src1];
                i->cmd.src2 = physmap[i->cmd.src2];
            }
        }
        break;

afterspill: // пост-обработка после "выливания регистра"
    }

Ещё не углубляясь в то, как именно мы выливаем регистр, стоит упомянуть, что у приведённого кода масса проблем. Во-первых, эвристика работает только в самых простых случаях; чаще встречаются ситуации навроде
   ...
10 нужны r1,r2,r3,r4
   ...
20 нужны r1,r3,r4,r5
   ...
30 нужны r2,r3,r4,r5
   ...
Регистру r5 не хватает физического, потому что все физические израсходовались на r1,r2,r3,r4; но нет ни одной команды, где все пять регистров нужны одновременно.

Более жёсткая проблема — что каждый вылив засоряет программу бесполезными парами store/load, и их нужно вычищать — иначе используемые в них регистры создают достаточно «шума», чтоб регистров не хватило больше ни на что.

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

И, раз уж мы пошли удалять лишние load и store, удалим заодно и прочие лишние команды. Учитывая, что у операций нашего п-кода нет других побочных эффектов, кроме вычисления регистра с результатом, — можно удалять команды, результат которых не жив на выходе. Может быть, программист присвоил значение неиспользуемой переменной, или употребил оператор наподобие (2+2);
Удаляем всё подряд — так удалим до кучи недостижимый код (например, jz после hlt), и сожмём цепочки прыжков (заменим прыжок на прыжок одним прыжком).

Для удаления команды, чтобы не искать и не исправлять все прыжки на неё, удобно заменить её на nop; в качестве него назначим безусловный прыжок на следующую команду (jz r00, +0). Выгода в том, что на следующей итерации прыжок на nop сожмётся по цепочке, и сам nop вычистится как недостижимая команда.

Простые оптимизации


Для обнаружения недостижимых команд пользуемся обходом в глубину; чтобы следить, какие команды уже обошли, в struct commandn добавляем новое поле int reachcnt;
Нам хватило бы и булева поля; но «степень захода» каждой команды, может статься, ещё пригодится когда-нибудь потом.
void markReachable(pcommandn cmd) {
    while(!cmd->reachcnt++) {
        if (cmd->cmd.opcode==command::jz)
            markReachable(cmd->tgt);
        if (hasnext(cmd))
            cmd++;
        else
            break;
    }
}

void nopOut(pcommandn cmd) {
    pcommandn next = cmd; next++;
    cmd->cmd = command(command::jz, 0,0);
    cmd->tgt = next;
}

void simpleopt() {
    // сжать цепочки прыжков
    foreach(i, pcode)
        if(i->cmd.opcode==command::jz)
            while(i->tgt->cmd.opcode==command::jz && !i->tgt->cmd.dest)
                i->tgt = i->tgt->tgt;
    // удалить недостижимый код
    foreach(i, pcode) i->reachcnt = 0;
    markReachable(pcode.begin());
    foreach2(i, pcode, next)
        if(!i->reachcnt)
            pcode.erase(i);
    // удалить все nop: уже не могут быть целью прыжка
    foreach2(i, pcode, next)
        if(i->cmd.opcode==command::jz &&
                !i->cmd.dest && i->tgt==next)
            pcode.erase(i);
}

    // предварительная обработка в цикле назначения регистров:
    simpleopt();
    // удалить команды с неживым результатом
    liveness();
    bool changed = false;
    foreach(i, pcode)
        if(writesdest(i) && !contains(i->onexit, i->cmd.dest)) {
            nopOut(i);
            changed = true;
        }
    if (changed) continue;
    // расщепление версий
    // ...


Расщепление версий


Если в «интервале нужности» регистра есть разрыв, т.е. значение из одного набора команд никогда не проникает в другой набор, — значит, регистр можно «расщепить» на пару регистров с более короткими временами жизни.
Для выделения безразрывных фрагментов из времён жизни пригодится ещё один графовый алгоритм: поиск компонент связности.
Стремимся больше к ясности кода, чем к его эффективности; поэтому у нас пвг внутри пвг, и слияние компонент выполняется обходом всего графа.

В struct commandn потребуется ещё одно поле, последнее на сегодня: std::map<regnum,regnum> version;
В нём будем хранить для каждой команды соответствия «п-регистр -> номер версии».
Если регистр в команде используется, а соответствия в version ещё нет — значит, обход до этой команды ещё не дошёл.
Для внешнего же пвг, чтобы не заводить новое поле, пользуемся тем же reachcnt, что и в markReachable()
std::map<regnum,regnum> renameto;       // для слияния компонент

void versionizeReg(pcommandn cmd, regnum r, regnum rv) { // переименовать r в rv во всей компоненте
    while(!contains(cmd->version, r) &&
            (contains(cmd->onenter, r) || contains(cmd->onexit, r))) {
        // переименование
        cmd->version[r] = renameto[rv];
        if (cmd->cmd.dest==r) cmd->cmd.dest=renameto[rv];
        if (has2src(cmd)) {
            if (cmd->cmd.src1==r) cmd->cmd.src1=renameto[rv];
            if (cmd->cmd.src2==r) cmd->cmd.src2=renameto[rv];
        }
        if (!contains(cmd->onexit,r)) return; // больше не живой
        if (cmd->cmd.opcode==command::jz &&
                contains(cmd->tgt->onenter, r)) {
            versionizeReg(cmd->tgt, r, rv);
        }
        if (hasnext(cmd)) {
            cmd++;
            if (contains(cmd->onenter, r))
                continue;
        }
        return; // зашли в тупик
    }
    // натолкнулись на другую версию?
    if(contains(cmd->version, r) && cmd->version[r]!=renameto[rv]) {
        // слить renameto[rv] и cmd->version[r]
        regnum from = std::max(cmd->version[r], renameto[rv]),
               to = std::min(cmd->version[r], renameto[rv]);
        renameto[from] = to;
        foreach(i, pcode) {
            if (i->cmd.dest==from) i->cmd.dest = to;
            if (has2src(i)) {
                if (i->cmd.src1==from) i->cmd.src1 = to;
                if (i->cmd.src2==from) i->cmd.src2 = to;
            }
            if(contains(i->version, r) && i->version[r]==from)
                i->version[r] = to;
        }
    }
}

void versionize(pcommandn cmd) {
    while(!cmd->reachcnt++) {
        // versionize registers that live on exit
        foreach(r, cmd->onexit)
            if(!contains(cmd->version, *r)) {
                regnum rv = newreg();
                renameto[rv] = rv;
                versionizeReg(cmd, *r, rv);
            }
        if (cmd->cmd.opcode==command::jz)
            versionize(cmd->tgt);
        if (hasnext(cmd))
            cmd++;
        else
            break;
    }
}

    // расщепление версий:
    foreach(i, pcode) {
        i->version.clear();
        i->reachcnt = 0;
    }
    renameto.clear();
    int lastbasereg = lastreg;
    versionize(pcode.begin());
    // переименовать версии, чтоб начинались с 1
    foreach(i, pcode) {
        if (i->cmd.dest) i->cmd.dest-=lastbasereg;
        if (has2src(i)) {
            if (i->cmd.src1) i->cmd.src1-=lastbasereg;
            if (i->cmd.src2) i->cmd.src2-=lastbasereg;
        }
    }
    lastreg -= lastbasereg;

Осталось реализовать собственно вылив регистра. Конкретизируем эвристику: вылить можно любой регистр, который жив, но командой не используется.
regnum spillable(pcommandn cmd) { // найти регистр, который можно вылить
    aliveset alive;
    alive.insert(cmd->onenter.begin(), cmd->onenter.end());
    alive.insert(cmd->onexit.begin(), cmd->onexit.end());
    alive.erase(cmd->cmd.dest);
    if (has2src(cmd)) {
        alive.erase(cmd->cmd.src1);
        alive.erase(cmd->cmd.src2);
    }
    if (!alive.size()) return 0;
    return *alive.begin();
}

В отдельном map будем хранить по номеру регистра «адрес» его копии в памяти, чтобы все выливы регистра попадали в одно и то же место. Адрес присваивается регистру лишь в момент первого вылива.
// spill slots
std::map<regnum,int> spill;
int lastspill = 0;

void spillAt(pcommandn cmd, regnum victim, pcommandn next) {
    // найти / выделить слот
    int spslot = spill[victim];
    if(!spslot) {
        spslot = ++lastspill;
        spill[victim] = spslot;
    }
    // вставить store перед и load после
    pcommandn me = pcode.insert(next, *cmd);
    cmd->cmd = command(command::store, victim, spslot);
    commandn load(command(command::load, victim, spslot));
    if(hasnext(me))
        pcode.insert(next, load);
    if(me->cmd.opcode==command::jz)
        me->tgt = pcode.insert(me->tgt, load);
}

Поскольку команда заменяется тройкой store-cmd-load, нужно, чтобы существующие прыжки на команду прыгали на вставленный перед ней store. Чтобы не искать такие прыжки по всему коду, мы вставляем следующей командой копию cmd, а потом оригинал команды заменяем на store.
Аналогично, если команда — условный переход, то нужно, чтобы load выполнился при обоих исходах; поэтому и добавим его следующей командой, и вставим перед целью прыжка.

(Немного досадно, что из-за возможности переезда команд из одного commandn в другой нам придётся связывать строки для echo с самими командами по «идентификатору», как и в первой древесной реализации: ни индексы команд, ни указатели не остаются неизменными.)

Вторая эвристика: если не удалось найти команду, в которой заняты все физические регистры, то возьмём тот физический регистр, который «лучше всего подходит» (меньше всего коллизий с уже назначенными регистрами), и попытаемся освободить его всюду, где он нужен, но занят.
    // не хватило физ. регистра для п-регистра №r
    regnum victim;
    // эвристика 1: найдём команду, в которой не хватает регистров
    foreach2(i, pcode, next)
        if ((i->cmd.opcode!=command::load && i->cmd.opcode!=command::store) &&
                ((contains(i->onenter, r) && i->onenterp.size()==lastp) ||
                 (contains(i->onexit, r) && i->onexitp.size()==lastp))) {
            victim = spillable(i);
            assert(victim);
            spillAt(i, victim, next);
            goto afterspill;
        }
    // эвристика 2: найдём "самый подходящий" регистр
    physreg bestfit = (physreg)(std::max_element(collisions.begin(), collisions.end())-collisions.begin()+1);
    foreach2(i, pcode, next)
        if ((i->cmd.opcode!=command::load && i->cmd.opcode!=command::store) &&
                ((contains(i->onenter, r) && contains(i->onenterp, bestfit)) ||
                 (contains(i->onexit, r) && contains(i->onexitp, bestfit))) &&
                (victim = spillable(i))) {
            spillAt(i, victim, next);
            goto afterspill;
        }
    yyerror("don't know how to proceed");

При расщеплении версий нужно не забыть скопировать номер слота (все версии одного регистра хранятся в одном слоте), а потом, при переименовании версий, — не забыть обновить spill.

Компилятор уже почти работает; последняя проблема — что генерируется куча бесполезных load и store, и из-за них не остаётся регистров на осмысленные команды.

Работа с памятью


Во-первых, может оказаться, что некоторые регистры используются исключительно в командах load/store
Такие команды бесполезны: регистр записывается всегда в тот же слот, из которого был прочитан.
Вставим чистку после расщепления версий: там у нас как раз должно получиться много регистров с коротким временем жизни.
    // вычистить бессмысленные регистры
    std::vector<bool> used(lastreg+1);
    foreach(i, pcode) {
        if (writesdest(i) && i->cmd.opcode!=command::load)
            used[i->cmd.dest] = true;
        if (readsdest(i) && i->cmd.opcode!=command::store)
            used[i->cmd.dest] = true;
        if (has2src(i)) {
            used[i->cmd.src1] = true;
            used[i->cmd.src2] = true;
        }
    }
    foreach(i, pcode)
        if ((i->cmd.opcode==command::load && !used[i->cmd.dest]) ||
            (i->cmd.opcode==command::store && !used[i->cmd.dest]))
                nopOut(i);

Во-вторых, если у нас есть цепочки одинаковых load, то все, кроме последней, удалятся за то, что прочитанный регистр не жив. А вот если у нас цепочки одинаковых store, то для их удаления нужно придумать нечто новое. Алгоритм очень похож на итеративное определение нужности регистров, только теперь определяем «несохранённость» — чтобы вычистить все сохранения уже сохранённых регистров.
  • регистр не сохранён в команде, которая задаёт его значение;
  • если из команды A можно перейти на B (непосредственно или прыжком), и регистр не сохранён в A, то он не сохранён и в B;
  • регистр сохранён в команде, которая сохраняет его значение.
Видим, что от предыдущего этот алгоритм отличается только направлением распространения: нужность распространяется от каждой команды к предыдущим, а несохранённость — к последующим.
В общем виде итеративный алгоритм вычисления множеств регистров в каждой точке программы называется data flow analysis, и применяется, кроме двух названных, и для многих других оптимизаций.

void unsaved() {
    bool changed = false;
    // rule 1
    foreach(i, pcode) {
        i->onenter = i->onexit = aliveset();
        if (writesdest(i)) {
            i->onexit.insert(i->cmd.dest);
            changed = true;
        }
    }
    while (changed) {
        changed = false;
        foreach2(i, pcode, next) {
            int oldsize = i->onenter.size()+i->onexit.size();
            // rule 2 (next command)
            if (hasnext(i))
                next->onenter.insert(i->onexit.begin(), i->onexit.end());
            // rule 2 (jmp target)
            if (i->cmd.opcode==command::jz)
                i->tgt->onenter.insert(i->onexit.begin(), i->onexit.end());
            // rule 3
            i->onexit.insert(i->onenter.begin(), i->onenter.end());
            if (i->cmd.opcode==command::store)
                i->onexit.erase(i->cmd.dest);

            if (i->onenter.size()+i->onexit.size() != oldsize)
                changed = true;
        }
    }
}

afterspill: // пост-обработка после "выливания регистра"
        unsaved();
        foreach(i, pcode)
            if (i->cmd.opcode==command::store && !contains(i->onenter, i->cmd.dest))
                nopOut(i);
    }


Что получилось?


Весь компилятор вместе: tyomitch.net.ru/jsk.y.regs.html
Из полутысячи строк, к парсингу относится лишь пятая часть. Действительно кажется, что по сравнению с трудозатратами на остальную часть компилятора, парсер — неинтересная мелочь сбоку. Но это лишь потому, что создание парсеров обсосано до косточек, и нам остаётся лишь воспользоваться готовым; тогда как при обработке кода больше места выдумке.

В итоге назначения регистров и первых оптимизаций, генерируемый код удлинился всего на пару команд:
00 mov   r01, 0
01 mov   r02, 0x3e8
02 echo  0x12e
03 echo  r01
04 echo  0xa8
05 echo  r02
06 echo  0xaf
07 le    r03, r01, r02
08 jz    r03, +0x1f (=0x28)
09 add   r03, r01, r02
0a mov   r04, 2
0b div   r03, r03, r04
0c echo  0x16a
0d echo  r03
0e echo  0xd4
0f input r04
10 store r01, 1
11 mov   r01, 1
12 eq    r01, r04, r01
13 jz    r01, +5 (=0x19)
14 load  r01, 1
15 mov   r02, 1
16 sub   r02, r03, r02
17 add   r02, r02, 0
18 jz    0,   -0x12 (=0x7)
19 mov   r01, 2
1a eq    r01, r04, r01
1b jz    r01, +4 (=0x20)
1c mov   r01, 1
1d add   r01, r03, r01
1e add   r01, r01, 0
1f jz    0,   -0x19 (=0x7)
20 load  r01, 1
21 mov   r03, 3
22 eq    r03, r04, r03
23 jz    r03, +2 (=0x26)
24 echo  0x14e
25 hlt
26 echo  0x172
27 jz    0,   -0x21 (=7)
28 echo  0x107
29 hlt

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

Продолжим в августе: уезжаю в отпуск, и дописываю этот пост прямо из аэропорта.
Всем приятного лета!
Tags:компиляциягенерация кодаоптимизация кода
Hubs: Programming
Total votes 62: ↑60 and ↓2 +58
Views4.1K
Программист 1С
from 70,000 to 120,000 ₽Сима-лендRemote job
Программист 1С
from 75,000 ₽РегионПерсоналИваново
Ведущий программист 1С
from 150,000 ₽Компания ОмегаСанкт-ПетербургRemote job
Unity-разработчик на VR&AR проекты
from 60,000 ₽JetStyleЕкатеринбургRemote job