Index: lib/Transforms/Scalar/IndVarSimplify.cpp
===================================================================
--- lib/Transforms/Scalar/IndVarSimplify.cpp
+++ lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -144,7 +144,7 @@
   bool rewriteNonIntegerIVs(Loop *L);
 
   bool simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
-  bool optimizeLoopExits(Loop *L);
+  bool optimizeLoopExits(Loop *L, SCEVExpander &Rewriter);
 
   bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
   bool rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
@@ -2624,7 +2624,7 @@
   return MadeAnyChanges;
 }
 
-bool IndVarSimplify::optimizeLoopExits(Loop *L) {
+bool IndVarSimplify::optimizeLoopExits(Loop *L, SCEVExpander &Rewriter) {
   SmallVector<BasicBlock*, 16> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
@@ -2700,8 +2700,7 @@
     assert(MaxExitCount->getType() == ExitCount->getType());
     
     // Can we prove that some other exit must be taken strictly before this
-    // one?  TODO: handle cases where ule is known, and equality is covered
-    // by a dominating exit
+    // one?
     if (SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_ULT,
                                      MaxExitCount, ExitCount)) {
       bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
@@ -2715,16 +2714,90 @@
       continue;
     }
 
-    // TODO: If we can prove that the exiting iteration is equal to the exit
-    // count for this exit and that no previous exit oppurtunities exist within
-    // the loop, then we can discharge all other exits.  (May fall out of
-    // previous TODO.) 
+    // If we know that this exit's count is equal to the loops exit count, then
+    // we know we won't reach any exits strictly after this one and can fold
+    // them out of existance.  There may be an exit before us which causes us
+    // never to reach this one on the exiting iteration, so we still don't know
+    // whether this exit is taken.
+    const SCEV *ExactBTC = SE->getBackedgeTakenCount(L);
+    if (isa<SCEVCouldNotCompute>(ExactBTC))
+      continue;
+    // TODO: Bitwidth conversion.
+    if (!isa<SCEVCouldNotCompute>(ExactBTC) &&
+        SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_EQ,
+                                     ExactBTC, ExitCount))
+      for (BasicBlock *OtherExitingBB : ExitingBlocks) {
+        // If our exitting block exits multiple loops, we can only rewrite the
+        // innermost one.  Otherwise, we're changing how many times the
+        // innermost loop runs before it exits. 
+        if (LI->getLoopFor(OtherExitingBB) != L)
+          continue;
+
+        if (!DT->properlyDominates(ExitingBB, OtherExitingBB))
+          continue;
+
+        // Can't rewrite non-branch yet.
+        BranchInst *BI = dyn_cast<BranchInst>(OtherExitingBB->getTerminator());
+        if (!BI)
+          continue;
+
+        // If already constant, nothing to do.
+        if (isa<Constant>(BI->getCondition()))
+          continue;
     
+        bool ExitIfTrue = !L->contains(*succ_begin(OtherExitingBB));
+        auto *OldCond = BI->getCondition();
+        auto *NewCond = ExitIfTrue ? ConstantInt::getFalse(OldCond->getType()) :
+          ConstantInt::getTrue(OldCond->getType());
+        BI->setCondition(NewCond);
+        if (OldCond->use_empty())
+          DeadInsts.push_back(OldCond);
+        Changed = true;
+      }
+
+#if 1
     // TODO: If we can't prove any relation between our exit count and the
     // loops exit count, but taking this exit doesn't require actually running
     // the loop (i.e. no side effects, no computed values used in exit), then
     // we can replace the exit test with a loop invariant test which exits on
-    // the first iteration.  
+    // the first iteration.
+    bool LoopIsReadOnly = true;
+    for (BasicBlock *BB : L->blocks())
+      for (auto &I : *BB)
+        LoopIsReadOnly &= !I.mayHaveSideEffects();
+
+    bool DominatesAllOther = true;
+    for (BasicBlock *OtherExitingBB : ExitingBlocks)
+      if (OtherExitingBB != ExitingBB &&
+          !DT->properlyDominates(ExitingBB, OtherExitingBB)) {
+        // TODO: exclude invariant ones
+        DominatesAllOther = false;
+        break;
+      }
+
+    BasicBlock *ExitBlock = *succ_begin(ExitingBB);
+    if (L->contains(ExitBlock))
+      ExitBlock = *std::next(succ_begin(ExitingBB));
+    bool NoPHI = empty(ExitBlock->phis());
+    dbgs() << ExitBlock->getName() << "\n";
+    dbgs() << LoopIsReadOnly << DominatesAllOther << NoPHI << "\n";
+    if (LoopIsReadOnly && DominatesAllOther && NoPHI) {
+      IRBuilder<> B(BI);
+      dbgs() << *ExactBTC << "\n";
+      dbgs() << *ExitCount << "\n";
+#if 1
+      SCEVExpander Rewriter2(*SE, DL, "indvars2");
+      auto *NewCond = B.CreateICmp(CmpInst::ICMP_EQ,
+                                   Rewriter2.expandCodeFor(ExactBTC),
+                                   Rewriter2.expandCodeFor(ExitCount));
+      auto *OldCond = BI->getCondition();
+      BI->setCondition(NewCond);
+      if (OldCond->use_empty())
+        DeadInsts.push_back(OldCond);
+#endif
+      Changed = true;
+    }
+#endif
   }
   return Changed;
 }
@@ -2785,7 +2858,7 @@
   // Eliminate redundant IV cycles.
   NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);
 
-  Changed |= optimizeLoopExits(L);
+  Changed |= optimizeLoopExits(L, Rewriter);
 
   // If we have a trip count expression, rewrite the loop's exit condition
   // using it.