[Polly][RTC] Split alias groups according to read only base addresses

[jdoerfert]

Summary

If there are multiple read only base addresses in an alias group
we can split it into multiple alias groups each with only one
read only alias group. This way we might reduce the number of
comparisons significantly as it grows linear in the number of
alias groups but exponential in their size.

[grosser]

If there are multiple read only base addresses in an alias group
we can split it into multiple alias groups each with only one
read only alias group. This way we might reduce the number of

read only access.

comparisons significantly as it grows linear in the number of
alias groups but exponential in their size.

lib/Analysis/ScopInfo.cpp

1206

C++11 range based for?

[jdoerfert]

Closed by commit rL218757 (authored by @jdoerfert).

lib/Analysis/ScopInfo.cpp

 
 void 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
   //      for all memory accesses inside the SCoP.
   //   o) For each alias set we then map the aliasing pointers back to the
   //      memory accesses we know, thus obtain groups of memory accesses which
   //      might alias.
+  //   o) We split groups such that they contain at most one read only base
+  //      address.
   //   o) For each group with more then one base pointer we then compute minimal
   //      and maximal accesses to each array in this group.
   using AliasGroupTy = SmallVector<MemoryAccess *, 4>;
 
   AliasSetTracker AST(AA);
 
   DenseMap<Value *, MemoryAccess *> PtrToAcc;
+  DenseSet<Value *> HasWriteAccess;
   for (ScopStmt *Stmt : *this) {
     for (MemoryAccess *MA : *Stmt) {
       if (MA->isScalar())
         continue;
+      if (!MA->isRead())
+        HasWriteAccess.insert(MA->getBaseAddr());
       Instruction *Acc = MA->getAccessInstruction();
       PtrToAcc[getPointerOperand(*Acc)] = MA;
       AST.add(Acc);
     }
   }
 
   SmallVector<AliasGroupTy, 4> AliasGroups;
   for (AliasSet &AS : AST) {
     if (AS.isMustAlias())
       continue;
     AliasGroupTy AG;
     for (auto PR : AS)
       AG.push_back(PtrToAcc[PR.getValue()]);
     assert(AG.size() > 1 &&
            "Alias groups should contain at least two accesses");
     AliasGroups.push_back(std::move(AG));
   }
 
-  SmallPtrSet<const Value *, 4> BaseValues;
-  for (auto I = AliasGroups.begin(); I != AliasGroups.end();) {
-    BaseValues.clear();
-    for (MemoryAccess *MA : *I)
-      BaseValues.insert(MA->getBaseAddr());
-    if (BaseValues.size() > 1)
-      I++;
-    else
-      I = AliasGroups.erase(I);
+  DenseMap<const Value *, SmallPtrSet<MemoryAccess *, 8>> ReadOnlyPairs;
+  SmallPtrSet<const Value *, 4> NonReadOnlyBaseValues;
+  for (unsigned u = 0, e = AliasGroups.size(); u < e; u++) {
+    NonReadOnlyBaseValues.clear();
+    ReadOnlyPairs.clear();
+
+    AliasGroupTy &AG = AliasGroups[u];
+    for (auto II = AG.begin(); II != AG.end();) {
+      Value *BaseAddr = (*II)->getBaseAddr();
+      if (HasWriteAccess.count(BaseAddr)) {
+        NonReadOnlyBaseValues.insert(BaseAddr);
+        II++;
+      } else {
+        ReadOnlyPairs[BaseAddr].insert(*II);
+        II = AG.erase(II);
+      }
+    }
+
+    // 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();
+      continue;
+    }
+
+    // If we don't have non read only pointers clear the alias group.
+    if (NonReadOnlyBaseValues.empty()) {
+      AG.clear();
+      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());
 
     isl_union_map *Accesses = isl_union_map_empty(getParamSpace());
     for (MemoryAccess *MA : AG)
       Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation());
     Accesses = isl_union_map_intersect_domain(Accesses, getDomains());
 

test/Isl/Ast/aliasing_multiple_alias_groups.ll

 ; RUN: opt %loadPolly -polly-code-generator=isl -polly-ast -analyze          < %s | FileCheck %s --check-prefix=NOAA
 ; RUN: opt %loadPolly -polly-code-generator=isl -polly-ast -analyze -tbaa    < %s | FileCheck %s --check-prefix=TBAA
 ;
 ;    void jd(int *Int0, int *Int1, float *Float0, float *Float1) {
 ;      for (int i = 0; i < 1024; i++) {
 ;        Int0[i] = Int1[i];
 ;        Float0[i] = Float1[i];
 ;      }
 ;    }
 ;
 ; 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_Float1[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Float1[0]
+; NOAA-DAG:    &MemRef_Float0[1024] <= &MemRef_Float1[0] || &MemRef_Float1[1024] <= &MemRef_Float0[0]
 ; NOAA-DAG:    &MemRef_Int1[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Int1[0]
-; NOAA-DAG:    &MemRef_Int1[1024] <= &MemRef_Float1[0] || &MemRef_Float1[1024] <= &MemRef_Int1[0]
 ; NOAA:      ))
 ;
 ; TBAA:      if (1 && (
 ; TBAA-DAG:    &MemRef_Int0[1024] <= &MemRef_Int1[0] || &MemRef_Int1[1024] <= &MemRef_Int0[0]
 ; TBAA-DAG:    &MemRef_Float1[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Float1[0]
 ; TBAA:      ))
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

test/ScopInfo/aliasing_multiple_alias_groups.ll

 
 !0 = metadata !{metadata !1, metadata !1, i64 0}
 !1 = metadata !{metadata !"int", metadata !2, i64 0}
 !2 = metadata !{metadata !"omnipotent char", metadata !3, i64 0}
 !3 = metadata !{metadata !"Simple C/C++ TBAA"}
 !4 = metadata !{metadata !5, metadata !5, i64 0}
 !5 = metadata !{metadata !"float", metadata !2, i64 0}
 
-; NOAA: Alias Groups (1):
+; NOAA: Alias Groups (2):
+; NOAA-NEXT: {{\[\[}}
 ; NOAA-DAG:      <{ MemRef_Int0[(0)] }, { MemRef_Int0[(1024)] }>
-; NOAA-DAG:      <{ MemRef_Int1[(0)] }, { MemRef_Int1[(1024)] }>
+; NOAA-DAG:      <{ MemRef_{{(Int|Float)}}1[(0)] }, { MemRef_{{(Int|Float)}}1[(1024)] }>
 ; NOAA-DAG:      <{ MemRef_Float0[(0)] }, { MemRef_Float0[(1024)] }>
-; NOAA-DAG:      <{ MemRef_Float1[(0)] }, { MemRef_Float1[(1024)] }>
+; NOAA:      {{\]\]}}
+; NOAA-NEXT: {{\[\[}}
+; NOAA-DAG:      <{ MemRef_Int0[(0)] }, { MemRef_Int0[(1024)] }>
+; NOAA-DAG:      <{ MemRef_Float0[(0)] }, { MemRef_Float0[(1024)] }>
+; NOAA-DAG:      <{ MemRef_{{(Int|Float)}}1[(0)] }, { MemRef_{{(Int|Float)}}1[(1024)] }>
+; NOAA:      {{\]\]}}
+
 
-; TBAA-DAG: Alias Groups (2):
+; TBAA: Alias Groups (2):
+; TBAA-NEXT: {{\[\[}}
 ; TBAA-DAG:      <{ MemRef_Int0[(0)] }, { MemRef_Int0[(1024)] }>
 ; TBAA-DAG:      <{ MemRef_Int1[(0)] }, { MemRef_Int1[(1024)] }>
+; TBAA:      {{\]\]}}
+; TBAA-NEXT: {{\[\[}}
 ; TBAA-DAG:      <{ MemRef_Float0[(0)] }, { MemRef_Float0[(1024)] }>
 ; TBAA-DAG:      <{ MemRef_Float1[(0)] }, { MemRef_Float1[(1024)] }>
+; TBBA:      {{\]\]}}

test/ScopInfo/run-time-check-read-only-arrays.ll

+; RUN: opt %loadPolly -polly-code-generator=isl -polly-scops -analyze < %s | FileCheck %s
+;
+; void foo(float *A, float *B, float *C, long N) {
+;   for (long i = 0; i < N; i++)
+;     C[i] = A[i] + B[i];
+; }
+;
+; CHECK: Alias Groups (2):
+;
+; This test case verifies that we do not create run-time checks for two
+; read-only arrays.
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @foo(float* %A, float* %B, float* %C, i64 %N) {
+entry:
+  br label %for.body
+
+for.body:
+  %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %for.body ]
+  %arrayidx.A = getelementptr float* %A, i64 %indvar
+  %arrayidx.B = getelementptr float* %B, i64 %indvar
+  %arrayidx.C = getelementptr float* %C, i64 %indvar
+  %val.A = load float* %arrayidx.A
+  %val.B = load float* %arrayidx.B
+  %add = fadd float %val.A, %val.B
+  store float %add, float* %arrayidx.C
+  %indvar.next = add nsw i64 %indvar, 1
+  %exitcond = icmp ne i64 %indvar.next, %N
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:
+  ret void
+}