taylor simpson Tera Computer Company, 2815 Eastlake Ave.
Does anyone have thoughts/opinions on the algorithm presented in "Simple and Efficient Construction of Static Single Assignment Form" by Braun, et al?
I'm basing some of this on a fun paper I wrote ( and stealing directly from my Ph D thesis ( 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 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.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.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.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.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.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).