[PATCH][PR tree-optimization/67892] Use FSM threader to handle backedges
Jeff Law
law@redhat.com
Thu Oct 29 16:20:00 GMT 2015
As as been noted in the past, the old jump threader's support for
threading across a loop backedge introduces significant complexity. The
most serious complexity is the need to handle processing statements a
second time (as we come around the top of the loop). This requires
invalidation support, potentially introduces loops in the SSA_NAME_VALUE
chains, etc.
I've speculated for a while that a backwards threader with a more
sensible region copying scheme was the right long term direction.
Sebastian got us started on that direction when he introduced the FSM
threader. Essentially it walks def-use chains backwards from a
conditional to try and find paths where an SSA_NAME has a constant
value. Those paths represent potentially optimizable jump threads and
he's using a SEME region copier to handle the SSA & CFG updates.
BZ67892 is an issue with the old jump threader's backedge handling.
Essentially when we thread across the backedge we're not completely
invaliding the SSA_NAME_VALUE chains -- and it's not entirely clear if
we can properly invalidate them.
So rather than bang my head against the wall writing more code to handle
cases in the old threader of marginal value I've taken this bug as an
opportunity to start exploiting the FSM threader more heavily.
The patches to date have been improving the FSM threader to handle cases
it missed, or where we really didn't want it to change the CFG. This
patch actually disables the old threader's backedge handling and
exclusively relies on the FSM threader to pick up those opportunities.
Bootstrapped and regression tested on x86_64-linux-gnu. Applied to the
trunk.
Next step is to start removing the now dead code from the old threader :-)
Jeff
-------------- next part --------------
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a088c13..430d361 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,21 @@
+2015-10-29 Jeff Law <law@redhat.com>
+
+ 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 Richard Biener <rguenther@suse.de>
PR middle-end/68142
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 9a7d545..223554a 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2015-10-29 Jeff Law <law@redhat.com>
+
+ 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 <rguenther@suse.de>
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 b67dd18..fed6b31 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 2f17517..909009a 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 cfb4ace..90e01df 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 <gswitch *> (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<basic_block, va_gc> *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<basic_block> *visited_bbs = new hash_set<basic_block>;
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 f055f43..2136ff2 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 386aea7..ddd5061 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);
}
More information about the Gcc-patches
mailing list