diff options
| -rw-r--r-- | llvm/lib/Analysis/DependenceAnalysis.cpp | 47 | ||||
| -rw-r--r-- | llvm/test/Analysis/DependenceAnalysis/AA.ll | 140 |
2 files changed, 177 insertions, 10 deletions
diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index b63ec2772e4..72ee33c41c3 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -621,13 +621,38 @@ void Dependence::dump(raw_ostream &OS) const { OS << "!\n"; } +// Returns NoAlias/MayAliass/MustAlias for two memory locations based upon their +// underlaying objects. If LocA and LocB are known to not alias (for any reason: +// tbaa, non-overlapping regions etc), then it is known there is no dependecy. +// Otherwise the underlying objects are checked to see if they point to +// different identifiable objects. static AliasResult underlyingObjectsAlias(AliasAnalysis *AA, - const DataLayout &DL, const Value *A, - const Value *B) { - const Value *AObj = GetUnderlyingObject(A, DL); - const Value *BObj = GetUnderlyingObject(B, DL); - return AA->alias(AObj, DL.getTypeStoreSize(AObj->getType()), - BObj, DL.getTypeStoreSize(BObj->getType())); + const DataLayout &DL, + const MemoryLocation &LocA, + const MemoryLocation &LocB) { + // Check the original locations (minus size) for noalias, which can happen for + // tbaa, incompatible underlying object locations, etc. + MemoryLocation LocAS(LocA.Ptr, MemoryLocation::UnknownSize, LocA.AATags); + MemoryLocation LocBS(LocB.Ptr, MemoryLocation::UnknownSize, LocB.AATags); + if (AA->alias(LocAS, LocBS) == NoAlias) + return NoAlias; + + // Check the underlying objects are the same + const Value *AObj = GetUnderlyingObject(LocA.Ptr, DL); + const Value *BObj = GetUnderlyingObject(LocB.Ptr, DL); + + // If the underlying objects are the same, they must alias + if (AObj == BObj) + return MustAlias; + + // We may have hit the recursion limit for underlying objects, or have + // underlying objects where we don't know they will alias. + if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj)) + return MayAlias; + + // Otherwise we know the objects are different and both identified objects so + // must not alias. + return NoAlias; } @@ -3298,8 +3323,9 @@ DependenceInfo::depends(Instruction *Src, Instruction *Dst, Value *SrcPtr = getLoadStorePointerOperand(Src); Value *DstPtr = getLoadStorePointerOperand(Dst); - switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr, - SrcPtr)) { + switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), + MemoryLocation::get(Dst), + MemoryLocation::get(Src))) { case MayAlias: case PartialAlias: // cannot analyse objects if we don't understand their aliasing. @@ -3715,8 +3741,9 @@ const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep, assert(isLoadOrStore(Dst)); Value *SrcPtr = getLoadStorePointerOperand(Src); Value *DstPtr = getLoadStorePointerOperand(Dst); - assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr, - SrcPtr) == MustAlias); + assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), + MemoryLocation::get(Dst), + MemoryLocation::get(Src)) == MustAlias); // establish loop nesting levels establishNestingLevels(Src, Dst); diff --git a/llvm/test/Analysis/DependenceAnalysis/AA.ll b/llvm/test/Analysis/DependenceAnalysis/AA.ll new file mode 100644 index 00000000000..0d213e25e13 --- /dev/null +++ b/llvm/test/Analysis/DependenceAnalysis/AA.ll @@ -0,0 +1,140 @@ +; RUN: opt < %s -analyze -basicaa -tbaa -da | FileCheck %s + +; CHECK-LABEL: 'Dependence Analysis' for function 'test_no_noalias' +; CHECK: da analyze - none! +; CHECK: da analyze - confused! +; CHECK: da analyze - none! +define void @test_no_noalias(i32* %A, i32* %B) { + store i32 1, i32* %A + store i32 2, i32* %B + ret void +} + +; CHECK-LABEL: test_one_noalias +; CHECK: da analyze - none! +; CHECK: da analyze - none! +; CHECK: da analyze - none! +define void @test_one_noalias(i32* noalias %A, i32* %B) { + store i32 1, i32* %A + store i32 2, i32* %B + ret void +} + +; CHECK-LABEL: test_two_noalias +; CHECK: da analyze - none! +; CHECK: da analyze - none! +; CHECK: da analyze - none! +define void @test_two_noalias(i32* noalias %A, i32* noalias %B) { + store i32 1, i32* %A + store i32 2, i32* %B + ret void +} + +; CHECK-LABEL: test_global_alias +; CHECK: da analyze - none! +; CHECK: da analyze - confused! +; CHECK: da analyze - none! +@g = global i32 5 +define void @test_global_alias(i32* %A) { + store i32 1, i32* %A + store i32 2, i32* @g + ret void +} + +; CHECK-LABEL: test_global_noalias +; CHECK: da analyze - none! +; CHECK: da analyze - none! +; CHECK: da analyze - none! +define void @test_global_noalias(i32* noalias %A) { + store i32 1, i32* %A + store i32 2, i32* @g + ret void +} + +; CHECK-LABEL: test_global_size +; CHECK: da analyze - none! +; CHECK: da analyze - confused! +; CHECK: da analyze - none! +; CHECK: da analyze - none! +; CHECK: da analyze - confused! +; CHECK: da analyze - none! + +@a = global i16 5, align 2 +@b = global i16* @a, align 4 +define void @test_global_size() { + %l0 = load i16*, i16** @b, align 4 + %l1 = load i16, i16* %l0, align 2 + store i16 1, i16* @a, align 2 + ret void +} + +; CHECK-LABEL: test_tbaa_same +; CHECK: da analyze - none! +; CHECK: da analyze - confused! +; CHECK: da analyze - none! +define void @test_tbaa_same(i32* %A, i32* %B) { + store i32 1, i32* %A, !tbaa !5 + store i32 2, i32* %B, !tbaa !5 + ret void +} + +; CHECK-LABEL: test_tbaa_diff +; CHECK: da analyze - none! +; CHECK: da analyze - none! +; CHECK: da analyze - none! +define void @test_tbaa_diff(i32* %A, i16* %B) { + store i32 1, i32* %A, !tbaa !5 + store i16 2, i16* %B, !tbaa !9 + ret void +} + +; CHECK-LABEL: tbaa_loop +; CHECK: da analyze - input +; CHECK: da analyze - none +; CHECK: da analyze - output +define void @tbaa_loop(i32 %I, i32 %J, i32* nocapture %A, i16* nocapture readonly %B) { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i16, i16* %B, i32 %j.us + %0 = load i16, i16* %arrayidx.us, align 4, !tbaa !9 + %sext = sext i16 %0 to i32 + %add.us = add i32 %sext, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + +!5 = !{!6, !6, i64 0} +!6 = !{!"int", !7, i64 0} +!7 = !{!"omnipotent char", !8, i64 0} +!8 = !{!"Simple C/C++ TBAA"} +!9 = !{!10, !10, i64 0} +!10 = !{!"short", !7, i64 0} |
