[19/40] graphite: Add runtime alias checking

Message ID 20211215155447.19379-20-frederik@codesourcery.com
State New
Headers
Series OpenACC "kernels" Improvements |

Commit Message

Frederik Harwath Dec. 15, 2021, 3:54 p.m. UTC
  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.c
        (generate_alias_cond): New function.
        (graphite_regenerate_ast_isl): Use from here.
        * graphite-poly.c (new_scop): Create unhandled_alias_ddrs vec ...
        (free_scop): and release here.
        * graphite-scop-detection.c (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.
---
 gcc/common.opt                          |   4 +
 gcc/graphite-isl-ast-to-gimple.c        |  60 ++++++
 gcc/graphite-poly.c                     |   2 +
 gcc/graphite-scop-detection.c           | 241 +++++++++++++++++++++---
 gcc/graphite.h                          |   4 +
 gcc/sese.h                              |  18 ++
 gcc/testsuite/gcc.dg/graphite/alias-1.c |  22 +++
 7 files changed, 328 insertions(+), 23 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/alias-1.c

--
2.33.0

-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955
  

Patch

diff --git a/gcc/common.opt b/gcc/common.opt
index 1a5b9bfcca91..b6c46ab63e34 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -1673,6 +1673,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.c b/gcc/graphite-isl-ast-to-gimple.c
index 0712d85b67a6..073b471775de 100644
--- a/gcc/graphite-isl-ast-to-gimple.c
+++ b/gcc/graphite-isl-ast-to-gimple.c
@@ -1456,6 +1456,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.  */

@@ -1496,12 +1524,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.c b/gcc/graphite-poly.c
index 1dfc28e6caea..a7aabcb33c99 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -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.c b/gcc/graphite-scop-detection.c
index 46c470210d05..924004e3f3c4 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -1542,6 +1542,125 @@  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 res;
+}
+
+/* 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);
+  opt_result res = opt_result::success ();
+
+  if (! DR_BASE_ADDRESS (dr))
+    res = opt_result::failure_at (stmt, "%s no base address.\n", error);
+  else if (! DR_OFFSET (dr))
+    res = opt_result::failure_at (stmt, "%s no offset.\n", error);
+  else if (! DR_INIT (dr))
+    res = opt_result::failure_at (stmt, "%s no init.\n", error);
+  else if (! DR_STEP (dr))
+    res = opt_result::failure_at (stmt, "%s no step.\n", error);
+  else if (! tree_fits_uhwi_p (DR_STEP (dr)))
+    res = opt_result::failure_at (stmt, "%s step too large.\n", error);
+
+  if (!res)
+    DEBUG_PRINT (dump_data_reference (dump_file, dr));
+
+  return res;
+}
+
+/* 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
@@ -1549,7 +1668,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;

@@ -1557,33 +1676,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))
-       {
-         /* 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))))
-           {
-             free_graph (g);
-             return false;
-           }
-         add_edge (g, i, j);
-         add_edge (g, j, i);
-       }
+  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++)
+        {
+
+          data_reference_p dr2 = dri2->dr;
+          if (!(DR_IS_READ (dr1) && DR_IS_READ (dr2))
+              && dr_may_alias_p (dr1, dr2, nest))
+            {
+              /* 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;
+                }
+            }
+      }
+    }

   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++)
@@ -1703,7 +1899,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 6464d2f50ce7..03febfa39986 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 cd19e6010196..c51ea68bfb47 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/gcc.dg/graphite/alias-1.c b/gcc/testsuite/gcc.dg/graphite/alias-1.c
new file mode 100644
index 000000000000..ee80dae1df33
--- /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 *-*-* } } } */