[tree-ssa] Inlining vs gimple vs compound expressions

[tree-ssa] Inlining vs gimple vs compound expressions

[law]

Diego/Andrew -- Back when we were in Toronto, we discussed getting rid of
COMPOUND_EXPRs.  Where do we stand on this?

The reason I ask is I'm sitting here looking at how to modify the inliner
so that the trees it creates are still in gimple form.  And, believe it
or not, it doesn't look terribly hard.  Conceptually, all I think I need
is a stack of CE nodes.  Of course if CE nodes are going away soon,
then, well, my scheme would be a waste of time to implement.

If CE nodes are going to hang around for a little while, I've got a
couple of questions.

First, can we ever get a function with no CE nodes?  ie, can a function's
tree ever be something like this:

  RETURN_EXPR
      |
  MODIFY_EXPR
      /\
     /  \
    /    \
 RESULT CALL_EXPR



Second, is TREE_OPERAND (CE_NODE, 1)) ever anything other than another
CE node or NULL?  ie, is this a valid tree?

      CE
      /\
     /  \
    /    \
LOOP_EXPR \
        RETURN_EXPR
           |
        MODIFY_EXPR
           /\
          /  \
         /    \
      RESULT  CALL_EXPR


             

Or should it instead be:


      CE
      /\
     /  \
    /    \
LOOP_EXPR \
          CE
          /\
         /  \
        /    \
     RETURN  NULL
       |
     MODIFY
      /\
     /  \
    /    \
RESULT  CALL

The second form is easier to deal with as we always know the CALL is on 
the LHS of the CE at the top of the stack.  It also simplifies insertion
of the new CE node when we inline the call.


Jeff

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[Andrew MacLeod]

On Thu, 2003-02-27 at 14:46, law@redhat.com wrote:
> 
> 
> Diego/Andrew -- Back when we were in Toronto, we discussed getting rid of
> COMPOUND_EXPRs.  Where do we stand on this?
> 

As far as I know, they are going to be around for a little while. I
beelive its a quite invasive change to the front ends to generate tree's
diofferently. Im supplying some generic link routines which the fornt
ends can then be modified to use, and then once they use nothing but
those routines, we can plug in another solution. 

> The reason I ask is I'm sitting here looking at how to modify the inliner
> so that the trees it creates are still in gimple form.  And, believe it
> or not, it doesn't look terribly hard.  Conceptually, all I think I need
> is a stack of CE nodes.  Of course if CE nodes are going away soon,
> then, well, my scheme would be a waste of time to implement.
> 
> If CE nodes are going to hang around for a little while, I've got a
> couple of questions.
> 
> First, can we ever get a function with no CE nodes?  ie, can a function's
> tree ever be something like this:
> 
>   RETURN_EXPR
>       |
>   MODIFY_EXPR
>       /\
>      /  \
>     /    \
>  RESULT CALL_EXPR
> 
> 
Dunno, but I don't see why not.

> 
> Second, is TREE_OPERAND (CE_NODE, 1)) ever anything other than another
> CE node or NULL?  ie, is this a valid tree?
> 
>       CE
>       /\
>      /  \
>     /    \
> LOOP_EXPR \
>         RETURN_EXPR
>            |
>         MODIFY_EXPR
>            /\
>           /  \
>          /    \
>       RESULT  CALL_EXPR
> 
>
Yes, I beleive the last CE node has 2 statements.. ie, the last CE node
will always look like this. Thats my understanding anyway.

 
>              
> 
> Or should it instead be:
> 
> 
>       CE
>       /\
>      /  \
>     /    \
> LOOP_EXPR \
>           CE
>           /\
>          /  \
>         /    \
>      RETURN  NULL
>        |
>      MODIFY
>       /\
>      /  \
>     /    \
> RESULT  CALL
> 
> The second form is easier to deal with as we always know the CALL is on 
> the LHS of the CE at the top of the stack.  It also simplifies insertion
> of the new CE node when we inline the call.
> 

I thought this was a problem too, but apparently not.

you could use the container....  thats how we do it in other places.
So instead of pushing on the CE node, you push on the address of the
field which points to the CE node. Then, when you pop it off, you
dereference it, and you are going to be looking at either
  - a CE node, in which case its a container, and you now its on the
LHS, or
  - something other than a CE node, which means its the RHS of a CE.

And since you have the address of the pointer to this node, you can
easily add new CE nodes, or do whatever you want.

Is that too cryptic? :-)

Andrew

[tree-ssa] Inlining vs gimple vs compound expressions

[Andrew Haley]

law@redhat.com writes:
 > 
 > 
 > Diego/Andrew -- Back when we were in Toronto, we discussed getting rid of
 > COMPOUND_EXPRs.  Where do we stand on this?
 > 
 > The reason I ask is I'm sitting here looking at how to modify the inliner
 > so that the trees it creates are still in gimple form.  And, believe it
 > or not, it doesn't look terribly hard.  Conceptually, all I think I need
 > is a stack of CE nodes.  Of course if CE nodes are going away soon,
 > then, well, my scheme would be a waste of time to implement.
 > 
 > If CE nodes are going to hang around for a little while, I've got a
 > couple of questions.
 > 
 > First, can we ever get a function with no CE nodes?  ie, can a function's
 > tree ever be something like this:
 > 
 >   RETURN_EXPR
 >       |
 >   MODIFY_EXPR
 >       /\
 >      /  \
 >     /    \
 >  RESULT CALL_EXPR

I think I have seen that with Java.

 > Second, is TREE_OPERAND (CE_NODE, 1)) ever anything other than another
 > CE node or NULL?  ie, is this a valid tree?
 > 
 >       CE
 >       /\
 >      /  \
 >     /    \
 > LOOP_EXPR \
 >         RETURN_EXPR
 >            |
 >         MODIFY_EXPR
 >            /\
 >           /  \
 >          /    \
 >       RESULT  CALL_EXPR

Java again: AFAIK in all cases it's quite legal to replace a
COMPOUND_EXPR with a BLOCK or a variable and vice versa.

Andrew.

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[Andrew MacLeod]

On Thu, 2003-02-27 at 14:46, law@redhat.com wrote:
> 
> 
> Diego/Andrew -- Back when we were in Toronto, we discussed getting rid of
> COMPOUND_EXPRs.  Where do we stand on this?
> 
> The reason I ask is I'm sitting here looking at how to modify the inliner
> so that the trees it creates are still in gimple form.  And, believe it
> or not, it doesn't look terribly hard.  Conceptually, all I think I need
> is a stack of CE nodes.  Of course if CE nodes are going away soon,
> then, well, my scheme would be a waste of time to implement.
> 

However, this begs a different question. We should be able to do
whatever we want without even knowing about the existince of a CE node.
Of course, all you need is insertion routines. Actually  in this case, I
think all you need are the linkig routines?  You would be dealing with a
tree-statement_iterator, n'est pas?  So if you have routines to
link_before and link_after, then you dont care about anything else.  

Is that correct?

so things like:

tree_stmt_iterator tsi_link_before      PARAMS ((tree_stmt_iterator, tree));
tree_stmt_iterator tsi_link_after       PARAMS ((tree_stmt_iterator, tree));
tree_stmt_iterator tsi_delink           PARAMS ((tree_stmt_iterator));
tree_stmt_iterator tsi_new_stmt_list    PARAMS ((tree, tree_stmt_anchor *));
tree_stmt_iterator tsi_stmt_list_start  PARAMS ((tree_stmt_anchor));


for instance.

Does that give you all the functionality you need? or do you need
something else?

Andrew

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[Daniel Berlin]

On Thursday, February 27, 2003, at 02:46  PM, law@redhat.com wrote:

>
>
> Diego/Andrew -- Back when we were in Toronto, we discussed getting rid 
> of
> COMPOUND_EXPRs.  Where do we stand on this?
Without CE's how do you propose we perform insertion, for instance.
I'm not bitching, i'm asking, since SSAPRE needs to do it.

I also find it odd that a potential decision that affects other people 
working on tree-ssa optimizers was not discussed publicly at all yet, 
and you act as if it's possibly a done deal.
It's one thing to propose it in toronto, do some work, decide it's not 
a good idea, and never mention it, but like i said, you act as if this 
is something already decided one way or the other.  And even if you 
want to play that way (which isn't particularly nice to do, but hey, 
whatever) if they are "going away soon", it would be nice to, you know, 
tell other people involved in development before it just up and 
happened one day?

That said, it's not that i like CE's particularly, since right now the 
restrictions on them make me unable to easily do SSAPRE insertion (in 
particular, the requirement that the first argument of a CE not be a CE 
itself), since i can't control where in a CE the trees i want to insert 
before/after appear.
Thus, the reason i'm waiting for Andrew's insertion code.

--Dan

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[Steven Bosscher]

Op do 27-02-2003, om 20:46 schreef law@redhat.com:
> 
> 
> Diego/Andrew -- Back when we were in Toronto, we discussed getting rid of
> COMPOUND_EXPRs.  Where do we stand on this?

For those who are trying to write a front end that is based on the
tree-ssa work, would you please be more specific about what you mean
with "getting rid of COMPOUND_EXPRs"?  Does it mean that GENERIC/GIMPLE
will not use them anymore?

Greetz
Steven

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[Andrew MacLeod]

On Thu, 2003-02-27 at 15:34, Daniel Berlin wrote:
> 
> On Thursday, February 27, 2003, at 02:46  PM, law@redhat.com wrote:
> 
> >
> >
> > Diego/Andrew -- Back when we were in Toronto, we discussed getting rid 
> > of
> > COMPOUND_EXPRs.  Where do we stand on this?
> Without CE's how do you propose we perform insertion, for instance.
> I'm not bitching, i'm asking, since SSAPRE needs to do it.
> 
> I also find it odd that a potential decision that affects other people 
> working on tree-ssa optimizers was not discussed publicly at all yet, 
> and you act as if it's possibly a done deal.
> It's one thing to propose it in toronto, do some work, decide it's not 
> a good idea, and never mention it, but like i said, you act as if this 
> is something already decided one way or the other.  And even if you 
> want to play that way (which isn't particularly nice to do, but hey, 
> whatever) if they are "going away soon", it would be nice to, you know, 
> tell other people involved in development before it just up and 
> happened one day?
> 
> That said, it's not that i like CE's particularly, since right now the 
> restrictions on them make me unable to easily do SSAPRE insertion (in 
> particular, the requirement that the first argument of a CE not be a CE 
> itself), since i can't control where in a CE the trees i want to insert 
> before/after appear.
> Thus, the reason i'm waiting for Andrew's insertion code.
> 

All our discussion entailed was eliminating the dependance on a specific
implementation of linking tree nodes, which is what CE nodes do. Thus
the main drive of the iterators and the inserting/linking routines is to
keep users from ever seeing something like a CE node, which is pure
infrastructure, and half our problem.

If you dont know they exist, we are open to removing them and replacing
them with something better, of which lots of people have ideas on what
would be better. The goal is a competely transparent underlying
structure that can be plug-replaced with something better someday.

Andrew

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[law]

In message <1046375862.29820.352.camel@p4>, Andrew MacLeod writes:
 >As far as I know, they are going to be around for a little while. I
 >beelive its a quite invasive change to the front ends to generate tree's
 >diofferently. Im supplying some generic link routines which the fornt
 >ends can then be modified to use, and then once they use nothing but
 >those routines, we can plug in another solution. 
OK.

[ ... ]
 >I thought this was a problem too, but apparently not.
 >
 >you could use the container....
Possibly, though it that may require some major surgery in the inliner
since it's not aware of containers at all.  It just DFS walks the
function's entire tree structure replacing suitable CALL_EXPRs with
BIND_EXPRs.

Assuming that surgery isn't insanely difficult we have to keep both
the old scheme and the new scheme around since someone could compile
with -fdisable-simple and inlining still needs to work.


 >So instead of pushing on the CE node, you push on the address of the
 >field which points to the CE node. Then, when you pop it off, you
 >dereference it, and you are going to be looking at either
 >  - a CE node, in which case its a container, and you now its on the
 >LHS, or
 >  - something other than a CE node, which means its the RHS of a CE.
 >
 >And since you have the address of the pointer to this node, you can
 >easily add new CE nodes, or do whatever you want.
 >
 >Is that too cryptic? :-)
I don't follow how this tells you if the call was on the LHS or RHS, but
for now I'll assume it does and start looking at what it would take to
make the inliner know about containers....

Jeff

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[law]

In message <1046378181.760.91.camel@steven>, Steven Bosscher writes:
 >Op do 27-02-2003, om 20:46 schreef law@redhat.com:
 >> 
 >> 
 >> Diego/Andrew -- Back when we were in Toronto, we discussed getting rid of
 >> COMPOUND_EXPRs.  Where do we stand on this?
 >
 >For those who are trying to write a front end that is based on the
 >tree-ssa work, would you please be more specific about what you mean
 >with "getting rid of COMPOUND_EXPRs"?  Does it mean that GENERIC/GIMPLE
 >will not use them anymore?
Basically CEs are a rather heavy-weight means to link trees together, both
in terms of their memory requirements and the silly requirement that
have to strip them away anytime we want to do anything with the underlying
node.

If you're not careful you start to end up with STRIP_foo things everywhere
because you don't ever know if you're looking at the real node or the CE
container.  And you still miss some, leading to weird failures because
you were looking at the container rather than the real expression.

The basic idea was to avoid all that crazyness with a scheme that worked
better.  However, based on messages from Andrew it doesn't sound like 
CEs will be going away anytime soon.

jeff

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[Andrew MacLeod]

On Thu, 2003-02-27 at 16:01, law@redhat.com wrote:
> In message <1046378181.760.91.camel@steven>, Steven Bosscher writes:
>  >Op do 27-02-2003, om 20:46 schreef law@redhat.com:
>  >> 
>  >> 
>  >> Diego/Andrew -- Back when we were in Toronto, we discussed getting rid of
>  >> COMPOUND_EXPRs.  Where do we stand on this?
>  >
>  >For those who are trying to write a front end that is based on the
>  >tree-ssa work, would you please be more specific about what you mean
>  >with "getting rid of COMPOUND_EXPRs"?  Does it mean that GENERIC/GIMPLE
>  >will not use them anymore?
> Basically CEs are a rather heavy-weight means to link trees together, both
> in terms of their memory requirements and the silly requirement that
> have to strip them away anytime we want to do anything with the underlying
> node.
> 
> If you're not careful you start to end up with STRIP_foo things everywhere
> because you don't ever know if you're looking at the real node or the CE
> container.  And you still miss some, leading to weird failures because
> you were looking at the container rather than the real expression.
> 
> The basic idea was to avoid all that crazyness with a scheme that worked
> better.  However, based on messages from Andrew it doesn't sound like 
> CEs will be going away anytime soon.
> 

They might not be going away, but they will be transparent. You should
never have to look for or create a CE node explicitly. You *should* be
able to do everything through iterators and iterator manipulators. 

Thats the plan anyway :-)

Andrew 

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[Jason Merrill]

On Thu, 27 Feb 2003 15:34:30 -0500, Daniel Berlin <dberlin@dberlin.org> wrote:

> That said, it's not that i like CE's particularly, since right now the
> restrictions on them make me unable to easily do SSAPRE insertion (in
> particular, the requirement that the first argument of a CE not be a CE
> itself)

This needn't be a requirement, except in the interests of avoiding
recursion.  In the gimplifier I frequently replace simple statements with
CEs, which usually means putting one in the first argument of another CE;
this is later tidied up with a call to rationalize_compound_expr.  Would a
strategy like that work for you?

Jason

Re: [tree-ssa] Inlining vs gimple vs compound expressions

[law]

In message <1046376409.1390.362.camel@p4>, Andrew MacLeod writes:
 >However, this begs a different question. We should be able to do
 >whatever we want without even knowing about the existince of a CE node.
 >Of course, all you need is insertion routines. Actually  in this case, I
 >think all you need are the linkig routines?  You would be dealing with a
 >tree-statement_iterator, n'est pas?  So if you have routines to
 >link_before and link_after, then you dont care about anything else.  
 >
 >Is that correct?
 >
 >so things like:
 >
 >tree_stmt_iterator tsi_link_before      PARAMS ((tree_stmt_iterator, tree));
 >tree_stmt_iterator tsi_link_after       PARAMS ((tree_stmt_iterator, tree));
 >tree_stmt_iterator tsi_delink           PARAMS ((tree_stmt_iterator));
 >tree_stmt_iterator tsi_new_stmt_list    PARAMS ((tree, tree_stmt_anchor *));
 >tree_stmt_iterator tsi_stmt_list_start  PARAMS ((tree_stmt_anchor));
 >
 >
 >for instance.
 >
 >Does that give you all the functionality you need? or do you need
 >something else?
Well, I've got the inliner using the tree statement iterators (it was
a rather easy conversion).  So, yes, I'm pretty sure those routines would
be everything I need.

If you've got some code you want to throw my way to poke at, feel free.

jeff