Re: Intermediate Representation

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.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.