On Mon, Oct 19, 2015 at 6:23 PM, Jeff Law <l...@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 <l...@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 <l...@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 <rguent...@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. */
>
