[SDAG] avoid generating libcall to function with same name

[spatel]

Summary

This is a potentially better alternative to D131452 that also appears to avoid the infinite loop bug from:
https://github.com/llvm/llvm-project/issues/56403

This is again a minimal fix to minimize merging pain for the release. But if this makes sense, then we'd want to guard all of the RTLIB generation (and other libcalls?) with 'nobuiltin'?

[nickdesaulniers]

The langref says of nobuiltin:

nobuiltin
This indicates that the callee function at a call site is not recognized as a built-in function. LLVM will retain the original call and not replace it with equivalent code based on the semantics of the built-in function, unless the call site uses the builtin attribute. This is valid at call sites and on function declarations and definitions.

Isn't this patch now doing the opposite? If the callee is marked nobuiltin, we should retain the call explicitly as written unless the call site is attributed as builtin. Or am I misreading the langref? Otherwise, what is the point of nobuiltin in this test?

(I also think --rtlib=none needs to be recorded in IR to avoid libcalls, too).

llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

4431–4434

I feel like if TLI.getLibcallName() returns the same string as the fn we're currently ISEL'ing, then we've found a potential inf loop.

[spatel]

In D131521#3711030, @nickdesaulniers wrote:

The langref says of nobuiltin:

nobuiltin
This indicates that the callee function at a call site is not recognized as a built-in function. LLVM will retain the original call and not replace it with equivalent code based on the semantics of the built-in function, unless the call site uses the builtin attribute. This is valid at call sites and on function declarations and definitions.

Isn't this patch now doing the opposite? If the callee is marked nobuiltin, we should retain the call explicitly as written unless the call site is attributed as builtin. Or am I misreading the langref? Otherwise, what is the point of nobuiltin in this test?

I hadn't read that text in a while. I was assuming that "nobuiltin" on this function meant that it could not call builtins (and I think that was the desired behavior in the bug report). But I agree - the way it is defined is the opposite. I'm not familiar with how this is supposed to work. I see that if you build C source with "-ffreestanding", then the functions will have a different attribute -- "no-builtins" -- is that the attribute we should be detecting here?

Or we bail out with a combination of (1) this function is marked "nobuiltin" / "no-builtins" and (2) it is potentially calling a function with the same name (as suggested in the inline comment)?

[efriedma]

There are basically two different forms of LLVM "knowing" the meaning of a library call:

1. We assume we have a full-featured C library, with properties annotated in TargetLibraryInfo. This basically corresponds to -fno-builtin/"no-builtins".
2. If input IR contains certain constructs, we assume the corresponding compiler-rt/libm calls from include/llvm/IR/RuntimeLibcalls.def are available. Really, the issue here is that even if we wanted to avoid generating libcalls, we don't actually have an alternative in a lot of cases: no other lowering is implemented in LLVM.

Most the functionality from RuntimeLibcalls.def for integer/float arithmetic doesn't require any runtime, so we could in theory provide it some other way, like embedding an implementation into the object file. We've sort of started moving in this direction (see D126644).

Not sure we should be keying this off of "no-builtins"; having a C library is different from having compiler-rt builtins. We generally expect freestanding binaries to include compiler-rt builtins, but not a C library.

[nickdesaulniers]

In D131521#3712311, @spatel wrote:

I see that if you build C source with "-ffreestanding", then the functions will have a different attribute -- "no-builtins" -- is that the attribute we should be detecting here?

No (and I agree with @efriedma ).

My understanding (which itself might not be precise) is that C code can be "hosted" or "freestanding."

Hosted is the common case for userspace application developers, while freestanding is more common in embedded use cases, though these aren't always strictly the case. The Linux kernel for example hasn't yet decided whether it wants to be freestanding or not, and changes it mind per arch. *yikes*

A C program tends to implicitly link against a libc and a compiler runtime. -ffreestanding implies a libc will not be available, but it implies nothing about the compiler runtime. Instead --rtlib=none implies no compiler-rt should be linked against, but implies nothing about the libc.

The function/symbol for this patch is __muloti4 which we should expect to be provided by the compiler runtime, not the libc. So -ffreestanding is relevant for libcall optimizations that assume function symbols with specific identifiers can be assumed to have semantics specific to libc.

I don't think we have an equivalent fn attr or mdnode for --rtlib=none in IR. If we did, and it was explicitly set, then we can't assume functions like __muloti4 will be available to link against.

So I agree when @efriedma says:

We generally expect freestanding binaries to include compiler-rt builtins, but not a C library.

I don't see no-builtins specifically in the LangRef; not sure if that was a typo or worse: undocumented IR attributes. *yikes*
Oh, you weren't kidding: https://godbolt.org/z/o49oK6GYG *yikes*
Well I sure wouldn't do anything with that attr until its semantics are well documented.

[nickdesaulniers]

In D131521#3714285, @nickdesaulniers wrote:

I don't think we have an equivalent fn attr or mdnode for --rtlib=none in IR. If we did, and it was explicitly set, then we can't assume functions like __muloti4 will be available to link against.

Further, a libc like musl might compile with -ffreestanding to avoid the compiler creating inf loops in the implementations of these runtime-provided function definitions, just like the test case in this bug. They would miss out on other potential libcall optimizations the compiler could find that don't result in inf loops, but I think musl also wants individual definitions to not have cross TU dependencies, which makes picking and choosing a subset of the runtime to ship more feasible.

So if someone defined __muloti4 (as this test case does, as we do in compiler-rt) I'd imagine they'd run into a similar problem (as demonstrated by this test case) and would require a similar solution. I wonder how we build compiler-rt to avoid this dilemma?

[efriedma]

I wonder how we build compiler-rt to avoid this dilemma?

We use ad-hoc solutions that happen to work. For muloti, this particular multiply+divide pattern doesn't show up, so it's not a problem. This basically works as long as compiler-rt and the compiler are tightly coupled. It sort of breaks down when people try to build compiler-rt equivalents in other languages. Given there's now at least three implementations that are built with LLVM (compiler-rt itself, zig, and rust), maybe a more principled solution is appropriate.

I don't see no-builtins specifically in the LangRef; not sure if that was a typo or worse: undocumented IR attributes. *yikes*
Oh, you weren't kidding: https://godbolt.org/z/o49oK6GYG *yikes*
Well I sure wouldn't do anything with that attr until its semantics are well documented.

That should be documented, yes.

[spatel]

So there's a lot of potential follow-up to make this work in general.

I'm still looking at a quick fix for the release branch to avoid the particular inf-loop that was reported in #56403. Change this patch to string match the function name as suggested earlier or proceed with D131452?

[spatel]

Updated to bail out if the function name matches the libcall name.

[nickdesaulniers]

I think this is a good enough approach for now; thanks for pursuing a fix.

llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

void DAGTypeLegalizer::ExpandIntRes_XMULO(SDNode *N,
   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
   if (VT == MVT::i32)
     LC = RTLIB::MULO_I32;
   else if (VT == MVT::i64)
     LC = RTLIB::MULO_I64;
   else if (VT == MVT::i128)
     LC = RTLIB::MULO_I128;
 
-  if (LC == RTLIB::UNKNOWN_LIBCALL || !TLI.getLibcallName(LC)) {
+  // If we don't have the libcall or if the function we are compiling is the
+  // implementation of the expected libcall (avoid inf-loop), expand inline.
+  if (LC == RTLIB::UNKNOWN_LIBCALL || !TLI.getLibcallName(LC) ||
+      TLI.getLibcallName(LC) == DAG.getMachineFunction().getName()) {
     // FIXME: This is not an optimal expansion, but better than crashing.
     EVT WideVT =
         EVT::getIntegerVT(*DAG.getContext(), VT.getScalarSizeInBits() * 2);
     SDValue LHS = DAG.getNode(ISD::SIGN_EXTEND, dl, WideVT, N->getOperand(0));
     SDValue RHS = DAG.getNode(ISD::SIGN_EXTEND, dl, WideVT, N->getOperand(1));
     SDValue Mul = DAG.getNode(ISD::MUL, dl, WideVT, LHS, RHS);
     SDValue MulLo, MulHi;
     SplitInteger(Mul, MulLo, MulHi);

llvm/test/CodeGen/AArch64/umulo-128-legalisation-lowering.ll

start:
   %1 = extractvalue { i128, i1 } %0, 0
   %2 = extractvalue { i128, i1 } %0, 1
   %3 = zext i1 %2 to i8
   %4 = insertvalue { i128, i8 } undef, i128 %1, 0
   %5 = insertvalue { i128, i8 } %4, i8 %3, 1
   ret { i128, i8 } %5
 }
 
-define i128 @__muloti4(i128 %0, i128 %1, i32* nocapture nonnull writeonly align 4 %2) #4 {
+; PR56403
+; We avoid lowering the intrinsic as a libcall because this function has the same name as
+; the libcall we wanted to generate (that would create an infinite loop).
+
+define i128 @__muloti4(i128 %0, i128 %1, i32* nocapture nonnull writeonly align 4 %2) #2 {
 ; AARCH-LABEL: __muloti4:
 ; AARCH:       // %bb.0: // %Entry
-; AARCH-NEXT:    str x30, [sp, #-48]! // 8-byte Folded Spill
-; AARCH-NEXT:    stp x20, x19, [sp, #32] // 16-byte Folded Spill
-; AARCH-NEXT:    mov x19, x4
+; AARCH-NEXT:    asr x9, x1, #63
+; AARCH-NEXT:    asr x10, x3, #63
+; AARCH-NEXT:    umulh x14, x0, x2
+; AARCH-NEXT:    mov x8, x1
+; AARCH-NEXT:    mul x11, x2, x9
 ; AARCH-NEXT:    str wzr, [x4]
-; AARCH-NEXT:    add x4, sp, #8
-; AARCH-NEXT:    stp x22, x21, [sp, #16] // 16-byte Folded Spill
-; AARCH-NEXT:    mov x21, x3
-; AARCH-NEXT:    mov x20, x2
-; AARCH-NEXT:    mov x22, x1
-; AARCH-NEXT:    str xzr, [sp, #8]
-; AARCH-NEXT:    bl __muloti4
-; AARCH-NEXT:    ldr x8, [sp, #8]
-; AARCH-NEXT:    cmp x8, #0
-; AARCH-NEXT:    cset w8, ne
-; AARCH-NEXT:    tbz x22, #63, .LBB1_2
+; AARCH-NEXT:    umulh x12, x10, x0
+; AARCH-NEXT:    umulh x13, x2, x9
+; AARCH-NEXT:    madd x12, x10, x1, x12
+; AARCH-NEXT:    add x13, x13, x11
+; AARCH-NEXT:    mul x10, x10, x0
+; AARCH-NEXT:    madd x9, x3, x9, x13
+; AARCH-NEXT:    add x12, x12, x10
+; AARCH-NEXT:    adds x10, x10, x11
+; AARCH-NEXT:    mul x11, x1, x2
+; AARCH-NEXT:    adc x9, x12, x9
+; AARCH-NEXT:    umulh x13, x1, x2
+; AARCH-NEXT:    mul x12, x0, x3
+; AARCH-NEXT:    adds x11, x11, x14
+; AARCH-NEXT:    umulh x14, x0, x3
+; AARCH-NEXT:    cinc x13, x13, hs
+; AARCH-NEXT:    adds x1, x12, x11
+; AARCH-NEXT:    mul x12, x8, x3
+; AARCH-NEXT:    cinc x11, x14, hs
+; AARCH-NEXT:    mul x0, x0, x2
+; AARCH-NEXT:    adds x11, x13, x11
+; AARCH-NEXT:    umulh x13, x8, x3
+; AARCH-NEXT:    cset w14, hs
+; AARCH-NEXT:    adds x11, x12, x11
+; AARCH-NEXT:    adc x12, x13, x14
+; AARCH-NEXT:    adds x10, x11, x10
+; AARCH-NEXT:    adc x9, x12, x9
+; AARCH-NEXT:    asr x11, x1, #63
+; AARCH-NEXT:    eor x9, x9, x11
+; AARCH-NEXT:    eor x10, x10, x11
+; AARCH-NEXT:    orr x9, x10, x9
+; AARCH-NEXT:    cmp x9, #0
+; AARCH-NEXT:    cset w9, ne
+; AARCH-NEXT:    tbz x8, #63, .LBB1_2
 ; AARCH-NEXT:  // %bb.1: // %Entry
-; AARCH-NEXT:    eor x9, x21, #0x8000000000000000
-; AARCH-NEXT:    orr x9, x20, x9
-; AARCH-NEXT:    cbz x9, .LBB1_3
+; AARCH-NEXT:    eor x8, x3, #0x8000000000000000
+; AARCH-NEXT:    orr x8, x2, x8
+; AARCH-NEXT:    cbz x8, .LBB1_3
 ; AARCH-NEXT:  .LBB1_2: // %Else2
-; AARCH-NEXT:    cbz w8, .LBB1_4
+; AARCH-NEXT:    cbz w9, .LBB1_4
 ; AARCH-NEXT:  .LBB1_3: // %Then7
 ; AARCH-NEXT:    mov w8, #1
-; AARCH-NEXT:    str w8, [x19]
+; AARCH-NEXT:    str w8, [x4]
 ; AARCH-NEXT:  .LBB1_4: // %Block9
-; AARCH-NEXT:    ldp x20, x19, [sp, #32] // 16-byte Folded Reload
-; AARCH-NEXT:    ldp x22, x21, [sp, #16] // 16-byte Folded Reload
-; AARCH-NEXT:    ldr x30, [sp], #48 // 8-byte Folded Reload
 ; AARCH-NEXT:    ret
 Entry:
   store i32 0, i32* %2, align 4
   %.fr = freeze i128 %1
   %mul = tail call { i128, i1 } @llvm.smul.with.overflow.i128(i128 %0, i128 %.fr)
   %3 = icmp slt i128 %0, 0
   %4 = icmp eq i128 %.fr, -170141183460469231731687303715884105728
   %5 = and i1 %3, %4

 }
 
 declare { i128, i1 } @llvm.umul.with.overflow.i128(i128, i128) #1
 declare { i128, i1 } @llvm.smul.with.overflow.i128(i128, i128) #1
 
 attributes #0 = { nounwind readnone uwtable }
 attributes #1 = { nounwind readnone speculatable }
 attributes #2 = { nounwind }
-attributes #4 = { nounwind mustprogress nobuiltin }