COMS W4115
Programming Languages and Translators
Lecture 22: Optimization of Basic Blocks
April 16, 2008

Lecture Outline

  1. Review
  2. Instruction selection
  3. Optimization of basic blocks
  4. Order of evaluation

1. Review

2. Instruction Selection

3. Optimization of Basic Blocks

  • DAGs can be used to find local common subexpressions in basic blocks.
  • See Example 8.10, p. 534.
  • Algebra can be used to find additional common subexpressions.
  • See Example 8.11, p. 535.
  • Peephole optimization is done by examining a sliding window of target instructions and whenever possible, replacing an instruction sequence within the peephole by a shorter or faster sequence.
  • Some common peephole optimizations:
    • Elimination of redundant loads and stores
      • Example: A straightforward code generator might produce for
        a = b + c
        d = a + e
        the code sequence
        
            LD  R0, b      // R0 = b
            ADD R0, R0, c  // R0 = R0 + c
            ST  a, R0      // a  = R0
            LD  R0, a      // R0 = a
            ADD R0, R0, e  // R0 = R0 + e
            ST  d, R0      // d  = R0
            
            
        A peephole optimizer can eliminate the fourth instruction which is a redundant load.

    • Flow-of-control optimization
      • Example: A peephole optimizer can eliminate a jump to a jump:
      • 
                goto L1                  goto L2
                   .
                   .         ⇒
                   .
            L1: goto L2              L1: goto L2
            
           
    • Algebraic simplification
      • Example: A peephole optimizer can remove instructions that have no effect such as a = a + 0 or a = a * 1.

    • Reduction in strength
      • Example: A peephole optimizer can replace expensive operations by equivalent cheaper ones such as a ^ 2 by a * a or a * 2 by a + a.

    • Use of machine idioms
      • Example: A peephole optimizer can replace a long sequence of machine instructions by an equivalent single instruction, for example, using a special instruction such as INC i for
      • 
            LD  R0, i      // R0 = i
            ADD R0, R0, 1  // R0 = R0 + 1
            ST  i, R0      // 1  = R0
            
           

4. Order of Evaluation

  • Order of evaluation of the nodes in an expression dag or expression tree can affect the number of registers required to evaluate the expression.
  • Sethi-Ullman algorithm (pp. 567-572) can be used to label the nodes of an expression tree with Ershov numbers to produce machine code with the minimum number of spills (storing the contents of a register to a temporary memory location so the register can be used for another computation).

5. Reading

  • ALSU, Sections 8.5-8.7, 8.10


aho@cs.columbia.edu