HSSA: Aliases in SSA

Massimiliano Mantione

Novell

Executive summary

• Representing aliases in SSA form
• Representing also indirect operations
• Perform all SSA based optimizations uniformly on local and indirect variables
• This talk is not about detecting and analyzing aliases!

Detailed Summary

• Model the effect of aliasing on scalar variables
• Reduce the overhead of the above representation
• Represent indirect operations in SSA as "virtual variables"
• Apply GVN to all of the above (obtaining Hashed SSA, or HSSA)

When do we have aliasing?

• When storage locations partially overlap
• When a local variable is referred by a pointer used in an indirect operation
• When the address of a local variable is passed to a function
• When a variable is not local, and it can be accessed by other functions

Modeling aliasing effects

• Definitions can be "MustDef" or "MayDef" (χ operator)
• Uses can be "MustUse" or "MayUse"(μ operator)
• The χ argument is the assigned variable itself (to make liveness work correctly)
• χ and μ operators must be inserted in the code where appropriate...
• Example of φ, χ and μ placement:
  • Original: i = 2; if (j) {f();} else {*p = 3;} return i;
  • Transformed: i₁ = 2; if (j₁) {μ(i₁); f();} else {*p = 3; i₂ = χ(i₁);} i₃ = &phi(i₁,i₂); return i₃;

SSA with "zero versioning"

• χ operations can produce many useless variable versions
• ...which in turn can introduce useless φ variables...
• The idea is to factor all these useless versions together (zero version)

A definition of "real occurrence"

• A "real occurrence" is an occurrence of a variable in the original program
• Therefore, φ, μ and χ arguments are not real occurrences
• The idea is to give version "zero" to all versions that have no real occurrences and no known value (generated by a χ operator)
• The rationale is that since they do not directly appear in the code, and their value is unknown, distinguishing them is almost pointless

"Zero version" variables

• A variable has version zero if it has no real occurrence and its value comes from a χ with zero or more intervening φ's.
• Alternatively, we give a recursive definition:
  • The left side of a χ has version zero if it has no real occurrence
  • If the operand of a φ has zero version, if the φ result has no real occurrence it also has version zero

Detecting zero versions, part one

• Each variable version has a "HasRealOcc" flag, initially false (and set to true when we meet a real occurrence)
• Each program variable has a "NonZeroPhiList", initially empty
• For each version of each variable:
  • if HasRealOcc is false and the version is defined by a χ, set version to zero
  • if HasRealOcc is false and the version is defined by a φ, examine the φ operands:
    • if all of them have HasRealOcc true, set the φ HasRealOcc to true
    • if one or more has version zero, set φ version to zero
    • otherwise, add φ to NonZeroPhiList of its variable

Detecting zero versions, part two

• For each program variable, iterate until NonZeroPhiList no longer changes, and for each φ in NonZeroPhiList, examine the φ operands:
  • if all of them have HasRealOcc true, set the φ HasRealOcc to true
  • if one or more has version zero, set φ version to zero
  • if any of the two above conditions is met, remove the φ from the list
• The upper bound of this final iteration is the longest chain of contiguous φ assignments in the program

Considerations on zero versions

• Since variables with zero versions have no known value, not being able to distinguish them does not affect optimizations that operate on values
• When performing DEADCE, zero versions must be assumed live
• They can only be used in a μ and defined by a χ, however it is possible that if the μ is eliminated the real occurrence used in the χ becomes dead but we cannot detect it

Indirect memory operations in SSA

• Examples: *p, *(p+1), **p, p->next, a[i]
• Loads and stores are represented in the obvious way (dereference and assignment operators)
• We call the referred locations "indirect variables"
• We could think about renaming indirect variables (like real ones in SSA): they would get a new number also if the underlying expression changes
• Example of indirect operations:
  • Original: i = *p; p = p + 1; j = *p;
  • Renamed: i₁ = (*p₁)₁; p₂ = p₁ + 1; j₁ = (*p₂)₂;

The problems with indirect variables

• The straightforward way of renaming indirect variables would be to apply the SSA renaming pass multiple times (one for each level of indirection)
• This is not practical (even if alias analysis could be improved after each pass)
• Also, we would need a sound way of dealing with aliasing (placing μ and χ operators)

Introducing "virtual variables"

• Definition: the virtual variable of an indirect variable is an imaginary scalar variable that has identical aliasing characteristics as the indirect variable
• It represent the location (or better the set of potential locations) referred by the indirect memory operations in an indirect variable
• Contrast this with the indirect operation, which is the actual code that is emitted by the compiler

Handling virtual variables: aliasing

• We perform alias analysis (μ and χ placement) on virtual variables
• They are handled just like scalar variables (in the same passes)
• Alias analysis can take into account the address expression to deduce that two indirect variables do not alias each other
• Each occurrence of an indirect variable is annotated with μ and χ of its virtual variable

Handling virtual variables: SSA

• SSA renaming on virtual variables works as usual, and in the same pass as with scalar variables
• Use-def relationships of virtual variables now represent use-def relationships of indirect variables
• If we wanted to version indirect variables, we would use the version numbers of their virtual variable (unless the address expression itself has changed version!)

GVN and indirect memory operations

• In practice we will not renumber indirect variables
• Instead, we will give GVN table entries to them (handling them uniformly with scalar variables)
• Virtual variables are just an aid to apply aliasing effects, be aware of liveness and perform SSA renaming
• The resulting IR form (HSSA) has five kinds of nodes:
  • leaf nodes (constants, addresses and variables)
  • operands
  • indirect variables ("ivar"), which are half operand and half variable nodes

Building HSSA (part 1: SSA form)

• Perform alias analysis and assign virtual variables to indirect variables
• Insert μ and χ operands for scalar and virtual variables
• Insert φ operands (considering both regular and χ store operations)
• Perform SSA renaming on all scalar and virtual variables

Building HSSA (part 2: zero versions)

• In one single pass:
  • perform DEADCE (also on χ and φ stores)
  • perform steps 1 and 2 of the zero version detection (up to setting HasRealOcc for all variable versions)
• Perform the remaining passes of the zero version algorithm

Building HSSA (part 3a: applying GVN)

• Generate a unique value number and var node for each scalar and virtual variable version that is still live
• Perform a pre-order traversal of the dominator tree, applying GVN to the whole code
• expressions are processed bottom up, reusing existing expression nodes and using variable nodes of the appropriate SSA version (the current one in the DT traversal)

Building HSSA (part 3b: ivar equality)

• Two ivar nodes match if these conditions are both true:
  • their address expressions have the same value number, and
  • their virtual variables have the same versions, or are separated by definitions that do not alias the ivar (possible to verify because of the DT traversal order)

Building HSSA (part 3c: unreal ops.)

• The left side of each assignment (direct and indirect, real, φ and χ) is updated to point to its var or ivar node (which will point back to the defining statement)
• Also all φ, μ and χ operands are be updated to point to the corresponding GVN table entry

Using HSSA

• HSSA (once built) is memory efficient because expressions are shared among use points (they are represented as HSSA table nodes)
• Indirect operation (ivar) nodes are both variariables and expressions, and benefit from the optimizations applied to both kinds of nodes
• Optimizations conceived to be applied on scalar variables work "out of the box" on indirect locations
• Particularly, it is relatively easy to implement "register promotion" (the paper authors call it "indirect removal")
• Of course the effectiveness of most of the above depends on the quality of alias analysis...

HSSA in the real world

• It has been used effectively in SGI compilers, first for MIPS and then for IA64 CPUs
• It is still present in the Intel Open64 Compiler Infrastructure
• We tried to introduce it in the Mono JIT, and had a prototype working, but we gave up:
  • operating on a tree-based IR the HSSA construction code was complex and slow (way too slow for a JIT)
  • our register allocator could not handle the added register pressure and spilled all over the place, making the optimized code often slower than the original one (and with architecture dependent patterns, depending on the number of available registers)
• I still "dream" of an HSSA based register allocator in the Mono JIT...

Questions?

Thank you all!

Things I did using SSA