[InstCombine] pow(C,x) -> exp2(log2(C)*x)

[xbolva00]

Summary

Transform
pow(C,x)

To
exp2(log2(C)*x)

if C > 0, C != inf, C != NaN (and C is not power of 2, since we have some fold for such case already).

log(C) is folded by the compiler and exp2 is much faster to compute than pow.

[efriedma]

I'm a little wary about fold the case where doesNotAccessMemory is false, but I guess it's likely okay.

I'm guessing it doesn't matter whether you use exp or exp2 here? I guess the performance is probably similar, but it isn't obvious to me.

Should we specifically have test coverage for transforming pow(10, x) to exp?

lib/Transforms/Utils/SimplifyLibCalls.cpp

1351 ↗

(On Diff #207624)

Please don't check "isFast()", instead, check the components you actually need for this. You clearly need afn; not sure if you need anything else to handle cases where the exponent is zero/inf/nan.

1354 ↗

(On Diff #207624)

I'd rather explicitly fold the "log" here, so we know it actually happens; the constant folding code will not fold it in all cases.

[xbolva00]

Switched to exp2 (faster).
Addressed some review comments.
Added pow(10, e) test.

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1354 ↗

(On Diff #207624)

emitUnaryFloatFnCall automatically folds it? @spatel @lebedev.ri

Not sure how to get log2 of APFloat...

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1354 ↗

(On Diff #207624)

Ah, right. It was constant folded only in “fast” mode..

[xbolva00]

test/Transforms/InstCombine/pow-exp.ll

7 ↗

(On Diff #207637)

Should we also change sFast() check in the fold above this new fold to just “afn” check ? @efriedma @spatel

[efriedma]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1354 ↗

(On Diff #207624)

lib/Analysis/ConstantFolding.cpp has some code that calls APFloat::convertToDouble() and uses the host C library's implementation of various routines: specifically, fabs, log2, log, log10, exp, exp2, sin, cos, sqrt, acos, asin, atan, ceil, cosh, exp, floor, round, sinh, tan, tanh, pow, fmod, atan2. This is not ideal, but the trigonometric and exponential functions are tricky to implement with correct rounding, and nobody has spent the time to implement them on APFloat.

It's worth noting that we never fold the long double versions.

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1354 ↗

(On Diff #207624)

Thanks, I will use this solution.

[xbolva00]

Fold log2 "manually".

[evandro]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1355 ↗

(On Diff #207781)

Shouldn't this call and the one below be to log2()?

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1355 ↗

(On Diff #207781)

Ah, yes. Fixed.

[evandro]

Since using exp2(log()) was mathematically incorrect, have you run any benchmark that validates the results, such SPEC CPU2006 or CPU2017? If so, what kind of improvement did it register?

[xbolva00]

In D64099#1569028, @evandro wrote:

Since using exp2(log()) was mathematically incorrect, have you run any benchmark that validates the results, such SPEC CPU2006 or CPU2017? If so, what kind of improvement did it register?

I tested the first patch and the second revision with change to exp2 locally with simple examples to check for correctness and performance - and yes, I didn’t check previous revision with folding so a mistake was made.

I have no access to the SPEC benchmarks.

[xbolva00]

Precommited tests, rebased.

[evandro]

In D64099#1569035, @xbolva00 wrote:

I tested the first patch and the second revision with change to exp2 locally with simple examples to check for correctness and performance - and yes, I didn’t check previous revision with folding so a mistake was made.

I have no access to the SPEC benchmarks.

What correctness tests did you run? If necessary, I can run SPEC to validate this patch at least on x86-64.

[xbolva00]

GCC has exp variant of this transformation so I checked their preconditions - unsafe math. My first patch had isFast() check but @efriedma requested to specify it better. I think afn/ninf/nnan is all we need. I wrote some small tests and compared printed results between Clang and GCC. I don’t think we could formally prove this transformation with Alive.

So, If you can test this patch with SPEC, please do - Thanks!

[evandro]

It was actually harder to find a SPEC benchmark that triggered this case. As a matter of fact, it shows up only in CPU2017's 525.x264_r. But I can confirm that it works successfully.

Thank you for this patch.

lib/Transforms/Utils/SimplifyLibCalls.cpp

1238 ↗

(On Diff #208036)

Please, update this comment.

1350 ↗

(On Diff #208036)

Not really necessary to specify the conditions in the comment.

1360 ↗

(On Diff #208036)

"mul" was used above to describe products.

test/Transforms/InstCombine/pow-exp.ll

208 ↗

(On Diff #208036)

Again, not really necessary to spell out the conditions in the comment.

[xbolva00]

Addressed review notes.

[xbolva00]

In D64099#1577068, @evandro wrote:

It was actually harder to find a SPEC benchmark that triggered this case. As a matter of fact, it shows up only in CPU2017's 525.x264_r. But I can confirm that it works successfully.

Thank you for this patch.

Thanks !

llvm/trunk/lib/Transforms/Utils/SimplifyLibCalls.cpp

static Value *getPow(Value *InnerChain[33], unsigned Exp, IRBuilder<> &B) {
   };
 
   InnerChain[Exp] = B.CreateFMul(getPow(InnerChain, AddChain[Exp][0], B),
                                  getPow(InnerChain, AddChain[Exp][1], B));
   return InnerChain[Exp];
 }
 
 /// Use exp{,2}(x * y) for pow(exp{,2}(x), y);
-/// exp2(n * x) for pow(2.0 ** n, x); exp10(x) for pow(10.0, x).
+/// exp2(n * x) for pow(2.0 ** n, x); exp10(x) for pow(10.0, x);
+/// exp2(log2(C)*x) for pow(C,x).
 Value *LibCallSimplifier::replacePowWithExp(CallInst *Pow, IRBuilder<> &B) {
   Value *Base = Pow->getArgOperand(0), *Expo = Pow->getArgOperand(1);
   AttributeList Attrs = Pow->getCalledFunction()->getAttributes();
   Module *Mod = Pow->getModule();
   Type *Ty = Pow->getType();
   bool Ignored;
 
   // Evaluate special cases related to a nested function as the base.
Value *LibCallSimplifier::replacePowWithExp(CallInst *Pow, IRBuilder<> &B) {
 
   // pow(10.0, x) -> exp10(x)
   // TODO: There is no exp10() intrinsic yet, but some day there shall be one.
   if (match(Base, m_SpecificFP(10.0)) &&
       hasUnaryFloatFn(TLI, Ty, LibFunc_exp10, LibFunc_exp10f, LibFunc_exp10l))
     return emitUnaryFloatFnCall(Expo, TLI, LibFunc_exp10, LibFunc_exp10f,
                                 LibFunc_exp10l, B, Attrs);
 
+  // pow(C,x) -> exp2(log2(C)*x)
+  if (Pow->hasOneUse() && Pow->hasApproxFunc() && Pow->hasNoNaNs() &&
+      Pow->hasNoInfs() && BaseF->isNormal() && !BaseF->isNegative()) {
+    Value *Log = nullptr;
+    if (Ty->isFloatTy())
+      Log = ConstantFP::get(Ty, std::log2(BaseF->convertToFloat()));
+    else if (Ty->isDoubleTy())
+      Log = ConstantFP::get(Ty, std::log2(BaseF->convertToDouble()));
+
+    if (Log) {
+      Value *FMul = B.CreateFMul(Log, Expo, "mul");
+      if (Pow->doesNotAccessMemory()) {
+        return B.CreateCall(Intrinsic::getDeclaration(Mod, Intrinsic::exp2, Ty),
+                            FMul, "exp2");
+      } else {
+        if (hasUnaryFloatFn(TLI, Ty, LibFunc_exp2, LibFunc_exp2f,
+                            LibFunc_exp2l))
+          return emitUnaryFloatFnCall(FMul, TLI, LibFunc_exp2, LibFunc_exp2f,
+                                      LibFunc_exp2l, B, Attrs);
+      }
+    }
+  }
   return nullptr;
 }
 
 static Value *getSqrtCall(Value *V, AttributeList Attrs, bool NoErrno,
                           Module *M, IRBuilder<> &B,
                           const TargetLibraryInfo *TLI) {
   // If errno is never set, then use the intrinsic for sqrt().
   if (NoErrno) {
default:
     break;
   }
   return nullptr;
 }
 
 FortifiedLibCallSimplifier::FortifiedLibCallSimplifier(
     const TargetLibraryInfo *TLI, bool OnlyLowerUnknownSize)
     : TLI(TLI), OnlyLowerUnknownSize(OnlyLowerUnknownSize) {}
 No newline at end of file

llvm/trunk/test/Transforms/InstCombine/pow-exp.ll

 ; CHECK-NEXT:    [[POW:%.*]] = call fast double @llvm.pow.f64(double [[CALL1]], double [[P1:%.*]])
 ; CHECK-NEXT:    ret double [[POW]]
 ;
   %call1 = call fast double %fptr()
   %pow = call fast double @llvm.pow.f64(double %call1, double %p1)
   ret double %pow
 }
 
+; pow(C,x) -> exp2(log2(C)*x)
+
 declare void @use_d(double)
 declare void @use_f(float)
 
 define double @pow_ok_base(double %e) {
 ; CHECK-LABEL: @pow_ok_base(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call nnan ninf afn double @pow(double 0x3FE6666666666666, double [[E:%.*]])
-; CHECK-NEXT:    ret double [[CALL]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul nnan ninf afn double [[E:%.*]], 0xBFE0776228967D13
+; CHECK-NEXT:    [[EXP2:%.*]] = call nnan ninf afn double @exp2(double [[MUL]])
+; CHECK-NEXT:    ret double [[EXP2]]
 ;
   %call = tail call afn nnan ninf double @pow(double 0x3FE6666666666666, double %e)
   ret double %call
 }
 
 define double @pow_ok_base_fast(double %e) {
 ; CHECK-LABEL: @pow_ok_base_fast(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call fast double @pow(double 0x3FE6666666666666, double [[E:%.*]])
-; CHECK-NEXT:    ret double [[CALL]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul fast double [[E:%.*]], 0xBFE0776228967D13
+; CHECK-NEXT:    [[EXP2:%.*]] = call fast double @exp2(double [[MUL]])
+; CHECK-NEXT:    ret double [[EXP2]]
 ;
   %call = tail call fast double @pow(double 0x3FE6666666666666, double %e)
   ret double %call
 }
 
 define double @pow_ok_base2(double %e) {
 ; CHECK-LABEL: @pow_ok_base2(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call nnan ninf afn double @pow(double 1.770000e+01, double [[E:%.*]])
-; CHECK-NEXT:    ret double [[CALL]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul nnan ninf afn double [[E:%.*]], 0x4010952C788751AC
+; CHECK-NEXT:    [[EXP2:%.*]] = call nnan ninf afn double @exp2(double [[MUL]])
+; CHECK-NEXT:    ret double [[EXP2]]
 ;
   %call = tail call afn nnan ninf double @pow(double 1.770000e+01, double %e)
   ret double %call
 }
 
 define double @pow_ok_base3(double %e) {
 ; CHECK-LABEL: @pow_ok_base3(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call nnan ninf afn double @pow(double 1.010000e+01, double [[E:%.*]])
-; CHECK-NEXT:    ret double [[CALL]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul nnan ninf afn double [[E:%.*]], 0x400AB0B5584886CD
+; CHECK-NEXT:    [[EXP2:%.*]] = call nnan ninf afn double @exp2(double [[MUL]])
+; CHECK-NEXT:    ret double [[EXP2]]
 ;
   %call = tail call afn nnan ninf double @pow(double 1.010000e+01, double %e)
   ret double %call
 }
 
 define double @pow_ok_ten_base(double %e) {
 ; CHECK-LABEL: @pow_ok_ten_base(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call nnan ninf afn double @pow(double 1.000000e+01, double [[E:%.*]])
-; CHECK-NEXT:    ret double [[CALL]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul nnan ninf afn double [[E:%.*]], 0x400A934F0979A371
+; CHECK-NEXT:    [[EXP2:%.*]] = call nnan ninf afn double @exp2(double [[MUL]])
+; CHECK-NEXT:    ret double [[EXP2]]
 ;
   %call = tail call afn nnan ninf double @pow(double 1.000000e+01, double %e)
   ret double %call
 }
 
 define float @powf_ok_base(float %e) {
 ; CHECK-LABEL: @powf_ok_base(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call nnan ninf afn float @powf(float 0x3FE6666660000000, float [[E:%.*]])
-; CHECK-NEXT:    ret float [[CALL]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul nnan ninf afn float [[E:%.*]], 0xBFE0776240000000
+; CHECK-NEXT:    [[EXP2F:%.*]] = call nnan ninf afn float @exp2f(float [[MUL]])
+; CHECK-NEXT:    ret float [[EXP2F]]
 ;
   %call = tail call afn nnan ninf float @powf(float 0x3FE6666660000000, float %e)
   ret float %call
 }
 
 define float @powf_ok_base2(float %e) {
 ; CHECK-LABEL: @powf_ok_base2(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call nnan ninf afn float @powf(float 0x4031B33340000000, float [[E:%.*]])
-; CHECK-NEXT:    ret float [[CALL]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul nnan ninf afn float [[E:%.*]], 0x4010952C80000000
+; CHECK-NEXT:    [[EXP2F:%.*]] = call nnan ninf afn float @exp2f(float [[MUL]])
+; CHECK-NEXT:    ret float [[EXP2F]]
 ;
   %call = tail call afn nnan ninf float @powf(float 0x4031B33340000000, float %e)
   ret float %call
 }
 
 define float @powf_ok_base3(float %e) {
 ; CHECK-LABEL: @powf_ok_base3(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call nnan ninf afn float @powf(float 0x4024333340000000, float [[E:%.*]])
-; CHECK-NEXT:    ret float [[CALL]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul nnan ninf afn float [[E:%.*]], 0x400AB0B560000000
+; CHECK-NEXT:    [[EXP2F:%.*]] = call nnan ninf afn float @exp2f(float [[MUL]])
+; CHECK-NEXT:    ret float [[EXP2F]]
 ;
   %call = tail call afn nnan ninf float @powf(float 0x4024333340000000, float %e)
   ret float %call
 }
 
 define float @powf_ok_ten_base(float %e) {
 ; CHECK-LABEL: @powf_ok_ten_base(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call nnan ninf afn float @powf(float 1.000000e+01, float [[E:%.*]])
-; CHECK-NEXT:    ret float [[CALL]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul nnan ninf afn float [[E:%.*]], 0x400A934F00000000
+; CHECK-NEXT:    [[EXP2F:%.*]] = call nnan ninf afn float @exp2f(float [[MUL]])
+; CHECK-NEXT:    ret float [[EXP2F]]
 ;
   %call = tail call afn nnan ninf float @powf(float 1.000000e+01, float %e)
   ret float %call
 }
 
+; Negative tests
+
 define double @pow_zero_base(double %e) {
 ; CHECK-LABEL: @pow_zero_base(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call nnan ninf afn double @pow(double 0.000000e+00, double [[E:%.*]])
 ; CHECK-NEXT:    ret double [[CALL]]
 ;
   %call = tail call afn nnan ninf double @pow(double 0.000000e+00, double %e)
   ret double %call
 }

llvm/trunk/test/Transforms/InstCombine/pow_fp_int.ll

;
   ret double %res
 }
 
 ; Negative tests
 
 define double @pow_uitofp_const_base_fast_i32(i32 %x) {
 ; CHECK-LABEL: @pow_uitofp_const_base_fast_i32(
 ; CHECK-NEXT:    [[SUBFP:%.*]] = uitofp i32 [[X:%.*]] to float
-; CHECK-NEXT:    [[POW:%.*]] = tail call fast float @llvm.pow.f32(float 7.000000e+00, float [[SUBFP]])
-; CHECK-NEXT:    [[RES:%.*]] = fpext float [[POW]] to double
+; CHECK-NEXT:    [[MUL:%.*]] = fmul fast float [[SUBFP]], 0x4006757680000000
+; CHECK-NEXT:    [[EXP2:%.*]] = call fast float @llvm.exp2.f32(float [[MUL]])
+; CHECK-NEXT:    [[RES:%.*]] = fpext float [[EXP2]] to double
 ; CHECK-NEXT:    ret double [[RES]]
 ;
   %subfp = uitofp i32 %x to float
   %pow = tail call fast float @llvm.pow.f32(float 7.000000e+00, float %subfp)
   %res = fpext float %pow to double
   ret double %res
 }
 
;
   %subfp = uitofp i32 %x to double
   %res = tail call fast double @llvm.pow.f64(double %base, double %subfp)
   ret double %res
 }
 
 define double @pow_sitofp_const_base_fast_i64(i64 %x) {
 ; CHECK-LABEL: @pow_sitofp_const_base_fast_i64(
 ; CHECK-NEXT:    [[SUBFP:%.*]] = sitofp i64 [[X:%.*]] to float
-; CHECK-NEXT:    [[POW:%.*]] = tail call fast float @llvm.pow.f32(float 7.000000e+00, float [[SUBFP]])
-; CHECK-NEXT:    [[RES:%.*]] = fpext float [[POW]] to double
+; CHECK-NEXT:    [[MUL:%.*]] = fmul fast float [[SUBFP]], 0x4006757680000000
+; CHECK-NEXT:    [[EXP2:%.*]] = call fast float @llvm.exp2.f32(float [[MUL]])
+; CHECK-NEXT:    [[RES:%.*]] = fpext float [[EXP2]] to double
 ; CHECK-NEXT:    ret double [[RES]]
 ;
   %subfp = sitofp i64 %x to float
   %pow = tail call fast float @llvm.pow.f32(float 7.000000e+00, float %subfp)
   %res = fpext float %pow to double
   ret double %res
 }
 
 define double @pow_uitofp_const_base_fast_i64(i64 %x) {
 ; CHECK-LABEL: @pow_uitofp_const_base_fast_i64(
 ; CHECK-NEXT:    [[SUBFP:%.*]] = uitofp i64 [[X:%.*]] to float
-; CHECK-NEXT:    [[POW:%.*]] = tail call fast float @llvm.pow.f32(float 7.000000e+00, float [[SUBFP]])
-; CHECK-NEXT:    [[RES:%.*]] = fpext float [[POW]] to double
+; CHECK-NEXT:    [[MUL:%.*]] = fmul fast float [[SUBFP]], 0x4006757680000000
+; CHECK-NEXT:    [[EXP2:%.*]] = call fast float @llvm.exp2.f32(float [[MUL]])
+; CHECK-NEXT:    [[RES:%.*]] = fpext float [[EXP2]] to double
 ; CHECK-NEXT:    ret double [[RES]]
 ;
   %subfp = uitofp i64 %x to float
   %pow = tail call fast float @llvm.pow.f32(float 7.000000e+00, float %subfp)
   %res = fpext float %pow to double
   ret double %res
 }