COMS W4115
Programming Languages and Translators
Lecture 22: Optimization of Basic Blocks
April 16, 2008
Lecture Outline
- Review
- Instruction selection
- Optimization of basic blocks
- 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
- Various addressing modes:
- indexed address
- integer indexed by a register
- indirect addressing
- 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