preston@titan.rice.edu (Preston Briggs) (04/10/90)
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
jlg@lambda.UUCP (Jim Giles) (04/11/90)
From article <6526@brazos.Rice.edu>, by preston@titan.rice.edu (Preston Briggs): > [...] > 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). I am, of course, interested in the work. And I will go immediately to the library to get copies of their previous papers. But, I don't see how you can to interprocedural analysis where separate compilation is involved. Separate compilation implies that the compiler is completely unaware of the content of procedures other than the one currently being compiled. In fact, all the procedures in a given program may have been developed _and_COMPILED_ at different sites. The only thing the local user has are the libraries and a loader to put them together. Anyway, just trying to get the straight story. J. Giles