Re: Smallest Optimizer

<SAND_DUANE@tandem.com> wrote:
>I'm curious about
>the range of observed sizes for the beasts we call optimizing
>compilers, both the smallest and the largest.


I have just finished my Ph.D. thesis on how to simplify optimizing compilers
to a large extent. As part of my research, I have implemented a prototypical
optimizing compiler for a large subset of the programming language Oberon-2.
Here is some data on it.


The compiler is written in Oberon-2, and compiles for the PowerPC architecture.
It consists of 18 modules, totalling 10615 source lines, or 414 kBytes source,
and 212 kBytes of PowerPC object code.


The whole compiler is based on a framework we call guarded single-assignment
form, which you can consider as a combination of gated single-assignment form
and a variant of control-dependence graphs for structured programming
languages. It tightly integrates data-flow and control-flow.


The compiler performs the following optimizations:


- Inlining
- Constant Propagation, Unreachable Code Elimination
- Copy Propagation, Value Numbering
- Dead Code Elimination
- Reassociation, Loop Invariant Code Motion, Strength Reduction
- Peephole Optimizations
- Region Scheduling
- Register Allocation by Hierarchical Graph Coloring


The code quality achieved is comparable to the one of GCC. The compilation
time is about eight times faster than GCC, namely about 1000 lines/sec on
a 66 MHz PowerPC 601 based IBM RS/6000 Model 250.


The savings are due to the novel intermediate program representation, which
is only applicable to programs in structured programming languages (i.e.
without unstructured control-flow using GOTO-statements), and which can be
generated directly in one pass while parsing the source program. The clean
semantics of the representation allowed to simplify many of the optimization
algorithms, and allowed to keep the whole compiler simple and fast.


The thesis will eventually become available in electronic form. People
interested in it may send me email, so that I notify them once it is available.




Marc-Michael Brandis
Institute for Computer Systems
ETH-Zentrum (Swiss Federal Institute of Technology)
CH-8092 Zurich, Switzerland
email: brandis@inf.ethz.ch
--

Return to the comp.compilers page.
Search the comp.compilers archives again.