[InstCombine] Optimize div/ldiv/lldiv

[xbolva00]

Summary

Expand function call to pair of sdiv and srem.

PR42818: https://bugs.llvm.org/show_bug.cgi?id=42818

[xbolva00]

Some general notes:

1, ldiv and lldiv returns agregate, div not - how to solve div case? expand it using shift and or?
2, This looks quite weird for me:

declare { i64, i64 } @ldiv(i64, i64)
declare { i64, i64 } @lldiv(i64, i64)

but this is what I got on Linux Ubuntu OS.
3, Test coverage - if any other tests, please tell me.

[xbolva00]

Fixed copy paste bug.

[xbolva00]

Fixed TLI..

[craig.topper]

Div is returning an i64 because that's the x86-64 ABI. In 32-bit mode I don't think it will return i64.

[craig.topper]

In fact in 32-bit mode x86. You'll get the return value passed by pointer with the sret attribute for all 3 functions.

[xbolva00]

Ah yes... That probably complicates many things here...

[xbolva00]

lib/Analysis/TargetLibraryInfo.cpp

1292

Can I leave TODO for 32bit versions of div?

[craig.topper]

What targets does the divl and divll code work for? Definitely doesn't work for arm on linux or i386 on linux. But those are the only ones I checked.

Would it be better to just recognize this as a builtin in clang and just emit the IR instructions?

[xbolva00]

Would it be better to just recognize this as a builtin in clang and just emit the IR instructions?

This seems like a better approach

[efriedma]

If we're going to recognize a C function that returns an aggregate, we need to be very careful that the form we're recognizing is a specific, known pattern. We need to be sure that we're recognizing a specific way of returning an aggregate, and TLI needs an API to tell transforms which specific way it recognized. We don't need to add all the possible patterns in the first patch, of course.

One concern that applies to "div" specifically, which you didn't mention, is that the order of the members of div_t isn't specified in any standard, so we also need an API to get the order on a given target.

It might be better to just handle this in clang, instead of TLI; it would be much easier to do the right thing with an AST that has the original struct type and member names. Or actually, maybe this just isn't worth doing, because the API is rarely used; I tried searching the entire Android tree, and only managed to find a couple uses.

[xbolva00]

Yeah, probably not worth to do since it is rarely used (but surprisingly latest MSVC does it)

include/llvm/Analysis/TargetLibraryInfo.def

 TLI_DEFINE_ENUM_INTERNAL(coshl)
 TLI_DEFINE_STRING_INTERNAL("coshl")
 /// long double cosl(long double x);
 TLI_DEFINE_ENUM_INTERNAL(cosl)
 TLI_DEFINE_STRING_INTERNAL("cosl")
 /// char *ctermid(char *s);
 TLI_DEFINE_ENUM_INTERNAL(ctermid)
 TLI_DEFINE_STRING_INTERNAL("ctermid")
+/// div_t div(int numerator, int denominator);
+TLI_DEFINE_ENUM_INTERNAL(div)
+TLI_DEFINE_STRING_INTERNAL("div")
 /// int execl(const char *path, const char *arg, ...);
 TLI_DEFINE_ENUM_INTERNAL(execl)
 TLI_DEFINE_STRING_INTERNAL("execl")
 /// int execle(const char *file, const char *arg, ..., char * const envp[]);
 TLI_DEFINE_ENUM_INTERNAL(execle)
 TLI_DEFINE_STRING_INTERNAL("execle")
 /// int execlp(const char *file, const char *arg, ...);
 TLI_DEFINE_ENUM_INTERNAL(execlp)

 TLI_DEFINE_ENUM_INTERNAL(ldexp)
 TLI_DEFINE_STRING_INTERNAL("ldexp")
 /// float ldexpf(float x, int n);
 TLI_DEFINE_ENUM_INTERNAL(ldexpf)
 TLI_DEFINE_STRING_INTERNAL("ldexpf")
 /// long double ldexpl(long double x, int n);
 TLI_DEFINE_ENUM_INTERNAL(ldexpl)
 TLI_DEFINE_STRING_INTERNAL("ldexpl")
+/// ldiv_t ldiv(long numerator, long denominator);
+TLI_DEFINE_ENUM_INTERNAL(ldiv)
+TLI_DEFINE_STRING_INTERNAL("ldiv")
 /// long long int llabs(long long int j);
 TLI_DEFINE_ENUM_INTERNAL(llabs)
 TLI_DEFINE_STRING_INTERNAL("llabs")
+/// lldiv_t lldiv(long long numerator, long long denominator);
+TLI_DEFINE_ENUM_INTERNAL(lldiv)
+TLI_DEFINE_STRING_INTERNAL("lldiv")
 /// double log(double x);
 TLI_DEFINE_ENUM_INTERNAL(log)
 TLI_DEFINE_STRING_INTERNAL("log")
 /// double log10(double x);
 TLI_DEFINE_ENUM_INTERNAL(log10)
 TLI_DEFINE_STRING_INTERNAL("log10")
 /// float log10f(float x);
 TLI_DEFINE_ENUM_INTERNAL(log10f)

include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
   // Integer Library Call Optimizations
   Value *optimizeFFS(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFls(CallInst *CI, IRBuilder<> &B);
   Value *optimizeAbs(CallInst *CI, IRBuilder<> &B);
   Value *optimizeIsDigit(CallInst *CI, IRBuilder<> &B);
   Value *optimizeIsAscii(CallInst *CI, IRBuilder<> &B);
   Value *optimizeToAscii(CallInst *CI, IRBuilder<> &B);
   Value *optimizeAtoi(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeDiv(CallInst *CI, IRBuilder<> &B);
   Value *optimizeStrtol(CallInst *CI, IRBuilder<> &B);
 
   // Formatting and IO Library Call Optimizations
   Value *optimizeErrorReporting(CallInst *CI, IRBuilder<> &B,
                                 int StreamArg = -1);
   Value *optimizePrintF(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSPrintF(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSnPrintF(CallInst *CI, IRBuilder<> &B);

lib/Analysis/TargetLibraryInfo.cpp

bool TargetLibraryInfoImpl::isValidProtoForLibFunc(const FunctionType &FTy,
   case LibFunc_cosf:
   case LibFunc_cosh:
   case LibFunc_cosh_finite:
   case LibFunc_coshf:
   case LibFunc_coshf_finite:
   case LibFunc_coshl:
   case LibFunc_coshl_finite:
   case LibFunc_cosl:
+    return (NumParams == 1 && FTy.getReturnType()->isFloatingPointTy() &&
+            FTy.getReturnType() == FTy.getParamType(0));
+  case LibFunc_div:
+    return (NumParams == 2 && FTy.getReturnType()->isIntegerTy() &&
+            FTy.getParamType(0)->isIntegerTy() &&
+            FTy.getParamType(1)->isIntegerTy());
   case LibFunc_exp10:
   case LibFunc_exp10_finite:
   case LibFunc_exp10f:
   case LibFunc_exp10f_finite:
   case LibFunc_exp10l:
   case LibFunc_exp10l_finite:
   case LibFunc_exp2:
   case LibFunc_exp2_finite:
bool TargetLibraryInfoImpl::isValidProtoForLibFunc(const FunctionType &FTy,
   case LibFunc_expm1f:
   case LibFunc_expm1l:
   case LibFunc_fabs:
   case LibFunc_fabsf:
   case LibFunc_fabsl:
   case LibFunc_floor:
   case LibFunc_floorf:
   case LibFunc_floorl:
+  case LibFunc_ldiv:
+  case LibFunc_lldiv:
+    return (NumParams == 2 && FTy.getReturnType()->isAggregateType() &&
+            FTy.getParamType(0)->isIntegerTy() &&
+            FTy.getParamType(1)->isIntegerTy());
   case LibFunc_log10:
   case LibFunc_log10_finite:
   case LibFunc_log10f:
   case LibFunc_log10f_finite:
   case LibFunc_log10l:
   case LibFunc_log10l_finite:
   case LibFunc_log1p:
   case LibFunc_log1pf:

lib/Transforms/Utils/BuildLibCalls.cpp

bool llvm::inferLibFuncAttributes(Function &F, const TargetLibraryInfo &TLI) {
 
   if(!isLibFreeFunction(&F, TheLibFunc) && !isReallocLikeFn(&F,  &TLI))
     Changed |= setDoesNotFreeMemory(F);
 
   if (F.getParent() != nullptr && F.getParent()->getRtLibUseGOT())
     Changed |= setNonLazyBind(F);
 
   switch (TheLibFunc) {
+  case LibFunc_div:
+  case LibFunc_ldiv:
+  case LibFunc_lldiv:
+    Changed |= setDoesNotThrow(F);
+    Changed |= setDoesNotCapture(F, 0);
+    Changed |= setOnlyReadsMemory(F, 0);
+    Changed |= setDoesNotCapture(F, 1);
+    Changed |= setOnlyReadsMemory(F, 1);
+    return Changed;
   case LibFunc_strlen:
   case LibFunc_wcslen:
     Changed |= setOnlyReadsMemory(F);
     Changed |= setDoesNotThrow(F);
     Changed |= setOnlyAccessesArgMemory(F);
     Changed |= setDoesNotCapture(F, 0);
     return Changed;
   case LibFunc_strchr:

lib/Transforms/Utils/SimplifyLibCalls.cpp

 Value *LibCallSimplifier::optimizeAtoi(CallInst *CI, IRBuilder<> &B) {
   StringRef Str;
   if (!getConstantStringInfo(CI->getArgOperand(0), Str))
     return nullptr;
 
   return convertStrToNumber(CI, Str, 10);
 }
 
+Value *LibCallSimplifier::optimizeDiv(CallInst *CI, IRBuilder<> &B) {
+  // TODO handle div
+  Value *Op0 = CI->getArgOperand(0);
+  Value *Op1 = CI->getArgOperand(1);
+  Value *V = B.CreateInsertValue(UndefValue::get(CI->getType()),
+                                 B.CreateSDiv(Op0, Op1), 0);
+  V = B.CreateInsertValue(V, B.CreateSRem(Op0, Op1), 1);
+  return V;
+}
+
 Value *LibCallSimplifier::optimizeStrtol(CallInst *CI, IRBuilder<> &B) {
   StringRef Str;
   if (!getConstantStringInfo(CI->getArgOperand(0), Str))
     return nullptr;
 
   if (!isa<ConstantPointerNull>(CI->getArgOperand(1)))
     return nullptr;
 
if (TLI->getLibFunc(*Callee, Func) && TLI->has(Func)) {
     case LibFunc_isascii:
       return optimizeIsAscii(CI, Builder);
     case LibFunc_toascii:
       return optimizeToAscii(CI, Builder);
     case LibFunc_atoi:
     case LibFunc_atol:
     case LibFunc_atoll:
       return optimizeAtoi(CI, Builder);
+    // TODO
+    // case LibFunc_div:
+    case LibFunc_ldiv:
+    case LibFunc_lldiv:
+      return optimizeDiv(CI, Builder);
     case LibFunc_strtol:
     case LibFunc_strtoll:
       return optimizeStrtol(CI, Builder);
     case LibFunc_printf:
       return optimizePrintF(CI, Builder);
     case LibFunc_sprintf:
       return optimizeSPrintF(CI, Builder);
     case LibFunc_snprintf:

test/Transforms/InstCombine/div-call.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+declare i64 @div(i32, i32)
+declare { i64, i64 } @ldiv(i64, i64)
+declare { i64, i64 } @lldiv(i64, i64)
+declare void @use(i64)
+
+define i64 @div_qout_rem(i32 %x, i32 %y) {
+; CHECK-LABEL: @div_qout_rem(
+; CHECK-NEXT:    [[DIVREM:%.*]] = tail call i64 @div(i32 [[X:%.*]], i32 [[Y:%.*]])
+; CHECK-NEXT:    ret i64 [[DIVREM]]
+;
+  %divrem = tail call i64 @div(i32 %x, i32 %y)
+  ret i64 %divrem
+}
+
+define i64 @div_qout_rem_multiuse(i32 %x, i32 %y) {
+; CHECK-LABEL: @div_qout_rem_multiuse(
+; CHECK-NEXT:    [[DIVREM:%.*]] = tail call i64 @div(i32 [[X:%.*]], i32 [[Y:%.*]])
+; CHECK-NEXT:    tail call void @use(i64 [[DIVREM]])
+; CHECK-NEXT:    ret i64 [[DIVREM]]
+;
+  %divrem = tail call i64 @div(i32 %x, i32 %y)
+  tail call void @use(i64 %divrem)
+  ret i64 %divrem
+}
+
+define i32 @div_qout(i32 %x, i32 %y) {
+; CHECK-LABEL: @div_qout(
+; CHECK-NEXT:    [[DIVREM:%.*]] = tail call i64 @div(i32 [[X:%.*]], i32 [[Y:%.*]])
+; CHECK-NEXT:    [[QUOT:%.*]] = trunc i64 [[DIVREM]] to i32
+; CHECK-NEXT:    ret i32 [[QUOT]]
+;
+  %divrem = tail call i64 @div(i32 %x, i32 %y)
+  %quot = trunc i64 %divrem to i32
+  ret i32 %quot
+}
+
+define i32 @div_rem(i32 %x, i32 %y) {
+; CHECK-LABEL: @div_rem(
+; CHECK-NEXT:    [[DIVREM:%.*]] = tail call i64 @div(i32 [[X:%.*]], i32 [[Y:%.*]])
+; CHECK-NEXT:    [[L:%.*]] = lshr i64 [[DIVREM]], 32
+; CHECK-NEXT:    [[REM:%.*]] = trunc i64 [[L]] to i32
+; CHECK-NEXT:    ret i32 [[REM]]
+;
+  %divrem = tail call i64 @div(i32 %x, i32 %y)
+  %l = lshr i64 %divrem, 32
+  %rem = trunc i64 %l to i32
+  ret i32 %rem
+}
+
+define { i64, i64 } @ldiv_qout_rem(i64 %x, i64 %y) {
+; CHECK-LABEL: @ldiv_qout_rem(
+; CHECK-NEXT:    [[TMP1:%.*]] = sdiv i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = insertvalue { i64, i64 } undef, i64 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = srem i64 [[X]], [[Y]]
+; CHECK-NEXT:    [[TMP4:%.*]] = insertvalue { i64, i64 } [[TMP2]], i64 [[TMP3]], 1
+; CHECK-NEXT:    ret { i64, i64 } [[TMP4]]
+;
+  %divrem = tail call { i64, i64 } @ldiv(i64 %x, i64 %y)
+  ret { i64, i64 } %divrem
+}
+
+define i64 @ldiv_qout(i64 %x, i64 %y) {
+; CHECK-LABEL: @ldiv_qout(
+; CHECK-NEXT:    [[TMP1:%.*]] = sdiv i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
+;
+  %divrem = tail call { i64, i64 } @ldiv(i64 %x, i64 %y)
+  %quot = extractvalue { i64, i64 } %divrem, 0
+  ret i64 %quot
+}
+
+define i64 @ldiv_rem(i64 %x, i64 %y) {
+; CHECK-LABEL: @ldiv_rem(
+; CHECK-NEXT:    [[TMP1:%.*]] = srem i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
+;
+  %divrem = tail call { i64, i64 } @ldiv(i64 %x, i64 %y)
+  %rem = extractvalue { i64, i64 } %divrem, 1
+  ret i64 %rem
+}
+
+define { i64, i64 } @lldiv_qout_rem(i64 %x, i64 %y) {
+; CHECK-LABEL: @lldiv_qout_rem(
+; CHECK-NEXT:    [[TMP1:%.*]] = sdiv i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = insertvalue { i64, i64 } undef, i64 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = srem i64 [[X]], [[Y]]
+; CHECK-NEXT:    [[TMP4:%.*]] = insertvalue { i64, i64 } [[TMP2]], i64 [[TMP3]], 1
+; CHECK-NEXT:    ret { i64, i64 } [[TMP4]]
+;
+  %divrem = tail call { i64, i64 } @lldiv(i64 %x, i64 %y)
+  ret { i64, i64 } %divrem
+}
+
+define i64 @lldiv_qout(i64 %x, i64 %y) {
+; CHECK-LABEL: @lldiv_qout(
+; CHECK-NEXT:    [[TMP1:%.*]] = sdiv i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
+;
+  %divrem = tail call { i64, i64 } @lldiv(i64 %x, i64 %y)
+  %quot = extractvalue { i64, i64 } %divrem, 0
+  ret i64 %quot
+}
+
+define i64 @lldiv_rem(i64 %x, i64 %y) {
+; CHECK-LABEL: @lldiv_rem(
+; CHECK-NEXT:    [[TMP1:%.*]] = srem i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
+;
+  %divrem = tail call { i64, i64 } @lldiv(i64 %x, i64 %y)
+  %rem = extractvalue { i64, i64 } %divrem, 1
+  ret i64 %rem
+}

unittests/Analysis/TargetLibraryInfoTest.cpp

parseAssembly(
       "declare float @cabsf([2 x float])\n"
       "declare x86_fp80 @cabsl([2 x x86_fp80])\n"
       "declare double @cos(double)\n"
       "declare float @cosf(float)\n"
       "declare double @cosh(double)\n"
       "declare float @coshf(float)\n"
       "declare x86_fp80 @coshl(x86_fp80)\n"
       "declare x86_fp80 @cosl(x86_fp80)\n"
+      "declare i64 @div(i32, i32)\n"
       "declare i8* @ctermid(i8*)\n"
       "declare double @exp(double)\n"
       "declare double @exp2(double)\n"
       "declare float @exp2f(float)\n"
       "declare x86_fp80 @exp2l(x86_fp80)\n"
       "declare float @expf(float)\n"
       "declare x86_fp80 @expl(x86_fp80)\n"
       "declare double @expm1(double)\n"