[SCEV] Calculate PHI range based on its underlying values instead of just its inputs

[dmakogon]

Summary

This teaches SCEV to calculate range of a PHI as a union of its underlying values ranges.
Currently we do it by uniting ranges of its inputs, but there are cases where two or more PHIs
are cycled so such approach would give the full range.
This uses PhiValues analysis to get underlying values for PHIs and then unite their ranges.

[mkazantsev]

Need to carefully think how to invalidate it correctly. I guess you need updates in forgetValue and maybe somewhere else.

[mkazantsev]

llvm/lib/CodeGen/SafeStack.cpp

920

Can we reuse cached result from analysis?

[mkazantsev]

@nikic this is not a final solution, but could you please evaluate CT impact of this one? Just for reference.

[nikic]

In D134178#3799419, @mkazantsev wrote:

@nikic this is not a final solution, but could you please evaluate CT impact of this one? Just for reference.

Unfortunately there is a crash when building test-suite: http://llvm-compile-time-tracker.com/show_error.php?commit=d1ebd749bf430527616aab33a7340f9fd2736228

Note that to make this change viable, every pass that preserves SCEV must also preserve PhiValues -- I doubt this is worth the effort or complexity.

[mkazantsev]

Likely this is due to missing invalidation. @dmakogon pls fix the known issue and run more extensive fuzz testing to find what else is missing.

@nikic it shouldn't be a problem. If I'm reading this correctly, PhiValues makes computation lazily by request and supports by-value invalidation. If we have preserved SCEV => we have forgotten all values in SCEV that need to be forgotten => we have also invalidated them in PhiValues. This automatically gives what we want, no?

[nikic]

Marking as changes requested for now due to known issues.

In D134178#3801903, @mkazantsev wrote:

@nikic it shouldn't be a problem. If I'm reading this correctly, PhiValues makes computation lazily by request and supports by-value invalidation. If we have preserved SCEV => we have forgotten all values in SCEV that need to be forgotten => we have also invalidated them in PhiValues. This automatically gives what we want, no?

I'm not sure this is true, because PhiValues will also contain phis that are outside loops, and those may not get invalidated by SCEVs invalidation mechanisms, right?

llvm/include/llvm/Analysis/ScalarEvolution.h

 class DataLayout;
 class DominatorTree;
 class Function;
 class GEPOperator;
 class Instruction;
 class LLVMContext;
 class Loop;
 class LoopInfo;
+class PhiValues;
 class raw_ostream;
 class ScalarEvolution;
 class SCEVAddRecExpr;
 class SCEVUnknown;
 class StructType;
 class TargetLibraryInfo;
 class Type;
 class Value;
clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) {
     return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
   }
   [[nodiscard]] static bool hasFlags(SCEV::NoWrapFlags Flags,
                                      SCEV::NoWrapFlags TestFlags) {
     return TestFlags == maskFlags(Flags, TestFlags);
   };
 
   ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC,
-                  DominatorTree &DT, LoopInfo &LI);
+                  DominatorTree &DT, LoopInfo &LI, PhiValues &PV);
   ScalarEvolution(ScalarEvolution &&Arg);
   ~ScalarEvolution();
 
   LLVMContext &getContext() const { return F.getContext(); }
 
   /// Test if values of the given type are analyzable within the SCEV
   /// framework. This primarily includes integer types, and it can optionally
   /// include pointer types if the ScalarEvolution class has access to
private:
   AssumptionCache ∾
 
   /// The dominator tree.
   DominatorTree &DT;
 
   /// 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<SCEVCouldNotCompute> CouldNotCompute;
 
   /// The type for HasRecMap.
   using HasRecMapType = DenseMap<const SCEV *, bool>;
 
   /// This is a cache to record whether a SCEV contains any scAddRecExpr.
   HasRecMapType HasRecMap;

llvm/lib/Analysis/ScalarEvolution.cpp

 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #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"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
if (Known.getMinValue() != Known.getMaxValue() + 1)
           ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1),
           RangeType);
     if (NS > 1)
       ConservativeResult = ConservativeResult.intersectWith(
           ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
                         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<PHINode>(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;
       }
     }
 
     // vscale can't be equal to zero
     if (const auto *II = dyn_cast<IntrinsicInst>(U->getValue()))
ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
   : CallbackVH(V), SE(se) {}
 
 //===----------------------------------------------------------------------===//
 //                   ScalarEvolution Class Implementation
 //===----------------------------------------------------------------------===//
 
 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
   // relevant basic blocks, and not just terminators.  Doing this is a waste of
   // time if the IR does not actually contain any calls to
   // @llvm.experimental.guard, so do a quick check and remember this beforehand.
   //
   // This pessimizes the case where a pass that preserves ScalarEvolution wants
   // to _add_ guards to the module when there weren't any before, and wants
   // ScalarEvolution to optimize based on those guards.  For now we prefer to be
   // efficient in lieu of being smart in that rather obscure case.
 
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   HasGuards = GuardDecl && !GuardDecl->use_empty();
 }
 
 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)),
       PendingMerges(std::move(Arg.PendingMerges)),
       MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       PredicatedBackedgeTakenCounts(
           std::move(Arg.PredicatedBackedgeTakenCounts)),
while (!Worklist.empty()) {
     }
 
     append_range(Worklist, successors(BB));
   }
 }
 
 void ScalarEvolution::verify() const {
   ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
-  ScalarEvolution SE2(F, TLI, AC, DT, LI);
+  ScalarEvolution SE2(F, TLI, AC, DT, LI, PV);
 
   SmallVector<Loop *, 8> LoopStack(LI.begin(), LI.end());
 
   // Map's SCEV expressions from one ScalarEvolution "universe" to another.
   struct SCEVMapper : public SCEVRewriteVisitor<SCEVMapper> {
     SCEVMapper(ScalarEvolution &SE) : SCEVRewriteVisitor<SCEVMapper>(SE) {}
 
     const SCEV *visitConstant(const SCEVConstant *Constant) {
bool ScalarEvolution::invalidate(
     Function &F, const PreservedAnalyses &PA,
     FunctionAnalysisManager::Invalidator &Inv) {
   // Invalidate the ScalarEvolution object whenever it isn't preserved or one
   // of its dependencies is invalidated.
   auto PAC = PA.getChecker<ScalarEvolutionAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
          Inv.invalidate<AssumptionAnalysis>(F, PA) ||
          Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
-         Inv.invalidate<LoopAnalysis>(F, PA);
+         Inv.invalidate<LoopAnalysis>(F, PA) ||
+         Inv.invalidate<PhiValuesAnalysis>(F, PA);
 }
 
 AnalysisKey ScalarEvolutionAnalysis::Key;
 
 ScalarEvolution ScalarEvolutionAnalysis::run(Function &F,
                                              FunctionAnalysisManager &AM) {
   return ScalarEvolution(F, AM.getResult<TargetLibraryAnalysis>(F),
                          AM.getResult<AssumptionAnalysis>(F),
                          AM.getResult<DominatorTreeAnalysis>(F),
-                         AM.getResult<LoopAnalysis>(F));
+                         AM.getResult<LoopAnalysis>(F),
+                         AM.getResult<PhiValuesAnalysis>(F));
 }
 
 PreservedAnalyses
 ScalarEvolutionVerifierPass::run(Function &F, FunctionAnalysisManager &AM) {
   AM.getResult<ScalarEvolutionAnalysis>(F).verify();
   return PreservedAnalyses::all();
 }
 

 }
 
 INITIALIZE_PASS_BEGIN(ScalarEvolutionWrapperPass, "scalar-evolution",
                       "Scalar Evolution Analysis", false, true)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 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)
 
 char ScalarEvolutionWrapperPass::ID = 0;
 
 ScalarEvolutionWrapperPass::ScalarEvolutionWrapperPass() : FunctionPass(ID) {
   initializeScalarEvolutionWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 bool ScalarEvolutionWrapperPass::runOnFunction(Function &F) {
   SE.reset(new ScalarEvolution(
       F, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
       getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
       getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
-      getAnalysis<LoopInfoWrapperPass>().getLoopInfo()));
+      getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
+      getAnalysis<PhiValuesWrapperPass>().getResult()));
   return false;
 }
 
 void ScalarEvolutionWrapperPass::releaseMemory() { SE.reset(); }
 
 void ScalarEvolutionWrapperPass::print(raw_ostream &OS, const Module *) const {
   SE->print(OS);
 }

llvm/lib/CodeGen/SafeStack.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #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"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/Argument.h"
if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {
       ShouldPreserveDominatorTree = false;
     }
 
     // Likewise, lazily compute loop info.
     LoopInfo LI(*DT);
 
     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)
         .run();
   }
 };
 
 } // end anonymous namespace

llvm/test/Analysis/ScalarEvolution/cycled_phis.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 declare i1 @cond()
 
 ; FIXME: Range of phi_1 and phi_2 here can be sharpened to [10, 21).
 define void @test_01() {
 ; 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: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %phi_1 U: [10,21) S: [10,21) Exits: <<Unknown>> 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: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %phi_2 U: [10,21) S: [10,21) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %cond = call i1 @cond()
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_01
 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 ;
 entry:

 
 ; FIXME: Both inner and outer loop Phis should have the same range [0, 3000).
 define void @test_02(i32* %p, i32* %q) {
 ; CHECK-LABEL: 'test_02'
 ; CHECK-NEXT:  Classifying expressions for: @test_02
 ; 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: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant }
+; CHECK-NEXT:    --> %outer_phi U: [0,3000) S: [0,3000) Exits: <<Unknown>> 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: <<Unknown>> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant }
+; CHECK-NEXT:    --> %inner_phi U: [0,3000) S: [0,3000) Exits: <<Unknown>> 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: <<Unknown>> 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: <<Unknown>> 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: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Variant }
+; CHECK-NEXT:    --> %inner_phi U: [0,3000) S: [0,3000) Exits: <<Unknown>> 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: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_02
 ; CHECK-NEXT:  Loop %inner_loop: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %inner_loop: Unpredictable max backedge-taken count.
 ; CHECK-NEXT:  Loop %inner_loop: Unpredictable predicated backedge-taken count.
 ; CHECK-NEXT:  Loop %outer_loop: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %outer_loop: Unpredictable max backedge-taken count.

 define void @test_03(i32* %p, i32* %q) {
 ; CHECK-LABEL: 'test_03'
 ; CHECK-NEXT:  Classifying expressions for: @test_03
 ; CHECK-NEXT:    %start_1 = load i32, i32* %p, align 4, !range !0
 ; CHECK-NEXT:    --> %start_1 U: [0,1000) S: [0,1000)
 ; 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: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant }
+; CHECK-NEXT:    --> %outer_phi U: [0,3000) S: [0,3000) Exits: <<Unknown>> 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: <<Unknown>> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant }
+; CHECK-NEXT:    --> %inner_phi_1 U: [0,3000) S: [0,3000) Exits: <<Unknown>> 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: <<Unknown>> LoopDispositions: { %inner_loop: Variant, %outer_loop: Variant }
+; CHECK-NEXT:    --> %inner_phi_2 U: [0,3000) S: [0,3000) Exits: <<Unknown>> 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: <<Unknown>> 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: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Variant }
+; CHECK-NEXT:    --> %inner_phi_1 U: [0,3000) S: [0,3000) Exits: <<Unknown>> 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: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_03
 ; CHECK-NEXT:  Loop %inner_loop: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %inner_loop: Unpredictable max backedge-taken count.
 ; CHECK-NEXT:  Loop %inner_loop: Unpredictable predicated backedge-taken count.
 ; CHECK-NEXT:  Loop %outer_loop: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %outer_loop: Unpredictable max backedge-taken count.

llvm/test/Analysis/ScalarEvolution/unknown_phis.ll

 ;       go into infinite loop analyzing these Phis.
 ; CHECK-LABEL: 'merge_values_with_ranges_looped'
 ; CHECK-NEXT:  Classifying expressions for: @merge_values_with_ranges_looped
 ; CHECK-NEXT:    %len_a = load i32, i32* %a_len_ptr, align 4, !range !0
 ; CHECK-NEXT:    --> %len_a U: [0,2147483647) S: [0,2147483647)
 ; 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: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %p1 U: [0,2147483647) S: [0,2147483647) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %p2 = phi i32 [ %len_b, %entry ], [ %p1, %loop ]
-; CHECK-NEXT:    --> %p2 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %p2 U: [0,2147483647) S: [0,2147483647) Exits: <<Unknown>> 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
 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,101) S: [1,101) Exits: 100 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @merge_values_with_ranges_looped
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 99
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 99
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 99