Компиляция. 8: оптимизация

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

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

1. Починка бага
2. Чистка копирований
3. Что получилось?
4. Сворачивание констант
5. Реализация

Починка бага

Дело в том, что мы решили было схитрить, и при первом присваивании значения переменной не выполнять собственно копирование, а просто объявить регистр с промежуточным значением местом хранения переменной:
    ID '=' EXPR       { $$ = $3;
                        if(vars[$1])
                            emit(command::add, vars[$1], $3, 0);
                        else
                            vars[$1] = $3; // new var
                      }

Тогда при компиляции операции типа a=2; получим одну команду MOV R1, 2 (из свёртки 2) и запомним vars["a"]=R1 (из свёртки присваивания).
Всё верно, просто и естественно.

Проблема возникала тогда, когда в правой части присваивания использовалось не промежуточное значение, а нечто долгоживущее: например, другая переменная.

a = 2;
b = a;

Во второй свёртке присваивания не генерируется новый код — только запоминаем vars["b"]=R1
Обе переменные оказались в одном регистре, и при изменении одной из них — изменится и вторая.

Решение лежит на поверхности: для каждой новой переменной заводим новый регистр.
    ID '=' EXPR       { $$ = $3;
                        if(!vars[$1]) vars[$1] = newreg();
                        emit(command::add, vars[$1], $3, 0);
                      }

Тогда из a=2; получим уже пару команд

MOV R1, 2
ADD R2, R1, 0

и запоминаем vars["a"]=R2
Если за ней следует b = a; — то к коду добавится MOV R3, R2, 0 и vars["b"]=R3

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

Чистка копирований

Copy elimination — одна из простых оптимизаций, которую я обещал с самого первого поста серии. Как и для оптимизаций, выполняемых во время назначения регистров, для чистки удобно применить data-flow analysis. Важным отличием от двух предыдущих применений DFA (проход назад для обнаружения живых регистров, проход вперёд для обнаружения сохранённых регистров) будет являться то, что в каждой точке храним не одно множество регистров, а разбиение всех регистров на множества одинаковых. Можно смотреть на это как на более общий случай DFA, чем два рассмотренных прежде. (Прежде, регистры всегда разбивались на два множества — «включённые» и «исключённые».)

Как же будем разбивать регистры?

• команда ADD RA, RB, 0 переносит RA во множество к RB;
• любая другая команда, изменяющая регистр, выносит его во множество-синглетон;
• RA и RB будут вместе в команде C, если они вместе во всех командах, из которых можно перейти в C (непосредственно или прыжком).

После получения окончательного разбиения будет видно, где вместо копии можно использовать оригинал: вместо RA можно использовать RB, если они вместе во всех командах, где используется RA.

И ещё одна тонкость: поскольку при переходах от команды к команде мы не наращиваем множества, а усекаем (пересекаем все входящие множества), то перед запуском DFA нужно инициализировать множества не в пустые, а во всеобъемлющие — и по мере работы алгоритма множества усекутся, как надо. Чтобы не тратиться и не держать взаправду в каждой команде множество всех существующих регистров, договоримся считать «отсутствующий итератор» указывающим именно на такое всеобъемлющее множество.

Для удобства, три нужных нам операции над разбиениями оформляем в класс. В разбиении храним список множеств, на которые разбиты регистры (кроме «глобального» множества, в котором регистры все вместе находятся изначально), и для каждого регистра (кроме тех, что в «глобальном» множестве) — итератор того множества, в котором он находится.

С древесным std::set у меня возникли непонятные проблемы, так что я написал себе контейнер bit::set с аналогичным интерфейсом, но с std::bitset внутри. Параметром шаблона он принимает максимальное значение ключа в множестве.
Заодно в bit::set вынесены стандартные операции над множествами (&=, |=).

typedef bit::set<regnum,255> regset;

class regPartition {
    typedef std::list<regset> regsets;
    regsets sets;
    std::map<regnum, regsets::iterator> byreg;
// изначально: все регистры в "глобальном" разбиении

public:
    // возвращает: изменилось ли разбиение
    bool add(regnum copy, regnum orig) {
        if (byreg.count(copy)) {
            if(byreg[copy]==byreg[orig]) // уже вместе
                return false;
            byreg[copy]->erase(copy);
            // был последним?
            if(!byreg[copy]->size())
                sets.erase(byreg[copy]);
        }
        assert(byreg.count(orig));
        byreg[copy] = byreg[orig];
        byreg[copy]->insert(copy);
        return true;
    }

    void remove(regnum r) {
        if (byreg.count(‌r)) {
            if(byreg[r]->size()==1) return; // уже один
            byreg[r]->erase(‌r);
        }
        byreg[r] = sets.insert(sets.end(), regset());
        byreg[r]->insert(‌r);
    }

    // возвращает: изменилось ли разбиение
    bool isect(/*const*/regPartition& p, const command& self) {
        bool changed = false;
        // оставить вместе только тех, кто вместе и в p
        foreach(i, byreg) {
            regnum r = i->first;
            // split by p.byreg[r]
            regsets::iterator withR = i->second,
                         withoutR = sets.insert(sets.end(), regset());
            foreach2(j, (*withR), next)
                // не разделяем, если текущая команда -- mov с теми же регистрами:
                //   всё равно на следующем шагу объединятся
                if(!(self.opcode==command::add && !self.src2 &&
                    ((self.src1==r && self.dest==*j)||(self.dest==r && self.src1==*j)))
                &&((!p.byreg.count(‌r) && p.byreg.count(*j)) ||  // R in global, J isn't
                    (p.byreg.count(‌r) && !p.byreg[r]->count(*j)))) { // R not in global
                        withR->erase(*j);
                        withoutR->insert(*j);
                        byreg[*j] = withoutR;
                }
            if(!withoutR->size()) // ничего не отделилось
                sets.erase(withoutR);
            else // разделили
                changed = true;
        }
        // теперь те, что в глобальном в this, но не в p
        foreach(i, p.sets) {
            regset inP;
            foreach(j, (*i))
                if(!byreg.count(*j)) inP.insert(*j);
            if(inP.size()) {
                regsets::iterator newSet = sets.insert(sets.end(), inP);
                foreach(j, inP) byreg[*j] = newSet;
                changed = true;
            }
        }
        return changed;
    }

// применение разбиения: формируем для r множество возможных замен (во всём коде)
    void apply(regnum r, regset& global) {
        if (!r) return; // may not be replaced
        assert(byreg.count(‌r));
        if(!global.size()) // uninitialized set
            global = *byreg[r];
        else // initialized; intersect
            global &= *byreg[r];
    }
}

В struct commandn добавляем новое поле regPartition copies;
Теперь привычным образом реализуем DFA, используя уже готовые операции:
void copies() {
        // а) вычисляем разбиения для каждой команды
        bool changed = false;
        foreach(i, pcode) {
            i->copies = regPartition();
            // rule 2
            if (writesdest(i)) {
                i->copies.remove(i->cmd.dest);
                changed = true;
            }
        }
        while (changed) {
            changed = false;
            foreach2(i, pcode, next) {
                // rule 1
                if (i->cmd.opcode==command::add && !i->cmd.src2)
                    changed |= i->copies.add(i->cmd.dest, i->cmd.src1);
                // rule 3 (next command)
                if (hasnext(i))
                    changed |= next->copies.isect(i->copies, next->cmd);
                // rule 3 (jmp target)
                if (i->cmd.opcode==command::jz)
                    changed |= i->tgt->copies.isect(i->copies, i->tgt->cmd);
            }
        }
        // б) вычисляем возможные замены во всём коде
        std::vector<regset> copies(lastreg+1);
        foreach(i, pcode) {
            if(readsdest(i))
                i->copies.apply(i->cmd.dest, copies[i->cmd.dest]);
            if(has2src(i)) {
                i->copies.apply(i->cmd.src1, copies[i->cmd.src1]);
                i->copies.apply(i->cmd.src2, copies[i->cmd.src2]);
            }
        }
        // в) объединяем копии
        for(regnum r=1; r<=lastreg; r++) {
            copies[r].erase(‌r);
            if(copies[r].size()) {  // остались возможные замены?
                regnum s = *(copies[r].begin()); // заменим r на s
                foreach(i, pcode) { // во всём коде
                    if(i->cmd.dest==r)
                        i->cmd.dest = s;
                    if(has2src(i)) {
                        if(i->cmd.src1==r) i->cmd.src1 = s;
                        if(i->cmd.src2==r) i->cmd.src2 = s;
                    }
                    if(i->cmd.opcode==command::add && i->cmd.src1==i->cmd.dest && !i->cmd.src2) // self-mov
                        nopOut(i);
                }
                foreach(c, copies)  // и в векторе замен
                    if(c->count(‌r)) {
                        c->erase(‌r);
                        c->insert(s);
                    }
            }
        }
}
Вызов copies(); вставим в самое начало цикла оптимизаций, перед проверкой живости.

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

По сравнению с прошлым разом, код сократился ещё на пару команд:

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   r03, r01, r02
0a mov   r04, 2
0b div   r03, r03, r04
0c echo  0x162
0d echo  r03
0e echo  0xcc
0f input r04
10 store r01, 1
11 mov   r01, 1
12 eq    r01, r04, r01
13 jz    r01, +4 (=0x18)
14 load  r01, 1
15 mov   r02, 1
16 sub   r02, r03, r02
17 jz    0,   -0x11 (=0x7)
18 mov   r01, 2
19 eq    r01, r04, r01
1a jz    r01, +3 (=0x1e)
1b mov   r01, 1
1c add   r01, r03, r01
1d jz    0,   -0x17 (=0x7)
1e load  r01, 1
1f mov   r03, 3
20 eq    r03, r04, r03
21 jz    r03, +2 (=0x24)
22 echo  0x146
23 hlt
24 echo  0x16a
25 jz    0,   -0x1f (=7)
26 echo  0xff
27 hlt

Может показаться, что про исчезнувшие команды (add r01, r01, 0 и add r02, r02, 0) сразу было видно, что они бессмысленные. На самом деле, эти команды принимали бессмысленную форму только после назначения физических регистров, т.е. на самом последнем этапе перед выводом готового п-кода. До тех пор, номера п-регистров у операндов различались; лишь выполненный нами только что анализ позволил их объединить, и удалить ставшее бессмысленным копирование — всё это задолго до назначения физических регистров.

Сворачивание констант

Ещё одна стандартная оптимизация, которая, как и предыдущие, реализуется при помощи DFA, — constant folding. Принцип донельзя прост: если известны значения операндов, то операцию можно выполнить сразу при компиляции. Например, вместо кода

MOV R1, 2
MOV R2, 3
ADD R3, R1, R2

можем сгенерировать сразу же

MOV R3, 5

Операции над константами не обязательно свидетельствуют о небрежности программиста, поленившегося вычислить заранее известный результат: например, pixels=1024*768; легче читать и поддерживать, чем pixels=786432;

В этот раз, в каждой команде храним множества регистров, для которых известны значения, — вместе со значениями: в виде std::map<regnum,int>
Как обычно, формулируем три правила вычисления множеств:

• в команде MOV R, X значение R известно, и это X;
• в любой другой команде, задающей значение R, это значение неизвестно;
• в команде C известно значение R, если оно известно и одинаково во всех командах, из которых можно перейти в C (непосредственно или прыжком).

Вновь видим: направление прохода — вперёд (от значения регистра в предыдущей команде зависит её значение в последующей); операция в узлах — объединение неизвестных регистров.

Когда множества стабилизируются, сможем заменить каждую операцию, оба операнда которой известны, на MOV.

Те же самые данные позволят нам выполнить ещё одну оптимизацию — constant propagation (подстановка известного значения вместо ссылки на регистр). Эта оптимизация невозможна при выбранном нами формате п-кода, потому что в нём отсутствуют операции над регистром и константой; такие операции, однако, присутствуют во многих реальных процессорах, так что выполнить полноценную «подстановку констант» можно будет при генерации выполнимого кода. Сейчас же ограничимся заменой нулевого значения на R0.

Например, конструкция типа if (1>2) { echo("unreachable"); }, которая компилируется в

MOV R1, 1
MOV R2, 2
GT R3, R1, R2
JZ R3, label
ECHO "unreachable"
label:

превратится на этапе сворачивания констант в

MOV R1, 1
MOV R2, 2
MOV R3, 0
JZ R3, label
ECHO "unreachable"
label:

и уже реализованная нами в прошлый раз оптимизация «уничтожение неживого кода» удалит две первых команды MOV.
Если же мы заодно заменим нулевое значение на R0:

MOV R3, 0
JZ R0, label
ECHO "unreachable"
label:

то вместе с неживым кодом удалится и последний MOV, а «уничтожение недостижимого кода» удалит ещё и ECHO, превратив JZ в NOP.

Аналогично можно удалять из кода JZ с известным ненулевым значением. Второй реализованный «особый случай» — замена команд ADD RX, (0), RY на ADD RX, RY, R0, чтобы алгоритм чистки копирований распознал в этой команде копирование из регистра в регистр.

Ещё одна выгода от сворачивания констант — что теперь в наших командах могут использоваться отрицательные значения. Из-за того, что в лексере мы задали токен NUM регэкспом [0-9]+, строки типа "-123" интерпретировались как унарный минус и затем литерал 123; поэтому они компилировались в п-код наподобие

MOV R1, 123
SUB R2, R0, R1

Теперь же в п-коде будет честная команда MOV R1, -123.

Реализация

struct commandn дополняется ещё парой полей:
std::map<regnum,int> known; regset unknown;

Основой оптимизации, как и в предыдущих случаях, является DFA:
void constp() {
        bool changed = false;
        foreach(i, pcode) {
            i->known.clear(); i->unknown.clear();
            if (i->cmd.opcode==command::mov) { // rule 1
                i->known[i->cmd.dest] = i->cmd.imm;
                changed = true;
            } else if(writesdest(i)) { // rule 2
                i->unknown.insert(i->cmd.dest);
                changed = true;
            }
        }
        while(changed) {
            changed = false;
            foreach2(i, pcode, next) {
                // rule 3 (next command)
                if (hasnext(i))
                    changed |= propagate(i, next);
                // rule 3 (jmp target)
                if (i->cmd.opcode==command::jz)
                    changed |= propagate(i, i->tgt);
            }
        }
        // заменим известные значения
        foreach(i, pcode) {
            i->known[0] = 0; // R0 известен всегда
            if(has2src(i) && i->known.count(i->cmd.src1) && i->known.count(i->cmd.src2))
                i->cmd = command(command::mov, i->cmd.dest, ops[i->cmd.opcode](i->known[i->cmd.src1],i->known[i->cmd.src2]));
            // подставляем 0
            if(has2src(i)) {
                if(i->known.count(i->cmd.src1) && !i->known[i->cmd.src1])
                    i->cmd.src1 = 0;
                if(i->known.count(i->cmd.src2) && !i->known[i->cmd.src2])
                    i->cmd.src2 = 0;
                if(i->cmd.opcode==command::add && !i->cmd.src1) { // чтоб распознавалось как копирование
                    i->cmd.src1 = i->cmd.src2;
                    i->cmd.src2 = 0;
                }
            }
            if(readsdest(i) && i->known.count(i->cmd.dest))
                if(!i->known[i->cmd.dest])
                    i->cmd.dest = 0;
                else // значение известно, но это не 0
                    if(i->cmd.opcode==command::jz) nopOut(i);
        }
}

Процедура propagate() реализует объединение множеств неизвестных регистров: регистр с несколькими известными значениями объявляется неизвестным.
bool propagate(pcommandn from, pcommandn to) {
        bool changed = false; // возвращает: изменились ли множества
        // проверяем известные значения
        foreach(i, from->known) {
            regnum r = i->first;
            if(to->known.count(‌r))
                if((to->known[r]!=i->second) // другое, и не заданное правилом 1
                    &&!((to->cmd.opcode==command::mov) && (to->cmd.dest==r))) {
                        to->known.erase(‌r);
                        to->unknown.insert(‌r);
                        changed = true;
                } else; // значение известное и верное
            else if(!to->unknown.count(‌r)) { // по умолчанию, известно
                to->known[r]=i->second;
                changed = true;
            }
        }
        // объединяем неизвестные
        foreach(r, from->unknown)
            if(!to->unknown.count(*r)) {
                to->unknown.insert(*r);
                to->known.erase(*r);
                changed = true;
            }
        return changed;
}

Последнее, что осталось, — собственно вычисление значения, когда операнды известны. Так же, как в выполнятеле джей-скрипа, заводим по функции на каждый опкод:
int hlt(int src1, int src2) { assert(false); return 0; }
int add(int src1, int src2) { return src1+src2; }
int sub(int src1, int src2) { return src1-src2; }
...
int lt(int src1, int src2) { return src1<src2; }
int (*ops[])(int, int) = {hlt, hlt, hlt, hlt, hlt, hlt, hlt, add, sub, mul, div, eq, ne, ge, le, gt, lt};

Вставим вызов constp(); перед copies(); — и на этом с оптимизацией закончим.

В следующем посте — собираем из п-кода с расставленными физическими регистрами настоящий исполнимый код для x86/x64.