Index: llvm/trunk/include/llvm/Analysis/BasicAliasAnalysis.h =================================================================== --- llvm/trunk/include/llvm/Analysis/BasicAliasAnalysis.h +++ llvm/trunk/include/llvm/Analysis/BasicAliasAnalysis.h @@ -43,6 +43,7 @@ class PHINode; class SelectInst; class TargetLibraryInfo; +class PhiValues; class Value; /// This is the AA result object for the basic, local, and stateless alias @@ -60,19 +61,22 @@ AssumptionCache &AC; DominatorTree *DT; LoopInfo *LI; + PhiValues *PV; public: BasicAAResult(const DataLayout &DL, const Function &F, const TargetLibraryInfo &TLI, AssumptionCache &AC, - DominatorTree *DT = nullptr, LoopInfo *LI = nullptr) - : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI) {} + DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + PhiValues *PV = nullptr) + : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV) + {} BasicAAResult(const BasicAAResult &Arg) : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC), - DT(Arg.DT), LI(Arg.LI) {} + DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {} BasicAAResult(BasicAAResult &&Arg) : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), - AC(Arg.AC), DT(Arg.DT), LI(Arg.LI) {} + AC(Arg.AC), DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {} /// Handle invalidation events in the new pass manager. bool invalidate(Function &Fn, const PreservedAnalyses &PA, Index: llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp @@ -28,6 +28,7 @@ #include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Analysis/PhiValues.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/CallSite.h" @@ -93,7 +94,8 @@ // depend on them. if (Inv.invalidate(Fn, PA) || (DT && Inv.invalidate(Fn, PA)) || - (LI && Inv.invalidate(Fn, PA))) + (LI && Inv.invalidate(Fn, PA)) || + (PV && Inv.invalidate(Fn, PA))) return true; // Otherwise this analysis result remains valid. @@ -1527,34 +1529,70 @@ return Alias; } - SmallPtrSet UniqueSrc; SmallVector V1Srcs; bool isRecursive = false; - for (Value *PV1 : PN->incoming_values()) { - if (isa(PV1)) - // If any of the source itself is a PHI, return MayAlias conservatively - // to avoid compile time explosion. The worst possible case is if both - // sides are PHI nodes. In which case, this is O(m x n) time where 'm' - // and 'n' are the number of PHI sources. + if (PV) { + // If we have PhiValues then use it to get the underlying phi values. + const PhiValues::ValueSet &PhiValueSet = PV->getValuesForPhi(PN); + // If we have more phi values than the search depth then return MayAlias + // conservatively to avoid compile time explosion. The worst possible case + // is if both sides are PHI nodes. In which case, this is O(m x n) time + // where 'm' and 'n' are the number of PHI sources. + if (PhiValueSet.size() > MaxLookupSearchDepth) return MayAlias; - - if (EnableRecPhiAnalysis) - if (GEPOperator *PV1GEP = dyn_cast(PV1)) { - // Check whether the incoming value is a GEP that advances the pointer - // result of this PHI node (e.g. in a loop). If this is the case, we - // would recurse and always get a MayAlias. Handle this case specially - // below. - if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 && - isa(PV1GEP->idx_begin())) { - isRecursive = true; - continue; + // Add the values to V1Srcs + for (Value *PV1 : PhiValueSet) { + if (EnableRecPhiAnalysis) { + if (GEPOperator *PV1GEP = dyn_cast(PV1)) { + // Check whether the incoming value is a GEP that advances the pointer + // result of this PHI node (e.g. in a loop). If this is the case, we + // would recurse and always get a MayAlias. Handle this case specially + // below. + if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 && + isa(PV1GEP->idx_begin())) { + isRecursive = true; + continue; + } } } - - if (UniqueSrc.insert(PV1).second) V1Srcs.push_back(PV1); + } + } else { + // If we don't have PhiInfo then just look at the operands of the phi itself + // FIXME: Remove this once we can guarantee that we have PhiInfo always + SmallPtrSet UniqueSrc; + for (Value *PV1 : PN->incoming_values()) { + if (isa(PV1)) + // If any of the source itself is a PHI, return MayAlias conservatively + // to avoid compile time explosion. The worst possible case is if both + // sides are PHI nodes. In which case, this is O(m x n) time where 'm' + // and 'n' are the number of PHI sources. + return MayAlias; + + if (EnableRecPhiAnalysis) + if (GEPOperator *PV1GEP = dyn_cast(PV1)) { + // Check whether the incoming value is a GEP that advances the pointer + // result of this PHI node (e.g. in a loop). If this is the case, we + // would recurse and always get a MayAlias. Handle this case specially + // below. + if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 && + isa(PV1GEP->idx_begin())) { + isRecursive = true; + continue; + } + } + + if (UniqueSrc.insert(PV1).second) + V1Srcs.push_back(PV1); + } } + // If V1Srcs is empty then that means that the phi has no underlying non-phi + // value. This should only be possible in blocks unreachable from the entry + // block, but return MayAlias just in case. + if (V1Srcs.empty()) + return MayAlias; + // If this PHI node is recursive, set the size of the accessed memory to // unknown to represent all the possible values the GEP could advance the // pointer to. @@ -1879,7 +1917,8 @@ AM.getResult(F), AM.getResult(F), &AM.getResult(F), - AM.getCachedResult(F)); + AM.getCachedResult(F), + AM.getCachedResult(F)); } BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { @@ -1891,12 +1930,12 @@ void BasicAAWrapperPass::anchor() {} INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa", - "Basic Alias Analysis (stateless AA impl)", true, true) + "Basic Alias Analysis (stateless AA impl)", false, true) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa", - "Basic Alias Analysis (stateless AA impl)", true, true) + "Basic Alias Analysis (stateless AA impl)", false, true) FunctionPass *llvm::createBasicAAWrapperPass() { return new BasicAAWrapperPass(); @@ -1907,10 +1946,12 @@ auto &TLIWP = getAnalysis(); auto &DTWP = getAnalysis(); auto *LIWP = getAnalysisIfAvailable(); + auto *PVWP = getAnalysisIfAvailable(); Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F, TLIWP.getTLI(), ACT.getAssumptionCache(F), &DTWP.getDomTree(), - LIWP ? &LIWP->getLoopInfo() : nullptr)); + LIWP ? &LIWP->getLoopInfo() : nullptr, + PVWP ? &PVWP->getResult() : nullptr)); return false; } @@ -1920,6 +1961,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); + AU.addUsedIfAvailable(); } BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) { Index: llvm/trunk/test/Analysis/BasicAA/invalidation.ll =================================================================== --- llvm/trunk/test/Analysis/BasicAA/invalidation.ll +++ llvm/trunk/test/Analysis/BasicAA/invalidation.ll @@ -24,6 +24,18 @@ ; CHECK-LI-INVALIDATE: Invalidating analysis: BasicAA ; CHECK-LI-INVALIDATE: Running pass: AAEvaluator ; CHECK-LI-INVALIDATE: Running analysis: BasicAA +; +; Check PhiValues specifically. +; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \ +; RUN: -passes='require,require,invalidate,aa-eval' -aa-pipeline='basic-aa' \ +; RUN: | FileCheck %s --check-prefix=CHECK-PV-INVALIDATE +; CHECK-PV-INVALIDATE: Running pass: RequireAnalysisPass +; CHECK-PV-INVALIDATE: Running analysis: BasicAA +; CHECK-PV-INVALIDATE: Running pass: InvalidateAnalysisPass +; CHECK-PV-INVALIDATE: Invalidating analysis: PhiValuesAnalysis +; CHECK-PV-INVALIDATE: Invalidating analysis: BasicAA +; CHECK-PV-INVALIDATE: Running pass: AAEvaluator +; CHECK-PV-INVALIDATE: Running analysis: BasicAA ; Some code that will result in actual AA queries, including inside of a loop. ; FIXME: Sadly, none of these queries managed to use either the domtree or Index: llvm/trunk/test/Analysis/BasicAA/phi-aa.ll =================================================================== --- llvm/trunk/test/Analysis/BasicAA/phi-aa.ll +++ llvm/trunk/test/Analysis/BasicAA/phi-aa.ll @@ -1,5 +1,5 @@ -; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -phi-values -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=basic-aa -passes='require,aa-eval' -print-all-alias-modref-info -disable-output 2>&1 | 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-S128" target triple = "x86_64-unknown-linux-gnu" @@ -78,3 +78,39 @@ declare void @inc(i32*) +; When we have a chain of phis in nested loops we should recognise if there's +; actually only one underlying value. +; CHECK-LABEL: loop_phi_chain +; CHECK: NoAlias: i32* %val1, i32* @Y +; CHECK: NoAlias: i32* %val2, i32* @Y +; CHECK: NoAlias: i32* %val3, i32* @Y +define void @loop_phi_chain(i32 %a, i32 %b, i32 %c) { +entry: + br label %loop1 + +loop1: + %n1 = phi i32 [ 0, %entry ], [ %add1, %loop2 ] + %val1 = phi i32* [ @X, %entry ], [ %val2, %loop2 ] + %add1 = add i32 %n1, 1 + %cmp1 = icmp ne i32 %n1, 32 + br i1 %cmp1, label %loop2, label %end + +loop2: + %n2 = phi i32 [ 0, %loop1 ], [ %add2, %loop3 ] + %val2 = phi i32* [ %val1, %loop1 ], [ %val3, %loop3 ] + %add2 = add i32 %n2, 1 + %cmp2 = icmp ne i32 %n2, 32 + br i1 %cmp2, label %loop3, label %loop1 + +loop3: + %n3 = phi i32 [ 0, %loop2 ], [ %add3, %loop3 ] + %val3 = phi i32* [ %val2, %loop2 ], [ %val3, %loop3 ] + store i32 0, i32* %val3, align 4 + store i32 0, i32* @Y, align 4 + %add3 = add i32 %n3, 1 + %cmp3 = icmp ne i32 %n3, 32 + br i1 %cmp3, label %loop3, label %loop2 + +end: + ret void +} Index: llvm/trunk/test/Analysis/BasicAA/phi-values-usage.ll =================================================================== --- llvm/trunk/test/Analysis/BasicAA/phi-values-usage.ll +++ llvm/trunk/test/Analysis/BasicAA/phi-values-usage.ll @@ -0,0 +1,50 @@ +; RUN: opt -debug-pass=Executions -phi-values -memcpyopt -instcombine -disable-output < %s 2>&1 | FileCheck %s + +; Check that phi values is not run when it's not already available, and that +; basicaa is freed after a pass that preserves CFG. + +; CHECK: Executing Pass 'Phi Values Analysis' +; CHECK: Executing Pass 'Basic Alias Analysis (stateless AA impl)' +; CHECK: Executing Pass 'Memory Dependence Analysis' +; CHECK: Executing Pass 'MemCpy Optimization' +; CHECK-DAG: Freeing Pass 'MemCpy Optimization' +; CHECK-DAG: Freeing Pass 'Phi Values Analysis' +; CHECK-DAG: Freeing Pass 'Memory Dependence Analysis' +; CHECK-DAG: Freeing Pass 'Basic Alias Analysis (stateless AA impl)' +; CHECK-NOT: Executing Pass 'Phi Values Analysis' +; CHECK: Executing Pass 'Basic Alias Analysis (stateless AA impl)' +; CHECK: Executing Pass 'Combine redundant instructions' + +declare void @otherfn([4 x i8]*) +declare i32 @__gxx_personality_v0(...) + +; This function is one where if we didn't free basicaa after memcpyopt then the +; usage of basicaa in instcombine would cause a segfault due to stale phi-values +; results being used. +define void @fn(i8* %this, i64* %ptr) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) { +entry: + %arr = alloca [4 x i8], align 8 + %gep1 = getelementptr inbounds [4 x i8], [4 x i8]* %arr, i64 0, i32 0 + br i1 undef, label %then, label %if + +if: + br label %then + +then: + %phi = phi i64* [ %ptr, %if ], [ null, %entry ] + store i8 1, i8* %gep1, align 8 + %load = load i64, i64* %phi, align 8 + %gep2 = getelementptr inbounds i8, i8* undef, i64 %load + %gep3 = getelementptr inbounds i8, i8* %gep2, i64 40 + invoke i32 undef(i8* undef) + to label %invoke unwind label %lpad + +invoke: + unreachable + +lpad: + landingpad { i8*, i32 } + catch i8* null + call void @otherfn([4 x i8]* nonnull %arr) + unreachable +} Index: llvm/trunk/test/Other/opt-O2-pipeline.ll =================================================================== --- llvm/trunk/test/Other/opt-O2-pipeline.ll +++ llvm/trunk/test/Other/opt-O2-pipeline.ll @@ -125,6 +125,7 @@ ; CHECK-NEXT: Delete dead loops ; CHECK-NEXT: Unroll loops ; CHECK-NEXT: MergedLoadStoreMotion +; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results ; CHECK-NEXT: Memory Dependence Analysis ; CHECK-NEXT: Lazy Branch Probability Analysis @@ -138,6 +139,7 @@ ; CHECK-NEXT: Sparse Conditional Constant Propagation ; CHECK-NEXT: Demanded bits analysis ; CHECK-NEXT: Bit-Tracking Dead Code Elimination +; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results ; CHECK-NEXT: Natural Loop Information ; CHECK-NEXT: Lazy Branch Probability Analysis @@ -155,6 +157,7 @@ ; CHECK-NEXT: Canonicalize natural loops ; CHECK-NEXT: LCSSA Verifier ; CHECK-NEXT: Loop-Closed SSA Form Pass +; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results ; CHECK-NEXT: Scalar Evolution Analysis ; CHECK-NEXT: Loop Pass Manager Index: llvm/trunk/test/Other/opt-O3-pipeline.ll =================================================================== --- llvm/trunk/test/Other/opt-O3-pipeline.ll +++ llvm/trunk/test/Other/opt-O3-pipeline.ll @@ -129,6 +129,7 @@ ; CHECK-NEXT: Delete dead loops ; CHECK-NEXT: Unroll loops ; CHECK-NEXT: MergedLoadStoreMotion +; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results ; CHECK-NEXT: Memory Dependence Analysis ; CHECK-NEXT: Lazy Branch Probability Analysis @@ -142,6 +143,7 @@ ; CHECK-NEXT: Sparse Conditional Constant Propagation ; CHECK-NEXT: Demanded bits analysis ; CHECK-NEXT: Bit-Tracking Dead Code Elimination +; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results ; CHECK-NEXT: Natural Loop Information ; CHECK-NEXT: Lazy Branch Probability Analysis @@ -159,6 +161,7 @@ ; CHECK-NEXT: Canonicalize natural loops ; CHECK-NEXT: LCSSA Verifier ; CHECK-NEXT: Loop-Closed SSA Form Pass +; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results ; CHECK-NEXT: Scalar Evolution Analysis ; CHECK-NEXT: Loop Pass Manager Index: llvm/trunk/test/Other/opt-Os-pipeline.ll =================================================================== --- llvm/trunk/test/Other/opt-Os-pipeline.ll +++ llvm/trunk/test/Other/opt-Os-pipeline.ll @@ -112,6 +112,7 @@ ; CHECK-NEXT: Delete dead loops ; CHECK-NEXT: Unroll loops ; CHECK-NEXT: MergedLoadStoreMotion +; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results ; CHECK-NEXT: Memory Dependence Analysis ; CHECK-NEXT: Lazy Branch Probability Analysis @@ -125,6 +126,7 @@ ; CHECK-NEXT: Sparse Conditional Constant Propagation ; CHECK-NEXT: Demanded bits analysis ; CHECK-NEXT: Bit-Tracking Dead Code Elimination +; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results ; CHECK-NEXT: Natural Loop Information ; CHECK-NEXT: Lazy Branch Probability Analysis @@ -142,6 +144,7 @@ ; CHECK-NEXT: Canonicalize natural loops ; CHECK-NEXT: LCSSA Verifier ; CHECK-NEXT: Loop-Closed SSA Form Pass +; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results ; CHECK-NEXT: Scalar Evolution Analysis ; CHECK-NEXT: Loop Pass Manager Index: llvm/trunk/test/Transforms/SCCP/preserve-analysis.ll =================================================================== --- llvm/trunk/test/Transforms/SCCP/preserve-analysis.ll +++ llvm/trunk/test/Transforms/SCCP/preserve-analysis.ll @@ -7,11 +7,9 @@ ; CHECK: Globals Alias Analysis ; CHECK: Dominator Tree Construction ; CHECK: Natural Loop Information -; CHECK: Basic Alias Analysis (stateless AA impl) ; CHECK: Sparse Conditional Constant Propagation ; CHECK-NOT: Dominator Tree Construction ; CHECK-NOT: Natural Loop Information -; CHECK-NOT: Basic Alias Analysis (stateless AA impl) ; CHECK-NOT: Globals Alias Analysis ; CHECK: Loop Vectorization