Русский
Русский
English
Статистика
Реклама

Разработка стековой виртуальной машины и компилятора под неё (часть 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 addressb = memory[ip++];      // get arguments count (argc)b = sp + b;            // calculate new frame pointermemory[--sp] = ip;     // push return address to the stackmemory[--sp] = fp;     // push old Frame pointer to stackmemory[--sp] = lp;     // push old Local variables pointer to stackfp = b;                // set Frame pointer to arguments pointerlp = sp - 1;           // set Local variables pointer after top of a stackip = a;                // jump to call addressbreak;case OP_RET:a = memory[sp++];      // read function return value on top of a stackb = lp;                // save Local variables pointersp = fp;               // set stack pointer to Frame pointer (drop locals)lp = memory[b + 1];    // restore old Local variables pointerfp = memory[b + 2];    // restore old Frame pointerip = memory[b + 3];    // set IP to return addressmemory[--sp] = a;      // save return value on top of a stackbreak;case OP_LOAD:a = memory[ip++];         // read local variable indexb = lp - a;               // calculate local variable addressmemory[--sp] = memory[b]; // push local variable to stackbreak;case OP_STORE:a = memory[ip++];         // read local variable indexb = lp - a;               // calculate local variable addressmemory[b] = memory[sp++]; // pop top of stack to local variablebreak;case OP_ARG:a = memory[ip++];         // read parameter indexb = fp - a - 1;           // calculate parameter addressmemory[--sp] = memory[b]; // push parameter to stackbreak;case OP_DROP:                   // pop and drop value from stacksp++;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] -> TOPEXECUTION TIME: 0.620997s

В консоли данная программа выдает следующее

Эти числа в консоли говорят, что вызовы функций, передача аргументов, аллокация локальных переменных, возврат значения и восстановление стека после вызова работают нормально. Значит можно полностью переходить и фокусироваться на разработке компилятора для этой виртуальной машины (AST и генерацию кода). Теперь в виртуальной машине есть всё необходимое.

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

Источник: habr.com
К списку статей
Опубликовано: 20.06.2021 10:05:00
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

C++

Виртуализация

Компиляторы

C

Виртуальные машины

Хобби

Категории

Последние комментарии

© 2006-2022, personeltest.ru