🚀 go-pugleaf

Jim Giles writes:
> David Gudeman writes:
>> It is
>> true that the optimization of pointer arithmetic is more difficult,
>> but a good enough compiler can detect all possible aliases by global
>> control flow analysis, even with seperate compilation.

>That's just the point.  The _compiler_ can't do any such thing!  That's
>the _definition_ separate compilation - the different program units
>are unknown to each other at compile time.  The only implementation
>so far proposed (on the net anyway) which does interprocedual data
>flow analysis in this way has the _loader_ do code generation.

Well, we can do better than link- or load-time optimization.
At Rice U., people (Callahan, Cooper, Kennedy, Torczon, and others)
have been working on interprocedural analysis for several years.  
They've discovered fast algorithms to do, among other things, 
interprocedural alias analysis.  Further, they know how to handle 
separate compilation (despite the ivory tower that people are 
beginning to invoke).  Finally, the algorithms are used at Rice
and in industry (to further spite the anti-intellectual heathen
among you).

Unfortunately, ...
these are aliases introduced at procedure call sites,
when passing globals by reference or when passing a local by reference
in more than 1 parameter position.

Aliases introduced by pointer manipulation are much harder.  
Optimizers wonder, when they see an assignment

	p->left->right->key = 1;

exactly what memory locations might be changed.  Now, we could make a 
guess by looking at the types of the pointers and such, but (in most 
code) the resulting approximation would be too imprecise to be useful.
Of course, casting makes things worse.

The latest paper I know of will appear at 
this summer's compiler construction conference:

	Analysis of Pointers and Structures
	Chase, Wegman, Zadeck

Note that this work concerns intra-procedural analysis.
Interprocedural variants are still harder.

So, despite my bragging on interprocedural analysis,
I don't believe pointer references can be analyzed with the
same precision as array references.  Pointer arithmetic
and casts make the analysis even harder.

--
Preston Briggs				looking for the great leap forward
preston@titan.rice.edu