I-langs for optimization

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

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