[tree-ssa] edge insertion/split problem

[Andrew MacLeod]

On Mon, 2003-06-16 at 13:09, law@redhat.com wrote:
> 
> Let's consider the following:
> 
>   # BLOCK 7.  PRED: 36 6.  SUCC: 9 8 10.
>   retry:;;
>   
<...>
>   
>   # BLOCK 10 (/speedy/virgin-tree-ssa/libf2c/libI77/lread.c:140).  PRED: 9 7.  
> SUCC: 11.
>   #   f__lcount_5 = PHI <f__lcount_3(7), f__lcount_4(9)>;
>   #   f__llx_15 = PHI <f__llx_13(7), f__llx_14(9)>;
>   #   f__ltype_28 = PHI <f__ltype_26(7), f__ltype_27(9)>;
>   #   sp_52 = PHI <sp_192(7), sp_51(9)>;
>   #   sp1_63 = PHI <sp_192(7), sp1_62(9)>;
>   #   spe_69 = PHI <spe_194(7), spe_68(9)>;
>   #   .GLOBAL_VAR_79 = PHI <.GLOBAL_VAR_197(7), .GLOBAL_VAR_210(9)>;
>   #   ch_100 = PHI <T.125_196(7), ch_209(9)>;
>   #   MT.6_115 = PHI <MT.6_113(7), MT.6_114(9)>;
>   #   f__lx_144 = PHI <f__lx_142(7), f__lx_143(9)>;
>   #   f__lquit_154 = PHI <f__lquit_152(7), f__lquit_153(9)>;
>   while (1)
> 
> Of particular interest is ch_* and T.125*
> 
> Now the first thing I noticed is that they aren't coalesced.  I haven't
> dug deeply into that, though I do happen to know that "T125" shouldn't
> conflict with any version of "ch".  It's probably worth noting that T.125
> has precisely one version, which we seem to handle specially which may
> somehow be preventing it from coalescing.  Assume that all versions of "ch"
> will coalesce (they do).
>

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.

> Anyway, that's not the real problem, the real problem is our edge insertion
> code mucks things up.
> 
> Given that T125 and ch will not coalesce, we can determine that we will
> need to insert a copy from T125 to ch on the edge from block 7 to block 10.
> 
> 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?

> 
> 
>   # BLOCK 7.  PRED: 36 6.  SUCC: 152 8 154.
>   retry:;;
>   
>   #   VUSE <MT.6_113>;
>   #   VUSE <.GLOBAL_VAR_77>;
>   sp = &s;
>   (void)0;
>   spe = sp + 40B;
>   havenum = 0;
>   
>   #   .GLOBAL_VAR_197 = VDEF <.GLOBAL_VAR_77>;
>   #   VUSE <MT.6_113>;
>   #   VUSE <.GLOBAL_VAR_77>;
>   T.125 = l_getc ();
>   (void)0;
>   switch (T.125)
>     {
>       {
>         
>         # BLOCK 8 (/speedy/virgin-tree-ssa/libf2c/libI77/lread.c:133).  PRED: 
> 7.  SUCC: 153.
>         case 45:;
>         
>         #   MT.6_199 = VDEF <MT.6_113>;
>         #   f__lcount_200 = VDEF <f__lcount_3>;
>         #   f__llx_201 = VDEF <f__llx_13>;
>         #   f__ltype_202 = VDEF <f__ltype_26>;
>         #   f__lx_203 = VDEF <f__lx_142>;
>         #   f__lquit_204 = VDEF <f__lquit_152>;
>         #   .GLOBAL_VAR_205 = VDEF <.GLOBAL_VAR_197>;
>         *sp = (char)T.125;
>         sp = sp + 1B;
>         (void)0;
>         spe = spe + 1B;
>         sp1 = sp;
>         
>         # BLOCK 153.  PRED: 8.  SUCC: 9.
>         goto <ULbd0>;;
>         
>         # BLOCK 152 (/speedy/virgin-tree-ssa/libf2c/libI77/lread.c:137).  
> PRED: 7.  SUCC: 9.
>         case 43:;
>         sp1 = sp;
>         
>         # BLOCK 9.  PRED: 153 152.  SUCC: 155.
>         <ULbd0>:;;
>         
>         #   .GLOBAL_VAR_210 = VDEF <.GLOBAL_VAR_78>;
>         #   VUSE <MT.6_114>;
>         #   VUSE <.GLOBAL_VAR_78>;
>         ch = l_getc ()
>       }
>     };
>   
>   # BLOCK 155.  PRED: 9.  SUCC: 10.
>   goto <ULc40>;;
>   
>   # BLOCK 10 (/speedy/virgin-tree-ssa/libf2c/libI77/lread.c:140).  PRED: 155 
> 154.  SUCC: 11.
>   <ULc40>:;;
> 
>   # BLOCK 154.  PRED: 7.  SUCC: 10.
>   ch = T.125;
>   sp1 = sp;
>   
>   # BLOCK 10 (/speedy/virgin-tree-ssa/libf2c/libI77/lread.c:140).  PRED: 155 
> 154.  SUCC: 11.
>   while (1)
> 
> 
> 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.


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

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

So you got a testcase for this? In any case, tell me about RETRY...

Andrew