SSA bibliography

plenty of information about SSA

out of print

The most important paper in the field. Comprehensive yet readable. Note there was an earlier version at POPL 89.

A fascinating account of constant propagation - different approaches. Clear application of SSA to good advantage.

early paper from SSA authors

early paper from SSA authors

describes semi-pruned SSA form, as used in Machine SUIF. Cheaper to compute than fully pruned form yet nearly as small.

pessimistic construction of SSA - not v efficient idea but a really neat way of presenting it

syntax directed SSA construction for Oberon, a high-level very well-structured language

Whereas Cytron et al.’s algorithm is an eager forwards approach, this new approach is lazy and backwards i.e. it searches backwards from uses to find reaching definitions, inserting φ functions at control flow join points along the way. Memoization avoids repeated lookups, on-the-fly optimization simplifies generated IR. Implemented in LLVM

early inspiration for SSA. Discusses variable names, data dependence, control flow, graphical notation, etc.

the classic paper on how to compute dominators quickly.

***The date is wrong on the top of the paper.*** In this paper an "optimal" algorithm is given to compute simple join birthpoints. An earlier version appeared in POPL

global value graph (pre-SSA IR) for linear time constant propagation

linear algorithm is given to perform constant propagation in time linear in the size of the use-definition chains. Updated version of Reif77 and Reif82

a linear φ-function placement algm

rather complicated expansion of above tech report. Theoretical framework for φ-fn placement algorithms, general enough to cope with most other placement algms!

title says it all - although this one doesn't go as fast as Bilardi and Pingali, according to BP's paper (a personal communication). However, this is the one that Microsoft use for their Marmot compiler - so it must be ok... uses data structures known as DJ-graphs.

precomputes merge sets for each CFG node. The merge set is the set of locations where phi-fns will be needed for vars defined in n. Do not need to recompute if phi-fns are later placed in n. Apparently good for dense variable definitions, demonstrated on SPEC CPU 2000.

extends SSA form to handle arrays more elegantly

extends SSA to handle arrays and objects, in Java-like langs. Builds upon the original Array SSA - by splitting classes up into heap-arrays of appropriate fields, and indexing into these heap arrays by object references (quite clever!) Then just uses standard Array SSA transformation. three kinds of phi nodes - standard, then array defn phi, then array use phi. Rename arrays each time we do a lookup (cf SSU). Uses global value numbering instead of points-to analysis to determine when object references are same/different. Analysis enables scalar replacement - remove redundant loads, then redundant stores. Comments that transformation to SSA leads to flow-sensitivity property. Actually implemented in IBM Jalapeno JIT compiler.

Introduces the concept of dynamic single assignment form (DSA).

reviews array SSA, goes onto develop dynamic single assignment, which is similar to linear naming, only seems to be for arrays. Make it work by adding extra dimensions to arrays to cope with repeated assignments to same elements (probably due to loops)

also available as a HP Labs technical report. Describes DSA and expanded virtual registers, the cloning support nec for DSA. Basically converts each scalar into an array

gives some motivation for DSA in terms of memory hierarchy design for embedded systems. Then gives two diff methods for constructing DSA, one from SSA, one from CFG. Plenty of discussion, no results and not much analysis.

really simple

rather complicated!

SSA for pointers. No phi nodes, instead it just does global value numbering for scalar variables, and for single-indirect pointers. A ptr has two global value numbers, one for the var itself, and one for the location it points to. This allows us to detect symbolic equality, and to make assumptions about definition sets. No explicit phi nodes, they aren't deemed necessary.

Claims that SSA turns flow-insensitive analysis into flow-sensitive analysis. Slightly suspect paper. But interesting claim, even if not backed up formally.

a little like SSI, if you factor full-path-predicates into the variable names. Does SSA-like scheme for predicated ISAs, such as IA64.

constant propagation analysis on a value graph, relies on a predicated form of SSA

quite involved, but enables data speculation in SSA form, with notion of likeliness of operations

Does profiling to identify hot paths through a CFG, then introduces the tau-function, which allows us to discard variable definitions from non-hot paths, enabling speculative optimizations like constant propagation. Shows how speculative constant propagation works on real programs, with a hit-rate metric that shows how often speculation is correct.

early attempt at dealing with simple kind of parallelism, introduces extra pseudo-assignment for parallel merge points

caters for more complicated parallel programs, introduces an extra pseudo-assignment

more complicated still. Extends CSSA with support for mutexes

clearest description of concurrent CFGs and CSSA. With three diff kinds of pseudo-assignment now.

similar to SSI, has phi functions, and also pi functions to rename at conditional branches and after array bounds checks

reference chaining - a generalization of SSA. For forwards or backwards data flow problems, but not both. Talks a lot about factored use and def chains. A student of Michael Wolfe's

introduces concept of factored use-def chains, as a form of SSA

haven't actually read this. It uses a variant of SSA to discover properties of variables. Mentions FUD chains.

simple techniques so machine code can be properly represented as SSA, and optimised using SSA algms

interpretable SSA. Simple techniques to interpret phi fns, single-assignment arrays, etc. V similar to SafeTSA

describes interprocedural SSA - similar to supergraph. For program visualization and slicing, in order to do user-assisted parallelization in an interactive manner

describes the concepts and implementation of the interprocedural SSA framework as implemented in Bauhaus. Can be used together with many different pointer analyses.

First half is nice and hacky - all about why SSI is needed, contrasting it with SSA, etc., also a (slightly strange) way to construct it using SESE regions. Second half is wierd and wonderful theory, whcich hopefully we can largely ignore - gives an executable semantics to some variant of the standard SSI form.

Corrects mistakes in previous definitions of SSI. Considers properties of live ranges in SSI programs.

hard-going, but just a brief mention of the merits of SSI in the conclusions

fascinating stuff, quite simple to read. Quite early on they mention that SSI might be a possible alternative intermediate form, just a footnote

does debugging using model checking, for Java programs. Uses SSI in order to construct the model. Cites me as well as Ananian for SSI construction!

uses SSI for some kind of ECAD-like hardware synthesis

presents static single use form, complete with lambda (inverse phi) nodes - uses it to do PRE for STORE instrs

A rather more informal SSU presentation - for register allocation in IXP processors - with no reference to other SSU work

defines static single use - BUT - really SSI - only rename at control flow split points, uses ψ-nodes instead of σ-nodes.

transforming programs so that they have linear names - a linear name is only used once (PhD thesis).

introduction to use-once variables. Argues that they are needed in mainstream programming languages. Gives some examples from LISP world.

shows how to do PRE using SSA - derives factored redundancy graph from SSA and does forwards and backwards data flow analysis on this. Shows how to use SSA to do analysis/optimization for expressions, not just for vars. Also defines an interesting density function to measure sparseness.

a different approach to SSA-based PRE. Uses value numbering to identify redundant computation, rather than a more syntactic measure. This approach has been implemented in Jikes RVM and GCC.

combines WZ91 sparse conditional constant propagation with type propagation for concrete types in Java programs. A poorly written, short, rather dodgy paper, but still quite an interesting find

uses SSA to undo register colouring, then infers types and transforms RTL back into C. All thoughts, and no real implementations here...

a variant of SSA that purports to be useful for symbolic analysis and interpretation. Uses a data flow like Value Flow Graph for optimization. Lack of detail for construction algorithm

SSA for model checking. Using the dominance properties of SSA enables efficient generation of verification conditions

liveness analysis based directly on SSA, rather than specialized data flow analysis

describes design and implementation of Marmot - uses SSA, buth as some criticism for how hard it is to do transformations efficiently in SSA.

Just a website with a link to a white paper, no real detail here. However it does mention that the HotSpot server VM uses an SSA-based IR.

overview document (rather outdated!) for SUIF v1

general introduction to machine suif

SSA docs for Machine SUIF

PDW - fascinating data flow stuff - but switch nodes are just like SSI sigma nodes.

reintroduces gated single assignment, shows how to compute gating fns quicker than previously

TGSA is a simplified version of GSA

SafeTSA is a replacement for Java bytecode - a VM-based intermediate form that encodes implicit type-safety. (effectively diff stacks for diff types)

another SafeTSA paper, integrating SafeTSA into Jikes RVM via a custom classloader and comparing performance with Java bytecode on simple benchmarks

introduces a low-level IR based on SSA that encodes type info for type-safe compiler optimizations

introduces a type system that works like SSA. Effectively type inference is SSA transformation. So we can encode SSA as type-based info, rather than in variable renaming.

handles register spilling and rematerialization. Deals with a new algorithm for repairing SSA.

uses some kind of boolean optimization techniques (maths!) to generate near-optimal instruction sequences for DSP programs in SSA form.

an interesting read. Do register allocation directly in SSA, rather than translate out of SSA. Some graph theory here.

shows how liveness analysis is O(1) for SSI programs, interesting graph-theoretic properties of SSI-based register interference graphs

uses SSA for hardware synthesis, shows how tweaks in φ-function placement affects hardware efficiency

Extends work of leung99, for reducing number of moves after eliminating phi-functions when converting out of SSA. Variable pinning coalescing technique.

Despite work of Hack, showing that SSA programs are colourable in linear time, register allocation is still NP-complete

destroy SSA after register allocation, without increasing the number of spill variables

A new coalescing algorithm for reg coloring after SSA-based register allocation

fun paper on register allocation for architectures like x86 with overlapping registers of different sizes. Does ultimate live range splitting, adds pseudo-assignments for live variables between every individual instruction. This is known as the elementary form.

SSA-based register allocator reduces dynamic number of spill instructions in benchmark code, in relation to linear scan and graph coloring allocators

new algorithm for translating out of SSA, efficient enough to be implemented in JIT compilers

another out-of-SSA algorithm, replacing phi-functions with copies where appropriate. Copies are eliminated with coalescing.

Comparison of several classical out-of-SSA algorithms, Briggs, etc.

interesting approach to embedding SSA info directly in standard Java bytecode, using local variables as SSA registers, neat encoding of phi functions and dominator tree.