Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -57,6 +57,7 @@ class LLVMContext; class Loop; class LoopInfo; +class PhiValues; class raw_ostream; class ScalarEvolution; class SCEVAddRecExpr; @@ -484,7 +485,7 @@ }; ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, - DominatorTree &DT, LoopInfo &LI); + DominatorTree &DT, LoopInfo &LI, PhiValues &PV); ScalarEvolution(ScalarEvolution &&Arg); ~ScalarEvolution(); @@ -1246,6 +1247,9 @@ /// The loop information for the function we are currently analyzing. LoopInfo &LI; + /// The information about underlying values of phis. + PhiValues &PV; + /// This SCEV is used to represent unknown trip counts and things. std::unique_ptr CouldNotCompute; Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -79,6 +79,7 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/PhiValues.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" @@ -6671,20 +6672,22 @@ APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1), RangeType); - // A range of Phi is a subset of union of all ranges of its input. + // A range of Phi is a subset of union of all ranges of its underlying + // values. if (const PHINode *Phi = dyn_cast(U->getValue())) { + auto &PValues = PV.getValuesForPhi(Phi); // Make sure that we do not run over cycled Phis. if (PendingPhiRanges.insert(Phi).second) { - ConstantRange RangeFromOps(BitWidth, /*isFullSet=*/false); - for (const auto &Op : Phi->operands()) { - auto OpRange = getRangeRef(getSCEV(Op), SignHint); - RangeFromOps = RangeFromOps.unionWith(OpRange); + ConstantRange RangeFromPhiValues(BitWidth, /*isFullSet=*/false); + for (const auto &PhiValue : PValues) { + auto ValueRange = getRangeRef(getSCEV(PhiValue), SignHint); + RangeFromPhiValues = RangeFromPhiValues.unionWith(ValueRange); // No point to continue if we already have a full set. - if (RangeFromOps.isFullSet()) + if (RangeFromPhiValues.isFullSet()) break; } ConservativeResult = - ConservativeResult.intersectWith(RangeFromOps, RangeType); + ConservativeResult.intersectWith(RangeFromPhiValues, RangeType); bool Erased = PendingPhiRanges.erase(Phi); assert(Erased && "Failed to erase Phi properly?"); (void) Erased; @@ -13153,8 +13156,8 @@ ScalarEvolution::ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, - LoopInfo &LI) - : F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), + LoopInfo &LI, PhiValues &PV) + : F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV), CouldNotCompute(new SCEVCouldNotCompute()), ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64) { // To use guards for proving predicates, we need to scan every instruction in @@ -13174,7 +13177,7 @@ ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg) : F(Arg.F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT), - LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)), + LI(Arg.LI), PV(Arg.PV), CouldNotCompute(std::move(Arg.CouldNotCompute)), ValueExprMap(std::move(Arg.ValueExprMap)), PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)), PendingPhiRanges(std::move(Arg.PendingPhiRanges)), @@ -13754,7 +13757,7 @@ void ScalarEvolution::verify() const { ScalarEvolution &SE = *const_cast(this); - ScalarEvolution SE2(F, TLI, AC, DT, LI); + ScalarEvolution SE2(F, TLI, AC, DT, LI, PV); SmallVector LoopStack(LI.begin(), LI.end()); @@ -13982,7 +13985,8 @@ return !(PAC.preserved() || PAC.preservedSet>()) || Inv.invalidate(F, PA) || Inv.invalidate(F, PA) || - Inv.invalidate(F, PA); + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA); } AnalysisKey ScalarEvolutionAnalysis::Key; @@ -13992,7 +13996,8 @@ return ScalarEvolution(F, AM.getResult(F), AM.getResult(F), AM.getResult(F), - AM.getResult(F)); + AM.getResult(F), + AM.getResult(F)); } PreservedAnalyses @@ -14018,6 +14023,7 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(PhiValuesWrapperPass) INITIALIZE_PASS_END(ScalarEvolutionWrapperPass, "scalar-evolution", "Scalar Evolution Analysis", false, true) @@ -14032,7 +14038,8 @@ F, getAnalysis().getTLI(F), getAnalysis().getAssumptionCache(F), getAnalysis().getDomTree(), - getAnalysis().getLoopInfo())); + getAnalysis().getLoopInfo(), + getAnalysis().getResult())); return false; } Index: llvm/lib/CodeGen/SafeStack.cpp =================================================================== --- llvm/lib/CodeGen/SafeStack.cpp +++ llvm/lib/CodeGen/SafeStack.cpp @@ -25,6 +25,7 @@ #include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/InlineCost.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/PhiValues.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/StackLifetime.h" @@ -916,7 +917,9 @@ DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); - ScalarEvolution SE(F, TLI, ACT, *DT, LI); + PhiValues PV(F); + + ScalarEvolution SE(F, TLI, ACT, *DT, LI, PV); return SafeStack(F, *TL, *DL, ShouldPreserveDominatorTree ? &DTU : nullptr, SE) Index: llvm/test/Analysis/ScalarEvolution/cycled_phis.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/cycled_phis.ll +++ llvm/test/Analysis/ScalarEvolution/cycled_phis.ll @@ -8,9 +8,9 @@ ; CHECK-LABEL: 'test_01' ; CHECK-NEXT: Classifying expressions for: @test_01 ; CHECK-NEXT: %phi_1 = phi i32 [ 10, %entry ], [ %phi_2, %loop ] -; CHECK-NEXT: --> %phi_1 U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: --> %phi_1 U: [10,21) S: [10,21) Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: %phi_2 = phi i32 [ 20, %entry ], [ %phi_1, %loop ] -; CHECK-NEXT: --> %phi_2 U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: --> %phi_2 U: [10,21) S: [10,21) Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: %cond = call i1 @cond() ; CHECK-NEXT: --> %cond U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: Determining loop execution counts for: @test_01 @@ -38,15 +38,15 @@ ; CHECK-NEXT: %start = load i32, i32* %p, align 4, !range !0 ; CHECK-NEXT: --> %start U: [0,1000) S: [0,1000) ; CHECK-NEXT: %outer_phi = phi i32 [ %start, %entry ], [ %inner_lcssa, %outer_backedge ] -; CHECK-NEXT: --> %outer_phi U: full-set S: full-set Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant } +; CHECK-NEXT: --> %outer_phi U: [0,3000) S: [0,3000) Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant } ; CHECK-NEXT: %inner_phi = phi i32 [ %outer_phi, %outer_loop ], [ %inner_load, %inner_loop ] -; CHECK-NEXT: --> %inner_phi U: full-set S: full-set Exits: <> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant } +; CHECK-NEXT: --> %inner_phi U: [0,3000) S: [0,3000) Exits: <> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant } ; CHECK-NEXT: %inner_load = load i32, i32* %q, align 4, !range !1 ; CHECK-NEXT: --> %inner_load U: [2000,3000) S: [2000,3000) Exits: <> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant } ; CHECK-NEXT: %inner_cond = call i1 @cond() ; CHECK-NEXT: --> %inner_cond U: full-set S: full-set Exits: <> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant } ; CHECK-NEXT: %inner_lcssa = phi i32 [ %inner_phi, %inner_loop ] -; CHECK-NEXT: --> %inner_phi U: full-set S: full-set Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Variant } +; CHECK-NEXT: --> %inner_phi U: [0,3000) S: [0,3000) Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Variant } ; CHECK-NEXT: %outer_cond = call i1 @cond() ; CHECK-NEXT: --> %outer_cond U: full-set S: full-set Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant } ; CHECK-NEXT: Determining loop execution counts for: @test_02 @@ -89,15 +89,15 @@ ; CHECK-NEXT: %start_2 = load i32, i32* %q, align 4, !range !1 ; CHECK-NEXT: --> %start_2 U: [2000,3000) S: [2000,3000) ; CHECK-NEXT: %outer_phi = phi i32 [ %start_1, %entry ], [ %inner_lcssa, %outer_backedge ] -; CHECK-NEXT: --> %outer_phi U: full-set S: full-set Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant } +; CHECK-NEXT: --> %outer_phi U: [0,3000) S: [0,3000) Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant } ; CHECK-NEXT: %inner_phi_1 = phi i32 [ %outer_phi, %outer_loop ], [ %inner_phi_2, %inner_loop ] -; CHECK-NEXT: --> %inner_phi_1 U: full-set S: full-set Exits: <> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant } +; CHECK-NEXT: --> %inner_phi_1 U: [0,3000) S: [0,3000) Exits: <> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant } ; CHECK-NEXT: %inner_phi_2 = phi i32 [ %start_2, %outer_loop ], [ %inner_phi_1, %inner_loop ] -; CHECK-NEXT: --> %inner_phi_2 U: full-set S: full-set Exits: <> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant } +; CHECK-NEXT: --> %inner_phi_2 U: [0,3000) S: [0,3000) Exits: <> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant } ; CHECK-NEXT: %inner_cond = call i1 @cond() ; CHECK-NEXT: --> %inner_cond U: full-set S: full-set Exits: <> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant } ; CHECK-NEXT: %inner_lcssa = phi i32 [ %inner_phi_1, %inner_loop ] -; CHECK-NEXT: --> %inner_phi_1 U: full-set S: full-set Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Variant } +; CHECK-NEXT: --> %inner_phi_1 U: [0,3000) S: [0,3000) Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Variant } ; CHECK-NEXT: %outer_cond = call i1 @cond() ; CHECK-NEXT: --> %outer_cond U: full-set S: full-set Exits: <> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant } ; CHECK-NEXT: Determining loop execution counts for: @test_03 Index: llvm/test/Analysis/ScalarEvolution/unknown_phis.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/unknown_phis.ll +++ llvm/test/Analysis/ScalarEvolution/unknown_phis.ll @@ -39,9 +39,9 @@ ; CHECK-NEXT: %len_b = load i32, i32* %b_len_ptr, align 4, !range !0 ; CHECK-NEXT: --> %len_b U: [0,2147483647) S: [0,2147483647) ; CHECK-NEXT: %p1 = phi i32 [ %len_a, %entry ], [ %p2, %loop ] -; CHECK-NEXT: --> %p1 U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: --> %p1 U: [0,2147483647) S: [0,2147483647) Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: %p2 = phi i32 [ %len_b, %entry ], [ %p1, %loop ] -; CHECK-NEXT: --> %p2 U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: --> %p2 U: [0,2147483647) S: [0,2147483647) Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ] ; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,100) S: [0,100) Exits: 99 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add i32 %iv, 1