Compiler Optimization

Motivation for SSA Form

Many optimizations can be simplified by using SSA form. Consider this counterexample with the presented algorithms.

// 1.
x = 10;
if(...) {
// 2.
    x = 20;
    y = x;
} else {
// 3.
    y = x;
}
// 4.

1. Constant Folding

Algorithm:

1. Create a map $M: V\to \text{int|undefined}$ where $V$ is a variable. Initialize to undefined.

2. For each statement, if it is of form:

   • x = c set M[x] = c

   • x = y set M[x] = M[y]

     • Replace y with M[y] if defined

   • v = Op x y set M[v] = Op(M[x], M[y]) where Op(...) may return undefined

     • Replace Op x y with Op(M[x], M[y]) if defined

     • Otherwise replace x with M[x] if defined and y with M[y] if defined

This only works with SSA. Consider the above snippet as the counterexample.

2. Copy Propagation

Algorithm:

1. Create a map $M:V\to V$. Initialize M[x]=x

2. For each statement, if it is of form:

   • x = y set M[x] = M[y]

   • v = Op x y replace with v = Op M[x] M[y]

Again, this only works with SSA.

3. Dead Code Elimination

Algorithm:

1. https://sites.cs.ucsb.edu/~yufeiding/cs293s/slides/293S_07_SSA_dead.pdf