šŸ“–
Notes
  • Typed Lua
    • Typed Lua (Old)
  • Fast Userspace Kernel (FUsK)
  • Compiler Optimization
  • RISC-V Merged CmpBr
  • School Projects
    • cc3k
    • wlp4cc
  • Microkernel Design
  • cxkernel
Powered by GitBook
On this page

Was this helpful?

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→int|undefinedM: V\to \text{int|undefined}M:V→int|undefined where VVV 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→VM:V\to VM:V→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:

PreviousFast Userspace Kernel (FUsK)NextRISC-V Merged CmpBr

Last updated 3 years ago

Was this helpful?

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