Static Single Assignment

φ (phi) nodes/instructions that represent a join of all the definitions of a variable if multiple definitions exist in the control-flow graph. Placed at the top of basic blocks.

Each variable is assigned to at most once.

Only flow dependencies exist, however this property doesn't hold for arrays or for pointers.

Efficiently Computing Static Single Assignment Form and the Control Dependence Graph

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, F. Kenneth Zadeck
ACM Transactions on Programming Languages and Systems
1991
Comprehensive overview

Constant propagation with conditional branches

Mark N. Wegman, F. Kenneth Zadeck
ACM Transactions on Programming Languages and Systems
1991
Application of SSA for constant propagation

Global value numbers and redundant computations

B. K. Rosen, M. N. Wegman, F. K. Zadeck
Proceeding of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
1988
Early application of SSA

Detecting equality of variables in programs

B. Alpern, M. N. Wegman, F. K. Zadeck
Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
1988
Early application of SSA with phi_if, phi_entry, phi_exit nodes.

Control-flow extension to SSA

γ (gamma) nodes/instructions that replace φ-nodes and have an extra field for a condition operand.

The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages

Robert A. Ballance, Arthur B. Maccabe, Karl J. Ottenstein
Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation
1990
Gated Single Assignment form is an intermediate representation on the way to calculating the full PDW form.

Efficient building and placing of gating functions

Peng Tu, David Padua
Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation
1995

Construction of Thinned Gated Single-Assignment Form

Paul Havlak
Workshop on Languages and Compilers for Parallel Computing
1993

Pointer analysis extension to SSA

Efficient accommodation of may-alias information in SSA form

Ron Cytron, Reid Gershbein
Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation
1993

Effective Representation of Aliases and Indirect Memory Operations in SSA Form

Fred C. Chow, Sun Chan, Shin-Ming Liu, Raymond Lo, Mark Streich
Proceedings of the 6th International Conference on Compiler Construction
1996

Extended SSA Numbering: Introducing SSA Properties to Language with Multi-level Pointers

Christopher Lapkowski, Laurie J. Hendren
Proceedings of the 7th International Conference on Compiler Construction
1998

The inverse of SSA for uses

Λ (Lambda) nodes/instructions that represent a split of a value for subsequent uses.

Each variable is used at most once.

If used with SSA only flow dependencies will exist with one def-use chain. If not used with SSA then flow and anti dependences may be some what simpler.

SSU has been used for store elimination.

Register promotion by sparse partial redundancy elimination of loads and stores

Raymond Lo, Fred Chow, Robert Kennedy, Shin-Ming Liu, Peng Tu
Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation
1998

Taming the IXP network processor

Lal George and Matthias Blume
Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation
2003

Optimization of Object-Oriented and Concurrent Programs

John Bradley Plevyack
PhD Thesis, University of Illinois at Urbana-Champaign
1996

SSA plus the inverse of SSA for defs

σ (sigma) nodes/instructions that take a variable and give a split that represents all future definitions. Placed at the end of basic blocks

σ nodes/instructions enable forward propagation of data.

The Static Single Information Form

C. Scott Ananian
Master's Thesis, Massachusetts Institute of Technology
September 1999

A framework for virtual register renaming schemes

Jeremy Singer
Submitted to LDTA'04 (ETAPS satellite workshop)
2003

SSA with extensions for arrays

dφ and uφ nodes/instructions to represent definitions to a particular array or uses of a particular array.

Array SSA extends SSA so that it is useful for eliminating redundant loads and stores to arrays.

Array SSA with extensions for strongly typed languages.

Also extensions for bound check elimination.

Heap operands associated with instructions.

Π (Pi) instructions placed following comparisons.

Memory variables are said to exist in disjoint (non-aliasing) Heaps thereby reducing the number of potential dependencies.

Π instructions used to prove that particular use of a variable is within a given range.

ABCD: Eliminating Bounds Checks on Demand

Rastislav Bodik, Rajiv Gupta, and Vivek Sarkar
ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI 2000), Vancouver, British Columbia, Canada, June 17-21, 2000

Array SSA with extensions to specify index ranges

Heap operands to instructions with information on the indexs used

Knowing index information can reduce the number of dependencies.

Copy nodes to produce unique copies of operands.

Variables are linearly named so that they are used at most once.

Scope exceeds SSU?

Linear naming with definitions being unique

SSA with redundant (copying) φ nodes following loops.

Simplifies loop optimisations as definitions of escaping variables need only be added for phi nodes following the loop.