- 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!

- 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 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

- 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*_{1}= 2; if (j_{1}) {**μ(i**f();} else {*p_{1});_{}= 3;**i**}_{2}= χ(i_{1});**i**return i_{3}= &phi(i_{1},i_{2});_{3};

- Original:

- χ 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 "
*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

- 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

- 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

- if all of them have

- if

- 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

- if all of them have
- The upper bound of this final iteration is the longest chain of contiguous φ assignments in the program

- 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

- 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*_{1}= (*p_{1}); p_{1}_{2}= p_{1}+ 1; j_{1}= (*p_{2});_{2}

- Original:

- 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)

- 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

- 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

- 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!)

- 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

- 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

- 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

- 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)

- 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)

- 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

- 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...

- 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...

Things I did using SSA

- Array Bounds Check Removal (and predication in general)
- Partial Redundancy Elimination (using SSAPRE)
- An attemp at HSSA
- An attempt at building SSA
and doing a register allocator__fast__