[AArch64] Disable __muloti4 libcalls for AArch64

[sebastianpoeplau]

Summary

The library function only exists in compiler-rt, not in libgcc.

This is consistent with similar changes for x86-64 (D109385),
x86 (D108928), ARM (D108842), MIPS (D108844), PPC (D108936), and
RISC-V (D108939).

[sebastianpoeplau]

Removed internal ticket identifiers from the commit message

[sebastianpoeplau]

The build failure on Debian is caused by a clangd unit test that seems unrelated to AArch64 codegen; I'm assuming for now that the failure isn't caused by this change.

[sebastianpoeplau]

Ping

[sdesmalen]

From reading the thread on https://github.com/llvm/llvm-project/issues/16778 (which is closed, although the issue doesn't seem resolved), this is a stop-gap for toolchains that don't include an implementation for __muloti4. An implementation seems to exist in compiler-rt, but compiler-rt isn't linked with by default. It seems unfortunate that there is no way to still emit a call to __muloti4 when we do link with compiler-rt, but from reading that thread there is currently no way to tell LLVM that an implementation of __muloti4 is available.

So I'm happy to accept this change, but please wait for a few days to land it to see if @rengolin or @nickdesaulniers has any comments.

[sebastianpoeplau]

From reading the thread on https://github.com/llvm/llvm-project/issues/16778 (which is closed, although the issue doesn't seem resolved), this is a stop-gap for toolchains that don't include an implementation for __muloti4. An implementation seems to exist in compiler-rt, but compiler-rt isn't linked with by default. It seems unfortunate that there is no way to still emit a call to __muloti4 when we do link with compiler-rt, but from reading that thread there is currently no way to tell LLVM that an implementation of __muloti4 is available.

That's my understanding as well.

So I'm happy to accept this change, but please wait for a few days to land it to see if @rengolin or @nickdesaulniers has any comments.

Will do. Thanks for your review!

[rengolin]

In D141836#4073296, @sebastianpoeplau wrote:

From reading the thread on https://github.com/llvm/llvm-project/issues/16778 (which is closed, although the issue doesn't seem resolved), this is a stop-gap for toolchains that don't include an implementation for __muloti4. An implementation seems to exist in compiler-rt, but compiler-rt isn't linked with by default. It seems unfortunate that there is no way to still emit a call to __muloti4 when we do link with compiler-rt, but from reading that thread there is currently no way to tell LLVM that an implementation of __muloti4 is available.

That's my understanding as well.

Every few years I come to this issue via bugs or reviews. I am shocked that this is still an issue today...

This isn't by far a good solution, but it will work around the "original" problem, just not the "actual" problem.

I don't mind this going in as is, but I'll let @nickdesaulniers approve to be sure I'm not missing anything.

@echristo FYI

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

607

please, add a comment:

// TODO: Link compiler-rt's builtins by default in Clang once and for all
// See: https://github.com/llvm/llvm-project/issues/16778

[echristo]

The right move here is to check about muloti, not disable it unless the
aarch64 backend doesn't need it.

[rengolin]

In D141836#4074521, @echristo wrote:

The right move here is to check about muloti, not disable it unless the
aarch64 backend doesn't need it.

You mean __has_builtin?

The problem is that LLVM itself lowers the call for generic code, because it thinks there is support (since the target reports there is), so users can't do much to avoid it.

This "fix" is just telling LLVM there isn't such call, and so it lowers to standard arithmetic. Checking clang is linking RT is not fool-proof either (multi-stage compilation).

My view is that it's wrong to say we have that builtin when it's possible not to have, so I'd err in the side of caution and only re-enable it when we make sure we know when it's safe to lower.

In the end, the generated code is probably a bit worse than the implemented one, but still works, so it won't break anything.

[sebastianpoeplau]

Added requested comment

[echristo]

I would hypothesize that the number of platforms where compiler-rt is used to link aarch64 code is greater than the number that don't and there's work to make linking with compiler-rt (https://github.com/llvm/llvm-project/tree/main/llvm-libgcc) in order to replace uses on other platforms. In addition, while my employment meant I couldn't add this to libgcc in the past there's no reason why it couldn't be added as well. Has anyone tried?

[nickdesaulniers]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103034

[cjdb]

In D141836#4080778, @echristo wrote:

I would hypothesize that the number of platforms where compiler-rt is used to link aarch64 code is greater than the number that don't and there's work to make linking with compiler-rt (https://github.com/llvm/llvm-project/tree/main/llvm-libgcc) in order to replace uses on other platforms. In addition, while my employment meant I couldn't add this to libgcc in the past there's no reason why it couldn't be added as well. Has anyone tried?

+1 to trying to add these to libgcc instead of removing from compiler-rt. Both ChromeOS and FreeBSD use llvm-libgcc to make compiler-rt appear as if it is libgcc (but it's still compiler-rt), and this may have unintended consequences. I suspect that there are more systems that do this too.

[rengolin]

In D141836#4080877, @cjdb wrote:

+1 to trying to add these to libgcc instead of removing from compiler-rt.

To be clear, no one is suggesting to remove this from compiler-rt, just not enable by default for LLVM lowering on AArch64. Very different things.

There are some Linux distros and FreeBSD who do the same thing, and they'd also be affected. But since this is a build issue, we could work around it by some build flag or triple check that enables it.

there's no reason why it couldn't be added as well. Has anyone tried?

Honestly, I don't know, and am still a little surprised that it's still not there yet...

But the main problem back then, and is still relevant now, is that adding it to libgcc won't fix for the previous versions, which will be available for years on distros, builds, etc.

I think this is an orthogonal issue. Sure, it would be nice to have that in libgcc, and it would eventually fix the problem, but it wouldn't make a difference today.

I'm also surprised that this is still the only (?) case where we have that kind of a problem. I'd expect it to be more widespread...

[rengolin]

Just to make sure there's no panic, I'm blocking the revision until more people looked over. I'll remove once we have a number of approvals from people in different positions.

I'm also adding Bero (Mandriva's maintainer), David (our FreeBSD representative) and Hans (Chromium) to check over their side.

Feel free to add more people.

[efriedma]

I think there just isn't any good way forward that imposes demands on the "system" libgcc/compiler-rt. Adding or modifying APIs to libgcc/compiler-rt simply isn't practical given that programs are linked using implementations distributed independent from the compiler. Even if we convince the gcc developers to add __muloti4, it'll be years before it actually ships in Linux distributions. There are bunch of APIs we'd want if it were straightforward to add new ones; not just mul-with-overflow, but also saturating float-to-int, clz with zero defined, memory functions optimized for small sizes, outlined prologue/epilogue sequences, existing functions with optimized ABI, math functions that don't mess with errno, etc.

Long-term, I think the only practical way forward is to teach LLVM to embed the definitions of helper functions such as "mul-with-overflow" as weak symbols into the files that use them, so we can just assume they're always available.

I don't have a strong opinion on whether the current patch is the right way forward short-term. Maybe restrict the change to glibc/musl targets, though, since we generally use compiler-rt on other aarch64 targets (and it's included __muloti4 for ages).

[manojgupta]

At least for ChromeOS, as long as this change is limited to clang not making calls to it and function is not removed from compiler-rt, it works for us . We ship a libgcc_s.so using compiler-rt sources so we need so compatibility there so that older binaries keep working.

[theraven]

This seems like a regression for FreeBSD. This function was added to compiler-rt before we officially supported AArch64 and so I'm pretty sure it's shipped in every AArch64 version of FreeBSD, even Tier 2 releases.

[rengolin]

Ok, created a proposal to split builtins: https://discourse.llvm.org/t/proposal-split-built-ins-from-the-rest-of-compiler-rt/67978

If there's a better option, it hopefully will be reached there.

[echristo]

Wanted to say thank you for your work on that proposal - I think it sets
the right tone and consensus is looking nice :)

Thanks!

-eric

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

AArch64TargetLowering::AArch64TargetLowering(const TargetMachine &TM,
   setOperationAction(ISD::SSUBO, MVT::i64, Custom);
   setOperationAction(ISD::USUBO, MVT::i32, Custom);
   setOperationAction(ISD::USUBO, MVT::i64, Custom);
   setOperationAction(ISD::SMULO, MVT::i32, Custom);
   setOperationAction(ISD::SMULO, MVT::i64, Custom);
   setOperationAction(ISD::UMULO, MVT::i32, Custom);
   setOperationAction(ISD::UMULO, MVT::i64, Custom);
 
+  // The MULO libcall is not part of libgcc, only compiler-rt.
+  //
+  // TODO: Link compiler-rt's builtins by default in Clang once and for all
+  // See: https://github.com/llvm/llvm-project/issues/16778
+  setLibcallName(RTLIB::MULO_I128, nullptr);
+
   setOperationAction(ISD::ADDCARRY, MVT::i32, Custom);
   setOperationAction(ISD::ADDCARRY, MVT::i64, Custom);
   setOperationAction(ISD::SUBCARRY, MVT::i32, Custom);
   setOperationAction(ISD::SUBCARRY, MVT::i64, Custom);
   setOperationAction(ISD::SADDO_CARRY, MVT::i32, Custom);
   setOperationAction(ISD::SADDO_CARRY, MVT::i64, Custom);
   setOperationAction(ISD::SSUBO_CARRY, MVT::i32, Custom);
   setOperationAction(ISD::SSUBO_CARRY, MVT::i64, Custom);

llvm/test/CodeGen/AArch64/i128-math.ll

 ; CHECK-NEXT:    ret
   %1 = mul i128 %x, %y
   ret i128 %1
 }
 
 define { i128, i8 } @i128_checked_mul(i128 %x, i128 %y) {
 ; CHECK-LABEL: i128_checked_mul:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    stp x30, xzr, [sp, #-16]! // 8-byte Folded Spill
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    .cfi_offset w30, -16
-; CHECK-NEXT:    add x4, sp, #8
-; CHECK-NEXT:    bl __muloti4
-; CHECK-NEXT:    ldr x8, [sp, #8]
-; CHECK-NEXT:    cmp x8, #0
+; CHECK-NEXT:    asr x8, x1, #63
+; CHECK-NEXT:    asr x9, x3, #63
+; CHECK-NEXT:    mul x10, x2, x8
+; CHECK-NEXT:    umulh x11, x2, x8
+; CHECK-NEXT:    umulh x12, x9, x0
+; CHECK-NEXT:    mul x13, x9, x0
+; CHECK-NEXT:    add x11, x11, x10
+; CHECK-NEXT:    madd x9, x9, x1, x12
+; CHECK-NEXT:    madd x8, x3, x8, x11
+; CHECK-NEXT:    adds x10, x13, x10
+; CHECK-NEXT:    umulh x11, x0, x2
+; CHECK-NEXT:    add x9, x9, x13
+; CHECK-NEXT:    mul x13, x1, x2
+; CHECK-NEXT:    adc x9, x9, x8
+; CHECK-NEXT:    umulh x12, x1, x2
+; CHECK-NEXT:    mul x8, x0, x3
+; CHECK-NEXT:    adds x11, x13, x11
+; CHECK-NEXT:    umulh x13, x0, x3
+; CHECK-NEXT:    cinc x12, x12, hs
+; CHECK-NEXT:    adds x8, x8, x11
+; CHECK-NEXT:    mul x0, x0, x2
+; CHECK-NEXT:    cinc x11, x13, hs
+; CHECK-NEXT:    mul x13, x1, x3
+; CHECK-NEXT:    adds x11, x12, x11
+; CHECK-NEXT:    umulh x12, x1, x3
+; CHECK-NEXT:    cset w14, hs
+; CHECK-NEXT:    adds x11, x13, x11
+; CHECK-NEXT:    adc x12, x12, x14
+; CHECK-NEXT:    adds x10, x11, x10
+; CHECK-NEXT:    asr x11, x8, #63
+; CHECK-NEXT:    adc x9, x12, x9
+; CHECK-NEXT:    cmp x10, x11
+; CHECK-NEXT:    mov x1, x8
+; CHECK-NEXT:    ccmp x9, x11, #0, eq
 ; CHECK-NEXT:    cset w2, eq
-; CHECK-NEXT:    ldr x30, [sp], #16 // 8-byte Folded Reload
 ; CHECK-NEXT:    ret
   %1 = tail call { i128, i1 } @llvm.smul.with.overflow.i128(i128 %x, i128 %y)
   %2 = extractvalue { i128, i1 } %1, 0
   %3 = extractvalue { i128, i1 } %1, 1
   %4 = xor i1 %3, true
   %5 = zext i1 %4 to i8
   %6 = insertvalue { i128, i8 } undef, i128 %2, 0
   %7 = insertvalue { i128, i8 } %6, i8 %5, 1
   ret { i128, i8 } %7
 }
 
 define { i128, i8 } @i128_overflowing_mul(i128 %x, i128 %y) {
 ; CHECK-LABEL: i128_overflowing_mul:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    stp x30, xzr, [sp, #-16]! // 8-byte Folded Spill
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    .cfi_offset w30, -16
-; CHECK-NEXT:    add x4, sp, #8
-; CHECK-NEXT:    bl __muloti4
-; CHECK-NEXT:    ldr x8, [sp, #8]
-; CHECK-NEXT:    cmp x8, #0
+; CHECK-NEXT:    asr x8, x1, #63
+; CHECK-NEXT:    asr x9, x3, #63
+; CHECK-NEXT:    mul x10, x2, x8
+; CHECK-NEXT:    umulh x11, x2, x8
+; CHECK-NEXT:    umulh x12, x9, x0
+; CHECK-NEXT:    mul x13, x9, x0
+; CHECK-NEXT:    add x11, x11, x10
+; CHECK-NEXT:    madd x9, x9, x1, x12
+; CHECK-NEXT:    madd x8, x3, x8, x11
+; CHECK-NEXT:    adds x10, x13, x10
+; CHECK-NEXT:    umulh x11, x0, x2
+; CHECK-NEXT:    add x9, x9, x13
+; CHECK-NEXT:    mul x13, x1, x2
+; CHECK-NEXT:    adc x9, x9, x8
+; CHECK-NEXT:    umulh x12, x1, x2
+; CHECK-NEXT:    mul x8, x0, x3
+; CHECK-NEXT:    adds x11, x13, x11
+; CHECK-NEXT:    umulh x13, x0, x3
+; CHECK-NEXT:    cinc x12, x12, hs
+; CHECK-NEXT:    adds x8, x8, x11
+; CHECK-NEXT:    mul x0, x0, x2
+; CHECK-NEXT:    cinc x11, x13, hs
+; CHECK-NEXT:    mul x13, x1, x3
+; CHECK-NEXT:    adds x11, x12, x11
+; CHECK-NEXT:    umulh x12, x1, x3
+; CHECK-NEXT:    cset w14, hs
+; CHECK-NEXT:    adds x11, x13, x11
+; CHECK-NEXT:    adc x12, x12, x14
+; CHECK-NEXT:    adds x10, x11, x10
+; CHECK-NEXT:    asr x11, x8, #63
+; CHECK-NEXT:    adc x9, x12, x9
+; CHECK-NEXT:    cmp x10, x11
+; CHECK-NEXT:    mov x1, x8
+; CHECK-NEXT:    ccmp x9, x11, #0, eq
 ; CHECK-NEXT:    cset w2, ne
-; CHECK-NEXT:    ldr x30, [sp], #16 // 8-byte Folded Reload
 ; CHECK-NEXT:    ret
   %1 = tail call { i128, i1 } @llvm.smul.with.overflow.i128(i128 %x, i128 %y)
   %2 = extractvalue { i128, i1 } %1, 0
   %3 = extractvalue { i128, i1 } %1, 1
   %4 = zext i1 %3 to i8
   %5 = insertvalue { i128, i8 } undef, i128 %2, 0
   %6 = insertvalue { i128, i8 } %5, i8 %4, 1
   ret { i128, i8 } %6
 }
 
 define i128 @i128_saturating_mul(i128 %x, i128 %y) {
 ; CHECK-LABEL: i128_saturating_mul:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    str x30, [sp, #-32]! // 8-byte Folded Spill
-; CHECK-NEXT:    .cfi_def_cfa_offset 32
-; CHECK-NEXT:    stp x20, x19, [sp, #16] // 16-byte Folded Spill
-; CHECK-NEXT:    .cfi_offset w19, -8
-; CHECK-NEXT:    .cfi_offset w20, -16
-; CHECK-NEXT:    .cfi_offset w30, -32
-; CHECK-NEXT:    add x4, sp, #8
-; CHECK-NEXT:    mov x19, x3
-; CHECK-NEXT:    mov x20, x1
-; CHECK-NEXT:    str xzr, [sp, #8]
-; CHECK-NEXT:    bl __muloti4
-; CHECK-NEXT:    ldr x8, [sp, #8]
-; CHECK-NEXT:    eor x9, x19, x20
-; CHECK-NEXT:    ldp x20, x19, [sp, #16] // 16-byte Folded Reload
-; CHECK-NEXT:    asr x9, x9, #63
-; CHECK-NEXT:    eor x10, x9, #0x7fffffffffffffff
+; CHECK-NEXT:    asr x8, x1, #63
+; CHECK-NEXT:    asr x9, x3, #63
+; CHECK-NEXT:    umulh x14, x1, x2
+; CHECK-NEXT:    mul x10, x2, x8
+; CHECK-NEXT:    umulh x11, x2, x8
+; CHECK-NEXT:    umulh x12, x9, x0
+; CHECK-NEXT:    mul x13, x9, x0
+; CHECK-NEXT:    add x11, x11, x10
+; CHECK-NEXT:    madd x9, x9, x1, x12
+; CHECK-NEXT:    madd x8, x3, x8, x11
+; CHECK-NEXT:    adds x10, x13, x10
+; CHECK-NEXT:    umulh x12, x0, x2
+; CHECK-NEXT:    add x9, x9, x13
+; CHECK-NEXT:    mul x11, x1, x2
+; CHECK-NEXT:    adc x8, x9, x8
+; CHECK-NEXT:    mul x9, x0, x3
+; CHECK-NEXT:    adds x11, x11, x12
+; CHECK-NEXT:    umulh x12, x0, x3
+; CHECK-NEXT:    cinc x13, x14, hs
+; CHECK-NEXT:    adds x9, x9, x11
+; CHECK-NEXT:    cinc x11, x12, hs
+; CHECK-NEXT:    mul x12, x1, x3
+; CHECK-NEXT:    adds x11, x13, x11
+; CHECK-NEXT:    umulh x13, x1, x3
+; CHECK-NEXT:    cset w14, hs
+; CHECK-NEXT:    adds x11, x12, x11
+; CHECK-NEXT:    adc x12, x13, x14
+; CHECK-NEXT:    adds x10, x11, x10
+; CHECK-NEXT:    adc x8, x12, x8
+; CHECK-NEXT:    asr x11, x9, #63
+; CHECK-NEXT:    eor x8, x8, x11
+; CHECK-NEXT:    eor x10, x10, x11
+; CHECK-NEXT:    orr x8, x10, x8
+; CHECK-NEXT:    eor x10, x3, x1
+; CHECK-NEXT:    mul x11, x0, x2
+; CHECK-NEXT:    asr x10, x10, #63
+; CHECK-NEXT:    eor x12, x10, #0x7fffffffffffffff
 ; CHECK-NEXT:    cmp x8, #0
-; CHECK-NEXT:    csinv x0, x0, x9, eq
-; CHECK-NEXT:    csel x1, x10, x1, ne
-; CHECK-NEXT:    ldr x30, [sp], #32 // 8-byte Folded Reload
+; CHECK-NEXT:    csinv x0, x11, x10, eq
+; CHECK-NEXT:    csel x1, x12, x9, ne
 ; CHECK-NEXT:    ret
   %1 = tail call { i128, i1 } @llvm.smul.with.overflow.i128(i128 %x, i128 %y)
   %2 = extractvalue { i128, i1 } %1, 0
   %3 = extractvalue { i128, i1 } %1, 1
   %4 = xor i128 %y, %x
   %5 = icmp sgt i128 %4, -1
   %6 = select i1 %5, i128 170141183460469231731687303715884105727, i128 -170141183460469231731687303715884105728
   %7 = select i1 %3, i128 %6, i128 %2
   ret i128 %7
 }