This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]