[InstCombine] Missed optimization in math expression: pow multiplications

[spatel]

Summary

This patch enables folding following expressions under -ffast-math flag:
pow(a, b) * a -> pow(a, b+1)
(1/a) * pow(a, b) -> pow(a, b-1)
pow(a, b) * pow(c, b) -> pow(a*c, b)
pow(a, b) * pow(a, c) -> pow(a, b+c)
Motivation: https://bugs.llvm.org/show_bug.cgi?id=35595.

[davide]

I'm slightly worried about all this bunch of missing instcombines added, as InstCombine is already really really slow.

[davide]

That said, this one is probably one we really want. I skimmed the code quickly and I think it's correct, but please wait for somebody else to take a look

[spatel]

Why is this patch WIP? The mentioned case of 'pow(a, x) * a * a * a * a -> pow(a, x+4)' is handled already by this patch.

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

377–380

You mentioned that you see warnings without explicitly setting these to nullptr in Xcode. I use Xcode as an IDE too, but I don't see any warnings like that when I remove the nullptrs.

If this is really a problem, then you must be getting hundreds of these warnings for existing code that does not initialize things like this? I'd prefer not to bloat the code unnecessarily.

385

Need to handle commuted versions too (please add a test):

define double @pow_ab_x_a_fast_commute(double %a, double %b)  {
  %c = fdiv double 1.0, %a  ; defeat complexity-based canonicalization of operands
  %p = call fast double @llvm.pow.f64(double %a, double %b)
  %mul = fmul fast double %c, %p
  ret double %mul
}

386–387

Here and below: use m_Specific instead of the trailing check for equality?

395–396

Please use variable names that match the formulas in the code comments for better readability.

[Quolyk]

pow(a, x) * a * a * a * a emits to

define double @pow_ab_x_aaaa_fast(double %a, double %x) {
  %1 = call fast double @llvm.pow.f64(double %a, double %x)
  %2 = fmul fast double %a, %a
  %3 = fmul fast double %2, %2
  %mul4 = fmul fast double %3, %1
  ret double %mul4
}

I don't see obvious ways to fold these instructions. I Would appreciate if somebody could help me with this.

[spatel]

In D41608#969442, @Quolyk wrote:

pow(a, x) * a * a * a * a emits to

define double @pow_ab_x_aaaa_fast(double %a, double %x) {
  %1 = call fast double @llvm.pow.f64(double %a, double %x)
  %2 = fmul fast double %a, %a
  %3 = fmul fast double %2, %2
  %mul4 = fmul fast double %3, %1
  ret double %mul4
}

I don't see obvious ways to fold these instructions. I Would appreciate if somebody could help me with this.

This looks like it went through -reassociate first? I was checking with a straight IR translation, so we're just multiplying by 'a' over and over. This would require more complex logic, so that's a different patch (and I'm not sure where it would belong).

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

385

This comment was marked 'Done', but I don't see code to account for this or the test that I suggested.

[Quolyk]

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

385

My bad, I thought fdiv_pow_ab_a test would be enough.

[Quolyk]

Update tests. Apply patch only for pow multiplications. Pow divisions will be considered in different patch.

[spatel]

This patch is trying to do too many things at once. Please split only the 1st transform (pow(X, Y) * X -> pow(X, Y+1)) into its own patch, and let's continue looking at that alone as a 1st step. You should consider (and include tests for) these variations:

1. Commuted operands for fmul.
2. Extra uses of the pow result.
3. Vector types.
4. Additional FMF.

We don't necessarily need tests for every permutation of those, but there needs to be more coverage than what we see here currently.

test/Transforms/InstCombine/fmul-pow.ll

28–29

This is a misleading test name. This isn't the commuted version of the previous test - the fmul does not have a common operand with the pow().

I think you want something like this:

declare double @call_f64(double)
define double @pow_ab_a_reassoc(double %p, double %b) {
  %a = call double @call_f64(double %p)  ; thwart complexity-based canonicalization
  %pow = call double @llvm.pow.f64(double %a, double %b)
  %mul = fmul reassoc double %a, %pow
  ret double %mul
}

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

[spatel]

The folds shown here have all been added now, so this patch can be abandoned:
7736c1936a93d7
914576c1f0b669
61af2ab68142729
072b03c4714ea4

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y))))
     return BinaryOperator::CreateFMulFMF(X, Y, &I);
 
   // -X * C --> X * -C
   Constant *C;
   if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C)))
     return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &I);
 
   // Sink negation: -X * Y --> -(X * Y)
   if (match(Op0, m_OneUse(m_FNeg(m_Value(X)))))
     return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op1, &I), &I);
 
   // Sink negation: Y * -X --> -(X * Y)
   if (match(Op1, m_OneUse(m_FNeg(m_Value(X)))))
     return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op0, &I), &I);
 
   // fabs(X) * fabs(X) -> X * X
   if (Op0 == Op1 && match(Op0, m_Intrinsic<Intrinsic::fabs>(m_Value(X))))
     return BinaryOperator::CreateFMulFMF(X, X, &I);
 
   // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
   if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
     return replaceInstUsesWith(I, V);
 
   if (I.hasAllowReassoc()) {
     // Reassociate constant RHS with another constant to form constant
     // expression.
     if (match(Op1, m_Constant(C)) && C->isFiniteNonZeroFP()) {
       Constant *C1;
       if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) {
         // (C1 / X) * C --> (C * C1) / X
         Constant *CC1 = ConstantExpr::getFMul(C, C1);
         if (CC1->isNormalFP())
           return BinaryOperator::CreateFDivFMF(CC1, X, &I);
       }
       if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
         // (X / C1) * C --> X * (C / C1)
if (I.hasAllowReassoc()) {
     if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) &&
         match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y))) &&
         (Op0->hasOneUse() || Op1->hasOneUse())) {
       Value *XY = Builder.CreateFAddFMF(X, Y, &I);
       Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I);
       return replaceInstUsesWith(I, Exp2);
     }
 
+    // pow(X, Y) * X -> pow(X, Y+1)
+    if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Specific(Op1), m_Value(Y)))) {
+      Value *One = ConstantFP::get(Op0->getType(), 1.0);
+      Value *YIncr = Builder.CreateFAddFMF(Y, One, &I);
+      Value *Pow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, Op1, YIncr, &I);
+      return replaceInstUsesWith(I, Pow);
+    }
+
+    // (1/X) * pow(X, Y) -> pow(X, Y-1)
+    if (match(Op0, m_OneUse(m_FDiv(m_SpecificFP(1.0), m_Value(X)))) &&
+        match(Op1, m_Intrinsic<Intrinsic::pow>(m_Specific(X), m_Value(Y)))) {
+      Value *One = ConstantFP::get(Op0->getType(), 1.0);
+      Value *YDecr = Builder.CreateFSubFMF(Y, One, &I);
+      Value *Pow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, X, YDecr, &I);
+      return replaceInstUsesWith(I, Pow);
+    }
+
+    Value *Z;
+    // pow(X, Y) * pow(Z, Y) -> pow(X*Z, Y)
+    if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Value(X), m_Value(Y))) &&
+        match(Op1, m_Intrinsic<Intrinsic::pow>(m_Value(Z), m_Specific(Y)))) {
+      Value *XZ = Builder.CreateFMulFMF(X, Z, &I);
+      Value *Pow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, XZ, Y, &I);
+      return replaceInstUsesWith(I, Pow);
+    }
+
+    // pow(X, Y) * pow(X, Z) -> pow(X, Y+Z)
+    if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Value(X), m_Value(Y))) &&
+        match(Op1, m_Intrinsic<Intrinsic::pow>(m_Specific(X), m_Value(Z)))) {
+      Value *YZ = Builder.CreateFAddFMF(Y, Z, &I);
+      Value *Pow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, X, YZ, &I);
+      return replaceInstUsesWith(I, Pow);
+    }
+
     // (X*Y) * X => (X*X) * Y where Y != X
     //  The purpose is two-fold:
     //   1) to form a power expression (of X).
     //   2) potentially shorten the critical path: After transformation, the
     //  latency of the instruction Y is amortized by the expression of X*X,
     //  and therefore Y is in a "less critical" position compared to what it
     //  was before the transformation.
     if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) &&

test/Transforms/InstCombine/fmul-pow.ll

 ;
   %1 = call double @llvm.pow.f64(double %a, double %b)
   %mul = fmul double %1, %a
   ret double %mul
 }
 
 define double @pow_ab_a_reassoc(double %a, double %b)  {
 ; CHECK-LABEL: @pow_ab_a_reassoc(
-; CHECK-NEXT:    [[TMP1:%.*]] = call double @llvm.pow.f64(double [[A:%.*]], double [[B:%.*]])
-; CHECK-NEXT:    [[MUL:%.*]] = fmul reassoc double [[TMP1]], [[A]]
-; CHECK-NEXT:    ret double [[MUL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd reassoc double [[B:%.*]], 1.000000e+00
+; CHECK-NEXT:    [[TMP2:%.*]] = call reassoc double @llvm.pow.f64(double [[A:%.*]], double [[TMP1]])
+; CHECK-NEXT:    ret double [[TMP2]]
 ;
   %1 = call double @llvm.pow.f64(double %a, double %b)
   %mul = fmul reassoc double %1, %a
   ret double %mul
 }
 
 define double @pow_ab_a_reassoc_commute(double %a, double %b)  {
 ; CHECK-LABEL: @pow_ab_a_reassoc_commute(
-; CHECK-NEXT:    [[TMP1:%.*]] = fdiv double 1.000000e+00, [[A:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = call double @llvm.pow.f64(double [[A]], double [[B:%.*]])
-; CHECK-NEXT:    [[MUL:%.*]] = fmul reassoc double [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    ret double [[MUL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd reassoc double [[B:%.*]], -1.000000e+00
+; CHECK-NEXT:    [[TMP2:%.*]] = call reassoc double @llvm.pow.f64(double [[A:%.*]], double [[TMP1]])
+; CHECK-NEXT:    ret double [[TMP2]]
 ;
   %1 = fdiv double 1.0, %a
   %2 = call double @llvm.pow.f64(double %a, double %b)
   %mul = fmul reassoc double %1, %2
   ret double %mul
 }
 
 define double @pow_ab_pow_cb(double %a, double %b, double %c) {
 ; CHECK-LABEL: @pow_ab_pow_cb(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call double @llvm.pow.f64(double [[A:%.*]], double [[B:%.*]])
 ; CHECK-NEXT:    [[TMP2:%.*]] = call double @llvm.pow.f64(double [[C:%.*]], double [[B]])
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul double [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret double [[MUL]]
 ;
   %1 = call double @llvm.pow.f64(double %a, double %b)
   %2 = call double @llvm.pow.f64(double %c, double %b)
   %mul = fmul double %2, %1
   ret double %mul
 }
 
 define double @pow_ab_pow_cb_reassoc(double %a, double %b, double %c) {
 ; CHECK-LABEL: @pow_ab_pow_cb_reassoc(
-; CHECK-NEXT:    [[TMP1:%.*]] = call double @llvm.pow.f64(double [[A:%.*]], double [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = call double @llvm.pow.f64(double [[C:%.*]], double [[B]])
-; CHECK-NEXT:    [[MUL:%.*]] = fmul reassoc double [[TMP2]], [[TMP1]]
-; CHECK-NEXT:    ret double [[MUL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fmul reassoc double [[C:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call reassoc double @llvm.pow.f64(double [[TMP1]], double [[B:%.*]])
+; CHECK-NEXT:    ret double [[TMP2]]
 ;
   %1 = call double @llvm.pow.f64(double %a, double %b)
   %2 = call double @llvm.pow.f64(double %c, double %b)
   %mul = fmul reassoc double %2, %1
   ret double %mul
 }
 
 define double @pow_ab_pow_ac(double %a, double %b, double %c) {
 ; CHECK-LABEL: @pow_ab_pow_ac(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call double @llvm.pow.f64(double [[A:%.*]], double [[B:%.*]])
 ; CHECK-NEXT:    [[TMP2:%.*]] = call double @llvm.pow.f64(double [[A]], double [[C:%.*]])
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul double [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret double [[MUL]]
 ;
   %1 = call double @llvm.pow.f64(double %a, double %b)
   %2 = call double @llvm.pow.f64(double %a, double %c)
   %mul = fmul double %2, %1
   ret double %mul
 }
 
 define double @pow_ab_x_pow_ac_reassoc(double %a, double %b, double %c) {
 ; CHECK-LABEL: @pow_ab_x_pow_ac_reassoc(
-; CHECK-NEXT:    [[TMP1:%.*]] = call double @llvm.pow.f64(double [[A:%.*]], double [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = call double @llvm.pow.f64(double [[A]], double [[C:%.*]])
-; CHECK-NEXT:    [[MUL:%.*]] = fmul reassoc double [[TMP2]], [[TMP1]]
-; CHECK-NEXT:    ret double [[MUL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd reassoc double [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call reassoc double @llvm.pow.f64(double [[A:%.*]], double [[TMP1]])
+; CHECK-NEXT:    ret double [[TMP2]]
 ;
   %1 = call double @llvm.pow.f64(double %a, double %b)
   %2 = call double @llvm.pow.f64(double %a, double %c)
   %mul = fmul reassoc double %2, %1
   ret double %mul
 }