Static Single Assignment Form
The Static Single Assignment (SSA) form is a representation of programs that is used in many optimizing compilers. Many optimization algorithms are simpler to implement if a program has been converted to this form. The SSA form was proposed by Shapiro and Saint in 1970, but it did not become popular until around 1990 when Cytron, Ferrante et al showed how to use dominance frontiers to compute the SSA form.
The key step in conversion to SSA form is F-placement. If V and E denote the sets of nodes and edges respectively of the program, the algorithm of Cytron et al can take W(|V|*|V|) time even for structured programs. Sreedhar and Gao used DJ-graphs to do F-placement in O(|E|) time, but their algorithm is not competitive with the Cytron et al algorithm in practice.
With Gianfranco Bilardi, we showed that F-placement can be done in O(|E|), using the Augmented Dominator Tree (ADT) data structure. This algorithm is asymptotically optimal for doing F-placement for a single variable. On the SPEC benchmarks, this algorithm runs 5 times faster than the DJ-graph algorithm for this problem, and it outperforms the dominance frontiers algorithm by a small margin.
We also invented an optimal algorithm for doing F-placement for multiple variables in structured programs. The problem of designing such an algorithm for general programs remains open.
All these algorithms are described in our JACM paper which is a "everything you ever wanted to know about SSA form but were afraid to ask" paper! This paper provides a simple framework, based a new relation called the merge relation, for understanding all F-placement algorithms in the literature. In the process of describing these algorithms, we also derive most known properties of the SSA form; we also present a number of previously unpublished algorithms for doing F-placement in O(|E|) time.