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

[Sebastian Pop <sebpop at gmail dot com>]

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.

Sebastian