in defence of C

[Henry Spencer]

This is an attempt at a rebuttal to Dan Klein's diatribe entitled
"C doesn't optimize, it neatens".  [Sound of afterburners in background]

For openers, if one uses "optimize" in the strictest sense, there are
no optimizing compilers (not even Bliss compilers qualify) and probably
never will be any.  If it is used in the normal compiler sense of "improve",
then many of the things that common C compilers do can quite legitimately
be called optimization.  It is true that they don't do as much of it as
the Bliss compilers, but then few compilers do.  The Bliss compilers are
better called "super-optimizing" rather than just "optimizing".

Second, several people have already pointed out that one must separate
compiler and language.  I am sure that if you looked hard, you could
find a Bliss compiler that didn't do heavy optimization.  (I am fairly
sure that the original Bliss-10 compiler produced unremarkable code.)
Similarly, if you look hard you can find C compilers that do much more
optimization than PCC.

There is one respect in which the language itself is guilty of being
a bit restrictive about optimization.  The language taken by the Bliss
compiler I know -- the original Bliss-11 super-optimizer -- had quite
elaborate facilities for inserting notations in the program that told
the compiler "something funny going on here, suppress optimization X".
(Well, it wasn't quite that specific, but almost.)  C has never had
such a facility, and this means that C compilers must tread carefully
lest they mis-compile code dealing with such eldritch beasties as
device registers and memory mappers.  It is not always easy for the
C compiler to determine whether specific optimizations are safe.

Going on to Dan's specific complaints...

Bliss is smarter about pushing arguments that happen to be adjacent
to each other in memory.  Big deal.  There are a lot of such things
in the Bliss compilers:  "microsecond per month" optimizations, which
might -- over the total lifetime of the compiler -- save almost enough
CPU cycles to justify the extra complexity and implementation effort.

Bliss does a direct return rather than branching to common return
code as C does.  Guilty, unless there is non-trivial common code
involved (which there isn't in Dan's example).

C is not smart enough to extract invariant code from loops.  True,
but some of Dan's comments are incorrect.  The problem is a little
deeper than it seems, because C semantics dictate that the loop must
act as if all parts of the termination test were executed every time.
This includes side effects, which can be very subtle in the presence
of things like device registers.  It is *not* sufficient to note that
the loop doesn't do anything to variable "a"; it is also necessary to
confirm that "a" is an ordinary variable rather than a pointer to
something that might be heaven-knows-where, *and* that the address of
"a" is not being passed to some other routine that might do something
sinister with delayed effects.

Bliss is smart enough to use a complex loop-control instruction, which
C doesn't notice.  Guilty.

Dan's comments on use of registers rather than stack locations are
confused.  C is using a register temporary just like Bliss is; the
difference is that the control variable is on the stack rather than
in a register.  And *that* is because it wasn't declared "register".
Making non-register variables into register variables is possible,
but requires scanning the entire scope to determine that nothing
ever takes their address.  It can be done, but it's not quite as
simple as Dan makes it sound.

C is accessing the variable using a non-zero offset from fp, while
Bliss is smart enough to notice that it can do it with a zero offset
from sp.  Probably guilty, although the VAX C calling sequence should
be studied carefully to determine whether it is pulling the standard
C trick of keeping an empty temporary at the top of the stack.  If it
is, then this optimization is incorrect without deeper thought about
the implications.  Calling sequence design in C is a very tricky subject,
badly complicated by the presence of things like longjmp() which *must*
be able to unwind a stack without elaborate symbol-table references.

Bliss is doing the loop increment one extra time to simplify the
code.  This again is a legitimate strategy in C only if it can be
guaranteed to be safe to evaluate the expression (with possible side
effects) an extra time.  As discussed before, this isn't trivial even
in simple-seeming cases.  Guilty but with extenuating circumstances.

C is not smart enough to combine two variables with non-overlapping
lifetimes into a single storage cell.  Nor is it smart enough to
make that cell a register.  Guilty but with minor reservations.
This optimization is ok in C only if nothing ever takes the address
of either variable.

C doesn't automatically remove unused local variables, while Bliss
does.  My own view is that neither compiler is doing the right thing --
they ought to complain, non-fatally.  This aside, guilty, although
this is one of those things that comes under the heading of really
bizarre input.

Dan complains, long and loud, about the overhead resulting from C
producing superfluous .data/.text directives in its output.  This
is obviously a result of the compiler being lazy, knowing that the
next phase (here the assembler) will tidy up.  Evidently Dan is
not aware that this technique is used on a massive scale inside the
Bliss compiler; it just doesn't show externally.

C does not optimize out common subexpressions.  True, because in
the presence of things like device registers this optimization is
*very* dangerous.  The case Dan presents is probably safe... but
if I worked on it I could probably come up with circumstances in
which it wouldn't be.

And the rest of Dan's complaints are all reasonably correct, subject
to some of the reservations mentioned above.

In short, it's true that the current VAX C compiler doesn't do as
much optimization as one would often like.  But it is also true that
C is a dangerous language to optimize, and many of the standard ways
of improving code are not safe without non-trivial analysis.  I am
aware of at least one "heavy optimizing" compiler for C, although I
have not yet seen details.  It can be done.
-- 
				Henry Spencer @ U of Toronto Zoology
				{allegra,ihnp4,linus,decvax}!utzoo!henry