[IndVars] Use exit count reasoning to discharge obviously untaken exits

[reames]

Summary

Continue in the spirit of D63618, and use exit count reasoning to prove away loop exits which can not be taken since the backedge taken count of the loop as a whole is provably less than the minimal BE count required to take this particular loop exit.

As demonstrated in the newly added tests, this triggers in a number of cases where IndVars was previously unable to discharge obviously redundant exit tests. And some not so obvious ones.

Suggestions on tests to exercise the backedge guard form would be very welcome. I'm not sure is the isKnownPredicate version actually gives us anything, but it's reasonable for completeness sake?

[nikic]

lib/Transforms/Scalar/IndVarSimplify.cpp

2734

Some kind of copy and paste mistake? The second clause of the || fully subsumes the last.

[reames]

lib/Transforms/Scalar/IndVarSimplify.cpp

2734

Yep, that should have been the backedge case. Good catch.

Now you see why I asked for ideas on how to test that case. :)

[reames]

Address Nikita's catch.

[reames]

Remove the untested code since no one suggested uses. Hopefully this should unblock review.

[jdoerfert]

Some minor comments. Generally this makes sense but someone else should probably take a look as well.

lib/Transforms/Scalar/IndVarSimplify.cpp

2703

BI, with this definition, is already available.

2731

Same as above.

2739

Same (non-trivial) code as above, could we extract it somehow?

[reames]

Address review comments

[reames]

lib/Transforms/Scalar/IndVarSimplify.cpp

2739

Seems like a reasonable suggestion. I'll explore options for a helper function in a follow on commit. We have this same pattern in a few other places as well.

[nikic]

LGTM

lib/Transforms/Scalar/IndVarSimplify.cpp

2690

nit: Unnecessary parens.

[morehouse]

The assertion assert(!ExitCount->isZero() && "Should have been folded above"); is failing during the unittest build on the UBSan bot: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-ubsan/builds/13940

FAILED: unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o 
/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang++   -DGTEST_HAS_RTTI=0 -DGTEST_HAS_TR1_TUPLE=0 -DGTEST_LANG_CXX11=1 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Iunittests/Support -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support -I/usr/include/libxml2 -Iinclude -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/include -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/unittest/googletest/include -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/unittest/googlemock/include -fsanitize=undefined -w -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -std=c++11 -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wcovered-switch-default -Wno-class-memaccess -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wstring-conversion -fno-omit-frame-pointer -gline-tables-only -fsanitize=undefined -fno-sanitize=vptr,function -fno-sanitize-recover=all -fsanitize-blacklist=/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/sanitizers/ubsan_blacklist.txt -fdiagnostics-color -ffunction-sections -fdata-sections -O3    -UNDEBUG  -Wno-variadic-macros -Wno-gnu-zero-variadic-macro-arguments -fno-exceptions -fno-rtti -MD -MT unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o -MF unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o.d -o unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o -c /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support/LEB128Test.cpp
clang-9: /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp:2813: bool {anonymous}::IndVarSimplify::run(llvm::Loop*): Assertion `!ExitCount->isZero() && "Should have been folded above"' failed.
Stack dump:
0.	Program arguments: /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -disable-free -main-file-name LEB128Test.cpp -mrelocation-model pic -pic-level 2 -mthread-model posix -mdisable-fp-elim -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debug-info-kind=line-tables-only -dwarf-version=4 -debugger-tuning=gdb -ffunction-sections -fdata-sections -coverage-notes-file /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build_ubsan/unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.gcno -resource-dir /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/lib/clang/9.0.0 -dependency-file unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o.d -sys-header-deps -MT unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o -D GTEST_HAS_RTTI=0 -D GTEST_HAS_TR1_TUPLE=0 -D GTEST_LANG_CXX11=1 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I unittests/Support -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support -I /usr/include/libxml2 -I include -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/include -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/unittest/googletest/include -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/unittest/googlemock/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -Wno-long-long -Wimplicit-fallthrough -Wcovered-switch-default -Wno-class-memaccess -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wstring-conversion -Wno-variadic-macros -Wno-gnu-zero-variadic-macro-arguments -pedantic -w -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build_ubsan -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fsanitize=alignment,array-bounds,bool,builtin,enum,float-cast-overflow,integer-divide-by-zero,nonnull-attribute,null,object-size,pointer-overflow,return,returns-nonnull-attribute,shift-base,shift-exponent,signed-integer-overflow,unreachable,vla-bound -fsanitize-blacklist=/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/sanitizers/ubsan_blacklist.txt -fdepfile-entry=/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/sanitizers/ubsan_blacklist.txt -fno-rtti -fobjc-runtime=gcc -fdiagnostics-show-option -fcolor-diagnostics -vectorize-loops -vectorize-slp -faddrsig -o unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o -x c++ /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support/LEB128Test.cpp 
1.	<eof> parser at end of file
2.	Per-module optimization passes
3.	Running pass 'CallGraph Pass Manager' on module '/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support/LEB128Test.cpp'.
4.	Running pass 'Loop Pass Manager' on function '@_ZN12_GLOBAL__N_129LEB128Test_DecodeULEB128_Test8TestBodyEv'
5.	Running pass 'Induction Variable Simplification' on basic block '%do.body.i1427'
 #0 0x000056385b4fbb9a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2b1cb9a)
 #1 0x000056385b4f9925 llvm::sys::RunSignalHandlers() (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2b1a925)
 #2 0x000056385b4f9a3c SignalHandler(int) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2b1aa3c)
 #3 0x00007f3bda1a10e0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x110e0)
 #4 0x00007f3bd8f60fff raise (/lib/x86_64-linux-gnu/libc.so.6+0x32fff)
 #5 0x00007f3bd8f6242a abort (/lib/x86_64-linux-gnu/libc.so.6+0x3442a)
 #6 0x00007f3bd8f59e67 (/lib/x86_64-linux-gnu/libc.so.6+0x2be67)
 #7 0x00007f3bd8f59f12 (/lib/x86_64-linux-gnu/libc.so.6+0x2bf12)
 #8 0x000056385b2ede4d (anonymous namespace)::IndVarSimplify::run(llvm::Loop*) (.part.484) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x290ee4d)
 #9 0x000056385b2ee9bf (anonymous namespace)::IndVarSimplifyLegacyPass::runOnLoop(llvm::Loop*, llvm::LPPassManager&) (.part.485) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x290f9bf)
#10 0x000056385a986f13 llvm::LPPassManager::runOnFunction(llvm::Function&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x1fa7f13)
#11 0x000056385af4c010 llvm::FPPassManager::runOnFunction(llvm::Function&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x256d010)
#12 0x000056385a8e16c5 (anonymous namespace)::CGPassManager::runOnModule(llvm::Module&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x1f026c5)
#13 0x000056385af4cd54 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x256dd54)
#14 0x000056385b6f9a29 (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2d1aa29)
#15 0x000056385b6fb358 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2d1c358)
#16 0x000056385c106cfa clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3727cfa)
#17 0x000056385c99aac9 clang::ParseAST(clang::Sema&, bool, bool) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3fbbac9)
#18 0x000056385c104729 clang::CodeGenAction::ExecuteAction() (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3725729)
#19 0x000056385bba1e41 clang::FrontendAction::Execute() (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x31c2e41)
#20 0x000056385bb68c60 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3189c60)
#21 0x000056385bc48482 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3269482)
#22 0x0000563859933986 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0xf54986)
#23 0x00005638598a820d main (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0xec920d)
#24 0x00007f3bd8f4e2e1 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e1)
#25 0x000056385992fb4a _start (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0xf50b4a)

Could someone please take a look?

[reames]

In D63733#1587822, @morehouse wrote:

The assertion assert(!ExitCount->isZero() && "Should have been folded above"); is failing during the unittest build on the UBSan bot: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-ubsan/builds/13940

I submitted a speculative fix for this in rL366241, but I'd really appreciate someone familiar with the bot extracting IR so that I can confirm there's only one issue here.

lib/Transforms/Scalar/IndVarSimplify.cpp

class IndVarSimplify {
   SmallVector<WeakTrackingVH, 16> DeadInsts;
 
   bool isValidRewrite(Value *FromVal, Value *ToVal);
 
   bool handleFloatingPointIV(Loop *L, PHINode *PH);
   bool rewriteNonIntegerIVs(Loop *L);
 
   bool simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
+  bool optimizeLoopExits(Loop *L);
 
   bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
   bool rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
   bool rewriteFirstIterationLoopExitValues(Loop *L);
   bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) const;
 
   bool linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,
                                  const SCEV *ExitCount,
while (I != Preheader->begin()) {
     ToMove->moveBefore(*ExitBlock, InsertPt);
     if (Done) break;
     InsertPt = ToMove->getIterator();
   }
 
   return MadeAnyChanges;
 }
 
+bool IndVarSimplify::optimizeLoopExits(Loop *L) {
+  SmallVector<BasicBlock*, 16> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+  BasicBlock * const Latch = L->getLoopLatch();
+
+  // Form an expression for the maximum exit count possible for this loop. We
+  // merge the max and exact information to approximate a version of
+  // getMaxBackedgeTakenInfo which isn't restricted to just constants.
+  // TODO: factor this out as a version of getMaxBackedgeTakenCount which
+  // isn't guaranteed to return a constant.
+  SmallVector<const SCEV*, 4> ExitCounts;
+  const SCEV *MaxConstEC = SE->getMaxBackedgeTakenCount(L);
+  if (!isa<SCEVCouldNotCompute>(MaxConstEC))
+    ExitCounts.push_back(MaxConstEC);
+  for (BasicBlock *ExitingBB : ExitingBlocks) {
+    const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
+    if (!isa<SCEVCouldNotCompute>(ExitCount)) {
+      assert(DT->dominates(ExitingBB, Latch) &&
+             "We should only have known counts for exiting blocks that "
+             "dominate latch!");
+      ExitCounts.push_back(ExitCount);
+    }
+  }
+  if (ExitCounts.empty())
+    return false;
+  const SCEV *MaxExitCount = SE->getUMinFromMismatchedTypes(ExitCounts);
+
+  bool Changed = false;
+  for (BasicBlock *ExitingBB : 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(ExitingBB) != L)
+      continue;
+
+    // Can't rewrite non-branch yet.
+    BranchInst *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
+    if (!BI)
+      continue;
+
+    // If already constant, nothing to do.
+    if (isa<Constant>((BI->getCondition())))
+      continue;
+    
+    const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
+    if (isa<SCEVCouldNotCompute>(ExitCount))
+      continue;
+
+    // If we know we'd exit on the first iteration, rewrite the exit to
+    // reflect this.  This does not imply the loop must exit through this
+    // exit; there may be an earlier one taken on the first iteration.
+    // TODO: Given we know the backedge can't be taken, we should go ahead
+    // and break it.  Or at least, kill all the header phis and simplify.
+    if (ExitCount->isZero()) {
+      auto *BI = cast<BranchInst>(ExitingBB->getTerminator());
+      bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
+      auto *OldCond = BI->getCondition();
+      auto *NewCond = ExitIfTrue ? ConstantInt::getTrue(OldCond->getType()) :
+        ConstantInt::getFalse(OldCond->getType());
+      BI->setCondition(NewCond);
+      if (OldCond->use_empty())
+        DeadInsts.push_back(OldCond);
+      Changed = true;
+      continue;
+    }
+
+    // If we end up with a pointer exit count, bail.
+    if (!ExitCount->getType()->isIntegerTy() ||
+        !MaxExitCount->getType()->isIntegerTy())
+      return false;
+    
+    Type *WiderType =
+      SE->getWiderType(MaxExitCount->getType(), ExitCount->getType());
+    ExitCount = SE->getNoopOrZeroExtend(ExitCount, WiderType);
+    MaxExitCount = SE->getNoopOrZeroExtend(MaxExitCount, WiderType);
+    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
+    if (SE->isKnownPredicate(CmpInst::ICMP_ULT, MaxExitCount, ExitCount) ||
+        SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_ULT,
+                                     MaxExitCount, ExitCount) ||
+        (SE->isKnownNonZero(ExitCount) &&
+         SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_ULT,
+                                      MaxExitCount, ExitCount))) {
+      auto *BI = cast<BranchInst>(ExitingBB->getTerminator());
+      bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
+      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;
+      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.) 
+    
+    // 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.  
+  }
+  return Changed;
+}
+
 //===----------------------------------------------------------------------===//
 //  IndVarSimplify driver. Manage several subpasses of IV simplification.
 //===----------------------------------------------------------------------===//
 
 bool IndVarSimplify::run(Loop *L) {
   // We need (and expect!) the incoming loop to be in LCSSA.
   assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
          "LCSSA required to run indvars!");
#endif
   //
   if (ReplaceExitValue != NeverRepl &&
       !isa<SCEVCouldNotCompute>(BackedgeTakenCount))
     Changed |= rewriteLoopExitValues(L, Rewriter);
 
   // Eliminate redundant IV cycles.
   NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);
 
+  Changed |= optimizeLoopExits(L);
+
   // If we have a trip count expression, rewrite the loop's exit condition
   // using it.  
   if (!DisableLFTR) {
     SmallVector<BasicBlock*, 16> ExitingBlocks;
     L->getExitingBlocks(ExitingBlocks);
     for (BasicBlock *ExitingBB : ExitingBlocks) {
       // Can't rewrite non-branch yet.
       if (!isa<BranchInst>(ExitingBB->getTerminator()))
         continue;
 
       // 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(ExitingBB) != L)
         continue;
       
       if (!needsLFTR(L, ExitingBB))
         continue;
 
       const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
       if (isa<SCEVCouldNotCompute>(ExitCount))
         continue;
 
-      // If we know we'd exit on the first iteration, rewrite the exit to
-      // reflect this.  This does not imply the loop must exit through this
-      // exit; there may be an earlier one taken on the first iteration.
-      // TODO: Given we know the backedge can't be taken, we should go ahead
-      // and break it.  Or at least, kill all the header phis and simplify.
-      if (ExitCount->isZero()) {
-        auto *BI = cast<BranchInst>(ExitingBB->getTerminator());
-        bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
-        auto *OldCond = BI->getCondition();
-        auto *NewCond = ExitIfTrue ? ConstantInt::getTrue(OldCond->getType()) :
-          ConstantInt::getFalse(OldCond->getType());
-        BI->setCondition(NewCond);
-        if (OldCond->use_empty())
-          DeadInsts.push_back(OldCond);
-        Changed = true;
-        continue;
-      }
+      assert(!ExitCount->isZero() && "Should have been folded above");
       
       PHINode *IndVar = FindLoopCounter(L, ExitingBB, ExitCount, SE, DT);
       if (!IndVar)
         continue;
       
       // Avoid high cost expansions.  Note: This heuristic is questionable in
       // that our definition of "high cost" is not exactly principled.  
       if (Rewriter.isHighCostExpansion(ExitCount, L))

test/Transforms/IndVarSimplify/eliminate-exit.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -indvars -S < %s | FileCheck %s
+
+define void @ult(i64 %n, i64 %m) {
+; CHECK-LABEL: @ult(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP0:%.*]] = icmp ult i64 [[N:%.*]], [[M:%.*]]
+; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i64 [[IV]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    call void @side_effect()
+; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[EXIT_LOOPEXIT]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp0 = icmp ult i64 %n, %m
+  br i1 %cmp0, label %loop, label %exit
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
+  %iv.next = add i64 %iv, 1
+  %cmp1 = icmp ult i64 %iv, %n
+  br i1 %cmp1, label %latch, label %exit
+latch:
+  call void @side_effect()
+  %cmp2 = icmp ult i64 %iv, %m
+  br i1 %cmp2, label %loop, label %exit
+exit:
+  ret void
+}
+
+define void @ugt(i64 %n, i64 %m) {
+; CHECK-LABEL: @ugt(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i64 [[N:%.*]], [[M:%.*]]
+; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
+; CHECK-NEXT:    br i1 true, label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    call void @side_effect()
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[IV]], [[M]]
+; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp0 = icmp ugt i64 %n, %m
+  br i1 %cmp0, label %loop, label %exit
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
+  %iv.next = add i64 %iv, 1
+  %cmp1 = icmp ult i64 %iv, %n
+  br i1 %cmp1, label %latch, label %exit
+latch:
+  call void @side_effect()
+  %cmp2 = icmp ult i64 %iv, %m
+  br i1 %cmp2, label %loop, label %exit
+exit:
+  ret void
+}
+
+define void @ule(i64 %n, i64 %m) {
+; CHECK-LABEL: @ule(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP0:%.*]] = icmp ule i64 [[N:%.*]], [[M:%.*]]
+; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i64 [[IV]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    call void @side_effect()
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[IV]], [[M]]
+; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp0 = icmp ule i64 %n, %m
+  br i1 %cmp0, label %loop, label %exit
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
+  %iv.next = add i64 %iv, 1
+  %cmp1 = icmp ult i64 %iv, %n
+  br i1 %cmp1, label %latch, label %exit
+latch:
+  call void @side_effect()
+  %cmp2 = icmp ult i64 %iv, %m
+  br i1 %cmp2, label %loop, label %exit
+exit:
+  ret void
+}
+
+define void @uge(i64 %n, i64 %m) {
+; CHECK-LABEL: @uge(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP0:%.*]] = icmp uge i64 [[N:%.*]], [[M:%.*]]
+; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i64 [[IV]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    call void @side_effect()
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[IV]], [[M]]
+; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp0 = icmp uge i64 %n, %m
+  br i1 %cmp0, label %loop, label %exit
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
+  %iv.next = add i64 %iv, 1
+  %cmp1 = icmp ult i64 %iv, %n
+  br i1 %cmp1, label %latch, label %exit
+latch:
+  call void @side_effect()
+  %cmp2 = icmp ult i64 %iv, %m
+  br i1 %cmp2, label %loop, label %exit
+exit:
+  ret void
+}
+
+
+define void @ult_const_max(i64 %n) {
+; CHECK-LABEL: @ult_const_max(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP0:%.*]] = icmp ult i64 [[N:%.*]], 20
+; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    br i1 true, label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    call void @side_effect()
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[IV]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp0 = icmp ult i64 %n, 20
+  br i1 %cmp0, label %loop, label %exit
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
+  %iv.next = add i64 %iv, 1
+  %udiv = udiv i64 %iv, 10
+  %cmp1 = icmp ult i64 %udiv, 2
+  br i1 %cmp1, label %latch, label %exit
+latch:
+  call void @side_effect()
+  %cmp2 = icmp ult i64 %iv, %n
+  br i1 %cmp2, label %loop, label %exit
+exit:
+  ret void
+}
+
+
+declare void @side_effect()