Does anyone have thoughts/opinions on the algorithm presented in "Simple and Efficient Construction of Static Single Assignment Form"[1] by Braun, et al? I'm mostly wondering whether there are any non-obvious "gotchas" that aren't apparent to me as a non-expert.

1. http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf

It's a well-regarded folklore algorithm, although that paper is the first publication with a detailed analysis. If I was designing a compiler frontend and optimizer/backend in concert I would definitely use it unless some other constraint prevented it. In addition to not having to generate a non-SSA program and then immediately throw it away, it allows you to do basic optimizations during SSA construction that you would probably do immediately after constructing SSA anyways.

The two major downsides would be extra complexity in the frontend and the impossibility of using the algorithm for SSA repair after IR modifications. The extra complexity in the frontend can hopefully be hidden behind an abstraction, and a lot of serious compilers end up using a separate implementation of SSA construction for repair anyways, so I don't know how big of a deal these drawbacks really are.

I am one of the authors of the "highly-optimized implementation of Cytron et al.'s algorithm" that is used in LLVM. That is a bit of a misattribution; I changed LLVM to use the DJ graph algorithm by Sreedhar and Gao before they took their measurements for the paper. I would have expected their approach to be even faster in comparison than what they measured, but it could just be that they didn't do serious performance analysis and tuning.

That's a great project. I was always curious about what makes SSA so special for compiler construction. Can we have more context? Why this book? For who?

Why SSA? Please also read the first chapter.

What: The IR (internal represention) is in SSA form is if every variable is defined once, and every use of a variable refers to exactly one definition. Think of const-only or functional programming, without any assignment statements. In SSA you can have only one lvalue, and multiple writes to the same variable in different branches are split into so-called phi merges, with a renamed final variable.

Why? It's the basis for most compiler optimizations. You can write compilers without, but for most optimizations you'll need to convert to SSA.

For whom? For compiler and optimizer writers. People who like to optimize their programs to get better performance.

> what makes SSA so special for compiler construction

It makes doing immutability and loop invariant reasoning a ton easier, along with constant propagation: https://en.wikipedia.org/wiki/Static_single_assignment_form

More generally, SSA means implicit use/def information. Use/def information and traversal are critical components of many static analyses and transformations: having the IR in SSA form greatly simplifies reasoning about and implementing these analyses and transformations.

This is a great question, and its one that isn't really made clear anywhere iin compiler books that teach it. The tl;dr is that you get lots of nice properties for free, and that it makes writing analysis algorithms much simpler with fewer edge cases.

For context, I was involved for a bit in writing this book, and I was at the conference that spawned it, and I wrote chapter 25. That said, it's been a few years and my memory is poor, so I may have some details below wrong. I'm basing some of this on a fun paper I wrote (http://paulbiggar.com/research/fit-2009.pdf) and stealing directly from my PhD thesis (http://paulbiggar.com/research/#phd-dissertation, section 3.3)

Factored use-def chain: With a def-use chain, dataflow results may be propagated directly from the assignment of a variable to all of its uses. However, a def-use chain requires an edge from each definition to each use, which may be expensive when a program has many definitions and uses of the same variable. In practice, this occurs in the presence of switch-statements. SSA factors the def-use chain over a φ-node, avoiding this pathological case.

OK, english version: in program analysis, you want to know the value of a variable, so you create a "def-use chain" which connects a definition of a variable to all of its uses. In some cases, you might have very many uses and definitions, esp of the same variable. This esp happens with switch-statements. In SSA form, each variable is only defined once, so you dont get pathological cases here.

Flow-sensitivity: A flow-insensitive algorithm performed on an SSA form is much more precise than if SSA form were not used. The flow-insensitive problem of multiple definitions to the same variable is solved by the single assignment property. The allows a flow-insensitive algorithm to approach the precision of a flow-sensitive algorithm.

English version: if you put something in SSA form, you can connect the use of a value directly to its definition (since it's only defined once, with one value). Without SSA, you might have more definitions of that variable, and so not know it's exact value, type, etc, when you go to use it. Without SSA form, to get that data you'd have to analyse the flow of the program (look at loops and if statements, etc). With SSA form, you can ignore those and get a similar level of precision.

Memory usage: Without SSA form, an analysis must store information for every variable at every program point. SSA form allows a sparse analysis, where an analysis must store information only for every assignment in the program. With a unique version per assignment, the memory usage of storing the results of an analysis can be considerably lower than using bit-vector or set-based approaches.

In English: When storing the results of your analysis, you can save them much more cheaply in SSA form, from a CPU and memory perspective. Without SSA, you need a hashtable of variables, with a list of values each. In SSA form, you only need on value, not a list of values, for each variable. You can also number single-assignment variables by number, rather than by name, and so use simple arrays rather than hashtables to store the results.

It might also interest this audience that the book source is in their subversion:

https://gforge.inria.fr/scm/viewvc.php/book/?root=ssabook

There is also a "slides" directory up one, but I didn't investigate further.

Nice start.