Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!ames!haven!decuac!e2big.mko.dec.com!bacchus.pa.dec.com!decwrl!sdd.hp.com!usc!snorkelwacker!spdcc!ima!esegue!compilers-sender
From: preston@titan.rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Re: Intermediate Representation
Keywords: code, optimize, design
Message-ID: <1990Aug9.225859.10175@rice.edu>
Date: 10 Aug 90 15:41:46 GMT
References: <1990Aug08.171640.13892@esegue.segue.boston.ma.us> <1990Aug09.180627.18848@esegue.segue.boston.ma.us>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: preston@titan.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Lines: 57
Approved: compilers@esegue.segue.boston.ma.us

I wrote:
>>AST's seem too high-level for doing lots of optimization.  We want the
>>details of array accesses, etc. exposed to the optimizer.

>>I believe there are many optimizations that can be carried out 
>>most effectively on a high-level representation (for example, 
>>those requiring dependence analysis) and many that should be 
>>carried out on a low level representation (e.g., CSE elimination, 
>>strength reduction).

grover@brahmand.Eng.Sun.COM (Vinod Grover) writes:
>First of all, there is no reason why an AST based IR cannot have low-level
>features (such as array/memory accesses).

>Second, as Bliss-11 showed global CSE elimination can be done at a high
>level. Similarly, strength reduction isnt that hard at a high level. Karl
>Ottenstein showed, in an IEEE paper several years ago, that strength
>reduction is easy to do on PDGs and can easily be extended to ASTs. (I do
>not have the reference handy but can post it, if anyone is interested.)

I'm mostly presenting my "religious convictions" here; I agree that there
are many ways to skin a cat.  However, Ottenstein's paper serves a 
nice illustration.  

He discusses strength reduction of induction variables in the context of
DO/FOR-style loops, with the iteration variable clearly marked by the
header node, as increment expressions and the limit tests.

A more general algorithm (say Cocke and Kennedy) would perform strength 
reduction over any loop (while loops, loops built out of if's and goto's), 
would discover all the induction variables (not just the loop control 
variable), and would make provision for linear function test replacement.  
Other algorithms extend partial redundancy elimination to discover strength 
reductions in linear regions (I've seen versions by Chow and by Dhamdhere).

The point is that people are seduced by the apparent simplicity of
analysis of ASTs.  Don't be fooled!  Without care, you'll have to write
routines to analyze DO loops, WHILE loops, REPEAT-UNTILs, LOOPs with
EXITs, etc...  I write routines that work with more traditional flow
graphs (directed graphs) -- all loops look the same to me.  Ditto for CASE
statements, IF statements, GOTO's, ad nauseum.

I also wonder about the memory requirements of a detailed AST; that is,
one with all the fun of each multidimensional array access written out in
tree form.  PDG's and PDW's are even scarier in this respect.

While it may be that AST fans can show ways around my complaints, can they
also give me some positive reasons to switch?  What's the gain?

(speaking as a devil's advocate, of course)

-- 
Preston Briggs				looking for the great leap forward
preston@titan.rice.edu
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue.  Meta-mail to compilers-request@esegue.