File names are infinite in length, where infinity is set to 255 characters.
--Peter Collinson: The Unix File System
Итак, у нас есть программа на п-коде, и в её распоряжении неограниченное количество регистров (т.е. 255). Число регистров у реального процессора куда меньше (предположим, четыре). Что будем делать?
Далее в посте:
- Разбор п-кода
- Время жизни
- Реализация
- Простые оптимизации
- Расщепление версий
- Работа с памятью
- Что получилось?
Разбор п-кода
В прошлом посте был дамп скомпилированной программы. Её 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)
- На выход каждой команды копируем вход достижимых из неё команд; (правило №2)
- На вход каждой команды копируем её выход, исключая записанный командой регистр; (правило №3)
- На выход каждой команды копируем вход достижимых из неё команд; (правило №2)
После нескольких итераций получаем окончательную разметку «живучести регистров» — какие регистры нужны каждой команде. Тогда можем переименовывать регистры п-кода в физические — например, «по-жадному»: берём «самый нужный» регистр (нужный наибольшему количеством команд); переименовываем в физический, который ещё не занят в соответствующих командах; повторяем.
Оптимальный выбор, каким п-регистрам следует предоставить физические, чтобы хватило на как можно больше, — возможен только полным перебором: эта задача равносильна «раскраске графа в минимум цветов», про которую математики верят, что для неё не существует эффективного решения. Наше «жадное» приближение — не самое худшее из возможных.
Что делать, если для очередного п-регистра не окажется свободного физического? Например, в нашем коде есть команды (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
Зато, поскольку используется только четыре регистра, этот п-код возможно будет перевести в машинный код реального процессора.
Продолжим в августе: уезжаю в отпуск, и дописываю этот пост прямо из аэропорта.
Всем приятного лета!
