В свободное время попиливаю компилятор ЯП для разминки мозгов и чтобы не забыть ассемблер окончательно.
По семантике ЯП Си-подобный, по синтаксису больше похож на что-то из линейки Паскаль/Модула/Оберон.
За основу брал Context Хохлова, но перепилил практически все сорцы.
Компилятор многопроходный. Сначала строится синтаксическое дерево. Потом на нём выполняются некоторые простые оптимизации. Потом запускается бэкэнд. (Другой подход применён, например, в tcc, где программа компилируется за один проход — ради скорости компиляции.)
Некоторые вещи вычисляются/оптимизируются сразу при парсинге. Например, логическое отрицание вообще не сохраняется в синтаксическое дерево, если может быть заменено на эквивалентную трансформацию отрицаемого выражения:
word Not(word P)
switch Node[P].ID of
case iOR: Node[P].ID = iAND; Not(Node[P].pLeft); Not(Node[P].pRight);
case iAND: Node[P].ID = iOR; Not(Node[P].pLeft); Not(Node[P].pRight);
case iXOR: Node[P].ID = iEQV;
case iEQV: Node[P].ID = iXOR;
case iLT: Node[P].ID = iGE;
case iLE: Node[P].ID = iGT;
case iEQ: Node[P].ID = iNE;
case iNE: Node[P].ID = iEQ;
case iGE: Node[P].ID = iLT;
case iGT: Node[P].ID = iLE;
default:
word P2 = Peek();
Node[P2].ID = iNOT;
Node[P2].pLeft = P;
return P2;
end:switch
return P;
end
Бэкэнд не строит промежуточного представления, на котором можно было бы гонять умные алгоритмы, соответственно 90% оптимизаций, описанных в «Книге дракона» невозможны. Пока я пытаюсь выжать максимум из компиляции на основе синтаксического дерева.
Ассемблерный листинг строится рекурсивным обходом дерева. При этом оптимизация осуществляется локально, в каждом отдельном узле, исходя только из информации доступной для узла и пары его дочерних элементов (или иногда — заглядывая чуть глубже).
Хочу показать, чего удалось добиться с этим подходом на примере компиляции арифметических выражений:
Оптимизация умножения на константу при помощи add, shl и lea. Пример умножения на 15 при помощи lea:
mov EAX, dword [EBP-24]
lea EAX, [EAX*2+EAX]
lea EAX, [EAX*4+EAX]
push EAX
call @10013
Компиляция выражения put_word(v100 * 18 + v1 * 27);:
mov EAX, dword [EBP-24]
lea EAX, [EAX*8+EAX]
add EAX, EAX
mov EBX, dword [EBP-8]
lea EBX, [EBX*2+EBX]
lea EBX, [EBX*8+EBX]
add EAX, EBX
push EAX
call @10013
Здесь умножения заменены более оптимальными инструкциями и разумно распределены регистры.
Компиляция выражения word v500 = v2 * v100 + v3 * v100;:
mov EAX, dword [EBP-12]
mul dword [EBP-24]
push EAX
mov EAX, dword [EBP-16]
mul dword [EBP-24]
pop EBX
add EAX, EBX
mov dword [EBP-32], EAX
Более оптимальным кодом был бы вариант:
mov EAX, dword [EBP-12]
mul dword [EBP-24]
mov EBX, EAX
mov EAX, dword [EBP-16]
mul dword [EBP-24]
add EAX, EBX
mov dword [EBP-32], EAX
Но компилятору в текущей реализации недоступна информация, потребуется ли EBX при вычислении второго слагаемого. Поэтому он сохраняет EAX на стек и затем восстанавливает оттуда значение в EBX уже после того как второе слагаемое вычислено.
Компиляция выражения put_word(v500 - v100 * v5);:
mov EAX, dword [EBP-24]
mul dword [EBP-20]
mov EBX, dword [EBP-32]
xchg EAX, EBX
sub EAX, EBX
push EAX
call @10013
Компилятор требует от выражения результат во вполне определённом регистре. Поэтому столкнувшись с тем, что операнды оказались в обратном порядке, он вынужден вставлять лишний xchg. Ситуацию можно решить, если разрешить выражению в ряде случаев свободно выбирать регистр для результата. Тогда код был бы таким:
mov EAX, dword [EBP-24]
mul dword [EBP-20]
mov EBX, dword [EBP-32]
sub EBX, EAX
push EBX
call @10013
Компиляция выражения put_word((v500 * 2 + v2) + (v200 & v1) + (v200 - 100) * 10 - 100 - v200 - v100);:
mov EAX, dword [EBP-32]
add EAX, EAX
add EAX, dword [EBP-12]
mov EBX, dword [EBP-28]
and EBX, dword [EBP-8]
add EAX, EBX
mov EBX, dword [EBP-28]
sub EBX, 100
lea EBX, [EBX*4+EBX]
add EBX, EBX
add EAX, EBX
sub EAX, 100
sub EAX, dword [EBP-28]
sub EAX, dword [EBP-24]
push EAX
call @10013
Пример компиляции ветвлений для блока switch (табличная реализация switch пока отсутствует) :
mov EAX, dword [@@DATA+EAX+7177840]
sub EAX, 0xD
je @11097
sub EAX, 0x3
je @11098
sub EAX, 0xFFFFFFFE
je @11099
dec EAX
je @11100
sub EAX, 0x5
je @11101
dec EAX
je @11102
dec EAX
je @11103
dec EAX
je @11104
dec EAX
je @11105
dec EAX
je @11106
jmp @11107
Пример переиспользования значения константы в регистре вместо загрузки другой константы:
word v0 = 0;
word v1 = 1;
word v2 = 2;
word v3 = 3;
word v5 = 5;
word v100 = 100;
word v200 = 200;
xor EAX, EAX
mov dword [EBP-4], EAX
inc EAX
mov dword [EBP-8], EAX
inc EAX
mov dword [EBP-12], EAX
inc EAX
mov dword [EBP-16], EAX
mov EAX, 5
mov dword [EBP-20], EAX
mov EAX, 100
mov dword [EBP-24], EAX
add EAX, EAX
mov dword [EBP-28], EAX
Сам компилятор полностью работоспособен, запускается в 32-разрядном режиме под виндой и линуксом и, в принципе, легко может быть портирован на другие ОС. Написан на самом себе (self-hosted) и частично обвешан тестами. Далее в планах научить его генерировать код для какой-нибудь другой системы команд. ARM, MIPS, RISC-V… что-то из этого.
Задавайте ваши вопросы.
