re PR tree-optimization/88533 (Higher performance penalty of array-bounds checking for sparse-matrix vector multiply)

2018-12-19  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/88533
	Revert
	2018-04-30  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/28364
	PR tree-optimization/85275
	* tree-ssa-loop-ch.c (ch_base::copy_headers): Stop after
	copying first exit test.

	* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Adjust.

	* tree-ssa-loop-ch.c: Include tree-phinodes.h and
	ssa-iterators.h.
	(should_duplicate_loop_header_p): Track whether stmt compute
	loop invariants or values based on IVs.  Apart from the
	original loop header only duplicate blocks with exit tests
	that are based on IVs or invariants.

	* gcc.dg/tree-ssa/copy-headers-6.c: New testcase.
	* gcc.dg/tree-ssa/copy-headers-7.c: Likewise.
	* gcc.dg/tree-ssa/ivopt_mult_1.c: Un-XFAIL.
	* gcc.dg/tree-ssa/ivopt_mult_2.c: Likewise.

From-SVN: r267262

1 files changed, 65 insertions, 10 deletions

diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c
index 4d4813d..3a09410 100644
--- a/gcc/tree-ssa-loop-ch.c
+++ b/gcc/tree-ssa-loop-ch.c
@@ -34,6 +34,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-scopedtables.h"
 #include "tree-ssa-threadedge.h"
 #include "tree-ssa-sccvn.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
 #include "params.h"
 
 /* Duplicates headers of loops if they are small enough, so that the statements
@@ -50,7 +52,6 @@ should_duplicate_loop_header_p (basic_block header, struct loop *loop,
 				int *limit)
 {
   gimple_stmt_iterator bsi;
-  gimple *last;
 
   gcc_assert (!header->aux);
 
@@ -99,8 +100,8 @@ should_duplicate_loop_header_p (basic_block header, struct loop *loop,
       return false;
     }
 
-  last = last_stmt (header);
-  if (gimple_code (last) != GIMPLE_COND)
+  gcond *last = dyn_cast <gcond *> (last_stmt (header));
+  if (!last)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
@@ -109,10 +110,24 @@ should_duplicate_loop_header_p (basic_block header, struct loop *loop,
       return false;
     }
 
-  /* Count number of instructions and punt on calls.  */
+  for (gphi_iterator psi = gsi_start_phis (header); !gsi_end_p (psi);
+       gsi_next (&psi))
+    {
+      gphi *phi = psi.phi ();
+      tree res = gimple_phi_result (phi);
+      if (INTEGRAL_TYPE_P (TREE_TYPE (res))
+	  || POINTER_TYPE_P (TREE_TYPE (res)))
+	gimple_set_uid (phi, 1 /* IV */);
+      else
+	gimple_set_uid (phi, 0);
+    }
+
+  /* Count number of instructions and punt on calls.
+     Populate stmts INV/IV flag to later apply heuristics to the
+     kind of conditions we want to copy.  */
   for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
     {
-      last = gsi_stmt (bsi);
+      gimple *last = gsi_stmt (bsi);
 
       if (gimple_code (last) == GIMPLE_LABEL)
 	continue;
@@ -142,7 +157,52 @@ should_duplicate_loop_header_p (basic_block header, struct loop *loop,
 		     header->index);
 	  return false;
 	}
+
+      /* Classify the stmt based on whether its computation is based
+         on a IV or whether it is invariant in the loop.  */
+      gimple_set_uid (last, 0);
+      if (!gimple_vuse (last))
+	{
+	  bool inv = true;
+	  bool iv = false;
+	  ssa_op_iter i;
+	  tree op;
+	  FOR_EACH_SSA_TREE_OPERAND (op, last, i, SSA_OP_USE)
+	    if (!SSA_NAME_IS_DEFAULT_DEF (op)
+		&& flow_bb_inside_loop_p (loop,
+					  gimple_bb (SSA_NAME_DEF_STMT (op))))
+	      {
+		if (!(gimple_uid (SSA_NAME_DEF_STMT (op)) & 2 /* INV */))
+		  inv = false;
+		if (gimple_uid (SSA_NAME_DEF_STMT (op)) & 1 /* IV */)
+		  iv = true;
+	      }
+	  gimple_set_uid (last, (iv ? 1 : 0) | (inv ? 2 : 0));
+	}
     }
+
+  /* If the condition tests a non-IV loop variant we do not want to rotate
+     the loop further.  Unless this is the original loop header.  */
+  tree lhs = gimple_cond_lhs (last);
+  tree rhs = gimple_cond_rhs (last);
+  if (header != loop->header
+      && ((TREE_CODE (lhs) == SSA_NAME
+	   && !SSA_NAME_IS_DEFAULT_DEF (lhs)
+	   && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (lhs)))
+	   && gimple_uid (SSA_NAME_DEF_STMT (lhs)) == 0)
+	  || (TREE_CODE (rhs) == SSA_NAME
+	      && !SSA_NAME_IS_DEFAULT_DEF (rhs)
+	      && flow_bb_inside_loop_p (loop,
+					gimple_bb (SSA_NAME_DEF_STMT (rhs)))
+	      && gimple_uid (SSA_NAME_DEF_STMT (rhs)) == 0)))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "  Not duplicating bb %i: condition based on non-IV loop"
+		 "variant.\n", header->index);
+      return false;
+    }
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "    Will duplicate bb %i\n", header->index); 
   return true;
@@ -343,11 +403,6 @@ ch_base::copy_headers (function *fun)
 	  bbs[n_bbs++] = header;
 	  gcc_assert (bbs_size > n_bbs);
 	  header = exit->dest;
-	  /* Make sure to stop copying after we copied the first exit test.
-	     Without further heuristics we do not want to rotate the loop
-	     any further.  */
-	  if (loop_exits_from_bb_p (loop, exit->src))
-	    break;
 	}
 
       if (!exit)