From 1f09b819559865be5a366e11a9c0f9bf495f91bc 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.
* Makefile.in: Add dependence on pointer-set.o.
* tree-ssa-threadedge.c: Include pointer-set.h.
(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/Makefile.in | 1 +
gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c | 32 +++++
gcc/tree-ssa-threadedge.c | 170 ++++++++++++++++++++++-
3 files changed, 202 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
@@ -1310,6 +1310,7 @@ OBJS = \
opts-global.o \
passes.o \
plugin.o \
+ pointer-set.o \
postreload-gcse.o \
postreload.o \
predict.o \
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;
+}
@@ -49,6 +49,7 @@ along with GCC; see the file COPYING3. If not see
#include "params.h"
#include "tree-ssa-threadedge.h"
#include "builtins.h"
+#include "pointer-set.h"
/* To avoid code explosion due to jump threading, we limit the
number of statements we are going to copy. This variable
@@ -628,6 +629,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 +658,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 +923,145 @@ 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,
+ struct pointer_set_t *visited_bbs)
+{
+ if (start_bb == end_bb)
+ {
+ vec_safe_push (path, start_bb);
+ return true;
+ }
+
+ if (!pointer_set_insert (visited_bbs, 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;
+}
+
+/* CTRL_STMT is a COND_EXPR or SWITCH_EXPR statement whose controlling
+ expression is the variable EXPR. We trace the value of the variable 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,
+ struct pointer_set_t *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)
+ {
+ struct pointer_set_t *visited_bbs = pointer_set_create ();
+
+ if (find_thread_path (var_bb, e->src, next_path, visited_bbs))
+ e_count = e_count + 1;
+
+ pointer_set_destroy (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
+ || pointer_set_insert (visited_phis, 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 *> ();
+
+ 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->dest))
+ kind = EDGE_COPY_SRC_BLOCK;
+ else
+ kind = EDGE_COPY_SRC_JOINER_BLOCK;
+
+ jump_thread_edge *x = new jump_thread_edge (e, kind);
+ jump_thread_path->safe_push (x);
+ }
+
+ 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 +1147,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,6 +1196,24 @@ thread_through_normal_block (edge e,
backedge_seen_p);
return 1;
}
+
+ if (TREE_CODE (cond) != SSA_NAME)
+ 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);
+ struct pointer_set_t *visited_phis = pointer_set_create ();
+
+ find_control_statement_thread_paths (cond, visited_phis, bb_path);
+
+ pointer_set_destroy (visited_phis);
+ vec_free (bb_path);
+
+ return -1;
}
return 0;
}
--
2.1.0.243.g30d45f7