Removed redundant alias checks generated during run time.

  As specified in PR23888, run-time alias check generation is expensive
  in terms of compile-time. This reduces the compile time by computing
  minimal/maximal access only once for each base pointer

Contributed-by: Pratik Bhatu <cs12b1010@iith.ac.in>
llvm-svn: 243024

11 files changed, 177 insertions, 108 deletions

diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index d3aba3d8f9c..3cc97ab8fca 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -713,8 +713,13 @@ public:
   /// @brief Vector of minimal/maximal accesses to different arrays.
   using MinMaxVectorTy = SmallVector<MinMaxAccessTy, 4>;
 
-  /// @brief Vector of minimal/maximal access vectors one for each alias group.
-  using MinMaxVectorVectorTy = SmallVector<MinMaxVectorTy *, 4>;
+  /// @brief Pair of minimal/maximal access vectors representing
+  /// read write and read only accesses
+  using MinMaxVectorPairTy = std::pair<MinMaxVectorTy *,MinMaxVectorTy *>;
+
+  /// @brief Vector of pair of minimal/maximal access vectors representing
+  /// non read only and read only accesses for each alias group.
+  using MinMaxVectorPairVectorTy = SmallVector<MinMaxVectorPairTy, 4>;
 
 private:
   Scop(const Scop &) = delete;
@@ -815,7 +820,7 @@ private:
   ///
   /// During code generation we will create a runtime alias check for each alias
   /// group to ensure the SCoP is executed in an alias free environment.
-  MinMaxVectorVectorTy MinMaxAliasGroups;
+  MinMaxVectorPairVectorTy MinMaxAliasGroups;
 
   /// Create the static control part with a region, max loop depth of this
   /// region and parameters used in this region.
@@ -986,7 +991,7 @@ public:
   bool buildAliasGroups(AliasAnalysis &AA);
 
   /// @brief Return all alias groups for this SCoP.
-  const MinMaxVectorVectorTy &getAliasGroups() const {
+  const MinMaxVectorPairVectorTy &getAliasGroups() const {
     return MinMaxAliasGroups;
   }
 
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 5771c9b3d1b..15c1b76985c 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1465,6 +1465,23 @@ static __isl_give isl_set *getAccessDomain(MemoryAccess *MA) {
   return isl_set_reset_tuple_id(Domain);
 }
 
+/// @brief Wrapper function to calculate minimal/maximal accesses to each array.
+static bool calculateMinMaxAccess(__isl_take isl_union_map *Accesses,
+                       __isl_take isl_union_set *Domains,
+                       __isl_take isl_set *AssumedContext,
+                       Scop::MinMaxVectorTy *MinMaxAccesses){
+
+  Accesses = isl_union_map_intersect_domain(Accesses, Domains);
+  isl_union_set *Locations = isl_union_map_range(Accesses);
+  Locations = isl_union_set_intersect_params(Locations, AssumedContext);
+  Locations = isl_union_set_coalesce(Locations);
+  Locations = isl_union_set_detect_equalities(Locations);
+  bool Valid = (0 == isl_union_set_foreach_set(Locations, buildMinMaxAccess,
+                                               MinMaxAccesses));
+  isl_union_set_free(Locations);
+  return Valid;
+}
+
 bool Scop::buildAliasGroups(AliasAnalysis &AA) {
   // To create sound alias checks we perform the following steps:
   //   o) Use the alias analysis and an alias set tracker to build alias sets
@@ -1476,10 +1493,10 @@ bool Scop::buildAliasGroups(AliasAnalysis &AA) {
   //      accesses. That means two minimal/maximal accesses are only in a group
   //      if their access domains intersect, otherwise they are in different
   //      ones.
-  //   o) We split groups such that they contain at most one read only base
-  //      address.
+  //   o) We partition each group into read only and non read only accesses.
   //   o) For each group with more than one base pointer we then compute minimal
-  //      and maximal accesses to each array in this group.
+  //      and maximal accesses to each array of a group in read only and non
+  //      read only partitions separately.
   using AliasGroupTy = SmallVector<MemoryAccess *, 4>;
 
   AliasSetTracker AST(AA);
@@ -1565,9 +1582,8 @@ bool Scop::buildAliasGroups(AliasAnalysis &AA) {
 
     // If we don't have read only pointers check if there are at least two
     // non read only pointers, otherwise clear the alias group.
-    if (ReadOnlyPairs.empty()) {
-      if (NonReadOnlyBaseValues.size() <= 1)
-        AG.clear();
+    if (ReadOnlyPairs.empty() && NonReadOnlyBaseValues.size() <= 1){
+      AG.clear();
       continue;
     }
 
@@ -1577,50 +1593,51 @@ bool Scop::buildAliasGroups(AliasAnalysis &AA) {
       continue;
     }
 
-    // If we have both read only and non read only base pointers we combine
-    // the non read only ones with exactly one read only one at a time into a
-    // new alias group and clear the old alias group in the end.
-    for (const auto &ReadOnlyPair : ReadOnlyPairs) {
-      AliasGroupTy AGNonReadOnly = AG;
-      for (MemoryAccess *MA : ReadOnlyPair.second)
-        AGNonReadOnly.push_back(MA);
-      AliasGroups.push_back(std::move(AGNonReadOnly));
-    }
-    AG.clear();
-  }
-
-  for (AliasGroupTy &AG : AliasGroups) {
-    if (AG.empty())
-      continue;
-
-    MinMaxVectorTy *MinMaxAccesses = new MinMaxVectorTy();
-    MinMaxAccesses->reserve(AG.size());
+    // Calculate minimal and maximal accesses for non read only accesses.
+    MinMaxVectorTy *MinMaxAccessesNonReadOnly = new MinMaxVectorTy();
+    MinMaxAccessesNonReadOnly->reserve(AG.size());
 
     isl_union_map *Accesses = isl_union_map_empty(getParamSpace());
+
+    // AG contains only non read only accesses.
     for (MemoryAccess *MA : AG)
       Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation());
-    Accesses = isl_union_map_intersect_domain(Accesses, getDomains());
 
-    isl_union_set *Locations = isl_union_map_range(Accesses);
-    Locations = isl_union_set_intersect_params(Locations, getAssumedContext());
-    Locations = isl_union_set_coalesce(Locations);
-    Locations = isl_union_set_detect_equalities(Locations);
-    bool Valid = (0 == isl_union_set_foreach_set(Locations, buildMinMaxAccess,
-                                                 MinMaxAccesses));
-    isl_union_set_free(Locations);
-    MinMaxAliasGroups.push_back(MinMaxAccesses);
+    bool Valid = calculateMinMaxAccess(Accesses, getDomains(),
+                                       getAssumedContext(),
+                                       MinMaxAccessesNonReadOnly);
+
+    // Bail out if the number of values we need to compare is too large.
+    // This is important as the number of comparisions grows quadratically with
+    // the number of values we need to compare.
+    if (!Valid || (MinMaxAccessesNonReadOnly->size() + !ReadOnlyPairs.empty() >
+                   RunTimeChecksMaxArraysPerGroup)){
+      for (MinMaxAccessTy &MMA : *(MinMaxAccessesNonReadOnly)) {
+        isl_pw_multi_aff_free(MMA.first);
+        isl_pw_multi_aff_free(MMA.second);
+      }
+      return false;
+    }
+
+    // Calculate minimal and maximal accesses for read only accesses.
+    MinMaxVectorTy *MinMaxAccessesReadOnly = new MinMaxVectorTy();
+    MinMaxAccessesReadOnly->reserve(ReadOnlyPairs.size());
+
+    Accesses = isl_union_map_empty(getParamSpace());
+
+    for (const auto &ReadOnlyPair : ReadOnlyPairs)
+      for (MemoryAccess *MA : ReadOnlyPair.second)
+        Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation());
+
+    Valid = calculateMinMaxAccess(Accesses, getDomains(),getAssumedContext(),
+                                  MinMaxAccessesReadOnly);
+    MinMaxVectorPairTy pair(MinMaxAccessesNonReadOnly,MinMaxAccessesReadOnly);
+    MinMaxAliasGroups.push_back(pair);
 
     if (!Valid)
       return false;
   }
 
-  // Bail out if the number of values we need to compare is too large.
-  // This is important as the number of comparisions grows quadratically with
-  // the number of values we need to compare.
-  for (const auto *Values : MinMaxAliasGroups)
-    if (Values->size() > RunTimeChecksMaxArraysPerGroup)
-      return false;
-
   return true;
 }
 
@@ -1681,12 +1698,17 @@ Scop::~Scop() {
   isl_schedule_free(Schedule);
 
   // Free the alias groups
-  for (MinMaxVectorTy *MinMaxAccesses : MinMaxAliasGroups) {
-    for (MinMaxAccessTy &MMA : *MinMaxAccesses) {
+  for (MinMaxVectorPairTy &MinMaxAccessPair : MinMaxAliasGroups) {
+    for (MinMaxAccessTy &MMA : *(MinMaxAccessPair.first)) {
       isl_pw_multi_aff_free(MMA.first);
       isl_pw_multi_aff_free(MMA.second);
     }
-    delete MinMaxAccesses;
+    for (MinMaxAccessTy &MMA : *(MinMaxAccessPair.second)) {
+      isl_pw_multi_aff_free(MMA.first);
+      isl_pw_multi_aff_free(MMA.second);
+    }
+    delete MinMaxAccessPair.first;
+    delete MinMaxAccessPair.second;
   }
 }
 
@@ -1766,16 +1788,42 @@ void Scop::printContext(raw_ostream &OS) const {
 }
 
 void Scop::printAliasAssumptions(raw_ostream &OS) const {
-  OS.indent(4) << "Alias Groups (" << MinMaxAliasGroups.size() << "):\n";
+  int noOfGroups=0;
+  for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups){
+    if (Pair.second->size() == 0)
+      noOfGroups += 1;
+    else
+      noOfGroups += Pair.second->size();
+  }
+
+  OS.indent(4) << "Alias Groups (" << noOfGroups  << "):\n";
   if (MinMaxAliasGroups.empty()) {
     OS.indent(8) << "n/a\n";
     return;
   }
-  for (MinMaxVectorTy *MinMaxAccesses : MinMaxAliasGroups) {
-    OS.indent(8) << "[[";
-    for (MinMaxAccessTy &MinMacAccess : *MinMaxAccesses)
-      OS << " <" << MinMacAccess.first << ", " << MinMacAccess.second << ">";
-    OS << " ]]\n";
+
+  for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups){
+
+    // If the group has no read only accesses print the write accesses.
+    if (Pair.second->empty()){
+      OS.indent(8) << "[[";
+      for (MinMaxAccessTy &MMANonReadOnly : *(Pair.first)){
+        OS << " <" << MMANonReadOnly.first << ", "
+           << MMANonReadOnly.second << ">";
+      }
+      OS << " ]]\n";
+    }
+
+    for (MinMaxAccessTy &MMAReadOnly : *(Pair.second)){
+      OS.indent(8) << "[[";
+      OS << " <" << MMAReadOnly.first << ", "
+         << MMAReadOnly.second << ">";
+      for (MinMaxAccessTy &MMANonReadOnly : *(Pair.first)){
+        OS << " <" << MMANonReadOnly.first << ", "
+           << MMANonReadOnly.second << ">";
+      }
+      OS << " ]]\n";
+    }
   }
 }
 
diff --git a/polly/lib/CodeGen/IslAst.cpp b/polly/lib/CodeGen/IslAst.cpp
index 9f564bc4745..7d9ce1a3627 100644
--- a/polly/lib/CodeGen/IslAst.cpp
+++ b/polly/lib/CodeGen/IslAst.cpp
@@ -303,6 +303,30 @@ static __isl_give isl_ast_node *AtEachDomain(__isl_take isl_ast_node *Node,
   return isl_ast_node_set_annotation(Node, Id);
 }
 
+// Build alias check condition given a pair of minimal/maximal access.
+static __isl_give isl_ast_expr *buildCondition(__isl_keep isl_ast_build *Build,
+                             Scop::MinMaxAccessTy *It0,
+                             Scop::MinMaxAccessTy *It1){
+    isl_ast_expr *NonAliasGroup,*MinExpr, *MaxExpr;
+    MinExpr =
+        isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+            Build, isl_pw_multi_aff_copy(It0->first)));
+    MaxExpr =
+        isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+            Build, isl_pw_multi_aff_copy(It1->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(It1->first)));
+    MaxExpr =
+        isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+            Build, isl_pw_multi_aff_copy(It0->second)));
+    NonAliasGroup =
+        isl_ast_expr_or(NonAliasGroup, isl_ast_expr_le(MaxExpr, MinExpr));
+
+    return NonAliasGroup;
+}
+
 void IslAst::buildRunCondition(__isl_keep isl_ast_build *Build) {
   // The conditions that need to be checked at run-time for this scop are
   // available as an isl_set in the AssumedContext from which we can directly
@@ -310,30 +334,22 @@ void IslAst::buildRunCondition(__isl_keep isl_ast_build *Build) {
   RunCondition = isl_ast_build_expr_from_set(Build, S->getAssumedContext());
 
   // 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);
-      }
+  // group which consists of read only and non read only (read write) accesses.
+  // This operation is by construction quadratic in the read-write pointers and
+  // linear int the read only pointers in each alias group.
+  for (const Scop::MinMaxVectorPairTy &MinMaxAccessPair : S->getAliasGroups()) {
+    auto *MinMaxReadWrite = MinMaxAccessPair.first;
+    auto *MinMaxReadOnly = MinMaxAccessPair.second;
+    auto RWAccEnd = MinMaxReadWrite->end();
+
+    for (auto RWAccIt0 = MinMaxReadWrite->begin(); RWAccIt0 != RWAccEnd;
+         ++RWAccIt0) {
+      for (auto RWAccIt1 = RWAccIt0 + 1; RWAccIt1 != RWAccEnd; ++RWAccIt1)
+        RunCondition = isl_ast_expr_and(RunCondition,
+                                       buildCondition(Build,RWAccIt0,RWAccIt1));
+      for (Scop::MinMaxAccessTy &ROAccIt : *MinMaxReadOnly)
+        RunCondition = isl_ast_expr_and(RunCondition,
+                                       buildCondition(Build,RWAccIt0,&ROAccIt));
     }
   }
 }
diff --git a/polly/test/Isl/Ast/alias_simple_1.ll b/polly/test/Isl/Ast/alias_simple_1.ll
index 17145ee996e..f441cc87d25 100644
--- a/polly/test/Isl/Ast/alias_simple_1.ll
+++ b/polly/test/Isl/Ast/alias_simple_1.ll
@@ -12,11 +12,11 @@
 ;        A[i] = B[i];
 ;    }
 ;
-; NOAA: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
-; BASI: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; NOAA: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
+; BASI: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
 ; TBAA: if (N <= 1024)
-; SCEV: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
-; GLOB: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; SCEV: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
+; GLOB: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/Isl/Ast/alias_simple_2.ll b/polly/test/Isl/Ast/alias_simple_2.ll
index e2489ac7ef9..ba8283b17ea 100644
--- a/polly/test/Isl/Ast/alias_simple_2.ll
+++ b/polly/test/Isl/Ast/alias_simple_2.ll
@@ -12,11 +12,11 @@
 ;        A[i] = B[i];
 ;    }
 ;
-; NOAA: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; NOAA: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
 ; BASI: if (N <= 1024)
-; TBAA: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
-; SCEV: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
-; GLOB: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; TBAA: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
+; SCEV: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
+; GLOB: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/Isl/Ast/alias_simple_3.ll b/polly/test/Isl/Ast/alias_simple_3.ll
index 2e42214cfc1..e3aeb7b1242 100644
--- a/polly/test/Isl/Ast/alias_simple_3.ll
+++ b/polly/test/Isl/Ast/alias_simple_3.ll
@@ -12,11 +12,11 @@
 ;        A[i] = B[i];
 ;    }
 ;
-; NOAA: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; NOAA: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
 ; BASI: if (N <= 1024)
 ; TBAA: if (N <= 1024)
-; SCEV: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
-; GLOB: if (N <= 1024 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; SCEV: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
+; GLOB: if (N <= 1024 && (&MemRef_B[N] <= &MemRef_A[0] || &MemRef_A[N] <= &MemRef_B[0]))
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/Isl/Ast/aliasing_multiple_alias_groups.ll b/polly/test/Isl/Ast/aliasing_multiple_alias_groups.ll
index 7f214edd6c3..6d3531f9b19 100644
--- a/polly/test/Isl/Ast/aliasing_multiple_alias_groups.ll
+++ b/polly/test/Isl/Ast/aliasing_multiple_alias_groups.ll
@@ -9,15 +9,15 @@
 ;    }
 ;
 ; NOAA:      if (1 && (
-; NOAA-DAG:    &MemRef_Float0[1024] <= &MemRef_Int0[0] || &MemRef_Int0[1024] <= &MemRef_Float0[0]
-; NOAA-DAG:    &MemRef_Float1[1024] <= &MemRef_Int0[0] || &MemRef_Int0[1024] <= &MemRef_Float1[0]
-; NOAA-DAG:    &MemRef_Int1[1024] <= &MemRef_Int0[0] || &MemRef_Int0[1024] <= &MemRef_Int1[0]
-; NOAA-DAG:    &MemRef_Float0[1024] <= &MemRef_Float1[0] || &MemRef_Float1[1024] <= &MemRef_Float0[0]
+; NOAA-DAG:    &MemRef_Int0[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Int0[0]
 ; NOAA-DAG:    &MemRef_Int1[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Int1[0]
+; NOAA-DAG:    &MemRef_Float1[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Float1[0]
+; NOAA-DAG:    &MemRef_Int1[1024] <= &MemRef_Int0[0] || &MemRef_Int0[1024] <= &MemRef_Int1[0]
+; NOAA-DAG:    &MemRef_Float1[1024] <= &MemRef_Int0[0] || &MemRef_Int0[1024] <= &MemRef_Float1[0]
 ; NOAA:      ))
 ;
 ; TBAA:      if (1 && (
-; TBAA-DAG:    &MemRef_Int0[1024] <= &MemRef_Int1[0] || &MemRef_Int1[1024] <= &MemRef_Int0[0]
+; TBAA-DAG:    &MemRef_Int1[1024] <= &MemRef_Int0[0] || &MemRef_Int0[1024] <= &MemRef_Int1[0]
 ; TBAA-DAG:    &MemRef_Float1[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Float1[0]
 ; TBAA:      ))
 ;
diff --git a/polly/test/Isl/Ast/aliasing_parametric_simple_1.ll b/polly/test/Isl/Ast/aliasing_parametric_simple_1.ll
index 1ae73d34912..cdd5b67281c 100644
--- a/polly/test/Isl/Ast/aliasing_parametric_simple_1.ll
+++ b/polly/test/Isl/Ast/aliasing_parametric_simple_1.ll
@@ -5,7 +5,7 @@
 ;        A[i] = B[c];
 ;    }
 ;
-; CHECK: if (1 && (&MemRef_A[1024] <= &MemRef_B[c] || &MemRef_B[c + 1] <= &MemRef_A[0]))
+; CHECK: if (1 && (&MemRef_B[c + 1] <= &MemRef_A[0] || &MemRef_A[1024] <= &MemRef_B[c]))
 ; CHECK:     for (int c0 = 0; c0 <= 1023; c0 += 1)
 ; CHECK:       Stmt_for_body(c0);
 ; CHECK: else
diff --git a/polly/test/Isl/Ast/aliasing_parametric_simple_2.ll b/polly/test/Isl/Ast/aliasing_parametric_simple_2.ll
index bb0ac5753d3..67b50cc378d 100644
--- a/polly/test/Isl/Ast/aliasing_parametric_simple_2.ll
+++ b/polly/test/Isl/Ast/aliasing_parametric_simple_2.ll
@@ -5,7 +5,7 @@
 ;        A[i] = B[c - 10] + B[5];
 ;    }
 ;
-; CHECK: if (1 && (&MemRef_A[1024] <= &MemRef_B[c >= 15 ? 5 : c - 10] || &MemRef_B[c <= 15 ? 6 : c - 9] <= &MemRef_A[0]))
+; CHECK: if (1 && (&MemRef_B[c <= 15 ? 6 : c - 9] <= &MemRef_A[0] || &MemRef_A[1024] <= &MemRef_B[c >= 15 ? 5 : c - 10]))
 ; CHECK:     for (int c0 = 0; c0 <= 1023; c0 += 1)
 ; CHECK:       Stmt_for_body(c0);
 ; CHECK: else
diff --git a/polly/test/Isl/CodeGen/aliasing_parametric_simple_1.ll b/polly/test/Isl/CodeGen/aliasing_parametric_simple_1.ll
index 28da51460f6..d24b3af5c7d 100644
--- a/polly/test/Isl/CodeGen/aliasing_parametric_simple_1.ll
+++ b/polly/test/Isl/CodeGen/aliasing_parametric_simple_1.ll
@@ -5,15 +5,15 @@
 ;        A[i] = B[c];
 ;    }
 ;
-; CHECK:  %[[AMax:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 1024
-; CHECK:  %[[BMin:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %B, i32 %c
-; CHECK:  %[[AltB:[._a-zA-Z0-9]*]] = icmp ule i32* %[[AMax]], %[[BMin]]
 ; CHECK:  %[[Cext:[._a-zA-Z0-9]*]] = sext i32 %c to i64
 ; CHECK:  %[[Cp1:[._a-zA-Z0-9]*]] = add nsw i64 %[[Cext]], 1
 ; CHECK:  %[[BMax:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %B, i64 %[[Cp1]]
 ; CHECK:  %[[AMin:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 0
 ; CHECK:  %[[BltA:[._a-zA-Z0-9]*]] = icmp ule i32* %[[BMax]], %[[AMin]]
-; CHECK:  %[[NoAlias:[._a-zA-Z0-9]*]] = or i1 %[[AltB]], %[[BltA]]
+; CHECK:  %[[AMax:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 1024
+; CHECK:  %[[BMin:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %B, i32 %c
+; CHECK:  %[[AltB:[._a-zA-Z0-9]*]] = icmp ule i32* %[[AMax]], %[[BMin]]
+; CHECK:  %[[NoAlias:[._a-zA-Z0-9]*]] = or i1 %[[BltA]], %[[AltB]]
 ; CHECK:  %[[RTC:[._a-zA-Z0-9]*]] = and i1 true, %[[NoAlias]]
 ; CHECK:  br i1 %[[RTC]], label %polly.start, label %for.cond
 ;
diff --git a/polly/test/Isl/CodeGen/aliasing_parametric_simple_2.ll b/polly/test/Isl/CodeGen/aliasing_parametric_simple_2.ll
index 972ce0a69d3..f4f9f4c2634 100644
--- a/polly/test/Isl/CodeGen/aliasing_parametric_simple_2.ll
+++ b/polly/test/Isl/CodeGen/aliasing_parametric_simple_2.ll
@@ -5,14 +5,6 @@
 ;        A[i] = B[c - 10] + B[5];
 ;    }
 ;
-; CHECK:  %[[AMax:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 1024
-; CHECK:  %[[m0:[._a-zA-Z0-9]*]] = sext i32 %c to i64
-; CHECK:  %[[m1:[._a-zA-Z0-9]*]] = icmp sge i64 %[[m0]], 15
-; CHECK:  %[[m2:[._a-zA-Z0-9]*]] = sext i32 %c to i64
-; CHECK:  %[[m3:[._a-zA-Z0-9]*]] = sub nsw i64 %[[m2]], 10
-; CHECK:  %[[m4:[._a-zA-Z0-9]*]] = select i1 %[[m1]], i64 5, i64 %[[m3]]
-; CHECK:  %[[BMin:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %B, i64 %[[m4]]
-; CHECK:  %[[AltB:[._a-zA-Z0-9]*]] = icmp ule i32* %[[AMax]], %[[BMin]]
 ; CHECK:  %[[M0:[._a-zA-Z0-9]*]] = sext i32 %c to i64
 ; CHECK:  %[[M1:[._a-zA-Z0-9]*]] = icmp sle i64 %[[M0]], 15
 ; CHECK:  %[[M2:[._a-zA-Z0-9]*]] = sext i32 %c to i64
@@ -21,7 +13,15 @@
 ; CHECK:  %[[BMax:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %B, i64 %[[M4]]
 ; CHECK:  %[[AMin:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 0
 ; CHECK:  %[[BltA:[._a-zA-Z0-9]*]] = icmp ule i32* %[[BMax]], %[[AMin]]
-; CHECK:  %[[NoAlias:[._a-zA-Z0-9]*]] = or i1 %[[AltB]], %[[BltA]]
+; CHECK:  %[[AMax:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 1024
+; CHECK:  %[[m0:[._a-zA-Z0-9]*]] = sext i32 %c to i64
+; CHECK:  %[[m1:[._a-zA-Z0-9]*]] = icmp sge i64 %[[m0]], 15
+; CHECK:  %[[m2:[._a-zA-Z0-9]*]] = sext i32 %c to i64
+; CHECK:  %[[m3:[._a-zA-Z0-9]*]] = sub nsw i64 %[[m2]], 10
+; CHECK:  %[[m4:[._a-zA-Z0-9]*]] = select i1 %[[m1]], i64 5, i64 %[[m3]]
+; CHECK:  %[[BMin:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %B, i64 %[[m4]]
+; CHECK:  %[[AltB:[._a-zA-Z0-9]*]] = icmp ule i32* %[[AMax]], %[[BMin]]
+; CHECK:  %[[NoAlias:[._a-zA-Z0-9]*]] = or i1 %[[BltA]], %[[AltB]]
 ; CHECK:  %[[RTC:[._a-zA-Z0-9]*]] = and i1 true, %[[NoAlias]]
 ; CHECK:  br i1 %[[RTC]], label %polly.start, label %for.cond
 ;