Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -1198,17 +1198,22 @@ // 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) For each group with more then one base pointer we then compute minimal + // 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 // and maximal accesses to each array in this group. using AliasGroupTy = SmallVector; AliasSetTracker AST(AA); DenseMap PtrToAcc; + DenseSet 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); @@ -1227,19 +1232,54 @@ AliasGroups.push_back(std::move(AG)); } - SmallPtrSet 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> ReadOnlyPairs; + SmallPtrSet NonReadOnlyBaseValues; + for (AliasGroupTy &AG : AliasGroups) { + NonReadOnlyBaseValues.clear(); + ReadOnlyPairs.clear(); + + 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(); } bool Valid = true; for (AliasGroupTy &AG : AliasGroups) { + if (AG.empty()) + continue; + MinMaxVectorTy *MinMaxAccesses = new MinMaxVectorTy(); MinMaxAccesses->reserve(AG.size()); Index: polly/trunk/test/Isl/Ast/aliasing_multiple_alias_groups.ll =================================================================== --- polly/trunk/test/Isl/Ast/aliasing_multiple_alias_groups.ll +++ polly/trunk/test/Isl/Ast/aliasing_multiple_alias_groups.ll @@ -12,9 +12,8 @@ ; 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 && ( Index: polly/trunk/test/ScopInfo/aliasing_multiple_alias_groups.ll =================================================================== --- polly/trunk/test/ScopInfo/aliasing_multiple_alias_groups.ll +++ polly/trunk/test/ScopInfo/aliasing_multiple_alias_groups.ll @@ -39,14 +39,25 @@ !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: {{\]\]}} Index: polly/trunk/test/ScopInfo/run-time-check-read-only-arrays.ll =================================================================== --- polly/trunk/test/ScopInfo/run-time-check-read-only-arrays.ll +++ polly/trunk/test/ScopInfo/run-time-check-read-only-arrays.ll @@ -0,0 +1,33 @@ +; 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 +}