[Polly][RTC] Use the domain to split alias groups.

[jdoerfert]

Summary

We use a parametric abstraction of the domain to split alias groups
if accesses cannot be executed under the same parameter evaluation.

The two test cases check that we can remove alias groups if the
pointers which might alias are never accessed under the same parameter
evaluation and that the minimal/maximal accesses are not global but
with regards to the parameter evaluation.

[sebpop]

LGTM.

lib/Analysis/ScopInfo.cpp

1176

s/devide/divide/

1182

s/more then/more than/

test/ScopInfo/aliasing_conditional_alias_groups_2.ll

4

s/depeend/depend/

[grosser]

The patch looks technical OK to me.

Avoid alias checks all together seems clearly beneficial to me. It is not as clear if splitting alias groups for cases like the one below is worth the additional complexity or if there may even be cases where it further complicates the generated code. On the other side, as the code is self contained and can easily be moved into a sub-function we can probably see this in the future.

lib/Analysis/ScopInfo.cpp

1214

Maybe add a comment (or extract this loop into its own function)

test/ScopInfo/aliasing_conditional_alias_groups_1.ll

4

Nice.

test/ScopInfo/aliasing_conditional_alias_groups_2.ll

6

Before this change we got:

%tmp38 = icmp ne i32 %b, 0
%tmp39 = select i1 %tmp38, i64 6, i64 1024
%polly.access.B = getelementptr i32* %B, i64 %tmp39
%tmp40 = select i1 %tmp38, i64 0, i64 7
%polly.access.A = getelementptr i32* %A, i64 %tmp40
%tmp41 = icmp ule i32* %polly.access.B, %polly.access.A
%tmp42 = select i1 %tmp38, i64 1024, i64 8
%polly.access.A1 = getelementptr i32* %A, i64 %tmp42
%tmp43 = select i1 %tmp38, i64 5, i64 0
%polly.access.B2 = getelementptr i32* %B, i64 %tmp43
%tmp44 = icmp ule i32* %polly.access.A1, %polly.access.B2
%tmp45 = or i1 %tmp41, %tmp44

12 instructions

after this change we got:

%polly.access.A = getelementptr i32* %A, i64 8
%tmp42 = icmp ule i32* %polly.access.A, %B
%polly.access.B1 = getelementptr i32* %B, i64 1024
%polly.access.A2 = getelementptr i32* %A, i64 7
%tmp43 = icmp ule i32* %polly.access.B1, %polly.access.A2
%tmp44 = or i1 %tmp42, %tmp43
%polly.access.A3 = getelementptr i32* %A, i64 1024
%polly.access.B4 = getelementptr i32* %B, i64 5
%tmp45 = icmp ule i32* %polly.access.A3, %polly.access.B4
%polly.access.B5 = getelementptr i32* %B, i64 6
%tmp46 = icmp ule i32* %polly.access.B5, %A
%tmp47 = or i1 %tmp45, %tmp46
%tmp48 = and i1 %tmp44, %tmp47

13 instructions

This does not seem to be a clear improvement (in this case rather a small regression at least in terms of instruction count).

[jdoerfert]

test/ScopInfo/aliasing_conditional_alias_groups_2.ll

6

But it's more precise ;)

Just look at the alias groups we generate, two small precise ones instead of one overaproximated one :)

[jdoerfert]

Closed by commit rL218758 (authored by @jdoerfert).

lib/Analysis/ScopInfo.cpp

static int buildMinMaxAccess(__isl_take isl_set *Set, void *User) {
   MaxPMA = isl_pw_multi_aff_set_pw_aff(MaxPMA, Pos, LastDimAff);
 
   MinMaxAccesses->push_back(std::make_pair(MinPMA, MaxPMA));
 
   isl_set_free(Set);
   return 0;
 }
 
+static __isl_give isl_set *getAccessDomain(MemoryAccess *MA) {
+  isl_set *Domain = MA->getStatement()->getDomain();
+  Domain = isl_set_project_out(Domain, isl_dim_set, 0, isl_set_n_dim(Domain));
+  return isl_set_reset_tuple_id(Domain);
+}
+
 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 devide each group based on the domains of the minimal/maximal
+  //      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) 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 (AliasSet &AS : AST) {
     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));
   }
 
+  for (unsigned u = 0; u < AliasGroups.size(); u++) {
+    AliasGroupTy NewAG;
+    AliasGroupTy &AG = AliasGroups[u];
+    AliasGroupTy::iterator AGI = AG.begin();
+    isl_set *AGDomain = getAccessDomain(*AGI);
+    while (AGI != AG.end()) {
+      MemoryAccess *MA = *AGI;
+      isl_set *MADomain = getAccessDomain(MA);
+      if (isl_set_is_disjoint(AGDomain, MADomain)) {
+        NewAG.push_back(MA);
+        AGI = AG.erase(AGI);
+        isl_set_free(MADomain);
+      } else {
+        AGDomain = isl_set_union(AGDomain, MADomain);
+        AGI++;
+      }
+    }
+    if (NewAG.size() > 1)
+      AliasGroups.push_back(std::move(NewAG));
+    isl_set_free(AGDomain);
+  }
+
   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];
+    if (AG.size() < 2) {
+      AG.clear();
+      continue;
+    }
+
     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);

test/ScopInfo/aliasing_conditional_alias_groups_1.ll

+; RUN: opt %loadPolly -polly-code-generator=isl -polly-scops -analyze < %s | FileCheck %s
+;
+; Check that there is no alias group because we either access A or B never both.
+;
+; CHECK: Alias Groups (0):
+;
+;    void jd(int b, int *A, int *B) {
+;      for (int i = 0; i < 1024; i++) {
+;        if (b)
+;          A[i] = A[i - 1];
+;        else
+;          B[i] = B[i - 1];
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32 %b, i32* %A, i32* %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tobool = icmp eq i32 %b, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %tmp = add nsw i64 %indvars.iv, -1
+  %arrayidx = getelementptr inbounds i32* %A, i64 %tmp
+  %tmp3 = load i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %tmp3, i32* %arrayidx2, align 4
+  br label %if.end
+
+if.else:                                          ; preds = %for.body
+  %tmp4 = add nsw i64 %indvars.iv, -1
+  %arrayidx5 = getelementptr inbounds i32* %B, i64 %tmp4
+  %tmp5 = load i32* %arrayidx5, align 4
+  %arrayidx7 = getelementptr inbounds i32* %B, i64 %indvars.iv
+  store i32 %tmp5, i32* %arrayidx7, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/aliasing_conditional_alias_groups_2.ll

+; RUN: opt %loadPolly -polly-code-generator=isl -polly-scops -analyze < %s | FileCheck %s
+;
+; Check that we create two alias groups since the mininmal/maximal accesses
+; depeend on %b.
+;
+; CHECK: Alias Groups (2):
+;
+;    void jd(int b, int *A, int *B) {
+;      for (int i = 0; i < 1024; i++) {
+;        if (b)
+;          A[i] = B[5];
+;        else
+;          B[i] = A[7];
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32 %b, i32* %A, i32* %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tobool = icmp eq i32 %b, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32* %B, i64 5
+  %tmp = load i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %tmp, i32* %arrayidx1, align 4
+  br label %if.end
+
+if.else:                                          ; preds = %for.body
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 7
+  %tmp1 = load i32* %arrayidx2, align 4
+  %arrayidx4 = getelementptr inbounds i32* %B, i64 %indvars.iv
+  store i32 %tmp1, i32* %arrayidx4, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}