[LICM] Simplify (X < A && X < B) into (X < MIN(A, B)) if MIN(A, B) is loop-invariant

[mkazantsev]

Summary

We don't do this transform in InstCombine in general case for arbitrary values, because cost of
AND and 2 ICMP's isn't higher than of MIN and ICMP. However, LICM also has a notion
about the loop structure. This transform becomes profitable if A and B are loop-invariant and
X is not: by doing this, we can compute min outside the loop.

[nikic]

My high level question would be whether this should be part of LICM. Basically, what we're doing here is a reassociation transform to expose a loop invariant, which can then be hoisted. This recently also came up in other contexts, e.g. D143631.

It looks like currently LoopInstSimplify is scheduled before LICM, so the operands might not have been hoisted yet. Having LICM rewrite expressions to enable hoisting would make sure that operands are hoisted first.

[mkazantsev]

In D143726#4128119, @nikic wrote:

My high level question would be whether this should be part of LICM. Basically, what we're doing here is a reassociation transform to expose a loop invariant, which can then be hoisted. This recently also came up in other contexts, e.g. D143631.

It looks like currently LoopInstSimplify is scheduled before LICM, so the operands might not have been hoisted yet. Having LICM rewrite expressions to enable hoisting would make sure that operands are hoisted first.

Making this in LICM also makes sense. We have a different pipeline, so in our case this happens after LICM (and other passes) as a cleanup.

[mkazantsev]

Moved to LICM.

[mkazantsev]

Ping

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

2426

This transform is not legal for logical and/or. Counter-proof: https://alive2.llvm.org/ce/z/7sVXdy Please limit this to just m_Or/m_And and add a test that logical case is not folded.

2430–2432

2441

Personally, I'd include swapping the invariant to the right in the initial patch. Otherwise the transform is fragile.

2469

ICmpInst::Predicate

2472

I think you need takeName() to avoid the unnecesary 1 suffix.

llvm/test/Transforms/LICM/min_max.ll

482–1210

Some missing negative tests:

• Equality predicate
• Multi-use comparison
• Logical and/or (mentioned above)
• Swapped operands (but better implement support...)
• One icmp without invariant ops
• Mismatched predicates (e.g. one ult one ule)
• No common variant operand

[nikic]

Note that there are two codegen tests that need to be updated.

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

2426

Good catch! Thanks for pointing out.

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

2426

Logican and can be supported if RHS's are noundef. But I'll make it in a follow-up.

[mkazantsev]

llvm/test/Transforms/LICM/min_max.ll

482–1210

Actually some of them can be optimized, I'll add both positive and negative tests for these situations.

[mkazantsev]

Addressed comments & rebased on top of new tests.

[mkazantsev]

Removed some stray semicolons.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/LICM.cpp

2426

If RHS is undef, logical and will be converted to bitwise and by InstCombine. If we want to support the transform for logical and, we need to freeze the RHS.

2443

This TODO is already done :)

llvm/test/Transforms/LICM/min_max.ll

882

ule against constant is already canonicalized to ult by InstCombine, no need to handle here.

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

2426

That's an option too.

2443

Indeed.

[nikic]

This showed up as a small compile-time regression: http://llvm-compile-time-tracker.com/compare.php?from=946f8030b58d3d6975369c1b8e047385b86c7ab0&to=6b03ce374e0dc64868b4b6665056dfc3fda0e98f&stat=instructions:u I have no idea why, I don't see anything expensive in this patch.

[nikic]

Looks like fetching the preheader is expensive. Compile-time regression should be addressed by https://github.com/llvm/llvm-project/commit/a7322a2171e99fe9c465c3e13c49563b19402ae0.

[abrachet]

See assertion failures on this patch. https://storage.googleapis.com/fuchsia-artifacts/builds/8787007186219892481/build-debug/clang-crashreports/adler32-5bb726.c and https://storage.googleapis.com/fuchsia-artifacts/builds/8787007186219892481/build-debug/clang-crashreports/adler32-5bb726.sh for the reproducer. I tested locally and the failure goes away after reverting this change. Please take a look or revert if the fix will take a while.

clang: /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/DerivedTypes.h:725: Type *llvm::Type::getWithNewBitWidth(unsigned int) const: Assertion `isIntOrIntVectorTy() && "Original type expected to be a vector of integers or a scalar integer."' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: ./bin/clang -cc1 -triple aarch64-unknown-fuchsia -emit-obj -massembler-fatal-warnings -disable-free -clear-ast-before-backend -main-file-name adler32.c -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=non-leaf -ffp-contract=on -fno-rounding-math -mconstructor-aliases -ffreestanding -target-cpu generic -target-feature +v8a -target-feature +crc -target-feature -fp-armv8 -target-feature -crypto -target-feature -neon -target-feature +tpidr-el1 -target-feature -sha2 -target-feature -aes -target-feature +strict-align -target-feature +reserve-x20 -target-feature +fix-cortex-a53-835769 -target-abi aapcs -tune-cpu generic -Wunaligned-access -mllvm -treat-scalable-fixed-error-as-warning -debug-info-kind=constructor -dwarf-version=4 -debugger-tuning=gdb -mllvm -crash-diagnostics-dir=clang-crashreports -ffunction-sections -fdata-sections -fcoverage-compilation-dir=. -sys-header-deps -D _LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS -D _LIBCPP_ENABLE_THREAD_SAFETY_ANNOTATIONS=1 -D ZX_ASSERT_LEVEL=2 -D LK_DEBUGLEVEL=2 -D WITH_FRAME_POINTERS=1 -O2 -Wno-strict-prototypes -Wall -Wextra -Wconversion -Wextra-semi -Wimplicit-fallthrough -Wnewline-eof -Wstrict-prototypes -Wwrite-strings -Wno-sign-conversion -Wno-unused-parameter -Wnonportable-system-include-path -Wno-type-limits -Wthread-safety -Werror -Wno-error=deprecated-declarations -Wformat=2 -Wmissing-declarations -Wvla -Wshadow -Wno-conversion -Wmissing-prototypes -std=c11 -fconst-strings -fdebug-compilation-dir=. -ferror-limit 19 -fvisibility=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,shadow-call-stack -fsanitize-trap=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 -fno-sanitize-memory-param-retval -fno-sanitize-address-use-odr-indicator -fno-finite-loops -stack-protector 2 -ftrivial-auto-var-init=pattern -fno-signed-char -fgnuc-version=4.2.1 -fsized-deallocation -fcolor-diagnostics -vectorize-loops -vectorize-slp -debug-info-kind=constructor -target-feature +outline-atomics -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -x c adler32-5bb726.c
1.      <eof> parser at end of file
2.      Optimizer
 #0 0x0000564e541cc75d llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Support/Unix/Signals.inc:602:11
 #1 0x0000564e541ccbeb PrintStackTraceSignalHandler(void*) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Support/Unix/Signals.inc:676:1
 #2 0x0000564e541cb116 llvm::sys::RunSignalHandlers() /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Support/Signals.cpp:104:5
 #3 0x0000564e541cd1c5 SignalHandler(int) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Support/Unix/Signals.inc:413:1
 #4 0x00007f3ba1458f90 (/lib/x86_64-linux-gnu/libc.so.6+0x3bf90)
 #5 0x00007f3ba14a7ccc (/lib/x86_64-linux-gnu/libc.so.6+0x8accc)
 #6 0x00007f3ba1458ef2 raise (/lib/x86_64-linux-gnu/libc.so.6+0x3bef2)
 #7 0x00007f3ba1443472 abort (/lib/x86_64-linux-gnu/libc.so.6+0x26472)
 #8 0x00007f3ba1443395 (/lib/x86_64-linux-gnu/libc.so.6+0x26395)
 #9 0x00007f3ba1451df2 (/lib/x86_64-linux-gnu/libc.so.6+0x34df2)
#10 0x0000564e50ae14bd llvm::Type::getWithNewBitWidth(unsigned int) const /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/DerivedTypes.h:0:3
#11 0x0000564e50e5369f llvm::BasicTTIImplBase<llvm::AArch64TTIImpl>::getTypeBasedIntrinsicInstrCost(llvm::IntrinsicCostAttributes const&, llvm::TargetTransformInfo::TargetCostKind) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/CodeGen/BasicTTIImpl.h:1917:13
#12 0x0000564e50e4bd47 llvm::BasicTTIImplBase<llvm::AArch64TTIImpl>::getIntrinsicInstrCost(llvm::IntrinsicCostAttributes const&, llvm::TargetTransformInfo::TargetCostKind) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/CodeGen/BasicTTIImpl.h:1691:21
#13 0x0000564e50e39ca0 llvm::AArch64TTIImpl::getIntrinsicInstrCost(llvm::IntrinsicCostAttributes const&, llvm::TargetTransformInfo::TargetCostKind) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp:522:17
#14 0x0000564e50d420e4 llvm::TargetTransformInfoImplCRTPBase<llvm::AArch64TTIImpl>::getInstructionCost(llvm::User const*, llvm::ArrayRef<llvm::Value const*>, llvm::TargetTransformInfo::TargetCostKind) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/Analysis/TargetTransformInfoImpl.h:1056:25
#15 0x0000564e50d3e881 llvm::TargetTransformInfo::Model<llvm::AArch64TTIImpl>::getInstructionCost(llvm::User const*, llvm::ArrayRef<llvm::Value const*>, llvm::TargetTransformInfo::TargetCostKind) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/Analysis/TargetTransformInfo.h:1988:17
#16 0x0000564e53282dce llvm::TargetTransformInfo::getInstructionCost(llvm::User const*, llvm::ArrayRef<llvm::Value const*>, llvm::TargetTransformInfo::TargetCostKind) const /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Analysis/TargetTransformInfo.cpp:233:35
#17 0x0000564e51125fda llvm::TargetTransformInfo::getInstructionCost(llvm::User const*, llvm::TargetTransformInfo::TargetCostKind) const /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/Analysis/TargetTransformInfo.h:339:12
#18 0x0000564e527a3b19 isFreeInLoop(llvm::Instruction const&, llvm::Loop const*, llvm::TargetTransformInfo const*) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:1352:12
#19 0x0000564e5279c7f5 isNotUsedOrFreeInLoop(llvm::Instruction const&, llvm::Loop const*, llvm::LoopSafetyInfo const*, llvm::TargetTransformInfo*, bool&, bool) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:1385:8
#20 0x0000564e5279c5a9 llvm::sinkRegion(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::Loop*, llvm::MemorySSAUpdater&, llvm::ICFLoopSafetyInfo*, llvm::SinkAndHoistLICMFlags&, llvm::OptimizationRemarkEmitter*, llvm::Loop*) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:594:76
#21 0x0000564e5279b4e1 (anonymous namespace)::LoopInvariantCodeMotion::runOnLoop(llvm::Loop*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::ScalarEvolution*, llvm::MemorySSA*, llvm::OptimizationRemarkEmitter*, bool) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:458:15
#22 0x0000564e5279b1c8 llvm::LICMPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:287:7
#23 0x0000564e504ca9a4 llvm::detail::PassModel<llvm::Loop, llvm::LICMPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:89:17
#24 0x0000564e528160a8 llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Scalar/LoopPassManager.cpp:308:17
#25 0x0000564e504c74f4 llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:89:17
#26 0x0000564e53cd9567 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/PassManager.h:521:33
#27 0x0000564e4b7f0b34 llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:89:17
#28 0x0000564e53cd8305 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/IR/PassManager.cpp:124:38
#29 0x0000564e4b7f73d4 llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:89:17
#30 0x0000564e53cd8887 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/PassManager.h:521:33
#31 0x0000564e4b7d1bfb (anonymous namespace)::EmitAssemblyHelper::RunOptimizationPipeline(clang::BackendAction, std::__2::unique_ptr<llvm::raw_pwrite_stream, std::__2::default_delete<llvm::raw_pwrite_stream>>&, std::__2::unique_ptr<llvm::ToolOutputFile, std::__2::default_delete<llvm::ToolOutputFile>>&) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1042:5
#32 0x0000564e4b7ccf0f (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::__2::unique_ptr<llvm::raw_pwrite_stream, std::__2::default_delete<llvm::raw_pwrite_stream>>) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1099:3
#33 0x0000564e4b7cc434 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>, std::__2::unique_ptr<llvm::raw_pwrite_stream, std::__2::default_delete<llvm::raw_pwrite_stream>>) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1265:17
#34 0x0000564e4bcb8d2a clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:383:7
#35 0x0000564e4db7b1c3 clang::ParseAST(clang::Sema&, bool, bool) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/Parse/ParseAST.cpp:182:12
#36 0x0000564e4bad5ed6 clang::ASTFrontendAction::ExecuteAction() /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1170:1
#37 0x0000564e4bcb4584 clang::CodeGenAction::ExecuteAction() /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:1173:5
#38 0x0000564e4bad591c clang::FrontendAction::Execute() /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1062:7
#39 0x0000564e4ba001c8 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/Frontend/CompilerInstance.cpp:1049:23
#40 0x0000564e4bca42c7 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:264:8
#41 0x0000564e4a90d341 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) /usr/local/google/home/abrachet/Developer/llvm-project/clang/tools/driver/cc1_main.cpp:251:13
#42 0x0000564e4a902442 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) /usr/local/google/home/abrachet/Developer/llvm-project/clang/tools/driver/driver.cpp:363:5
#43 0x0000564e4a9011c7 clang_main(int, char**, llvm::ToolContext const&) /usr/local/google/home/abrachet/Developer/llvm-project/clang/tools/driver/driver.cpp:441:5
#44 0x0000564e4abd5ec3 findTool(int, char**, char const*) /usr/local/google/home/abrachet/Developer/llvm-project/build/tools/llvm-driver/LLVMDriverTools.def:6:1
#45 0x0000564e4abd5ab9 main /usr/local/google/home/abrachet/Developer/llvm-project/llvm/tools/llvm-driver/llvm-driver.cpp:83:35
#46 0x00007f3ba144418a (/lib/x86_64-linux-gnu/libc.so.6+0x2718a)
#47 0x00007f3ba1444245 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x27245)
#48 0x0000564e4a868129 _start (./bin/clang+0x5480129)

llvm/lib/Transforms/Scalar/LICM.cpp

 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/PredIteratorCache.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"

 STATISTIC(NumClonedBranches, "Number of branches cloned");
 STATISTIC(NumSunk, "Number of instructions sunk out of loop");
 STATISTIC(NumHoisted, "Number of instructions hoisted out of loop");
 STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
 STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
 STATISTIC(NumPromotionCandidates, "Number of promotion candidates");
 STATISTIC(NumLoadPromoted, "Number of load-only promotions");
 STATISTIC(NumLoadStorePromoted, "Number of load and store promotions");
+STATISTIC(NumMinMaxHoisted,
+          "Number min/max expressions hoisted out of the loop");
 
 /// Memory promotion is enabled by default.
 static cl::opt<bool>
     DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
                      cl::desc("Disable memory promotion in LICM pass"));
 
 static cl::opt<bool> ControlFlowHoisting(
     "licm-control-flow-hoisting", cl::Hidden, cl::init(false),
static bool isSafeToExecuteUnconditionally(
     OptimizationRemarkEmitter *ORE, const Instruction *CtxI,
     AssumptionCache *AC, bool AllowSpeculation);
 static bool pointerInvalidatedByLoop(MemorySSA *MSSA, MemoryUse *MU,
                                      Loop *CurLoop, Instruction &I,
                                      SinkAndHoistLICMFlags &Flags,
                                      bool InvariantGroup);
 static bool pointerInvalidatedByBlock(BasicBlock &BB, MemorySSA &MSSA,
                                       MemoryUse &MU);
+/// Try to simplify things like (A < INV_1 AND icmp A < INV_2) into (A <
+/// min(INV_1, INV_2)), if INV_1 and INV_2 are both loop invariants and their
+/// minimun can be computed outside of loop, and X is not a loop-invariant.
+static bool hoistMinMax(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
+                        MemorySSAUpdater &MSSAU);
 static Instruction *cloneInstructionInExitBlock(
     Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
     const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU);
 
 static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
                              MemorySSAUpdater &MSSAU);
 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
for (Instruction &I : llvm::make_early_inc_range(*BB)) {
           hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
                 MSSAU, SE, ORE);
           assert(DT->dominates(PN, BB) && "Conditional PHIs not expected");
           Changed = true;
           continue;
         }
       }
 
+      // Optimize complex patterns, such as (x < INV1 && x < INV2), turning them
+      // into (x < min(INV1, INV2)), and hoisting the invariant part of this
+      // expression out of the loop.
+      if (hoistMinMax(I, *CurLoop, *SafetyInfo, MSSAU)) {
+        ++NumMinMaxHoisted;
+        Changed = true;
+        continue;
+      }
+
       // Remember possibly hoistable branches so we can actually hoist them
       // later if needed.
       if (BranchInst *BI = dyn_cast<BranchInst>(&I))
         CFH.registerPossiblyHoistableBranch(BI);
     }
   }
 
   // If we hoisted instructions to a conditional block they may not dominate
bool pointerInvalidatedByBlock(BasicBlock &BB, MemorySSA &MSSA, MemoryUse &MU) {
   if (const auto *Accesses = MSSA.getBlockDefs(&BB))
     for (const auto &MA : *Accesses)
       if (const auto *MD = dyn_cast<MemoryDef>(&MA))
         if (MU.getBlock() != MD->getBlock() || !MSSA.locallyDominates(MD, &MU))
           return true;
   return false;
 }
 
+static bool hoistMinMax(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
+                        MemorySSAUpdater &MSSAU) {
+  auto *Preheader = L.getLoopPreheader();
+  assert(Preheader && "Loop is not in simplify form?");
+  bool Inverse = false;
+  using namespace PatternMatch;
+  Value *Cond1, *Cond2;
+  if (match(&I, m_Or(m_Value(Cond1), m_Value(Cond2))))
+    Inverse = true;
+  else if (!match(&I, m_And(m_Value(Cond1), m_Value(Cond2))))
+    return false;
+
+  auto MatchICmpAgainstInvariant = [&](Value *C, ICmpInst::Predicate &P,
+                                       Value *&LHS, Value *&RHS) {
+    if (!match(C, m_OneUse(m_ICmp(P, m_Value(LHS), m_Value(RHS)))))
+      return false;
+    if (!ICmpInst::isRelational(P))
+      return false;
+    if (L.isLoopInvariant(LHS)) {
+      std::swap(LHS, RHS);
+      P = ICmpInst::getSwappedPredicate(P);
+    }
+    if (L.isLoopInvariant(LHS) || !L.isLoopInvariant(RHS))
+      return false;
+    if (Inverse)
+      P = ICmpInst::getInversePredicate(P);
+    return true;
+  };
+  ICmpInst::Predicate P1, P2;
+  Value *LHS1, *LHS2, *RHS1, *RHS2;
+  if (!MatchICmpAgainstInvariant(Cond1, P1, LHS1, RHS1) ||
+      !MatchICmpAgainstInvariant(Cond2, P2, LHS2, RHS2))
+    return false;
+  if (P1 != P2 || LHS1 != LHS2)
+    return false;
+
+  // Everything is fine, we can do the transform.
+  bool UseMin = ICmpInst::isLT(P1) || ICmpInst::isLE(P1);
+  assert(
+      (UseMin || ICmpInst::isGT(P1) || ICmpInst::isGE(P1)) &&
+      "Relational predicate is either less (or equal) or greater (or equal)!");
+  Intrinsic::ID id = ICmpInst::isSigned(P1)
+                         ? (UseMin ? Intrinsic::smin : Intrinsic::smax)
+                         : (UseMin ? Intrinsic::umin : Intrinsic::umax);
+  IRBuilder<> Builder(Preheader->getTerminator());
+  Value *NewRHS = Builder.CreateBinaryIntrinsic(
+      id, RHS1, RHS2, nullptr, StringRef("invariant.") +
+                                   (ICmpInst::isSigned(P1) ? "s" : "u") +
+                                   (UseMin ? "min" : "max"));
+  Builder.SetInsertPoint(&I);
+  ICmpInst::Predicate P = P1;
+  if (Inverse)
+    P = ICmpInst::getInversePredicate(P);
+  Value *NewCond = Builder.CreateICmp(P, LHS1, NewRHS);
+  NewCond->takeName(&I);
+  I.replaceAllUsesWith(NewCond);
+  eraseInstruction(I, SafetyInfo, MSSAU);
+  eraseInstruction(*cast<Instruction>(Cond1), SafetyInfo, MSSAU);
+  eraseInstruction(*cast<Instruction>(Cond2), SafetyInfo, MSSAU);
+  return true;
+}
+
 /// Little predicate that returns true if the specified basic block is in
 /// a subloop of the current one, not the current one itself.
 ///
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
   assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
   return LI->getLoopFor(BB) != CurLoop;
 }

llvm/test/CodeGen/AMDGPU/wave32.ll

 ; GFX1032-LABEL: test_loop_with_if_else_break:
 ; GFX1032:       ; %bb.0: ; %bb
 ; GFX1032-NEXT:    v_cmp_ne_u32_e32 vcc_lo, 0, v0
 ; GFX1032-NEXT:    s_mov_b32 s2, 0
 ; GFX1032-NEXT:    s_and_saveexec_b32 s3, vcc_lo
 ; GFX1032-NEXT:    s_cbranch_execz .LBB11_6
 ; GFX1032-NEXT:  ; %bb.1: ; %.preheader
 ; GFX1032-NEXT:    s_load_dwordx2 s[0:1], s[0:1], 0x24
-; GFX1032-NEXT:    v_mov_b32_e32 v1, 0
-; GFX1032-NEXT:    s_mov_b32 s3, 1
-; GFX1032-NEXT:    ; implicit-def: $sgpr4
+; GFX1032-NEXT:    v_min_u32_e32 v1, 0x100, v0
+; GFX1032-NEXT:    v_mov_b32_e32 v2, 0
+; GFX1032-NEXT:    s_mov_b32 s4, 0
+; GFX1032-NEXT:    ; implicit-def: $sgpr3
 ; GFX1032-NEXT:    s_branch .LBB11_4
 ; GFX1032-NEXT:  .LBB11_2: ; %bb8
 ; GFX1032-NEXT:    ; in Loop: Header=BB11_4 Depth=1
-; GFX1032-NEXT:    v_cmp_ge_u32_e32 vcc_lo, s3, v0
-; GFX1032-NEXT:    s_cmpk_gt_u32 s3, 0xff
-; GFX1032-NEXT:    global_store_dword v1, v0, s[0:1]
-; GFX1032-NEXT:    s_cselect_b32 s5, -1, 0
-; GFX1032-NEXT:    s_add_i32 s3, s3, 1
-; GFX1032-NEXT:    s_or_b32 s5, s5, vcc_lo
-; GFX1032-NEXT:    s_waitcnt_depctr 0xffe3
+; GFX1032-NEXT:    s_add_i32 s4, s4, 1
+; GFX1032-NEXT:    global_store_dword v2, v0, s[0:1]
+; GFX1032-NEXT:    v_cmp_ge_u32_e32 vcc_lo, s4, v1
 ; GFX1032-NEXT:    s_add_u32 s0, s0, 4
 ; GFX1032-NEXT:    s_addc_u32 s1, s1, 0
-; GFX1032-NEXT:    s_andn2_b32 s4, s4, exec_lo
-; GFX1032-NEXT:    s_and_b32 s5, s5, exec_lo
-; GFX1032-NEXT:    s_or_b32 s4, s4, s5
+; GFX1032-NEXT:    s_andn2_b32 s3, s3, exec_lo
+; GFX1032-NEXT:    s_and_b32 s5, vcc_lo, exec_lo
+; GFX1032-NEXT:    s_or_b32 s3, s3, s5
 ; GFX1032-NEXT:  .LBB11_3: ; %Flow
 ; GFX1032-NEXT:    ; in Loop: Header=BB11_4 Depth=1
-; GFX1032-NEXT:    s_and_b32 s5, exec_lo, s4
+; GFX1032-NEXT:    s_and_b32 s5, exec_lo, s3
 ; GFX1032-NEXT:    s_or_b32 s2, s5, s2
 ; GFX1032-NEXT:    s_andn2_b32 exec_lo, exec_lo, s2
 ; GFX1032-NEXT:    s_cbranch_execz .LBB11_6
 ; GFX1032-NEXT:  .LBB11_4: ; %bb2
 ; GFX1032-NEXT:    ; =>This Inner Loop Header: Depth=1
 ; GFX1032-NEXT:    s_waitcnt lgkmcnt(0)
-; GFX1032-NEXT:    global_load_dword v2, v1, s[0:1]
-; GFX1032-NEXT:    s_or_b32 s4, s4, exec_lo
+; GFX1032-NEXT:    global_load_dword v3, v2, s[0:1]
+; GFX1032-NEXT:    s_or_b32 s3, s3, exec_lo
 ; GFX1032-NEXT:    s_waitcnt vmcnt(0)
-; GFX1032-NEXT:    v_cmp_gt_i32_e32 vcc_lo, 11, v2
+; GFX1032-NEXT:    v_cmp_gt_i32_e32 vcc_lo, 11, v3
 ; GFX1032-NEXT:    s_cbranch_vccz .LBB11_2
 ; GFX1032-NEXT:  ; %bb.5: ; in Loop: Header=BB11_4 Depth=1
-; GFX1032-NEXT:    ; implicit-def: $sgpr3
+; GFX1032-NEXT:    ; implicit-def: $sgpr4
 ; GFX1032-NEXT:    ; implicit-def: $sgpr0_sgpr1
 ; GFX1032-NEXT:    s_branch .LBB11_3
 ; GFX1032-NEXT:  .LBB11_6: ; %.loopexit
 ; GFX1032-NEXT:    s_endpgm
 ;
 ; GFX1064-LABEL: test_loop_with_if_else_break:
 ; GFX1064:       ; %bb.0: ; %bb
 ; GFX1064-NEXT:    v_cmp_ne_u32_e32 vcc, 0, v0
+; GFX1064-NEXT:    s_mov_b32 s6, 0
 ; GFX1064-NEXT:    s_and_saveexec_b64 s[2:3], vcc
 ; GFX1064-NEXT:    s_cbranch_execz .LBB11_6
 ; GFX1064-NEXT:  ; %bb.1: ; %.preheader
 ; GFX1064-NEXT:    s_load_dwordx2 s[0:1], s[0:1], 0x24
-; GFX1064-NEXT:    v_mov_b32_e32 v1, 0
-; GFX1064-NEXT:    s_mov_b32 s6, 1
+; GFX1064-NEXT:    v_min_u32_e32 v1, 0x100, v0
+; GFX1064-NEXT:    v_mov_b32_e32 v2, 0
 ; GFX1064-NEXT:    s_mov_b64 s[2:3], 0
 ; GFX1064-NEXT:    ; implicit-def: $sgpr4_sgpr5
 ; GFX1064-NEXT:    s_branch .LBB11_4
 ; GFX1064-NEXT:  .LBB11_2: ; %bb8
 ; GFX1064-NEXT:    ; in Loop: Header=BB11_4 Depth=1
-; GFX1064-NEXT:    v_cmp_ge_u32_e32 vcc, s6, v0
-; GFX1064-NEXT:    s_cmpk_gt_u32 s6, 0xff
-; GFX1064-NEXT:    global_store_dword v1, v0, s[0:1]
-; GFX1064-NEXT:    s_cselect_b64 s[8:9], -1, 0
 ; GFX1064-NEXT:    s_add_i32 s6, s6, 1
-; GFX1064-NEXT:    s_or_b64 s[8:9], s[8:9], vcc
-; GFX1064-NEXT:    s_waitcnt_depctr 0xffe3
+; GFX1064-NEXT:    global_store_dword v2, v0, s[0:1]
+; GFX1064-NEXT:    v_cmp_ge_u32_e32 vcc, s6, v1
 ; GFX1064-NEXT:    s_add_u32 s0, s0, 4
 ; GFX1064-NEXT:    s_addc_u32 s1, s1, 0
 ; GFX1064-NEXT:    s_andn2_b64 s[4:5], s[4:5], exec
-; GFX1064-NEXT:    s_and_b64 s[8:9], s[8:9], exec
+; GFX1064-NEXT:    s_and_b64 s[8:9], vcc, exec
 ; GFX1064-NEXT:    s_or_b64 s[4:5], s[4:5], s[8:9]
 ; GFX1064-NEXT:  .LBB11_3: ; %Flow
 ; GFX1064-NEXT:    ; in Loop: Header=BB11_4 Depth=1
 ; GFX1064-NEXT:    s_and_b64 s[8:9], exec, s[4:5]
 ; GFX1064-NEXT:    s_or_b64 s[2:3], s[8:9], s[2:3]
 ; GFX1064-NEXT:    s_andn2_b64 exec, exec, s[2:3]
 ; GFX1064-NEXT:    s_cbranch_execz .LBB11_6
 ; GFX1064-NEXT:  .LBB11_4: ; %bb2
 ; GFX1064-NEXT:    ; =>This Inner Loop Header: Depth=1
 ; GFX1064-NEXT:    s_waitcnt lgkmcnt(0)
-; GFX1064-NEXT:    global_load_dword v2, v1, s[0:1]
+; GFX1064-NEXT:    global_load_dword v3, v2, s[0:1]
 ; GFX1064-NEXT:    s_or_b64 s[4:5], s[4:5], exec
 ; GFX1064-NEXT:    s_waitcnt vmcnt(0)
-; GFX1064-NEXT:    v_cmp_gt_i32_e32 vcc, 11, v2
+; GFX1064-NEXT:    v_cmp_gt_i32_e32 vcc, 11, v3
 ; GFX1064-NEXT:    s_cbranch_vccz .LBB11_2
 ; GFX1064-NEXT:  ; %bb.5: ; in Loop: Header=BB11_4 Depth=1
 ; GFX1064-NEXT:    ; implicit-def: $sgpr6
 ; GFX1064-NEXT:    ; implicit-def: $sgpr0_sgpr1
 ; GFX1064-NEXT:    s_branch .LBB11_3
 ; GFX1064-NEXT:  .LBB11_6: ; %.loopexit
 ; GFX1064-NEXT:    s_endpgm
 bb:

llvm/test/CodeGen/PowerPC/sms-cpy-1.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=powerpc64le-unknown-linux-gnu -verify-machineinstrs\
 ; RUN:       -mcpu=pwr9 --ppc-enable-pipeliner 2>&1 | FileCheck %s
 
 @.str.28 = external unnamed_addr constant [69 x i8], align 1
 
 define void @print_res() nounwind {
 ; CHECK-LABEL: print_res:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    mflr 0
 ; CHECK-NEXT:    stdu 1, -128(1)
 ; CHECK-NEXT:    std 0, 144(1)
 ; CHECK-NEXT:    lwz 3, 0(3)
 ; CHECK-NEXT:    addi 3, 3, -1
 ; CHECK-NEXT:    clrldi 4, 3, 32
-; CHECK-NEXT:    cmplwi 3, 1
-; CHECK-NEXT:    li 3, 1
-; CHECK-NEXT:    iselgt 3, 4, 3
-; CHECK-NEXT:    li 4, 2
-; CHECK-NEXT:    addi 3, 3, -1
-; CHECK-NEXT:    cmpldi 3, 2
-; CHECK-NEXT:    isellt 3, 3, 4
+; CHECK-NEXT:    cmplwi 3, 3
+; CHECK-NEXT:    li 3, 3
+; CHECK-NEXT:    isellt 3, 4, 3
+; CHECK-NEXT:    li 4, 1
+; CHECK-NEXT:    cmpldi 3, 1
+; CHECK-NEXT:    iselgt 3, 3, 4
 ; CHECK-NEXT:    li 4, 0
-; CHECK-NEXT:    addi 3, 3, 1
 ; CHECK-NEXT:    li 5, 0
-; CHECK-NEXT:    li 7, -1
 ; CHECK-NEXT:    mtctr 3
+; CHECK-NEXT:    li 7, -1
 ; CHECK-NEXT:    lbz 5, 0(5)
 ; CHECK-NEXT:    li 3, 1
 ; CHECK-NEXT:    bdz .LBB0_6
 ; CHECK-NEXT:  # %bb.1:
 ; CHECK-NEXT:    xori 6, 5, 84
 ; CHECK-NEXT:    clrldi 5, 7, 32
 ; CHECK-NEXT:    addi 3, 3, 1
 ; CHECK-NEXT:    addi 8, 7, -1

llvm/test/Transforms/LICM/min_max.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S %s -passes='loop-mssa(licm)'  -verify-memoryssa  | FileCheck %s
 
-; TODO: turn to %iv <u umin(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv <u umin(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_ult(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ult(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV]], [[INVARIANT_UMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ult i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv <=u umin(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv <=u umin(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_ule(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ule(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ule i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ule i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ule i32 [[IV]], [[INVARIANT_UMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ule i32 %iv, %inv_1
   %cmp_2 = icmp ule i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv <s smin(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv <s smin(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_slt(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_slt(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp slt i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp slt i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_SMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp slt i32 %iv, %inv_1
   %cmp_2 = icmp slt i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv <=s smin(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv <=s smin(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_sle(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_sle(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp sle i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp sle i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sle i32 [[IV]], [[INVARIANT_SMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp sle i32 %iv, %inv_1
   %cmp_2 = icmp sle i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv >u umax(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv >u umax(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_ugt(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ugt(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ugt i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ugt i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ugt i32 [[IV]], [[INVARIANT_UMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ugt i32 %iv, %inv_1
   %cmp_2 = icmp ugt i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv >=u umax(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv >=u umax(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_uge(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_uge(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp uge i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp uge i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp uge i32 [[IV]], [[INVARIANT_UMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp uge i32 %iv, %inv_1
   %cmp_2 = icmp uge i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv >s smax(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv >s smax(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_sgt(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_sgt(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp sgt i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp sgt i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sgt i32 [[IV]], [[INVARIANT_SMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp sgt i32 %iv, %inv_1
   %cmp_2 = icmp sgt i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv >=s smax(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv >=s smax(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_sge(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_sge(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp sge i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp sge i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sge i32 [[IV]], [[INVARIANT_SMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp sge i32 %iv, %inv_1
   %cmp_2 = icmp sge i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: Turn OR to AND and handle accordingly.
+; Turn OR to AND and handle accordingly.
 define i32 @test_ult_inv(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ult_inv(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = or i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV]], [[INVARIANT_UMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ult i32 %iv, %inv_2
   %loop_cond = or i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: Turn OR to AND and handle accordingly.
+; Turn OR to AND and handle accordingly.
 define i32 @test_ule_inv(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ule_inv(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ule i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ule i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = or i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ule i32 [[IV]], [[INVARIANT_UMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ule i32 %iv, %inv_1
   %cmp_2 = icmp ule i32 %iv, %inv_2
   %loop_cond = or i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: Turn OR to AND and handle accordingly.
+; Turn OR to AND and handle accordingly.
 define i32 @test_slt_inv(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_slt_inv(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp slt i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp slt i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = or i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_SMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp slt i32 %iv, %inv_1
   %cmp_2 = icmp slt i32 %iv, %inv_2
   %loop_cond = or i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: Turn OR to AND and handle accordingly.
+; Turn OR to AND and handle accordingly.
 define i32 @test_sle_inv(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_sle_inv(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp sle i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp sle i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = or i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sle i32 [[IV]], [[INVARIANT_SMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp sle i32 %iv, %inv_1
   %cmp_2 = icmp sle i32 %iv, %inv_2
   %loop_cond = or i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: Turn OR to AND and handle accordingly.
+; Turn OR to AND and handle accordingly.
 define i32 @test_ugt_inv(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ugt_inv(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ugt i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ugt i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = or i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ugt i32 [[IV]], [[INVARIANT_UMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ugt i32 %iv, %inv_1
   %cmp_2 = icmp ugt i32 %iv, %inv_2
   %loop_cond = or i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: Turn OR to AND and handle accordingly.
+; Turn OR to AND and handle accordingly.
 define i32 @test_uge_inv(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_uge_inv(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp uge i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp uge i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = or i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp uge i32 [[IV]], [[INVARIANT_UMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp uge i32 %iv, %inv_1
   %cmp_2 = icmp uge i32 %iv, %inv_2
   %loop_cond = or i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: Turn OR to AND and handle accordingly.
+; Turn OR to AND and handle accordingly.
 define i32 @test_sgt_inv(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_sgt_inv(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp sgt i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp sgt i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = or i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sgt i32 [[IV]], [[INVARIANT_SMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp sgt i32 %iv, %inv_1
   %cmp_2 = icmp sgt i32 %iv, %inv_2
   %loop_cond = or i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: Turn OR to AND and handle accordingly.
+; Turn OR to AND and handle accordingly.
 define i32 @test_sge_inv(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_sge_inv(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp sge i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp sge i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = or i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sge i32 [[IV]], [[INVARIANT_SMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp sge i32 %iv, %inv_1
   %cmp_2 = icmp sge i32 %iv, %inv_2
   %loop_cond = or i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv <u umin(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv <u umin(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_ult_swapped(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ult_swapped(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ugt i32 [[INV_1:%.*]], [[IV]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ugt i32 [[INV_2:%.*]], [[IV]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV]], [[INVARIANT_UMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ugt i32 %inv_1, %iv
   %cmp_2 = icmp ugt i32 %inv_2, %iv
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv <=u umin(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv <=u umin(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_ule_swapped(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ule_swapped(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp uge i32 [[INV_1:%.*]], [[IV]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp uge i32 [[INV_2:%.*]], [[IV]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ule i32 [[IV]], [[INVARIANT_UMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp uge i32 %inv_1, %iv
   %cmp_2 = icmp uge i32 %inv_2, %iv
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv <s smin(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv <s smin(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_slt_swapped(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_slt_swapped(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp sgt i32 [[INV_1:%.*]], [[IV]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp sgt i32 [[INV_2:%.*]], [[IV]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_SMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp sgt i32 %inv_1, %iv
   %cmp_2 = icmp sgt i32 %inv_2, %iv
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv <=s smin(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv <=s smin(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_sle_swapped(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_sle_swapped(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp sge i32 [[INV_1:%.*]], [[IV]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp sge i32 [[INV_2:%.*]], [[IV]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sle i32 [[IV]], [[INVARIANT_SMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp sge i32 %inv_1, %iv
   %cmp_2 = icmp sge i32 %inv_2, %iv
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv >u umax(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv >u umax(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_ugt_swapped(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ugt_swapped(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[INV_1:%.*]], [[IV]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[INV_2:%.*]], [[IV]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ugt i32 [[IV]], [[INVARIANT_UMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %inv_1, %iv
   %cmp_2 = icmp ult i32 %inv_2, %iv
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv >=u umax(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv >=u umax(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_uge_swapped(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_uge_swapped(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ule i32 [[INV_1:%.*]], [[IV]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ule i32 [[INV_2:%.*]], [[IV]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp uge i32 [[IV]], [[INVARIANT_UMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ule i32 %inv_1, %iv
   %cmp_2 = icmp ule i32 %inv_2, %iv
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv >s smax(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv >s smax(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_sgt_swapped(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_sgt_swapped(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp slt i32 [[INV_1:%.*]], [[IV]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp slt i32 [[INV_2:%.*]], [[IV]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sgt i32 [[IV]], [[INVARIANT_SMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp slt i32 %inv_1, %iv
   %cmp_2 = icmp slt i32 %inv_2, %iv
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
-; TODO: turn to %iv >=s smax(inv_1, inv_2) and hoist it out of loop.
+; turn to %iv >=s smax(inv_1, inv_2) and hoist it out of loop.
 define i32 @test_sge_swapped(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_sge_swapped(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp sle i32 [[INV_1:%.*]], [[IV]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp sle i32 [[INV_2:%.*]], [[IV]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp sge i32 [[IV]], [[INVARIANT_SMAX]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp sle i32 %inv_1, %iv
   %cmp_2 = icmp sle i32 %inv_2, %iv
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; TODO: inv_2 needs freeze because hoisted umax would create a new use that didn't exist before.
 ; Counter-example: %cmp_1 = false, %inv_2 = poison.
 define i32 @test_logical_and_ult_needs_freeze(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_logical_and_ult_needs_freeze(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = select i1 [[CMP_1]], i1 [[CMP_2]], i1 false
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ult i32 %iv, %inv_2
   %loop_cond = select i1 %cmp_1, i1 %cmp_2, i1 false
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; TODO: turn to %iv <u umin(inv_1, inv_2) and hoist it out of loop.
 ; https://alive2.llvm.org/ce/z/mhKGtT
 define i32 @test_logical_and_ult_pos(i32 %start, i32 %inv_1, i32 noundef %inv_2) {
 ; CHECK-LABEL: @test_logical_and_ult_pos(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = select i1 [[CMP_1]], i1 [[CMP_2]], i1 false
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ult i32 %iv, %inv_2
   %loop_cond = select i1 %cmp_1, i1 %cmp_2, i1 false
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; TODO: inv_2 needs freeze because hoisted umax would create a new use that didn't exist before.
 define i32 @test_logical_or_ult_inv_needs_freeze(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_logical_or_ult_inv_needs_freeze(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = select i1 [[CMP_1]], i1 true, i1 [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ult i32 %iv, %inv_2
   %loop_cond = select i1 %cmp_1, i1 true, i1 %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; TODO: turn to %iv <u umax(inv_1, inv_2) and hoist it out of loop.
 ; https://alive2.llvm.org/ce/z/zgyG5N
 define i32 @test_logical_or_ult_inv_pos(i32 %start, i32 %inv_1, i32 noundef %inv_2) {
 ; CHECK-LABEL: @test_logical_or_ult_inv_pos(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = select i1 [[CMP_1]], i1 true, i1 [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ult i32 %iv, %inv_2
   %loop_cond = select i1 %cmp_1, i1 true, i1 %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; Mismatched predicates, do not optimize.
 define i32 @test_mismatched_predicates_neg(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_mismatched_predicates_neg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ule i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ule i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; TODO: Turn ule against constant into ult against constant, then do the same as in test_ult.
 ; https://alive2.llvm.org/ce/z/rucunQ
 define i32 @test_mismatched_predicates_constant_pos_1(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_mismatched_predicates_constant_pos_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ule i32 [[IV]], 100
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ule i32 %iv, 100
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; TODO: Turn ult against a constant into ule, then do the same as in test_ule.
 ; https://alive2.llvm.org/ce/z/-ht-pU
 define i32 @test_mismatched_predicates_constant_pos_2(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_mismatched_predicates_constant_pos_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], 100
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ule i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, 100
   %cmp_2 = icmp ule i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; Do not optimize: `ule -1` cannot be turned into `ult 0` because of overflow.
 ; However, this condition is trivially true anyways, so do not bother about it.
 define i32 @test_mismatched_predicates_constant_neg(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_mismatched_predicates_constant_neg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ule i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ule i32 %iv, -1
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; Do not optimize: predicate eq.
 define i32 @test_eq_neg(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_eq_neg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp eq i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp eq i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp eq i32 %iv, %inv_1
   %cmp_2 = icmp eq i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; Do not optimize: predicate ne.
 define i32 @test_ne_neg(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ne_neg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ne i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ne i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ne i32 %iv, %inv_1
   %cmp_2 = icmp ne i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv
 }
 
 ; Do not optimize: extra use.
 define i32 @test_ult_extra_use_1_neg(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ult_extra_use_1_neg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1_LCSSA:%.*]] = phi i1 [ [[CMP_1]], [[LOOP]] ]
 ; CHECK-NEXT:    call void @use(i1 [[CMP_1_LCSSA]])
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ult i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   call void @use(i1 %cmp_1)
   ret i32 %iv
 }
 
 define i32 @test_ult_extra_use_2_neg(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ult_extra_use_2_neg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_2_LCSSA:%.*]] = phi i1 [ [[CMP_2]], [[LOOP]] ]
 ; CHECK-NEXT:    call void @use(i1 [[CMP_2_LCSSA]])
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ult i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   call void @use(i1 %cmp_2)
   ret i32 %iv
 }
 
-; TODO: This can be optimized, despite the fact that loop_cond has other uses.
+; This can be optimized, despite the fact that loop_cond has other uses.
 define i32 @test_ult_extra_use_result_pos(i32 %start, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ult_extra_use_result_pos(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVARIANT_UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INV_1:%.*]], i32 [[INV_2:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV]], [[INV_1:%.*]]
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV]], [[INV_2:%.*]]
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV]], [[INVARIANT_UMIN]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 ; CHECK-NEXT:    [[LOOP_COND_LCSSA:%.*]] = phi i1 [ [[LOOP_COND]], [[LOOP]] ]
 ; CHECK-NEXT:    call void @use(i1 [[LOOP_COND_LCSSA]])
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %loop]
   %cmp_1 = icmp ult i32 %iv, %inv_1
   %cmp_2 = icmp ult i32 %iv, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   call void @use(i1 %loop_cond)
   ret i32 %iv
 }
 
 ; Do not optimize: comparison against different variant values.
 define i32 @test_ult_different_variants_neg(i32 %start_1, i32 %start_2, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ult_different_variants_neg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i32 [ [[START_1:%.*]], [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i32 [ [[START_2:%.*]], [[ENTRY]] ], [ [[IV_2_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV_1]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV_2]], [[INV_2:%.*]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_1_NEXT]] = add i32 [[IV_1]], 1
 ; CHECK-NEXT:    [[IV_2_NEXT]] = add i32 [[IV_2]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_1_LCSSA:%.*]] = phi i32 [ [[IV_1]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_1_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv_1 = phi i32 [%start_1, %entry], [%iv_1.next, %loop]
   %iv_2 = phi i32 [%start_2, %entry], [%iv_2.next, %loop]
   %cmp_1 = icmp ult i32 %iv_1, %inv_1
   %cmp_2 = icmp ult i32 %iv_2, %inv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv_1.next = add i32 %iv_1, 1
   %iv_2.next = add i32 %iv_2, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv_1
 }
 
 ; Do not optimize: one of comparisons is against loop-variant.
 define i32 @test_ult_compare_against_variant_neg(i32 %start_1, i32 %start_2, i32 %inv_1, i32 %inv_2) {
 ; CHECK-LABEL: @test_ult_compare_against_variant_neg(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i32 [ [[START_1:%.*]], [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i32 [ [[START_2:%.*]], [[ENTRY]] ], [ [[IV_2_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[IV_1]], [[INV_1:%.*]]
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[IV_1]], [[IV_2]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = and i1 [[CMP_1]], [[CMP_2]]
 ; CHECK-NEXT:    [[IV_1_NEXT]] = add i32 [[IV_1]], 1
 ; CHECK-NEXT:    [[IV_2_NEXT]] = add i32 [[IV_2]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_1_LCSSA:%.*]] = phi i32 [ [[IV_1]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i32 [[IV_1_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv_1 = phi i32 [%start_1, %entry], [%iv_1.next, %loop]
   %iv_2 = phi i32 [%start_2, %entry], [%iv_2.next, %loop]
   %cmp_1 = icmp ult i32 %iv_1, %inv_1
   %cmp_2 = icmp ult i32 %iv_1, %iv_2
   %loop_cond = and i1 %cmp_1, %cmp_2
   %iv_1.next = add i32 %iv_1, 1
   %iv_2.next = add i32 %iv_2, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret i32 %iv_1
 }
 
 declare void @use(i1)