[tree-ssa] edge insertion/split problem

[law at redhat dot com]

Let's consider the following:

  # BLOCK 7.  PRED: 36 6.  SUCC: 9 8 10.
  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_196 = l_getc ();
  (void)0;
  switch (T.125_196)
    {
      {
        
        # BLOCK 8 (/speedy/virgin-tree-ssa/libf2c/libI77/lread.c:133).  PRED: 
7.  SUCC: 9.
        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_192 = (char)T.125_196;
        sp_206 = sp_192 + 1B;
        (void)0;
        spe_208 = spe_194 + 1B;
        
        # BLOCK 9 (/speedy/virgin-tree-ssa/libf2c/libI77/lread.c:137).  PRED: 
7 8.  SUCC: 10.
        #   f__lcount_4 = PHI <f__lcount_3(7), f__lcount_200(8)>;
        #   f__llx_14 = PHI <f__llx_13(7), f__llx_201(8)>;
        #   f__ltype_27 = PHI <f__ltype_26(7), f__ltype_202(8)>;
        #   sp_51 = PHI <sp_192(7), sp_206(8)>;
        #   sp1_62 = PHI <sp_192(7), sp_206(8)>;
        #   spe_68 = PHI <spe_194(7), spe_208(8)>;
        #   .GLOBAL_VAR_78 = PHI <.GLOBAL_VAR_197(7), .GLOBAL_VAR_205(8)>;
        #   MT.6_114 = PHI <MT.6_113(7), MT.6_199(8)>;
        #   f__lx_143 = PHI <f__lx_142(7), f__lx_203(8)>;
        #   f__lquit_153 = PHI <f__lquit_152(7), f__lquit_204(8)>;
        case 43:;
        
        #   .GLOBAL_VAR_210 = VDEF <.GLOBAL_VAR_78>;
        #   VUSE <MT.6_114>;
        #   VUSE <.GLOBAL_VAR_78>;
        ch_209 = l_getc ()
      }
    };
  
  # 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).

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:



  # 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
and the label <ULc40> should have been inserted immediately before block #10.
The copies ch = T.125 and sp1 = sp should have been inserted immediately
after the switch statement.


FWIW, this is blocking the EH cleanup patch.

Jeff