From 21f0717ab16fe725e887536f5f90b7487b6431cd Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Thu, 29 Oct 2015 10:20:06 -0600 Subject: [PATCH] [PATCH][PR tree-optimization/67892] Use FSM threader to handle backedges PR tree-optimization/67892 * tree-ssa-threadedge.c (simplify_controL_stmt_condition): Fix typo in comment. (thread_through_normal_block): If we have seen a backedge, then do nothing. No longer call find_jump_threads_backwards here. (thread_across_edge): Use find_jump_threads_backwards to find jump threads if the old style threader was not successful. * tree-ssa-threadbackward.c (get_gimple_control_stmt): Use gsi_last_nondebug_bb. Return NULL if the block does not end with a control statement. (find_jump_threads_backwards): Setup code moved here from tree-ssa-threadedge.c::thread_through_normal_block. Accept single edge argument instead of name & block. * tree-ssa-threadbackward.h (find_jump_threads_backwards): Update prototype. PR tree-optimization/67892 * gcc.dg/tree-ssa/pr21417: Update expected output. * gcc.dg/tree-ssa/ssa-dom-thread-2b.c: Likewise. From-SVN: r229538 --- gcc/ChangeLog | 18 ++++++++ gcc/testsuite/ChangeLog | 6 +++ gcc/testsuite/gcc.dg/tree-ssa/pr21417.c | 2 +- .../gcc.dg/tree-ssa/ssa-dom-thread-2b.c | 5 +-- gcc/tree-ssa-threadbackward.c | 45 ++++++++++++++++--- gcc/tree-ssa-threadbackward.h | 2 +- gcc/tree-ssa-threadedge.c | 33 +++----------- 7 files changed, 73 insertions(+), 38 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 2d42512389c..4fbfea05287 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,21 @@ +2015-10-29 Jeff Law + + PR tree-optimization/67892 + * tree-ssa-threadedge.c (simplify_controL_stmt_condition): Fix typo + in comment. + (thread_through_normal_block): If we have seen a backedge, then + do nothing. No longer call find_jump_threads_backwards here. + (thread_across_edge): Use find_jump_threads_backwards to find + jump threads if the old style threader was not successful. + * tree-ssa-threadbackward.c (get_gimple_control_stmt): Use + gsi_last_nondebug_bb. Return NULL if the block does not end + with a control statement. + (find_jump_threads_backwards): Setup code moved here from + tree-ssa-threadedge.c::thread_through_normal_block. Accept + single edge argument instead of name & block. + * tree-ssa-threadbackward.h (find_jump_threads_backwards): Update + prototype. + 2015-10-29 Tom de Vries * fold-const.c (fold_unary_loc): Remove folding inhibition for restrict diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 9a7d5454e6c..223554ac31a 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2015-10-29 Jeff Law + + PR tree-optimization/67892 + * gcc.dg/tree-ssa/pr21417: Update expected output. + * gcc.dg/tree-ssa/ssa-dom-thread-2b.c: Likewise. + 2015-10-29 Richard Biener PR middle-end/68142 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr21417.c b/gcc/testsuite/gcc.dg/tree-ssa/pr21417.c index b67dd184fb5..fed6b31899c 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr21417.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr21417.c @@ -49,5 +49,5 @@ L23: /* We should thread the backedge to the top of the loop; ie we only execute the if (expr->common.code != 142) test once per loop iteration. */ -/* { dg-final { scan-tree-dump-times "Threaded jump" 1 "dom2" } } */ +/* { dg-final { scan-tree-dump-times "FSM jump thread" 1 "dom2" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2b.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2b.c index 2f17517ea29..909009a7f7c 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2b.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2b.c @@ -25,6 +25,5 @@ void thread_latch_through_header (void) /* Threading the latch to a later point in the loop is safe in this case. And we want to thread through the header as well. These are both caught by threading in DOM. */ -/* { dg-final { scan-tree-dump-not "Jumps threaded" "vrp1"} } */ -/* { dg-final { scan-tree-dump-times "Jumps threaded: 1" 0 "dom1"} } */ -/* { dg-final { scan-tree-dump-times "Jumps threaded: 2" 1 "dom1"} } */ +/* { dg-final { scan-tree-dump-not "Jumps threaded" "dom1"} } */ +/* { dg-final { scan-tree-dump-times "Jumps threaded: 2" 1 "vrp1"} } */ diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index cfb4ace8e9d..90e01dfb2ca 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -37,19 +37,22 @@ along with GCC; see the file COPYING3. If not see static int max_threaded_paths; /* Simple helper to get the last statement from BB, which is assumed - to be a control statement. */ + to be a control statement. Return NULL if the last statement is + not a control statement. */ + static gimple * get_gimple_control_stmt (basic_block bb) { - gimple_stmt_iterator gsi = gsi_last_bb (bb); + gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); if (gsi_end_p (gsi)) return NULL; gimple *stmt = gsi_stmt (gsi); enum gimple_code code = gimple_code (stmt); - gcc_assert (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO); - return stmt; + if (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO) + return stmt; + return NULL; } /* Return true if the CFG contains at least one path from START_BB to END_BB. @@ -340,11 +343,39 @@ fsm_find_control_statement_thread_paths (tree name, finding a path where NAME is a constant, we can thread the path. */ void -find_jump_threads_backwards (tree name, basic_block bb) +find_jump_threads_backwards (edge e) { + if (!flag_expensive_optimizations + || optimize_function_for_size_p (cfun) + || e->dest->loop_father != e->src->loop_father + || loop_depth (e->dest->loop_father) == 0) + return; + + gimple *stmt = get_gimple_control_stmt (e->dest); + if (!stmt) + return; + + enum gimple_code code = gimple_code (stmt); + tree name = NULL; + if (code == GIMPLE_SWITCH) + name = gimple_switch_index (as_a (stmt)); + else if (code == GIMPLE_GOTO) + name = gimple_goto_dest (stmt); + else if (code == GIMPLE_COND) + { + if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME + && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST + && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) + || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) + name = gimple_cond_lhs (stmt); + } + + if (!name || TREE_CODE (name) != SSA_NAME) + return; + vec *bb_path; vec_alloc (bb_path, n_basic_blocks_for_fn (cfun)); - vec_safe_push (bb_path, bb); + vec_safe_push (bb_path, e->dest); hash_set *visited_bbs = new hash_set; max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); @@ -352,4 +383,4 @@ find_jump_threads_backwards (tree name, basic_block bb) delete visited_bbs; vec_free (bb_path); -} +} diff --git a/gcc/tree-ssa-threadbackward.h b/gcc/tree-ssa-threadbackward.h index f055f432dd7..2136ff2620e 100644 --- a/gcc/tree-ssa-threadbackward.h +++ b/gcc/tree-ssa-threadbackward.h @@ -20,6 +20,6 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_TREE_SSA_THREADFSM_H #define GCC_TREE_SSA_THREADFSM_H -extern void find_jump_threads_backwards (tree, basic_block); +extern void find_jump_threads_backwards (edge); #endif /* GCC_TREE_SSA_THREADFSM_H */ diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index 386aea7d8f0..ddd50614fd3 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -566,7 +566,7 @@ simplify_control_stmt_condition (edge e, It is possible to get loops in the SSA_NAME_VALUE chains (consider threading the backedge of a loop where we have - a loop invariant SSA_NAME used in the condition. */ + a loop invariant SSA_NAME used in the condition). */ if (cached_lhs) { for (int i = 0; i < 2; i++) @@ -904,12 +904,10 @@ thread_through_normal_block (edge e, bitmap visited, bool *backedge_seen_p) { - /* If we have traversed a backedge, then we do not want to look - at certain expressions in the table that can not be relied upon. - Luckily the only code that looked at those expressions is the - SIMPLIFY callback, which we replace if we can no longer use it. */ + /* If we have seen a backedge, then we rely solely on the FSM threader + to find jump threads. */ if (*backedge_seen_p) - simplify = dummy_simplify; + return 0; /* We want to record any equivalences created by traversing E. */ if (!handle_dominating_asserts) @@ -1019,26 +1017,6 @@ thread_through_normal_block (edge e, backedge_seen_p); return 1; } - - if (!flag_expensive_optimizations - || optimize_function_for_size_p (cfun) - || !(TREE_CODE (cond) == SSA_NAME - || (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison - && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME - && TREE_CODE (TREE_OPERAND (cond, 1)) == INTEGER_CST)) - || e->dest->loop_father != e->src->loop_father - || loop_depth (e->dest->loop_father) == 0) - return 0; - - /* Extract the SSA_NAME we want to trace backwards if COND is not - already a bare SSA_NAME. */ - if (TREE_CODE (cond) != SSA_NAME) - cond = TREE_OPERAND (cond, 0); - - /* When COND cannot be simplified, try to find paths from a control - statement back through the PHI nodes which would affect that control - statement. */ - find_jump_threads_backwards (cond, e->dest); } return 0; } @@ -1118,6 +1096,8 @@ thread_across_edge (gcond *dummy_cond, path->release (); delete path; + find_jump_threads_backwards (e); + /* A negative status indicates the target block was deemed too big to duplicate. Just quit now rather than trying to use the block as a joiner in a jump threading path. @@ -1217,6 +1197,7 @@ thread_across_edge (gcond *dummy_cond, } else { + find_jump_threads_backwards (path->last ()->e); delete_jump_thread_path (path); } -- 2.30.2