Skip to content

Programming Language Theory: Analysis#

Static Single Assignment#

Each variable is (statically, syntactically) assigned only once

SSA Forms#

Conceptually, there's only one true SSA form - the maximal one.
All others are optimizations that generate fewer φ functions, so fewer need to be removed later

  • Minimality Axis: continuum between fully maximal SSA to fully minimal
  • Fully maximal: split every variable at every basic-block boundary, and put φ-functions for every variable in every block
    • crude but most intuitive form for construction with simplest algorithms for both phi insertion and variable renaming phases
    • renaming could process blocks in arbitrary order
  • Optimized maximal: avoiding placing phi functions in blocks with a single predecessor
    • reduces the number of phi functions but complicates renaming
    • requires processing predecessor first for each such single-predecessor block
  • Minimal for reducible CFGs
    • Some algorithms (e.g. optimized for simplicity) naturally produce minimal form only for reducible CFGs.
    • Applied to non-reducible CFGs, they may generate extra Phi functions
    • There're usually extensions to such algorithms to generate minimal form even for non-reducible CFGs too (but such extensions may add noticeable complexity to otherwise "simple" algorithm)
  • Fully minimal: no superfluous phi functions based only on graph properties of the CFG
  • Prunedness Axis:
  • Pruned: No dead φ functions
    • Minimal form can still phi functions which reference variables which are not actually used in the rest of the program
    • problematic because they artificially extend live ranges of referenced variables.
    • also defines new variables which aren't really live
    • Two obvious way to achieve this:
    • perform live variable analysis prior to SSA construction and use it to avoid placing dead phi functions;
    • run dead code elimination (DCE) pass after the construction (which requires live variable analysis first, this time on SSA form of the program already)
    • pruned SSA construction is more expensive than just the minimal form
    • if we will run DCE pass on anyway, we don't need to be concerned to construct pruned form, as we will get it after the DCE pass "for free".
  • Semi-pruned: an attempt to reduce Φ functions without incurring high cost of computing live variable information
    • compromise between fully pruned and minimal form, sometimes called "Briggs-Minimal" form
    • if a variable is never live upon entry into a basic block, it never needs a Φ function
    • during SSA construction, Φ functions for any "block-local" variables are omitted
  • Not pruned