5
$\begingroup$

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:

SSA Example 1

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?

$\endgroup$
  • $\begingroup$ I've implementing memoization for now, but that seems like cheating/not learning. $\endgroup$ – Jonathan Dickinson Jul 22 '16 at 21:33
  • $\begingroup$ This seems more complicated than the out-of-SSA algorithms I know. Why are you reinventing it anyway? $\endgroup$ – harold Jul 22 '16 at 21:35
  • $\begingroup$ @harold - Agreed, see last two sentences. Self-learning, and I can't find any approachable content on this stuff. All I can really find is "how to translate and work with SSA" and that's where the buck stops. Nothing really on translation to machine code. $\endgroup$ – Jonathan Dickinson Jul 22 '16 at 22:14
  • 2
    $\begingroup$ There is work on that too, for example check "Generalized Instruction Selection using SSA-Graphs" and the later chapters (or all of it, why not) of the "Static Single Assignment Book". $\endgroup$ – harold Jul 22 '16 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.