diff options
| -rw-r--r-- | lib/Analysis/BasicAliasAnalysis.cpp | 63 | ||||
| -rw-r--r-- | test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll | 2 | ||||
| -rw-r--r-- | test/Analysis/BasicAA/phi-aa.ll | 7 | ||||
| -rw-r--r-- | test/Analysis/BasicAA/phi-spec-order.ll | 2 | ||||
| -rw-r--r-- | test/Analysis/GlobalsModRef/aliastest.ll | 2 | ||||
| -rw-r--r-- | test/Transforms/ObjCARC/weak-copies.ll | 2 | ||||
| -rw-r--r-- | test/Transforms/ObjCARC/weak-dce.ll | 2 |
7 files changed, 40 insertions, 40 deletions
diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index 14268ec391..f1a9dd991c 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -18,8 +18,10 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Constants.h" @@ -41,9 +43,9 @@ using namespace llvm; /// Cutoff after which to stop analysing a set of phi nodes potentially involved /// in a cycle. Because we are analysing 'through' phi nodes we need to be -/// careful with value equivalence. We use dominance to make sure a value cannot -/// be involved in a cycle. -const unsigned MaxNumPhiBBsValueDominanceCheck = 20; +/// careful with value equivalence. We use reachability to make sure a value +/// cannot be involved in a cycle. +const unsigned MaxNumPhiBBsValueReachabilityCheck = 20; //===----------------------------------------------------------------------===// // Useful predicates @@ -453,7 +455,6 @@ namespace { virtual AliasResult alias(const Location &LocA, const Location &LocB) { - DT = 0; assert(AliasCache.empty() && "AliasCache must be cleared after use!"); assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && "BasicAliasAnalysis doesn't support interprocedural queries."); @@ -522,16 +523,14 @@ namespace { // Visited - Track instructions visited by pointsToConstantMemory. SmallPtrSet<const Value*, 16> Visited; - // We use the dominator tree to check values can't be part of a cycle. - DominatorTree *DT; - /// \brief Check whether two Values can be considered equivalent. /// /// In addition to pointer equivalence of \p V1 and \p V2 this checks /// whether they can not be part of a cycle in the value graph by looking at - /// all visited phi nodes an making sure that the value dominates all of - /// them. - bool isValueEqual(const Value *V1, const Value *V2); + /// all visited phi nodes an making sure that the phis cannot reach the + /// value. We have to do this because we are looking through phi nodes (That + /// is we say noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB). + bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2); /// \brief Dest and Src are the variable indices from two decomposed /// GetElementPtr instructions GEP1 and GEP2 which have common base @@ -1196,7 +1195,13 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, V2 = V2->stripPointerCasts(); // Are we checking for alias of the same value? - if (isValueEqual(V1, V2)) return MustAlias; + // Because we look 'through' phi nodes we could look at "Value" pointers from + // different iterations. We must therefore make sure that this is not the + // case. The function isValueEqualInPotentialCycles ensures that this cannot + // happen by looking at the visited phi nodes and making sure they cannot + // reach the value. + if (isValueEqualInPotentialCycles(V1, V2)) + return MustAlias; if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) return NoAlias; // Scalars cannot alias each other @@ -1317,7 +1322,8 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, return AliasCache[Locs] = Result; } -bool BasicAliasAnalysis::isValueEqual(const Value *V, const Value *V2) { +bool BasicAliasAnalysis::isValueEqualInPotentialCycles(const Value *V, + const Value *V2) { if (V != V2) return false; @@ -1325,23 +1331,23 @@ bool BasicAliasAnalysis::isValueEqual(const Value *V, const Value *V2) { if (!Inst) return true; - // Use the dominance if available. - DT = getAnalysisIfAvailable<DominatorTree>(); - if (DT) { - if (VisitedPhiBBs.size() > MaxNumPhiBBsValueDominanceCheck) - return false; + if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck) + return false; - // Make sure that the visited phis are dominated by the Value. - for (SmallPtrSet<const BasicBlock *, 8>::iterator - PI = VisitedPhiBBs.begin(), - PE = VisitedPhiBBs.end(); - PI != PE; ++PI) - if (!DT->dominates(Inst, *PI)) - return false; - return true; - } + // Use dominance or loop info if available. + DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>(); + LoopInfo *LI = getAnalysisIfAvailable<LoopInfo>(); + + // Make sure that the visited phis cannot reach the Value. This ensures that + // the Values cannot come from different iterations of a potential cycle the + // phi nodes could be involved in. + for (SmallPtrSet<const BasicBlock *, 8>::iterator PI = VisitedPhiBBs.begin(), + PE = VisitedPhiBBs.end(); + PI != PE; ++PI) + if (isPotentiallyReachable((*PI)->begin(), Inst, DT, LI)) + return false; - return false; + return true; } /// GetIndexDifference - Dest and Src are the variable indices from two @@ -1362,7 +1368,8 @@ void BasicAliasAnalysis::GetIndexDifference( // Find V in Dest. This is N^2, but pointer indices almost never have more // than a few variable indexes. for (unsigned j = 0, e = Dest.size(); j != e; ++j) { - if (!isValueEqual(Dest[j].V, V) || Dest[j].Extension != Extension) + if (!isValueEqualInPotentialCycles(Dest[j].V, V) || + Dest[j].Extension != Extension) continue; // If we found it, subtract off Scale V's from the entry in Dest. If it diff --git a/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll b/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll index c6a9cd9a10..06a804c392 100644 --- a/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll +++ b/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -domtree -basicaa -aa-eval -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -basicaa -aa-eval -disable-output 2>&1 | FileCheck %s ; TEST that A[1][0] may alias A[0][i]. target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128" diff --git a/test/Analysis/BasicAA/phi-aa.ll b/test/Analysis/BasicAA/phi-aa.ll index ed2d23e3ad..74279e1c4c 100644 --- a/test/Analysis/BasicAA/phi-aa.ll +++ b/test/Analysis/BasicAA/phi-aa.ll @@ -1,5 +1,4 @@ ; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -domtree -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s --check-prefix=DOM target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @@ -12,9 +11,6 @@ target triple = "x86_64-unknown-linux-gnu" ; CHECK-LABEL: foo ; CHECK: NoAlias: i32* %P, i32* @Z -; DOM-LABEL: foo -; DOM: NoAlias: i32* %P, i32* @Z - define void @foo(i32 %cond) nounwind { entry: %"alloca point" = bitcast i32 0 to i32 @@ -44,9 +40,6 @@ return: ; CHECK-LABEL: pr18068 ; CHECK: MayAlias: i32* %0, i32* %arrayidx5 -; DOM-LABEL: pr18068 -; DOM: MayAlias: i32* %0, i32* %arrayidx5 - define i32 @pr18068(i32* %jj7, i32* %j) { entry: %oa5 = alloca [100 x i32], align 16 diff --git a/test/Analysis/BasicAA/phi-spec-order.ll b/test/Analysis/BasicAA/phi-spec-order.ll index 3c9fa92363..4172d0963f 100644 --- a/test/Analysis/BasicAA/phi-spec-order.ll +++ b/test/Analysis/BasicAA/phi-spec-order.ll @@ -1,6 +1,6 @@ target datalayout = "E-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-f128:128:128-v128:128:128-n32:64" target triple = "powerpc64-bgq-linux" -; RUN: opt < %s -domtree -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s @X = external global [16000 x double], align 32 @Y = external global [16000 x double], align 32 diff --git a/test/Analysis/GlobalsModRef/aliastest.ll b/test/Analysis/GlobalsModRef/aliastest.ll index 864c516ec9..4cfed71bfb 100644 --- a/test/Analysis/GlobalsModRef/aliastest.ll +++ b/test/Analysis/GlobalsModRef/aliastest.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -domtree -basicaa -globalsmodref-aa -gvn -S | FileCheck %s +; RUN: opt < %s -basicaa -globalsmodref-aa -gvn -S | FileCheck %s @X = internal global i32 4 ; <i32*> [#uses=1] diff --git a/test/Transforms/ObjCARC/weak-copies.ll b/test/Transforms/ObjCARC/weak-copies.ll index 599689bc36..5dab4e049e 100644 --- a/test/Transforms/ObjCARC/weak-copies.ll +++ b/test/Transforms/ObjCARC/weak-copies.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -domtree -basicaa -objc-arc < %s | FileCheck %s +; RUN: opt -S -basicaa -objc-arc < %s | FileCheck %s target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" target triple = "x86_64-apple-darwin11.0.0" diff --git a/test/Transforms/ObjCARC/weak-dce.ll b/test/Transforms/ObjCARC/weak-dce.ll index 787fb905fd..f09467182b 100644 --- a/test/Transforms/ObjCARC/weak-dce.ll +++ b/test/Transforms/ObjCARC/weak-dce.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -domtree -basicaa -objc-arc < %s | FileCheck %s +; RUN: opt -S -basicaa -objc-arc < %s | FileCheck %s ; rdar://11434915 ; Delete the weak calls and replace them with just the net retain. |