Clark Verbrugge pointed out to me that someone had done work on making a *very* simple SSA conversion algorithm. It works by first pessimistically inserting phi nodes everywhere, and then iteratively removing them using two (trivial) simplification rules. This generates minimal SSA for reducible graphs, and has the advantage of being extremely simple. Furthermore, it has the advantage that we can tweak the cost by setting a maximum number of iterations, if we wish.
The authors show timing comparisons slowing that with unbounded number of iterations, it's slightly slower than dominance frontiers, *but*, it's much simpler to implement, it's *incremental* (meaning we can eliminate phi nodes introduced by naive code transformations easily), and I think we can improve over it by being less pessimistic when we first insert phi nodes. We could also potentially make it better for irreducible graphs by implementing more powerful reduction rules w.r.t. cycles, which we could use for code we really want to optimize.
I suggest we implement this algorithm for the AST->SSA IR conversion. It will be fast to implement, and fast if we bound the number of iterations for the baseline compiler. It should also be fairly easy to replace by another algorithm if we ever think we need to.
See: "SIMPLE GENERATION OF STATIC SINGLE ASSIGNMENT FORM", CC2000, JOHN AYCOCK, NIGEL HORSPOOL
- Maxime