[PATCH] Allow FSM threader to thread more complex conditions

	* tree-ssa-threadbackward.c (get_gimple_control_stmt): New function.
	(fsm_find_control_stmt_paths): Change name of first argument to
	more accurately relfect what it really is.  Handle simplification
	of GIMPLE_COND after finding a thread path for NAME.
	* tree-ssa-threadedge.c (simplify_control_stmt_condition): Allow
	nontrivial conditions to be handled by FSM threader.
	(thread_through_normal_block): Extract the name to looup via
	FSM threader from COND_EXPR.

	* gcc.dg/tree-ssa/ssa-thread-12.c: New test.
	* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Update expected output.
	* gcc.dg/tree-ssa/ssa-thread-11.c: Renamed from
	ssa-dom-thread-11.c.

From-SVN: r228739

7 files changed, 139 insertions, 12 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 61e46ff..a865043 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -7,6 +7,15 @@
 
 2015-10-12  Jeff Law  <law@redhat.com>
 
+	* tree-ssa-threadbackward.c (get_gimple_control_stmt): New function.
+	(fsm_find_control_stmt_paths): Change name of first argument to
+	more accurately relfect what it really is.  Handle simplification
+	of GIMPLE_COND after finding a thread path for NAME. 
+	* tree-ssa-threadedge.c (simplify_control_stmt_condition): Allow
+	nontrivial conditions to be handled by FSM threader.
+	(thread_through_normal_block): Extract the name to looup via
+	FSM threader from COND_EXPR.
+
 	* tree-ssa-threadbackward.c (fsm_find_thread_path): Remove
 	restriction that traced SSA_NAME is a user variable.
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 89f3363..4a08f0fe 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,10 @@
 2015-10-12  Jeff Law  <law@redhat.com>
 
+	* gcc.dg/tree-ssa/ssa-thread-12.c: New test.
+	* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Update expected output.
+	* gcc.dg/tree-ssa/ssa-thread-11.c: Renamed from
+	ssa-dom-thread-11.c.
+
 	* gcc.dg/tree-ssa/ssa-dom-thread-11.c: New test.
 
 2015-10-12  Ville Voutilainen  <ville.voutilainen@gmail.com>
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
index d8be023..445f250 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
@@ -1,6 +1,6 @@
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdump-tree-dom1-details" } */
-/* { dg-final { scan-tree-dump-times "FSM" 19 "dom1" } } */
+/* { dg-final { scan-tree-dump-times "FSM" 38 "dom1" } } */
 
 enum STATE {
   S0=0,
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
index 03d0334..03d0334 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c
new file mode 100644
index 0000000..0697fb0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c
@@ -0,0 +1,72 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dom1-details" } */
+/* { dg-final { scan-tree-dump "FSM" "dom1" } } */
+
+typedef struct bitmap_head_def *bitmap;
+typedef const struct bitmap_head_def *const_bitmap;
+typedef struct VEC_int_base
+{
+}
+VEC_int_base;
+typedef struct VEC_int_heap
+{
+  VEC_int_base base;
+}
+VEC_int_heap;
+typedef unsigned long BITMAP_WORD;
+typedef struct bitmap_element_def
+{
+  struct bitmap_element_def *next;
+  unsigned int indx;
+}
+bitmap_element;
+typedef struct bitmap_head_def
+{
+}
+bitmap_head;
+typedef struct
+{
+  bitmap_element *elt1;
+  bitmap_element *elt2;
+  BITMAP_WORD bits;
+}
+bitmap_iterator;
+static __inline__ void
+bmp_iter_and_compl_init (bitmap_iterator * bi, const_bitmap map1,
+			 const_bitmap map2, unsigned start_bit,
+			 unsigned *bit_no)
+{
+}
+
+static __inline__ void
+bmp_iter_next (bitmap_iterator * bi, unsigned *bit_no)
+{
+}
+
+static __inline__ unsigned char
+bmp_iter_and_compl (bitmap_iterator * bi, unsigned *bit_no)
+{
+  if (bi->bits)
+    {
+      while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
+	bi->elt2 = bi->elt2->next;
+    }
+}
+
+extern int VEC_int_base_length (VEC_int_base *);
+bitmap
+compute_idf (bitmap def_blocks, bitmap_head * dfs)
+{
+  bitmap_iterator bi;
+  unsigned bb_index, i;
+  VEC_int_heap *work_stack;
+  bitmap phi_insertion_points;
+  while ((VEC_int_base_length (((work_stack) ? &(work_stack)->base : 0))) > 0)
+    {
+      for (bmp_iter_and_compl_init
+	   (&(bi), (&dfs[bb_index]), (phi_insertion_points), (0), &(i));
+	   bmp_iter_and_compl (&(bi), &(i)); bmp_iter_next (&(bi), &(i)))
+	{
+	}
+    }
+}
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index ff6481c..5be6ee4 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -36,6 +36,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.  */
+static gimple *
+get_gimple_control_stmt (basic_block bb)
+{
+  gimple_stmt_iterator gsi = gsi_last_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;
+}
+
 /* Return true if the CFG contains at least one path from START_BB to END_BB.
    When a path is found, record in PATH the blocks from END_BB to START_BB.
    VISITED_BBS is used to make sure we don't fall into an infinite loop.  Bound
@@ -70,17 +86,17 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
   return false;
 }
 
-/* We trace the value of the SSA_NAME EXPR back through any phi nodes looking
+/* We trace the value of the SSA_NAME NAME back through any phi nodes looking
    for places where it gets a constant value and save the path.  Stop after
    having recorded MAX_PATHS jump threading paths.  */
 
 static void
-fsm_find_control_statement_thread_paths (tree expr,
+fsm_find_control_statement_thread_paths (tree name,
 					 hash_set<basic_block> *visited_bbs,
 					 vec<basic_block, va_gc> *&path,
 					 bool seen_loop_phi)
 {
-  gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
+  gimple *def_stmt = SSA_NAME_DEF_STMT (name);
   basic_block var_bb = gimple_bb (def_stmt);
 
   if (var_bb == NULL)
@@ -284,6 +300,20 @@ fsm_find_control_statement_thread_paths (tree expr,
 	  jump_thread_path->safe_push (x);
 	}
 
+      gimple *stmt = get_gimple_control_stmt ((*path)[0]);
+      gcc_assert (stmt);
+      /* We have found a constant value for ARG.  For GIMPLE_SWITCH
+	 and GIMPLE_GOTO, we use it as-is.  However, for a GIMPLE_COND
+	 we need to substitute, fold and simplify.  */
+      if (gimple_code (stmt) == GIMPLE_COND)
+	{
+	  enum tree_code cond_code = gimple_cond_code (stmt);
+
+	  /* We know the underyling format of the condition.  */
+	  arg = fold_binary (cond_code, boolean_type_node,
+			     arg, gimple_cond_rhs (stmt));
+	}
+
       /* Add the edge taken when the control variable has value ARG.  */
       edge taken_edge = find_taken_edge ((*path)[0], arg);
       jump_thread_edge *x
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 5ca9458..da2fb1f 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -551,11 +551,13 @@ simplify_control_stmt_condition (edge e,
           || !is_gimple_min_invariant (cached_lhs))
         cached_lhs = (*simplify) (dummy_cond, stmt, avail_exprs_stack);
 
-      /* If we were just testing that an integral type was != 0, and that
-	 failed, just return the first operand.  This gives the FSM code a
-	 chance to optimize the path.  */
-      if (cached_lhs == NULL
-	  && cond_code == NE_EXPR)
+      /* If we were testing an integer/pointer against a constant, then
+	 we can use the FSM code to trace the value of the SSA_NAME.  If
+	 a value is found, then the condition will collapse to a constant.
+
+	 Return the SSA_NAME we want to trace back rather than the full
+	 expression and give the FSM threader a chance to find its value.  */
+      if (cached_lhs == NULL)
 	{
 	  /* Recover the original operands.  They may have been simplified
 	     using context sensitive equivalences.  Those context sensitive
@@ -563,9 +565,10 @@ simplify_control_stmt_condition (edge e,
 	  tree op0 = gimple_cond_lhs (stmt);
 	  tree op1 = gimple_cond_rhs (stmt);
 
-	  if (INTEGRAL_TYPE_P (TREE_TYPE (op0))
+	  if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
+	       || POINTER_TYPE_P (TREE_TYPE (op0)))
 	      && TREE_CODE (op0) == SSA_NAME
-	      && integer_zerop (op1))
+	      && TREE_CODE (op1) == INTEGER_CST)
 	    return op0;
 	}
 
@@ -1046,11 +1049,19 @@ thread_through_normal_block (edge e,
 
       if (!flag_expensive_optimizations
 	  || optimize_function_for_size_p (cfun)
-	  || TREE_CODE (cond) != SSA_NAME
+	  || !(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.  */