Optimizations
MLRISC assumes that all high level optimizations (target
independent) have already been performed. This includes things like
inlining, array dependence analysis, and array bounds check
elimination. The target dependent optimizations that remain include
register allocation, scheduling and traditional optimizations to
support scheduling.
Register allocation
MLRISC includes a state-of-the-art graph-coloring based register
allocator that has an aggressive algorithm for copy-propagation. The
latter guarantees to eliminate copy instructions without introducing
spills.
Spills in the register allocator are under the control of the
client via call-backs to the front end. Where to spill registers and
the associated information that must be maintained is client specific
and varies with the compiler.
Scheduling
Several algorithms for acyclic global scheduling are provided. These
include:
- Superblock,
- a variant of Bernstein/Rodeh, and
- Percolation based scheduling.
These algorithms tend to be quite complex and require a large number
of support data structures and analysis. These include data structures
such as:
- dominator/post dominator trees,
- control dependency graphs, and
- data dependency graphs.
Support analysis and optimization include:
- constant propagation,
- global value numbering,
- loop invariant hoisting,
- incremental liveness,
- partial redundancy elimination, and
- parameterized form of abstract interpretation.
Lal George
Last modified: Tue Apr 28 15:23:04 EDT 1998