This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Improve backwards threading
On Tue, 9 Aug 2016, Richard Biener wrote:
> On Fri, 5 Aug 2016, Jeff Law wrote:
>
> > On 08/05/2016 07:36 AM, Richard Biener wrote:
> > > @@ -560,6 +562,14 @@ fsm_find_control_statement_thread_paths
> > > edge taken_edge = profitable_jump_thread_path (path, bbi, name,
> > > arg);
> > > if (taken_edge)
> > > {
> > > + /* If the taken edge is a loop entry avoid mashing two
> > > + loops into one with multiple latches by splitting
> > > + the edge. This only works if that block won't become
> > > + a latch of this loop. */
> > > + if ((bb_loop_depth (taken_edge->src)
> > > + < bb_loop_depth (taken_edge->dest))
> > > + && ! single_succ_p (bbi))
> > > + split_edge (taken_edge);
> > > if (bb_loop_depth (taken_edge->src)
> > > >= bb_loop_depth (taken_edge->dest))
> > > convert_and_register_jump_thread_path (path, taken_edge);
> > >
> > > note you need the PR72772 fix to trigger all this.
> > I'm a little confused here. In the case where the taken edge goes into a
> > deeper loop nest you're splitting the edge -- to what end? The backwards
> > threader isn't going to register that jump thread. So if this is fixing
> > something, then we've got the fix in the wrong place.
>
> Ok, so I've figured that splitting the edge is indeed pointless unless
> it does exactly the same as creating a forwarder. We may not blindly
> thread backwards to a loop header because of correctness issues in
> re-using old loop meta-data for that loop (and in the
> ubsan.exp=pr71403-2.c case miscompiling the testcase). What we need
> is a forwarder block we can thread to which eventually becomes the
> new loop header. Note this is also what we'd achieve with properly
> initializing loops in the threader - sth we should do anyway with
> looking at loop meta data. This is likely also why the old threader has
> (in DOM):
>
> /* We need to know loop structures in order to avoid destroying them
> in jump threading. Note that we still can e.g. thread through loop
> headers to an exit edge, or through loop header to the loop body,
> assuming
> that we update the loop info.
>
> TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
> to several overly conservative bail-outs in jump threading, case
> gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
> missing. We should improve jump threading in future then
> LOOPS_HAVE_PREHEADERS won't be needed here. */
> loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
>
> thus we run into exactly those cases now in the FSM threader. Thus
> the following patch fixes the two testcases with the PR72772 fix
> applied as well.
>
> It's also possible to create a forwarder on-demand at the place I
> splitted the edge and avoid creating preheaders for all loops but I
> as we should init the loop optimizer to be able to look at loop
> metadata anyway there's not much point in doing that.
>
> Bootstrap / regtest pending on x86_64-unknown-linux-gnu, ok for trunk?
I have now applied this as follows (gcc.dg/tree-ssa/ssa-dom-thread-7.c
needed adjustment).
Bootstrapped / tested on x86_64-unknown-linux-gnu.
Richard.
2016-08-11 Richard Biener <rguenther@suse.de>
* tree-ssa-threadbackward.c (pass_data_thread_jumps): Remove
unconditional TODO_cleanup_cfg.
(pass_thread_jumps::execute): Initialize loops, perform a CFG
cleanup only if we threaded a jump.
* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Adjust.
Index: gcc/tree-ssa-threadbackward.c
===================================================================
*** gcc/tree-ssa-threadbackward.c (revision 239276)
--- gcc/tree-ssa-threadbackward.c (working copy)
*************** const pass_data pass_data_thread_jumps =
*** 674,680 ****
0,
0,
0,
! ( TODO_cleanup_cfg | TODO_update_ssa ),
};
class pass_thread_jumps : public gimple_opt_pass
--- 674,680 ----
0,
0,
0,
! TODO_update_ssa,
};
class pass_thread_jumps : public gimple_opt_pass
*************** pass_thread_jumps::gate (function *fun A
*** 699,704 ****
--- 699,706 ----
unsigned int
pass_thread_jumps::execute (function *fun)
{
+ loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
+
/* Try to thread each block with more than one successor. */
basic_block bb;
FOR_EACH_BB_FN (bb, fun)
*************** pass_thread_jumps::execute (function *fu
*** 706,713 ****
if (EDGE_COUNT (bb->succs) > 1)
find_jump_threads_backwards (bb);
}
! thread_through_all_blocks (true);
! return 0;
}
}
--- 708,717 ----
if (EDGE_COUNT (bb->succs) > 1)
find_jump_threads_backwards (bb);
}
! bool changed = thread_through_all_blocks (true);
!
! loop_optimizer_finalize ();
! return changed ? TODO_cleanup_cfg : 0;
}
}
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c (revision 239276)
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c (working copy)
@@ -1,8 +1,9 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-thread1-stats -fdump-tree-thread2-stats -fdump-tree-thread3-stats -fdump-tree-dom3-stats -fdump-tree-vrp2-stats -fno-guess-branch-probability" } */
+/* { dg-options "-O2 -fdump-tree-thread1-stats -fdump-tree-thread2-stats -fdump-tree-dom2-stats -fdump-tree-thread3-stats -fdump-tree-dom3-stats -fdump-tree-vrp2-stats -fno-guess-branch-probability" } */
/* { dg-final { scan-tree-dump "Jumps threaded: 16" "thread1" } } */
-/* { dg-final { scan-tree-dump "Jumps threaded: 6" "thread2" } } */
+/* { dg-final { scan-tree-dump "Jumps threaded: 9" "thread2" } } */
/* { dg-final { scan-tree-dump "Jumps threaded: 3" "thread3" } } */
+/* { dg-final { scan-tree-dump-not "Jumps threaded" "dom2" } } */
/* { dg-final { scan-tree-dump-not "Jumps threaded" "dom3" } } */
/* { dg-final { scan-tree-dump-not "Jumps threaded" "vrp2" } } */