Programming Languages and Translators

Lecture 22: Optimization of Basic Blocks

April 16, 2008

- Review
- Instruction selection
- Optimization of basic blocks
- Order of evaluation

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

- 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