[gcc/devel/omp/gcc-12] graphite: Add runtime alias checking

[gcc/devel/omp/gcc-12] graphite: Add runtime alias checking

[Kwok Yeung]

https://gcc.gnu.org/g:f7643da2684126397a3161abfc9b292146bb8ad5

commit f7643da2684126397a3161abfc9b292146bb8ad5
Author: Frederik Harwath <frederik@codesourcery.com>
Date:   Tue Nov 16 16:15:08 2021 +0100

    graphite: Add runtime alias checking
    
    Graphite rejects a SCoP if it contains a pair of data references for
    which it cannot determine statically if they may alias. This happens
    very often, for instance in C code which does not use explicit
    "restrict".  This commit adds the possibility to analyze a SCoP
    nevertheless and perform an alias check at runtime.  Then, if aliasing
    is detected, the execution will fall back to the unoptimized SCoP.
    
    TODO This needs more testing on non-OpenACC code.
    
    gcc/ChangeLog:
    
            * common.opt: Add fgraphite-runtime-alias-checks.
            * graphite-isl-ast-to-gimple.cc
            (generate_alias_cond): New function.
            (graphite_regenerate_ast_isl): Use from here.
            * graphite-poly.cc (new_scop): Create unhandled_alias_ddrs vec ...
            (free_scop): and release here.
            * graphite-scop-detection.cc (dr_defs_outside_region): New function.
            (dr_well_analyzed_for_runtime_alias_check_p): New function.
            (graphite_runtime_alias_check_p): New function.
            (build_alias_set): Record unhandled alias ddrs for later alias check
            creation if flag_graphite_runtime_alias_checks is true instead
            of failing.
            * graphite.h (struct scop): Add field unhandled_alias_ddrs.
            * sese.h (has_operands_from_region_p): New function.
    
    gcc/testsuite/ChangeLog:
    
            * gcc.dg/graphite/alias-1.c: New test.

Diff:
---
 gcc/ChangeLog.omp                       |  17 +++
 gcc/common.opt                          |   4 +
 gcc/graphite-isl-ast-to-gimple.cc       |  60 ++++++++
 gcc/graphite-poly.cc                    |   2 +
 gcc/graphite-scop-detection.cc          | 233 +++++++++++++++++++++++++++++---
 gcc/graphite.h                          |   4 +
 gcc/sese.h                              |  18 +++
 gcc/testsuite/ChangeLog.omp             |   4 +
 gcc/testsuite/gcc.dg/graphite/alias-1.c |  22 +++
 9 files changed, 344 insertions(+), 20 deletions(-)

diff --git a/gcc/ChangeLog.omp b/gcc/ChangeLog.omp
index f2047acc527..5e39494ec59 100644
--- a/gcc/ChangeLog.omp
+++ b/gcc/ChangeLog.omp
@@ -1,3 +1,20 @@
+2021-11-16  Frederik Harwath  <frederik@codesourcery.com>
+
+	* common.opt: Add fgraphite-runtime-alias-checks.
+	* graphite-isl-ast-to-gimple.cc
+	(generate_alias_cond): New function.
+	(graphite_regenerate_ast_isl): Use from here.
+	* graphite-poly.cc (new_scop): Create unhandled_alias_ddrs vec ...
+	(free_scop): and release here.
+	* graphite-scop-detection.cc (dr_defs_outside_region): New function.
+	(dr_well_analyzed_for_runtime_alias_check_p): New function.
+	(graphite_runtime_alias_check_p): New function.
+	(build_alias_set): Record unhandled alias ddrs for later alias check
+	creation if flag_graphite_runtime_alias_checks is true instead
+	of failing.
+	* graphite.h (struct scop): Add field unhandled_alias_ddrs.
+	* sese.h (has_operands_from_region_p): New function.
+
 2021-11-16  Frederik Harwath  <frederik@codesourcery.com>
 
 	* tree-loop-distribution.cc (data_ref_segment_size): Remove function.
diff --git a/gcc/common.opt b/gcc/common.opt
index 8a0dafc522d..8511e025174 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -1700,6 +1700,10 @@ fgraphite-identity
 Common Var(flag_graphite_identity) Optimization
 Enable Graphite Identity transformation.
 
+fgraphite-runtime-alias-checks
+Common Var(flag_graphite_runtime_alias_checks) Optimization Init(1)
+Allow Graphite to add runtime alias checks to loop-nests if aliasing cannot be resolved statically.
+
 fhoist-adjacent-loads
 Common Var(flag_hoist_adjacent_loads) Optimization
 Enable hoisting adjacent loads to encourage generating conditional move
diff --git a/gcc/graphite-isl-ast-to-gimple.cc b/gcc/graphite-isl-ast-to-gimple.cc
index 634af18850c..28a63f449b9 100644
--- a/gcc/graphite-isl-ast-to-gimple.cc
+++ b/gcc/graphite-isl-ast-to-gimple.cc
@@ -1452,6 +1452,34 @@ generate_entry_out_of_ssa_copies (edge false_entry,
     }
 }
 
+/* Create a condition that evaluates to TRUE if all ALIAS_DDRS are free of
+   aliasing. */
+
+static tree
+generate_alias_cond (vec<ddr_p> &alias_ddrs, loop_p context_loop)
+{
+  gcc_checking_assert (flag_graphite_runtime_alias_checks
+		       && alias_ddrs.length () > 0);
+  gcc_checking_assert (context_loop);
+
+  auto_vec<dr_with_seg_len_pair_t> check_pairs;
+  compute_alias_check_pairs (context_loop, &alias_ddrs, &check_pairs);
+  gcc_checking_assert (check_pairs.length () > 0);
+
+  tree alias_cond = NULL_TREE;
+  create_runtime_alias_checks (context_loop, &check_pairs, &alias_cond);
+  gcc_checking_assert (alias_cond);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Generated runtime alias check: ");
+      print_generic_expr (dump_file, alias_cond, dump_flags);
+      fprintf (dump_file, "\n");
+    }
+
+  return alias_cond;
+}
+
 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
    Return true if code generation succeeded.  */
 
@@ -1492,12 +1520,44 @@ graphite_regenerate_ast_isl (scop_p scop)
   region->if_region = if_region;
 
   loop_p context_loop = region->region.entry->src->loop_father;
+  gcc_checking_assert (context_loop);
   edge e = single_succ_edge (if_region->true_region->region.entry->dest);
   basic_block bb = split_edge (e);
 
   /* Update the true_region exit edge.  */
   region->if_region->true_region->region.exit = single_succ_edge (bb);
 
+  if (flag_graphite_runtime_alias_checks
+      && scop->unhandled_alias_ddrs.length () > 0)
+    {
+      /* SCoP detection has failed to handle the aliasing between some data
+	 references of the SCoP statically. Generate an alias check that selects
+	 the newly generated version of the SCoP in the true-branch of the
+	 conditional if aliasing can be ruled out at runtime and the original
+	 version of the SCoP, otherwise. */
+
+      loop_p loop
+	  = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
+			      scop->scop_info->region.exit->src->loop_father);
+      tree cond = generate_alias_cond (scop->unhandled_alias_ddrs, loop);
+      tree non_alias_cond = build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
+      set_ifsese_condition (region->if_region, non_alias_cond);
+
+      /* The loop-nest vec is shared by all DDRs. */
+      DDR_LOOP_NEST (scop->unhandled_alias_ddrs[0]).release ();
+
+      unsigned int i;
+      struct data_dependence_relation *ddr;
+
+      FOR_EACH_VEC_ELT (scop->unhandled_alias_ddrs, i, ddr)
+	if (ddr)
+	  free_dependence_relation (ddr);
+      scop->unhandled_alias_ddrs.truncate (0);
+    }
+
+  if (dump_file)
+    fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n");
+
   t.translate_isl_ast (context_loop, root_node, e, ip);
   if (! t.codegen_error_p ())
     {
diff --git a/gcc/graphite-poly.cc b/gcc/graphite-poly.cc
index 42ed038768e..dc7710ce4a1 100644
--- a/gcc/graphite-poly.cc
+++ b/gcc/graphite-poly.cc
@@ -255,6 +255,7 @@ new_scop (edge entry, edge exit)
   scop_set_region (s, region);
   s->pbbs.create (3);
   s->drs.create (3);
+  s->unhandled_alias_ddrs.create (1);
   s->dependence = NULL;
   return s;
 }
@@ -272,6 +273,7 @@ free_scop (scop_p scop)
 
   scop->pbbs.release ();
   scop->drs.release ();
+  scop->unhandled_alias_ddrs.release ();
 
   isl_set_free (scop->param_context);
   scop->param_context = NULL;
diff --git a/gcc/graphite-scop-detection.cc b/gcc/graphite-scop-detection.cc
index 1ddabf40a1b..233c13161b3 100644
--- a/gcc/graphite-scop-detection.cc
+++ b/gcc/graphite-scop-detection.cc
@@ -1540,6 +1540,123 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
   return new_gimple_poly_bb (bb, drs, reads, writes);
 }
 
+/* Checks if all parts of DR are defined outside of REGION.  This allows an
+   alias check involving DR to be placed in front of the region. */
+
+static opt_result
+dr_defs_outside_region (const sese_l &region, data_reference_p dr)
+{
+  static const char *pre
+      = "cannot create alias check for SCoP. Data reference's";
+  static const char *suf = "uses definitions from SCoP.\n";
+  opt_result res = opt_result::success ();
+
+  if (has_operands_from_region_p (DR_BASE_OBJECT (dr), region))
+    res = opt_result::failure_at (DR_STMT (dr), "%s base %s", pre, suf);
+  else if (has_operands_from_region_p (DR_INIT (dr), region))
+    res = opt_result::failure_at (DR_STMT (dr), "%s constant offset %s", pre,
+				  suf);
+  else if (has_operands_from_region_p (DR_STEP (dr), region))
+    res = opt_result::failure_at (DR_STMT (dr), "%s step %s", pre, suf);
+  else if (has_operands_from_region_p (DR_OFFSET (dr), region))
+    res = opt_result::failure_at (DR_STMT (dr), "%s loop-invariant offset %s",
+				  pre, suf);
+  else if (has_operands_from_region_p (DR_BASE_ADDRESS (dr), region))
+    res = opt_result::failure_at (DR_STMT (dr), "%s base address %s", pre,
+				  suf);
+  else
+    for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
+      if (has_operands_from_region_p (DR_ACCESS_FN (dr, i), region))
+	{
+	  res = opt_result::failure_at (
+	      DR_STMT (dr), "%s %d-th access function  %s", pre, i + 1, pre);
+	  break;
+	}
+
+  return opt_result::success ();
+}
+
+/* Check that all constituents of DR that are used by the
+   "compute_alias_check_pairs" function have been analyzed as required. */
+
+static opt_result
+dr_well_analyzed_for_runtime_alias_check_p (data_reference_p dr)
+{
+  static const char* error =
+    "data-reference not well-analyzed for runtime check.";
+  gimple* stmt = DR_STMT (dr);
+
+  if (! DR_BASE_ADDRESS (dr))
+    return opt_result::failure_at (stmt, "%s no base address.\n", error);
+  else if (! DR_OFFSET (dr))
+    return opt_result::failure_at (stmt, "%s no offset.\n", error);
+  else if (! DR_INIT (dr))
+    return opt_result::failure_at (stmt, "%s no init.\n", error);
+  else if (! DR_STEP (dr))
+    return opt_result::failure_at (stmt, "%s no step.\n", error);
+  else if (! tree_fits_uhwi_p (DR_STEP (dr)))
+    return opt_result::failure_at (stmt, "%s step too large.\n", error);
+
+  DEBUG_PRINT (dump_data_reference (dump_file, dr));
+
+  return opt_result::success ();
+}
+
+/* Return TRUE if it is possible to create a runtime alias check for
+   data-references DR1 and DR2 from LOOP and place it in front of REGION. */
+
+static opt_result
+graphite_runtime_alias_check_p (data_reference_p dr1, data_reference_p dr2,
+				class loop *loop, const sese_l &region)
+{
+  gcc_checking_assert (loop);
+  gcc_checking_assert (dr1);
+  gcc_checking_assert (dr2);
+
+  if (dump_file)
+    {
+      fprintf (dump_file,
+	       "Attempting runtime alias check creation for DRs:\n");
+      dump_data_reference (dump_file, dr1);
+      dump_data_reference (dump_file, dr2);
+    }
+
+  if (!optimize_loop_for_speed_p (loop))
+    return opt_result::failure_at (DR_STMT (dr1),
+				   "runtime alias check not supported when"
+				   " optimizing for size.\n");
+
+  /* Verify that we have enough information about the data-references and
+     context loop to construct a runtime alias check expression with
+     "compute_alias_check_pairs". */
+  tree niters = number_of_latch_executions (loop);
+  if (niters == NULL_TREE || niters == chrec_dont_know)
+    return opt_result::failure_at (DR_STMT (dr1),
+				   "failed to obtain number of iterations of "
+				   "loop %d.\n", loop->num);
+
+  opt_result ok = dr_well_analyzed_for_runtime_alias_check_p (dr1);
+  if (!ok)
+    return ok;
+
+  ok = dr_well_analyzed_for_runtime_alias_check_p (dr2);
+  if (!ok)
+    return ok;
+
+  /* The runtime alias check would be placed before REGION and hence it cannot
+     use definitions made within REGION. */
+
+  ok = dr_defs_outside_region (region, dr1);
+  if (!ok)
+    return ok;
+
+  ok = dr_defs_outside_region (region, dr2);
+  if (!ok)
+    return ok;
+
+  return opt_result::success ();
+}
+
 /* Compute alias-sets for all data references in DRS.  */
 
 static bool 
@@ -1547,7 +1664,7 @@ build_alias_set (scop_p scop)
 {
   int num_vertices = scop->drs.length ();
   struct graph *g = new_graph (num_vertices);
-  dr_info *dr1, *dr2;
+  dr_info *dri1, *dri2;
   int i, j;
   int *all_vertices;
 
@@ -1555,33 +1672,110 @@ build_alias_set (scop_p scop)
     = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
 			scop->scop_info->region.exit->src->loop_father);
 
-  FOR_EACH_VEC_ELT (scop->drs, i, dr1)
-    for (j = i+1; scop->drs.iterate (j, &dr2); j++)
-      if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
+  gcc_checking_assert (nest);
+
+  vec<loop_p> nest_vec;
+  nest_vec.create (1);
+  if (flag_graphite_runtime_alias_checks)
+    nest_vec.safe_push (nest);
+
+  FOR_EACH_VEC_ELT (scop->drs, i, dri1)
+    {
+      data_reference_p dr1 = dri1->dr;
+
+      for (j = i + 1; scop->drs.iterate (j, &dri2); j++)
 	{
-	  /* Dependences in the same alias set need to be handled
-	     by just looking at DR_ACCESS_FNs.  */
-	  if (DR_NUM_DIMENSIONS (dr1->dr) == 0
-	      || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
-	      || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
-				    DR_BASE_OBJECT (dr2->dr),
-				    OEP_ADDRESS_OF)
-	      || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
-				       TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
+
+	  data_reference_p dr2 = dri2->dr;
+	  if (!(DR_IS_READ (dr1) && DR_IS_READ (dr2))
+	      && dr_may_alias_p (dr1, dr2, nest))
 	    {
-	      free_graph (g);
-	      return false;
+	      /* Dependences in the same alias set need to be handled
+		 by just looking at DR_ACCESS_FNs.  */
+	      bool dimension_zero = DR_NUM_DIMENSIONS (dr1) == 0;
+	      bool different_dimensions
+		  = DR_NUM_DIMENSIONS (dr1) != DR_NUM_DIMENSIONS (dr2);
+	      bool different_base_objects = !operand_equal_p (
+		  DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), OEP_ADDRESS_OF);
+	      bool incompatible_types
+		  = !types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1)),
+					 TREE_TYPE (DR_BASE_OBJECT (dr2)));
+	      bool ddr_can_be_handled
+		  = !(dimension_zero || different_dimensions
+		      || different_base_objects || incompatible_types);
+
+	      if (!ddr_can_be_handled)
+		{
+		  DEBUG_PRINT (
+		      dp << "[build_alias_set] "
+			    "Cannot handle aliasing between data references:\n";
+		      print_gimple_stmt (dump_file, dr1->stmt, 2, TDF_DETAILS);
+		      print_gimple_stmt (dump_file, dr2->stmt, 2, TDF_DETAILS);
+		      dp << "\n");
+		  if (dimension_zero)
+		    DEBUG_PRINT (dp << "DR1 has dimension 0.\n");
+		  if (different_base_objects)
+		    DEBUG_PRINT (dp << "DRs have different base objects.\n");
+		  if (different_dimensions)
+		    DEBUG_PRINT (dp << "DRs have different dimensions.\n");
+		  if (incompatible_types)
+		    DEBUG_PRINT (dp <<
+				 "DRs have incompatible base object types.\n");
+		}
+
+	      if (ddr_can_be_handled)
+		{
+		  add_edge (g, i, j);
+		  add_edge (g, j, i);
+		  continue;
+		}
+
+	      loop_p common_loop
+		  = find_common_loop ((DR_STMT (dr1))->bb->loop_father,
+				      (DR_STMT (dr2))->bb->loop_father);
+	      edge scop_entry = scop->scop_info->region.entry;
+	      dr1 = create_data_ref (scop_entry, common_loop, DR_REF (dr1),
+				     DR_STMT (dr1), DR_IS_READ (dr1),
+				     DR_IS_CONDITIONAL_IN_STMT (dr1));
+	      dr2 = create_data_ref (scop_entry, common_loop, DR_REF (dr2),
+				     DR_STMT (dr2), DR_IS_READ (dr2),
+				     DR_IS_CONDITIONAL_IN_STMT (dr2));
+
+	      if (flag_graphite_runtime_alias_checks
+		  && graphite_runtime_alias_check_p (dr1, dr2, nest,
+						     scop->scop_info->region))
+		{
+		  ddr_p ddr = initialize_data_dependence_relation (dr1, dr2,
+								   nest_vec);
+		  scop->unhandled_alias_ddrs.safe_push (ddr);
+		}
+	      else
+		{
+		  if (flag_graphite_runtime_alias_checks)
+		    {
+		      unsigned int i;
+		      struct data_dependence_relation *ddr;
+
+		      FOR_EACH_VEC_ELT (scop->unhandled_alias_ddrs, i, ddr)
+		      if (ddr)
+			free_dependence_relation (ddr);
+		      scop->unhandled_alias_ddrs.truncate (0);
+		    }
+
+		  nest_vec.release ();
+		  free_graph (g);
+		  return false;
+		}
 	    }
-	  add_edge (g, i, j);
-	  add_edge (g, j, i);
-	}
+      }
+    }
 
   all_vertices = XNEWVEC (int, num_vertices);
   for (i = 0; i < num_vertices; i++)
     all_vertices[i] = i;
 
   scop->max_alias_set
-    = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
+      = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
   free (all_vertices);
 
   for (i = 0; i < g->n_vertices; i++)
@@ -1701,7 +1895,6 @@ gather_bbs::after_dom_children (basic_block bb)
     }
 }
 
-
 /* Compute sth like an execution order, dominator order with first executing
    edges that stay inside the current loop, delaying processing exit edges.  */
 
diff --git a/gcc/graphite.h b/gcc/graphite.h
index d37bab79e84..81d2d3f6cf6 100644
--- a/gcc/graphite.h
+++ b/gcc/graphite.h
@@ -368,6 +368,10 @@ struct scop
   /* The maximum alias set as assigned to drs by build_alias_sets.  */
   unsigned max_alias_set;
 
+  /* A set of ddrs that were rejected by build_alias_set during scop detection
+     and that must be handled by other means (runtime checking). */
+  vec<ddr_p> unhandled_alias_ddrs;
+
   /* All the basic blocks in this scop that contain memory references
      and that will be represented as statements in the polyhedral
      representation.  */
diff --git a/gcc/sese.h b/gcc/sese.h
index 4e786ba4c54..5ace026d1d1 100644
--- a/gcc/sese.h
+++ b/gcc/sese.h
@@ -153,6 +153,24 @@ defined_in_sese_p (tree name, const sese_l &r)
   return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r);
 }
 
+/* Returns true if EXPR has operands that are defined in REGION.  */
+
+static bool
+has_operands_from_region_p (tree expr, const sese_l &region)
+{
+  if (!expr || is_gimple_min_invariant (expr))
+    return false;
+
+  if (TREE_CODE (expr) == SSA_NAME)
+    return defined_in_sese_p (expr, region);
+
+  for (int i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
+    if (has_operands_from_region_p (TREE_OPERAND (expr, i), region))
+      return true;
+
+  return false;
+}
+
 /* Returns true when LOOP is in REGION.  */
 
 static inline bool
diff --git a/gcc/testsuite/ChangeLog.omp b/gcc/testsuite/ChangeLog.omp
index 0f4878dd195..0aeb2333c4a 100644
--- a/gcc/testsuite/ChangeLog.omp
+++ b/gcc/testsuite/ChangeLog.omp
@@ -1,3 +1,7 @@
+2021-11-16  Frederik Harwath <frederik@codesourcery.com>
+
+	* gcc.dg/graphite/alias-1.c: New test.
+
 2021-11-16  Frederik Harwath <frederik@codesourcery.com>
 	    Thomas Schwinge <thomas@codesourcery.com>
 
diff --git a/gcc/testsuite/gcc.dg/graphite/alias-1.c b/gcc/testsuite/gcc.dg/graphite/alias-1.c
new file mode 100644
index 00000000000..ee80dae1df3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/alias-1.c
@@ -0,0 +1,22 @@
+/* This test demonstrates a loop nest that Graphite cannot handle
+   because of aliasing. It should be possible to handle this loop nest
+   by creating a runtime alias check like in the very similar test
+   alias-0-runtime-check.c. However Graphite analyses the data
+   reference with respect to the innermost loop that contains the data
+   reference, the variable "i" remains uninstantiated (in contrast to
+   "j"), and consequently the alias check cannot be placed outside of
+   the SCoP since "i" is not defined there. */
+
+/* { dg-options "-O2 -fgraphite-identity -fgraphite-runtime-alias-checks -fdump-tree-graphite-details" } */
+
+void sum(int *x, int *y, unsigned *sum)
+{
+  unsigned i,j;
+  *sum = 0;
+
+  for (i = 0; i < 10000; i=i+1)
+    for (j = 0; j < 22222; j=j+1)
+      *sum +=  x[i] + y[j];
+}
+
+/* { dg-final { scan-tree-dump "number of SCoPs: 1" "graphite" { xfail *-*-* } } } */