Данный пост является продолжением Ещё одной архитектуры виртуальной машины (части первой).
В прошлый раз мы остановились на примере модуля, вычисляющего факториал. Рассмотрим его подробнее, а потом запустим и проверим работу.
Прежде, чем начать обсуждение, приведём код, создающий модуль факториала:
Строка 3 определяет vtype — тип переменной, элемент которой содержит 8 байт. В строке 4 добавляется регистр io на базе этого типа. Такой регистр будет описывать переменную, содержащую один элемент, т.е., по сути, хранить одно 64-битное слово. Далее, в строке 5, добавляем новый тип процедуры ptype. Тип процедуры – дополнительная сущность, определяющая интерфейс вызова процедуры. Она нужна не только для создания процедуры, но и для определения процедурной ссылки. Наш пример не использует никаких ссылок, и ptype нужен только для создания единственной процедуры модуля. Данный тип процедуры назначает ранее созданный нами регистр io, в качестве регистра ввода-вывода. Этот регистр наша процедура факториала будет использовать в качестве входного аргумента (n) и возвращаемого результата (n!).
В строке 6 создаётся внешняя процедура на базе ранее определённого нами ptype. Теперь нужно наполнить её инструкциями. Вначале вставляем инструкцию условного перехода JNZ. Эта инструкция сравнивает содержимое io с нулём. Если io не равен нулю, то происходит прыжок на 3 инструкции вперёд. В противном случае мы записываем в io единицу (инструкция CPI8) и выходим (RET). Как вы поняли, это обработка частного случая вычисления факториала: 0! = 1.
Обратим внимание, что JNZ работает с 64-битными числами. Т.е. если бы vtype содержал, скажем, 7 байт, то на строке 7 объект ModuleBuilder бросил бы исключение, поскольку в таком случае io не являлся бы валидным аргументом для этой инструкции. Легко проверить, что в случае 9 байт никакой ошибки бы не произошло. Более того, если бы мы в ptype добавили ссылки на другие переменные, ошибки всё равно не было бы. Таков общий принцип – каждая инструкция проверяет достаточность своего аргумента для её выполнения и не возражает, если фактически переменная содержит дополнительные данные. Даже если бы io был массивом, JNZ приняла бы во внимание только первый элемент, игнорируя остальные.
В строке 10 определяется новый регистр pr для хранения произведения. Далее создаётся новый стековый фрейм на основе pr (инструкция PUSH). С этих пор регистру pr соответствует 64-битное слово, выделенное в стеке.
Как было сказано в предыдущем посте, инструкции PUSH соответствует инструкция POP, удаляющая стековый фрейм. Вложенность фреймов может быть произвольной, но целостность стекового фрейма не может быть нарушена. Это, в частности, значит, что фрейм не может содержать инструкцию перехода за его пределы. За целостностью фреймов следит ModuleBuilder.
В строке 12 мы присваиваем pr единицу. Следующая инструкция, являясь телом цикла, присваивает pr = io * pr (инструкция MUL). Далее декрементируется io (инструкция DEC), и результат сравнивается с нулём (инструкция JNZ). Если io не обнулился, происходит переход на две инструкции назад.
Со строки 16 тело цикла закончилось и происходит присвоение io = pr. Поскольку мы выполнили всю работу, нам больше не нужен pr, потому мы удаляем соответствующий фрейм (инструкция POP), и, наконец, выходим из функции (инструкция RET).
В строке 20 мы создаём новый модуль, с которым ассоциирована переменная module. Теперь нам остаётся запустить нашу процедуру факториала.
В строке 4 мы распаковываем модуль. Распаковка означает компиляцию в машинный код (для этого используется инфраструктура LLVM). Теперь посчитаем факториал для n = 20. Можно убедиться, что мы получаем верный результат.
В прошлый раз мы остановились на примере модуля, вычисляющего факториал. Рассмотрим его подробнее, а потом запустим и проверим работу.
Прежде, чем начать обсуждение, приведём код, создающий модуль факториала:
Как видно из кода, модуль создаётся с помощью класса ModuleBuilder. Этот класс позволяет добавлять типы переменных, регистры, процедуры и многое другое в создаваемый модуль.
- ModuleBuilder builder;
- VarTypeId vtype = builder.addVarType(8);
- RegId io = builder.addReg(0, vtype);
- ProcTypeId ptype = builder.addProcType(0, io);
- ProcId proc = builder.addProc(PFLAG_EXTERNAL, ptype);
- builder.addProcInstr(proc, JNZInstr(io, 3));
- builder.addProcInstr(proc, CPI8Instr(1, io));
- builder.addProcInstr(proc, RETInstr());
- RegId pr = builder.addReg(0, vtype);
- builder.addProcInstr(proc, PUSHInstr(pr));
- builder.addProcInstr(proc, CPI8Instr(1, pr));
- builder.addProcInstr(proc, MULInstr(io, pr, pr));
- builder.addProcInstr(proc, DECInstr(io));
- builder.addProcInstr(proc, JNZInstr(io, -2));
- builder.addProcInstr(proc, CPBInstr(pr, io));
- builder.addProcInstr(proc, POPInstr());
- builder.addProcInstr(proc, RETInstr());
- builder.createModule(module);
Строка 3 определяет vtype — тип переменной, элемент которой содержит 8 байт. В строке 4 добавляется регистр io на базе этого типа. Такой регистр будет описывать переменную, содержащую один элемент, т.е., по сути, хранить одно 64-битное слово. Далее, в строке 5, добавляем новый тип процедуры ptype. Тип процедуры – дополнительная сущность, определяющая интерфейс вызова процедуры. Она нужна не только для создания процедуры, но и для определения процедурной ссылки. Наш пример не использует никаких ссылок, и ptype нужен только для создания единственной процедуры модуля. Данный тип процедуры назначает ранее созданный нами регистр io, в качестве регистра ввода-вывода. Этот регистр наша процедура факториала будет использовать в качестве входного аргумента (n) и возвращаемого результата (n!).
В строке 6 создаётся внешняя процедура на базе ранее определённого нами ptype. Теперь нужно наполнить её инструкциями. Вначале вставляем инструкцию условного перехода JNZ. Эта инструкция сравнивает содержимое io с нулём. Если io не равен нулю, то происходит прыжок на 3 инструкции вперёд. В противном случае мы записываем в io единицу (инструкция CPI8) и выходим (RET). Как вы поняли, это обработка частного случая вычисления факториала: 0! = 1.
Обратим внимание, что JNZ работает с 64-битными числами. Т.е. если бы vtype содержал, скажем, 7 байт, то на строке 7 объект ModuleBuilder бросил бы исключение, поскольку в таком случае io не являлся бы валидным аргументом для этой инструкции. Легко проверить, что в случае 9 байт никакой ошибки бы не произошло. Более того, если бы мы в ptype добавили ссылки на другие переменные, ошибки всё равно не было бы. Таков общий принцип – каждая инструкция проверяет достаточность своего аргумента для её выполнения и не возражает, если фактически переменная содержит дополнительные данные. Даже если бы io был массивом, JNZ приняла бы во внимание только первый элемент, игнорируя остальные.
В строке 10 определяется новый регистр pr для хранения произведения. Далее создаётся новый стековый фрейм на основе pr (инструкция PUSH). С этих пор регистру pr соответствует 64-битное слово, выделенное в стеке.
Как было сказано в предыдущем посте, инструкции PUSH соответствует инструкция POP, удаляющая стековый фрейм. Вложенность фреймов может быть произвольной, но целостность стекового фрейма не может быть нарушена. Это, в частности, значит, что фрейм не может содержать инструкцию перехода за его пределы. За целостностью фреймов следит ModuleBuilder.
В строке 12 мы присваиваем pr единицу. Следующая инструкция, являясь телом цикла, присваивает pr = io * pr (инструкция MUL). Далее декрементируется io (инструкция DEC), и результат сравнивается с нулём (инструкция JNZ). Если io не обнулился, происходит переход на две инструкции назад.
Со строки 16 тело цикла закончилось и происходит присвоение io = pr. Поскольку мы выполнили всю работу, нам больше не нужен pr, потому мы удаляем соответствующий фрейм (инструкция POP), и, наконец, выходим из функции (инструкция RET).
В строке 20 мы создаём новый модуль, с которым ассоциирована переменная module. Теперь нам остаётся запустить нашу процедуру факториала.
В строке 1 мы создаём экземпляр структуры, соответствующей переменной в одно 64-битное слово (определение структуры SVariable пока опустим). В строке 2 готовим переменную для удобного тестирования результата.
- SVariable<8, 0, 0> io;
- uint64_t &val = *reinterpret_cast<uint64_t*>(io.elts[0].bytes);
- module.unpack();
- val = 20;
- module.callProc(proc, io);
- if(val != 2432902008176640000LLU)
- throw Exception();
В строке 4 мы распаковываем модуль. Распаковка означает компиляцию в машинный код (для этого используется инфраструктура LLVM). Теперь посчитаем факториал для n = 20. Можно убедиться, что мы получаем верный результат.
