[RTC] Runtime Alias Checks for the ISL backend

  This change will build all alias groups (minimal/maximal accesses
  to possible aliasing base pointers) we have to check before
  we can assume an alias free environment. It will also use these
  to create Runtime Alias Checks (RTC) in the ISL code generation
  backend, thus allow us to optimize SCoPs despite possibly aliasing
  pointers when this backend is used.

  This feature will be enabled for the isl code generator, e.g.,
  --polly-code-generator=isl, but disabled for:
    - The cloog code generator (still the default).
    - The case delinearization is enabled.
    - The case non-affine accesses are allowed.

llvm-svn: 218046

1 files changed, 28 insertions, 0 deletions

diff --git a/polly/lib/CodeGen/IslAst.cpp b/polly/lib/CodeGen/IslAst.cpp
index 81fb8d74362..9c5070ecd6e 100644
--- a/polly/lib/CodeGen/IslAst.cpp
+++ b/polly/lib/CodeGen/IslAst.cpp
@@ -310,6 +310,34 @@ void IslAst::buildRunCondition(__isl_keep isl_ast_build *Build) {
   isl_pw_aff *Cond = isl_pw_aff_union_max(PwOne, PwZero);
 
   RunCondition = isl_ast_build_expr_from_pw_aff(Build, Cond);
+
+  // Create the alias checks from the minimal/maximal accesses in each alias
+  // group. This operation is by construction quadratic in the number of
+  // elements in each alias group.
+  isl_ast_expr *NonAliasGroup, *MinExpr, *MaxExpr;
+  for (const Scop::MinMaxVectorTy *MinMaxAccesses : S->getAliasGroups()) {
+    auto AccEnd = MinMaxAccesses->end();
+    for (auto AccIt0 = MinMaxAccesses->begin(); AccIt0 != AccEnd; ++AccIt0) {
+      for (auto AccIt1 = AccIt0 + 1; AccIt1 != AccEnd; ++AccIt1) {
+        MinExpr =
+            isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+                Build, isl_pw_multi_aff_copy(AccIt0->first)));
+        MaxExpr =
+            isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+                Build, isl_pw_multi_aff_copy(AccIt1->second)));
+        NonAliasGroup = isl_ast_expr_le(MaxExpr, MinExpr);
+        MinExpr =
+            isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+                Build, isl_pw_multi_aff_copy(AccIt1->first)));
+        MaxExpr =
+            isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+                Build, isl_pw_multi_aff_copy(AccIt0->second)));
+        NonAliasGroup =
+            isl_ast_expr_or(NonAliasGroup, isl_ast_expr_le(MaxExpr, MinExpr));
+        RunCondition = isl_ast_expr_and(RunCondition, NonAliasGroup);
+      }
+    }
+  }
 }
 
 IslAst::IslAst(Scop *Scop, Dependences &D) : S(Scop) {