Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!snorkelwacker!spdcc!ima!esegue!compilers-sender
From: jouvelot@brokaw.lcs.mit.edu (Pierre Jouvelot)
Newsgroups: comp.compilers
Subject: Re: Intermediate Representation
Keywords: code, optimize, design
Message-ID: <1990Aug13.150819.17410@mintaka.lcs.mit.edu>
Date: 13 Aug 90 21:41:19 GMT
References: <1990Aug09.180627.18848@esegue.segue.boston.ma.us> <1990Aug9.225859.10175@rice.edu> <1990Aug11.203048.848@mintaka.lcs.mit.edu> <1990Aug12.212723.1247@rice.edu>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: jouvelot@brokaw.lcs.mit.edu (Pierre Jouvelot)
Organization: MIT
Lines: 55
Approved: compilers@esegue.segue.boston.ma.us

In article <1990Aug12.212723.1247@rice.edu> preston@titan.rice.edu 
(Preston Briggs) writes:

>In article <1990Aug11.203048.848@mintaka.lcs.mit.edu> I write:
>
>>With the AST approach, the cleanest way to deal with this overabundance of
>>control structures is to define a single "generic" loop construct; all the
>>control structures can then be trivially desugared (e.g., by the parser)
>>into your own version of loop.
>
>I don't see the trivial desuguring by the parser, particularly with an IF -
>GOTO form of the loop.
>
>I can see discovering the entire CFG and then doing interval analysis to
>discover a nice tree-like grouping of nested control structures a la Sharir
>(or others), but you're still punting on irreducible flow graphs.

Well, you almost got a point here. The way the PIPS system deals with
irreducible flow graphs is interesting. Basically, the AST data type
definition looks something like this (I use the straightforward NewGen
syntax) :

    instruction = block:instruction* + test + call + loop + unstructured ;

    test = condition:expression x true:instruction x false:instruction ;

    unstructured = instruction x predecessors:unstructured*
			       x successors:unstructured* ;

    ....

which says that an instruction is either a block (which is a list of
instructions), a test (which has a condition expression and a true and false
instruction), a call or a loop (not specified here) or an "unstructured". An
"unstructured" datatype denotes a control structure that could correspond to
an irreducible graph. The key point is that the instruction that appears in
an "unstructured" value can be *any* instruction (i.e., can be a block, or a
test ... or even another control graph !). The usual data flow algorithms
seem to carry along with this kind of recursive approach (although I still
have to find the time to prove it :-).

With this way, you keep the power of ASTs while being able to deal with
arbitrary control graphs on which, our parallelizer is pretty unable to do
much about, anyway. However, notice that, if you can figure out (as I do)
that a "dirty" control graph is embedded inside an otherwise "nice" DO loop,
then from the outside, the loop looks like a well structured one which can
be parallelized ; this is a great plus of this approach.

Pierre
--
. CAI, Ecole des Mines, Paris (France): jouvelot@ensmp.fr
. LCS, MIT, Cambridge (USA): jouvelot@brokaw.lcs.mit.edu
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.