[SLC] Simplify pow(x, 0.333...) to cbrt(x)

[evandro]

Summary

This transformation helps some benchmarks in SPEC CPU200 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.

[lebedev.ri]

Tests?

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1138–1139

There seems to be two variants: https://godbolt.org/g/Rw1Gxt
Can you output the value that doesn't match?

[efriedma]

Missing testcases.

I'm not sure what you mean by "a hard time matching the exponent"; I can't see any reason float would be different from double, assuming you're actually using the right constant.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1125

You need nsz: pow(-0., 1./3) returns +0, but cbrt(-0.) returns -0.

I think I'd prefer to require afn for this; not sure it's necessary, but better to be safe.

Please add explicit comments explaining why you need nnan and ninf (nnan because pow() returns a nan for negative x, ninf for pow(-inf, 1./3)).

[spatel]

Shouldn't this patch use the existing code in replacePowWithSqrt(), so we're not (incompletely) duplicating the logic?

That code also has a TODO comment about choosing the minimal set of FMF to enable the fold. Whatever we decide that predicate will be should be identical for both transforms?

[evandro]

In D49040#1155206, @spatel wrote:

Shouldn't this patch use the existing code in replacePowWithSqrt(), so we're not (incompletely) duplicating the logic?

That code also has a TODO comment about choosing the minimal set of FMF to enable the fold. Whatever we decide that predicate will be should be identical for both transforms?

The logic is almost the same, except that sqrt() has a corresponding intrinsic and cbrt() doesn't. So. at elast for now, methinks that it's easier to understand and review this change as a separate function. Then, if needed, both functions could be merged.

[evandro]

Add a test case.

[evandro]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1138–1139

Please, see any example using float in the test case below.

[evandro]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1138–1139

My bad. I crafted the test case using the IEEE754 bits for SP instead of the bits for DP truncated for float.

[evandro]

Enable handling of float.

[lebedev.ri]

llvm/test/Transforms/InstCombine/pow-cbrt.ll

1

Just use ./utils/update_test_checks.py

[efriedma]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1125

isFast() is deprecated, because it makes the actual requirements unclear and disables optimizations where it isn't necessary. (In particular, you don't need reassoc here.)

[evandro]

Refactor all of the code that simplifies pow(x, 0.5) to sqrt() by folding it into a new function that handles all simplifications to radical operations.

[evandro]

Allow splat vectors for trivial simplifications.

[evandro]

Ping! 🔔

[evandro]

¡Ping! 🔔🔔

[spatel]

If I'm seeing it correctly, there are several independent changes going on here. Can you split this up to make the review easier?

1. Add all new tests with baseline CHECKs as an NFC preliminary step.
2. It's not clear to me what the FMF diffs in pow-sqrt.ll are showing. If we are adjusting FMF constraints on existing folds, that should be an independent patch?
3. The cosmetic diffs in variable names (Base, Expo, Shrunk, etc) look fine, so those can be another preliminary NFC commit before the part that needs further review.
4. The cbrt transform can be the last patch/commit in this series; once we have the cleanup done, that should be a very small diff.

[evandro]

OK. Please, stay tuned.

[evandro]

Committed rL338152 to add the base line test case pow-cbrt.ll.

[evandro]

Ping! 🔔

[spatel]

As we discussed in D49306, I agree that this is probably a good perf transform, but I don't think we've shown any compelling reason to do this in IR vs. DAGCombiner.

There are downsides to doing this in IR currently because we don't have a cbrt intrinsic. That means we have different behavior based on data type (vectors won't get transformed).
It's also not clear why transforming to a form with fdiv in the negative exponent case is better than a single pow instruction. (And that case probably needs some perf justification even as a backend fold.)

[evandro]

OK, then.

llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
   Value *optimizeWcslen(CallInst *CI, IRBuilder<> &B);
   // Wrapper for all String/Memory Library Call Optimizations
   Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B);
 
   // Math Library Optimizations
   Value *optimizeCAbs(CallInst *CI, IRBuilder<> &B);
   Value *optimizeCos(CallInst *CI, IRBuilder<> &B);
   Value *optimizePow(CallInst *CI, IRBuilder<> &B);
-  Value *replacePowWithSqrt(CallInst *Pow, IRBuilder<> &B);
+  Value *replacePowWithRoot(CallInst *Pow, IRBuilder<> &B);
   Value *optimizeExp2(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFMinFMax(CallInst *CI, IRBuilder<> &B);
   Value *optimizeLog(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSqrt(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSinCosPi(CallInst *CI, IRBuilder<> &B);
   Value *optimizeTan(CallInst *CI, IRBuilder<> &B);
   // Wrapper for all floating point library call optimizations
   Value *optimizeFloatingPointLibCall(CallInst *CI, LibFunc Func,

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

static const unsigned AddChain[33][2] = {
       {3, 24}, {14, 14}, {4, 25}, {15, 15}, {3, 28}, {16, 16},
   };
 
   InnerChain[Exp] = B.CreateFMul(getPow(InnerChain, AddChain[Exp][0], B),
                                  getPow(InnerChain, AddChain[Exp][1], B));
   return InnerChain[Exp];
 }
 
-/// Use square root in place of pow(x, +/-0.5).
-Value *LibCallSimplifier::replacePowWithSqrt(CallInst *Pow, IRBuilder<> &B) {
-  Value *Sqrt, *Base = Pow->getArgOperand(0), *Expo = Pow->getArgOperand(1);
+/// Use sqrt() for pow(x, +/-0.5) and cbrt() for pow(x, +/-0.333...).
+Value *LibCallSimplifier::replacePowWithRoot(CallInst *Pow, IRBuilder<> &B) {
+  Value *Root, *Base = Pow->getArgOperand(0), *Expo = Pow->getArgOperand(1);
+  AttributeList Attrs = Pow->getCalledFunction()->getAttributes();
   Module *Mod = Pow->getModule();
   Type *Ty = Pow->getType();
 
   const APFloat *ExpoF;
-  if (!match(Expo, m_APFloat(ExpoF)) ||
-      (!ExpoF->isExactlyValue(0.5) && !ExpoF->isExactlyValue(-0.5)))
+  if (!match(Expo, m_APFloat(ExpoF)))
     return nullptr;
 
+  const double OneThird = (Ty->getTypeID() == Type::FloatTyID)
+                          ? (1.0f / 3.0f) : (1.0 / 3.0);
+  bool isHalf  (ExpoF->isExactlyValue(0.5) || ExpoF->isExactlyValue(-0.5)),
+       isThird (ExpoF->isExactlyValue(OneThird) ||
+                ExpoF->isExactlyValue(-OneThird));
+  if (!isHalf && !isThird)
+    return nullptr;
+
+  // Expand pow(x, +/-0.5) to sqrt().
+  if (isHalf) {
     // If errno is never set, then use the intrinsic for sqrt().
     if (Pow->hasFnAttr(Attribute::ReadNone)) {
-    Function *SqrtFn = Intrinsic::getDeclaration(Pow->getModule(),
-                                                 Intrinsic::sqrt, Ty);
-    Sqrt = B.CreateCall(SqrtFn, Base, "sqrt");
+      Function *SqrtFn = Intrinsic::getDeclaration(Mod, Intrinsic::sqrt, Ty);
+      Root = B.CreateCall(SqrtFn, Base, "sqrt");
     }
     // Otherwise, use the libcall for sqrt().
-  else if (hasUnaryFloatFn(TLI, Ty, LibFunc_sqrt, LibFunc_sqrtf, LibFunc_sqrtl))
+    else if (hasUnaryFloatFn(TLI, Ty,
+                             LibFunc_sqrt, LibFunc_sqrtf, LibFunc_sqrtl))
       // TODO: We also should check that the target can in fact lower the sqrt()
-    // libcall. We currently have no way to ask this question, so we ask if
+      // libcall.  We currently have no way to ask this question, so we ask if
       // the target has a sqrt() libcall, which is not exactly the same.
-    Sqrt = emitUnaryFloatFnCall(Base, TLI->getName(LibFunc_sqrt), B,
-                                Pow->getCalledFunction()->getAttributes());
+      Root = emitUnaryFloatFnCall(Base, TLI->getName(LibFunc_sqrt), B, Attrs);
     else
       return nullptr;
 
     // Handle signed zero base by expanding to fabs(sqrt(x)).
     if (!Pow->hasNoSignedZeros()) {
       Function *FAbsFn = Intrinsic::getDeclaration(Mod, Intrinsic::fabs, Ty);
-    Sqrt = B.CreateCall(FAbsFn, Sqrt, "abs");
+      Root = B.CreateCall(FAbsFn, Root, "abs");
     }
 
     // Handle non finite base by expanding to
     // (x == -infinity ? +infinity : sqrt(x)).
     if (!Pow->hasNoInfs()) {
       Value *PosInf = ConstantFP::getInfinity(Ty),
             *NegInf = ConstantFP::getInfinity(Ty, true);
       Value *FCmp = B.CreateFCmpOEQ(Base, NegInf, "iseq");
-    Sqrt = B.CreateSelect(FCmp, PosInf, Sqrt);
+      Root = B.CreateSelect(FCmp, PosInf, Root);
+    }
+  }
+  // Expand pow(x, +/-0.333...) to cbrt(), but only for a regular base.
+  else if (isThird &&
+           Pow->hasNoInfs() && Pow->hasNoNaNs() && Pow->hasNoSignedZeros()) {
+    if (hasUnaryFloatFn(TLI, Ty, LibFunc_cbrt, LibFunc_cbrtf, LibFunc_cbrtl))
+      Root = emitUnaryFloatFnCall(Base, TLI->getName(LibFunc_cbrt), B, Attrs);
+    else
+      return nullptr;
   }
+  else
+    return nullptr;
 
   // If the exponent is negative, then get the reciprocal.
   if (ExpoF->isNegative())
-    Sqrt = B.CreateFDiv(ConstantFP::get(Ty, 1.0), Sqrt, "reciprocal");
+    Root = B.CreateFDiv(ConstantFP::get(Ty, 1.0), Root, "reciprocal");
 
-  return Sqrt;
+  return Root;
 }
 
 Value *LibCallSimplifier::optimizePow(CallInst *Pow, IRBuilder<> &B) {
   Value *Base = Pow->getArgOperand(0), *Expo = Pow->getArgOperand(1);
   Function *Callee = Pow->getCalledFunction();
   AttributeList Attrs = Callee->getAttributes();
   StringRef Name = Callee->getName();
   Module *Module = Pow->getModule();
Value *LibCallSimplifier::optimizePow(CallInst *Pow, IRBuilder<> &B) {
   // pow(x, 1.0) -> x
   if (match(Expo, m_FPOne()))
     return Base;
 
   // pow(x, 2.0) -> x * x
   if (match(Expo, m_SpecificFP(2.0)))
     return B.CreateFMul(Base, Base, "square");
 
-  if (Value *Sqrt = replacePowWithSqrt(Pow, B))
-    return Sqrt;
+  if (Value *Root = replacePowWithRoot(Pow, B))
+    return Root;
 
   // pow(x, n) -> x * x * x * ...
   const APFloat *ExpoF;
   if (Pow->isFast() && match(Expo, m_APFloat(ExpoF))) {
     // We limit to a max of 7 multiplications, thus the maximum exponent is 32.
     APFloat LimF(ExpoF->getSemantics(), 33.0),
             ExpoA(abs(*ExpoF));
     if (ExpoA.isInteger() && ExpoA.compare(LimF) == APFloat::cmpLessThan) {

llvm/test/Transforms/InstCombine/pow-cbrt.ll

-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define double @pow_intrinsic_third_fast(double %x) {
 ; CHECK-LABEL: @pow_intrinsic_third_fast(
-; CHECK-NEXT:    [[POW:%.*]] = call fast double @llvm.pow.f64(double [[X:%.*]], double 0x3FD5555555555555)
-; CHECK-NEXT:    ret double [[POW]]
+; CHECK-NEXT:    [[CBRT:%.*]] = call fast double @cbrt(double %x) #1
+; CHECK-NEXT:    ret double [[CBRT]]
 ;
   %pow = call fast double @llvm.pow.f64(double %x, double 0x3fd5555555555555)
   ret double %pow
 }
 
 define float @powf_intrinsic_third_fast(float %x) {
 ; CHECK-LABEL: @powf_intrinsic_third_fast(
-; CHECK-NEXT:    [[POW:%.*]] = call fast float @llvm.pow.f32(float [[X:%.*]], float 0x3FD5555560000000)
-; CHECK-NEXT:    ret float [[POW]]
+; CHECK-NEXT:    [[CBRTF:%.*]] = call fast float @cbrtf(float %x) #1
+; CHECK-NEXT:    ret float [[CBRTF]]
 ;
   %pow = call fast float @llvm.pow.f32(float %x, float 0x3fd5555560000000)
   ret float %pow
 }
 
 define double @pow_intrinsic_third_approx(double %x) {
 ; CHECK-LABEL: @pow_intrinsic_third_approx(
-; CHECK-NEXT:    [[POW:%.*]] = call afn double @llvm.pow.f64(double [[X:%.*]], double 0x3FD5555555555555)
+; CHECK-NEXT:    [[POW:%.*]] = call afn double @llvm.pow.f64(double %x, double 0x3FD5555555555555)
 ; CHECK-NEXT:    ret double [[POW]]
 ;
   %pow = call afn double @llvm.pow.f64(double %x, double 0x3fd5555555555555)
   ret double %pow
 }
 
 define float @powf_intrinsic_third_approx(float %x) {
 ; CHECK-LABEL: @powf_intrinsic_third_approx(
-; CHECK-NEXT:    [[POW:%.*]] = call afn float @llvm.pow.f32(float [[X:%.*]], float 0x3FD5555560000000)
+; CHECK-NEXT:    [[POW:%.*]] = call afn float @llvm.pow.f32(float %x, float 0x3FD5555560000000)
 ; CHECK-NEXT:    ret float [[POW]]
 ;
   %pow = call afn float @llvm.pow.f32(float %x, float 0x3fd5555560000000)
   ret float %pow
 }
 
 define double @pow_libcall_third_fast(double %x) {
 ; CHECK-LABEL: @pow_libcall_third_fast(
-; CHECK-NEXT:    [[POW:%.*]] = call fast double @pow(double [[X:%.*]], double 0x3FD5555555555555)
-; CHECK-NEXT:    ret double [[POW]]
+; CHECK-NEXT:    [[CBRT:%.*]] = call fast double @cbrt(double %x)
+; CHECK-NEXT:    ret double [[CBRT]]
 ;
   %pow = call fast double @pow(double %x, double 0x3fd5555555555555)
   ret double %pow
 }
 
 define float @powf_libcall_third_fast(float %x) {
 ; CHECK-LABEL: @powf_libcall_third_fast(
-; CHECK-NEXT:    [[POW:%.*]] = call fast float @powf(float [[X:%.*]], float 0x3FD5555560000000)
-; CHECK-NEXT:    ret float [[POW]]
+; CHECK-NEXT:    [[CBRTF:%.*]] = call fast float @cbrtf(float %x)
+; CHECK-NEXT:    ret float [[CBRTF]]
 ;
   %pow = call fast float @powf(float %x, float 0x3fd5555560000000)
   ret float %pow
 }
 
 define double @pow_intrinsic_negthird_fast(double %x) {
 ; CHECK-LABEL: @pow_intrinsic_negthird_fast(
-; CHECK-NEXT:    [[POW:%.*]] = call fast double @llvm.pow.f64(double [[X:%.*]], double 0xBFD5555555555555)
-; CHECK-NEXT:    ret double [[POW]]
+; CHECK-NEXT:    [[CBRT:%.*]] = call fast double @cbrt(double %x) #1
+; CHECK-NEXT:    [[RECP:%.*]] = fdiv fast double 1.000000e+00, [[CBRT]]
+; CHECK-NEXT:    ret double [[RECP]]
 ;
   %pow = call fast double @llvm.pow.f64(double %x, double 0xbfd5555555555555)
   ret double %pow
 }
 
 define float @powf_intrinsic_negthird_fast(float %x) {
 ; CHECK-LABEL: @powf_intrinsic_negthird_fast(
-; CHECK-NEXT:    [[POW:%.*]] = call fast float @llvm.pow.f32(float [[X:%.*]], float 0xBFD5555560000000)
-; CHECK-NEXT:    ret float [[POW]]
+; CHECK-NEXT:    [[CBRTF:%.*]] = call fast float @cbrtf(float %x) #1
+; CHECK-NEXT:    [[RECP:%.*]] = fdiv fast float 1.000000e+00, [[CBRTF]]
+; CHECK-NEXT:    ret float [[RECP]]
 ;
   %pow = call fast float @llvm.pow.f32(float %x, float 0xbfd5555560000000)
   ret float %pow
 }
 
 define double @pow_intrinsic_negthird_approx(double %x) {
 ; CHECK-LABEL: @pow_intrinsic_negthird_approx(
-; CHECK-NEXT:    [[POW:%.*]] = call afn double @llvm.pow.f64(double [[X:%.*]], double 0xBFD5555555555555)
+; CHECK-NEXT:    [[POW:%.*]] = call afn double @llvm.pow.f64(double %x, double 0xBFD5555555555555)
 ; CHECK-NEXT:    ret double [[POW]]
 ;
   %pow = call afn double @llvm.pow.f64(double %x, double 0xbfd5555555555555)
   ret double %pow
 }
 
 define float @powf_intrinsic_negthird_approx(float %x) {
 ; CHECK-LABEL: @powf_intrinsic_negthird_approx(
-; CHECK-NEXT:    [[POW:%.*]] = call afn float @llvm.pow.f32(float [[X:%.*]], float 0xBFD5555560000000)
+; CHECK-NEXT:    [[POW:%.*]] = call afn float @llvm.pow.f32(float %x, float 0xBFD5555560000000)
 ; CHECK-NEXT:    ret float [[POW]]
 ;
   %pow = call afn float @llvm.pow.f32(float %x, float 0xbfd5555560000000)
   ret float %pow
 }
 
 define double @pow_libcall_negthird_fast(double %x) {
 ; CHECK-LABEL: @pow_libcall_negthird_fast(
-; CHECK-NEXT:    [[POW:%.*]] = call fast double @pow(double [[X:%.*]], double 0xBFD5555555555555)
-; CHECK-NEXT:    ret double [[POW]]
+; CHECK-NEXT:    [[CBRT:%.*]] = call fast double @cbrt(double %x)
+; CHECK-NEXT:    [[RECP:%.*]] = fdiv fast double 1.000000e+00, [[CBRT]]
+; CHECK-NEXT:    ret double [[RECP]]
 ;
   %pow = call fast double @pow(double %x, double 0xbfd5555555555555)
   ret double %pow
 }
 
 define float @powf_libcall_negthird_fast(float %x) {
 ; CHECK-LABEL: @powf_libcall_negthird_fast(
-; CHECK-NEXT:    [[POW:%.*]] = call fast float @powf(float [[X:%.*]], float 0xBFD5555560000000)
-; CHECK-NEXT:    ret float [[POW]]
+; CHECK-NEXT:    [[CBRTF:%.*]] = call fast float @cbrtf(float %x)
+; CHECK-NEXT:    [[RECP:%.*]] = fdiv fast float 1.000000e+00, [[CBRTF]]
+; CHECK-NEXT:    ret float [[RECP]]
 ;
   %pow = call fast float @powf(float %x, float 0xbfd5555560000000)
   ret float %pow
 }
 
 declare double @llvm.pow.f64(double, double) #0
 declare float @llvm.pow.f32(float, float) #0
 declare double @pow(double, double)
 declare float @powf(float, float)
 
 attributes #0 = { nounwind readnone speculatable }