> For the complete documentation index, see [llms.txt](https://theonekevin.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://theonekevin.gitbook.io/notes/compiler-optimization.md).

# Compiler Optimization

### Motivation for SSA Form

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

```c
// 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>