Re: Language-independent functions-as-trees representation

[Paul Brook <paul at nowt dot org>]

I'm currently helping write the Fortran 95 frontend to GCC 
(g95.sourceforege.net). This is of some interest to as we generate SIMPLE 
trees a function at a time..

On Friday 23 August 2002 8:16 pm, Diego Novillo wrote:
> On Fri, 23 Aug 2002, Jason Merrill wrote:
> > Basically, I'm wondering if other people are interested enough in this
> > change to 1) help with the design for the IR and 2) help with porting
> > the existing tree optimizers to the new IR.

I definitely think it's a decision that should be made sooner rather than 
later. It does seem a bit strange to have the two different classes of 
tree. I'll give what help I can, although I've not much idea how the new 
optimizers work.

<snip>
> just a do-while guarded with an if() (a-la SUIF).  For the
> do-loop expression,  I'd like:
>
> 	DO_LOOP_EXPR
> 		INDEX_DECL -> var
> 		LB_EXPR -> val
> 		UB_EXPR -> val
> 		COND_CODE -> '<' | '>' | '<=' | '>='
> 		STEP_EXPR -> val
> 		LANDING_EXPR -> COMPOUND_EXPR
> 		BODY_EXPR -> COMPOUND_EXPR
>
> This is equivalent to the following:
>
> for (INDEX_DECL = LB_EXPR;
>      INDEX_DECL COND_CODE UB_EXPR;
>      INDEX_DECL += STEP_EXPR)
> {
>   if (INDEX_DECL == LB_EXPR)
>     LANDING_EXPR;
>   else
>     BODY_EXPR;
> }

This is pretty much ideal for fortran. We generate a lot of loops like this 
implicity for the scalarized array code.

> LANDING_EXPR is just a convenience for optimizers to have
> somewhere to blindly move invariant code to.  This would be
> expanded to something like:
>
> INDEX_DECL = LB_EXPR;
> if (INDEX_DECL COND_CODE UB_EXPR)
>     LANDING_EXPR;
> for (...)
>
> We could do without it.  Another important feature of
> DO_LOOP_EXPR is that both UB_EXPR and STEP_EXPR should be loop
> invariant (ideally, constants).  Anything that the front-end
> can't (or won't) convert directly can be dealt with a loop
> canonicalization pass which would do some basic data flow
> analysis to re-write WHILE_EXPRs.

Agreed.

<snip>
> > The Java loop has 1 (or 0) EXIT_EXPR, used to express the loop
> > condition. This makes it easy to distinguish from 'break's, which are
> > expressed with EXIT_BLOCK_EXPR.
> >
> > EXIT_EXPR is a bit backwards for this purpose, as its sense is opposite
> > to that of the loop condition, so we end up calling invert_truthvalue
> > twice in the process of generating and expanding it.  But that's not a
> > big deal.
> >
> > >From an optimization perspective, are
> > > LABELED_BLOCK_EXPR/EXIT_BLOCK_EXPR
> >
> > easier to deal with than plain gotos?  I assume they're preferable to
> > the current loosely bound BREAK_STMT, which has no information about
> > what it's exiting.  EXIT_EXPR would have the same problem if it were
> > used to express 'break'.
>
> What's wrong with BREAK_STMT?  As long as you know its parent,
> it's relatively easy to figure out where to send the flow edge.
> GOTO_STMTs are just as easy to deal with.  I don't have a problem
> with the existing setup.  I don't know about
> LABELED_BLOCK_EXPR/EXIT_BLOCK_EXPR.

The existing BREAK_STMT isn't sufficient for Fortran purposes, where a 
break/continue statement can break out of an outer loop. We're currently 
implementing this with GOTO_STMTs, but could equally well use 
LABELED_BLOCK_EXPR/EXIT_BLOCK_EXPR if this made things easier for 
optimizations.