Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!usc!snorkelwacker!spdcc!esegue!compilers-sender
From: convex!csmith@uunet.UU.NET (Chris Smith)
Newsgroups: comp.compilers
Subject: Re: Intermediate Representation
Keywords: parse, design, optimize
Message-ID: <1990Aug12.183239.11205@esegue.segue.boston.ma.us>
Date: 12 Aug 90 18:32:39 GMT
References: <1990Aug08.171640.13892@esegue.segue.boston.ma.us> <1990Aug09.180627.18848@esegue.segue.boston.ma.us> <1990Aug9.225859.10175@rice.edu>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: convex!csmith@uunet.UU.NET (Chris Smith)
Organization: Compilers Central
Lines: 58
Approved: compilers@esegue.segue.boston.ma.us
In-Reply-To: preston@titan.rice.edu's message of 10 Aug 90 15:41:46 GMT


In article <1990Aug9.225859.10175@rice.edu> Preston Briggs writes:

   >>AST's seem too high-level for doing lots of optimization.

   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.  

These algorithms *are* tree based, if not AST based -- the first step is
to do some control flow analysis to write the program as a sequence of
properly nested loops.  You can do the same optimizations on the loops no
matter how you discover them.

   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.

Depends on how abstract the ASTs are.  All of those loops can be easily
written as infinite trivial loops with breaks, plus other stuff in the
right places.  You need sequential composition, alternation,
loop/break/continue, and nothing else, to handle everything except goto.
(maybe alternation should be an n-way branch, maybe it makes sense to have
a special form for C switch, but such details don't matter much).  Gotos
that don't jump into statements from outside are pretty easy too (as break
or continue in a properly positioned loop).

   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?

It runs in linear time, and it does each thing that needs doing (and/or
bit vectors, scan through them) exactly once.  Probably faster.

You have a hold on both ends of an interesting region.  Say, in

	if ... then
	   ... a + b ...
	end if
	... a + b ...

where the if doesn't modify a+b and you're allowed to raise exceptions
prematurely.  You can insert a+b before the if.  Partial redundancy
elimination won't.  (It would insert a+b into an else branch, but there
isn't one.)  Iterative algorithms have info about one end of a region
whose other end is implicitly the procedure entry or exit, or sometimes
the enclosing loop entry or exit.  Tree-based algorithms extend this.

In
	loop
	 if ... a + b ... end if ...
	end loop

If a+b is loop invariant and doesn't raise exceptions or you don't care,
you can hoist it.  You might not want to if it's under switch rather than
if.  With trees, you can.
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue.  Meta-mail to compilers-request@esegue.