# 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

• Issues in code generation
• The target machine
• Basic blocks and flow graphs

## 2. Instruction Selection

• Issues
• Level of the IR
• Nature of the instruction set architecture
• Desired quality of the generated code
• Target machine
• n general-purpose registers
• Instructions: load, store, compute, jump, conditional jump
• integer indexed by a register
• immediate constant
• Example 1: for `x = y + z` we can generate
• ``````
LD  R0, y      // R0 = y
ADD R0, R0, z  // R0 = R0 + z
ST  x, R0      // x  = R0

Example 2: for b = a[i] we can generate

LD  R1, i      // R1 = i
MUL R1, R1, 8  // R0 = R0 + 8
LD  R2, a(R1)  // R2 = contents(a + contents(R1))
ST  b, R2      // x  = R2

Example 3: for *p = y we can generate

LD  R1, p      // R1 = p
LD  R2, y      // R2 = y
ST  0(R1), R2  // contents(0 + contents(R1)) = R2

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