I've been working on a project that I call veria for around two months now, and yesterday it compiled the first piece of Java code to native x64 code through the veria jit compiler. The largest and most complex part of veria is implemented; what remains is mostly the backend of the jit compiler. Most of the backend is trivial stuff -- two hash lookups, a call to a libjit function, and a hash insertion -- however, the phi instruction (the veria instruction set is register-based single static assignment) is somewhat complicated as libjit uses a somewhat different model. Let's take an example; first an instruction set with phi nodes (similar to veria):
JEQ R0, R1, L1
R2 = 10
JMP L2
L1:
R3 = 20
L2:
R4 = PHI(R2, R3)
Second, the same function in an instruction set similar to libjit's:
JEQ R0, R1, L1
R2 = 10
MEM[0] = R2
JMP L2
L1:
R3 = 20
MEM[0] = R2
L2:
R4 = MEM[0]
Looking carefully at these two instruction sequences we see that the PHI instruction is replaced with R4 = MEM[0] (reading from the memory) and the assignments to R2 and R3 are followed by a write to MEM[0]. The instruction sequence without the PHI instruction is very close to how code running on an actual computer, while the first has this magic PHI instruction that can't really be executed... but, assuming R4 = PHI(R2, R3) is just another spelling of R4 = MEM[0], all that is missing from the first sequence to be executed are the writes to memory.
Let's spell those write instructions as PREPHI and give it and it's matching PHI instruction a unique number. Here's the result with comments saying the alternative spelling:
JEQ R0, R1, L1
R2 = 10
PREPHI R2, 0 // MEM[0] = R2
JMP L2
L1:
R3 = 20
PREPHI R3, 0 // MEM[0] = R3
L2:
R4 = PHI(R2, R3, 0) // R4 = MEM[0]
So what we got here is an instruction set that is single static assignments but that can be mapped to instructions set such as libjit's through a single pass. And it also de-mystifies the phi instruction. The cost is that any phi instruction inserted by the optimizer needs a matching prephi instructions.
