[InstCombine] avoid generating mul intrinsic that lowers as a libcall

[spatel]

Summary

This is a minimal fix for issue #56403. We need to avoid creating a libcall to the libcall itself, or we get an infinite loop.

As noted in the bug report, this is not a complete solution. We should be guarding all intrinsic transforms like this with some kind of check to ensure we are not lowering to a libcall, but I don't think that query exists in IR.

I drafted an alternate patch that would move this transform to AggressiveInstCombine and check TTI.isTypeLegal(), but that might go beyond what we want (for example: don't do the transform for i8 types on AArch64?).

[RKSimon]

Makes sense to me, and should be relatively trivial to merge into 15.x

@andrewrk @nickdesaulniers any thoughts?

[spatel]

In D131452#3709394, @RKSimon wrote:

Makes sense to me, and should be relatively trivial to merge into 15.x

Yes, I intentionally made this patch minimal to make merging easy. That does leave out some non-obvious context though - the existing transforms are tested extensively in 6 different files:
fb38b7aab3f23604611 (D65143)
473a063a5e13812878 (D65144)
35fa7b8ad83e6cddb38

This patch doesn't affect any of the motivating types (scalars from i8 to i64 and vectors with those elements).

Also for reference;

/// Legal integers and common types are considered desirable. This is used to
/// avoid creating instructions with types that may not be supported well by the
/// the backend.
/// NOTE: This treats i8, i16 and i32 specially because they are common
///       types in frontend languages.
bool InstCombinerImpl::isDesirableIntType(unsigned BitWidth) const {

[efriedma]

I wonder if we should have some more comprehensive solution to the whole "recursive call" thing, as opposed to the ad-hoc transform avoidance we currently use... but this seems fine for now.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4066

The comment here should more specifically call out the possibility of a recursive call. If we have a non-legal divide, we're probably generating a libcall anyway...

[spatel]

Patch updated:
Mention the recursive call potential of the transform in the code comment.

[spatel]

Abandoning - we proceeded with a codegen fix instead (D131521).

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

default:
                                                                   m_Value(X)),
                                                           m_Instruction(Mul)),
                                              m_Deferred(X))),
                              m_Instruction(Div))))) {
     NeedNegation = Pred == ICmpInst::Predicate::ICMP_EQ;
   } else
     return nullptr;
 
+  // Bail out if the type is not desirable. The intrinsic might be lowered as a
+  // function call if the target can't handle the type. This could even be the
+  // implementation of that libcall, and that would cause an infinite loop in
+  // the generated code.
+  //
+  // We allow the transform for vectors under the assumption that those will
+  // always be expanded inline.
+  Type *Ty = X->getType();
+  if (Ty->isIntegerTy() && !isDesirableIntType(Ty->getPrimitiveSizeInBits()))
+    return nullptr;
+
   BuilderTy::InsertPointGuard Guard(Builder);
   // If the pattern included (x * y), we'll want to insert new instructions
   // right before that original multiplication so that we can replace it.
   bool MulHadOtherUses = Mul && !Mul->hasOneUse();
   if (MulHadOtherUses)
     Builder.SetInsertPoint(Mul);
 
   Function *F = Intrinsic::getDeclaration(I.getModule(),
                                           Div->getOpcode() == Instruction::UDiv
                                               ? Intrinsic::umul_with_overflow
                                               : Intrinsic::smul_with_overflow,
-                                          X->getType());
+                                          Ty);
   CallInst *Call = Builder.CreateCall(F, {X, Y}, "mul");
 
   // If the multiplication was used elsewhere, to ensure that we don't leave
   // "duplicate" instructions, replace uses of that original multiplication
   // with the multiplication result from the with.overflow intrinsic.
   if (MulHadOtherUses)
     replaceInstUsesWith(*Mul, Builder.CreateExtractValue(Call, 0, "mul.val"));
 

llvm/test/Transforms/PhaseOrdering/AArch64/mul-ov.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes="default<O3>" -S < %s  | FileCheck %s
 
+; PR56403
+; We do not want to form a mul-with-overflow intrinsic here because
+; that could be lowered to a runtime libcall: __muloti4!
+
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-unknown-linux-unknown"
 
 define i128 @__muloti4(i128 %0, i128 %1, i32* nonnull align 4 %2) {
 ; CHECK-LABEL: @__muloti4(
 ; CHECK-NEXT:  Entry:
-; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i128 [[TMP1:%.*]]
 ; CHECK-NEXT:    store i32 0, i32* [[TMP2:%.*]], align 4
-; CHECK-NEXT:    [[MUL:%.*]] = tail call { i128, i1 } @llvm.smul.with.overflow.i128(i128 [[TMP0:%.*]], i128 [[DOTFR]])
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i128 [[TMP0]], 0
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i128 [[DOTFR]], -170141183460469231731687303715884105728
-; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP3]], [[TMP4]]
-; CHECK-NEXT:    br i1 [[TMP5]], label [[THEN7:%.*]], label [[ELSE2:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = mul i128 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i128 [[TMP0]], 0
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i128 [[TMP1]], -170141183460469231731687303715884105728
+; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[TMP4]], i1 [[TMP5]], i1 false
+; CHECK-NEXT:    br i1 [[TMP6]], label [[THEN7:%.*]], label [[ELSE2:%.*]]
 ; CHECK:       Else2:
-; CHECK-NEXT:    [[MUL_OV:%.*]] = extractvalue { i128, i1 } [[MUL]], 1
-; CHECK-NEXT:    br i1 [[MUL_OV]], label [[THEN7]], label [[BLOCK9:%.*]]
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i128 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BLOCK9:%.*]], label [[THEN3:%.*]]
+; CHECK:       Then3:
+; CHECK-NEXT:    [[TMP7:%.*]] = sdiv i128 [[TMP3]], [[TMP0]]
+; CHECK-NEXT:    [[DOTNOT3:%.*]] = icmp eq i128 [[TMP7]], [[TMP1]]
+; CHECK-NEXT:    br i1 [[DOTNOT3]], label [[BLOCK9]], label [[THEN7]]
 ; CHECK:       Then7:
 ; CHECK-NEXT:    store i32 1, i32* [[TMP2]], align 4
 ; CHECK-NEXT:    br label [[BLOCK9]]
 ; CHECK:       Block9:
-; CHECK-NEXT:    [[MUL_VAL:%.*]] = extractvalue { i128, i1 } [[MUL]], 0
-; CHECK-NEXT:    ret i128 [[MUL_VAL]]
+; CHECK-NEXT:    ret i128 [[TMP3]]
 ;
 Entry:
   %3 = alloca i128, align 16
   %4 = alloca i128, align 16
   store i32 0, i32* %2, align 4
   %5 = mul i128 %0, %1
   store i128 %5, i128* %3, align 16
   %6 = icmp slt i128 %0, 0