[PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 670 bytes --]

If I hack up GCC's old jump threader to avoid threading across backedges 
and instead let the FSM threader handle that case, then we end up with 
cases where the FSM threader creates irreducible loops with marginal 
benefit.

This can be seen in ssa-dom-thread-2{d,e,f}.c.

We've long avoided such threads in the old jump threader.  We generally 
want to avoid them in the FSM threader as well.  The only case where 
we're going to allow them is when we're able to eliminate a multi-way 
branch from the loop.

Bootstrapped and regression tested on x86_64-linux-gnu.  Also tested the 
above mentioned testcases with my hacked up compiler.

Installed on the trunk.

Jeff

[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 2794 bytes --]

commit 518690952b62c1d38b89cdbef0490a7d11f06c40
Author: Jeff Law <law@redhat.com>
Date:   Mon Oct 19 10:23:26 2015 -0600

    [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch
    
    	* tree-ssa-threadupdate.c (valid_jump_thread_path): Reject paths
    	that create irreducible loops unless the path elimiantes a multiway
    	branch.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 89a42c1..ff3d3fc 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2015-10-19  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-threadupdate.c (valid_jump_thread_path): Reject paths
+	that create irreducible loops unless the path elimiantes a multiway
+	branch.
+
 2015-10-19  Richard Biener  <rguenther@suse.de>
 
 	PR tree-optimization/67975
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 5632a88..8e3437a 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2553,11 +2553,31 @@ static bool
 valid_jump_thread_path (vec<jump_thread_edge *> *path)
 {
   unsigned len = path->length ();
+  bool multiway_branch = false;
 
-  /* Check that the path is connected.  */
+  /* Check that the path is connected and see if there's a multi-way
+     branch on the path.  */
   for (unsigned int j = 0; j < len - 1; j++)
-    if ((*path)[j]->e->dest != (*path)[j+1]->e->src)
-      return false;
+    {
+      if ((*path)[j]->e->dest != (*path)[j+1]->e->src)
+        return false;
+      gimple *last = last_stmt ((*path)[j]->e->dest);
+      multiway_branch |= (last && gimple_code (last) == GIMPLE_SWITCH);
+    }
+
+  /* If we are trying to thread the loop latch to a block that does
+     not dominate the loop latch, then that will create an irreducible
+     loop.  We avoid that unless the jump thread has a multi-way
+     branch, in which case we have deemed it worth losing other
+     loop optimizations later if we can eliminate the multi-way branch.  */
+  edge e = (*path)[0]->e;
+  struct loop *loop = e->dest->loop_father;
+  if (!multiway_branch
+      && loop->latch
+      && loop_latch_edge (loop) == e
+      && (determine_bb_domination_status (loop, path->last ()->e->dest)
+	  == DOMST_NONDOMINATING))
+    return false;
 
   return true;
 }
@@ -2650,7 +2670,9 @@ thread_through_all_blocks (bool may_peel_loop_headers)
       if (bitmap_bit_p (threaded_blocks, entry->src->index)
 	  /* Verify that the jump thread path is still valid: a
 	     previous jump-thread may have changed the CFG, and
-	     invalidated the current path.  */
+	     invalidated the current path or the requested jump
+	     thread might create irreducible loops which should
+	     generally be avoided.  */
 	  || !valid_jump_thread_path (path))
 	{
 	  /* Remove invalid FSM jump-thread paths.  */

Re: [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[Hans-Peter Nilsson]

On Mon, 19 Oct 2015, Jeff Law wrote:
> If I hack up GCC's old jump threader to avoid threading across backedges and
> instead let the FSM threader handle that case, then we end up with cases where
> the FSM threader creates irreducible loops with marginal benefit.
>
> This can be seen in ssa-dom-thread-2{d,e,f}.c.
>
> We've long avoided such threads in the old jump threader.  We generally want
> to avoid them in the FSM threader as well.  The only case where we're going to
> allow them is when we're able to eliminate a multi-way branch from the loop.
>
> Bootstrapped and regression tested on x86_64-linux-gnu.  Also tested the above
> mentioned testcases with my hacked up compiler.
>
> Installed on the trunk.

Please do *not* backport this, it causes
unreachable-jump-table-entry issues for cris-elf, breaking build
in newlib.  Although this *is* a manifestation of undue reliance
on assembler broken-dot-word support for this target, I can
imagine similar issues with branches stretched beyond optimal
limit for other targets.

I have no idea whether there's an actual bug related to the
patch or something "just waiting to happen" and 16-bit-offsets
just too close to the limits.  Brief inspection of the generated
assembly-code is, well, "inconclusive".  Also, I'm travelling at
the moment.

<non-inline patch can't be quoted, but it's r228974 on trunk.>

brgds, H-P

Re: [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[Bernd Schmidt]

On 10/21/2015 02:03 AM, Hans-Peter Nilsson wrote:
> <non-inline patch can't be quoted, but it's r228974 on trunk.>

If you're using Thunderbird, you can quote non-inline patches by 
selecting the parts you want to quote before replying.


Bernd

Re: [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[Jeff Law]

On 10/20/2015 06:03 PM, Hans-Peter Nilsson wrote:
> On Mon, 19 Oct 2015, Jeff Law wrote:
>> If I hack up GCC's old jump threader to avoid threading across backedges and
>> instead let the FSM threader handle that case, then we end up with cases where
>> the FSM threader creates irreducible loops with marginal benefit.
>>
>> This can be seen in ssa-dom-thread-2{d,e,f}.c.
>>
>> We've long avoided such threads in the old jump threader.  We generally want
>> to avoid them in the FSM threader as well.  The only case where we're going to
>> allow them is when we're able to eliminate a multi-way branch from the loop.
>>
>> Bootstrapped and regression tested on x86_64-linux-gnu.  Also tested the above
>> mentioned testcases with my hacked up compiler.
>>
>> Installed on the trunk.
>
> Please do *not* backport this, it causes
> unreachable-jump-table-entry issues for cris-elf, breaking build
> in newlib.  Although this *is* a manifestation of undue reliance
> on assembler broken-dot-word support for this target, I can
> imagine similar issues with branches stretched beyond optimal
> limit for other targets.
Not planning to.

>
> I have no idea whether there's an actual bug related to the
> patch or something "just waiting to happen" and 16-bit-offsets
> just too close to the limits.  Brief inspection of the generated
> assembly-code is, well, "inconclusive".  Also, I'm travelling at
> the moment.
Feel free to pass it along when you get back.

jeff

Re: [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[Richard Biener]

On Mon, Oct 19, 2015 at 6:23 PM, Jeff Law <law@redhat.com> wrote:
> If I hack up GCC's old jump threader to avoid threading across backedges and
> instead let the FSM threader handle that case, then we end up with cases
> where the FSM threader creates irreducible loops with marginal benefit.
>
> This can be seen in ssa-dom-thread-2{d,e,f}.c.
>
> We've long avoided such threads in the old jump threader.  We generally want
> to avoid them in the FSM threader as well.  The only case where we're going
> to allow them is when we're able to eliminate a multi-way branch from the
> loop.
>
> Bootstrapped and regression tested on x86_64-linux-gnu.  Also tested the
> above mentioned testcases with my hacked up compiler.
>
> Installed on the trunk.

Note that this fixed some of the size regressions I see on SPEC CPU 2000
but not all, esp. 176.gcc seems to be as bad as before (seen with plain -O2
on x86_64).

Richard.

> Jeff
>
> commit 518690952b62c1d38b89cdbef0490a7d11f06c40
> Author: Jeff Law <law@redhat.com>
> Date:   Mon Oct 19 10:23:26 2015 -0600
>
>     [PATCH] Don't allow FSM threader to create irreducible loops unless it
> eliminates a multi-way branch
>
>         * tree-ssa-threadupdate.c (valid_jump_thread_path): Reject paths
>         that create irreducible loops unless the path elimiantes a multiway
>         branch.
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 89a42c1..ff3d3fc 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,9 @@
> +2015-10-19  Jeff Law  <law@redhat.com>
> +
> +       * tree-ssa-threadupdate.c (valid_jump_thread_path): Reject paths
> +       that create irreducible loops unless the path elimiantes a multiway
> +       branch.
> +
>  2015-10-19  Richard Biener  <rguenther@suse.de>
>
>         PR tree-optimization/67975
> diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
> index 5632a88..8e3437a 100644
> --- a/gcc/tree-ssa-threadupdate.c
> +++ b/gcc/tree-ssa-threadupdate.c
> @@ -2553,11 +2553,31 @@ static bool
>  valid_jump_thread_path (vec<jump_thread_edge *> *path)
>  {
>    unsigned len = path->length ();
> +  bool multiway_branch = false;
>
> -  /* Check that the path is connected.  */
> +  /* Check that the path is connected and see if there's a multi-way
> +     branch on the path.  */
>    for (unsigned int j = 0; j < len - 1; j++)
> -    if ((*path)[j]->e->dest != (*path)[j+1]->e->src)
> -      return false;
> +    {
> +      if ((*path)[j]->e->dest != (*path)[j+1]->e->src)
> +        return false;
> +      gimple *last = last_stmt ((*path)[j]->e->dest);
> +      multiway_branch |= (last && gimple_code (last) == GIMPLE_SWITCH);
> +    }
> +
> +  /* If we are trying to thread the loop latch to a block that does
> +     not dominate the loop latch, then that will create an irreducible
> +     loop.  We avoid that unless the jump thread has a multi-way
> +     branch, in which case we have deemed it worth losing other
> +     loop optimizations later if we can eliminate the multi-way branch.  */
> +  edge e = (*path)[0]->e;
> +  struct loop *loop = e->dest->loop_father;
> +  if (!multiway_branch
> +      && loop->latch
> +      && loop_latch_edge (loop) == e
> +      && (determine_bb_domination_status (loop, path->last ()->e->dest)
> +         == DOMST_NONDOMINATING))
> +    return false;
>
>    return true;
>  }
> @@ -2650,7 +2670,9 @@ thread_through_all_blocks (bool may_peel_loop_headers)
>        if (bitmap_bit_p (threaded_blocks, entry->src->index)
>           /* Verify that the jump thread path is still valid: a
>              previous jump-thread may have changed the CFG, and
> -            invalidated the current path.  */
> +            invalidated the current path or the requested jump
> +            thread might create irreducible loops which should
> +            generally be avoided.  */
>           || !valid_jump_thread_path (path))
>         {
>           /* Remove invalid FSM jump-thread paths.  */
>

Re: [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[Hans-Peter Nilsson]

On Tue, 20 Oct 2015, Jeff Law wrote:
> On 10/20/2015 06:03 PM, Hans-Peter Nilsson wrote:
> > I have no idea whether there's an actual bug related to the
> > patch or something "just waiting to happen" and 16-bit-offsets
> > just too close to the limits.  Brief inspection of the generated
> > assembly-code is, well, "inconclusive".  Also, I'm travelling at
> > the moment.
> Feel free to pass it along when you get back.

Thanks.  Diffstat says the r228974 version is 104 lines less, so
it's not obvious at *that* level and likely looks like an
improvement except for the breakage and stretched jumptables.
I'll open a proper bug-report soonish when less rushed.

JFTR, it's worthwhile to check that we're not missing something
that takes care of "all else equal, keep the target close to the
jumptable".  If we do miss that, that's an obvious enhancement
more or less for all targets.  If we already have that, there's
likely a bug.

brgds, H-P

Re: [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[Jeff Law]

On 10/21/2015 06:05 AM, Hans-Peter Nilsson wrote:
> On Tue, 20 Oct 2015, Jeff Law wrote:
>> On 10/20/2015 06:03 PM, Hans-Peter Nilsson wrote:
>>> I have no idea whether there's an actual bug related to the
>>> patch or something "just waiting to happen" and 16-bit-offsets
>>> just too close to the limits.  Brief inspection of the generated
>>> assembly-code is, well, "inconclusive".  Also, I'm travelling at
>>> the moment.
>> Feel free to pass it along when you get back.
>
> Thanks.  Diffstat says the r228974 version is 104 lines less, so
> it's not obvious at *that* level and likely looks like an
> improvement except for the breakage and stretched jumptables.
> I'll open a proper bug-report soonish when less rushed.
Note that r228974 strictly reduces the number of jump threading paths we 
optimize with the FSM bits.  Essentially it's rejecting cases where 
threading the jump will result in an irreducible loop unless it's able 
to remove a multi-way branch in the loop.

Getting larger code would be a bit of a surprise (due to block 
duplication jump threading often increases code size), but certainly 
isn't impossible.  I certainly had cases where the FSM bits would create 
an irreducible loop, which was then later made reducible by other 
transformations.  Those two-stage kinds of optimizations won't occur 
anymore.

The other possibility is by keeping the loop structure sane, we may be 
getting other loop optimizations such as LICM or strength reduction 
which might be making things larger.



>
> JFTR, it's worthwhile to check that we're not missing something
> that takes care of "all else equal, keep the target close to the
> jumptable".  If we do miss that, that's an obvious enhancement
> more or less for all targets.  If we already have that, there's
> likely a bug.
Jump threading doesn't really have that concept as its occurring much 
earlier in the optimization pipeline.

It does try to avoid useless churn of the CFG and SSA graph, which I've 
noticed is generally good at keeping things from moving around 
unnecessarily.

But again, when you've got the time, pass along a testcase.  I'm happy 
to look at it in detail.

Jeff

Re: [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[Jeff Law]

On 10/21/2015 02:56 AM, Richard Biener wrote:
> On Mon, Oct 19, 2015 at 6:23 PM, Jeff Law <law@redhat.com> wrote:
>> If I hack up GCC's old jump threader to avoid threading across backedges and
>> instead let the FSM threader handle that case, then we end up with cases
>> where the FSM threader creates irreducible loops with marginal benefit.
>>
>> This can be seen in ssa-dom-thread-2{d,e,f}.c.
>>
>> We've long avoided such threads in the old jump threader.  We generally want
>> to avoid them in the FSM threader as well.  The only case where we're going
>> to allow them is when we're able to eliminate a multi-way branch from the
>> loop.
>>
>> Bootstrapped and regression tested on x86_64-linux-gnu.  Also tested the
>> above mentioned testcases with my hacked up compiler.
>>
>> Installed on the trunk.
>
> Note that this fixed some of the size regressions I see on SPEC CPU 2000
> but not all, esp. 176.gcc seems to be as bad as before (seen with plain -O2
> on x86_64).
I haven't started looking at them explicitly yet.  Good to know it 
helped some though.

jeff