[tree-ssa] Insert on edge comment

[Daniel Berlin]

On Monday, June 2, 2003, at 06:09  PM, Andrew MacLeod wrote:

> On Mon, 2003-06-02 at 17:44, Daniel Berlin wrote:
>>
>>
>> On Mon, 2 Jun 2003, Chris Lattner wrote:
>>
>>> On Mon, 2 Jun 2003, [iso-8859-1] Pop Sébastian wrote:
>>>
>>>> This is the facet of "instruction stream controlled by the CFG",  
>>>> rather
>>>> than the classic view of "trees over which we keep up to date the  
>>>> CFG".
>>>>
>>>> If I'm not wrong this is still one of the major advantages of the
>>>> representation that LLVM has over the current status of tree-ssa.   
>>>> Chris?
>>>
>>> Yup, this is how we do it in LLVM.  It was worked out quite well for  
>>> us,
>>> and makes things like successors/predecessors of a basic block  
>>> extremely
>>> easy to find... making just about every CFG based analysis and
>>> optimization simpler.  I highly recommend things like loop  
>>> expressions, if
>>> expressions and switch statements be lowered down into the equivilent
>>> "conditional branch", "unconditional branch", and "multi-way branch"
>>> instructions...
>>
>> This would solve the whole fun with "insert after while statement at  
>> end
>> of block" stuff i deal with.
>> It's only because of the special semantics of the "while" statement  
>> that
>> this occurs in the first place.
>> If it was just a simple jump, we'd insert before. But it's a whole  
>> magic
>> expression with a body and whatnot.
>
>
> 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.
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.
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.


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.

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.

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?

> 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.

> Andrew
>