[SCEV] Infer ranges for SCC consisting of cycled Phis

[mkazantsev]

Summary

Our current strategy of computing ranges of SCEVUnknown Phis was to simply
compute the union of ranges of all its inputs. In order to avoid infinite recursion,
we mark Phis as pending and conservatively return full set for them. As result,
even simplest patterns of cycled phis always have a range of full set.

This patch makes this logic a bit smarter. We basically do the same, but instead
of taking inputs of single Phi we find its strongly connected component (SCC)
and compute the union of all inputs that come into this SCC from outside.

Processing entire SCC together has one more advantage: we can set range for all
of them at once, because the only thing that happens to them is the same value is
being passed between those Phis. So, despite we spend more time analyzing a
single Phi, overall we may save time by not processing other SCC members, so
amortized compile time spent should be approximately the same.

[mkazantsev]

Theoretically it should not harm CT, but would be nice to ensure that. Nikita, could you please help me with that?

[nikic]

Compile-time impact looks okay: https://llvm-compile-time-tracker.com/compare.php?from=a7d084a18de736e0ed750c67c5851fa6b2a085f5&to=06e833e5593c85cc6aed401b1a186d9257c10484&stat=instructions

llvm/lib/Analysis/ScalarEvolution.cpp

6597

Why is it okay to ignore operands in PendingPhiRanges here?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6597

They are not ignored, they are some SS Phi's input so they will be in Roots. We will take the range from them for our union.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6597

SCC Phi*

[reames]

Seems overall reasonable, though, I'm curious, where do you see this trigger in practice? Given this formulation doesn't involve anything but phis, it disallows IVs. Given that, I'm curious what patterns create this.

llvm/lib/Analysis/ScalarEvolution.cpp

6576–6577

This block of code has gotten quite complicated, probably time for a helper function.

6597

I'm not sure about this statement. IF this is the *first* recursion (e.g. the top level value is a phi) in this SCC then sure, but we'd analyze something which happened to contain a non-SCC phi, then recursed into it's operands (which contained an SCC phi), I'm unsure. At a minimum, I think the code would be easier to follow if you seperated the SCC detection from the PendingPHIRange mechanism.

6626

Does this ever get hit? I'd expect this to be unreachable as we'd always traverse the same SCC by definition from any entry.

[mkazantsev]

In D110620#3030883, @reames wrote:

Seems overall reasonable, though, I'm curious, where do you see this trigger in practice? Given this formulation doesn't involve anything but phis, it disallows IVs. Given that, I'm curious what patterns create this.

It's the first step. I'm planning to generalize this to deal with chunked IV.

Imagine we had a single block loop which was incrementing. Everything was fine, and SCEV knew how to deal with its range.

Then we chunked the iteration space is split in chunks, and we have two loops, outer phi being start for inner phi, and taking it as backedge input.

SCEV in this case becomes just helpless to do anything. It cannot even prove they are non-negative if they start from 0 and only go up. The thing I am aiming is SCC's consisting of SCEVUnknowns and SCEVAddReds<nuw>/<nsw>. Idea is following: if a SCC only takes non-negative values from outside, and all its addrecs have nuw/nsw, then the entire thing is non-negative.

Examples of this I've merged as test/Transforms/IndVarSimplify/outer_phi.ll.

But this is a bit far-fetched. As a first step I wanted to fix case with cycled Phis, whether they are chunked IV or they are just siblings or whatever.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6597

Basically, the algorithm is correct even if we ignore random nodes. The phis that get into SCC all:

• Are reachable from first Phi;
• Use first Phi (directly or indirectly).

It means that in any case SCC is some strongly connected component, even if not maximal by inclusion. It's OK. Our statement that SCC Phis can only take values that come to them from outside is still true.

In practice, if we ever meet a pending input, it will have range of full set and entire thing will also be full set.

6626

I think you are right. Need to check.

[mkazantsev]

Planning rework.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6626

Actually no, this happens quite often. Here is what happens when I add assert:

Failed Tests (22):
  LLVM :: Analysis/CostModel/X86/interleaved-load-f64-stride-4.ll
  LLVM :: Analysis/CostModel/X86/interleaved-load-i16-stride-6.ll
  LLVM :: Analysis/CostModel/X86/interleaved-store-f32-stride-2.ll
  LLVM :: Analysis/CostModel/X86/interleaved-store-i32-stride-4.ll
  LLVM :: Analysis/CostModel/X86/interleaved-store-i32-stride-6.ll
  LLVM :: Analysis/CostModel/X86/interleaved-store-i64-stride-3.ll
  LLVM :: Analysis/CostModel/X86/interleaved-store-i8-stride-6.ll
  LLVM :: CodeGen/AMDGPU/amdpal-callable.ll
  LLVM :: CodeGen/AMDGPU/wave32.ll
  LLVM :: CodeGen/ARM/loop-indexing.ll
  LLVM :: CodeGen/Hexagon/swp-epilog-reuse4.ll
  LLVM :: CodeGen/X86/stack-protector.ll
  LLVM :: CodeGen/X86/vector-fshl-256.ll
  LLVM :: Transforms/Attributor/willreturn.ll
  LLVM :: Transforms/IndVarSimplify/no-iv-rewrite.ll
  LLVM :: Transforms/LoopStrengthReduce/lsr-comp-time.ll
  LLVM :: Transforms/LoopUnroll/runtime-loop-branchweight.ll
  LLVM :: Transforms/LoopUnroll/runtime-loop2.ll
  LLVM :: Transforms/LoopVectorize/ARM/tail-folding-counting-down.ll
  LLVM :: Transforms/LoopVectorize/PowerPC/reg-usage.ll
  LLVM :: Transforms/LoopVectorize/X86/gather_scatter.ll
  LLVM :: Transforms/LoopVectorize/tail-folding-counting-down.ll

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6576–6577

Factored out.

[mkazantsev]

Factored out SCC logic.

[mkazantsev]

Ping

[mkazantsev]

Here is some more motivation what it was for: D111878

[mkazantsev]

Ping

[mkazantsev]

Ping

[mkazantsev]

Ping

[reames]

Ok, sorry for taking so long to reply to this. Something had been bugging me, and I hadn't quite taken the time to figure out what. I finally did.

I think this solution is majorly overkill, and adds an amount of complexity which is not justified. Let me walk through an alternate approach; I'm curious what you think.

The basic problem we have is a loop nest where the inner loop has an unknown trip count, and an addrec IV. This inner loop is wrapped in an outer loop which uses the increment of the inner IV as the backedge value of the outer IV. It's worth highlighting that if the inner loop had a computable trip count, the outer loops IV would likely also become an addrec. We can totally form the expression for the step of the outer loop, but since it's not loop invariant in the outer loop, we don't have an addrec.

As a brief aside, I've long wondered whether we should allow addrec's with loop varying step. If we did, we'd have a clean model for the outer IV. I'm not proposing we do that now, just mentioning it.

However, I think we can and should pattern match this "almost an addrec" pattern in the range check logic. Looking at a SCEVUnknown phi, checking to see if it matches this pattern (loop header, backedge is addrec with start value function of self, check!) is pretty straight forward. Much much simpler than the SCC matching at least.

Unless you have a motivating case which is not a nested loop, I think we should do this approach instead.

[reames]

Inline comments on the SCC implementation. As stated in previous comment, I think we should take an alternate approach, but leaving the comments since I took the time to build the mental state on the code.

llvm/lib/Analysis/ScalarEvolution.cpp

6717

This case results in the new code being strictly inferior to the old code on large phi nodes.

6725

I'm not sure simply ignoring an input is correct here. We may have to abort instead.

Hm, I think you're intent is that these get treated like external roots to the SCC. This a) probably explains why you get inconsistent SCCs over time, and b) deserves a comment at minimum,

6735

Instead of reusing the worklist variable, please scope the code such that you can use two worklists. Makes tracking the flow much easier.

6793

This bothers me for two reasons: 1) It implies we sometimes don't recognize a phi node as being part of an SCC, and sometimes do, and 2) this is spooky action at a distance where later queries change cached results.

I strongly suspect this is masking a bug above.

[mkazantsev]

Thanks for the suggesting, I need to wright a prototype to see how it works and if it covers all I need.

[mkazantsev]

Actually the definition of "almost addrec" doesn't even cover the motivation for this patch, where we have 2 phis from same block that just swap values. I don't think we can have any good framing here.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6717

Two points here:

1. Old code, seeing cycled phis, will always return full set, which in union will also give fullset for all phis. So no, in this case it's not worse, because "worse" is impossible.

2. Old code, not seeing cycled phis, will do exactly same thing as this one (e.g. process phi itself as the sole root).

So no, if I'm reading this correctly, it is strictly not worse than the old one.

6725

Off course it is correct to cut in any arbitrary place. We can take any subset of Phis, even if it's not a SCC, collect all inputs from outside of this subset, and use their union as estimate of the range of all these Phis. But it's only profitable when this subset is a SCC.

[mkazantsev]

Because incomplete SCCs draw a lot of questions and suspicions, despite I think everything should still work correctly for them, these cases are unimportant for any practical purpose.

I've reworked it so that it will either find full SCC (and therefore do better than before), or conservatively bail to processing of a single Phi.

Reduction of SCC to "AddRec with variant step" is too weak and doesn't handle swap example, so I think think it's worthwhile.

[reames]

LGTM.

I'm still not entirely convinced this is the best approach, but the simplified approach appears correct, and this looks at least reasonable.

[aeubanks]

I'm seeing a miscompile caused by assuming the entire SCC has the same range. One phi in the SCC has a corresponding llvm.assume limiting its range, but that assume doesn't apply to another phi in the SCC.

I apologize for the fairly large repro (at least it's only one function!).
$ opt -passes=indvars test.ll -S
You'll see that the br condition right before the invoke i32 @wobble.7 becomes false. That's because %tmp951 has a corresponding assume that it's non-negative. However, %tmp298, which is in the same phi SCC, is not under that assumption, but this patch still updates its range to be non-negative.

test.ll152 KBDownload

llvm/lib/Analysis/ScalarEvolution.cpp

6693–6698

Here

[xbolva00]

llvm/test/Analysis/ScalarEvolution/cycled_phis.ll

33

Remove fixme

[mkazantsev]

In D110620#3361521, @aeubanks wrote:

I'm seeing a miscompile caused by assuming the entire SCC has the same range. One phi in the SCC has a corresponding llvm.assume limiting its range, but that assume doesn't apply to another phi in the SCC.

I apologize for the fairly large repro (at least it's only one function!).
$ opt -passes=indvars test.ll -S
You'll see that the br condition right before the invoke i32 @wobble.7 becomes false. That's because %tmp951 has a corresponding assume that it's non-negative. However, %tmp298, which is in the same phi SCC, is not under that assumption, but this patch still updates its range to be non-negative.

test.ll152 KBDownload

Taking a look...

[mkazantsev]

This comment was removed by mkazantsev.

[mkazantsev]

Oh I think I see what happens... We could side-exit before assume was executed for example. This is a fundamental bug then. Need to find another approach to this.

[mkazantsev]

I'll try a completely different solution then.

llvm/include/llvm/Analysis/ScalarEvolution.h

ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Step,
                                      const SCEV *MaxBECount, unsigned BitWidth);
 
   /// If the unknown expression U corresponds to a simple recurrence, return
   /// a constant range which represents the entire recurrence.  Note that
   /// *add* recurrences with loop invariant steps aren't represented by
   /// SCEVUnknowns and thus don't use this mechanism.
   ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U);
 
+  /// Return true and fill \p SCC with elements of PNINode-composed strongly
+  /// connected component that contains \p Phi. Here SCC is a maximum by
+  /// inclusion subgraph composed of Phis that transitively use one another as
+  /// inputs. Otherwise, return false and conservatively put \p Phi into \p SCC
+  /// as the only element of its strongly connected component.
+  bool collectSCC(const PHINode *Phi,
+                  SmallVectorImpl<const PHINode *> &SCC) const;
+
+  /// Sharpen range of entire SCEVUnknown Phi strongly connected component that
+  /// includes \p Phi. On output, \p ConservativeResult is the sharpened range.
+  void sharpenPhiSCCRange(const PHINode *Phi, ConstantRange &ConservativeResult,
+                          ScalarEvolution::RangeSignHint SignHint);
+
   /// We know that there is no SCEV for the specified value.  Analyze the
   /// expression.
   const SCEV *createSCEV(Value *V);
 
   /// Provide the special handling we need to analyze PHI SCEVs.
   const SCEV *createNodeForPHI(PHINode *PN);
 
   /// Helper function called from createNodeForPHI.

llvm/lib/Analysis/ScalarEvolution.cpp

 #define DEBUG_TYPE "scalar-evolution"
 
 STATISTIC(NumTripCountsComputed,
           "Number of loops with predictable loop counts");
 STATISTIC(NumTripCountsNotComputed,
           "Number of loops without predictable loop counts");
 STATISTIC(NumBruteForceTripCountsComputed,
           "Number of loops with trip counts computed by force");
+STATISTIC(NumFoundPhiSCCs,
+          "Number of found Phi-composed strongly connected components");
 
 static cl::opt<unsigned>
 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
                         cl::ZeroOrMore,
                         cl::desc("Maximum number of iterations SCEV will "
                                  "symbolically execute a constant "
                                  "derived loop"),
                         cl::init(100));
ClassifyExpressions("scalar-evolution-classify-expressions",
     cl::desc("When printing analysis, include information on every instruction"));
 
 static cl::opt<bool> UseExpensiveRangeSharpening(
     "scalar-evolution-use-expensive-range-sharpening", cl::Hidden,
     cl::init(false),
     cl::desc("Use more powerful methods of sharpening expression ranges. May "
              "be costly in terms of compile time"));
 
+static cl::opt<unsigned> MaxPhiSCCAnalysisSize(
+    "scalar-evolution-max-scc-analysis-depth", cl::Hidden,
+    cl::desc("Maximum amount of nodes to process while searching SCEVUnknown "
+             "Phi strongly connected components"),
+    cl::init(8));
+
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // Implementation of the SCEV class.
 //
 
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.
-    if (const PHINode *Phi = dyn_cast<PHINode>(U->getValue())) {
-      // Make sure that we do not run over cycled Phis.
-      if (PendingPhiRanges.insert(Phi).second) {
-        ConstantRange RangeFromOps(BitWidth, /*isFullSet=*/false);
-        for (auto &Op : Phi->operands()) {
-          auto OpRange = getRangeRef(getSCEV(Op), SignHint);
-          RangeFromOps = RangeFromOps.unionWith(OpRange);
-          // No point to continue if we already have a full set.
-          if (RangeFromOps.isFullSet())
-            break;
-        }
-        ConservativeResult =
-            ConservativeResult.intersectWith(RangeFromOps, RangeType);
-        bool Erased = PendingPhiRanges.erase(Phi);
-        assert(Erased && "Failed to erase Phi properly?");
-        (void) Erased;
-      }
-    }
-
-    return setRange(U, SignHint, std::move(ConservativeResult));
-  }
-
-  return setRange(S, SignHint, std::move(ConservativeResult));
+    if (const PHINode *Phi = dyn_cast<PHINode>(U->getValue()))
+      if (!PendingPhiRanges.count(Phi))
+        sharpenPhiSCCRange(Phi, ConservativeResult, SignHint);
+
+    return setRange(U, SignHint, std::move(ConservativeResult));
+  }
+
+  return setRange(S, SignHint, std::move(ConservativeResult));
+}
+
+bool ScalarEvolution::collectSCC(const PHINode *Phi,
+                                 SmallVectorImpl<const PHINode *> &SCC) const {
+  assert(SCC.empty() && "Precondition: SCC should be empty.");
+  auto Bail = [&]() {
+    SCC.clear();
+    SCC.push_back(Phi);
+    return false;
+  };
+  SmallPtrSet<const PHINode *, 4> Reachable;
+  {
+    // First, find all PHI nodes that are reachable from Phi.
+    SmallVector<const PHINode *, 4> Worklist;
+    Reachable.insert(Phi);
+    Worklist.push_back(Phi);
+    while (!Worklist.empty()) {
+      if (Reachable.size() > MaxPhiSCCAnalysisSize)
+        // Too many nodes to process. Assume that SCC is composed of Phi alone.
+        return Bail();
+      auto *Curr = Worklist.pop_back_val();
+      for (auto &Op : Curr->operands()) {
+        if (auto *PhiOp = dyn_cast<PHINode>(&*Op)) {
+          if (PendingPhiRanges.count(PhiOp))
+            // Do not want to deal with this situation, so conservatively bail.
+            return Bail();
+          if (Reachable.insert(PhiOp).second)
+            Worklist.push_back(PhiOp);
+        }
+      }
+    }
+  }
+  {
+    // Out of reachable nodes, find those from which Phi is also reachable. This
+    // defines a SCC.
+    SmallVector<const PHINode *, 4> Worklist;
+    SmallPtrSet<const PHINode *, 4> SCCSet;
+    SCCSet.insert(Phi);
+    SCC.push_back(Phi);
+    Worklist.push_back(Phi);
+    while (!Worklist.empty()) {
+      auto *Curr = Worklist.pop_back_val();
+      for (auto *User : Curr->users())
+        if (auto *PN = dyn_cast<PHINode>(User))
+          if (Reachable.count(PN) && SCCSet.insert(PN).second) {
+            Worklist.push_back(PN);
+            SCC.push_back(PN);
+          }
+    }
+  }
+  return true;
+}
+
+void
+ScalarEvolution::sharpenPhiSCCRange(const PHINode *Phi,
+                                    ConstantRange &ConservativeResult,
+                                    ScalarEvolution::RangeSignHint SignHint) {
+  // Collect strongly connected component (further on - SCC ) composed of Phis.
+  // Analyze all values that are incoming to this SCC (we call them roots).
+  // All SCC elements have range that is not wider than union of ranges of
+  // roots.
+  SmallVector<const PHINode *, 8> SCC;
+  if (collectSCC(Phi, SCC))
+    ++NumFoundPhiSCCs;
+
+  // Collect roots: inputs of SCC nodes that come from outside of SCC.
+  SmallPtrSet<Value *, 4> Roots;
+  const SmallPtrSet<const PHINode *, 8> SCCSet(SCC.begin(), SCC.end());
+  for (auto *PN : SCC)
+    for (auto &Op : PN->operands()) {
+      auto *PhiInput = dyn_cast<PHINode>(Op);
+      if (!PhiInput || !SCCSet.count(PhiInput))
+        Roots.insert(Op);
+    }
+
+  // Mark SCC elements as pending to avoid infinite recursion if there is a
+  // cyclic dependency through some instruction that is not a PHI.
+  for (auto *PN : SCC) {
+    bool Inserted = PendingPhiRanges.insert(PN).second;
+    assert(Inserted && "PHI is already pending?");
+    (void)Inserted;
+  }
+
+  auto BitWidth = ConservativeResult.getBitWidth();
+  ConstantRange RangeFromRoots(BitWidth, /*isFullSet=*/false);
+  for (auto *Root : Roots) {
+    auto OpRange = getRangeRef(getSCEV(Root), SignHint);
+    RangeFromRoots = RangeFromRoots.unionWith(OpRange);
+    if (RangeFromRoots.isFullSet())
+  ConstantRange::PreferredRangeType RangeType =
+      SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? ConstantRange::Unsigned
+                                                       : ConstantRange::Signed;
+      ConservativeResult.intersectWith(RangeFromRoots, RangeType);
+
+  DenseMap<const SCEV *, ConstantRange> &Cache =
+      SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
+                                                       : SignedRanges;
+  // Entire SCC has the same range.
+  for (auto *PN : SCC) {
+    bool Erased = PendingPhiRanges.erase(PN);
+    (void)Erased;
+    auto *PNSCEV = getSCEV(const_cast<PHINode *>(PN));
+    auto I = Cache.find(PNSCEV);
+    if (I == Cache.end())
+      setRange(PNSCEV, SignHint, ConservativeResult);
+    else {
+      auto SharpenedRange =
+          I->second.intersectWith(ConservativeResult, RangeType);
+      setRange(PNSCEV, SignHint, SharpenedRange);
 }
 
 // Given a StartRange, Step and MaxBECount for an expression compute a range of
 // values that the expression can take. Initially, the expression has a value
 // from StartRange and then is changed by Step up to MaxBECount times. Signed
 // argument defines if we treat Step as signed or unsigned.
 static ConstantRange getRangeForAffineARHelper(APInt Step,
                                                const ConstantRange &StartRange,
                                                const APInt &MaxBECount,
                                                unsigned BitWidth, bool Signed) {
   // If either Step or MaxBECount is 0, then the expression won't change, and we
   // just need to return the initial range.
   if (Step == 0 || MaxBECount == 0)
     return StartRange;
 
   // If we don't know anything about the initial value (i.e. StartRange is
   // FullRange), then we don't know anything about the final range either.
   // Return FullRange.
   if (StartRange.isFullSet())
     return ConstantRange::getFull(BitWidth);
 
   // If Step is signed and negative, then we use its absolute value, but we also
   // note that we're moving in the opposite direction.
   bool Descending = Signed && Step.isNegative();
 
   if (Signed)
     // This is correct even for INT_SMIN. Let's look at i8 to illustrate this:
     // abs(INT_SMIN) = abs(-128) = abs(0x80) = -0x80 = 0x80 = 128.
     // This equations hold true due to the well-defined wrap-around behavior of
     // APInt.
     Step = Step.abs();
 
   // Check if Offset is more than full span of BitWidth. If it is, the
   // expression is guaranteed to overflow.
   if (APInt::getMaxValue(StartRange.getBitWidth()).udiv(Step).ult(MaxBECount))
     return ConstantRange::getFull(BitWidth);
 
   // Offset is by how much the expression can change. Checks above guarantee no
   // overflow here.
   APInt Offset = Step * MaxBECount;
 
   // Minimum value of the final range will match the minimal value of StartRange
   // if the expression is increasing and will be decreased by Offset otherwise.
ConstantRange SR =
       getRangeForAffineARHelper(StepSRange.getSignedMin(), StartSRange,
                                 MaxBECountValue, BitWidth, /* Signed = */ true);
   SR = SR.unionWith(getRangeForAffineARHelper(StepSRange.getSignedMax(),
                                               StartSRange, MaxBECountValue,
                                               BitWidth, /* Signed = */ true));
 
   // Next, consider step unsigned.
   ConstantRange UR = getRangeForAffineARHelper(
       getUnsignedRangeMax(Step), getUnsignedRange(Start),
       MaxBECountValue, BitWidth, /* Signed = */ false);
 
   // Finally, intersect signed and unsigned ranges.
   return SR.intersectWith(UR, ConstantRange::Smallest);
 }
 
 ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
     const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth,

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:
   br label %loop
 
 loop:
   %phi_1 = phi i32 [ 10, %entry], [%phi_2, %loop]
   %phi_2 = phi i32 [ 20, %entry], [%phi_1, %loop]
   %cond = call i1 @cond()
   br i1 %cond, label %loop, label %exit
 
 exit:
   ret void
 }
 
 ; 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_lcssa U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant }
+; CHECK-NEXT:    --> %inner_lcssa U: [0,3000) S: [0,3000) Exits: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant }
 ; 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.
outer_backedge:
   %inner_lcssa = phi i32 [%inner_phi, %inner_loop]
   %outer_cond = call i1 @cond()
   br i1 %outer_cond, label %outer_loop, label %exit
 
 exit:
   ret void
 }
 
-; FIXME: All phis should have range [0, 3000)
 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_lcssa U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant }
+; CHECK-NEXT:    --> %inner_lcssa U: [0,3000) S: [0,3000) Exits: <<Unknown>> LoopDispositions: { %outer_loop: Variant, %inner_loop: Invariant }
 ; 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

if.false:
   br label %merge
 
 merge:
   %len = phi i32 [ %len_a, %if.true ], [ %len_b, %if.false ]
   ret void
 }
 
 define void @merge_values_with_ranges_looped(i32 *%a_len_ptr, i32 *%b_len_ptr) {
-; TODO: We could be much smarter here. So far we just make sure that we do not
-;       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