> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/programming_language_theory/codegen/single_static_assignment_form.md).

# Single Static Assignment (SSA) form

## Basic idea

An IR in which every variable is assigned exactly once. Joins in control flow are bridged by $\phi$-functions that pick a value based on which predecessor block executed. SSA exposes data-flow directly and makes most optimisations linear.

## Key formulas

* $\phi$-function: $x\_3 = \phi(x\_1, x\_2)$ at a join from blocks $B\_1, B\_2$.
* Dominance frontier $DF(B)$: nodes where $B$ does *not* strictly dominate but does dominate a predecessor — places where $\phi$-nodes are inserted.
* Cytron et al.'s algorithm: linear in size of dominance frontiers.