markhall@pyrps5.pyramid.com (Mark Hall) (01/14/89)
What `level' of intermediate language is best for optimization?
I am looking for references (and opinions!) regarding the `level' of
intermediate language (i-lang) which is best processed by all those
state-of-the-art optimizers out there. As a simple example of two
different `levels', I would say that an i-lang which is tree-based and
contains `if', `while', and `switch' operators (close to a syntax tree)
is higher level than a linear i-lang wherein all control flow occurs
via explicit tests and branches*.
To get things started, there are more register to register transfers
exposed at the low-level, and so more chances for smart register
allocation occur. So score 1 for the low levels (anyone have
experience to the contrary?). On the other hand, I claim that one can
do a better job of common subexpression elimination (CSE) on a high
level tree form. Consider the C fragment:
i1 = (b && c || d);
i2 = (b && c || d);
since C requires short-circuit evaluation of && and ||, this will be
broken into separate basic blocks for a low-level i-lang, and so the
obvious CSE optimization will be missed by low-level optimizers.
A high level optimizer can recognize this common subexpression, but its
notion of a `flow graph' is more difficult to deal with. There are
expressions in a basic block which might not be reached and so cannot
be counted on as sources for CSE (anyone else encounter this problem?).
The foregoing were just trivial examples of tradeoffs. What I am
really looking for are lengthy expostulations for one or the other
(or neither) based on personal experience or cited papers. All level
of detail is welcome.
Feel free to expound on the support required for data dependence
analysis in vectorizing & parallelizing optimizers. You might also want
to mention which `level', if any, facilitates debugging.
-Mark Hall (smart mailer): markhall@pyramid.pyramid.com
(uucp paths): {ames|decwrl|sun|seismo}!pyramid!markhall
--------------------------------------------------------------------
* - Either level may or may not contain machine dependencies. I'm not
strictly interested in optimizers that claim to be machine independent.
[I always thought that if you wanted to do a really thorough job, you needed
to do optimizations at lots of different levels, not just one. -John]
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { decvax | harvard | yale | bbn}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers. Meta-mail to ima!compilers-requeststeve@hupcap.clemson.edu (Steve Stevenson) (01/18/89)
> What `level' of intermediate language is best for optimization?
We have been doing some work here with vectorization and languages which are
oriented to scientific programming. We so far find that the necessity to deal
with idioms sets the level. That is, if the level is too low, the
optimizations are hard to find; if to high, one gets a copy of the original
input. Contact Abbas Youssefi ( youssef@citron.cs.clemson.edu ) for the latest
in our war stories.
Steve (really "D. E.") Stevenson steve@hubcap.clemson.edu
Department of Computer Science, (803)656-5880.mabell
Clemson University, Clemson, SC 29634-1906
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { decvax | harvard | yale | bbn}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers. Meta-mail to ima!compilers-request