From bac0f2a390048652910f77503b21b3e208daeae1 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <s.pop@samsung.com>
Date: Fri, 26 Sep 2014 14:54:20 -0500
Subject: [PATCH] jump thread for PR 54742
Adapted from a patch from James Greenhalgh.
* tree-ssa-threadedge.c (simplify_control_stmt_condition): Restore the
original value of cond when simplification fails.
(find_thread_path): New.
(find_control_statement_thread_paths): New.
(thread_through_normal_block): Call find_control_statement_thread_paths.
* testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c: New.
---
gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c | 32 ++++
gcc/tree-ssa-threadedge.c | 180 ++++++++++++++++++++++-
gcc/tree-ssa-threadupdate.c | 4 +
3 files changed, 215 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
new file mode 100644
@@ -0,0 +1,32 @@
+int sum0, sum1, sum2, sum3;
+int foo(char * s, char** ret)
+{
+ int state=0;
+ char c;
+
+ for (; *s && state != 4; s++)
+ {
+ c = *s;
+ if (c == '*')
+ {
+ s++;
+ break;
+ }
+ switch (state) {
+ case 0:
+ if (c == '+') state = 1;
+ else if (c != '-') sum0+=c;
+ break;
+ case 1:
+ if (c == '+') state = 2;
+ else if (c == '-') state = 0;
+ else sum1+=c;
+ break;
+ default:
+ break;
+ }
+
+ }
+ *ret = s;
+ return state;
+}
@@ -628,6 +628,7 @@ simplify_control_stmt_condition (edge e,
rather than use a relational operator. These are simpler to handle. */
if (TREE_CODE (cond) == SSA_NAME)
{
+ tree original_lhs = cond;
cached_lhs = cond;
/* Get the variable's current value from the equivalence chains.
@@ -656,6 +657,12 @@ simplify_control_stmt_condition (edge e,
pass specific callback to try and simplify it further. */
if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
cached_lhs = (*simplify) (stmt, stmt);
+
+ /* We couldn't find an invariant. But, callers of this
+ function may be able to do something useful with the
+ unmodified destination. */
+ if (!cached_lhs)
+ cached_lhs = original_lhs;
}
else
cached_lhs = NULL;
@@ -915,6 +922,155 @@ thread_around_empty_blocks (edge taken_edge,
return false;
}
+/* Return true if there is at least one path from START_BB to END_BB.
+ VISITED_BBS is used to make sure we don't fall into an infinite loop. */
+
+static bool
+find_thread_path (basic_block start_bb, basic_block end_bb,
+ vec<basic_block, va_gc> *&path,
+ hash_set<basic_block> *visited_bbs)
+{
+ if (start_bb == end_bb)
+ {
+ vec_safe_push (path, start_bb);
+ return true;
+ }
+
+ if (!visited_bbs->add(start_bb))
+ {
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, start_bb->succs)
+ if (find_thread_path (e->dest, end_bb, path, visited_bbs))
+ {
+ vec_safe_push (path, start_bb);
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/* We trace the value of the variable EXPR back through any phi nodes looking
+ for places where it gets a constant value and save the path. */
+
+static void
+find_control_statement_thread_paths (tree expr,
+ hash_set<gimple> *visited_phis,
+ vec<basic_block, va_gc> *&path)
+{
+ tree var = SSA_NAME_VAR (expr);
+ gimple def_stmt = SSA_NAME_DEF_STMT (expr);
+ basic_block var_bb = gimple_bb (def_stmt);
+
+ if (var == NULL || var_bb == NULL)
+ return;
+
+ vec<basic_block, va_gc> *next_path;
+ vec_alloc (next_path, n_basic_blocks_for_fn (cfun));
+
+ basic_block last_bb_in_path = path->last ();
+
+ /* Put the path from var_bb to last_bb_in_path into next_path. */
+ if (var_bb != last_bb_in_path)
+ {
+ edge e;
+ int e_count = 0;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, last_bb_in_path->preds)
+ {
+ hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
+
+ if (find_thread_path (var_bb, e->src, next_path, visited_bbs))
+ e_count = e_count + 1;
+
+ delete visited_bbs;
+
+ /* If there is more than one path, stop. */
+ if (e_count > 1)
+ {
+ vec_free (next_path);
+ return;
+ }
+ }
+ }
+
+ /* Visit PHI nodes once. */
+ if (gimple_code (def_stmt) != GIMPLE_PHI
+ || visited_phis->add(def_stmt)) {
+ vec_free (next_path);
+ return;
+ }
+
+ /* Append all the nodes from next_path to path. */
+ vec_safe_splice (path, next_path);
+ gcc_assert (path->last () == var_bb);
+
+ /* Iterate over the arguments of PHI. */
+ unsigned int i;
+ for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
+ {
+ tree arg = gimple_phi_arg_def (def_stmt, i);
+ basic_block bbi = gimple_phi_arg_edge (def_stmt, i)->src;
+
+ /* Skip edges pointing outside the current loop. */
+ if (!arg || var_bb->loop_father != bbi->loop_father)
+ continue;
+
+ /* Add BBI to the path. */
+ vec_safe_push (path, bbi);
+
+ if (TREE_CODE (arg) == INTEGER_CST)
+ {
+ int j, n = path->length ();
+ vec<jump_thread_edge *> *jump_thread_path
+ = new vec<jump_thread_edge *> ();
+ int joiners = 0;
+
+ for (j = 0; j < n - 1; j++)
+ {
+ edge e = find_edge ((*path)[n - j - 1],
+ (*path)[n - j - 2]);
+ gcc_assert (e);
+ enum jump_thread_edge_type kind;
+
+ if (j == 0)
+ kind = EDGE_START_JUMP_THREAD;
+ else if (single_pred_p (e->src))
+ kind = EDGE_NO_COPY_SRC_BLOCK;
+ else {
+ kind = EDGE_COPY_SRC_JOINER_BLOCK;
+ ++joiners;
+ }
+
+ jump_thread_edge *x = new jump_thread_edge (e, kind);
+ jump_thread_path->safe_push (x);
+ }
+
+ /* Add the edge taken when the control variable has value ARG. */
+ edge taken_edge = find_taken_edge ((*path)[0], arg);
+ jump_thread_edge *x
+ = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+ jump_thread_path->safe_push (x);
+
+ /* Thread-update does not handle more than two joiners. A path with
+ less than 3 nodes should not be jump-threaded. */
+ if (joiners < 2 && n > 2)
+ register_jump_thread (jump_thread_path);
+ }
+ else if (TREE_CODE (arg) == SSA_NAME)
+ find_control_statement_thread_paths (arg, visited_phis, path);
+
+ /* Remove BBI from the path. */
+ path->pop ();
+ }
+
+ /* Remove all the nodes that we added from next_path. */
+ vec_safe_truncate (path, (path->length () - next_path->length ()));
+ vec_free (next_path);
+}
+
/* We are exiting E->src, see if E->dest ends with a conditional
jump which has a known value when reached via E.
@@ -1000,7 +1156,10 @@ thread_through_normal_block (edge e,
cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
handle_dominating_asserts);
- if (cond && is_gimple_min_invariant (cond))
+ if (!cond)
+ return 0;
+
+ if (is_gimple_min_invariant (cond))
{
edge taken_edge = find_taken_edge (e->dest, cond);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
@@ -1046,7 +1205,25 @@ thread_through_normal_block (edge e,
backedge_seen_p);
return 1;
}
+
+ if (TREE_CODE (cond) != SSA_NAME
+ || e->dest->loop_father != e->src->loop_father)
+ return 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. */
+ vec<basic_block, va_gc> *bb_path;
+ vec_alloc (bb_path, n_basic_blocks_for_fn (cfun));
+ vec_safe_push (bb_path, e->dest);
+ hash_set<gimple> *visited_phis = new hash_set<gimple>;
+
+ find_control_statement_thread_paths (cond, visited_phis, bb_path);
+
+ delete visited_phis;
+ vec_free (bb_path);
+
+ return -1;
}
return 0;
}
--
2.1.0.243.g30d45f7