[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

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

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

emitUnaryFloatFnCall automatically folds it? @spatel @lebedev.ri

Not sure how to get log2 of APFloat...

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1354

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

[xbolva00]

test/Transforms/InstCombine/pow-exp.ll

9

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

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

Thanks, I will use this solution.

[xbolva00]

Fold log2 "manually".

[evandro]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1355

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

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1355

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

Please, update this comment.

1350

Not really necessary to specify the conditions in the comment.

1360

"mul" was used above to describe products.

test/Transforms/InstCombine/pow-exp.ll

208

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 !

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).
 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 C > 0, C != inf, C != NaN
+  if (Pow->hasOneUse() && Pow->hasApproxFunc() && BaseF->isNormal() &&
+      !BaseF->isNegative()) {
+    Value *Log = nullptr;
+    if (Ty->isFloatTy())
+      Log = ConstantFP::get(Ty, std::log(BaseF->convertToFloat()));
+    else if (Ty->isDoubleTy())
+      Log = ConstantFP::get(Ty, std::log(BaseF->convertToDouble()));
+    if (Log) {
+      Value *FMul = B.CreateFMul(Log, Expo, "logmul");
+      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

test/Transforms/InstCombine/pow-exp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define float @powf_expf(float %x, float %y) {
 ; CHECK-LABEL: @powf_expf(
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul fast float [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[EXP:%.*]] = call fast float @llvm.exp.f32(float [[MUL]])
 ; CHECK-NEXT:    ret float [[EXP]]
 ;
   %call = call fast float @expf(float %x) nounwind readnone
   %pow = call fast float @llvm.pow.f32(float %call, float %y)
   ret float %pow
 }
 
 define float @powf_expf_libcall(float %x, float %y) {
 ; CHECK-LABEL: @powf_expf_libcall(
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul fast float [[X:%.*]], [[Y:%.*]]

 ; 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
 }
 
+declare void @use_d(double)
+declare void @use_f(float)
+
+define double @pow_ok_base(double %e) {
+; CHECK-LABEL: @pow_ok_base(
+; CHECK-NEXT:    [[LOGMUL:%.*]] = fmul afn double [[E:%.*]], 0xBFD6D3C324E13F50
+; CHECK-NEXT:    [[EXP2:%.*]] = call afn double @exp2(double [[LOGMUL]])
+; CHECK-NEXT:    ret double [[EXP2]]
+;
+  %call = tail call afn double @pow(double 0x3FE6666666666666, double %e)
+  ret double %call
+}
+
+define double @pow_ok_base2(double %e) {
+; CHECK-LABEL: @pow_ok_base2(
+; CHECK-NEXT:    [[LOGMUL:%.*]] = fmul afn double [[E:%.*]], 0x4006FD0F752F7F61
+; CHECK-NEXT:    [[EXP2:%.*]] = call afn double @exp2(double [[LOGMUL]])
+; CHECK-NEXT:    ret double [[EXP2]]
+;
+  %call = tail call afn 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:    [[LOGMUL:%.*]] = fmul afn double [[E:%.*]], 0x4002801292821F4C
+; CHECK-NEXT:    [[EXP2:%.*]] = call afn double @exp2(double [[LOGMUL]])
+; CHECK-NEXT:    ret double [[EXP2]]
+;
+  %call = tail call afn 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:    [[LOGMUL:%.*]] = fmul afn double [[E:%.*]], 0x40026BB1BBB55516
+; CHECK-NEXT:    [[EXP2:%.*]] = call afn double @exp2(double [[LOGMUL]])
+; CHECK-NEXT:    ret double [[EXP2]]
+;
+  %call = tail call afn 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:    [[LOGMUL:%.*]] = fmul afn float [[E:%.*]], 0xBFD6D3C340000000
+; CHECK-NEXT:    [[EXP2F:%.*]] = call afn float @exp2f(float [[LOGMUL]])
+; CHECK-NEXT:    ret float [[EXP2F]]
+;
+  %call = tail call afn float @powf(float 0x3FE6666660000000, float %e)
+  ret float %call
+}
+
+define float @powf_ok_base2(float %e) {
+; CHECK-LABEL: @powf_ok_base2(
+; CHECK-NEXT:    [[LOGMUL:%.*]] = fmul afn float [[E:%.*]], 0x4006FD0F80000000
+; CHECK-NEXT:    [[EXP2F:%.*]] = call afn float @exp2f(float [[LOGMUL]])
+; CHECK-NEXT:    ret float [[EXP2F]]
+;
+  %call = tail call afn float @powf(float 0x4031B33340000000, float %e)
+  ret float %call
+}
+
+define float @powf_ok_base3(float %e) {
+; CHECK-LABEL: @powf_ok_base3(
+; CHECK-NEXT:    [[LOGMUL:%.*]] = fmul afn float [[E:%.*]], 0x40028012A0000000
+; CHECK-NEXT:    [[EXP2F:%.*]] = call afn float @exp2f(float [[LOGMUL]])
+; CHECK-NEXT:    ret float [[EXP2F]]
+;
+  %call = tail call afn 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:    [[LOGMUL:%.*]] = fmul afn float [[E:%.*]], 0x40026BB1C0000000
+; CHECK-NEXT:    [[EXP2F:%.*]] = call afn float @exp2f(float [[LOGMUL]])
+; CHECK-NEXT:    ret float [[EXP2F]]
+;
+  %call = tail call afn float @powf(float 1.000000e+01, float %e)
+  ret float %call
+}
+
+define double @pow_zero_base(double %e) {
+; CHECK-LABEL: @pow_zero_base(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn double @pow(double 0.000000e+00, double [[E:%.*]])
+; CHECK-NEXT:    ret double [[CALL]]
+;
+  %call = tail call afn double @pow(double 0.000000e+00, double %e)
+  ret double %call
+}
+
+define double @pow_zero_base2(double %e) {
+; CHECK-LABEL: @pow_zero_base2(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn double @pow(double -0.000000e+00, double [[E:%.*]])
+; CHECK-NEXT:    ret double [[CALL]]
+;
+  %call = tail call afn double @pow(double -0.000000e+00, double %e)
+  ret double %call
+}
+
+define double @pow_inf_base(double %e) {
+; CHECK-LABEL: @pow_inf_base(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn double @pow(double 0x7FF0000000000000, double [[E:%.*]])
+; CHECK-NEXT:    ret double [[CALL]]
+;
+  %call = tail call afn double @pow(double 0x7FF0000000000000, double %e)
+  ret double %call
+}
+
+define double @pow_nan_base(double %e) {
+; CHECK-LABEL: @pow_nan_base(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn double @pow(double 0x7FF8000000000000, double [[E:%.*]])
+; CHECK-NEXT:    ret double [[CALL]]
+;
+  %call = tail call afn double @pow(double 0x7FF8000000000000, double %e)
+  ret double %call
+}
+
+define double @pow_negative_base(double %e) {
+; CHECK-LABEL: @pow_negative_base(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn double @pow(double -4.000000e+00, double [[E:%.*]])
+; CHECK-NEXT:    ret double [[CALL]]
+;
+  %call = tail call afn double @pow(double -4.000000e+00, double %e)
+  ret double %call
+}
+
+define double @pow_multiuse(double %e) {
+; CHECK-LABEL: @pow_multiuse(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn double @pow(double 5.000000e+00, double [[E:%.*]])
+; CHECK-NEXT:    tail call void @use_d(double [[CALL]])
+; CHECK-NEXT:    ret double [[CALL]]
+;
+  %call = tail call afn double @pow(double 5.000000e+00, double %e)
+  tail call void @use_d(double %call)
+  ret double %call
+}
+
+define double @pow_ok_base_no_afn(double %e) {
+; CHECK-LABEL: @pow_ok_base_no_afn(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call double @pow(double 0x3FE6666666666666, double [[E:%.*]])
+; CHECK-NEXT:    ret double [[CALL]]
+;
+  %call = tail call double @pow(double 0x3FE6666666666666, double %e)
+  ret double %call
+}
+
+define float @powf_zero_base(float %e) {
+; CHECK-LABEL: @powf_zero_base(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn float @powf(float 0.000000e+00, float [[E:%.*]])
+; CHECK-NEXT:    ret float [[CALL]]
+;
+  %call = tail call afn float @powf(float 0.000000e+00, float %e)
+  ret float %call
+}
+
+define float @powf_zero_base2(float %e) {
+; CHECK-LABEL: @powf_zero_base2(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn float @powf(float -0.000000e+00, float [[E:%.*]])
+; CHECK-NEXT:    ret float [[CALL]]
+;
+  %call = tail call afn float @powf(float -0.000000e+00, float %e)
+  ret float %call
+}
+
+define float @powf_inf_base(float %e) {
+; CHECK-LABEL: @powf_inf_base(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn float @powf(float 0x7FF0000000000000, float [[E:%.*]])
+; CHECK-NEXT:    ret float [[CALL]]
+;
+  %call = tail call afn float @powf(float 0x7FF0000000000000, float %e)
+  ret float %call
+}
+
+define float @powf_nan_base(float %e) {
+; CHECK-LABEL: @powf_nan_base(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn float @powf(float 0x7FF8000000000000, float [[E:%.*]])
+; CHECK-NEXT:    ret float [[CALL]]
+;
+  %call = tail call afn float @powf(float 0x7FF8000000000000, float %e)
+  ret float %call
+}
+
+define float @powf_negative_base(float %e) {
+; CHECK-LABEL: @powf_negative_base(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn float @powf(float -4.000000e+00, float [[E:%.*]])
+; CHECK-NEXT:    ret float [[CALL]]
+;
+  %call = tail call afn float @powf(float -4.000000e+00, float %e)
+  ret float %call
+}
+
+define float @powf_multiuse(float %e) {
+; CHECK-LABEL: @powf_multiuse(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn float @powf(float 5.000000e+00, float [[E:%.*]])
+; CHECK-NEXT:    tail call void @use_f(float [[CALL]])
+; CHECK-NEXT:    ret float [[CALL]]
+;
+  %call = tail call afn float @powf(float 5.000000e+00, float %e)
+  tail call void @use_f(float %call)
+  ret float %call
+}
+
+define float @powf_ok_base_no_afn(float %e) {
+; CHECK-LABEL: @powf_ok_base_no_afn(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call float @powf(float 0x3FE6666660000000, float [[E:%.*]])
+; CHECK-NEXT:    ret float [[CALL]]
+;
+  %call = tail call float @powf(float 0x3FE6666660000000, float %e)
+  ret float %call
+}
+
+define fp128 @powl_long_dbl_no_fold(fp128 %e) {
+; CHECK-LABEL: @powl_long_dbl_no_fold(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call afn fp128 @powl(fp128 0xL00000000000000005001000000000000, fp128 [[E:%.*]])
+; CHECK-NEXT:    ret fp128 [[CALL]]
+;
+  %call = tail call afn fp128 @powl(fp128 0xL00000000000000005001000000000000, fp128 %e)
+  ret fp128 %call
+}
+
 declare float @expf(float)
 declare double @exp(double)
 declare fp128 @expl(fp128)
 declare float @exp2f(float)
 declare double @exp2(double)
 declare fp128 @exp2l(fp128)
 declare float @exp10f(float)
 declare double @exp10(double)
 declare fp128 @exp10l(fp128)
 declare float @powf(float, float)
 declare double @pow(double, double)
 declare fp128 @powl(fp128, fp128)
 declare float @llvm.pow.f32(float, float)
 declare double @llvm.pow.f64(double, double)
 declare fp128 @llvm.pow.f128(fp128, fp128)

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:    [[LOGMUL:%.*]] = fmul fast float [[SUBFP]], 0x3FFF2272A0000000
+; CHECK-NEXT:    [[EXP2:%.*]] = call fast float @llvm.exp2.f32(float [[LOGMUL]])
+; 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:    [[LOGMUL:%.*]] = fmul fast float [[SUBFP]], 0x3FFF2272A0000000
+; CHECK-NEXT:    [[EXP2:%.*]] = call fast float @llvm.exp2.f32(float [[LOGMUL]])
+; 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:    [[LOGMUL:%.*]] = fmul fast float [[SUBFP]], 0x3FFF2272A0000000
+; CHECK-NEXT:    [[EXP2:%.*]] = call fast float @llvm.exp2.f32(float [[LOGMUL]])
+; 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
 }