[PATCH v2 3/5] dr: Add no-wrap bound.

From: Robin Dapp <[email protected]>

This patch adds a nowrap_bound field to data_reference which denotes the
upper bound under which the DR is non wrapping.

dr_analyze_innermost, create_data_ref, and find_data_references_in_stmt
get an additional parameter to control whether or not a no-wrap bound
should be recorded.

gcc/ChangeLog:

	* tree-data-ref.cc (dr_analyze_innermost): Add nowrap-bound param.
	(dr_analyze_indices): Likewise.
	(create_data_ref): Likewise.
	(find_data_references_in_stmt): Add allow_assumptions param.
	* tree-data-ref.h (struct data_reference): Add nowrap_bound.
	(DR_NOWRAP_BOUND): New.
	(dr_analyze_innermost): Pass on nowrap_bound.
	(find_data_references_in_stmt): Likewise.
---
 gcc/tree-data-ref.cc | 96 +++++++++++++++++++++++++++++++++++---------
 gcc/tree-data-ref.h  | 14 +++++--
 2 files changed, 88 insertions(+), 22 deletions(-)

diff --git a/gcc/tree-data-ref.cc b/gcc/tree-data-ref.cc
index 8e9d7871348..364fd1214b7 100644
--- a/gcc/tree-data-ref.cc
+++ b/gcc/tree-data-ref.cc
@@ -1129,11 +1129,15 @@ canonicalize_base_object_address (tree addr)
    dummy outermost loop.  In other cases perform loop analysis.
 
    Return true if the analysis succeeded and store the results in DRB if so.
-   BB analysis can only fail for bitfield or reversed-storage accesses.  */
+   BB analysis can only fail for bitfield or reversed-storage accesses.
+
+   If NOWRAP_BOUND is nonzero, allow simple_iv to record no-wrap bounds.
+   Then, store non-trivial bounds in NOWRAP_BOUND.  */
 
 opt_result
 dr_analyze_innermost (innermost_loop_behavior *drb, tree ref,
-		      class loop *loop, const gimple *stmt)
+		      class loop *loop, const gimple *stmt,
+		      tree *nowrap_bound)
 {
   poly_int64 pbitsize, pbitpos;
   tree base, poffset;
@@ -1195,9 +1199,11 @@ dr_analyze_innermost (innermost_loop_behavior *drb, tree ref,
       base = build_fold_addr_expr (base);
     }
 
+  bool allow_wrapping = (nowrap_bound != nullptr);
+
   if (in_loop)
     {
-      if (!simple_iv (loop, loop, base, &base_iv, true))
+      if (!simple_iv (loop, loop, base, &base_iv, true, allow_wrapping))
 	return opt_result::failure_at
 	  (stmt, "failed: evolution of base is not affine.\n");
     }
@@ -1206,25 +1212,35 @@ dr_analyze_innermost (innermost_loop_behavior *drb, tree ref,
       base_iv.base = base;
       base_iv.step = ssize_int (0);
       base_iv.no_overflow = true;
+      base_iv.nowrap_bound = NULL_TREE;
     }
 
   if (!poffset)
     {
       offset_iv.base = ssize_int (0);
       offset_iv.step = ssize_int (0);
+      offset_iv.nowrap_bound = NULL_TREE;
     }
   else
     {
       if (!in_loop)
-        {
-          offset_iv.base = poffset;
-          offset_iv.step = ssize_int (0);
-        }
-      else if (!simple_iv (loop, loop, poffset, &offset_iv, true))
+	{
+	  offset_iv.base = poffset;
+	  offset_iv.step = ssize_int (0);
+	  offset_iv.nowrap_bound = NULL_TREE;
+	}
+      else if (!simple_iv (loop, loop, poffset, &offset_iv, true,
+			   allow_wrapping))
 	return opt_result::failure_at
 	  (stmt, "failed: evolution of offset is not affine.\n");
     }
 
+  if (nowrap_bound)
+    {
+      *nowrap_bound = base_iv.nowrap_bound;
+      scev_combine_nowrap_bounds (nowrap_bound, offset_iv.nowrap_bound);
+    }
+
   init = ssize_int (pbytepos);
 
   /* Subtract any constant component from the base and add it to INIT instead.
@@ -1322,10 +1338,14 @@ base_supports_access_fn_components_p (tree base)
 }
 
 /* Determines the base object and the list of indices of memory reference
-   DR, analyzed in LOOP and instantiated before NEST.  */
+   DR, analyzed in LOOP and instantiated before NEST.
+
+   If NOWRAP_BOUND is nonzero, pass it to scev which will then store
+   the bound under which we do not wrap.  */
 
 static void
-dr_analyze_indices (struct indices *dri, tree ref, edge nest, loop_p loop)
+dr_analyze_indices (struct indices *dri, tree ref, edge nest, loop_p loop,
+		    tree *nowrap_bound = nullptr)
 {
   /* If analyzing a basic-block there are no indices to analyze
      and thus no access functions.  */
@@ -1360,7 +1380,7 @@ dr_analyze_indices (struct indices *dri, tree ref, edge nest, loop_p loop)
       if (TREE_CODE (ref) == ARRAY_REF)
 	{
 	  tree op = TREE_OPERAND (ref, 1);
-	  tree access_fn = analyze_scalar_evolution (loop, op);
+	  tree access_fn = analyze_scalar_evolution (loop, op, nowrap_bound);
 	  access_fn = instantiate_scev (nest, loop, access_fn);
 	  access_fns.safe_push (access_fn);
 	}
@@ -1402,7 +1422,7 @@ dr_analyze_indices (struct indices *dri, tree ref, edge nest, loop_p loop)
   if (TREE_CODE (ref) == MEM_REF)
     {
       tree op = TREE_OPERAND (ref, 0);
-      tree access_fn = analyze_scalar_evolution (loop, op);
+      tree access_fn = analyze_scalar_evolution (loop, op, nowrap_bound);
       access_fn = instantiate_scev (nest, loop, access_fn);
       STRIP_NOPS (access_fn);
       if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
@@ -1508,11 +1528,16 @@ free_data_ref (data_reference_p dr)
 
    Return the data_reference description of MEMREF.  NEST is the outermost
    loop in which the reference should be instantiated, LOOP is the loop
-   in which the data reference should be analyzed.  */
+   in which the data reference should be analyzed.
+
+   If ALLOW_ASSUMPTIONS is true, pass an empty no-wrap bound to scev and
+   have it store its assumptions there.  If we got a nontrivial
+   assumption, save it in DR's DR_NOWRAP_BOUND.  */
 
 struct data_reference *
 create_data_ref (edge nest, loop_p loop, tree memref, gimple *stmt,
-		 bool is_read, bool is_conditional_in_stmt)
+		 bool is_read, bool is_conditional_in_stmt,
+		 bool allow_assumptions)
 {
   struct data_reference *dr;
 
@@ -1529,11 +1554,25 @@ create_data_ref (edge nest, loop_p loop, tree memref, gimple *stmt,
   DR_IS_READ (dr) = is_read;
   DR_IS_CONDITIONAL_IN_STMT (dr) = is_conditional_in_stmt;
 
+  tree nowrap_bound = NULL_TREE;
   dr_analyze_innermost (&DR_INNERMOST (dr), memref,
-			nest != NULL ? loop : NULL, stmt);
-  dr_analyze_indices (&dr->indices, DR_REF (dr), nest, loop);
+			nest != NULL ? loop : NULL, stmt,
+			allow_assumptions ? &nowrap_bound : nullptr);
+  dr_analyze_indices (&dr->indices, DR_REF (dr), nest, loop,
+		      allow_assumptions ? &nowrap_bound : nullptr);
   dr_analyze_alias (dr);
 
+  if (nowrap_bound)
+    {
+      /* If there is a bound but it is zero, the assumption we build with it
+	 would never hold and we would always fall back to the scalar loop.
+	 Reset the DR so we can still get gather/scatter.  */
+      if (integer_zerop (nowrap_bound))
+	dr_reset (dr);
+      else
+	DR_NOWRAP_BOUND (dr) = nowrap_bound;
+    }
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       unsigned i;
@@ -1553,6 +1592,11 @@ create_data_ref (edge nest, loop_p loop, tree memref, gimple *stmt,
       fprintf (dump_file, "\n\tstep alignment: %d", DR_STEP_ALIGNMENT (dr));
       fprintf (dump_file, "\n\tbase_object: ");
       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
+      if (DR_NOWRAP_BOUND (dr))
+	{
+	  fprintf (dump_file, "\n\tnowrap bound: ");
+	  print_generic_expr (dump_file, DR_NOWRAP_BOUND (dr), TDF_SLIM);
+	}
       fprintf (dump_file, "\n");
       for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
 	{
@@ -6037,11 +6081,14 @@ loop_nest_has_data_refs (loop_p loop)
 
 /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
    reference, returns false, otherwise returns true.  NEST is the outermost
-   loop of the loop nest in which the references should be analyzed.  */
+   loop of the loop nest in which the references should be analyzed.
+   ALLOW_ASSUMPTIONS determines whether or not no-wrap assumptions
+   are allowed.  */
 
 opt_result
 find_data_references_in_stmt (class loop *nest, gimple *stmt,
-			      vec<data_reference_p> *datarefs)
+			      vec<data_reference_p> *datarefs,
+			      bool allow_assumptions)
 {
   auto_vec<data_ref_loc, 2> references;
   data_reference_p dr;
@@ -6054,7 +6101,8 @@ find_data_references_in_stmt (class loop *nest, gimple *stmt,
     {
       dr = create_data_ref (nest ? loop_preheader_edge (nest) : NULL,
 			    loop_containing_stmt (stmt), ref.ref,
-			    stmt, ref.is_read, ref.is_conditional_in_stmt);
+			    stmt, ref.is_read, ref.is_conditional_in_stmt,
+			    allow_assumptions);
       gcc_assert (dr != NULL);
       datarefs->safe_push (dr);
     }
@@ -6407,6 +6455,16 @@ free_data_refs (vec<data_reference_p>& datarefs)
   datarefs.release ();
 }
 
+/* Reset DR_INNERMOST, DR_NOWRAP_BOUND, and access functions of DR.  */
+
+void
+dr_reset (data_reference *dr)
+{
+  DR_INNERMOST (dr) = innermost_loop_behavior ();
+  DR_NOWRAP_BOUND (dr) = NULL_TREE;
+  dr->indices.access_fns.release ();
+}
+
 /* Common routine implementing both dr_direction_indicator and
    dr_zero_step_indicator.  Return USEFUL_MIN if the indicator is known
    to be >= USEFUL_MIN and -1 if the indicator is known to be negative.
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index e25f98d2966..ba901a5f6ce 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -172,6 +172,10 @@ struct data_reference
   /* Behavior of the memory reference in the innermost loop.  */
   struct innermost_loop_behavior innermost;
 
+  /* Upper bound for the number of loop iterations for which this DR's
+     IV does not wrap.  */
+  tree nowrap_bound;
+
   /* Subscripts of this data reference.  */
   struct indices indices;
 
@@ -201,6 +205,7 @@ struct data_reference
 #define DR_OFFSET_ALIGNMENT(DR)    (DR)->innermost.offset_alignment
 #define DR_STEP_ALIGNMENT(DR)      (DR)->innermost.step_alignment
 #define DR_INNERMOST(DR)           (DR)->innermost
+#define DR_NOWRAP_BOUND(DR)        (DR)->nowrap_bound
 
 typedef struct data_reference *data_reference_p;
 
@@ -520,7 +525,8 @@ typedef struct data_dependence_relation *ddr_p;
 
 
 opt_result dr_analyze_innermost (innermost_loop_behavior *, tree,
-				 class loop *, const gimple *);
+				 class loop *, const gimple *,
+				 tree * = nullptr);
 extern bool compute_data_dependences_for_loop (class loop *, bool,
 					       vec<loop_p> *,
 					       vec<data_reference_p> *,
@@ -542,14 +548,16 @@ extern void free_dependence_relation (struct data_dependence_relation *);
 extern void free_dependence_relations (vec<ddr_p>& );
 extern void free_data_ref (data_reference_p);
 extern void free_data_refs (vec<data_reference_p>& );
+void dr_reset (data_reference *);
 extern opt_result find_data_references_in_stmt (class loop *, gimple *,
-						vec<data_reference_p> *);
+						vec<data_reference_p> *,
+						bool = false);
 extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
 						   vec<data_reference_p> *);
 tree find_data_references_in_loop (class loop *, vec<data_reference_p> *);
 bool loop_nest_has_data_refs (loop_p loop);
 struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
-					bool);
+					bool, bool = false);
 extern bool find_loop_nest (class loop *, vec<loop_p> *);
 extern struct data_dependence_relation *initialize_data_dependence_relation
      (struct data_reference *, struct data_reference *, vec<loop_p>);
-- 
2.54.0