Re: Language-independent functions-as-trees representation

[Diego Novillo <dnovillo at redhat dot com>]

On Sat, 24 Aug 2002, Jason Merrill wrote:

> TREE_CHAIN of a COMPOUND_EXPR is currently unused; a sequence of statements
> is represented by a series of COMPOUND_EXPRs, each with a statement in op0,
> pointing to the next one through op1.
> 
And TREE_CHAIN would point to the previous one?  Isn't the extra
encapsulation even more cache hostile?

How about flattening the IR when we convert it into SIMPLE?  We
know that SIMPLE trees have a much more rigid layout.  Each tree
has at most two operands (lists could be modeled with array
containers).

Furthermore, we could flatten out statements into arrays as we
build the flow graph of the function.  Each basic block contains
an array of statements.  This setup makes intra-block insertions
expensive, so we could double chain them instead of treating them
like an array (similarly to what we do with the BASIC_BLOCK
array).


> The Java frontend uses a LOOP_EXPR (infinite loop) with an EXIT_EXPR for
> the loop condition, either at the beginning or end of the statement chain
> in LOOP_EXPR_BODY, for while and do-while loops respectively.  Does this
> work for you, or is that a significant inconvenience compared to hanging
> the condition directly off of the loop node?
> 
*shrug*  So, if the first node of a LOOP_EXPR_BODY is an
EXIT_EXPR then I'm dealing with a while(), otherwise I'm dealing
with a do/while?  I guess it would work.

> The key benefit of this scheme for SIMPLE is that it allows us to simplify
> the loop condition without having to copy its preque around a la
> insert_before_continue.  If the condition needs simplification, we just end
> up with a few other statements before we get to the EXIT_EXPR.
> 
Hmm, true, but this has just messed up the straightforward scheme
for building the flowgraph that I had described in my previous
paragraph.

This means that the only way for the flowgraph builder to tell a
while() from a do/while() is to walk the LOOP_EXPR_BODY and see
whether it's last node is an EXIT_EXPR?  That's very irritating.
We will have to walk the body twice, once to tell what it is and
the second time to build the nodes.

> > 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
> 
> I would say -> stmt for the last two.
> 
Yes.

> > LANDING_EXPR is just a convenience for optimizers to have somewhere to
> > blindly move invariant code to.  We could do without it.
> 
> I think my preference would be to do without it; if we're moving code out
> of the loop, it should go out of the loop.  But I don't feel strongly about
> this.
> 
The advantage of this is that all the optimizers can blindly move
code to the landing pad.  Afterwards, we have a single pass that
deals with generating code for it (ie, emitting the if() guard
before the loop begins).

> > 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.
> 
> My thinking was that if you're walking through a function the first time,
> when you see an EXIT_BLOCK_EXPR you know exactly which blocks it is going
> to close, and thus what cleanups and whatnot you might need to do.  With a
> general goto, if you haven't seen the label yet you don't know much of
> anything.  I suppose that in the optimizer you can annotate the gotos
> appropriately, but it's a bit more complicated.
> 
The flowgraph is built in two steps.  You first build all the
basic blocks and then you build all the edges.  By the time you
are building the edges, you have seen every label that is the
target of a goto.

> The thing about BREAK_STMT is that expand_exit_something has variable
> semantics; the things it does or doesn't exit depend on the value of
> exit_flag passed to expand_start_loop et al.  I'd prefer to make what it
> exits explicit.
> 
OK.  But you will always need to model gotos, right?  There's no
escaping that, I presume.



Diego.