Re: [patch] fix PR65048: check that jump-thread paths are still valid

[Jeff Law]

On 02/25/15 11:37, Sebastian Pop wrote:
Jeff Law wrote:
    Registering FSM jump thread: (10, 12)  (12, 13)  (13, 15)  (15, 3)
[ snip ]
    Registering FSM jump thread: (7, 10)  (10, 12)  (12, 13)  (13, 14)

What I'm having a bit of trouble wrapping my head around is how can
those two paths both be valid when you register them?  They have
different transitions out of bb13, one going to bb15 the other to
bb14, but they're both coming in via (10, 12).

Here is the output of debug_loops(3) showing the two paths before we start the
FSM code generation:

     bb_7 (preds = {bb_4 }, succs = {bb_8 bb_10 bb_11 })
     {
     <L26>:
       # .MEM_26 = VDEF <.MEM_1>
       a = 84;
       switch (x_8(D)) <default: <L24>, case 65: <L12>, case 85: <L4>>
     }
     bb_10 (preds = {bb_9 bb_5 bb_7 }, succs = {bb_12 })
     {
       # .MEM_30 = PHI <.MEM_4(9), .MEM_20(5), .MEM_26(7)>
       # _34 = PHI <_7(9), 65(5), 84(7)>
     <L12>:
       goto <bb 12> (<L10>);
     }
     bb_12 (preds = {bb_9 bb_11 bb_10 }, succs = {bb_3 bb_13 })
     {
       # _13 = PHI <_12(9), 65(11), 84(10)>
       # .MEM_32 = PHI <.MEM_4(9), .MEM_31(11), .MEM_30(10)>
       # _36 = PHI <_7(9), _35(11), _34(10)>
     <L10>:
       # .MEM_6 = VDEF <.MEM_32>
       b = _13;
       # VUSE <.MEM_6>
       c.0_10 = c;
       switch (c.0_10) <default: <L20>, case 85: <L14>>
     }
     bb_13 (preds = {bb_12 }, succs = {bb_14 bb_15 })
     {
     <L14>:
       switch (_36) <default: <L15>, case 71: <L16>>
     }
     bb_14 (preds = {bb_13 bb_6 bb_8 }, succs = {bb_15 })
     {
       # .MEM_33 = PHI <.MEM_6(13), .MEM_23(6), .MEM_28(8)>
       # _37 = PHI <_36(13), 65(6), 84(8)>
       # _39 = PHI <_13(13), _12(6), _12(8)>
     <L15>:
       # .MEM_18 = VDEF <.MEM_33>
       fn ();
     }
     bb_15 (preds = {bb_13 bb_14 }, succs = {bb_3 bb_16 })
     {
       # .MEM_17 = PHI <.MEM_6(13), .MEM_18(14)>
       # _38 = PHI <_36(13), _37(14)>
       # _40 = PHI <_13(13), _39(14)>
     <L16>:
       switch (_40) <default: <L20>, case 65: <L17>>
     }
     bb_3 (preds = {bb_16 bb_15 bb_12 bb_6 bb_8 }, succs = {bb_4 })
     {
       # .MEM_3 = PHI <.MEM_19(16), .MEM_17(15), .MEM_6(12), .MEM_23(6), 
.MEM_28(8)>
       # _9 = PHI <_38(16), _38(15), _36(12), 65(6), 84(8)>
       # _16 = PHI <65(16), _40(15), _13(12), _12(6), _12(8)>
     <L20>:
     }

First, let's look at why we jump thread from 10 to 3:
    Registering FSM jump thread: (10, 12)  (12, 13)  (13, 15)  (15, 3)

In other words, let's see how we can infer that "from bb_15 we are guaranteed to
jump into bb_3 if we come from bb_10."

So this switch in bb_15 is guaranteed to jump to the default case:
switch (_40) <default: <L20>, case 65: <L17>>

  # _40 = PHI <_13(13), _39(14)>

because when coming from bb_13, "_40 = _13", and then in bb_12 we have the 
definition
# _13 = PHI <_12(9), 65(11), 84(10)>

and so if we come from bb_10, the value of _13 is 84.
Because 84 != 65, switch (_40) will switch to default, that is a jump from 
bb_15 to bb_3.


Now let's see how we jump thread from 7 to 14:
    Registering FSM jump thread: (7, 10)  (10, 12)  (12, 13)  (13, 14)

Why do we know that from bb_13 we necessarily jump to bb_14 if we have just
executed the code in bb_7?

In other words, why do we jump to the default case of
switch (_36) <default: <L15>, case 71: <L16>>

# _36 = PHI <_7(9), _35(11), _34(10)>
# _34 = PHI <_7(9), 65(5), 84(7)>

so coming from bb_7, the value of the switch is 84 that is different than case 
71,
so we jump to the default case in "switch (_36) <default: <L15>, case 71: 
<L16>>".

let's make sure the paths that are registered are reasonable first

I think it is reasonable to jump thread these two paths.
So this is why the debugging output is so important ;-)  We might 
consider further enhancing the debug output to mark the state of each of 
those intermediate blocks, of particular importance is whether or not 
the block has a known static destination on the path.

In this test, the branch out of 13 is not known statically in the first 
path,but is known in the second path.  Thus 13' in the first path will 
continue to have a conditional branch (to 14 or 15' where 15' always 
goes to 3).  13'' in the second path will unconditionally transfer to 14.

So, now time for me to go read that patch thoroughly.

Thanks,

jeff