smart compilers

[Jeff Lee]

> > Compilers that optimize code can break programs regardless of what 
> > language that code is written in.  Optimizing compilers are very useful
> > as long as the optimization is optional (or at least can be turned
> > off when the code involved may be sensitive to optimization).
> 
> I must disagree with such a general statement.  There are compilers that
> claim to "optimize", and that do break code, but (especially nowadays)
> compiler writers go to great pains to ensure that this is not the case,
> and they DO provide ways for the programmer to inform the compiler that
> mystical things are happening (e.g, "volatile" declaration for variables
> that may be modified asynchronously (this for FORTRAN!!)).  An optimizing
> compiler that breaks code is buggy, and should be reported as such (rather
> than tolerated: "Oh, those optimizing compilers, such rascally programs.
> Can't expect an easy time if you want your code to run fast.").  Don't buy
> that lie.  Real compilers DO exist.
> 

One of the things that was stressed in the graduate compiler class here at
Georgia Tech was that you don't make optimizations that will make errors
look like they happened in a different place (to assist in debugging) much
less break things. Code movement is a shaky thing. You can cause errors
to happen (divides by 0 that would not normally occur) by moving invariant
code outside of a loop. These are incorrect optimizations. I always enjoyed
CDC's old FTN4 compiler (FORTRAN 66). It had, as I remember, 4 levels of
optimization with the last one included with the argument UO --- Unsafe
Optimizations. I have had code broken by this because it makes certain
assuptions about DO loops to try and keep things in registers.

In reponse to the person who didn't want the compiler to make any optimizations
for him (paraphrase, I want that sucker to do what I tell it to), there are
situations that need to be optimized that are hard for the user to control.
Everyone has seen the case of optimization for common subexpressions, eg...

	a = i + j + k;
	b = i + j;

turned into

	t = i + j;
	a = t + k;
	b = t;

or even

	b = i + j;
	a = b + k;

swapping an addition for a store (which may actually be a register and be
for free) or completely eliminating the addition. This is nice that it can be
done automatically but the real benefit of common subexpression elimination
is in optimizing things like array references where the programmer (in most
languages) has no way to optimize them out himself. Take for example the code
segment

	int a[3][5];
	    ...
	a[i-1][j-1] = 1;
	a[i-1][j]   = 2;
	a[i-1][j+1] = 3;

should expand into

	*(a + 5 * (i - 1) + j - 1) = 1;
	*(a + 5 * (i - 1) + j    ) = 2;
	*(a + 5 * (i - 1) + j + 1) = 3;

which is pretty tacky, but what was asked for. With very little smarts in your
common subexpression remover you can turn this into

	t = a + 5 * (i - 1) + j;
	*(t - 1) = 1;
	*(t    ) = 2;
	*(t + 1) = 3;

and with a small amount of expression rearrangement (which can also be a
tricky movement since theoretically things are associative but on a computer
they really aren't) you can finish it up with

	t = (a - 5) + 5 * i + j;
	*(t - 1) = 1;
	*(t    ) = 2;
	*(t + 1) = 3;

where (a - 5) is even a constant that can be calculated at compile time. Thus
with a little smarts we have turned 4 subtractions, 7 adds, and 3 multiplies
into 1 subtraction, 3 adds, and 1 multiply. None of these optimizations should
have broken anything yet they should almost triple the speed of the index
calculations. The only possible errors could be if either i or j were
a "volatile" variable, but the new C standard is fixing this.

I realize that the normal C user can perform all these optimizations himself
and that is one of the reasons that I like C. I can make these optimizations
if the need be. What I would like, though, is for the compiler to do these
for me automatically so I don't have to mangle my code to make it fast.
Also, the FORTRAN, PASCAL, BASIC, PL/I, etc.... user is left to the mercy of
the compiler to make these optimizations for him.

Excuse me for dragging on so long. This wasn't supposed to be a lecture.
-- 
Jeff Lee
CSNet:	Jeff @ GATech		ARPA:	Jeff.GATech @ CSNet-Relay
uucp:	...!{akgua,allegra,rlgvax,sb1,unmvax,ulysses,ut-sally}!gatech!jeff