[DAGCombiner] try to convert pow(x, 1/3) to cbrt(x)

[spatel]

Summary

This is a follow-up suggested in D51630 and originally proposed as an IR transform in D49040.

Copying the motivational statement by @evandro from that patch:
"This transformation helps some benchmarks in SPEC CPU2000 and CPU2006, such as 188.ammp, 447.dealII, 453.povray, and especially 300.twolf, as well as some proprietary benchmarks. Otherwise, no regressions on x86-64 or A64."

I'm proposing to add only the minimum support for a DAG node here. Since we don't have an LLVM IR intrinsic for cbrt, and there are no other DAG ways to create a FCBRT node yet, I don't think we need to worry about DAG builder, legalization, a strict variant, etc. We should be able to expand as needed when adding more functionality/transforms. For reference, these are transform suggestions currently listed in SimplifyLibCalls.cpp:

//   * cbrt(expN(X))  -> expN(x/3)
//   * cbrt(sqrt(x))  -> pow(x,1/6)
//   * cbrt(cbrt(x))  -> pow(x,1/9)

Also, given that we bail out on long double for now, I don't think there will be any logical differences between platforms, but let me know if you'd like to see test coverage for other targets.

[lebedev.ri]

test/CodeGen/X86/pow.ll

2 ↗

(On Diff #164283)

There is _mm_pow_ps() and _mm_cbrt_ps() in SSE.
Maybe there should be an -mattr=+sse runline?

[spatel]

test/CodeGen/X86/pow.ll

2 ↗

(On Diff #164283)

I didn't know about those. They're SVML library calls, right? Or is there an x86 hardware target somewhere out there?

There is support for the pow SVML call in LLVM, but I don't see cbrt anywhere. Either way, I'm not sure how that's testable here because SVML transforms happen in IR currently ( related discussion in: https://bugs.llvm.org/show_bug.cgi?id=38528 )

mattr=+sse is a requirement of x86-64, so how does making that explicit change things?

[lebedev.ri]

Looks good, but would be good for someone else to take a look, too.

lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

181–183 ↗

(On Diff #164283)

Will strict_fcbrt be needed, too?

[spatel]

In D51753#1232044, @lebedev.ri wrote:

Looks good, but would be good for someone else to take a look, too.

Thanks! I'll wait a few days at least for more feedback.

lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

181–183 ↗

(On Diff #164283)

Not sure. IIUC, we would want that if there's a possibility of converting *from* cbrt to something else. Here, we're only transforming *to* cbrt, so I don't see how a strict sibling would come into play at this point.

llvm/trunk/include/llvm/CodeGen/ISDOpcodes.h

enum NodeType {
     ADDRSPACECAST,
 
     /// FP16_TO_FP, FP_TO_FP16 - These operators are used to perform promotions
     /// and truncation for half-precision (16 bit) floating numbers. These nodes
     /// form a semi-softened interface for dealing with f16 (as an i16), which
     /// is often a storage-only type but has native conversions.
     FP16_TO_FP, FP_TO_FP16,
 
-    /// FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW,
-    /// FLOG, FLOG2, FLOG10, FEXP, FEXP2,
-    /// FCEIL, FTRUNC, FRINT, FNEARBYINT, FROUND, FFLOOR - Perform various unary
-    /// floating point operations. These are inspired by libm.
-    FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW,
+    /// Perform various unary floating-point operations inspired by libm.
+    FNEG, FABS, FSQRT, FCBRT, FSIN, FCOS, FPOWI, FPOW,
     FLOG, FLOG2, FLOG10, FEXP, FEXP2,
     FCEIL, FTRUNC, FRINT, FNEARBYINT, FROUND, FFLOOR,
     /// FMINNUM/FMAXNUM - Perform floating-point minimum or maximum on two
     /// values.
     /// In the case where a single input is NaN, the non-NaN input is returned.
     ///
     /// The return value of (FMINNUM 0.0, -0.0) could be either 0.0 or -0.0.
     FMINNUM, FMAXNUM,

llvm/trunk/include/llvm/IR/RuntimeLibcalls.def

 HANDLE_LIBCALL(POWI_F80, "__powixf2")
 HANDLE_LIBCALL(POWI_F128, "__powitf2")
 HANDLE_LIBCALL(POWI_PPCF128, "__powitf2")
 HANDLE_LIBCALL(SQRT_F32, "sqrtf")
 HANDLE_LIBCALL(SQRT_F64, "sqrt")
 HANDLE_LIBCALL(SQRT_F80, "sqrtl")
 HANDLE_LIBCALL(SQRT_F128, "sqrtl")
 HANDLE_LIBCALL(SQRT_PPCF128, "sqrtl")
+HANDLE_LIBCALL(CBRT_F32, "cbrtf")
+HANDLE_LIBCALL(CBRT_F64, "cbrt")
+HANDLE_LIBCALL(CBRT_F80, "cbrtl")
+HANDLE_LIBCALL(CBRT_F128, "cbrtl")
+HANDLE_LIBCALL(CBRT_PPCF128, "cbrtl")
 HANDLE_LIBCALL(LOG_F32, "logf")
 HANDLE_LIBCALL(LOG_F64, "log")
 HANDLE_LIBCALL(LOG_F80, "logl")
 HANDLE_LIBCALL(LOG_F128, "logl")
 HANDLE_LIBCALL(LOG_PPCF128, "logl")
 HANDLE_LIBCALL(LOG_FINITE_F32, "__logf_finite")
 HANDLE_LIBCALL(LOG_FINITE_F64, "__log_finite")
 HANDLE_LIBCALL(LOG_FINITE_F80, "__logl_finite")

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitFCOPYSIGN(SDNode *N) {
   return SDValue();
 }
 
 SDValue DAGCombiner::visitFPOW(SDNode *N) {
   ConstantFPSDNode *ExponentC = isConstOrConstSplatFP(N->getOperand(1));
   if (!ExponentC)
     return SDValue();
 
+  // Try to convert x ** (1/3) into cube root.
+  // TODO: Handle the various flavors of long double.
+  // TODO: Since we're approximating, we don't need an exact 1/3 exponent.
+  //       Some range near 1/3 should be fine.
+  EVT VT = N->getValueType(0);
+  if ((VT == MVT::f32 && ExponentC->getValueAPF().isExactlyValue(1.0f/3.0f)) ||
+      (VT == MVT::f64 && ExponentC->getValueAPF().isExactlyValue(1.0/3.0))) {
+    // pow(-0.0, 1/3) = +0.0; cbrt(-0.0) = -0.0.
+    // pow(-inf, 1/3) = +inf; cbrt(-inf) = -inf.
+    // pow(-val, 1/3) =  nan; cbrt(-val) = -num.
+    // For regular numbers, rounding may cause the results to differ.
+    // Therefore, we require { nsz ninf nnan afn } for this transform.
+    // TODO: We could select out the special cases if we don't have nsz/ninf.
+    SDNodeFlags Flags = N->getFlags();
+    if (!Flags.hasNoSignedZeros() || !Flags.hasNoInfs() || !Flags.hasNoNaNs() ||
+        !Flags.hasApproximateFuncs())
+      return SDValue();
+
+    // Do not create a cbrt() libcall if the target does not have it, and do not
+    // turn a pow that has lowering support into a cbrt() libcall.
+    if (!DAG.getLibInfo().has(LibFunc_cbrt) ||
+        (!DAG.getTargetLoweringInfo().isOperationExpand(ISD::FPOW, VT) &&
+         DAG.getTargetLoweringInfo().isOperationExpand(ISD::FCBRT, VT)))
+      return SDValue();
+
+    return DAG.getNode(ISD::FCBRT, SDLoc(N), VT, N->getOperand(0), Flags);
+  }
+
   // Try to convert x ** (1/4) into square roots.
   // x ** (1/2) is canonicalized to sqrt, so we do not bother with that case.
   // TODO: This could be extended (using a target hook) to handle smaller
   // power-of-2 fractional exponents.
   if (ExponentC->getValueAPF().isExactlyValue(0.25)) {
     // pow(-0.0, 0.25) = +0.0; sqrt(sqrt(-0.0)) = -0.0.
     // pow(-inf, 0.25) = +inf; sqrt(sqrt(-inf)) =  NaN.
     // For regular numbers, rounding may cause the results to differ.
     // Therefore, we require { nsz ninf afn } for this transform.
     // TODO: We could select out the special cases if we don't have nsz/ninf.
     SDNodeFlags Flags = N->getFlags();
     if (!Flags.hasNoSignedZeros() || !Flags.hasNoInfs() ||
         !Flags.hasApproximateFuncs())
       return SDValue();
 
     // Don't double the number of libcalls. We are trying to inline fast code.
-    EVT VT = N->getValueType(0);
     if (!DAG.getTargetLoweringInfo().isOperationLegalOrCustom(ISD::FSQRT, VT))
       return SDValue();
 
     // Assume that libcalls are the smallest code.
     // TODO: This restriction should probably be lifted for vectors.
     if (DAG.getMachineFunction().getFunction().optForSize())
       return SDValue();
 

llvm/trunk/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

Results.push_back(ExpandFPLibCall(Node, RTLIB::FMAX_F32, RTLIB::FMAX_F64,
                                       RTLIB::FMAX_PPCF128));
     break;
   case ISD::FSQRT:
   case ISD::STRICT_FSQRT:
     Results.push_back(ExpandFPLibCall(Node, RTLIB::SQRT_F32, RTLIB::SQRT_F64,
                                       RTLIB::SQRT_F80, RTLIB::SQRT_F128,
                                       RTLIB::SQRT_PPCF128));
     break;
+  case ISD::FCBRT:
+    Results.push_back(ExpandFPLibCall(Node, RTLIB::CBRT_F32, RTLIB::CBRT_F64,
+                                      RTLIB::CBRT_F80, RTLIB::CBRT_F128,
+                                      RTLIB::CBRT_PPCF128));
+    break;
   case ISD::FSIN:
   case ISD::STRICT_FSIN:
     Results.push_back(ExpandFPLibCall(Node, RTLIB::SIN_F32, RTLIB::SIN_F64,
                                       RTLIB::SIN_F80, RTLIB::SIN_F128,
                                       RTLIB::SIN_PPCF128));
     break;
   case ISD::FCOS:
   case ISD::STRICT_FCOS:

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

#endif
   case ISD::FABS:                       return "fabs";
   case ISD::FMINNUM:                    return "fminnum";
   case ISD::FMAXNUM:                    return "fmaxnum";
   case ISD::FMINNAN:                    return "fminnan";
   case ISD::FMAXNAN:                    return "fmaxnan";
   case ISD::FNEG:                       return "fneg";
   case ISD::FSQRT:                      return "fsqrt";
   case ISD::STRICT_FSQRT:               return "strict_fsqrt";
+  case ISD::FCBRT:                      return "fcbrt";
   case ISD::FSIN:                       return "fsin";
   case ISD::STRICT_FSIN:                return "strict_fsin";
   case ISD::FCOS:                       return "fcos";
   case ISD::STRICT_FCOS:                return "strict_fcos";
   case ISD::FSINCOS:                    return "fsincos";
   case ISD::FTRUNC:                     return "ftrunc";
   case ISD::FFLOOR:                     return "ffloor";
   case ISD::FCEIL:                      return "fceil";

llvm/trunk/lib/CodeGen/TargetLoweringBase.cpp

void TargetLoweringBase::initActions() {
   setOperationAction(ISD::ConstantFP, MVT::f16, Expand);
   setOperationAction(ISD::ConstantFP, MVT::f32, Expand);
   setOperationAction(ISD::ConstantFP, MVT::f64, Expand);
   setOperationAction(ISD::ConstantFP, MVT::f80, Expand);
   setOperationAction(ISD::ConstantFP, MVT::f128, Expand);
 
   // These library functions default to expand.
   for (MVT VT : {MVT::f32, MVT::f64, MVT::f128}) {
+    setOperationAction(ISD::FCBRT,      VT, Expand);
     setOperationAction(ISD::FLOG ,      VT, Expand);
     setOperationAction(ISD::FLOG2,      VT, Expand);
     setOperationAction(ISD::FLOG10,     VT, Expand);
     setOperationAction(ISD::FEXP ,      VT, Expand);
     setOperationAction(ISD::FEXP2,      VT, Expand);
     setOperationAction(ISD::FFLOOR,     VT, Expand);
     setOperationAction(ISD::FNEARBYINT, VT, Expand);
     setOperationAction(ISD::FCEIL,      VT, Expand);

llvm/trunk/test/CodeGen/X86/pow.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-- | FileCheck %s
 
 declare float @llvm.pow.f32(float, float)
 declare <4 x float> @llvm.pow.v4f32(<4 x float>, <4 x float>)
 
 declare double @llvm.pow.f64(double, double)
 declare <2 x double> @llvm.pow.v2f64(<2 x double>, <2 x double>)
 
+declare x86_fp80 @llvm.pow.f80(x86_fp80, x86_fp80)
+
 define float @pow_f32_one_fourth_fmf(float %x) nounwind {
 ; CHECK-LABEL: pow_f32_one_fourth_fmf:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    rsqrtss %xmm0, %xmm1
 ; CHECK-NEXT:    movaps %xmm0, %xmm2
 ; CHECK-NEXT:    mulss %xmm1, %xmm2
 ; CHECK-NEXT:    movss {{.*#+}} xmm3 = mem[0],zero,zero,zero
 ; CHECK-NEXT:    movaps %xmm2, %xmm4

 ; CHECK-NEXT:    retq
   %r = call nsz nnan reassoc <2 x double> @llvm.pow.v2f64(<2 x double> %x, <2 x double> <double 2.5e-1, double 2.5e-1>)
   ret <2 x double> %r
 }
 
 define float @pow_f32_one_third_fmf(float %x) nounwind {
 ; CHECK-LABEL: pow_f32_one_third_fmf:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movss {{.*#+}} xmm1 = mem[0],zero,zero,zero
-; CHECK-NEXT:    jmp powf # TAILCALL
+; CHECK-NEXT:    jmp cbrtf # TAILCALL
   %one = uitofp i32 1 to float
   %three = uitofp i32 3 to float
   %exp = fdiv float %one, %three
   %r = call nsz nnan ninf afn float @llvm.pow.f32(float %x, float %exp)
   ret float %r
 }
 
 define double @pow_f64_one_third_fmf(double %x) nounwind {
 ; CHECK-LABEL: pow_f64_one_third_fmf:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movsd {{.*#+}} xmm1 = mem[0],zero
-; CHECK-NEXT:    jmp pow # TAILCALL
+; CHECK-NEXT:    jmp cbrt # TAILCALL
   %one = uitofp i32 1 to double
   %three = uitofp i32 3 to double
   %exp = fdiv double %one, %three
   %r = call nsz nnan ninf afn double @llvm.pow.f64(double %x, double %exp)
   ret double %r
 }
 
+; TODO: We could turn this into cbrtl, but currently we only handle float/double types.
+
+define x86_fp80 @pow_f80_one_third_fmf(x86_fp80 %x) nounwind {
+; CHECK-LABEL: pow_f80_one_third_fmf:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    subq $40, %rsp
+; CHECK-NEXT:    fldt {{[0-9]+}}(%rsp)
+; CHECK-NEXT:    fldt {{.*}}(%rip)
+; CHECK-NEXT:    fstpt {{[0-9]+}}(%rsp)
+; CHECK-NEXT:    fstpt (%rsp)
+; CHECK-NEXT:    callq powl
+; CHECK-NEXT:    addq $40, %rsp
+; CHECK-NEXT:    retq
+  %one = uitofp i32 1 to x86_fp80
+  %three = uitofp i32 3 to x86_fp80
+  %exp = fdiv x86_fp80 %one, %three
+  %r = call nsz nnan ninf afn x86_fp80 @llvm.pow.f80(x86_fp80 %x, x86_fp80 %exp)
+  ret x86_fp80 %r
+}
+
+; We might want to allow this. The exact hex value for 1/3 as a double is 0x3fd5555555555555.
+
+define double @pow_f64_not_exactly_one_third_fmf(double %x) nounwind {
+; CHECK-LABEL: pow_f64_not_exactly_one_third_fmf:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movsd {{.*#+}} xmm1 = mem[0],zero
+; CHECK-NEXT:    jmp pow # TAILCALL
+  %r = call nsz nnan ninf afn double @llvm.pow.f64(double %x, double 0x3fd5555555555556)
+  ret double %r
+}
+
+; We require all 4 of nsz, ninf, nnan, afn.
+
+define double @pow_f64_not_enough_fmf(double %x) nounwind {
+; CHECK-LABEL: pow_f64_not_enough_fmf:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movsd {{.*#+}} xmm1 = mem[0],zero
+; CHECK-NEXT:    jmp pow # TAILCALL
+  %r = call nsz ninf afn double @llvm.pow.f64(double %x, double 0x3fd5555555555555)
+  ret double %r
+}
+