[IndVars] Remove monotonic checks with unknown exit count

[mkazantsev]

Summary

Even if the exact exit count is unknown, we can still prove that this exit will not be taken.
If we can prove that the predicate is monotonic, fulfilled on first & last iteration, and no
overflow happened in between, then the check can be removed.

[mkazantsev]

Planning to move this code to other place and merge with D87834

[mkazantsev]

Moved code to proper place.

[lebedev.ri]

This looks reasonable to me, but i'd prefer to defer to other reviewers.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2375

// Value of IV on *suggested* max possible last iteration.?

2386–2391

This seems fragile, i'd suggest

ICmpInst::Predicate NoOverflowPred = CmpInst::isSigned(Pred) ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
if (Step == MinusOne)
  NoOverflowPred = CmpInst::getSwappedPredicate(NoOverflowPred);

[mkazantsev]

Addressed comments & some minor refactoring.

[lebedev.ri]

IOW is this missing some precondition (potentially just a comment) that in signed case, the trip count is a positive number?

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2351–2364

It might be good to hoist that into some ICmp method,
this is at least the second such code block.

2388–2398

I agree about unsigned case:

----------------------------------------
define i1 @src(i32 %base, i32 %num) {
%0:
  %t0 = uadd_overflow {i32, i1, i24} %base, %num
  %t1 = extractvalue {i32, i1, i24} %t0, 1
  %t2 = xor i1 %t1, 1
  ret i1 %t2
}
=>
define i1 @tgt(i32 %base, i32 %num) {
%0:
  %t0 = add i32 %base, %num
  %t1 = icmp ule i32 %base, %t0
  ret i1 %t1
}
Transformation seems to be correct!

but signed case seems to be different:

----------------------------------------
define i1 @src(i32 %base, i32 %num) {
%0:
  %t0 = sadd_overflow {i32, i1, i24} %base, %num
  %t1 = extractvalue {i32, i1, i24} %t0, 1
  %t2 = xor i1 %t1, 1
  ret i1 %t2
}
=>
define i1 @tgt(i32 %base, i32 %num) {
%0:
  %t0 = add i32 %base, %num
  %t1 = icmp sle i32 %base, %t0
  ret i1 %t1
}
Transformation doesn't verify!
ERROR: Value mismatch

Example:
i32 %base = #x34600ff0 (878710768)
i32 %num = #xcba01020 (3416264736, -878702560)

Source:
{i32, i1, i24} %t0 = { #x00002010 (8208), #x0 (0), poison }
i1 %t1 = #x0 (0)
i1 %t2 = #x1 (1)

Target:
i32 %t0 = #x00002010 (8208)
i1 %t1 = #x0 (0)
Source value: #x1 (1)
Target value: #x0 (0)

----------------------------------------
define i1 @src(i32 %base, i31 %num_) {
%0:
  %num = zext i31 %num_ to i32
  %t0 = sadd_overflow {i32, i1, i24} %base, %num
  %t1 = extractvalue {i32, i1, i24} %t0, 1
  %t2 = xor i1 %t1, 1
  ret i1 %t2
}
=>
define i1 @tgt(i32 %base, i31 %num_) {
%0:
  %num = zext i31 %num_ to i32
  %t0 = add i32 %base, %num
  %t1 = icmp sle i32 %base, %t0
  ret i1 %t1
}
Transformation seems to be correct!

[reames]

llvm/include/llvm/Analysis/ScalarEvolution.h

935

For the context, use an instruction even if you don't actually need it yet. We made this mistake in LVI and spent years digging out. The problem with using the BB is you have to be very careful in documenting where in said block the fact holds.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2351

It really looks like at least part of this logic can be replaced with SE->isMonotonicPredicate(LHSS, Pred, IncreasingOut). In particular, I think that covers all your tricky overflow logic and does so more generally.

If I'm right about that, you can also generalize this. Consider:

• If is monotonic, and proven start == proven end (without caring which direction proved), the condition is invariant for the iterations executed.

This is starting to look a lot like it might belong in isLoopInvariantPredicate. It seems to be a generalization of the logic there.

[mkazantsev]

Hi Roman,

I'm not sure I understand your counter-example for signed. In case of base = 878710768, num= -878702560 (aka 3416264736), step = 1, it should be last = base + step * num = 8208, and the transform should not happen because of NoOverflowPred which is base <=s last.

In case of base = 878710768, num= -878702560 (aka 3416264736), step = -1, it should be last = base + step * num = 1 757 413 328, and again the transform should not happen because of NoOverflowPred which is base >=s last (for step = -1).

The condition with NoOverflowPred is actually the more general version of "number of iterations is positive" that you mentioned.

For example, for base = - 2^31 and num = -100 (aka 2^32 - 100) it is OK to make such transform because iterating from SINT_MIN with this number of iterations does not overflow: last = -2^31 + 2^32 - 100 = 2^31 - 100 (positive).

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolution.h

935

Just curious: what kind of mistake it was?

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2351

It does not. It requires proved nsw/nuw flags. We are OK if the last iteration actually does overflow, but in this case we exit the loop before our check.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2351–2364

isRelational seems to be what we need.

[mkazantsev]

1. Replaced context API with instruction (added corresponding TODO);
2. Simplified predicate check.

[reames]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2351

Is it fair to say that what you're implementing is isMonotonicPredicate(Pred, RHS, MaxIteration)? And that you're specifically focused on exploiting the overflow outside of MaxIteration?

If so, this seems like it might come down to a missing overflow flag on the SCEV. SCEVs overflow flags hold for all current uses, so as long as the overflow value isn't used on the last iteration (or outside the loop), SCEV should be able to infer the lack of overflow.

[mkazantsev]

Maybe this code should be moved into SCEV's function that does something similar (but more restrictively).

[mkazantsev]

Factored out most logic into SCEV.

[mkazantsev]

Ping.

[mkazantsev]

Ping.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

9288

IIUC there a reason we cannot use isMonotonicPredicate here is that it is not using the information from MaxIter (which is the max exit count in the case of this patch)? Would it be possible move the logic to use the max exit count of a loop into isMonotonicPredicate?

[apilipenko]

Still digging through the main logic. In the meantime see some minor comments inline.

llvm/include/llvm/Analysis/ScalarEvolution.h

969

Style. Suggest to drop At from the name so as to make it more readable isLoopInvariantPredicateDuringFirstIterations.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2335

Looks like a separable enhancement.

2429–2442

Separable refactoring?

[apilipenko]

llvm/lib/Analysis/ScalarEvolution.cpp

9284

Do we actually need to pass MaxIter? We already have the loop, we can check the max iterations for the loop inside of this function.

If we make this interface change, isLoopInvariantPredicateAtDuringFirstIterations interface becomes very similar to isLoopInvariantPredicate. At that point we can add context to isLoopInvariantPredicate and implement the proposed logic in isLoopInvariantPredicate.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9288

The main reason is that isMonotonicPredicate checks no-wrap flag, and we are interested in unsigned range for IV with negative step. Formally, it overflows on every iteration. So isMonotonicPredicate cannot deal with it.

Theoretically we could expand isMonotonicPredicate, making it smarter and able to handle this. But it is used in 3 different transforms, and such change would have unpredictable impact. So I'd rather do it separately.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9284

We do not necessarily want to evaluate the last iteration. In some cases (and this is in follow-up patches), if we prove that there are two exits with same iteration count, the 2nd one will not execute on the last iteration. So we might want to check the condition for pre-last iteration for it.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9284

Besides, before this code was written, max iter computation was a costly operation (I've added caching for it just today). But per argument above, I don't think we want to compute it inside.

I agree that isLoopInvariantPredicate might be remade into calling this function with last iteration. Let's not to API changes in the patches that are not about API changes. It can go separately after this work has concluded.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2429–2442

No. The old version does not use the max iter. The only difference of the new code is that it does.

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolution.h

969

No. At here means that this predicate is not true everywhere, but at specific point.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2335

Will do.

[apilipenko]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2429–2442

You can still extract the lambda and add a new parameter in the functional patch.

[mkazantsev]

Updated function's name, removing At and adding the notion of the fact that it's not just a random predicate, but an exit condition.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2351

It's more complex than that. We can't set nuw on SCEVAddRec with step -1. But we still can prove the condition {len,+,-1} <= u len is monotonic.

[mkazantsev]

Allright...

[apilipenko]

Accepting this change to unblock the progress.

Please, follow up with commoning this with the existing monotonic predicate functionality.

[mkazantsev]

I plan expanding logic of this code to handle more cases. Once all planned enhancements are made, we can think about merging it with isMonotonicPredicate.

[teemperor]

This breaks stage2 compilation on Green Dragon:

/Users/buildslave/jenkins/workspace/lldb-cmake/host-compiler/bin/clang++  -DGTEST_HAS_RTTI=0 -D_DEBUG -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/Target/AArch64 -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/lib/Target/AArch64 -Iinclude -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/include -Wdocumentation -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -fmodules -fmodules-cache-path=/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/module.cache -fcxx-modules -Xclang -fmodules-local-submodule-visibility -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -fdiagnostics-color -O3  -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.15.sdk    -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -MD -MT lib/Target/AArch64/CMakeFiles/LLVMAArch64CodeGen.dir/GISel/AArch64RegisterBankInfo.cpp.o -MF lib/Target/AArch64/CMakeFiles/LLVMAArch64CodeGen.dir/GISel/AArch64RegisterBankInfo.cpp.o.d -o lib/Target/AArch64/CMakeFiles/LLVMAArch64CodeGen.dir/GISel/AArch64RegisterBankInfo.cpp.o -c /Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/lib/Target/AArch64/GISel/AArch64RegisterBankInfo.cpp
Assertion failed: (WeightSum <= UINT32_MAX && "Expected weights to scale down to 32 bits"), function calcMetadataWeights, file /Users/buildslave/jenkins/workspace/clang-stage1-RA/llvm-project/llvm/lib/Analysis/BranchProbabilityInfo.cpp, line 493.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /Users/buildslave/jenkins/workspace/lldb-cmake/host-compiler/bin/clang++ -DGTEST_HAS_RTTI=0 -D_DEBUG -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/Target/AArch64 -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/lib/Target/AArch64 -Iinclude -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/include -Wdocumentation -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -fmodules -fmodules-cache-path=/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/module.cache -fcxx-modules -Xclang -fmodules-local-submodule-visibility -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -fdiagnostics-color -O3 -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.15.sdk -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -MD -MT lib/Target/AArch64/CMakeFiles/LLVMAArch64CodeGen.dir/GISel/AArch64RegisterBankInfo.cpp.o -MF lib/Target/AArch64/CMakeFiles/LLVMAArch64CodeGen.dir/GISel/AArch64RegisterBankInfo.cpp.o.d -o lib/Target/AArch64/CMakeFiles/LLVMAArch64CodeGen.dir/GISel/AArch64RegisterBankInfo.cpp.o -c /Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/lib/Target/AArch64/GISel/AArch64RegisterBankInfo.cpp 
1.	<eof> parser at end of file
2.	Per-module optimization passes
3.	Running pass 'CallGraph Pass Manager' on module '/Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/lib/Target/AArch64/GISel/AArch64RegisterBankInfo.cpp'.
4.	Running pass 'Branch Probability Analysis' on function '@"_ZZN4llvm23AArch64RegisterBankInfoC1ERKNS_18TargetRegisterInfoEENK3$_2clEv"'
Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
0  clang++                  0x000000010f1b5a6b llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 43
1  clang++                  0x000000010f1b4a95 llvm::sys::RunSignalHandlers() + 85
2  clang++                  0x000000010f1b51f2 llvm::sys::CleanupOnSignal(unsigned long) + 210
3  clang++                  0x000000010f0fdb0a (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) + 106
4  clang++                  0x000000010f0fdc87 CrashRecoverySignalHandler(int) + 135
5  libsystem_platform.dylib 0x00007fff6b6575fd _sigtramp + 29
6  libsystem_platform.dylib 0x00000001205ae380 _sigtramp + 18446603343552146848
7  libsystem_c.dylib        0x00007fff6b529808 abort + 120
8  libsystem_c.dylib        0x00007fff6b528ac6 err + 0
9  clang++                  0x0000000111de3973 llvm::BranchProbabilityInfo::calcMetadataWeights(llvm::BasicBlock const*) (.cold.17) + 35
10 clang++                  0x000000010e2cdafa llvm::BranchProbabilityInfo::calcMetadataWeights(llvm::BasicBlock const*) + 2186
11 clang++                  0x000000010e2d0b64 llvm::BranchProbabilityInfo::calculate(llvm::Function const&, llvm::LoopInfo const&, llvm::TargetLibraryInfo const*, llvm::PostDominatorTree*) + 1316
12 clang++                  0x000000010e2d11e2 llvm::BranchProbabilityInfoWrapperPass::runOnFunction(llvm::Function&) + 322
13 clang++                  0x000000010ea0f1d4 llvm::FPPassManager::runOnFunction(llvm::Function&) + 1092
14 clang++                  0x000000010e2fc3e4 (anonymous namespace)::CGPassManager::runOnModule(llvm::Module&) + 1588
15 clang++                  0x000000010ea0f7ca llvm::legacy::PassManagerImpl::run(llvm::Module&) + 986
16 clang++                  0x000000010f424844 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::__1::unique_ptr<llvm::raw_pwrite_stream, std::__1::default_delete<llvm::raw_pwrite_stream> >) + 12820
17 clang++                  0x000000010f6ee76a clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) + 1130
18 clang++                  0x00000001108bee63 clang::ParseAST(clang::Sema&, bool, bool) + 643
19 clang++                  0x000000010f9d5064 clang::FrontendAction::Execute() + 84
20 clang++                  0x000000010f977b83 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) + 2275
21 clang++                  0x000000010fa4d9d7 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) + 1639
22 clang++                  0x000000010d202d35 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) + 2309
23 clang++                  0x000000010d200999 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) + 377
24 clang++                  0x000000010f811687 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >*, bool*) const::$_1>(long) + 23
25 clang++                  0x000000010f0fda54 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) + 228
26 clang++                  0x000000010f810d3d clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >*, bool*) const + 429
27 clang++                  0x000000010f7e39cd clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&) const + 221
28 clang++                  0x000000010f7e3eed clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::__1::pair<int, clang::driver::Command const*> >&) const + 125
29 clang++                  0x000000010f7fa9cc clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::__1::pair<int, clang::driver::Command const*> >&) + 204
30 clang++                  0x000000010d2000c5 main + 10517
31 libdyld.dylib            0x00007fff6b45acc9 start + 1
32 libdyld.dylib            0x0000000000000034 start + 18446603338716435308
clang-12: error: clang frontend command failed with exit code 134 (use -v to see invocation)
clang version 12.0.0 (https://github.com/llvm/llvm-project.git 673f2f702b03be8c003889cbb5923e111c3e24d0)
Target: x86_64-apple-darwin19.5.0
Thread model: posix
InstalledDir: /Users/buildslave/jenkins/workspace/lldb-cmake/host-compiler/bin
clang-12: note: diagnostic msg: 
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-12: note: diagnostic msg: /var/folders/09/r4vw4v8n5kb67jl66zvlbljw0000gn/T/AArch64RegisterBankInfo-189543.cpp
clang-12: note: diagnostic msg: /var/folders/09/r4vw4v8n5kb67jl66zvlbljw0000gn/T/AArch64RegisterBankInfo-189543.cache
clang-12: note: diagnostic msg: /var/folders/09/r4vw4v8n5kb67jl66zvlbljw0000gn/T/AArch64RegisterBankInfo-189543.sh
clang-12: note: diagnostic msg: Crash backtrace is located in
clang-12: note: diagnostic msg: /Users/buildslave/Library/Logs/DiagnosticReports/clang-12_<YYYY-MM-DD-HHMMSS>_<hostname>.crash
clang-12: note: diagnostic msg: (choose the .crash file that corresponds to your crash)
clang-12: note: diagnostic msg:

[teemperor]

I uploaded a reproducer for the crash here: https://teemperor.de/pub/clang-crash-D87832-repro.zip

I'll revert this in the meantime to get the bots running again.

[teemperor]

Reverted this and a0d84d80315d0c725b5efcd889928bad1171ba56 (as it seems to be a follow-up cleanup patch) in e038b60d9169733367393f733058f0ff23c28d3f

[mkazantsev]

This assert is highly confusing. I'll investigate.

[mkazantsev]

I was able to successfully build clang stage 2. The attached repro doesn't reproduce the failure either.

[mkazantsev]

The failure doesn't reproruce and looks related to this story:

commit 2a4e704c92e8ec3d9217a7333368ea53cf3a583f
Author: Nico Weber <[e-mail]>
Date:   Tue Oct 27 09:18:42 2020 -0400

    Revert "Use uint64_t for branch weights instead of uint32_t"

    This reverts commit e5766f25c62c185632e3a75bf45b313eadab774b.
    Makes clang assert when building Chromium, see https://crbug.com/1142813
    for a repro.

commit e5766f25c62c185632e3a75bf45b313eadab774b
Author: Arthur Eubanks <[e-mail]>
Date:   Wed Sep 30 12:11:46 2020 -0700

    Use uint64_t for branch weights instead of uint32_t

    CallInst::updateProfWeight() creates branch_weights with i64 instead of i32.
    To be more consistent everywhere and remove lots of casts from uint64_t
    to uint32_t, use i64 for branch_weights.

    Reviewed By: davidxl

    Differential Revision: https://reviews.llvm.org/D88609

I am returning the change as the revert was erroneous.

[mkazantsev]

@teemperor please make sure you're reverting the patch that actually causes the failure...

[teemperor]

In D87832#2358714, @mkazantsev wrote:

@teemperor please make sure you're reverting the patch that actually causes the failure...

Apologies, not sure how my bisecting found your commit...

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// Test if the given expression is known to satisfy the condition described
   /// by Pred, LHS, and RHS.
   bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
                         const SCEV *RHS);
 
   /// Test if the given expression is known to satisfy the condition described
   /// by Pred, LHS, and RHS in the given Context.
   bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS,
                         const SCEV *RHS, const Instruction *Context);
 
   /// Test if the condition described by Pred, LHS, RHS is known to be true on
   /// every iteration of the loop of the recurrency LHS.
   bool isKnownOnEveryIteration(ICmpInst::Predicate Pred,
                                const SCEVAddRecExpr *LHS, const SCEV *RHS);
 
   /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
   /// is monotonically increasing or decreasing.  In the former case set
public:
   /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the
   /// loop invariant form of LHS `Pred` RHS.
   bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
                                 const SCEV *RHS, const Loop *L,
                                 ICmpInst::Predicate &InvariantPred,
                                 const SCEV *&InvariantLHS,
                                 const SCEV *&InvariantRHS);
 
+  /// Return true if the result of the predicate LHS `Pred` RHS is loop
+  /// invariant with respect to L at given Context during at least first
+  /// MaxIter iterations.  Set InvariantPred, InvariantLHS and InvariantLHS so
+  /// that InvariantLHS `InvariantPred` InvariantRHS is the loop invariant form
+  /// of LHS `Pred` RHS. The predicate should be the loop's exit condition.
+  bool isLoopInvariantExitCondDuringFirstIterations(
+      ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
+      const Instruction *Context, const SCEV *MaxIter,
+      ICmpInst::Predicate &InvariantPred, const SCEV *&InvariantLHS,
+      const SCEV *&InvariantRHS);
+
   /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
   /// iff any changes were made. If the operands are provably equal or
   /// unequal, LHS and RHS are set to the same value and Pred is set to either
   /// ICMP_EQ or ICMP_NE.
   bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
                             const SCEV *&RHS, unsigned Depth = 0);
 
   /// Return the "disposition" of the given SCEV with respect to the given

llvm/lib/Analysis/ScalarEvolution.cpp

if (!isLoopBackedgeGuardedByCond(L, P, LHS, RHS))
     return false;
 
   InvariantPred = Pred;
   InvariantLHS = ArLHS->getStart();
   InvariantRHS = RHS;
   return true;
 }
 
+bool ScalarEvolution::isLoopInvariantExitCondDuringFirstIterations(
+    ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
+    const Instruction *Context, const SCEV *MaxIter,
+    ICmpInst::Predicate &InvariantPred, const SCEV *&InvariantLHS,
+    const SCEV *&InvariantRHS) {
+  // Try to prove the following set of facts:
+  // - The predicate is monotonic.
+  // - If the check does not fail on the 1st iteration:
+  //   - No overflow will happen during first MaxIter iterations;
+  //   - It will not fail on the MaxIter'th iteration.
+  // If the check does fail on the 1st iteration, we leave the loop and no
+  // other checks matter.
+
+  // If there is a loop-invariant, force it into the RHS, otherwise bail out.
+  if (!isLoopInvariant(RHS, L)) {
+    if (!isLoopInvariant(LHS, L))
+      return false;
+
+    std::swap(LHS, RHS);
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+
+  auto *AR = dyn_cast<SCEVAddRecExpr>(LHS);
+  // TODO: Lift affinity limitation in the future.
+  if (!AR || AR->getLoop() != L || !AR->isAffine())
+    return false;
+
+  // The predicate must be relational (i.e. <, <=, >=, >).
+  if (!ICmpInst::isRelational(Pred))
+    return false;
+
+  // TODO: Support steps other than +/- 1.
+  const SCEV *Step = AR->getOperand(1);
+  auto *One = getOne(Step->getType());
+  auto *MinusOne = getNegativeSCEV(One);
+  if (Step != One && Step != MinusOne)
+    return false;
+
+  // Type mismatch here means that MaxIter is potentially larger than max
+  // unsigned value in start type, which mean we cannot prove no wrap for the
+  // indvar.
+  if (AR->getType() != MaxIter->getType())
+    return false;
+
+  // Value of IV on suggested last iteration.
+  const SCEV *Last = AR->evaluateAtIteration(MaxIter, *this);
+  // Does it still meet the requirement?
+  if (!isKnownPredicateAt(Pred, Last, RHS, Context))
+    return false;
+  // Because step is +/- 1 and MaxIter has same type as Start (i.e. it does
+  // not exceed max unsigned value of this type), this effectively proves
+  // that there is no wrap during the iteration. To prove that there is no
+  // signed/unsigned wrap, we need to check that
+  // Start <= Last for step = 1 or Start >= Last for step = -1.
+  ICmpInst::Predicate NoOverflowPred =
+      CmpInst::isSigned(Pred) ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
+  if (Step == MinusOne)
+    NoOverflowPred = CmpInst::getSwappedPredicate(NoOverflowPred);
+  const SCEV *Start = AR->getStart();
+  if (!isKnownPredicateAt(NoOverflowPred, Start, Last, Context))
+    return false;
+
+  // Everything is fine.
+  InvariantPred = Pred;
+  InvariantLHS = Start;
+  InvariantRHS = RHS;
+  return true;
+}
+
 bool ScalarEvolution::isKnownPredicateViaConstantRanges(
     ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {
   if (HasSameValue(LHS, RHS))
     return ICmpInst::isTrueWhenEqual(Pred);
 
   // This code is split out from isKnownPredicate because it is called from
   // within isLoopEntryGuardedByCond.
 

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

while (I != Preheader->begin()) {
     if (Done) break;
     InsertPt = ToMove->getIterator();
   }
 
   return MadeAnyChanges;
 }
 
 // Returns true if the condition of \p BI being checked is invariant and can be
-// proved to be trivially true.
+// proved to be trivially true during at least first \p MaxIter iterations.
 static bool isTrivialCond(const Loop *L, BranchInst *BI, ScalarEvolution *SE,
-                          bool ProvingLoopExit) {
+                          bool ProvingLoopExit, const SCEV *MaxIter) {
   ICmpInst::Predicate Pred;
   Value *LHS, *RHS;
   using namespace PatternMatch;
   BasicBlock *TrueSucc, *FalseSucc;
   if (!match(BI, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)),
                       m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc))))
     return false;
 
   assert((L->contains(TrueSucc) != L->contains(FalseSucc)) &&
          "Not a loop exit!");
 
   // 'LHS pred RHS' should now mean that we stay in loop.
   if (L->contains(FalseSucc))
     Pred = CmpInst::getInversePredicate(Pred);
 
   // If we are proving loop exit, invert the predicate.
   if (ProvingLoopExit)
     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?
   if (SE->isKnownPredicateAt(Pred, LHSS, RHSS, BI))
     return true;
 
+  if (ProvingLoopExit)
+    return false;
+
+  ICmpInst::Predicate InvariantPred;
+  const SCEV *InvariantLHS, *InvariantRHS;
+
+  // Check if there is a loop-invariant predicate equivalent to our check.
+  if (!SE->isLoopInvariantExitCondDuringFirstIterations(
+           Pred, LHSS, RHSS, L, BI, MaxIter, InvariantPred, InvariantLHS,
+           InvariantRHS))
     return false;
+
+  // Can we prove it to be trivially true?
+  return SE->isKnownPredicateAt(InvariantPred, InvariantLHS, InvariantRHS, BI);
 }
 
 bool IndVarSimplify::optimizeLoopExits(Loop *L, SCEVExpander &Rewriter) {
   SmallVector<BasicBlock*, 16> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   // Remove all exits which aren't both rewriteable and execute on every
   // iteration.
   auto NewEnd = llvm::remove_if(ExitingBlocks, [&](BasicBlock *ExitingBB) {
     // 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)
       return true;
 
     // Can't rewrite non-branch yet.
     BranchInst *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
     if (!BI)
       return true;
 
     // If already constant, nothing to do.
     if (isa<Constant>(BI->getCondition()))
       return true;
 
     // Likewise, the loop latch must be dominated by the exiting BB.
     if (!DT->dominates(ExitingBB, L->getLoopLatch()))
       return true;
 
     return false;
   });
   ExitingBlocks.erase(NewEnd, ExitingBlocks.end());
 
   if (ExitingBlocks.empty())
     return false;
 
   // Get a symbolic upper bound on the loop backedge taken count.
   const SCEV *MaxExitCount = SE->getSymbolicMaxBackedgeTakenCount(L);
   if (isa<SCEVCouldNotCompute>(MaxExitCount))
     return false;
 
   // Visit our exit blocks in order of dominance. We know from the fact that
   // all exits must dominate the latch, so there is a total dominance order
   // between them.
   llvm::sort(ExitingBlocks, [&](BasicBlock *A, BasicBlock *B) {
                // std::sort sorts in ascending order, so we want the inverse of
                // the normal dominance relation.
                if (A == B) return false;
                if (DT->properlyDominates(A, B))
                  return true;
                else {
                  assert(DT->properlyDominates(B, A) &&
                         "expected total dominance order!");
                  return false;
                }
   });
if (OldCond->use_empty())
       DeadInsts.emplace_back(OldCond);
   };
 
   bool Changed = false;
   SmallSet<const SCEV*, 8> DominatingExitCounts;
   for (BasicBlock *ExitingBB : ExitingBlocks) {
     const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
     if (isa<SCEVCouldNotCompute>(ExitCount)) {
       // Okay, we do not know the exit count here. Can we at least prove that it
       // will remain the same within iteration space?
       auto *BI = cast<BranchInst>(ExitingBB->getTerminator());
-      auto OptimizeCond = [&](bool Inverted) {
-        if (isTrivialCond(L, BI, SE, Inverted)) {
+      auto OptimizeCond = [&](bool Inverted, const SCEV *MaxIter) {
+        if (isTrivialCond(L, BI, SE, Inverted, MaxIter)) {
           FoldExit(ExitingBB, Inverted);
           return true;
         }
         return false;
       };
-      if (OptimizeCond(false) || OptimizeCond(true))
+      if (OptimizeCond(false, MaxExitCount) ||
+          OptimizeCond(true, MaxExitCount))
         Changed = true;
       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()) {

llvm/test/Transforms/IndVarSimplify/monotonic_checks.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -indvars -S < %s | FileCheck %s
 ; RUN: opt -passes=indvars -S < %s | FileCheck %s
 
 ; Monotonic decrementing iv. we should be able to prove that %iv.next <s len
 ; basing on its nsw and the fact that its starting value <s len.
 define i32 @test_01(i32* %p) {
 ; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG0:!range !.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], -1
-; CHECK-NEXT:    [[RC:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]]
-; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;

 define i32 @test_02(i32* %p) {
 ; CHECK-LABEL: @test_02(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG1:!range !.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[RC:%.*]] = icmp sgt i32 [[IV_NEXT]], [[LEN]]
-; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;

 define i32 @test_03(i32* %p) {
 ; CHECK-LABEL: @test_03(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG2:!range !.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
-; CHECK-NEXT:    [[RC:%.*]] = icmp ugt i32 [[IV_NEXT]], [[LEN]]
-; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;

 define i32 @test_04(i32* %p) {
 ; CHECK-LABEL: @test_04(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG2]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], -1
-; CHECK-NEXT:    [[RC:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]]
-; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;

llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll

 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG0]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
 ; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
-; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]]
-; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, i32* [[P]], i32 [[IV]]
 ; CHECK-NEXT:    [[EL:%.*]] = load i32, i32* [[EL_PTR]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       fail: