This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] fix PR65048: check that jump-thread paths are still valid
- From: Sebastian Pop <sebpop at gmail dot com>
- To: Jeff Law <law at redhat dot com>
- Cc: "Brian M. Rzycki" <brzycki at gmail dot com>, gcc-patches at gcc dot gnu dot org
- Date: Wed, 25 Feb 2015 18:37:49 +0000
- Subject: Re: [patch] fix PR65048: check that jump-thread paths are still valid
- Authentication-results: sourceware.org; auth=none
- References: <20150213235033 dot GA20179 at f1 dot c dot bardezibar dot internal> <54E2E67D dot 7030109 at redhat dot com> <20150218222723 dot GA24606 at f1 dot c dot bardezibar dot internal> <54EBB147 dot 2080400 at redhat 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