[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

2

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 *replacePowWithCbrt(CallInst *Pow, IRBuilder<> &B);
   Value *replacePowWithSqrt(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

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 cube root in place of pow(x, +/-0.333...).
+Value *LibCallSimplifier::replacePowWithCbrt(CallInst *Pow, IRBuilder<> &B) {
+  // Only in finite and normal math.
+  if (!Pow->hasNoInfs() || !Pow->hasNoNaNs())
+    return nullptr;
+
+  Type *Ty = Pow->getType();
+  Type::TypeID TyID = Ty->getTypeID();
+  // TODO: Handle SP FP as well, though the argument seems to never match below.
+  if (TyID != Type::DoubleTyID)
+    return nullptr;
+
+  ConstantFP *Arg2C = dyn_cast<ConstantFP>(Pow->getArgOperand(1));
+  if (!Arg2C)
+    return nullptr;
+
+  const APFloat SPPlusThird(1.0f / 3.0f), SPMinusThird(-1.0f / 3.0f),
+                DPPlusThird(1.0  / 3.0),  DPMinusThird(-1.0  / 3.0);
+  bool isPlusThird  = Arg2C->isExactlyValue((TyID == Type::FloatTyID)
+                                            ? SPPlusThird : DPPlusThird),
+       isMinusThird = Arg2C->isExactlyValue((TyID == Type::FloatTyID)
+                                            ? SPMinusThird : DPMinusThird);
+  if (!isPlusThird && !isMinusThird)
+    return nullptr;
+
+  if (!hasUnaryFloatFn(TLI, Ty, LibFunc_cbrt, LibFunc_cbrtf, LibFunc_cbrtl))
+    return nullptr;
+
+  // Fast-math flags from the pow() are propagated to all replacement ops.
+  IRBuilder<>::FastMathFlagGuard Guard(B);
+  B.setFastMathFlags(Pow->getFastMathFlags());
+  Value *Cbrt = emitUnaryFloatFnCall(Pow->getArgOperand(0),
+                                     TLI->getName(LibFunc_cbrt), B,
+                                     Pow->getCalledFunction()->getAttributes());
+
+  // If this is pow(x, -0.333...), get the reciprocal.
+  if (isMinusThird)
+    Cbrt = B.CreateFDiv(ConstantFP::get(Ty, 1.0), Cbrt);
+
+  return Cbrt;
+}
+
 /// Use square root in place of pow(x, +/-0.5).
 Value *LibCallSimplifier::replacePowWithSqrt(CallInst *Pow, IRBuilder<> &B) {
   // TODO: There is some subset of 'fast' under which these transforms should
   // be allowed.
   if (!Pow->isFast())
     return nullptr;
 
   const APFloat *Arg1C;
if (OpCCallee && TLI->getLibFunc(OpCCallee->getName(), Func) &&
       return emitUnaryFloatFnCall(FMul, OpCCallee->getName(), B,
                                   OpCCallee->getAttributes());
     }
   }
 
   if (Value *Sqrt = replacePowWithSqrt(CI, B))
     return Sqrt;
 
+  if (Value *Cbrt = replacePowWithCbrt(CI, B))
+    return Cbrt;
+
   ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
   if (!Op2C)
     return Ret;
 
   if (Op2C->getValueAPF().isZero()) // pow(x, 0.0) -> 1.0
     return ConstantFP::get(CI->getType(), 1.0);
 
   // FIXME: Correct the transforms and pull this into replacePowWithSqrt().

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

+; 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 @cbrt(double %x)
+; CHECK-NEXT:    ret double [[POW]]
+;
+  %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
+;
+  %pow = call fast float @llvm.pow.f32(float %x, float 0x3eaaaaab00000000)
+  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:    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(
+;
+  %pow = call afn float @llvm.pow.f32(float %x, float 0x3eaaaaab00000000)
+  ret float %pow
+}
+
+define double @pow_libcall_third_fast(double %x) {
+; CHECK-LABEL: @pow_libcall_third_fast
+; CHECK-NEXT:    [[POW:%.*]] = call fast double @cbrt(double %x)
+; CHECK-NEXT:    ret double [[POW]]
+;
+  %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
+;
+  %pow = call fast float @powf(float %x, float 0x3eaaaaab00000000)
+  ret float %pow
+}
+
+define double @pow_intrinsic_negthird_fast(double %x) {
+; CHECK-LABEL: @pow_intrinsic_negthird_fast
+; CHECK-NEXT:    [[CBR:%.*]] = call fast double @cbrt(double %x)
+; CHECK-NEXT:    [[POW:%.*]] = fdiv fast double 1.000000e+00, [[CBR]]
+; CHECK-NEXT:    ret double [[POW]]
+;
+  %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
+;
+  %pow = call fast float @llvm.pow.f32(float %x, float 0xbeaaaaab00000000)
+  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:    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(
+;
+  %pow = call afn float @llvm.pow.f32(float %x, float 0xbeaaaaab00000000)
+  ret float %pow
+}
+
+define double @pow_libcall_negthird_fast(double %x) {
+; CHECK-LABEL: @pow_libcall_negthird_fast
+; CHECK-NEXT:    [[CBR:%.*]] = call fast double @cbrt(double %x)
+; CHECK-NEXT:    [[POW:%.*]] = fdiv fast double 1.000000e+00, [[CBR]]
+; CHECK-NEXT:    ret double [[POW]]
+;
+  %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
+;
+  %pow = call fast float @powf(float %x, float 0xbeaaaaab00000000)
+  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 }