A catalog of ways to generate SSA
bernsteinbear.comStatic Single Assignment is a program representation where each “variable” (though this term can be misleading) is assigned exactly once. Mostly the variables aren’t variables at all, but instead names for values—for expressions. SSA is used a lot in compilers. See this lesson from Cornell for converting Bril to SSA, which also has some good background. I’m making this page to catalog the papers I have found interesting and leave a couple of comments on them.
I’m making progress on the Java decompiler I’ve mentioned in a previous post, and I want to share the next couple of tricks I’m using to speed it up. Java bytecode is a stack-based language, and so data flow is a bit cursed, especially when the control flow is complicated. I need to analyze data flow globally for expression inlining and some other stuff. Single-static assignment produces basically everything I need as a byproduct… but it’s not very fast. For one thing, it typically mutates the IR instead of returning data separately, and the resulting IR has imperative code mixed with functional code, which is a little unpleasant to work with. SSA has multiple implementations with very different performance characteristics and conditions, and each of them forces me to make a tradeoff I’m not positive about.
⌚ Nice watch!
How I implement SSA form. GitHub Gist: instantly share code, notes, and snippets.