Static Single-Assignment Form

Static Single-Assignment form is an intermediate format that allows optimizations to be done efficiently and easily. Every variable receives exactly one assignment during its lifetime, and $\phi$-functions are added at places where program flow joins. The value of the $\phi$-function ``magically'' depends on the path the program has taken; in practice, a move-insertion on each entrance path implements the $\phi$-function when coverting out of SSA form. An example, taken from [C+91], is shown in figures 1 and 2.

  

Figure 1: Straight-line code and its single assignment version.

  

Figure 2: If-expression code and its single assignment version.

The use of $\phi$-functions simplifies the book-keeping for various optimizations, and by maintaining a single point of definition for every variable allows the algorithms to execute in linear, rather than quadratic, time. Furthermore, this work has disovered that the $\phi$-function notation allows concise and accurate identification of state-machine registers in the translation of loop constructs. This application will be further discussed in section 4.3.2.

The translation into SSA form uses the algorithms discussed in [App97,C+91,LT79]. The dominator tree is computed using the Lengauer-Tarjan algorithm and path-compression, and is then used to compute the dominance frontier using Cytron's two-pass algorithm. After adding $\phi$-functions for the variable a at the dominance frontier of every node where a is defined, we walk the dominator tree to rename variables so that every variable is defined exactly once. There is a simpler algorithm for SSA form translation that utilizes source-language information to aid placement [BM94], but the more complicated algorithm implemented here works on simple quadruples, and thus allows front-end (source language) modification or replacement without necessitating changes to the back-end implemented in this project.

The $\phi$-functions of the SSA form were implemented as a tenth type of quadruple, and a flowgraph of the SSA-format quadruple list was input to the optimization routines.