[PATCH] Allow FSM threader to thread more complex conditions

[PATCH] Allow FSM threader to thread more complex conditions

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 923 bytes --]


Right now the FSM threader only handles trivial conditions. 
Specifically looking up a naked SSA_NAME (used for GIMPLE_SWITCH) and 
SSA_NAME != 0.

The FSM threader need not be so restrictive.  We can easily use it to 
lookup things like SSA_NAME <OP> constant for integral and pointer names.

Essentially the FSM threader walks backwards to find a value for a name. 
  If we find a constant, we can then substitute the value into the 
expression and simplify.  This patch implements the substitution part, 
then exploits it from tree-ssa-threadedge.c.

I'm also renaming the test I added in my previous commit.  It was poorly 
associated with DOM when in fact it was testing the FSM threader when 
called via VRP.  Given the desire to run the FSM threader independently, 
I'm just going to call these ssa-thread-<whatever>.c tests.

Bootstrapped and regression tested on x86_64-linux-gnu.  Installed on 
the trunk.

Jeff

[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 12765 bytes --]

commit 4b7f0fb7fbb338ae677c83d3be33570edd464885
Author: Jeff Law <law@redhat.com>
Date:   Mon Oct 12 15:37:42 2015 -0600

    [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.

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..4a08f0f 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-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c
deleted file mode 100644
index 03d0334..0000000
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c
+++ /dev/null
@@ -1,49 +0,0 @@
-/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp2-details" } */
-/* { dg-final { scan-tree-dump "FSM" "vrp2" } } */
-
-void abort (void);
-typedef struct bitmap_head_def *bitmap;
-typedef const struct bitmap_head_def *const_bitmap;
-typedef struct bitmap_obstack
-{
-  struct bitmap_obstack *next;
-  unsigned int indx;
-}
-bitmap_element;
-typedef struct bitmap_head_def
-{
-  bitmap_element *first;
-}
-bitmap_head;
-static __inline__ unsigned char
-bitmap_elt_ior (bitmap dst, bitmap_element * dst_elt,
-		bitmap_element * dst_prev, const bitmap_element * a_elt,
-		const bitmap_element * b_elt)
-{
-  ((void) (!(a_elt || b_elt) ? abort (), 0 : 0));
-}
-
-unsigned char
-bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b,
-		      const_bitmap kill)
-{
-  bitmap_element *dst_elt = dst->first;
-  const bitmap_element *a_elt = a->first;
-  const bitmap_element *b_elt = b->first;
-  const bitmap_element *kill_elt = kill->first;
-  bitmap_element *dst_prev = ((void *) 0);
-  while (a_elt || b_elt)
-    {
-      if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
-	  && (!a_elt || a_elt->indx >= b_elt->indx));
-      else
-	{
-	  bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt);
-	  if (a_elt && b_elt && a_elt->indx == b_elt->indx)
-	    ;
-	  else if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
-	    a_elt = a_elt->next;
-	}
-    }
-}
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-thread-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
new file mode 100644
index 0000000..03d0334
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
@@ -0,0 +1,49 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp2-details" } */
+/* { dg-final { scan-tree-dump "FSM" "vrp2" } } */
+
+void abort (void);
+typedef struct bitmap_head_def *bitmap;
+typedef const struct bitmap_head_def *const_bitmap;
+typedef struct bitmap_obstack
+{
+  struct bitmap_obstack *next;
+  unsigned int indx;
+}
+bitmap_element;
+typedef struct bitmap_head_def
+{
+  bitmap_element *first;
+}
+bitmap_head;
+static __inline__ unsigned char
+bitmap_elt_ior (bitmap dst, bitmap_element * dst_elt,
+		bitmap_element * dst_prev, const bitmap_element * a_elt,
+		const bitmap_element * b_elt)
+{
+  ((void) (!(a_elt || b_elt) ? abort (), 0 : 0));
+}
+
+unsigned char
+bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b,
+		      const_bitmap kill)
+{
+  bitmap_element *dst_elt = dst->first;
+  const bitmap_element *a_elt = a->first;
+  const bitmap_element *b_elt = b->first;
+  const bitmap_element *kill_elt = kill->first;
+  bitmap_element *dst_prev = ((void *) 0);
+  while (a_elt || b_elt)
+    {
+      if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
+	  && (!a_elt || a_elt->indx >= b_elt->indx));
+      else
+	{
+	  bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt);
+	  if (a_elt && b_elt && a_elt->indx == b_elt->indx)
+	    ;
+	  else if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
+	    a_elt = a_elt->next;
+	}
+    }
+}
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.  */