[IndVars] Support AND/OR in optimizeLoopExitWithUnknownExitCount

[mkazantsev]

Summary

This patch allows optimizeLoopExitWithUnknownExitCount to deal with
branches by conditions that are not immediately ICmp's, but aggregates
of ICmp's joined by arithmetic or logical AND/OR. Each ICmp is optimized
independently.

[mkazantsev]

I'm planning to land some more tests where branch exits loop by TRUE condition to make sure this works fine with it, but it's ready for review as is.

[mkazantsev]

Rebased on top of swapped tests; for some reason we don't optimize them. At least not miscompile (but need to analyze why).

[nikic]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1434

Why do we have to reconstruct the whole and chain? Can't we replace a single condition only? This looks quite fragile, especially as we probably want to generalize this to logical and as well, and at that point we'd have to replicate different types of ands in the correct position.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1434

It's only possible if no one else outside our cluster is using it. If they are, we can't simply replace operands of AND's.

One more (indirect, but still useful) effect of this algorithm is that it'll also eliminate duplicates, should they be in the AND tree.

As for logical AND -- what's the complexity? We keep conditions in the original order in Conditions, and replace them in the very same places. All it takes to support logical AND -- is to call another Builder function (multi-operand logical AND). If it doesn't exist, it's only a reason to write it.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1434

"using them" I mean "using ANDs"

[mkazantsev]

Disabled for loop-exiting true branch, just in case...

[nikic]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1434

It's only possible if no one else outside our cluster is using it. If they are, we can't simply replace operands of AND's.

That probably means that we need some one-use checks, otherwise we might unprofitable replicate a large condition tree.

One more (indirect, but still useful) effect of this algorithm is that it'll also eliminate duplicates, should they be in the AND tree.

I don't think it's the job of this transform to optimize ands with redundant operands...

As for logical AND -- what's the complexity? We keep conditions in the original order in Conditions, and replace them in the very same places. All it takes to support logical AND -- is to call another Builder function (multi-operand logical AND). If it doesn't exist, it's only a reason to write it.

There could be a mix of bitwise and logical and. Of course, it is safe to replace everything with logical and, it's just non-optimal.

In any case, I believe logical and handling should be part of the initial patch (or at least part of the patch stack). We should avoid differences in support, they will come back to bite us at some point :)

1451

I think the structure here isn't quite right. The L->contains(FalseSucc) check from createReplacement() should be in this function and just pass in an inversion flag. Then here, if we invert, we need to handle ORs, otherwise we need to handle ANDs.

Again, I think parity between and/or needs to be either in the initial patch, or in the patch stack.

[mkazantsev]

I agree that OR should be supported on the same grounds as AND. Need to check in more tests for it, and maybe this will be in this patch.

[mkazantsev]

As for logical OR/AND, they can go as follow-up.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1434

That probably means that we need some one-use checks, otherwise we might unprofitable replicate a large condition tree.

Yes, this is also a legit option.

I don't think it's the job of this transform to optimize ands with redundant operands...

But it just happens if we track duplicates, with no specific purpose... I mean, in ( (A & B)& (B & A) we will only consider A and B once and therefore remove duplicates. Though, if we check one-use, this effect also disappers.

There could be a mix of bitwise and logical and.

Let's leave logical operations for follow-up. I agree we should support them at some point, but they seem rare.

[mkazantsev]

Addressed Nikita's comments:

• OR is supported same as AND
• Logical AND and OR are also supported
• Got rid of code duplication, now the conditions are overwritten in existing instructions

[mkazantsev]

Solved trouble with IV widening.

[nikic]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1373–1374

nit: Missing static.

1451

LogicalOr also matches Or, no need to check both (same for LogicalAnd).

1466

To check that I understand the purpose of the MayNeedUpdate set: We can't simply RAUW because we only check one-use on the and/or ops, but not on the icmps, so the icmp may still have other users that shouldn't be replaced?

If so, would it be possible to add the one-use check on the icmp as well, which would allow us to use simple RAUW, and also avoid duplicating the icmp?

1479

nit: I would prefer passing in Inverted as a flag here rather than re-computing it in createReplacement. it took me a moment to understand that this code is not missing the inner condition inversion.

llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll

299

nit: Drop TODO

[mkazantsev]

Looks like I've uploaded wrong last diff here (pre-last looks OK), need to fix that and also address the comments.

[mkazantsev]

Addressed comments:

• Removed duplicating AND/logical AND matchers
• Simplified replacement logic, shrinking it down to one-use + RAUW mechanism
• Removed Fixed TODO

No-recompute of condition inversion is planned for follow-up.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1373–1374

https://github.com/llvm/llvm-project/commit/ba7af0bf693205fb82ff17d909c58e9402983fde

1451

Didn't know that, done.

1466

Yes, you are right about the intention here. We can do it I guess, I don't really have a motivating counter-example where it would really matter.

1479

Do you mind if it goes as a follow-up? It will require some non-trivial restructuring there.

[mkazantsev]

I realized that passing inverted doesn't requrie changing logic of SCEV queries, so not a big deal. Done in frames of this one.

[nikic]

This looks basically good to me, only concern is about the instruction move.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1446

This comment is out of place now (I think it can just be omitted, you have another below).

1464

I don't think we need to check isa<Instruction>(Curr) && here (I guess you could have a constant expression icmp or something, but the whole transform doesn't make sense for that case).

1480

Should we be setting the insert point on Rewriter instead? Mainly wondering if we might generate multiple insts and this then only moves one of them.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1464

Method parameter with one use?

1464

i.e. with more than one use.

1480

Interesting point, will check.

[nikic]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1464

We're only interested in and/or/icmp here, if one of the operands is a multi-use argument we won't be doing anything with it anyway (that is, it will not get transformed, but it also won't block any transforms on e.g. a different operand).

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1480

in short: createInvariantCond uses BI as expansion point for icmp and not rewriter's insertion point. I think this can be changed, but takes more than flick of fingers. Now much are you concerned? Can it go as follow-up?

We never generate more than 1 non-invariant instruction here as far as I can tell.

[mkazantsev]

Fixed astray comment.

Rewrote one-use check that now we only collect single use ICMPs as leaves and don't filter out what we don't need to.

As for insertion point, proposing follow-up. Needs some underlying refactoring I don't want to be blocked on.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1480

i.e. in fact it's also invariant, just placed in the loop. I guess we could instead use rewriter's insertion point and even inject it in preheader.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1464

Merge these two ifs?

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1464

Formally we can, but they're so semantically different...

[fhahn]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1461

nit: leaf ICMPs?

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1461

Thanks for catch!

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

createInvariantCond(const Loop *L, BasicBlock *ExitingBB,
   auto *RHSV = Rewriter.expandCodeFor(LIP.RHS);
   bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
   if (ExitIfTrue)
     InvariantPred = ICmpInst::getInversePredicate(InvariantPred);
   IRBuilder<> Builder(BI);
   return Builder.CreateICmp(InvariantPred, LHSV, RHSV,
                             BI->getCondition()->getName());
 }
 
 static std::optional<Value *>
 createReplacement(Value *V, const Loop *L, BasicBlock *ExitingBB,
-                  const SCEV *MaxIter, bool SkipLastIter, ScalarEvolution *SE,
-                  SCEVExpander &Rewriter) {
+                  const SCEV *MaxIter, bool Inverted, bool SkipLastIter,
+                  ScalarEvolution *SE, SCEVExpander &Rewriter) {
   ICmpInst::Predicate Pred;
   Value *LHS, *RHS;
   if (!match(V, m_ICmp(Pred, m_Value(LHS), m_Value(RHS))))
     return std::nullopt;
 
   // 'LHS pred RHS' should now mean that we stay in loop.
   auto *BI = cast<BranchInst>(ExitingBB->getTerminator());
-  BasicBlock *FalseSucc = BI->getSuccessor(1);
-  if (L->contains(FalseSucc))
+  if (Inverted)
     Pred = CmpInst::getInversePredicate(Pred);
 
   const SCEV *LHSS = SE->getSCEVAtScope(LHS, L);
   const SCEV *RHSS = SE->getSCEVAtScope(RHS, L);
   // Can we prove it to be trivially true or false?
   if (auto EV = SE->evaluatePredicateAt(Pred, LHSS, RHSS, BI))
     return createFoldedExitCond(L, ExitingBB, /*IsTaken*/ !*EV);
 

 
 static bool optimizeLoopExitWithUnknownExitCount(
     const Loop *L, BranchInst *BI, BasicBlock *ExitingBB, const SCEV *MaxIter,
     bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter,
     SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
   assert(
       (L->contains(BI->getSuccessor(0)) != L->contains(BI->getSuccessor(1))) &&
       "Not a loop exit!");
-  auto NewCond = createReplacement(BI->getCondition(), L, ExitingBB, MaxIter,
-                                   SkipLastIter, SE, Rewriter);
-  if (!NewCond)
+
+  // For branch that stays in loop by TRUE condition, go through AND. For branch
+  // that stays in loop by FALSE condition, go through OR. Both gives the
+  // similar logic: "stay in loop iff all conditions are true(false)".
+  bool Inverted = L->contains(BI->getSuccessor(1));
+  SmallVector<Value *, 4> LeafConditions;
+  SmallVector<Value *, 4> Worklist;
+  SmallPtrSet<Value *, 4> Visited;
+  Value *OldCond = BI->getCondition();
+  Visited.insert(OldCond);
+  Worklist.push_back(OldCond);
+
+  auto GoThrough = [&](Value *V) {
+    Value *LHS = nullptr, *RHS = nullptr;
+    // We do not want to duplicate these operations, but simply replace their
+    // operands. It is only legal when no one else is using them.
+    if (Inverted) {
+      if (!match(V, m_LogicalOr(m_Value(LHS), m_Value(RHS))))
         return false;
-  replaceExitCond(BI, *NewCond, DeadInsts);
+    } else {
+      if (!match(V, m_LogicalAnd(m_Value(LHS), m_Value(RHS))))
+        return false;
+    }
+    if (Visited.insert(LHS).second)
+      Worklist.push_back(LHS);
+    if (Visited.insert(RHS).second)
+      Worklist.push_back(RHS);
     return true;
+  };
+
+  do {
+    Value *Curr = Worklist.pop_back_val();
+    // Avoid instruction duplication.
+    if (isa<Instruction>(Curr) && !Curr->hasOneUse())
+      return false;
+    // Go through AND/OR conditions. Collect leaves.
+    if (!GoThrough(Curr))
+      LeafConditions.push_back(Curr);
+  } while (!Worklist.empty());
+
+  bool Changed = false;
+  for (auto *OldCond : LeafConditions)
+    if (auto Replaced =
+            createReplacement(OldCond, L, ExitingBB, MaxIter, Inverted,
+                              SkipLastIter, SE, Rewriter)) {
+      Changed = true;
+      auto *NewCond = *Replaced;
+      if (auto *NCI = dyn_cast<Instruction>(NewCond)) {
+        NCI->setName(OldCond->getName() + ".first_iter");
+        NCI->moveBefore(cast<Instruction>(OldCond));
+      }
+      LLVM_DEBUG(dbgs() << "Unknown exit count: Replacing " << *OldCond
+                        << " with " << *NewCond << "\n");
+      assert(OldCond->hasOneUse() && "Must be!");
+      OldCond->replaceAllUsesWith(NewCond);
+      DeadInsts.push_back(OldCond);
+    }
+  return Changed;
 }
 
 bool IndVarSimplify::canonicalizeExitCondition(Loop *L) {
   // Note: This is duplicating a particular part on SimplifyIndVars reasoning.
   // We need to duplicate it because given icmp zext(small-iv), C, IVUsers
   // never reaches the icmp since the zext doesn't fold to an AddRec unless
   // it already has flags.  The alternative to this would be to extending the
   // set of "interesting" IV users to include the icmp, but doing that

llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=indvars -S < %s | FileCheck %s
 
 declare i1 @cond()
 
 ; Range check here can be turned into invariant check.
 define i32 @test_simple_case(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_simple_case(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_CHECK]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[RANGE_CHECK3:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
-; CHECK-NEXT:    br i1 [[RANGE_CHECK3]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
+; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 ; CHECK:       failed_1:

 
 failed_1:
   ret i32 -1
 
 failed_2:
   ret i32 -2
 }
 
-; TODO: This example is equivalent to @test_simple_case, with only difference that
-;       both checks are littered with extra irrelevant conditions. We should be able
-;       to replace it with invariant despite this fact.
-;       https://alive2.llvm.org/ce/z/G4iW8c
+; This example is equivalent to @test_simple_case, with only difference that
+; both checks are littered with extra irrelevant conditions. We should be able
+; to replace it with invariant despite this fact.
+; https://alive2.llvm.org/ce/z/G4iW8c
 define i32 @test_litter_conditions(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1
-; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_MINUS_1]], [[LEN:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK]], [[FAKE_2]]
+; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]]
 ; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]

 
 failed_1:
   ret i32 -1
 
 failed_2:
   ret i32 -2
 }
 
-; TODO: Same as test_litter_conditions, but swapped exit block branches
-;       and exit condition expressed by OR. Still optimizable.
+; Same as test_litter_conditions, but swapped exit block branches
+; and exit condition expressed by OR. Still optimizable.
 define i32 @test_litter_conditions_inverse(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions_inverse(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1
-; CHECK-NEXT:    [[RANGE_CHECK_FAILED:%.*]] = icmp uge i32 [[IV_MINUS_1]], [[LEN:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED]], [[FAKE_2]]
+; CHECK-NEXT:    [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], [[FAKE_2]]
 ; CHECK-NEXT:    br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[RANGE_CHECK3:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
-; CHECK-NEXT:    br i1 [[RANGE_CHECK3]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
+; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 ; CHECK:       failed_1:

 
 failed_1:
   ret i32 -1
 
 failed_2:
   ret i32 -2
 }
 
-; TODO: Same as test_litter_conditions_01, but swapped exit block branches
-;       and condition expressed by OR. Still optimizable.
+; Same as test_litter_conditions_01, but swapped exit block branches
+; and condition expressed by OR. Still optimizable.
 define i32 @test_litter_conditions_01_inverse(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions_01_inverse(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[RANGE_CHECK_FAILED3:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
-; CHECK-NEXT:    br i1 [[RANGE_CHECK_FAILED3]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
+; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
+; CHECK-NEXT:    br i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 ; CHECK:       failed_1:

 
 failed_1:
   ret i32 -1
 
 failed_2:
   ret i32 -2
 }
 
 ; TODO: Simplified version 2 of test_litter_conditions.
 define i32 @test_litter_conditions_02(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions_02(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_CHECK]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1
-; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_MINUS_1]], [[LEN:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK]], [[FAKE_2]]
+; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]]
 ; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]

 
 failed_1:
   ret i32 -1
 
 failed_2:
   ret i32 -2
 }
 
-; TODO: Same as test_litter_conditions_02, but swapped exit block branches,
-;       and condition is expressed as OR. Still optimizable.
+; Same as test_litter_conditions_02, but swapped exit block branches,
+; and condition is expressed as OR. Still optimizable.
 define i32 @test_litter_conditions_02_inverse(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions_02_inverse(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_CHECK]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1
-; CHECK-NEXT:    [[RANGE_CHECK_FAILED:%.*]] = icmp uge i32 [[IV_MINUS_1]], [[LEN:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED]], [[FAKE_2]]
+; CHECK-NEXT:    [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], [[FAKE_2]]
 ; CHECK-NEXT:    br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]

 
 failed_1:
   ret i32 -1
 
 failed_2:
   ret i32 -2
 }
 
-; TODO: Same as @test_litter_conditions, but all conditions are computed in
-;       header block. Make sure we infer fact from the right context.
-;       https://alive2.llvm.org/ce/z/JiD-Pw
+; Same as @test_litter_conditions, but all conditions are computed in
+; header block. Make sure we infer fact from the right context.
+; https://alive2.llvm.org/ce/z/JiD-Pw
 define i32 @test_litter_conditions_bad_context(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions_bad_context(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
-; CHECK-NEXT:    [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1
-; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_MINUS_1]], [[LEN:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK]], [[FAKE_2]]
+; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]]
 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
 ; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:

 
 failed_1:
   ret i32 -1
 
 failed_2:
   ret i32 -2
 }
 
-; TODO: Same as @test_litter_conditions_bad_context, but swapped exit block branches,
-;       and conditions expressed as OR. Still optimizable.
+; Same as @test_litter_conditions_bad_context, but swapped exit block branches,
+; and conditions expressed as OR. Still optimizable.
 define i32 @test_litter_conditions_bad_context_inverse(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions_bad_context_inverse(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
-; CHECK-NEXT:    [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1
-; CHECK-NEXT:    [[RANGE_CHECK_FAILED:%.*]] = icmp uge i32 [[IV_MINUS_1]], [[LEN:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED]], [[FAKE_2]]
+; CHECK-NEXT:    [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], [[FAKE_2]]
 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
 ; CHECK-NEXT:    br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:

 
 done:
   ret i32 %iv
 
 failed:
   ret i32 -3
 }
 
-; TODO: Same as test_litter_conditions, but with logical AND.
+; Same as test_litter_conditions, but with logical AND.
 define i32 @test_litter_conditions_logical_and(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions_logical_and(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1
-; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_MINUS_1]], [[LEN:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[AND_2:%.*]] = select i1 [[RANGE_CHECK]], i1 [[FAKE_2]], i1 false
+; CHECK-NEXT:    [[AND_2:%.*]] = select i1 [[RANGE_CHECK_FIRST_ITER]], i1 [[FAKE_2]], i1 false
 ; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]

 
 failed_1:
   ret i32 -1
 
 failed_2:
   ret i32 -2
 }
 
-; TODO: Same as test_litter_conditions_inverse, but with logical OR.
+; Same as test_litter_conditions_inverse, but with logical OR.
 define i32 @test_litter_conditions_inverse_logical_or(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions_inverse_logical_or(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1
-; CHECK-NEXT:    [[RANGE_CHECK_FAILED:%.*]] = icmp uge i32 [[IV_MINUS_1]], [[LEN:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[OR_2:%.*]] = select i1 [[RANGE_CHECK_FAILED]], i1 true, i1 [[FAKE_2]]
+; CHECK-NEXT:    [[OR_2:%.*]] = select i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], i1 true, i1 [[FAKE_2]]
 ; CHECK-NEXT:    br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]