Basheyev 20 июн 2021 в 08:48

Разработка стековой виртуальной машины и компилятора под неё (часть III)

8 мин

6.1K

По ходу разработки генератора кода для виртуальной машины понял, что виртуальная машина не готова к полноценным вызовам функций, с передачей аргументов и хранением локальных переменных функций. Поэтому её необходимо доработать. А именно, нужно определиться с Соглашением о вызовах (calling convention). Есть много разных вариантов, но конечный выбор за разработчиком. Главное - это обеспечить целостность стека, после вызова.

Соглашение о вызовах (calling convention) - это правила по которым при вызове функции передаются аргументы в вызываемую функцию (стек/регистры, порядок), кто и как очищает стек после вызова (вызывающий/вызываемый) и как возвращается результат функции в точку вызова (стек/регистр). Ко всему прочему, вызываемые функции могут создавать локальные переменные, которые будут хранится в стеке, что тоже необходимо учитывать, особенно, чтобы работала рекурсия.

На сегодняшний день, наиболее знакомые мне Соглашения о вызове (calling convention), регулирующее правила передачи аргументов функции, очистки стека после вызова, а также логика хранения локальных переменных - это C declaration (cdecl, x86/64) и pascal. Попробую применить эти знания с небольшими модификациями, а именно без прямого доступа программы к регистрам виртуальной машины (она же всё таки стековая, а не регистровая). Итак, логика будет следующая:

Поясню что происходит. Функция main() вызывает функцию sum() и передаёт ей два аргумента - значение переменной i и константное число 10. Осуществляется передача аргументов путём добавления значений аргументов в стек слева направо (как в pascal). После чего осуществляется вызов функции инструкцией виртуальной машины call, которой указывается адрес вызова и количество передаваемых через стек аргументов - 2.

Дальше команда call должна сделать следующие вещи:

сохранить в стек адрес возврата после вызова IP (Instruction Pointer + 1)
сохранить в стек значение Frame Pointer (регистр виртуальной машины, которым мы показываем до куда очищать стек после вызова)
сохраняем в стек значение Locals Pointer (регистр указывающий на место в стеке где начинаются локальные переменные вызывающей функции)
выставить значение Frame Pointer на первый аргумент в стеке, чтобы мы знали докуда очищать стек после завершения выполнения функции
выставить значение Locals Pointer на адрес в стеке сразу после сохранных значение IP, FP, LP.

В свою очередь команда ret должна выполнить действия в обратном порядке:

Восстановить из стека предыдущие значения IP, FP, LP.
Взять результат выполнения функции с вершины стека.
Выставить SP = FP (очистить стек в состояние до вызова).
Положить на вершину стека результат выполнения функции.

Так как делаем стековую, а не регистровую виртуальную машину, не хочу давать прямой доступ к регистрам, поэтому доработаем инструкцию 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 0x21 - это распечатка числа с вершины стека в консоль):

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

[   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 и генерацию кода). Теперь в виртуальной машине есть всё необходимое.

Ура! Это вдохновляет!

Читать далее продолжение статьи и итоги...

Теги:

Хабы:

Разработка стековой виртуальной машины и компилятора под неё (часть III)

Публикации

Истории

Работа

Ближайшие события