Index: llvm/lib/Transforms/Scalar/LoopDeletion.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/LoopDeletion.cpp
+++ llvm/lib/Transforms/Scalar/LoopDeletion.cpp
@@ -126,6 +126,10 @@
   return true;
 }
 
+static bool loopMustProgress(Loop *L) {
+  return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
+}
+
 /// Remove a loop if it is dead.
 ///
 /// A loop is considered dead if it does not impact the observable behavior of
@@ -210,8 +214,7 @@
   // Don't remove loops for which we can't solve the trip count.
   // They could be infinite, in which case we'd be changing program behavior.
   const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
-  if (isa<SCEVCouldNotCompute>(S) &&
-      !L->getHeader()->getParent()->mustProgress() && !hasMustProgress(L)) {
+  if (isa<SCEVCouldNotCompute>(S) && !loopMustProgress(L)) {
     LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
                          "not required to make progress.\n");
     return Changed ? LoopDeletionResult::Modified
@@ -230,6 +233,68 @@
   return LoopDeletionResult::Deleted;
 }
 
+static bool usesLoopPHI(Instruction *I, Loop *L) {
+  if (!L->contains(I->getParent()))
+    return false;
+  if (isa<PHINode>(I))
+    return true;
+  for (auto &Op : I->operands())
+    if (Instruction *OpI = dyn_cast<Instruction>(&Op))
+      if (usesLoopPHI(OpI, L))
+        return true;
+  return false;
+}
+
+static bool tryInsertEarlyExit(Loop *L, DominatorTree &DT,
+                               ScalarEvolution &SE, LoopInfo &LI,
+                               MemorySSA *MSSA,
+                               OptimizationRemarkEmitter &ORE) {
+  using namespace PatternMatch;
+  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
+
+  // Only with a forward progress gurantee is it legal to exit early from a
+  // dead path of the loop.  Do early exit if only one or two blocks.
+  if (!loopMustProgress(L) || L->getNumBlocks() < 3)
+    return false;
+
+  BasicBlock *HeaderBlock = L->getHeader();
+  BasicBlock *LatchBlock = L->getLoopLatch();
+  Instruction *HeaderBr = HeaderBlock->getTerminator();
+  Instruction *CmpI = nullptr;
+  BasicBlock *Taken, *NotTaken;
+  if (!match(HeaderBr, m_Br(m_Instruction(CmpI), Taken, NotTaken)))
+    return false;
+
+  // See if header branches to latch.
+  if (Taken != LatchBlock && NotTaken != LatchBlock)
+    return false;
+
+  // Check that both header and latch are free of side-effects.
+  for (auto &I : *HeaderBlock)
+    if (I.mayHaveSideEffects() && !I.isDroppable())
+      return false;
+  for (auto &I : *LatchBlock)
+    if (I.mayHaveSideEffects() && !I.isDroppable())
+      return false;
+
+  // Check that the comparison is not based on any value redefined in the
+  // loop. It was not possible to hoist it out of the loop but here it is
+  // sufficient that it is constant on the dead path.  TODO: worth checking
+  // if incoming value from preheader/latch are the same and allow that case?
+  if (usesLoopPHI(CmpI, L))
+    return false;
+
+  // The header takes a branch across the main body of the loop directly to
+  // the latch. This path is dead, so turn this into an early exit.
+  Instruction *LatchBr = LatchBlock->getTerminator();
+  if (!match(LatchBr, m_Br(m_Value(), Taken, NotTaken)))
+    return false;
+  BasicBlock *ExitBlock = (Taken != HeaderBlock ? Taken : NotTaken);
+  unsigned OpNo = HeaderBr->getOperand(1) == LatchBlock ? 1 : 2;
+  HeaderBr->setOperand(OpNo, ExitBlock);
+  return true;
+}
+
 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
                                         LoopStandardAnalysisResults &AR,
                                         LPMUpdater &Updater) {
@@ -303,6 +368,8 @@
 
   if (Result == LoopDeletionResult::Deleted)
     LPM.markLoopAsDeleted(*L);
+  else if (tryInsertEarlyExit(L, DT, SE, LI, MSSA, ORE))
+    Result = LoopDeletionResult::Modified;
 
   return Result != LoopDeletionResult::Unmodified;
 }