Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!apple!snorkelwacker!spdcc!esegue!compilers-sender
From: preston@rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Re: Intermediate Representation
Keywords: code, optimize, design
Message-ID: <1990Aug08.171640.13892@esegue.segue.boston.ma.us>
Date: 8 Aug 90 17:16:40 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: Preston Briggs <preston@rice.edu>
Organization: Rice University, Houston
Lines: 45
Approved: compilers@esegue.segue.boston.ma.us
In-Reply-To: <1990Aug07.153407.8877@esegue.segue.boston.ma.us>

In article <1990Aug07.153407.8877@esegue.segue.boston.ma.us> you write:
>I would like know what people think is the best Intermediate Representation
>(IR) to be used for highly effective optimizations and code generation, and
>it should be portable.

>Examples of IRs that I know:
>(1) Abstract-syntax-tree (looks like Scheme code)
>(2) DAG
>(3) Three address code
>(4) P-code
>(5) Stanford's U-code

First, I'd classify (5) as an extension of (4) and I might group (2) with
(3).

I like low-level 3-address code (even lower level than assembly).  Several
optimizing compilers that have been built using such a representation -- the
best known is the PL.8 compiler built by researchers at IBM.

I don't much like IL's based on stack machines (roughly 4 and 5), at least
for optimization purposes.  Optimization wants explicit registers to hold
intermediate results.

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

Actually, I'll qualify this a little.  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).  This is the sort of approach we've taken locally.

Naturally, there are counter-examples to everything I've said.  AST based
compilers include Bliss-11, the PQCC based systems, and some of the Ada
efforts.  There's also Guy Steele's Rabbit compiler.  Fred Chow's thesis
describes an optimizing Pascal compiler based on (5).  I believe Chow's work
is also the basis for the MIPS compilers.  Some version of (4) is used in
Powell's Modula-2 compiler.

Preston
[Anybody tried program dependency graphs, per Ferrante et al. at IBM.  From
the articles I've seen, they look pretty neat. -John]
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue.  Meta-mail to compilers-request@esegue.