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

    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
    

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

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

    Похожие публикации

    Комментарии 11
      +5
      Положа руку на сердце — практически ничего не понял, но статья крутая! Пишите еще :)
        0
        А я увидел вызов yyparse(); и вспомнил, что что-то такое было на 3 курсе =)))
          0
          Помню нечто типа «mov bx,offset a» — поставить указатель на начало массива, если не ошибаюсь
          Даавноооо проходил асм в колледже, тогда он казался более понятныим и простым )
            0
            Опасный вы человек.
              0
              Ох… Путь Джедая у меня вызывает восхищение :)
                0
                удачного отдыха!
                  +1
                  Всё-таки писать компилятор и оптимизатор на си/си++ — та еще мозготрепка
                    0
                    а на чем вы предлагаете писать?
                      +1
                      OCaml или F#. Вообще что угодно с наличием ADT, паттерн-матчинга и сборщика мусора. Кода будет этак раз в 6-10 меньше
                        +1
                        на счет ADT и pattern matching согласен.

                        со сборщиком мусора сложнее в том плане, что (1) если наш компилятор является частью виртуальной машины, то нежелательно чтобы рядом какой-то левый сборщик мусора работал (в крайнем случае нужно пользоваться тем, который есть в самой ВМ) (2) сборщик мусора должен быть достаточно хороший, иначе придется костыли всякие вставлять всюду (кэши мелких объектиков, например), чтобы не тупило.
                    +2
                    ох, с распределением регистров столько всякой головной боли…

                    например, неортогональность системы команд x86 [некоторые команды требуют фиксированных регистров] и вообще взаимное влияние фаз выбора кода и распределения регистров.

                    хорошая ссылка по теме: магистерская работа Кристиана Виммера «Linear Scan Register Allocation
                    for the Java HotSpotTM Client Compiler» (http://www.ssw.uni-linz.ac.at/Research/Papers/Wimmer04Master/Wimmer04Master.pdf)

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое