Re: [tree-ssa] edge insertion/split problem

[Andrew MacLeod <amacleod at redhat dot com>]

On Mon, 2003-06-16 at 15:44, law@redhat.com wrote:
> 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.
> 


OH, never mind, I see,  I got temporarily confused by the MT VUSE gorp
:-) Never mind, Block 7 ends with a switch. DOh. DOh. DOh. 

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


The problem we are having here is the code to handle switch stmt's is
assuming the edge from SWITCH is going to a CASE.  IN this example,
there is an edge to the fallthrough block. Hmm. No empty default case
huh? that would be nice and consistant. I wasn't thinking we ever had to
deal with SWITCH->fallthrough case. Clearly that will need to be handled
differently.

umm. So that should be the only edge from the SWITCH block marked
FALLTHRU right?

If so, then it can be handled without too much hassle, and yes, we'll
need to insert goto's from all the cases.. what a pain. Are you sure we
don't just want to always have a "default" case block? :-) 

 Actually, maybe that is the easiest way to do it. We add an ELSE block
on the fallthrough edge from a COND_EXPR if one doesn't exist. If a
FALLTHRU block exists for a SWITCH, that means there is no default case
right? So we can turn any code on that edge into a DEFAULT case... n'est
pas?  Then no farting around with goto's.

DO I have to fudge much crap to do that?. I suppose the last case in the
switch might need a 'break' goto inserted. 
- Find the last stmt in the last case.. is there a simple way to do
that?) 
- if it isn't a 'goto', add a 'goto the label in DEST block'.
- Create new block. Add default case. Insert code here. 

When I change the edge from the switch to the default case, do I need to
do anything else to have it recognize it, or is that it?



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

What if the block ends in a COND_EXPR....(the if has no else, so it a
fallthu on that path), then there is no place to stick a goto. Or maybe
its a fallthrough from another switch on the other part of a conditional
branch.. Ive discovered incoming edges can come from just about anything
in any context (almost). ick.

Thats why I handle each case individually, this is just a situation I
wasn't expecting :-)

I think I prefer to handle it by adding a default: case, unless there is
strong objection. Then we keep the "nice clean" structure of the switch
:-) ha.



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

Yeah, I was thinking of labels, not the fallthrough.

> 
>  >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 :-)


I think I;ll just send you a patch later for the first try :-)

Andrew