[tree-ssa] edge insertion/split problem

[law@redhat.com]

In message <1055785318.17240.380.camel@p4>, Andrew MacLeod writes:
 >> Let's consider the following:
 >> 
 >>   # BLOCK 7.  PRED: 36 6.  SUCC: 9 8 10.
 >>   retry:;;
 >>   
 ><...>
 >>   
 >We currently make no attempts to coalesce things that originate in
 >seperate storage.. 'ch' and T.125 are seperate variables, we leave them
 >that way. You'll always get the copy. Someday I'll consider looking at
 >seperate local variables and consider coalescing them is we see a copy
 >between them, but right now we don't.
OK.

 >> That edge is a critical edge (block 7 has more than one successor and block
 >> 10 has more than one predecessor).  Meaning we'll need to split the edge.
 >> 
 >> This is a rather nasty case for edge splitting.  I think the right way to
 >> split this edge is to put a goto at the end of block 9 to the start of 
 >> block 10 (creating the label at the start of block #10).  Then you can
 >> insert our copy after the switch statement.
 >> 
 >> Instead we did some "interesting" things:
 >> 
 >Well, it trying to do the right thing :-) It just doesn't understand
 >what a RETRY is.  We need a case in find_insert_location for RETRY.
 >
 >What is a retry anyway?
 >
?!?  It's just a user label and unimportant for this problem as far
as I can tell.


 >> I think the goto <ULc40> should have been inserted at the end of block #9
 >
 >Well, we have to put the goto in the fallthru from the switch. There
 >could be more than one edge coming into block 10, (or if the switch were
 >an IF THEN ELSE fer instance)  so it easier to simply put a goto in that
 >fallthru location all the time, and jump around what use to be the
 >falthru.
I don't see how that can work.  What we effectively have is something like
this:

           7
          /|\
         / | \
        8  |  |
         \ |  |
          \|  |
           9  |
            \ /
             10

[ All control flow down. ]



Where block 7 is the code up to and including the jump for the switch.
Block 8 & 9 are case statements in the switch
Block 10 is the code immediately after the switch.

7->10 and 9->10 are both fall-thru edges.

If you're going to insert on the edge from 7->10 in this graph, you must
modify block 9.  I can't see any sensible alternatives.

It seems to me the simplistic approach for inserting on a critical edge
A->B is to look at all the preds of B, except A and for each of those
preds that does not explicitly jump to B, insert an explicit jump to B.

Then you insert whatever code you wanted on the path from A->B immediately
before the label which starts block B (since you have explicit jumps, you
know it'll have a label now).  If A falls through to B, then you're done.
Otherwise you need to revector the jump at the end of A.


 >
 >So its trying to generate:
 >
 >   BLOCK 155
 >     goto LAB
 >  BLOCK 10:
 >     ch = T.125
 >     sp1 = sp
 >  BLOCK 154
 >   LAB
 >   whioe (1)
 >
 >Its just not doing a very good job at it. Im not sure why you got 2
 >BLOCK 10's there... Thats pretty screwy :-)
I can't see how that's going to work.  Once you get to block 7, you're
unconditionally going to get to block 155, meaning you'll unconditionally
get to block 154 -- totally bypassing block 10.


 >So block 7 ends in a RETRY?
 >
 >Whats a retry?  We have to teach the edge inserter what to do when block
 >ends in that. Tell me it doesn't look like a simple call :-)
Ignore the retry.  It's a total red herring.


 >So you got a testcase for this? In any case, tell me about RETRY...
Only if you're willing to hack up your compiler in fun and interesting
ways :-)
jeff