[LICM] Support logical AND/OR when hoisting min/max

[mkazantsev]

Summary

We can handle logical AND/OR in the same way as arithmetic AND/OR, it only
takes us freezing RHS2 for which we may introduce a new use which didn't
exist before dynamically.

[nikic]

As mentioned on the other review, if the RHS is non-poison, then InstCombine will already convert logical to bitwise op. There's no need to reimplement a weaker check here. If we want to handle logical and/or in this context, the way to do it is to freeze the RHS, which will allow to always perform the fold.

[mkazantsev]

The problem here is that InstCombine is a non-loop pass, and some loop passes might be unable to see through freezes... Not sure how real this case is, lets try to just freeze, but maybe it can be an issue for some custom pipelines.

[mkazantsev]

Changed into solution with freeze.

[nikic]

LGTM

[abrachet]

This patch is causing assertion failures. See reproducer https://storage.googleapis.com/fuchsia-artifacts/builds/8787011276367081201/sanitizer_libc-53f165.tar.gz, I checked and reverting made the issue go away. Would you mind taking a look or reverting if the fix will take a while?

clang-cl: /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Utils/SCCPSolver.cpp:46: ConstantRange getConstantRange(const ValueLatticeElement &, Type *, bool): Assertion `Ty->isIntOrIntVectorTy() && "Should be int or int vector"' 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-cl -cc1 -triple x86_64-pc-windows-msvc19.20.0 -emit-obj -mincremental-linker-compatible -disable-free -clear-ast-before-backend -main-file-name sanitizer_libc.cpp -mrelocation-model pic -pic-level 2 -mframe-pointer=none -relaxed-aliasing -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -mllvm -x86-asm-syntax=intel -tune-cpu generic -mllvm -treat-scalable-fixed-error-as-warning -D_MT -flto-visibility-public-std --dependent-lib=libcmt --dependent-lib=oldnames --show-includes -sys-header-deps -fno-rtti-data -fms-volatile -fdiagnostics-format msvc -gno-column-info -gcodeview -debug-info-kind=constructor -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/opt/s/w/ir/x/w/staging/llvm_build/runtimes/runtimes-x86_64-pc-windows-msvc-bins -D HAVE_RPC_XDR_H=0 -D UNICODE -D _CRT_NONSTDC_NO_DEPRECATE -D _CRT_NONSTDC_NO_WARNINGS -D _CRT_SECURE_NO_DEPRECATE -D _CRT_SECURE_NO_WARNINGS -D _GLIBCXX_ASSERTIONS -D _LIBCPP_ENABLE_ASSERTIONS -D _SCL_SECURE_NO_DEPRECATE -D _SCL_SECURE_NO_WARNINGS -D _UNICODE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -O2 -Wno-unused-parameter -WCL4 -Wno-unused-parameter -Wthread-safety -Wthread-safety-reference -Wthread-safety-beta -Wno-gnu -Wno-variadic-macros -Wno-c99-extensions -Wno-format -Wframe-larger-than=570 -Wglobal-constructors -fdeprecated-macro -fdebug-compilation-dir=/opt/s/w/ir/x/w/staging/llvm_build/runtimes/runtimes-x86_64-pc-windows-msvc-bins -ferror-limit 19 -fno-builtin -fno-use-cxa-atexit -fms-extensions -fms-compatibility -fms-compatibility-version=19.20 -std=c++17 -fno-threadsafe-statics -finline-hint-functions -vectorize-loops -vectorize-slp -faddrsig -object-file-name=/opt/s/w/ir/x/w/staging/llvm_build/runtimes/runtimes-x86_64-pc-windows-msvc-bins/compiler-rt/lib/sanitizer_common/CMakeFiles/RTSanitizerCommon.x86_64.dir/sanitizer_libc.cpp.obj -x c++ sanitizer_libc-53f165.cpp
1.      <eof> parser at end of file
2.      Optimizer
 #0 0x000055cf4353d4dd llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Support/Unix/Signals.inc:602:11
 #1 0x000055cf4353d96b PrintStackTraceSignalHandler(void*) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Support/Unix/Signals.inc:676:1
 #2 0x000055cf4353be96 llvm::sys::RunSignalHandlers() /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Support/Signals.cpp:104:5
 #3 0x000055cf4353df45 SignalHandler(int) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Support/Unix/Signals.inc:413:1
 #4 0x00007fa1f8af0f90 (/lib/x86_64-linux-gnu/libc.so.6+0x3bf90)
 #5 0x00007fa1f8b3fccc (/lib/x86_64-linux-gnu/libc.so.6+0x8accc)
 #6 0x00007fa1f8af0ef2 raise (/lib/x86_64-linux-gnu/libc.so.6+0x3bef2)
 #7 0x00007fa1f8adb472 abort (/lib/x86_64-linux-gnu/libc.so.6+0x26472)
 #8 0x00007fa1f8adb395 (/lib/x86_64-linux-gnu/libc.so.6+0x26395)
 #9 0x00007fa1f8ae9df2 (/lib/x86_64-linux-gnu/libc.so.6+0x34df2)
#10 0x000055cf420e7d30 getConstantRange(llvm::ValueLatticeElement const&, llvm::Type*, bool) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Utils/SCCPSolver.cpp:47:7
#11 0x000055cf420ea330 llvm::SCCPInstVisitor::handleCallResult(llvm::CallBase&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Utils/SCCPSolver.cpp:1666:18
#12 0x000055cf420e9b11 llvm::SCCPInstVisitor::visitCallBase(llvm::CallBase&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Utils/SCCPSolver.cpp:1503:3
#13 0x000055cf420ff8ad llvm::SCCPInstVisitor::visitCallInst(llvm::CallInst&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Utils/SCCPSolver.cpp:615:55
#14 0x000055cf420ff66d llvm::InstVisitor<llvm::SCCPInstVisitor, void>::visitIntrinsicInst(llvm::IntrinsicInst&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/InstVisitor.h:219:53
#15 0x000055cf420ff563 llvm::InstVisitor<llvm::SCCPInstVisitor, void>::delegateCallInst(llvm::CallInst&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/InstVisitor.h:287:36
#16 0x000055cf420eea4d llvm::InstVisitor<llvm::SCCPInstVisitor, void>::visitCall(llvm::CallInst&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/Instruction.def:209:1
#17 0x000055cf420f3ea9 llvm::InstVisitor<llvm::SCCPInstVisitor, void>::visit(llvm::Instruction&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/Instruction.def:209:1
#18 0x000055cf420f36ab llvm::SCCPInstVisitor::operandChangedState(llvm::Instruction*) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Utils/SCCPSolver.cpp:515:3
#19 0x000055cf420edae0 llvm::SCCPInstVisitor::markUsersAsChanged(llvm::Value*) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Utils/SCCPSolver.cpp:535:7
#20 0x000055cf420eaea3 llvm::SCCPInstVisitor::solve() /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Utils/SCCPSolver.cpp:1708:5
#21 0x000055cf420eb70d llvm::SCCPSolver::solve() /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Utils/SCCPSolver.cpp:1888:46
#22 0x000055cf41ce2e96 runSCCP(llvm::Function&, llvm::DataLayout const&, llvm::TargetLibraryInfo const*, llvm::DomTreeUpdater&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Scalar/SCCP.cpp:85:5
#23 0x000055cf41ce2c70 llvm::SCCPPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/Scalar/SCCP.cpp:131:7
#24 0x000055cf3f82e214 llvm::detail::PassModel<llvm::Function, llvm::SCCPPass, 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
#25 0x000055cf4304a2f7 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
#26 0x000055cf3ab61a74 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
#27 0x000055cf4221af6d llvm::CGSCCToFunctionPassAdaptor::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Analysis/CGSCCPassManager.cpp:541:38
#28 0x000055cf3f83cbf4 llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::CGSCCToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:89:17
#29 0x000055cf422191e6 llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Analysis/CGSCCPassManager.cpp:89:9
#30 0x000055cf3f7fb054 llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:89:17
#31 0x000055cf42219fb6 llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Analysis/CGSCCPassManager.cpp:411:9
#32 0x000055cf3f83e494 llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::DevirtSCCRepeatedPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:89:17
#33 0x000055cf42219afb llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Analysis/CGSCCPassManager.cpp:279:18
#34 0x000055cf3f7fb584 llvm::detail::PassModel<llvm::Module, llvm::ModuleToPostOrderCGSCCPassAdaptor, 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
#35 0x000055cf43049617 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
#36 0x000055cf404d51b8 llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/abrachet/Developer/llvm-project/llvm/lib/Transforms/IPO/Inliner.cpp:1172:3
#37 0x000055cf3f8082d4 llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, 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
#38 0x000055cf43049617 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
#39 0x000055cf3ab42b3b (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
#40 0x000055cf3ab3de4f (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
#41 0x000055cf3ab3d374 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
#42 0x000055cf3b029c6a clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:383:7
#43 0x000055cf3ceec103 clang::ParseAST(clang::Sema&, bool, bool) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/Parse/ParseAST.cpp:182:12
#44 0x000055cf3ae46e16 clang::ASTFrontendAction::ExecuteAction() /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1170:1
#45 0x000055cf3b0254c4 clang::CodeGenAction::ExecuteAction() /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:1173:5
#46 0x000055cf3ae4685c clang::FrontendAction::Execute() /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1062:7
#47 0x000055cf3ad71108 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/Frontend/CompilerInstance.cpp:1049:23
#48 0x000055cf3b015207 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /usr/local/google/home/abrachet/Developer/llvm-project/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:264:8
#49 0x000055cf39c7e281 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
#50 0x000055cf39c73382 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) /usr/local/google/home/abrachet/Developer/llvm-project/clang/tools/driver/driver.cpp:363:5
#51 0x000055cf39c72107 clang_main(int, char**, llvm::ToolContext const&) /usr/local/google/home/abrachet/Developer/llvm-project/clang/tools/driver/driver.cpp:441:5
#52 0x000055cf39f46e03 findTool(int, char**, char const*) /usr/local/google/home/abrachet/Developer/llvm-project/build/tools/llvm-driver/LLVMDriverTools.def:6:1
#53 0x000055cf39f469f9 main /usr/local/google/home/abrachet/Developer/llvm-project/llvm/tools/llvm-driver/llvm-driver.cpp:83:35
#54 0x00007fa1f8adc18a (/lib/x86_64-linux-gnu/libc.so.6+0x2718a)
#55 0x00007fa1f8adc245 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x27245)
#56 0x000055cf39bd9069 _start (./bin/clang-cl+0x5480069)

[vitalybuka]

Broken

https://lab.llvm.org/buildbot/#/builders/37/builds/20720
https://lab.llvm.org/buildbot/#/builders/70/builds/34864
https://lab.llvm.org/buildbot/#/builders/19/builds/15536

and others

[mkazantsev]

Completely unrelated to this patch, seems to be an existing bug in SCCP.

[mkazantsev]

@abrachet if you can reproduce it in your env, could you please run it with -mllvm -print-before=sccp -mllvm -print-module-scope? The crash is obviously happening in a completely different pass, and it must be an existing bug. I see not enough ground for revert.

[abrachet]

In D145771#4187966, @mkazantsev wrote:

@abrachet if you can reproduce it in your env, could you please run it with -mllvm -print-before=sccp -mllvm -print-module-scope? The crash is obviously happening in a completely different pass, and it must be an existing bug. I see not enough ground for revert.

You can reproduce with https://storage.googleapis.com/fuchsia-artifacts/builds/8787011276367081201/sanitizer_libc-53f165.tar.gz and by changing the path of the compiler in the shell script to be to your clang-cl

[mkazantsev]

Ok I know what happened. We managed to create umin of pointer type, eh...

[mkazantsev]

I'll fix that.

llvm/lib/Transforms/Scalar/LICM.cpp

for (const auto &MA : *Accesses)
         if (MU.getBlock() != MD->getBlock() || !MSSA.locallyDominates(MD, &MU))
           return true;
   return false;
 }
 
 static bool hoistMinMax(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
                         MemorySSAUpdater &MSSAU) {
   bool Inverse = false;
+  bool IsLogical = 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))))
+  else if (match(&I, m_LogicalOr(m_Value(Cond1), m_Value(Cond2)))) {
+    Inverse = true;
+    IsLogical = true;
+  } else if (match(&I, m_And(m_Value(Cond1), m_Value(Cond2)))) {
+    // Do nothing
+  } else if (match(&I, m_LogicalAnd(m_Value(Cond1), m_Value(Cond2))))
+    IsLogical = true;
+  else
     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 (!LHS->getType()->isIntegerTy())
       return false;
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);
   auto *Preheader = L.getLoopPreheader();
   assert(Preheader && "Loop is not in simplify form?");
   IRBuilder<> Builder(Preheader->getTerminator());
+  // We are about to create a new guaranteed use for RHS2 which might not exist
+  // before (if it was a non-taken input of logical and/or instruction). If it
+  // was poison, we need to freeze it. Note that no new use for LHS and RHS1 are
+  // introduced, so they don't need this.
+  if (IsLogical)
+    RHS2 = Builder.CreateFreeze(RHS2, RHS2->getName() + ".fr");
   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);

llvm/test/Transforms/LICM/min_max.ll

loop:
   %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.
+; 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:    [[INV_2_FR:%.*]] = freeze i32 [[INV_2:%.*]]
+; CHECK-NEXT:    [[INVARIANT_UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INV_1:%.*]], i32 [[INV_2_FR]])
 ; 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:    [[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 = 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.
+; 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:    [[INV_2_FR:%.*]] = freeze i32 [[INV_2:%.*]]
+; CHECK-NEXT:    [[INVARIANT_UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INV_1:%.*]], i32 [[INV_2_FR]])
 ; 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:    [[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 = 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.
+; 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:    [[INV_2_FR:%.*]] = freeze i32 [[INV_2:%.*]]
+; CHECK-NEXT:    [[INVARIANT_UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[INV_1:%.*]], i32 [[INV_2_FR]])
 ; 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:    [[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 = 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.
+; 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:    [[INV_2_FR:%.*]] = freeze i32 [[INV_2:%.*]]
+; CHECK-NEXT:    [[INVARIANT_UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[INV_1:%.*]], i32 [[INV_2_FR]])
 ; 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:    [[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