Methods to implement a register-based IR in static single assignment form

Question

I'm writing a compiler for a register-based bytecode to an IR with static single assignment (SSA) form (specifically, from Dalvik VM bytecode to LLVM IR, but I'm hoping the question can be taken for the general topic) and am wondering the best, or theoretically cleanest way to go about this.

For instance, if we have the register-based instructions:

add vA, vB, vC    (vA := vB + vC)
...
sub vA, vD, vE    (vA := vD - vE)

then we can no longer use the old value of vA as it has been overwritten and replaced with vD - vE.

In SSA form we would have something more like

vA1 := vB + vC
...
vA2 := vD - vE

as each variable is assigned exactly once.

The problem is that in mapping from the register-based language we have no need of these previous values that SSA form keeps track of, as we only ever use the most up-to-date value of each register. To me it seems bad practise, or just "dirty", to keep creating new variables which we'll never use, but I suppose that's what you get with the representation.

My question is therefore what is the best way of achieving this mapping (a bit subjective, sorry). My original idea was that since I know the (fixed) number of registers used for each method I can keep a track of the most up-to-date value for each register and only ever use that, but I'm not sure how that'd work in practise.

I look forward to hearing your ideas.

Answer 1

Well, in general you'll have to use something similar to SSA construction algorithms. Things might be complicated in your case in presence of branching (consider e.g. you have if-else-like construction and you have one register modified only in "if" clause, but used afterwards).

Speaking of LLVM IR - just simply emit stuff in non-SSA form (allocating the registers on stack via alloca and load/store the values to then) and then just have mem2reg pass to clean everything for you. This is how clang, llvm-gcc and many other frontends emit the things :)