По ходу разработки генератора кода для виртуальной машины понял, что виртуальная машина не готова к полноценным вызовам функций, с передачей аргументов и хранением локальных переменных функций. Поэтому её необходимо доработать. А именно, нужно определиться с Соглашением о вызовах (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 и генерацию кода). Теперь в виртуальной машине есть всё необходимое.
Ура! Это вдохновляет!
Kroleg
Frame pointer — лишняя сущность. Всё можно адресовать относительно вершины стека. И всегда известно сколько из него вычесть при возврате.
Basheyev Автор
Интересно! Не сообразил как это сделать, если я не храню количество аргументов, локальных переменных и программа не имеет доступа к регистрам. Подскажите как? Попробую реализовать.
Kroleg
При компиляции любого выражения, компилятор знает, сколько временных объектов было помещено в стек. Это число — глубина самой вложенной локальной переменной относительно вершины стека. Остальные локалы находятся в соседних более глубоких элементах стека. Также копилятор знает количество локалов в данной точке. Сложив эти два числа компилятор получит смещение в стеке до элемента, хранящего адрес возврата. Сразу за адресом возврата в стеке лежат параметры, количество которых тоже известно компилятору.
То есть алгоритм такой:
Заводим в компиляторе три переменные:
params_count— количество параметров текущей функции (если язык разрешает переменное количество параметров — эта переменная хранит количество именованных парметров, а остальные пакуются в iterable контейнер, который становится еще одним параметром)locals_count— количество живых локалов — от начала функции до текущег компилируемого выражения.temps_count— глубина стека в текущем компилируемом выражении.Добавляем в виртуальную машину две инструкции
push_local/pop_localc одним числовым параметром —offset. Первая инструкция помещает на стек элемент стека, находящийся на глубине offset от вершины. Вторая наоборот снимает со стека вершину и присваивает ее элементу на глубинеoffsetот вершины. Эти две инструкции используются для доступа к локалам, параметрам, записи результата, и всяких манипуляций нужных для операций вида:a.field[index] += value.Порядок действий (при компиляции):
this_local->offset = ++locals_countdropи делаемlocals_count--push->temps_count++, приpop->temps_count--, при других инструкциях влияющих на стек — тоже изменяемtemps_count, напримерaddснимает со стека два элемента и кладет один, значитtemps_count--.push_local/pop_localс параметромtemps_count + locals_count - this_local->offsetpush_local/pop_localtemps_count + locals_count + 1 /*там адрес возврата лежит*/ + parameter->offset.return <expression>— компилируемexpression;pop_local temps_count + locals_count + 1 /*адрес возврата*/ + parameters_count; компилируемdrop temps_count + locals_count;ret. А коллер после инструкцииcallможет добавитьdrop function->params_count.При этом возможны вариации и оптимизации, например, можно класть результат прямо в место для первого параметра, или ввести специальную инструкцию
ret_val, в которой закодировано два числа — количество снимаемых темпов+локалов (смещение до адреса возврата) и количество снимаемых параметров, которое одновременно задает глубину элемента стека для результата. Такая инструкция позволяет очищать стек из вызывамой функции и экономит две инструкцииdropи однуpop_local.В общем, если сделать компилятор чуть более умным, можно сделать виртуальную машину существенно более постой и эффективной.
Кстати, имея
locals_countиtemps_count, компилятор может вычислитьmax_frame_sizeи положить его в начало функции, и тогда vm может делать проверку в момент вызова функции и защищаться от переполнения стека.qw1
Это имеет смысл, если делаем jit (компилируем в маш. код), тогда можно освободить регистр rbp под другие нужды. Но если у нас интерпретатор, не факт что после такой «оптимизации» код будет проще (а значит, быстрее), чем явное хранение frame pointer в переменной.
Kroleg
В обоих случаях для доступа к локалу и параметру нужно будет делать доступ в память по указателю (sp или frame pointer) + смещение из инструкции. Так что эта конкретная инструкция будет одинакова. Вообще-то в случае frame pointer смещение должно быть знаковым, и его получение из байткода будет дороже.
Экономия в моем подходе возникает:
serge-phi
Без FP трудно будет сделать трассировку стека для отладки и реализовать отмотку стека для try/catch/finally. Стоит ли оно того?
Kroleg
Try-catch-finally распадается на три несвязанные проблемы:
диспетчеризация - узнать насколько отмотать стек и к какому байткоду перейти (это делается или картами байткода или добавлением в стек capture-фреймов или прямыми проверками в каждом call и источнике исключений и переходу на landing pad) - эта проблема ортогональна frame-pointer-ам
размотка - разрушение локалов и темпов, делается или через GC или теггированием стековых элементов или разнесением стека значении и стека ссылок или в landing pad-ах. Эта часть тоже не зависит от того, используются frame-pointer-ы или нет.
восстановление контекста - присваивание правильных значений sp, pc, frame-pointer, exception handler и еще некоторым tls переменным, восстановление регистров. Для этой задачи frame-pointer создает лишнюю проблему.
Для отладки - vm должен иметь интерфейс отладчика с
on_function_entryon_function_returnметодами. Отладчик ведет свой список кадров активации. Положение всех локалов и параметров отсчитывается от соответствующего кадра. Информация отладчика хранится в отладчике (single responsibility).