Assertion `LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UDIV!" regression on mips with 16 branch

[andrewrk]

LLVM version release/16.x branch commit 3f9b92d027f5d0bd23f852b66d47c5061363532d

reduced.ll

target datalayout = "E-m:m-p:32:32-i8:8:32-i16:16:32-i64:64-n32-S64"
target triple = "mips-unknown-linux-unknown"

define internal fastcc i16 @"compiler_rt.udivmodei4.test.__udivei4/__umodei4"(i1200 %0) {
Entry:
  %1 = udiv i1200 1, %0
  store i1200 %1, ptr null, align 8
  ret i16 0
}

[nix-shell:~/misc/zig/build]$ ~/local/llvm15-assert/bin/clang -c reduced.ll -target mips-unknown-linux-unknown

[nix-shell:~/misc/zig/build]$ ~/local/llvm16-assert/bin/clang -c reduced.ll -target mips-unknown-linux-unknown
clang: /home/andy/Downloads/llvm-project-16/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp:4643: void llvm::DAGTypeLegalizer::ExpandIntRes_UDIV(llvm::SDNode*, llvm::SDValue&, llvm::SDValue&): Assertion `LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UDIV!"' 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: /home/andy/local/llvm16-assert/bin/clang -c reduced.ll -target mips-unknown-linux-unknown
1.  Code generation
2.  Running pass 'Function Pass Manager' on module 'reduced.ll'.
3.  Running pass 'MIPS DAG->DAG Pattern Instruction Selection' on function '@"compiler_rt.udivmodei4.test.__udivei4/__umodei4"'
 #0 0x00000000035bc671 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/andy/local/llvm16-assert/bin/clang+0x35bc671)
 #1 0x00000000035ba5ac llvm::sys::CleanupOnSignal(unsigned long) (/home/andy/local/llvm16-assert/bin/clang+0x35ba5ac)
 #2 0x00000000035102e8 CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #3 0x00007fa8bcd5ebf0 __restore_rt (/nix/store/4nlgxhb09sdr51nc9hdm8az5b08vzkgx-glibc-2.35-163/lib/libc.so.6+0x3dbf0)
 #4 0x00007fa8bcdabbc7 __pthread_kill_implementation (/nix/store/4nlgxhb09sdr51nc9hdm8az5b08vzkgx-glibc-2.35-163/lib/libc.so.6+0x8abc7)
 #5 0x00007fa8bcd5eb46 gsignal (/nix/store/4nlgxhb09sdr51nc9hdm8az5b08vzkgx-glibc-2.35-163/lib/libc.so.6+0x3db46)
 #6 0x00007fa8bcd494b5 abort (/nix/store/4nlgxhb09sdr51nc9hdm8az5b08vzkgx-glibc-2.35-163/lib/libc.so.6+0x284b5)
 #7 0x00007fa8bcd493d9 _nl_load_domain.cold.0 (/nix/store/4nlgxhb09sdr51nc9hdm8az5b08vzkgx-glibc-2.35-163/lib/libc.so.6+0x283d9)
 #8 0x00007fa8bcd577b6 (/nix/store/4nlgxhb09sdr51nc9hdm8az5b08vzkgx-glibc-2.35-163/lib/libc.so.6+0x367b6)
 #9 0x000000000485167a llvm::DAGTypeLegalizer::ExpandIntRes_UDIV(llvm::SDNode*, llvm::SDValue&, llvm::SDValue&) (/home/andy/local/llvm16-assert/bin/clang+0x485167a)
#10 0x00000000048706c2 llvm::DAGTypeLegalizer::ExpandIntegerResult(llvm::SDNode*, unsigned int) (/home/andy/local/llvm16-assert/bin/clang+0x48706c2)
#11 0x000000000479bbf6 llvm::DAGTypeLegalizer::run() (/home/andy/local/llvm16-assert/bin/clang+0x479bbf6)
#12 0x000000000479cd9c llvm::SelectionDAG::LegalizeTypes() (/home/andy/local/llvm16-assert/bin/clang+0x479cd9c)
#13 0x0000000004721421 llvm::SelectionDAGISel::CodeGenAndEmitDAG() (/home/andy/local/llvm16-assert/bin/clang+0x4721421)
#14 0x0000000004725554 llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) (/home/andy/local/llvm16-assert/bin/clang+0x4725554)
#15 0x00000000047273fe llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) (.part.0) SelectionDAGISel.cpp:0:0
#16 0x00000000019524eb llvm::MipsDAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) (/home/andy/local/llvm16-assert/bin/clang+0x19524eb)
#17 0x00000000028688d5 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (.part.0) MachineFunctionPass.cpp:0:0
#18 0x0000000002dfb2bb llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/andy/local/llvm16-assert/bin/clang+0x2dfb2bb)
#19 0x0000000002dfb4d1 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/andy/local/llvm16-assert/bin/clang+0x2dfb4d1)
#20 0x0000000002dfbd63 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/andy/local/llvm16-assert/bin/clang+0x2dfbd63)
#21 0x0000000003992361 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) (/home/andy/local/llvm16-assert/bin/clang+0x3992361)
#22 0x0000000004886efe clang::CodeGenAction::ExecuteAction() (/home/andy/local/llvm16-assert/bin/clang+0x4886efe)
#23 0x00000000041260f9 clang::FrontendAction::Execute() (/home/andy/local/llvm16-assert/bin/clang+0x41260f9)
#24 0x00000000040ad206 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/andy/local/llvm16-assert/bin/clang+0x40ad206)
#25 0x00000000041ee0e8 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/andy/local/llvm16-assert/bin/clang+0x41ee0e8)
#26 0x0000000000ad52ad cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/andy/local/llvm16-assert/bin/clang+0xad52ad)
#27 0x0000000000ad13fe ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) driver.cpp:0:0
#28 0x0000000003f15145 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<std::optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const::'lambda'()>(long) Job.cpp:0:0
#29 0x0000000003510724 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/andy/local/llvm16-assert/bin/clang+0x3510724)
#30 0x0000000003f155ee clang::driver::CC1Command::Execute(llvm::ArrayRef<std::optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const (.part.0) Job.cpp:0:0
#31 0x0000000003edebec clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&, bool) const (/home/andy/local/llvm16-assert/bin/clang+0x3edebec)
#32 0x0000000003edf74d clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&, bool) const (/home/andy/local/llvm16-assert/bin/clang+0x3edf74d)
#33 0x0000000003eedccc clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&) (/home/andy/local/llvm16-assert/bin/clang+0x3eedccc)
#34 0x0000000000ad3cc6 clang_main(int, char**) (/home/andy/local/llvm16-assert/bin/clang+0xad3cc6)
#35 0x00007fa8bcd4a24e __libc_start_call_main (/nix/store/4nlgxhb09sdr51nc9hdm8az5b08vzkgx-glibc-2.35-163/lib/libc.so.6+0x2924e)
#36 0x00007fa8bcd4a309 __libc_start_main@GLIBC_2.2.5 (/nix/store/4nlgxhb09sdr51nc9hdm8az5b08vzkgx-glibc-2.35-163/lib/libc.so.6+0x29309)
#37 0x0000000000acc415 _start (/home/andy/local/llvm16-assert/bin/clang+0xacc415)
clang-16: error: clang frontend command failed with exit code 134 (use -v to see invocation)
clang version 16.0.0 (git@github.com:llvm/llvm-project.git 3f9b92d027f5d0bd23f852b66d47c5061363532d)
Target: mips-unknown-linux-unknown
Thread model: posix
InstalledDir: /home/andy/local/llvm16-assert/bin
clang-16: note: diagnostic msg: Error generating preprocessed source(s) - no preprocessable inputs.

[llvmbot]

@llvm/issue-subscribers-backend-mips

[llvmbot]

@llvm/issue-subscribers-bug

[andrewrk]

Also observed with -target powerpc-unknown-linux-unknown.

[llvmbot]

@llvm/issue-subscribers-backend-powerpc

[andrewrk]

Also observed on powerpc64 and riscv64.

[tru]

Hm. Since this happens on several backends it seems to be a problem on a higher level potentially. Not sure whom to ping here @RKSimon - do you know what this might be

[RKSimon]

udiv of 1 by X should have folded to zext(icmp_eq X, 1) in InstCombine - is something generating this in the backend?

[RKSimon]

But general division by illegal types is barely supported: #44994 #45013

[llvmbot]

@llvm/issue-subscribers-backend-mips

[andrewrk]

I very likely have more regressions to report against the release/16.x branch after this is solved. Please let me know if I need to make a workaround for this issue for now so that I can find the other possible regressions in order to ensure the quality of llvm 16.0.0 is high.

[andrewrk]

These lowerings can be done by calling the compiler_rt functions __umodei4 and __udivei4.

LLVM 15.x did it, why can't LLVM 16.x do it?

[andrewrk]

This regressed in https://github.com/llvm/llvm-project/commit/6d13b80fcb1a338ef29eefd54677fdbcdd7c0e4d. I believe reverting that commit should be sufficient to solve this issue.

cc @mgehre-amd

[nikic]

These experimental, non-standard libcalls have been removed again, in favor of generating the necessary functions directly into the module. I believe this requires some per-target configuration that likely hasn't happened for anything but the major targets.

[andrewrk]

I think that was a mistake. The whole point of compiler_rt is to have libcalls such as these. Putting the functions directly in the module is clearly a workaround for some third party project's limitations. Instead, those limitations should be solved by said third parties.

[nikic]

The situation is pretty unfortunate, but I believe the consensus is that the libgcc situation doesn't really leave any other choice. There's some discussion on https://reviews.llvm.org/D120327 and a more recent one in https://discourse.llvm.org/t/proposal-split-built-ins-from-the-rest-of-compiler-rt/67978 (which is not about the integer division builtins, but happens to touch on many of the same topics).

For the record https://reviews.llvm.org/D126644 introduced the new approach and https://reviews.llvm.org/D130076 enabled it for X86, ARM and AArch64.

[andrewrk]

Thank you for providing this context. I am sorry I missed the discussion.

I think it is too bad that LLVM is introducing yet more complicated machinery when there is already a solution to the problem, compiler-rt. Maybe the gnu folks would add these functions to libgcc if you kept the pressure up.

Can there please be an option that I can enable to make LLVM do the straightforward libcall lowerings? It worked perfectly before, and now it is regressed. I don't want every object file to have bloated compiler_rt functions in them for no reason. I also want mips, powerpc, and riscv64 to continue working flawlessly, like they did with LLVM 15.

[mgehre-amd]

I believe that the codegen part only temporarily worked in LLVM 15, but not in any earlier version of LLVM. And even in LLVM 15, the library functions __divei4 etc were not in compiler-rt, so there was never a fully working end-to-end solution.

In LLVM 16 and later, those big integer divisions are supported end-to-end on X86, ARM and AArch64. I suggest to enable it for the targets you care about by creating a PR similar to https://reviews.llvm.org/D130076.

[andrewrk]

There was, actually, a fully working end-to-end solution. Don't forget that LLVM is not merely the internal compiler implementation details of clang, but a modular and reusable compiler backend technology.

Zig 0.10.x, which uses LLVM 15.x, supports multiplication and division for arbitrary sized integers via LLVM's __divei4 etc lowerings, and these are being used for a non-heap-allocating RSA implementation, used for TLS. It not only works on x86_64 and aarch64, but also on mips, powerpc, powerpc64, and riscv64.

Given that we are already at RC2, I don't think I can realistically do your suggestion and expect it to get landed by the time 16.x is tagged. I'm staring in the face of a major regression on all four of these targets.

What should I tell my users? "Sorry, we made a mistake by using LLVM for our compiler backend. They actually don't really care about regressions to targets other than x86 and ARM, or compiler frontends other than clang."?

[mgehre-amd]

I'm not opposed to bringing _divei4 back as a fallback/alternative for the current implementation. Feel free to open a PR that reverts 6d13b80fcb1a338ef29eefd54677fdbcdd7c0e4d.

[tru]

If everyone agrees I can revert that commit on the release branch.

[nikic]

If everyone agrees I can revert that commit on the release branch.

Not sure this is a good idea, but this decision should probably be up to @efriedma-quic and @MaskRay. If we do this, these builtins will probably have to stay around forever, so there would have to be consensus for that.

Zig 0.10.x, which uses LLVM 15.x, supports multiplication and division for arbitrary sized integers via LLVM's __divei4 etc lowerings, and these are being used for a non-heap-allocating RSA implementation, used for TLS. It not only works on x86_64 and aarch64, but also on mips, powerpc, powerpc64, and riscv64.

So ... assuming the new inline expansions were correctly generated on all platforms, would those actually be usable for this use case? Does your current __divei4 implementation provide constant time guarantees?

Given that we are already at RC2, I don't think I can realistically do your suggestion and expect it to get landed by the time 16.x is tagged. I'm staring in the face of a major regression on all four of these targets.

The 16.x release is still two weeks away, so there's still time to add support for these targets.

What should I tell my users? "Sorry, we made a mistake by using LLVM for our compiler backend. They actually don't really care about regressions to targets other than x86 and ARM, or compiler frontends other than clang."?

There's clearly been a communications failure here -- from the LLVM perspective, this feature was never implemented in the first place, only a half-finished implementation stub happened to be in-tree at the time LLVM 15 was cut. It's unfortunate that this ended up being interpreted as a stable builtins ABI guarantee by zig. Now we have to deal with it somehow.

[tstellar]

These experimental, non-standard libcalls have been removed again, in favor of generating the necessary functions directly into the module. I believe this requires some per-target configuration that likely hasn't happened for anything but the major targets.

Are you referring to __umodei4 and __udivei4 ?

[MaskRay]

The original features https://reviews.llvm.org/D120327 (with __divmodei5 and __udivmodei5 compiler-rt/lib/builtins functions) and https://reviews.llvm.org/D120329 were meant to have a GCC discussion (the naming collides with de facto namespace of libgcc functions) about but the discussion has not happened, so relanding the feature (e.g. reverting 6d13b80fcb1a338ef29eefd54677fdbcdd7c0e4d) will be premature.

I agree with the point that Zig relying on some implementation stubs happening to be in LLVM 15 is unfortunate. To be safe, release/16.x should be similar to release/14.x (clean, no such function) instead of release/15.x (stub implementation) since we haven't resolved the builtins/libgcc interop problem.

[efriedma-quic]

https://reviews.llvm.org/D133691 adds some target hooks that apparently need to be implemented on a per-target basis. Extending those hooks to other targets, or adding some more reasonable default, should be straightforward to implement, and safe to cherry-pick to 16.x

[nikic]

I've put up https://reviews.llvm.org/D144871, which should avoid the legalization failure. I think this is good enough for LLVM 16, though long term it would certainly be nice if one could chose a libcall lowering if one provides those libcalls.

[andrewrk]

Thank you @nikic - I really appreciate this. I am happy to report that Zig has all compiler-rt tests passing for all targets in the llvm16 branch against release/16.x (abf32977809e8a04c9c98b9f3c72d43e37931ee9) + your one-liner to TargetLoweringBase.cpp.

[tru]

@tstellar we should make sure that this is fixed/merged before 16.0.0.

[nikic]

/cherry-pick ddccc5ba4479a36dd4821f0948e118438fbf2e56

[llvmbot]

/branch llvm/llvm-project-release-prs/issue60531

[tru]

Thanks @nikic !

[llvmbot]

/pull-request llvm/llvm-project-release-prs#332