Static single-assignment form

In <a href="/facts/Compiler/WNfCDFJe">compiler</a> design, static single assignment form (often abbreviated as SSA form or simply SSA) is a type of <a href="/facts/Intermediate_representation/s0qRrbfh">intermediate representation</a> (IR) where each <a href="/facts/Variable_(computer_science)/VoCKtwml">variable</a> is <a href="/facts/Assignment_(computer_science)/kLevAoyJ">assigned</a> exactly once. SSA is used in most high-quality optimizing compilers for imperative languages, including <a href="/facts/LLVM/nPmcspQN">LLVM</a>, the <a href="/facts/GNU_Compiler_Collection/t07jh01k">GNU Compiler Collection</a>, and many commercial compilers.
There are efficient algorithms for converting programs into SSA form. To convert to SSA, existing variables in the original IR are split into versions, new variables typically indicated by the original name with a subscript, so that every definition gets its own version. Additional statements that assign to new versions of variables may also need to be introduced at the join point of two control flow paths. Converting from SSA form to machine code is also efficient.
SSA makes numerous analyses needed for optimizations easier to perform, such as determining <a href="/facts/Use-define_chain/sJ1haL3j">use-define chains</a>, because when looking at a use of a variable there is only one place where that variable may have received a value. Most optimizations can be adapted to preserve SSA form, so that one optimization can be performed after another with no additional analysis. The SSA based optimizations are usually more efficient and more powerful than their non-SSA form prior equivalents.
In <a href="/facts/Functional_language/cdxqPEIM">functional language</a> compilers, such as those for <a href="/facts/Scheme_(programming_language)/0aGdf3SC">Scheme</a> and <a href="/facts/ML_programming_language/RfwxASRF">ML</a>, <a href="/facts/Continuation-passing_style/lW296oxe">continuation-passing style</a> (CPS) is generally used. SSA is formally equivalent to a well-behaved subset of CPS excluding non-local control flow, so optimizations and transformations formulated in terms of one generally apply to the other. Using CPS as the intermediate representation is more natural for higher-order functions and interprocedural analysis. CPS also easily encodes <a href="/facts/Call/cc/Uc3bTJWC">call/cc</a>, whereas SSA does not.

Static single-assignment form open-in-new

Static single-assignment form