[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

2413 ↗

(On Diff #498773)

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.

2417–2419 ↗

(On Diff #498773)

2428 ↗

(On Diff #498773)

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

2456 ↗

(On Diff #498773)

ICmpInst::Predicate

2459 ↗

(On Diff #498773)

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

llvm/test/Transforms/LICM/min_max.ll

482 ↗

(On Diff #498773)

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

2413 ↗

(On Diff #498773)

Good catch! Thanks for pointing out.

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

2413 ↗

(On Diff #498773)

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 ↗

(On Diff #498773)

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

2443 ↗

(On Diff #504039)

This TODO is already done :)

2413 ↗

(On Diff #498773)

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.

llvm/test/Transforms/LICM/min_max.ll

883 ↗

(On Diff #504039)

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

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

2443 ↗

(On Diff #504039)

Indeed.

2413 ↗

(On Diff #498773)

That's an option too.

[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/LoopInstSimplify.cpp

 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include <optional>
 #include <utility>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-instsimplify"
 
 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
 
+/// 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 Value *tryToSimplifyAndOr(Instruction &I, Loop &L) {
+  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_LogicalOr(m_Value(Cond1), m_Value(Cond2))))
+    Inverse = true;
+  else if (!match(&I, m_LogicalAnd(m_Value(Cond1), m_Value(Cond2))))
+    return nullptr;
+
+  auto MatchICmpAgainstInvariant = [&](Value *C, ICmpInst::Predicate &P,
+                                       Value *&LHS, Value *&RHS) {
+    if (!C->hasOneUse())
+      return false;
+    if (!match(C, m_ICmp(P, m_Value(LHS), m_Value(RHS))))
+      return false;
+    if (!ICmpInst::isRelational(P))
+      return false;
+    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 nullptr;
+  if (P1 != P2 || LHS1 != LHS2)
+    return nullptr;
+
+  // 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;
+  if (ICmpInst::isSigned(P1)) {
+    if (UseMin)
+      id = Intrinsic::smin;
+    else
+      id = Intrinsic::smax;
+  } else {
+    assert(ICmpInst::isUnsigned(P1) &&
+           "All relational predicates are either signed or unsigned!");
+    if (UseMin)
+      id = Intrinsic::umin;
+    else
+      id = Intrinsic::umax;
+  }
+  IRBuilder<> Builder(Preheader->getTerminator());
+  Value *NewRHS =
+      Builder.CreateBinaryIntrinsic(id, RHS1, RHS2, nullptr, "invariant.rhs");
+  Builder.SetInsertPoint(&I);
+  auto P = P1;
+  if (Inverse)
+    P = ICmpInst::getInversePredicate(P);
+  auto *NewCond = Builder.CreateICmp(P, LHS1, NewRHS, I.getName());
+
+  return NewCond;
+}
+
+/// Try to make simplification that make sense in presence of loop. For example,
+/// they open up opportunities for hoisting invariants.
+static Value *tryToSimplifyWithLoop(Instruction &I, Loop &L) {
+  if (auto *S = tryToSimplifyAndOr(I, L))
+    return S;
+  return nullptr;
+}
+
+/// Try to simplify the instruction with by means possible.
+static Value *tryToSimplify(Instruction &I, Loop &L, LoopInfo &LI,
+                            const SimplifyQuery &SQ) {
+  // Try trivial peephole simplifications.
+  if (auto *S = simplifyInstruction(&I, SQ.getWithInstruction(&I)))
+    return S;
+  if (auto *S = tryToSimplifyWithLoop(I, L)) {
+    assert(LI.replacementPreservesLCSSAForm(&I, S) &&
+           "Loop simplification are not allowed to break LCSSA!");
+    return S;
+  }
+  return nullptr;
+}
+
 static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
                              AssumptionCache &AC, const TargetLibraryInfo &TLI,
                              MemorySSAUpdater *MSSAU) {
   const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
   SimplifyQuery SQ(DL, &TLI, &DT, &AC);
 
   // On the first pass over the loop body we try to simplify every instruction.
   // On subsequent passes, we can restrict this to only simplifying instructions
for (BasicBlock *BB : RPOT) {
 
         // We special case the first iteration which we can detect due to the
         // empty `ToSimplify` set.
         bool IsFirstIteration = ToSimplify->empty();
 
         if (!IsFirstIteration && !ToSimplify->count(&I))
           continue;
 
-        Value *V = simplifyInstruction(&I, SQ.getWithInstruction(&I));
+        Value *V = tryToSimplify(I, L, LI, SQ);
         if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
           continue;
 
         for (Use &U : llvm::make_early_inc_range(I.uses())) {
           auto *UserI = cast<Instruction>(U.getUser());
           U.set(V);
 
           // Do not bother dealing with unreachable code.

llvm/test/Transforms/LoopInstSimplify/loop_invariant.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S %s -passes=loop-instsimplify | FileCheck %s
 ; RUN: opt -S %s -passes='loop-mssa(loop-instsimplify)' -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_RHS:%.*]] = 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_COND1:%.*]] = icmp ult i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp ule i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp sle i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp ugt i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp uge i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp sgt i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp sge i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp ult i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp ule i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp sle i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp ugt i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp uge i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp sgt i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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_RHS:%.*]] = 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_COND1:%.*]] = icmp sge i32 [[IV]], [[INVARIANT_RHS]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND1]], 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: