Разработка стековой виртуальной машины и компилятора под неё (часть I)
Так сложилось, что за последние 18 лет, не приходилось писать на C/C++. На работе использовалась Java, да и ввиду должностей деятельность больше была связана с предпринимательством — переговоры, корпоративные продажи, выстраивание производственных операций и структурирование инвестиционных сделок. Захотелось в свободное от работы время восстановить навыки, размять часть мозга которую не напрягал все 18 лет и, естественно, начать с самых основ. Осталось придумать себе задачу.
В универе преподаватели, молодость которых приходилась на 70–80е годы, до объектно-ориентированного программирования убивались по теме разработке собственных языков (интерпретаторов, компиляторов) под предметные области. Всё это казалось невостребованным «старьём», но появление новых языков за последнее десятилетие (Go, Kotlin и множества других) повысили мой интерес к этой теме.
Решил в качестве хобби написать 32-bit стековую виртуальную машину и компилятор C подобного языка под неё, чтобы восстановить базовые навыки. Такая классическая Computer Science задачка для заполнения вечеров с пивом. Как предприниматель, я четко понимаю, что она никому не нужна, но такая практика нужна мне для эстетического инженерного удовольствия. Плюс когда об этом рассказываешь сам понимаешь глубже. С целью и мотивами определился. Начнём.
Так как это виртуальная машина, мне нужно определиться с её характеристиками:
CPU: 32-bitный набор команд, так как машина стековая, в основном операнды команд храним в стеке, из регистров только IP (Instruction Pointer) и SP (Stack Pointer), пока работаем с целыми числами со знаком (__int32), позже добавим остальные типы данных.
RAM: пусть памяти пока будет 65536 ячеек по 32-bit`а. Которую организуем просто. С нижних адресов в верх будут идти код (code/text) и данные (data, heap), а с верхних адресов вниз будет расти стек (stack). Дёшево и сердито.
Предусмотрим вот такие операции:
typedef __int32 WORD;
constexpr WORD OP_CODE_MASK = 0b00000000000000000000000011111111;
constexpr WORD OP_TYPE_MASK = 0b00000000000000000000111000000000;
constexpr WORD OP_HALT = 0b00000000000000000000000000000000;
constexpr WORD OP_CONST = 0b00000000000000000000000000000001;
constexpr WORD OP_PUSH = 0b00000000000000000000000000000010;
constexpr WORD OP_POP = 0b00000000000000000000000000000011;
constexpr WORD OP_INC = 0b00000000000000000000000000000100;
constexpr WORD OP_DEC = 0b00000000000000000000000000000101;
constexpr WORD OP_ADD = 0b00000000000000000000000000000110;
constexpr WORD OP_SUB = 0b00000000000000000000000000000111;
constexpr WORD OP_MUL = 0b00000000000000000000000000001000;
constexpr WORD OP_DIV = 0b00000000000000000000000000001001;
constexpr WORD OP_AND = 0b00000000000000000000000000001010;
constexpr WORD OP_OR = 0b00000000000000000000000000001011;
constexpr WORD OP_XOR = 0b00000000000000000000000000001100;
constexpr WORD OP_NOT = 0b00000000000000000000000000001101;
constexpr WORD OP_SHL = 0b00000000000000000000000000001110;
constexpr WORD OP_SHR = 0b00000000000000000000000000001111;
constexpr WORD OP_JMP = 0b00000000000000000000000000010001;
constexpr WORD OP_CMPJE = 0b00000000000000000000000000010010;
constexpr WORD OP_CMPJNE = 0b00000000000000000000000000010011;
constexpr WORD OP_CMPJG = 0b00000000000000000000000000010100;
constexpr WORD OP_CMPJGE = 0b00000000000000000000000000010101;
constexpr WORD OP_CMPJL = 0b00000000000000000000000000010110;
constexpr WORD OP_CMPJLE = 0b00000000000000000000000000010111;
constexpr WORD OP_DUP = 0b00000000000000000000000000011000;
constexpr WORD OP_CALL = 0b00000000000000000000000000011001;
constexpr WORD OP_RET = 0b00000000000000000000000000011010;
constexpr WORD OP_SYSCALL = 0b00000000000000000000000000011011;
constexpr WORD OP_RESERVED1 = 0b00000000000000000000000000011100;
constexpr WORD OP_RESERVED2 = 0b00000000000000000000000000011101;
constexpr WORD OP_RESERVED3 = 0b00000000000000000000000000011110;
constexpr WORD OP_RESERVED4 = 0b00000000000000000000000000011111;
constexpr WORD MAX_MEMORY = 65536;Пока первые 8 из 32 бит будут под команду (opcode), 1 бит зарезервируем под тип операнда (immediate или из стека), 3 бита под будущие типы данных (byte, short, int, long, char, float, double и что нибудь ещё), а остальные биты для чего нибудь применим. Пока не знаю.
class VMRuntime {
public:
VMRuntime(); // Constructor
~VMRuntime(); // Desctructor
bool loadImage(void* image, size_t size); // Load executable image
void run(); // Runs image from address 0
WORD readWord(WORD address); // Read WORD from memory
void writeWord(WORD address, WORD value); // Write WORD to memory
WORD getMaxAddress(); // Get max address in 32-bit words
WORD getIP(); // Get Instruction Pointer address
WORD getSP(); // Get Stack Pointer address
private:
WORD memory[MAX_MEMORY]; // Random access memory array
WORD ip; // Instruction pointer
WORD sp; // Stack pointer
WORD fp; // Frame pointer
void systemCall(WORD n); // System call
void printState(); // Print current VM state
};В классе виртуальной машине сделаем такие методы, чтобы загружать исполняемый образ в память виртуальной машины (loadImage), запускать исполнение (run), позволять снаружи читать/писать память (readWord, writeWord), читать состояние регистров IP, SP. Из приватных методов сделаем вывод состояния машины (распечатка регистров и содержания стека), а также метод для системных вызовов, чтобы код виртуальной машины мог вызывать что-то снаружи (сделаем проброс какого-нибудь API).
Исполнение построим просто — шагаем по памяти последовательно, читаем команду, в зависимости от команды берём операнды либо из стека, либо читаем операнд в следующей ячейке после команды. Повторяем пока не дойдём до команды HALT.
void VMRuntime::run() {
WORD a, b;
WORD opcode;
ip = 0;
sp = MAX_MEMORY - 1;
while (1) {
opcode = memory[ip++];
switch (opcode) {
//------------------------------------------------------------------------
// STACK OPERATIONS
//------------------------------------------------------------------------
case OP_CONST:
memory[--sp] = memory[ip++];
break;
case OP_PUSH:
memory[--sp] = memory[memory[ip++]];
break;
case OP_POP:
memory[memory[ip++]] = memory[sp++];
break;
case OP_DUP:
a = memory[sp];
memory[--sp] = a;
break;
//------------------------------------------------------------------------
// ARITHMETIC OPERATIONS
//------------------------------------------------------------------------
case OP_INC:
memory[sp]++;
break;
case OP_DEC:
memory[sp]--;
break;
case OP_ADD:
b = memory[sp++];
a = memory[sp++];
memory[--sp] = a + b;
break;
case OP_SUB:
b = memory[sp++];
a = memory[sp++];
memory[--sp] = a - b;
break;
case OP_MUL:
b = memory[sp++];
a = memory[sp++];
memory[--sp] = a * b;
break;
case OP_DIV:
b = memory[sp++];
a = memory[sp++];
memory[--sp] = a / b;
break;
//------------------------------------------------------------------------
// BITWISE OPERATIONS
//------------------------------------------------------------------------
case OP_AND:
b = memory[sp++];
a = memory[sp++];
memory[--sp] = a & b;
break;
case OP_OR:
b = memory[sp++];
a = memory[sp++];
memory[--sp] = a | b;
break;
case OP_XOR:
b = memory[sp++];
a = memory[sp++];
memory[--sp] = a ^ b;
break;
case OP_NOT:
a = memory[sp++];
memory[--sp] = ~a;
break;
case OP_SHL:
b = memory[sp++];
a = memory[sp++];
memory[--sp] = a << b;
break;
case OP_SHR:
b = memory[sp++];
a = memory[sp++];
memory[--sp] = a >> b;
break;
//------------------------------------------------------------------------
// FLOW CONTROL OPERATIONS
//------------------------------------------------------------------------
case OP_JMP:
ip = memory[ip];
break;
case OP_CMPJE:
b = memory[sp++];
a = memory[sp++];
if (a == b) ip = memory[ip]; else ip++;
break;
case OP_CMPJNE:
b = memory[sp++];
a = memory[sp++];
if (a != b) ip = memory[ip]; else ip++;
break;
case OP_CMPJG:
b = memory[sp++];
a = memory[sp++];
if (a > b) ip = memory[ip]; else ip++;
break;
case OP_CMPJGE:
a = memory[sp++];
b = memory[sp++];
if (a >= b) ip = memory[ip]; else ip++;
break;
case OP_CMPJL:
b = memory[sp++];
a = memory[sp++];
if (a < b) ip = memory[ip]; else ip++;
break;
case OP_CMPJLE:
b = memory[sp++];
a = memory[sp++];
if (a <= b) ip = memory[ip]; else ip++;
break;
//------------------------------------------------------------------------
// PROCEDURE CALL OPERATIONS
//------------------------------------------------------------------------
case OP_CALL:
a = memory[ip++];
memory[--sp] = ip;
ip = a;
break;
case OP_RET:
ip = memory[sp++];
break;
case OP_SYSCALL:
a = memory[ip++];
systemCall(a);
break;
case OP_HALT:
printState();
return;
default:
cout << "Runtime error - unknown opcode=" << opcode << endl;
printState();
return;
}
}
// Only one system call implemented - print string (0x20)
void VMRuntime::systemCall(WORD n) {
WORD ptr;
switch (n) {
case 0x20: // print C style string
ptr = memory[sp++];
cout << ((char*)&memory[ptr]);
break;
}
}В итоге получаем простенькую машину, которая умеет в арифметические и битовые операции, управлять ходом исполнения с условными переходами, вызывать функции (пока четкой конвенции по передачи аргументов через стек нет, но дальше доделаем).
Еще нам потребуется реализовать класс с помощью которого мы будем готовить исполняемый образ. Прикрутим к нему простые методы, которые будут записывать команды и данные, чтобы потом можно было этот образ «скормить» виртуальной машине.
class VMImage {
public:
VMImage();
~VMImage();
void clear();
WORD setEmitPointer(WORD address);
WORD getEmitPointer();
WORD emit(WORD opcode);
WORD emit(WORD opcode, WORD operand);
WORD readWord(WORD address);
void writeWord(WORD address, WORD value);
WORD writeData(WORD address, void* data, size_t length);
void* getImage();
size_t getImageSize();
void dissasemble();
private:
WORD memory[MAX_MEMORY];
WORD imageSize;
WORD ep;
};И теперь можно попробовать сделать простенькую программу с циклом и вызовом функции, которая печатает «Hello, world from VM!» 10 раз, чтобы проверить, что виртуальная машина более менее работает. На ассемблере виртуальной машины (мнемоники пока будут очень условные, синтаксис до конца не придумал) это программа будет выглядеть примерно так:
start: // Адрес [0]
push iVar // затолкаем значение iVar в стек
dec // уменьшим на один
call fn // вызовем функцию fn
dup // продублируем верхнее значение в стеке (Top Of Stack)
pop iVar // вытащим верхнее значение стека и запишем в iVar
const 0 // затолкаем в стек константу 0 для сравнения
cmpjg start // если iVar > 0 прыгаем на start:
halt // иначе завершаем программу
fn: // Адрес [64]
const myStr // заталкиваем в стек адрес строки
syscall 0x20 // делаем системный вызов для вывода строки в консоль
ret // возвращаемся туда откуда нас вызвали
dataSeg: // Адрес [128]
iVar = 10
myStr = "Hello, world from VM!\n"Сейчас лень писать под эту задачу транслятор для ассемблера виртуальной машины, потому что делаем высокоуровневый язык, который будем сходу компилировать в команды виртуальной машины. Но чтобы это записать в исполняемый виртуальной машиной образ воспользуемся классом VMImage:
void createExecutableImage(VMImage* img) {
WORD dataSeg = 128; // Data segment starts at 256
WORD iVar = dataSeg;
WORD myStr = dataSeg + 1;
img->writeWord(iVar, 10);
img->writeData(myStr, "Hello, world from VM!\n", 23);
WORD fn = 64;
WORD start = img->emit(OP_PUSH, iVar); // stack <- [iVar] (operand 1)
img->emit(OP_DEC); // stack[top]-- (operand 1 decrement)
img->emit(OP_CALL, fn); // Call function fn()
img->emit(OP_DUP); // duplicate stack top (operand 1 duplicate)
img->emit(OP_POP, iVar); // stack -> [iVar] (pop operand 1 duplicate to iVar)
img->emit(OP_CONST, 0); // push const 0 (operand 2)
img->emit(OP_CMPJG, start); // if (operand1 > operand2) jump to addr
img->emit(OP_HALT); // end of program
img->setEmitPointer(fn); // Function fn()
img->emit(OP_CONST, myStr); // Push constant string address
img->emit(OP_SYSCALL, 0x20); // Call system call 0x20, to print C style string to standard output
img->emit(OP_RET); // Return
}А затем запустим исполнение нашего образа на виртуальной машине, замерив время:
int main() {
VMImage* img = new VMImage();
createExecutableImage(img);
VMRuntime* vm = new VMRuntime();
vm->loadImage(img->getImage(), img->getImageSize());
auto start = std::chrono::high_resolution_clock::now();
vm->run();
auto end = std::chrono::high_resolution_clock::now();
auto ms_int = chrono::duration_cast(end - start).count();
cout << "EXECUTION TIME: " << ms_int / 1000000000.0 << "s" << endl;
delete vm;
delete img;
} Получаем в консоли:
Ура! Классно! Работают арифметика, команды условных переходов и вызов функций!
Это воодушевляет. Видимо дальше буду развивать эту историю…
