Based on a description of each register in a (virtual) machine and each instruction, shouldn't it be possible to generate an interpreter for such machine? And if it's possible to generate a interpreter, shouldn't it be possible to generate a JIT compiler as well? Additionally, if a interpreter can be generated, shouldn't it be possible to generate a "inference engine" that infers various static properties of a program, e.g., that c = a + b is 1 if a = 1 and b = 0?
Of course it is possible -- the question, however, is how such description should look. How convenient is it to write such description? Let's start with the description of the machines registers.
Assuming a simple machine with non-overlapping registers (i.e., no al/ah/ax/eax/rax mess) the register description is fairly straight forward, for instance:
rf: int64[64]
zflag: bit
which say that there is a register file called
rf consisting of 64 64bit registers and a flag,
zflag, indicating whether or not the result of the last arithmetic operation was zero.
Although the above is a description of the machine's register it's a state-less description, in the sense that it purely declarative description of
structure -- there is no mutation described here. Thus, this description is denoted the
structural semantic.
On top of the structure of the machine are the instructions, which mutate the registers. These are described by the
operational semantics. The following describes the
load instruction, which writes an immediate value to the register file:
def load(imm: int64, dst:int6):
rf[dst] = imm
where
imm and
dst are the operands to the instruction -- an immediate and the (index of the) destination register, respectively. Furthermore,
rf is the register file as described by the structural semantics above.
To give some credibility to my first claim, that it is possible to generate an interpreter from this description, note that the semantic description formulated as above can trivially be used as a interpreter (simple text transform is enough) as the following python program indicates:
rf = [0] * 64
zflag = 0
def load(imm, dst):
def execute():
rf[dst] = imm
return execute
program = [load(1000, 0), load(200, 1)]
for instr in program:
instr()
print(rf[0], rf[1])
Furthermore, translating the description into a more efficient C implementation is simply a matter of more trivialities and a tea spoon of relatively straight-forward type inference. But such details are not important for the argument I'm making.
Now, what about generating a JIT compiler for the
load instruction? Let's start by looking at the end result, that is, how can such a JIT compiler be implemented. Here's a sample of an implementation of the
load instruction implemented in C++:
class load {
int64_t imm;
unsigned dst;
public:
load(int64_t imm, unsigned dst) : imm(imm), dst(dst) { }
void emit(Xbyak::CodeGenerator& cg) {
gc.mov(gc.r8, imm);
gc.mov(gc.r9, dst);
gc.mov([rdi + offsetof(State, rf) + gc.r9 * 8],
gc.r9);
}
};
where we used the great
Xbyak framework for translating x64 assembler into binary encoded instructions. This class can be used to emit the
load instruction at runtime, that is, we have a working JIT compiler -- all generated from the
four line long description above!
I'm guessing that you by now sayt
show me the code. Sure,
here is a proof-of-concept implementation. It is called
jiggawatt and it can, as of the writing of this post, generate interpreters and jit compilers that support load instructions, add and sub instructions, non-conditional jumps, and conditional jumps. So far it does not generate a optimizing jit compiler, however that is (one of) the end goal(s).
But so what? Why would you ever need a interpreter and jit compiler generator? Well, as a back-end for DSLs as well as full-fledge programming languages is one application that comes to mind. Emulators of physical processors or other kind of hardware is another. A third application is for prototyping instruction sets and virtual machines.
