Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -1191,6 +1191,12 @@ 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); +} + 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 @@ -1198,6 +1204,10 @@ // 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 divide 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 than one base pointer we then compute minimal @@ -1232,12 +1242,40 @@ AliasGroups.push_back(std::move(AG)); } + // Split the alias groups based on their domain. + 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> ReadOnlyPairs; SmallPtrSet NonReadOnlyBaseValues; for (AliasGroupTy &AG : AliasGroups) { NonReadOnlyBaseValues.clear(); ReadOnlyPairs.clear(); + if (AG.size() < 2) { + AG.clear(); + continue; + } + for (auto II = AG.begin(); II != AG.end();) { Value *BaseAddr = (*II)->getBaseAddr(); if (HasWriteAccess.count(BaseAddr)) { Index: polly/trunk/test/ScopInfo/aliasing_conditional_alias_groups_1.ll =================================================================== --- polly/trunk/test/ScopInfo/aliasing_conditional_alias_groups_1.ll +++ polly/trunk/test/ScopInfo/aliasing_conditional_alias_groups_1.ll @@ -0,0 +1,56 @@ +; 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 +} Index: polly/trunk/test/ScopInfo/aliasing_conditional_alias_groups_2.ll =================================================================== --- polly/trunk/test/ScopInfo/aliasing_conditional_alias_groups_2.ll +++ polly/trunk/test/ScopInfo/aliasing_conditional_alias_groups_2.ll @@ -0,0 +1,55 @@ +; 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 +; depend 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 +}