[SCEV] Allow non-overflowing binops when analyzing SCC

[mkazantsev]

Summary

First step of Phi SCC processing was proving that the range of phi-translated
set of external inputs is the union of these inputs.

As the 2nd step, we also allow nuw+nsw binary operations to be included into
the SCC. For such SCCs, not only Phi translation, but also arithmetics is possible,
so we cannot just say its range is union of inputs. However, both Phi translation
and nuw+nsw arithmetic operation preserve the following invariant:
"If all external inputs into this SCC were non-negative, the SCC itself is also non-negative".

In practice, it is very useful to prove range of chunked Phis, what is shown in tests.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

449

This is some weird caching effect; I need to see if we can tackle this. Doesn't look too bad though.

[mkazantsev]

Needs rebase.

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);
 
-  /// Sharpen range of entire SCEVUnknown Phi strongly connected component that
-  /// includes \p Phi. On output, \p ConservativeResult is the sharpened range.
+  /// Sharpen range of a strongly connected component that includes \p Phi and
+  /// is composed of Phis and nuw+nsw binops. 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.

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getRangeRef(const SCEV *S,
 
   return setRange(S, SignHint, std::move(ConservativeResult));
 }
 
 void
 ScalarEvolution::sharpenPhiSCCRange(const PHINode *Phi,
                                     ConstantRange &ConservativeResult,
                                     ScalarEvolution::RangeSignHint SignHint) {
-  // Collect strongly connected component (further on - SCC ) composed of Phis.
+  // Collect strongly connected component (further on - SCC ) composed of Phis
+  // and nuw+nsw binary operators.
   // 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 *, 4> Worklist;
-  SmallPtrSet<const PHINode *, 4> Reachable;
+  // There are two possible cases:
+  // 1. SCC fully consists of Phis. Then all SCC elements have range that is
+  //    not wider than union of ranges of roots.
+  // 2. SCC contains at least one nuw+nsw BinOp. In this case, we are dealing
+  //    with loop that gets incremented on each iteration. The best we can do
+  //    is to prove that all incoming values of this SCC are non-negative.
+  //    In this case, the entire SCC is also non-negative, because neither a
+  //    Phi translation nor nuw+nsw BinOp can break this invariant.
+  SmallVector<const Instruction *, 4> Worklist;
+  SmallPtrSet<const Instruction *, 4> Reachable;
   Reachable.insert(Phi);
   Worklist.push_back(Phi);
-  // First, find all PHI nodes that are reachable from Phi.
+  // First, find all PHI nodes and nuw+nsw binops that are reachable from Phi.
   while (!Worklist.empty()) {
     if (Reachable.size() > MaxPhiSCCAnalysisSize) {
       // Too many nodes to process. Assume that SCC is composed of Phi alone.
       Reachable.clear();
       break;
     }
     auto *Curr = Worklist.pop_back_val();
     for (auto &Op : Curr->operands()) {
-      if (auto *PhiOp = dyn_cast<PHINode>(&*Op)) {
+      auto *I = dyn_cast<Instruction>(&*Op);
+      if (!I)
+        continue;
+      if (auto *PhiOp = dyn_cast<PHINode>(I)) {
         if (PendingPhiRanges.count(PhiOp))
           continue;
         if (Reachable.insert(PhiOp).second)
           Worklist.push_back(PhiOp);
-      }
+      } else if (auto *BO = dyn_cast<OverflowingBinaryOperator>(I))
+        // TODO: Handle nuw and nsw separately?
+        if (BO->hasNoSignedWrap() && BO->hasNoUnsignedWrap())
+          if (Reachable.insert(I).second)
+            Worklist.push_back(I);
     }
   }
 
-  SmallPtrSet<const PHINode *, 4> SCC;
+  SmallPtrSet<const Instruction *, 4> SCC;
   SCC.insert(Phi);
   Worklist.push_back(Phi);
+  bool SCCContainsOnlyPhis = true;
   // Out of reachable nodes, find those from which Phi is also reachable.
   // This defines a SCC.
   while (!Worklist.empty()) {
     auto *Curr = Worklist.pop_back_val();
     for (auto *User : Curr->users()) {
-      auto *PN = dyn_cast<PHINode>(User);
-      if (PN && Reachable.count(PN) && SCC.insert(PN).second)
-        Worklist.push_back(PN);
+      auto *I = cast<Instruction>(User);
+      if (Reachable.count(I)) {
+        if (!isa<PHINode>(I)) {
+          auto *BO = dyn_cast<OverflowingBinaryOperator>(I);
+          (void)BO;
+          assert(BO && "Only phis and binary operators are allowed!");
+          assert(BO->hasNoSignedWrap() && BO->hasNoUnsignedWrap() &&
+                 "Only non-wrapping BOs are allowed!");
+          SCCContainsOnlyPhis = false;
+        }
+        if (SCC.insert(I).second)
+          Worklist.push_back(I);
+      }
     }
   }
   Reachable.clear();
 
   // Collect roots: inputs of SCC nodes that come from outside of SCC.
   SmallPtrSet<Value *, 4> Roots;
   for (auto *PN : SCC)
     for (auto &Op : PN->operands()) {
-      auto *PhiInput = dyn_cast<PHINode>(Op);
-      if (!PhiInput || !SCC.count(PhiInput))
+      auto *InsnInput = dyn_cast<Instruction>(Op);
+      if (!InsnInput || !SCC.count(InsnInput))
         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) {
+  for (auto *I : SCC)
+    if (auto *PN = dyn_cast<PHINode>(I)) {
       bool Inserted = PendingPhiRanges.insert(PN).second;
       assert(Inserted && "PHI is already pending?");
       (void)Inserted;
     }
 
+  ConstantRange::PreferredRangeType RangeType =
+      SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED
+          ? ConstantRange::Unsigned : ConstantRange::Signed;
   auto BitWidth = ConservativeResult.getBitWidth();
+  if (SCCContainsOnlyPhis) {
+    // If SCC consists only of Phis, then its range is union of all incoming
+    // roots.
     ConstantRange RangeFromRoots(BitWidth, /*isFullSet=*/false);
     for (auto *Root : Roots) {
       auto OpRange = getRangeRef(getSCEV(Root), SignHint);
       RangeFromRoots = RangeFromRoots.unionWith(OpRange);
       // No point to continue if we already have a full set.
       if (RangeFromRoots.isFullSet())
         break;
     }
-  ConstantRange::PreferredRangeType RangeType =
-      SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED
-          ? ConstantRange::Unsigned : ConstantRange::Signed;
     ConservativeResult =
         ConservativeResult.intersectWith(RangeFromRoots, RangeType);
+  } else {
+    // If SCC includes binary operators, the best we can do is to prove that all
+    // roots are non-negative. In this case, Phi-translations and nuw+nsw
+    // operations will not violate this invariant.
+    bool ProvedNonNegative = all_of(Roots, [&](Value *Root) {
+      auto OpRange = getRangeRef(getSCEV(Root), SignHint);
+      return OpRange.isAllNonNegative();
+    });
+    if (ProvedNonNegative) {
+      auto SignedMaxPlus1 = APInt::getSignedMinValue(BitWidth);
+      auto RangeFromRoots =
+          ConstantRange::getNonEmpty(APInt::getZero(BitWidth), SignedMaxPlus1);
+      ConservativeResult =
+          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) {
+  for (auto *I : SCC)
+    if (auto *PN = dyn_cast<PHINode>(I)) {
       bool Erased = PendingPhiRanges.erase(PN);
       assert(Erased && "Failed to erase Phi properly?");
       (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,

llvm/test/Analysis/ScalarEvolution/outer_phi.ll

exit:
   ret i32 1
 }
 
 ; FIXME: both outer.iv and iv here can be proved non-negative.
 define i32 @test_02(i32 %a, i32 %b) {
 ; CHECK-LABEL: 'test_02'
 ; CHECK-NEXT:  Classifying expressions for: @test_02
 ; CHECK-NEXT:    %outer.iv = phi i32 [ 0, %entry ], [ %iv.next, %outer.backedge ]
-; CHECK-NEXT:    --> %outer.iv U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
+; CHECK-NEXT:    --> %outer.iv U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
 ; CHECK-NEXT:    %iv = phi i32 [ %outer.iv, %outer ], [ %iv.next, %inner.backedge ]
-; CHECK-NEXT:    --> {%outer.iv,+,1}<nuw><nsw><%inner> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
+; CHECK-NEXT:    --> {%outer.iv,+,1}<nuw><nsw><%inner> U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i32 %iv, 1
-; CHECK-NEXT:    --> {(1 + %outer.iv),+,1}<nw><%inner> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
+; CHECK-NEXT:    --> {(1 + %outer.iv)<nuw>,+,1}<nuw><%inner> U: [1,0) S: [1,0) Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
 ; CHECK-NEXT:    %inner.loop.cond = call i1 @cond()
 ; CHECK-NEXT:    --> %inner.loop.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner: Variant, %outer: Variant }
 ; CHECK-NEXT:    %outer.loop.cond = call i1 @cond()
 ; CHECK-NEXT:    --> %outer.loop.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_02
 ; CHECK-NEXT:  Loop %inner: <multiple exits> Unpredictable backedge-taken count.
-; CHECK-NEXT:    exit count for inner: ((-1 * %outer.iv) + (%b smax %outer.iv))
+; CHECK-NEXT:    exit count for inner: ((-1 * %outer.iv)<nsw> + (%b smax %outer.iv))
 ; CHECK-NEXT:    exit count for inner.backedge: ***COULDNOTCOMPUTE***
-; CHECK-NEXT:  Loop %inner: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %inner: max backedge-taken count is 2147483647
 ; CHECK-NEXT:  Loop %inner: Unpredictable predicated backedge-taken count.
 ; CHECK-NEXT:  Loop %outer: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT:    exit count for inner: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:    exit count for outer.backedge: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:  Loop %outer: Unpredictable max backedge-taken count.
 ; CHECK-NEXT:  Loop %outer: Unpredictable predicated backedge-taken count.
 ;
 entry:

llvm/test/Analysis/ScalarEvolution/pr49856.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
 
 define void @test() {
 ; CHECK-LABEL: 'test'
 ; CHECK-NEXT:  Classifying expressions for: @test
 ; CHECK-NEXT:    %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
-; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648)
+; CHECK-NEXT:    --> %tmp U: [0,-2147483648) S: [0,-2147483648)
 ; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
 ; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647)
 ; CHECK-NEXT:  Determining loop execution counts for: @test
 ;
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb3, %bb
   %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
   %tmp2 = add nuw nsw i32 %tmp, 1
   ret void
 
 bb3:                                              ; No predecessors!
   br label %bb1
 }

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

 
 ; Was pr49856.  We can match the recurrence without a loop
 ; since dominance collapses in unreachable code.  Conceptually,
 ; this is a recurrence which only executes one iteration.
 define void @nonloop_recurrence() {
 ; CHECK-LABEL: 'nonloop_recurrence'
 ; CHECK-NEXT:  Classifying expressions for: @nonloop_recurrence
 ; CHECK-NEXT:    %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
-; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648)
+; CHECK-NEXT:    --> %tmp U: [0,-2147483648) S: [0,-2147483648)
 ; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
 ; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647)
 ; CHECK-NEXT:  Determining loop execution counts for: @nonloop_recurrence
 ;
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb3, %bb
   %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
   %tmp2 = add nuw nsw i32 %tmp, 1
   ret void
 
 bb3:                                              ; No predecessors!
   br label %bb1
 }
 
 ; Tweak of pr49856 test case - analogous, but there is a loop
 ; it's trip count simply doesn't relate to the single iteration
 ; "recurrence" we found.
 define void @nonloop_recurrence_2() {
 ; CHECK-LABEL: 'nonloop_recurrence_2'
 ; CHECK-NEXT:  Classifying expressions for: @nonloop_recurrence_2
 ; CHECK-NEXT:    %tmp = phi i32 [ 2, %loop ], [ %tmp2, %bb3 ]
-; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %tmp U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
 ; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @nonloop_recurrence_2
 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 ;
 bb:

llvm/test/Analysis/ScalarEvolution/trivial-phis.ll

 
 do.end:                                           ; preds = %do.body
   %add.lcssa.wide = phi i64 [ %indvars.iv.next, %do.body ]
   ret i64 %add.lcssa.wide
 }
 
 ; CHECK-LABEL @test2
 ; CHECK:      %tmp24 = phi i64 [ %tmp14, %bb22 ], [ %tmp14, %bb13 ]
-; CHECK-NEXT: -->  %tmp24 U: full-set S: full-set       Exits: <<Unknown>>      LoopDispositions: { %bb13: Variant, %bb8: Variant, %bb17: Invariant, %bb27: Invariant }
+; CHECK-NEXT: -->  %tmp24 U: [0,-9223372036854775808) S: [0,-9223372036854775808)    Exits: <<Unknown>>    LoopDispositions: { %bb13: Variant, %bb8: Variant, %bb17: Invariant, %bb27: Invariant }
 
 define void @test2(i64 %arg, i32* noalias %arg1) {
 bb:
   %tmp = icmp slt i64 0, %arg
   br i1 %tmp, label %bb7, label %bb48
 
 bb7:                                              ; preds = %bb
   br label %bb8

llvm/test/Transforms/IndVarSimplify/outer_phi.ll

 side.exit:
   ret i32 0
 
 exit:
   ret i32 1
 }
 
 ; Same as test_01, but non-negativity of %b is known without context.
-; FIXME: We can remove 2nd check in loop.
 define i32 @test_05(i32 %a, i32* %bp) {
 ; CHECK-LABEL: @test_05(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 ; CHECK:       outer:
 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
+; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
 ; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       inner.1:
-; CHECK-NEXT:    [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
-; CHECK-NEXT:    br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
+; CHECK-NEXT:    br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
 ; CHECK:       inner.backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
 ; CHECK:       outer.backedge:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
 ; CHECK-NEXT:    [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]

 exit:
   ret i32 1
 }
 
 ; We should prove implication: iv <s b, b <s 0 => iv <u b.
 define i32 @test_05c(i32 %a, i32* %bp) {
 ; CHECK-LABEL: @test_05c(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1:![0-9]+]]
 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 ; CHECK:       outer:
 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
-; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
+; CHECK-NEXT:    br i1 false, label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       inner.1:
 ; CHECK-NEXT:    br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
 ; CHECK:       inner.backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
 ; CHECK:       outer.backedge:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]

 exit:
   ret i32 1
 }
 
 ; Same as test_05c, but 2nd condition reversed.
 define i32 @test_05d(i32 %a, i32* %bp) {
 ; CHECK-LABEL: @test_05d(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]]
 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 ; CHECK:       outer:
 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
-; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
+; CHECK-NEXT:    br i1 false, label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       inner.1:
 ; CHECK-NEXT:    br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
 ; CHECK:       inner.backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
 ; CHECK:       outer.backedge:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]

 exit:
   ret i32 1
 }
 
 ; Same as test_05c, but 1st condition inverted.
 define i32 @test_05g(i32 %a, i32* %bp) {
 ; CHECK-LABEL: @test_05g(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]]
 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 ; CHECK:       outer:
 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]]
-; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
+; CHECK-NEXT:    br i1 false, label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       inner.1:
 ; CHECK-NEXT:    br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
 ; CHECK:       inner.backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
 ; CHECK:       outer.backedge:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]

 exit:
   ret i32 1
 }
 
 ; Same as test_05d, but 1st condition inverted.
 define i32 @test_05h(i32 %a, i32* %bp) {
 ; CHECK-LABEL: @test_05h(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]]
 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 ; CHECK:       outer:
 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]]
-; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
+; CHECK-NEXT:    br i1 false, label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       inner.1:
 ; CHECK-NEXT:    br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
 ; CHECK:       inner.backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
 ; CHECK:       outer.backedge:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]

 side.exit:
   ret i32 0
 
 exit:
   ret i32 1
 }
 
 ; Same as test_02, but non-negativity of %b is known without context.
-; FIXME: We can remove 2nd check in loop.
 define i32 @test_06(i32 %a, i32* %bp) {
 ; CHECK-LABEL: @test_06(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 ; CHECK:       outer:
 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
+; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
 ; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       inner.1:
-; CHECK-NEXT:    [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
-; CHECK-NEXT:    br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
+; CHECK-NEXT:    br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
 ; CHECK:       inner.backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
 ; CHECK:       outer.backedge:
 ; CHECK-NEXT:    [[OUTER_MERGE]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
 ; CHECK-NEXT:    [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]

 side.exit:
   ret i32 0
 
 exit:
   ret i32 1
 }
 
 ; Same as test_03, but non-negativity of %b is known without context.
-; FIXME: We can remove 2nd check in loop.
 define i32 @test_07(i32 %a, i32* %bp) {
 ; CHECK-LABEL: @test_07(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 ; CHECK:       outer:
 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[OUTER_COND_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[OUTER_COND_1]], label [[INNER_PREHEADER:%.*]], label [[NO_INNER:%.*]]
 ; CHECK:       inner.preheader:
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       no_inner:
 ; CHECK-NEXT:    [[OUTER_COND_2:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br label [[OUTER_BACKEDGE]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ], [ [[OUTER_IV]], [[INNER_PREHEADER]] ]
-; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
+; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
 ; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       inner.1:
-; CHECK-NEXT:    [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
-; CHECK-NEXT:    br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
+; CHECK-NEXT:    br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
 ; CHECK:       inner.backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]]
 ; CHECK:       outer.backedge.loopexit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
 ; CHECK-NEXT:    br label [[OUTER_BACKEDGE]]
 ; CHECK:       outer.backedge: