Index: include/llvm/Analysis/BasicAliasAnalysis.h =================================================================== --- include/llvm/Analysis/BasicAliasAnalysis.h +++ 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 @@ -59,19 +60,20 @@ AssumptionCache ∾ DominatorTree *DT; LoopInfo *LI; + PhiValues *PV; public: BasicAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree *DT = nullptr, - LoopInfo *LI = nullptr) - : AAResultBase(), DL(DL), TLI(TLI), AC(AC), DT(DT), LI(LI) {} + LoopInfo *LI = nullptr, PhiValues *PV = nullptr) + : AAResultBase(), DL(DL), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV) {} BasicAAResult(const BasicAAResult &Arg) : AAResultBase(Arg), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT), - LI(Arg.LI) {} + LI(Arg.LI), PV(Arg.PV) {} BasicAAResult(BasicAAResult &&Arg) : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC), - DT(Arg.DT), LI(Arg.LI) {} + DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {} /// Handle invalidation events in the new pass manager. bool invalidate(Function &F, const PreservedAnalyses &PA, Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ 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(F, PA) || (DT && Inv.invalidate(F, PA)) || - (LI && Inv.invalidate(F, PA))) + (LI && Inv.invalidate(F, PA)) || + (PV && Inv.invalidate(F, PA))) return true; // Otherwise this analysis result remains valid. @@ -1521,34 +1523,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 + PhiValues::ValueSet PhiValueSet = PV->getUnderlyingPhiValues(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. @@ -1871,7 +1909,8 @@ AM.getResult(F), AM.getResult(F), &AM.getResult(F), - AM.getCachedResult(F)); + AM.getCachedResult(F), + &AM.getResult(F)); } BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { @@ -1887,6 +1926,7 @@ INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(PhiValuesWrapperPass) INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa", "Basic Alias Analysis (stateless AA impl)", true, true) @@ -1898,11 +1938,13 @@ auto &ACT = getAnalysis(); auto &TLIWP = getAnalysis(); auto &DTWP = getAnalysis(); + auto &PAWP = getAnalysis(); auto *LIWP = getAnalysisIfAvailable(); Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(), ACT.getAssumptionCache(F), &DTWP.getDomTree(), - LIWP ? &LIWP->getLoopInfo() : nullptr)); + LIWP ? &LIWP->getLoopInfo() : nullptr, + &PAWP.getResult())); return false; } @@ -1912,6 +1954,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); + AU.addRequired(); } BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) { Index: test/Analysis/BasicAA/phi-aa.ll =================================================================== --- test/Analysis/BasicAA/phi-aa.ll +++ test/Analysis/BasicAA/phi-aa.ll @@ -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: test/Transforms/GVN/pre-after-rle.ll =================================================================== --- test/Transforms/GVN/pre-after-rle.ll +++ test/Transforms/GVN/pre-after-rle.ll @@ -63,10 +63,12 @@ %cmp = icmp slt i32 1, %h br i1 %cmp, label %body, label %exit -; Alias analysis currently can't figure out %width doesn't alias %s, so just -; check that the redundant load has been removed. +; CHECK-LABEL: preheader.body_crit_edge: +; CHECK: load i32, i32* %width, align 8 + ; CHECK-LABEL: body: ; CHECK-NOT: load i32*, i32** %start, align 8 +; CHECK-NOT: load i32, i32* %width, align 8 body: %j = phi i32 [ 0, %preheader ], [ %j.next, %body ] %s = load i32*, i32** %start, align 8