smart compilers

[Andrew Klossner]

} It occurs to me that there are two ways to look at optimizers:
}
}	1) That an optimizer optimizes, not the language code, but ASSEMBLER
}	   code, and hence does not need to follow the language standard;
}
}	2) That an optimizer must follow the language standard exactly,
}	   and hence should optimize the language code itself.
}
} If you accept (1), as every optimizer I've seen is designed to do, you
} are likely to see an optimizer that will occasionally fail.  If (2),
} there is little optimization possible, especially in a language like
} Pascal where you can't manipulate the machine directly.

This shows a lack of familiarity with the computer science behind
optimization.

Systems which improve the assembler output from a compiler are commonly
called "peephole" optimizers, because they never look at more than a
very small part of the program (they look at the program through a
"peephole").  Unix is the only system I've encountered in which the
standard language optimizer is just an assembly code improver.

The more traditional (read "mainframe") optimization strategy is to
convert the entire program into an intermediate form which preserves
the meaning of the code and yet is amenable to rearrangement into a
more efficient program with equivalent meaning.  Once this is done, the
intermediate code is translated into assembler or machine code.
So-called "global" optimizers examine the entire program, using
"data-flow" algorithms which gather information by making several passes
over the intermediate code; this information is then used to make
decisions about how the program can be improved without changing its
meaning.

Pascal programs are particularly amenable to this sort of optimization.
The standard example is the assignment "a[i]:=a[i]+1".  This cannot be
expressed any more efficiently in Pascal, but in a good intermediate
code the translation can be arranged to reflect the fact that
computation of the address of a[i] need only be done once, and that an
"increment word in memory" instruction can be used.

} Let's face it, guys -- placing any limitations (i.e. standards) on a
} programming language is going to make an executing program in that language
} slower.  Optimizing is often simply ignoring some of the standards and
} removing their effects from the generated code.

Not at all.  An implementor who claims that she had to revise the
language in order to write an optimizer is being inexcusably lazy.

Despite the recent discussions about well-known optimizers breaking
programs, such behavior is considered incorrect by workers in the
field.  A good and readable treatment of optimization is Aho and
Ullman's "Principles of Compiler Design", which has become the standard
introductory compiler text.  The chapters on optimization emphasize
that an optimization which changes the semantics of the program is not
valid.

  -- Andrew Klossner   (decvax!tektronix!orca!andrew)       [UUCP]
                       (orca!andrew.tektronix at csnet-relay)  [ARPA]