14-01: Intermediate Code

  1. Intermediate language = high-level assembly:
    • Uses register names, but has an unlimited number;
    • Uses control structures like assembly language;
    • Uses opcodes but some are higher level.
  2. Three-address code:
    • x := y op z;
    • x := op y;
    • y and z are registers or constants.

14-02: Optimization Overview

  1. A basic block is a maximal sequence of instructions with:
    • no labels(except at the first instruction);
    • no jumps(except in the last instruction).
  2. A control-flow graph is a direct graph with
    • Basic blocks as nodes;
    • An edge from block A to block B if the execution can pass from the last instruction in A to the first instruction in B.
  3. Optimizations:
    • Local: apply to a basic block in isolation;
    • Global: apply to a CFG in isolation;
    • Inter-procedural: apply across method boundaries.

14-03: Local Optimization

  1. Constant folding;
  2. Eliminate unreachable basic blocks;
  3. Common subexpressions elimination (using SSA);
  4. Copy/Constant propagation (using SSA).
  5. Optimizing compilers repeat optimizations until no improvement is possible.

14-04: Peephole Optimization

  1. Peephole optimization is effective for improving assembly code:
    • The “peephole” is a short sequence of (usually contiguous) instructions;
    • The optimizer replaces the sequence with another equivalent one(but faster).

15-02: Constant Propagation

  1. To replace a use of x by a constant k we must know:
    • On every path to use of x, the last assignment to x is x := k.
  2. Rules:
    • If C(pi, x, out) = T for any i, then C(s, x, in) = T, pi - predecessors of s;
    • If C(pi, x, out) = c & C(pj, x, out) = d & d != c, then C(s, x, in) = T;
    • If C(pi, x, out) = c or ⊥ for all i, then C(s, x, in) = c;
    • If C(pi, x, out) = ⊥ for all i, then C(s, x, in) = ⊥;
    • C(s, x, out) = ⊥ if C(s, x, in) = ⊥;
    • C(x := c, x, out) = c if c is a constant;
    • C(x := f(…), x, out) = T;
    • C(y := …, x, out) = C(y := …, x, in) if x != y.
  3. Algorithm:
    • For every entry s to the program, set C(s, x, in) = T;
    • Set C(s, x, in) = C(s, x, out) = ⊥ everywhere else;
    • Repeat until all points satisfy 1-8:
    1. Pick s not satisfying 1-8 and update using the appropriate rule.

15-03: Analysis of Loops

⊥ is necessary for cycles in Constant Propagation.

15-04: Orderings

  1. T is the greatest value, ⊥ is the least;
    • All constants are in between and incompatible.
  2. Let lub be the least-upper bound in this ordering;
  3. Rules 1-4 can be written using lub:
    • C(s, x, in) = lub{ C(p, x, out) | p is a predecessor of s }.
  4. Constant Propagation algorithm is linear in program size.

15-05: Liveness Analysis

  1. A variable x is live at statement s if:
    • There exists a statement s’ that uses x;
    • There is a path from s to s’;
    • That path has no intervening assignment to x.
  2. Rules:
    • L(p, x, out) = v { L(s, x, in) | s a successor of p}
    • L(s, x, in) = true if s refers to x on the rhs;
    • L(x := e, x, in) = false if e does not refer to x;
    • L(s, x, in) = L(s, x, out) if s does not refer to x.
  3. Algorithm:
    • Let all L(…) = false initially;
    • Repeat until all statements s satisfy rules 1-4:
    1. Pick s where one of 1-4 does not hold and update using the appropriate rule.
  4. Constant Propagation is a forward analysis: information is pushed from inputs to outputs;
  5. Liveness is a backward analysis: information is pushed from outputs back towards inputs.