Optimization

This lecture takes 1.5 class periods.


Optimization

It may be possible to restructure the parse tree to reduce its size or to present a parse to the code generator from which the code generator is able to produce more efficient code. Some optimizations that can be applied to the parse tree are illustrated using source code rather than the parse tree.

We do not illustrate an optimizer in the parser for Simpile.

Peephole Optimization

Following code generation there are further optimizations that are possible. The code is scanned a few instructions at a time (the peephole) looking for combinations of instructions that may be replaced by more efficient combinations. Typical optimizations performed by a peephole optimizer include copy propagation across register loads and stores, strength reduction in arithmetic operators and memory access, and branch chaining.

We do not illustrate a peephole optimizer for Simp.

x := x + 1         ld x       ld x
                   inc        inc
                   store x    dup
y := x + 3         ld x   
                   ld 3       ld 3
                   add        add
                   store y    store y
x := x + z         ld x
                   ld z       ld z
                   add        add
                   store x    store x

Further Reading

For information on compiler construction using Lex and Yacc see\cite{SchFre85}. Pratt \cite{Pratt84} emphasizes virtual machines.