Re: [tree-ssa] Insert on edge comment

[Andrew MacLeod <amacleod at redhat dot com>]

On Mon, 2003-06-02 at 22:54, Daniel Berlin wrote:
> 
> On Monday, June 2, 2003, at 06:09  PM, Andrew MacLeod wrote:
> 
> > On Mon, 2003-06-02 at 17:44, Daniel Berlin wrote:
>
> > I read this as saying you are trying to find ways of inserting on an
> > edge without using the insert_on_edge routines.
> 
> Actually, I tried using it, and it won't work for me yet.
> 
> For starters:
> 
>        /* If the last stmt is a GOTO, the we can simply insert before  
> it.  */
>        if (TREE_CODE (last) == GOTO_EXPR || TREE_CODE (last) ==  
> LOOP_EXPR)
>          {
>            bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
>            return bsi;
>          }
> 1. Err, LOOP_EXPR is *not* a goto at all.

No, but it behaves exactly as an unconditional 'goto LOOP_BODY', which
by arrangement, is always the next stmt issued when we come out of
tree-ssa, so it essentially always becomes a fallthru. Its a place
holder.

> 2. This causes it to insert *before* the loop expr, when it should be  
> *in* the loop expr.
> This is the edge between the loop_expr and it's body.
> That's *in* the loop_expr, because the end of the src block is the loop  
> expr, and the beginning of the next block is the body.

You seem hung up on treating LOOP_EXPR as something special. There is no
condition in it, nor does it cause any code to be generated. I fail to
see how inserting a stmt immediately in front of a LOOP_EXPR, which is
what inserting on edge (0, 1) will do, isnt what you want. 
> Like so:
> 
> # BLOCK 0.  PRED: -1.  SUCC: 1.
>    pretmp.4_24 = in_9 + 1B; <<<<<<<<<< THIS
>    while (1)
>      {
>  >>>>>>>>> SHOULD REALLY BE HERE
>        # BLOCK 1  
> (/compilerstuff/gcc-rw-ssa/gcc/gcc/testsuite/gcc.c-torture/execute/ 
> 20011126-2.c:25).  PRED: 12 1 0.  SUCC: 1 2.
> 
What I dont understand is why where it is inserted doesn't work for you?
It'll be executed just before entering the loop, which is what the edge
(0,1) represents. Executed only upon entry to the loop.  You are trying
to make LOOP_EXPR more complicated than it is.  

BB0
LOOP_EXPR 
   | 
BB1
  BODY

is funcationally identical to 

BB0
goto loop_body_label;
BB1
loop_body_label:
BODY
goto loop_body_label;

If this was the explicit code you had, inserting on the edge (0,1) would
involve inserting your stmt in front of the goto in BB0.  This is what
we are doing now. The only differnce is we don't expose all the labels,
that way we know the structure of this loop is guaranteed to be well
formed and predictable. And that allows us to not even issue the goto
out of BB0 since we know for a fact that the body is always emitted as
the next stmt.

> 
> If i change the line above to not insert before LOOP_EXPR, I still  
> can't get it to insert where it says "SHOULD REALLY BE HERE" in a way  
> that does what i want.
> 

Of course not, as soon as you step into the LOOP_BODY, the back edge is
going to execute it. Thats why it inserts the stmt in front of the
LOOP_EXPR.


> It does:
>   # BLOCK 0  
> (/compilerstuff/gcc-rw-ssa/gcc/gcc/testsuite/gcc.c-torture/execute/ 
> 20011126-2.c:23).  PRED: -1.  SUCC: 13.
> 
>    while (1)
>      {
>       # BLOCK 13.  PRED: 0.  SUCC: 1.
>    pretmp.4_24 = in_9 + 1B;
> 
>        # BLOCK 1.  PRED: 13 12 1.  SUCC: 1 2.
> 
> *However*, while this looks right at first, it's not.
> The loop back edge is still from 12->1, not 12->13.
> 

Sure doesn't look right to me. you've put your stmt inside the body of
the loop. The CFG in this example looks screwed up now. Its like you are
trying to ignore the while(1) for some reason.

> IE the entire loop is:
> # BLOCK 0  
> (/compilerstuff/gcc-rw-ssa/gcc/gcc/testsuite/gcc.c-torture/execute/ 
> 20011126-2.c:23).  PRED: -1.  SUCC: 13.
> 
>    while (1)
>      {
>       # BLOCK 13.  PRED: 0.  SUCC: 1.
>    pretmp.4_24 = in_9 + 1B;
> 
>        # BLOCK 1.  PRED: 13 12 1.  SUCC: 1 2.
> 
> 	 # BLOCK 12. PRED: 10. SUCC: 1.
> 	}
> 
> Thus, the above, while looking right at first, is entirely equivalent  
> to:
> 
> # BLOCK 0  
> (/compilerstuff/gcc-rw-ssa/gcc/gcc/testsuite/gcc.c-torture/execute/ 
> 20011126-2.c:23).  PRED: -1.  SUCC: 13.
> 
>       # BLOCK 13.  PRED: 0.  SUCC: 1.
>    pretmp.4_24 = in_9 + 1B;
> 
>    while (1)
>      {
>        # BLOCK 1.  PRED: 13 12 1.  SUCC: 1 2.
> 	...
> 	 # BLOCK 12. PRED: 10. SUCC: 1.
> 	}
> 
> Thus, it's not really on the edge between 0 and 1, because if you  
> inserted the code on where it says the edge between 0 and 1 is, it  
> would also cause block 12's successor to be 13, not 1, cause of the  
> semantics of LOOP_EXPR.
> 
> By the by, do you see my point about why i hate LOOP_EXPR now?

No, sorry, totally fail to understand.

> 
> > Tell me what you are trying to do that you are having problems with...
> > Thats the infrastructure we are trying to provide right now... If you
> > present us with cases where we really can't handle it easily, then we
> > consider changing the way we do it. No one wants to use something which
> > is awkward.... so we want to fix it.
> 
> If you can tell me how to convince the edge inserter to really insert  
> where i want, and change the loop so it does what insertion there  
> should do, i'll be happy.
> There is just no way i can handle the redirects and whatnot in PRE  
> cleanly, because we don't even *know* or care what the edge is in in  
> terms of construct.
> 
The edge is treated as a fallthru from the block which ends in the
LOOP_EXPR node... I dont understand the confusion. LOOP_EXPR is a
container node. It does nothing except mark the end of a block because
it's body is guaranteed to have a back edge to the first stmt in the
body.  The LOOP_EXPR node is the marker saying this is the fallthru into
the top of the loop. Maybe it would help if you thought of it as a
macro... Its expands into the LOOP_BODY. The stmt immediately preceeding
the LOOP_EXPR is the last stmt before falling into the BODY of the loop.
The first stmt in the LOOP_BODY is always the target of the backedge at
the end of the LOOP_BODY.

It would be different if the LOOP_EXPR had a condition.... then you
wouldn't be able to insert something between the condition and the loop
body, and that could affect things. But there is no condition...

I really don't understand the difficulty.... It seems perfectly clean to
me. The edge insertion sure works in the out of ssa pass, and it does a
lot of them.

Andrew