SSA for stack machine code

Question

I'm working on a compiler for a stack machine (specifically CIL) and I've parsed the code into a graph of basic blocks. From here I'm looking to apply SSA to the methods, but it's not going too well. My first attempt (while working with a flat listing, rather than the graph) was to iterate over the code and keep a stack of SSA ids (that is, for the assign targets), pushing them when I produce an assignment, popping them when they're used. This works just fine for a single basic block, but I simply can't figure out how to handle producing Φ functions.

The idea I've been tossing around is to attach a stack position to the SSA ids and then look at what's still on the stack when the code paths converge, but this doesn't seem like the Right Way (TM) of doing things.

Is there a simple algorithm for tracking the stack manipulations across multiple code paths and determining the collisions when they converge?

Answer 1

You need to look at the multiple set of SSA ids converging on a node (basic block). Keep the intermediate basic block structure, that way you can easily use (e.g. query) all identifiers in a block.

I'm not sure what you mean with collision, but I assume you want to solve something like

 if (bExp)                  if (bExp)
   x := 1                    x1 := 1
 else            SSA:       else
   x := 2                    x2 := 2
 y := x;                    y := Phi(x1,x2)

that is, you want the Phi at this place. Realize that there is no Phi in executable code! Using the information that y is either (dependent) on x1 or x2, you can rewrite this in the next step. For example, in a memory-centric representation, the Phi(x1,x2) tells you that x1 and x2 should be two aliases to the same memory location, namely that of y. Phi just ties information together.

if (bExp)
  stackframe[y_index] = 1     (y_index being some offset)
else
  stackframe[y_index] = 2
nop

Hope this helps a bit!