I'm working on an LLVM-like kit for .Net - because this is something that's lacking in .Net and I really want to learn the more advanced compilation theory.
I'm really struggling to find anything digestible for turning Phi into platform code (in this case MSIL). Consider the following SSA fragment:
inputs = a0
a1 = a0 + 1
br branch1 a0 > 100
a2 = a1 / 2
br branch1
branch1:
a3 = phi(a1, a2)
_ = Log(a3, a1)
Granted, this code makes no sense from a AST-to-SSA standpoint because you'd need a temp in the source language anyway - it's valid SSA nonetheless.
The solution I came up with is to create a directed graph out out of all instructions. Edges are directed from stores toward the future read. Essentially:
NB: direction of arrows next to the red node.
When storing to a register (keeping in mind that MSIL has "infinitely" many registers), you just follow the directed graph and store to the final register that you end up on. If more than one path can be taken, allocate temporary registers and continue down each path (recursively).
inputs = p
r1 = p + 1
r2 = r1
if r1 > 100
r1 = r1 / 2
Log(r1, r2)
Because I'm using a graph, loops are a compounding problem (StackOverflow problems, not the website type). I decided on Tarjan's strongly connected components algorithm to do a topological sort and to identify cycles (what a beautiful algorithm). Creating a flyweight to indicate which variable(s) to assign to is then "merely" a matter of looping over the strongly connected components in reverse and maintaining some state.
The "merely" part of that is where I'm getting tripped up - things are becoming O(Nscary) very quickly. I also need to kludge in reading from inputs/parameters, because I'm using the last variableN that the values get stored to, to also load from (for obvious reasons). This gives me the idea that I've headed down the wrong path, and I'm out of ideas.
Does someone have a nudge in the right direction for me?
