Smallest Optimizer

Mammals and birds and reptiles and bugs come in nearly all kinds of
sizes, within some physical or ecological limits. I'm curious about
the range of observed sizes for the beasts we call optimizing
compilers, both the smallest and the largest. Please post to this
newsgroup your sightings of the amazing and the weird, dead or alive.


If the critter you report on requires other unusual organisms (like
code-generator generators, abstract machine translators, or unusual
languages) to reproduce itself, please include the sizes of those
hosts in its lifecycle total biomass.


To distinguish these critters from lower forms of compiler life,
let's say that the main group shares the characteristics of
    o Compiles from an imperative language with arrays, etc;
    o Generates code for a real register machine;
    o Uses those registers in a nontrivial, nonlocal way;
    o Moves or removes work across an entire routine, not just
          within an unconditional sequence of statements; and
    o Does something interesting with loops.


Examples of smallish critters of this kind are Michael Powell's
Modula-2 compiler and Jack Davidson and Manual Benitez's vpcc/vpo
C compiler. Bigger examples are GNU C, the Mips Ucode system, and
Stanford's SUIF system. Fraser and Hanson's tiny "lcc" ANSI C compiler
is excluded because it mostly does only intra-block optimizations.


Ken Thompson's tiny Plan 9 C compiler is barely included. It is
interestingly weird in how it blends the designs and goals for fast
dumb compilers and optimizing compilers. It does classic inter-block
flow optimizations for simple variable references but not for
arbitrary redundant expressions. It trusts the programmer to not
write redundant source code.


Todd Proebsting was recently asking about very fast compilers.
Optimizers could be fast either by doing as little as possible
(maybe giving a small optimizer) or by having a clever and complex
implementation of its methods (maybe giving a larger optimizer).
Optimizers could be small by using simple but inefficient
implementations of its methods. Optimizers could be large because
they cover so many separate optimizations, or they could be large
merely because they were coded by many people.


Where does your critter fit in all this?
--

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