Another virtual machine architecture (part two)

This post is a continuation of another virtual machine architecture (part one) .

Last time we stopped at the example of a module that calculates factorial. Consider it in more detail, and then run and check the work.



Before starting the discussion, we give the code that creates the factorial module:

1. ModuleBuilder builder ;
3. VarTypeId vtype = builder. addVarType ( 8 ) ;
4. RegId io = builder. addReg ( 0 , vtype ) ;
5. ProcTypeId ptype = builder. addProcType ( 0 , io ) ;
6. ProcId proc = builder. addProc ( PFLAG_EXTERNAL, ptype ) ;
7. builder. addProcInstr ( proc, JNZInstr ( io, 3 ) ) ;
8. builder. addProcInstr ( proc, CPI8Instr ( 1 , io ) ) ;
9. builder. addProcInstr ( proc, RETInstr ( ) ) ;
10. RegId pr = builder. addReg ( 0 , vtype ) ;
11. builder. addProcInstr ( proc, PUSHInstr ( pr ) ) ;
12. builder. addProcInstr ( proc, CPI8Instr ( 1 , pr ) ) ;
13. builder. addProcInstr ( proc, MULInstr ( io, pr, pr ) ) ;
14. builder. addProcInstr ( proc, DECInstr ( io ) ) ;
15. builder. addProcInstr ( proc, JNZInstr ( io, - 2 ) ) ;
16. builder. addProcInstr ( proc, CPBInstr ( pr, io ) ) ;
17. builder. addProcInstr ( proc, POPInstr ( ) ) ;
18. builder. addProcInstr ( proc, RETInstr ( ) ) ;
20. builder. createModule ( module ) ;

As can be seen from the code, the module is created using the ModuleBuilder class. This class allows you to add variable types, registers, procedures, and more to the module being created.
')
Line 3 defines vtype - the type of a variable whose element contains 8 bytes. Line 4 adds the io register based on this type. Such a register will describe a variable containing one element, i.e., in fact, store one 64-bit word. Further, in line 5, we add a new type of ptype procedure. The type of procedure is an additional entity that defines the procedure call interface. It is needed not only to create a procedure, but also to define a procedural reference. Our example does not use any references, and ptype is only needed to create a single module procedure. This type of procedure assigns the io register we created earlier, as an I / O register. This register will be used by our factorial procedure as an input argument (n) and a return result (n!).

In line 6, an external procedure is created based on the previously defined ptype. Now you need to fill it with instructions. First we insert the conditional branch instruction JNZ. This instruction compares the contents of io with zero. If io is not equal to zero, then there is a jump to 3 instructions forward. Otherwise, we write a unit into io (CPI8 instruction) and exit (RET). As you understand, this is a processing of a particular case of calculating factorial: 0! = 1.

Note that JNZ works with 64-bit numbers. Those. if vtype contained, say, 7 bytes, then on line 7 the ModuleBuilder object would throw an exception, because in this case io would not be a valid argument for this instruction. It is easy to verify that in the case of 9 bytes no error would have occurred. Moreover, if we had added references to other variables to ptype, there would still be no error. This is the general principle - each instruction checks the sufficiency of its argument for its execution and does not object if the variable actually contains additional data. Even if io were an array, JNZ would take into account only the first element, ignoring the rest.

Line 10 defines a new register, pr, for storing the work. Next, a new stack frame is created based on pr (PUSH instruction). From now on, the pr register corresponds to the 64-bit word allocated in the stack.

As mentioned in the previous post, the PUSH instruction corresponds to the POP instruction, which removes the stack frame. Frame nesting can be arbitrary, but the integrity of the stack frame cannot be broken. This, in particular, means that the frame cannot contain instructions for moving beyond its limits. The integrity of the frames is monitored by the ModuleBuilder.



In line 12, we assign pr to one. The following instruction, being a loop body, assigns pr = io * pr (MUL instruction). Next, the io (DEC instruction) is decremented, and the result is compared with zero (JNZ instruction). If io is not zeroed out, go back two instructions.

From line 16, the cycle body has ended and the assignment is io = pr. Since we have done all the work, we no longer need pr, so we delete the corresponding frame (POP instruction), and finally, we exit the function (RET instruction).

In line 20, we create a new module with which the variable module is associated. Now we have to run our factorial procedure.

1. SVariable < 8 , 0 , 0 > io ;
2. uint64_t & val = * reinterpret_cast < uint64_t * > ( io. elts [ 0 ] . bytes ) ;
4. module. unpack ( ) ;
6. val = 20 ;
7. module. callProc ( proc, io ) ;
8. if ( val ! = 2432902008176640000LLU )
9. throw Exception ( ) ;

In line 1, we create an instance of the structure corresponding to the variable in one 64-bit word (for the time being we omit the definition of the SVariable structure). In line 2 we prepare the variable for convenient testing of the result.

In line 4, we unpack the module. Unpacking means compiling into machine code (using the LLVM infrastructure for this). Now we calculate the factorial for n = 20. You can make sure that we get the correct result.