Same Result, Cheaper Program — CFGs and SSA

In one line

Optimization is turning a program into a cheaper program that gives the same result. On the tree, you precompute constants and strip away branches that are already decided, and on the instruction list, you build basic blocks and a control flow graph (CFG) and delete code that has no way in. If you compute dominators on that graph, you can even work out where SSA, the intermediate representation of practical compilers, puts its φ functions.

Why this was needed

People write for readability. They write 60 * 60 * 24 rather than 86400, leave debugging if (false) { … } around, and sometimes leave lines after a return. Module 6's compiler translates these exactly as written, so a 60 * 60 * 24 inside a loop becomes two multiplications every time it runs. If the compiler can precompute it instead, people get a fast program while still writing readable code.

But optimization has one line it must not cross. The result must not change. While trying to "precompute because it is a constant" on 7 / (3 - 3), the compiler must not die or erase the error — that line must raise a division by zero error right there at run time. A good optimizer is one that knows what it must not do before what it can do.

How it works

Constant folding. Walking the tree from the bottom up, you compute operations whose two sides are literals and replace them with a single literal. You keep 64-bit wrapping and division toward 0 exactly as the interpreter does, and expressions that would raise an error when run (division by zero, a negative exponent, an operation with mismatched types) are left unfolded. A folded literal inherits the position of the original operator. false && f() is false as a whole because the right side is not run, and true && e becomes e. An if (true) becomes that branch (kept as a block — so the scope remains), and a while (false) disappears entirely.

Basic blocks and the CFG. If you mark as "leaders" the first instruction, the places jumps go to, and the instruction right after a jump or RETURN in the instruction list, then from a leader to just before the next leader is a basic block. A block is entered only through its first instruction and left only through its last. A CFG records, for each block, the next blocks (the fall-through one and the jump target). Blocks that cannot be reached from the entrance by following the CFG may be deleted — this course's compiler appends CONST 0 · RETURN to the end of every function, so in every function that ends with return, those two instructions are left as unreachable code. After deleting, you must re-measure the offsets of the remaining jumps to the new positions.

fn pos(v) { if (v < 0) { return 0; } return v; }

 B0  0 GET_LOCAL 0         B0 → B1(흘러내림), B2(점프)
     1 CONST 0   ; 0
     2 LT
     3 JUMP_IF_FALSE 2 ; → 6
 B1  4 CONST 0   ; 0       B1 → 없음(RETURN)
     5 RETURN
 B2  6 GET_LOCAL 0         B2 → 없음
     7 RETURN
 B3  8 CONST 0   ; 0       ← 입구에서 닿지 않는다(컴파일러가 붙인 꼬리): 지운다
     9 RETURN

Dominators and SSA. That block d dominates block b means that every path from the entrance to b passes through d. The dominator sets of all blocks are found by repeating "the dominators of b = {b} ∪ (the intersection of the dominators of its predecessor blocks)" until nothing changes. Why do we need this? The intermediate representation of practical compilers (LLVM, GCC) is SSA, a form in which every variable is assigned exactly once. If you turn x = 1; if (c) x = 2; print x; into SSA, you get x1 = 1, x2 = 2, and where the two paths merge, x3 = φ(x1, x2). φ means "choose depending on which path you came by."

      B0: x1 = 1; if c
       /          \
  B1: x2 = 2       |
       \          /
      B2: x3 = φ(x1, x2); print x3        ← B2 는 B1 의 지배 경계

Where to put φ is told by the dominance frontier. The dominance frontier of block b is the blocks you reach by stepping out one step from the places b dominates and first meeting where dominance breaks — that is, where the value that came from b first meets values from other paths. You put φ on the dominance frontier of the blocks where the variable is assigned, and also count a newly placed φ as an assignment and keep widening until it stops growing (the iterated dominance frontier).

What it looks like in the field

• Almost all of -O2 runs on this graph. Constant propagation, dead code elimination, common subexpression elimination, and hoisting out of loops are all computations on SSA and the CFG. This is because in SSA each variable has one definition, so "where did this value come from" is visible at once. When you open clang's LLVM IR in module 10, you will see the phi instruction yourself.
• When optimization exposes bugs. "It works at -O0 but the result differs at -O2" is mostly not a bug in the optimizer but the result of the optimizer believing the program's undefined behavior (such as signed integer overflow) to be "something that does not happen" and deleting it. The promise of not changing the result is kept only for defined behavior.
• Why debugging gets harder. That a variable shows up as "optimized out" in optimized code is because the variable was split into several SSA values and some of them disappeared.

What you will do in the next lab

In opt.py, you build expression folding, program folding (stripping decided branches), basic blocks, the CFG, deleting unreachable blocks (re-measuring jumps), dominators and immediate dominators, dominance frontiers and φ placement, and the pipeline of fold → compile → delete. The grader compares the trees, chunks, and graphs against the reference, and checks with the VM that the optimized program gives the same result while executing fewer instructions.