Index: llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -1428,11 +1428,41 @@
   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)
+
+  SmallVector<Value *, 4> Conditions;
+  SmallVector<Value *, 4> Worklist;
+  SmallPtrSet<Value *, 4> Visited;
+  Visited.insert(BI->getCondition());
+  Worklist.push_back(BI->getCondition());
+  do {
+    Value *Curr = Worklist.pop_back_val();
+    Value *LHS, *RHS;
+    // Go through AND conditions.
+    if (match(Curr, m_And(m_Value(LHS), m_Value(RHS)))) {
+      if (Visited.insert(LHS).second)
+        Worklist.push_back(LHS);
+      if (Visited.insert(RHS).second)
+        Worklist.push_back(RHS);
+    } else
+      // Collect all terminal conditions.
+      Conditions.push_back(Curr);
+  } while (!Worklist.empty());
+
+  bool Changed = false;
+  for (size_t i = 0; i < Conditions.size(); ++i)
+    if (auto NewCond = createReplacement(Conditions[i], L, ExitingBB, MaxIter,
+                                         SkipLastIter, SE, Rewriter)) {
+      Changed = true;
+      Conditions[i] = *NewCond;
+    }
+
+  if (!Changed)
     return false;
-  replaceExitCond(BI, *NewCond, DeadInsts);
+
+  // Generate the AND aggregation of all Conditions.
+  IRBuilder<> Builder(cast<Instruction>(BI));
+  Value *NewCond = Builder.CreateAnd(Conditions);
+  replaceExitCond(BI, NewCond, DeadInsts);
   return true;
 }
 
Index: llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll
===================================================================
--- llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll
+++ llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll
@@ -56,26 +56,23 @@
   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
+; https://alive2.llvm.org/ce/z/G4iW8c
 define i32 @test_litter_conditions(i32 %start, i32 %len) {
 ; CHECK-LABEL: define {{[^@]+}}@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:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK]], [[FAKE_2]]
-; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
+; CHECK-NEXT:    [[AND_23:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[FAKE_2]], [[AND_23]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
@@ -294,21 +291,20 @@
   ret i32 -2
 }
 
-; TODO: Simplified version 2 of test_litter_conditions.
 define i32 @test_litter_conditions_02(i32 %start, i32 %len) {
 ; CHECK-LABEL: define {{[^@]+}}@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:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK]], [[FAKE_2]]
-; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
+; CHECK-NEXT:    [[AND_23:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[FAKE_2]], [[AND_23]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
@@ -408,25 +404,23 @@
   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
+; https://alive2.llvm.org/ce/z/JiD-Pw
 define i32 @test_litter_conditions_bad_context(i32 %start, i32 %len) {
 ; CHECK-LABEL: define {{[^@]+}}@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:    [[FAKE_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK]], [[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-NEXT:    [[AND_23:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[FAKE_2]], [[AND_23]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()