Разработка стековой виртуальной машины и компилятора под неё (часть III)
По ходу разработки генератора кода для виртуальной машины понял, что виртуальная машина не готова к полноценным вызовам функций, с передачей аргументов и хранением локальных переменных функций. Поэтому её необходимо доработать. А именно, нужно определиться с Соглашением о вызовах (calling convention). Есть много разных вариантов, но конечный выбор за разработчиком. Главное — это обеспечить целостность стека, после вызова.
Соглашение о вызовах (calling convention) — это правила по которым при вызове функции передаются аргументы в вызываемую функцию (стек/регистры, порядок), кто и как очищает стек после вызова (вызывающий/вызываемый) и как возвращается результат функции в точку вызова (стек/регистр). Ко всему прочему, вызываемые функции могут создавать локальные переменные, которые будут хранится в стеке, что тоже необходимо учитывать, особенно, чтобы работала рекурсия.
На сегодняшний день, наиболее знакомые мне Соглашения о вызове (calling convention), регулирующее правила передачи аргументов функции, очистки стека после вызова, а также логика хранения локальных переменных — это C declaration (cdecl, x86/64) и pascal. Попробую применить эти знания с небольшими модификациями, а именно без прямого доступа программы к регистрам виртуальной машины (она же всё таки стековая, а не регистровая). Итак, логика будет следующая:
Поясню что происходит. Функция main () вызывает функцию sum () и передаёт ей два аргумента — значение переменной i и константное число 10. Осуществляется передача аргументов путём добавления значений аргументов в стек слева направо (как в pascal). После чего осуществляется вызов функции инструкцией виртуальной машины call, которой указывается адрес вызова и количество передаваемых через стек аргументов — 2.
Дальше команда call должна сделать следующие вещи:
1) сохранить в стек адрес возврата после вызова IP (Instruction Pointer + 1)
2) сохранить в стек значение Frame Pointer (регистр виртуальной машины, которым мы показываем до куда очищать стек после вызова).
3) сохраняем в стек значение Locals Pointer (регистр указывающий на место в стеке где начинаются локальные переменные вызывающей функции).
4) выставить значение Frame Pointer на первый аргумент в стеке, чтобы мы знали докуда очищать стек после завершения выполнения функции.
5) выставить значение Locals Pointer на адрес в стеке сразу после сохранных значение IP, FP, LP.
В свою очередь команда ret должна выполнить действия в обратном порядке:
1) Восстановить из стека предыдущие значения IP, FP, LP.
2) Взять результат выполнения функции с вершины стека.
3) Выставить SP = FP (очистить стек в состояние до вызова).
4) Положить на вершину стека результат выполнения функции.
Так как делаем стековую, а не регистровую виртуальную машину, не хочу давать прямой доступ к регистрам, поэтому доработаем инструкцию CALL / RET, а также добавим четыре дополнительные инструкции LOAD (положить в стек значение локальной переменной с указанным индексом), STORE (взять верхнее значение в стеке и сохранить в локальной переменной с указанным индексом), ARG (добавить в стек значение аргумента функции с указанным индексом), а также DROP — инструкция выбросить из стека верхнее значение. Последняя инструкция DROP нужна для функций значение которых нам не нужно, так как мы не даём прямой доступ к регистрам.
case OP_CALL:
a = memory[ip++]; // get call address and increment address
b = memory[ip++]; // get arguments count (argc)
b = sp + b; // calculate new frame pointer
memory[--sp] = ip; // push return address to the stack
memory[--sp] = fp; // push old Frame pointer to stack
memory[--sp] = lp; // push old Local variables pointer to stack
fp = b; // set Frame pointer to arguments pointer
lp = sp - 1; // set Local variables pointer after top of a stack
ip = a; // jump to call address
break;
case OP_RET:
a = memory[sp++]; // read function return value on top of a stack
b = lp; // save Local variables pointer
sp = fp; // set stack pointer to Frame pointer (drop locals)
lp = memory[b + 1]; // restore old Local variables pointer
fp = memory[b + 2]; // restore old Frame pointer
ip = memory[b + 3]; // set IP to return address
memory[--sp] = a; // save return value on top of a stack
break;
case OP_LOAD:
a = memory[ip++]; // read local variable index
b = lp - a; // calculate local variable address
memory[--sp] = memory[b]; // push local variable to stack
break;
case OP_STORE:
a = memory[ip++]; // read local variable index
b = lp - a; // calculate local variable address
memory[b] = memory[sp++]; // pop top of stack to local variable
break;
case OP_ARG:
a = memory[ip++]; // read parameter index
b = fp - a - 1; // calculate parameter address
memory[--sp] = memory[b]; // push parameter to stack
break;
case OP_DROP: // pop and drop value from stack
sp++;
break;Скомпилируем код представленный на иллюстрации выше чтобы протестировать как работают новые инструкции CALL, RET, LOAD, STORE, ARG (примечание: syscall 0×21 — это распечатка числа с вершины стека в консоль):
Запустим исполнение этого кода с распечаткой состояния виртуальной машины после выполнения каждой инструкции:
[ 0] iconst 5 IP=2 FP=65535 LP=65534 SP=65534 STACK=[5] -> TOP
[ 2] iload #0 IP=4 FP=65535 LP=65534 SP=65533 STACK=[5,5] -> TOP
[ 4] idec IP=5 FP=65535 LP=65534 SP=65533 STACK=[5,4] -> TOP
[ 5] idup IP=6 FP=65535 LP=65534 SP=65532 STACK=[5,4,4] -> TOP
[ 6] istore #0 IP=8 FP=65535 LP=65534 SP=65533 STACK=[4,4] -> TOP
[ 8] idup IP=9 FP=65535 LP=65534 SP=65532 STACK=[4,4,4] -> TOP
[ 9] iconst 10 IP=11 FP=65535 LP=65534 SP=65531 STACK=[4,4,4,10] -> TOP
[ 11] call [32], 2 IP=32 FP=65533 LP=65527 SP=65528 STACK=[4,4,4,10,14,65535,65534] -> TOP
[ 32] iconst 10 IP=34 FP=65533 LP=65527 SP=65527 STACK=[4,4,4,10,14,65535,65534,10] -> TOP
[ 34] iarg #0 IP=36 FP=65533 LP=65527 SP=65526 STACK=[4,4,4,10,14,65535,65534,10,4] -> TOP
[ 36] iarg #1 IP=38 FP=65533 LP=65527 SP=65525 STACK=[4,4,4,10,14,65535,65534,10,4,10] -> TOP
[ 38] iadd IP=39 FP=65533 LP=65527 SP=65526 STACK=[4,4,4,10,14,65535,65534,10,14] -> TOP
[ 39] iload #0 IP=41 FP=65533 LP=65527 SP=65525 STACK=[4,4,4,10,14,65535,65534,10,14,10] -> TOP
[ 41] isub IP=42 FP=65533 LP=65527 SP=65526 STACK=[4,4,4,10,14,65535,65534,10,4] -> TOP
[ 42] ret IP=14 FP=65535 LP=65534 SP=65532 STACK=[4,4,4] -> TOP
[ 14] syscall 0x21 IP=16 FP=65535 LP=65534 SP=65533 STACK=[4,4] -> TOP
[ 16] iconst 0 IP=18 FP=65535 LP=65534 SP=65532 STACK=[4,4,0] -> TOP
[ 18] icmpjg [2] IP=2 FP=65535 LP=65534 SP=65534 STACK=[4] -> TOP
[ 2] iload #0 IP=4 FP=65535 LP=65534 SP=65533 STACK=[4,4] -> TOP
[ 4] idec IP=5 FP=65535 LP=65534 SP=65533 STACK=[4,3] -> TOP
[ 5] idup IP=6 FP=65535 LP=65534 SP=65532 STACK=[4,3,3] -> TOP
[ 6] istore #0 IP=8 FP=65535 LP=65534 SP=65533 STACK=[3,3] -> TOP
[ 8] idup IP=9 FP=65535 LP=65534 SP=65532 STACK=[3,3,3] -> TOP
[ 9] iconst 10 IP=11 FP=65535 LP=65534 SP=65531 STACK=[3,3,3,10] -> TOP
[ 11] call [32], 2 IP=32 FP=65533 LP=65527 SP=65528 STACK=[3,3,3,10,14,65535,65534] -> TOP
[ 32] iconst 10 IP=34 FP=65533 LP=65527 SP=65527 STACK=[3,3,3,10,14,65535,65534,10] -> TOP
[ 34] iarg #0 IP=36 FP=65533 LP=65527 SP=65526 STACK=[3,3,3,10,14,65535,65534,10,3] -> TOP
[ 36] iarg #1 IP=38 FP=65533 LP=65527 SP=65525 STACK=[3,3,3,10,14,65535,65534,10,3,10] -> TOP
[ 38] iadd IP=39 FP=65533 LP=65527 SP=65526 STACK=[3,3,3,10,14,65535,65534,10,13] -> TOP
[ 39] iload #0 IP=41 FP=65533 LP=65527 SP=65525 STACK=[3,3,3,10,14,65535,65534,10,13,10] -> TOP
[ 41] isub IP=42 FP=65533 LP=65527 SP=65526 STACK=[3,3,3,10,14,65535,65534,10,3] -> TOP
[ 42] ret IP=14 FP=65535 LP=65534 SP=65532 STACK=[3,3,3] -> TOP
[ 14] syscall 0x21 IP=16 FP=65535 LP=65534 SP=65533 STACK=[3,3] -> TOP
[ 16] iconst 0 IP=18 FP=65535 LP=65534 SP=65532 STACK=[3,3,0] -> TOP
[ 18] icmpjg [2] IP=2 FP=65535 LP=65534 SP=65534 STACK=[3] -> TOP
[ 2] iload #0 IP=4 FP=65535 LP=65534 SP=65533 STACK=[3,3] -> TOP
[ 4] idec IP=5 FP=65535 LP=65534 SP=65533 STACK=[3,2] -> TOP
[ 5] idup IP=6 FP=65535 LP=65534 SP=65532 STACK=[3,2,2] -> TOP
[ 6] istore #0 IP=8 FP=65535 LP=65534 SP=65533 STACK=[2,2] -> TOP
[ 8] idup IP=9 FP=65535 LP=65534 SP=65532 STACK=[2,2,2] -> TOP
[ 9] iconst 10 IP=11 FP=65535 LP=65534 SP=65531 STACK=[2,2,2,10] -> TOP
[ 11] call [32], 2 IP=32 FP=65533 LP=65527 SP=65528 STACK=[2,2,2,10,14,65535,65534] -> TOP
[ 32] iconst 10 IP=34 FP=65533 LP=65527 SP=65527 STACK=[2,2,2,10,14,65535,65534,10] -> TOP
[ 34] iarg #0 IP=36 FP=65533 LP=65527 SP=65526 STACK=[2,2,2,10,14,65535,65534,10,2] -> TOP
[ 36] iarg #1 IP=38 FP=65533 LP=65527 SP=65525 STACK=[2,2,2,10,14,65535,65534,10,2,10] -> TOP
[ 38] iadd IP=39 FP=65533 LP=65527 SP=65526 STACK=[2,2,2,10,14,65535,65534,10,12] -> TOP
[ 39] iload #0 IP=41 FP=65533 LP=65527 SP=65525 STACK=[2,2,2,10,14,65535,65534,10,12,10] -> TOP
[ 41] isub IP=42 FP=65533 LP=65527 SP=65526 STACK=[2,2,2,10,14,65535,65534,10,2] -> TOP
[ 42] ret IP=14 FP=65535 LP=65534 SP=65532 STACK=[2,2,2] -> TOP
[ 14] syscall 0x21 IP=16 FP=65535 LP=65534 SP=65533 STACK=[2,2] -> TOP
[ 16] iconst 0 IP=18 FP=65535 LP=65534 SP=65532 STACK=[2,2,0] -> TOP
[ 18] icmpjg [2] IP=2 FP=65535 LP=65534 SP=65534 STACK=[2] -> TOP
[ 2] iload #0 IP=4 FP=65535 LP=65534 SP=65533 STACK=[2,2] -> TOP
[ 4] idec IP=5 FP=65535 LP=65534 SP=65533 STACK=[2,1] -> TOP
[ 5] idup IP=6 FP=65535 LP=65534 SP=65532 STACK=[2,1,1] -> TOP
[ 6] istore #0 IP=8 FP=65535 LP=65534 SP=65533 STACK=[1,1] -> TOP
[ 8] idup IP=9 FP=65535 LP=65534 SP=65532 STACK=[1,1,1] -> TOP
[ 9] iconst 10 IP=11 FP=65535 LP=65534 SP=65531 STACK=[1,1,1,10] -> TOP
[ 11] call [32], 2 IP=32 FP=65533 LP=65527 SP=65528 STACK=[1,1,1,10,14,65535,65534] -> TOP
[ 32] iconst 10 IP=34 FP=65533 LP=65527 SP=65527 STACK=[1,1,1,10,14,65535,65534,10] -> TOP
[ 34] iarg #0 IP=36 FP=65533 LP=65527 SP=65526 STACK=[1,1,1,10,14,65535,65534,10,1] -> TOP
[ 36] iarg #1 IP=38 FP=65533 LP=65527 SP=65525 STACK=[1,1,1,10,14,65535,65534,10,1,10] -> TOP
[ 38] iadd IP=39 FP=65533 LP=65527 SP=65526 STACK=[1,1,1,10,14,65535,65534,10,11] -> TOP
[ 39] iload #0 IP=41 FP=65533 LP=65527 SP=65525 STACK=[1,1,1,10,14,65535,65534,10,11,10] -> TOP
[ 41] isub IP=42 FP=65533 LP=65527 SP=65526 STACK=[1,1,1,10,14,65535,65534,10,1] -> TOP
[ 42] ret IP=14 FP=65535 LP=65534 SP=65532 STACK=[1,1,1] -> TOP
[ 14] syscall 0x21 IP=16 FP=65535 LP=65534 SP=65533 STACK=[1,1] -> TOP
[ 16] iconst 0 IP=18 FP=65535 LP=65534 SP=65532 STACK=[1,1,0] -> TOP
[ 18] icmpjg [2] IP=2 FP=65535 LP=65534 SP=65534 STACK=[1] -> TOP
[ 2] iload #0 IP=4 FP=65535 LP=65534 SP=65533 STACK=[1,1] -> TOP
[ 4] idec IP=5 FP=65535 LP=65534 SP=65533 STACK=[1,0] -> TOP
[ 5] idup IP=6 FP=65535 LP=65534 SP=65532 STACK=[1,0,0] -> TOP
[ 6] istore #0 IP=8 FP=65535 LP=65534 SP=65533 STACK=[0,0] -> TOP
[ 8] idup IP=9 FP=65535 LP=65534 SP=65532 STACK=[0,0,0] -> TOP
[ 9] iconst 10 IP=11 FP=65535 LP=65534 SP=65531 STACK=[0,0,0,10] -> TOP
[ 11] call [32], 2 IP=32 FP=65533 LP=65527 SP=65528 STACK=[0,0,0,10,14,65535,65534] -> TOP
[ 32] iconst 10 IP=34 FP=65533 LP=65527 SP=65527 STACK=[0,0,0,10,14,65535,65534,10] -> TOP
[ 34] iarg #0 IP=36 FP=65533 LP=65527 SP=65526 STACK=[0,0,0,10,14,65535,65534,10,0] -> TOP
[ 36] iarg #1 IP=38 FP=65533 LP=65527 SP=65525 STACK=[0,0,0,10,14,65535,65534,10,0,10] -> TOP
[ 38] iadd IP=39 FP=65533 LP=65527 SP=65526 STACK=[0,0,0,10,14,65535,65534,10,10] -> TOP
[ 39] iload #0 IP=41 FP=65533 LP=65527 SP=65525 STACK=[0,0,0,10,14,65535,65534,10,10,10] -> TOP
[ 41] isub IP=42 FP=65533 LP=65527 SP=65526 STACK=[0,0,0,10,14,65535,65534,10,0] -> TOP
[ 42] ret IP=14 FP=65535 LP=65534 SP=65532 STACK=[0,0,0] -> TOP
[ 14] syscall 0x21 IP=16 FP=65535 LP=65534 SP=65533 STACK=[0,0] -> TOP
[ 16] iconst 0 IP=18 FP=65535 LP=65534 SP=65532 STACK=[0,0,0] -> TOP
[ 18] icmpjg [2] IP=20 FP=65535 LP=65534 SP=65534 STACK=[0] -> TOP
[ 20] ---- halt ----IP=21 FP=65535 LP=65534 SP=65534 STACK=[0] -> TOP
EXECUTION TIME: 0.620997sВ консоли данная программа выдает следующее
Эти числа в консоли говорят, что вызовы функций, передача аргументов, аллокация локальных переменных, возврат значения и восстановление стека после вызова работают нормально. Значит можно полностью переходить и фокусироваться на разработке компилятора для этой виртуальной машины (AST и генерацию кода). Теперь в виртуальной машине есть всё необходимое.
Ура! Это вдохновляет!
