[InstCombine] Missed optimization for pow(x, y) * pow(x, z) with fast-math

[vdsered]

Summary

If fast-math is set, then LLVM is free to do the following transformation pow(x, y) * pow(x, z) -> pow(x, y + z). This patch adds this transformation and tests for it. See more https://bugs.llvm.org/show_bug.cgi?id=47205

It handles two cases

1. When operands of fmul are different instructions

%4 = call reassoc float @llvm.pow.f32(float %0, float %1)
%5 = call reassoc float @llvm.pow.f32(float %0, float %2)
%6 = fmul reassoc float %5, %4
-->
%3 = fadd reassoc float %1, %2
%4 = call reassoc float @llvm.pow.f32(float %0, float %3)

2. When operands of fmul are the same instruction

%4 = call reassoc float @llvm.pow.f32(float %0, float %1)
%5 = fmul reassoc float %4, %4
-->
%3 = fadd reassoc float %1, %1
%4 = call reassoc float @llvm.pow.f32(float %0, float %3)

[vdsered]

Calling CreateBinaryIntrinsic instead of CreateIntrinsic for better readability

[vdsered]

I have noticed that there are two similiar transformations below exp2(X) * exp2(Y) -> exp2(X + Y) and exp(X) * exp(Y) -> exp(X + Y) that are done when each operand of multiplication has exactly one use which is n't true if, for example, there is exp2(X) * exp2(X) where exp2(X) is the same instruction, so it can be improved a little. I'm going to update the patch

[spatel]

In D102574#2763294, @vdsered wrote:

I have noticed that there are two similiar transformations below exp2(X) * exp2(Y) -> exp2(X + Y) and exp(X) * exp(Y) -> exp(X + Y) that are done when each operand of multiplication has exactly one use which is n't true if, for example, there is exp2(X) * exp2(X) where exp2(X) is the same instruction, so it can be improved a little. I'm going to update the patch

I recommend that you make that use-check logic into a helper function as a preliminary step, so it can be be accessed from other places. For example, we miss this transform too because the use check is too restrictive:
https://alive2.llvm.org/ce/z/27ryac

[vdsered]

In D102574#2763320, @spatel wrote:

In D102574#2763294, @vdsered wrote:

I have noticed that there are two similiar transformations below exp2(X) * exp2(Y) -> exp2(X + Y) and exp(X) * exp(Y) -> exp(X + Y) that are done when each operand of multiplication has exactly one use which is n't true if, for example, there is exp2(X) * exp2(X) where exp2(X) is the same instruction, so it can be improved a little. I'm going to update the patch

I recommend that you make that use-check logic into a helper function as a preliminary step, so it can be be accessed from other places. For example, we miss this transform too because the use check is too restrictive:
https://alive2.llvm.org/ce/z/27ryac

Are you talking about all checks that we do here? (see below)

Op0->hasOneUse() || Op1->hasOneUse() || (Op1 == Op0 && Op1->hasNUses(2))

Because I think this condition is going to be the same for many patterns and I will create another patch to implement the helper function and refactor conditions at least for those transformations (below) before updating this one

1. exp(X) * exp(Y) -> exp(X + Y)
2. exp2(X) * exp2(Y) -> exp2(X + Y)
3. sqrt(X) * sqrt(Y) -> sqrt(X * Y)

There are more cases when this sort of check is useful like in InstCombinerImpl::SimplifyAssociativeOrCommutative

// Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)"
// if C1 and C2 are constants.
Value *A, *B;
Constant *C1, *C2;
if (Op0 && Op1 &&
    Op0->getOpcode() == Opcode && Op1->getOpcode() == Opcode &&
    match(Op0, m_OneUse(m_BinOp(m_Value(A), m_Constant(C1)))) &&
    match(Op1, m_OneUse(m_BinOp(m_Value(B), m_Constant(C2))))) {

The only difference is how op0 and op1 are compared (via opcode), but the use-check can be relaxed too as I understand

[spatel]

In D102574#2764241, @vdsered wrote:

In D102574#2763320, @spatel wrote:

In D102574#2763294, @vdsered wrote:

I have noticed that there are two similiar transformations below exp2(X) * exp2(Y) -> exp2(X + Y) and exp(X) * exp(Y) -> exp(X + Y) that are done when each operand of multiplication has exactly one use which is n't true if, for example, there is exp2(X) * exp2(X) where exp2(X) is the same instruction, so it can be improved a little. I'm going to update the patch

I recommend that you make that use-check logic into a helper function as a preliminary step, so it can be be accessed from other places. For example, we miss this transform too because the use check is too restrictive:
https://alive2.llvm.org/ce/z/27ryac

Are you talking about all checks that we do here? (see below)

Op0->hasOneUse() || Op1->hasOneUse() || (Op1 == Op0 && Op1->hasNUses(2))

Yes - let's give that line a name (not sure what's best - "hasRemovableUser" ?), so we don't have to repeat it.

Because I think this condition is going to be the same for many patterns and I will create another patch to implement the helper function and refactor conditions at least for those transformations (below) before updating this one

1. exp(X) * exp(Y) -> exp(X + Y)
2. exp2(X) * exp2(Y) -> exp2(X + Y)
3. sqrt(X) * sqrt(Y) -> sqrt(X * Y)

Yes - please make a different patch. It's probably only mul/fmul that have a need for this. Most other binops should simplify if both operands are the same.
For example, the sqrt pattern should get folded by instsimplify, so I don't think that needs any changes.

[vdsered]

I created a new patch https://reviews.llvm.org/D102698. I will update the current patch when we close the new one.

[vdsered]

1. Replaced hasOneUse + equality of operands with isOnlyUserOfAnyOperand
2. FMF are added to produced fadd
3. Added negative tests

[vdsered]

@spatel you mentioned one more optimization with sext that we miss because of too strict use-constraint here. I'll create another patch for that. I think, it's going to be the last one. I don't know any other transformations for mul/fmul that would benefit from the new method.

[spatel]

In D102574#2791437, @vdsered wrote:

@spatel you mentioned one more optimization with sext that we miss because of too strict use-constraint here. I'll create another patch for that. I think, it's going to be the last one. I don't know any other transformations for mul/fmul that would benefit from the new method.

Yes, that was:
https://alive2.llvm.org/ce/z/27ryac
...and it would be another patch

I pushed the baseline tests for this patch with:
f03f4944cf

Please update/rebase here in Phab, so we'll see just the diffs from this patch.

[xbolva00]

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

101

Restore

[vdsered]

@spatel Done

[spatel]

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

89–100

Do you know why you are getting this (and similar) test changes? They are cosmetic (value names differ), but I don't see this when testing locally.

[vdsered]

Removed name diff in tests

[vdsered]

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

89–100

I have seen recently how update_test_checks warned about using tmps in tests so I thought of renaming. It doesn't say anything for these tests however... Updated the patch to remove the naming diff and see the actual changes in output for tests

[spatel]

LGTM

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

89–100

Ah - yes, the script will warn if it sees IR like:

%tmp1 = fmul float %x, %y

...because the script is creating FileCheck variables for unnamed values in IR (%1) with names like TMP1 (as we see in the examples in this patch). I don't see any potential conflicts with these tests.

[vdsered]

This comment was removed by vdsered.

[vdsered]

Sorry, I didn't see you have already committed :)

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Instruction *InstCombinerImpl::visitFMul(BinaryOperator &I) {
   if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C)))
     return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &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()) {
+    // pow(x, y) * pow(x, z) -> pow(x, y + z)
+    // If operands of fmul are equal and they have exactly two uses, then
+    // they have one user. It is useful for a case like the one below
+    //
+    // %2 = pow %0, %1
+    // %3 = fmul %2, %2
+    // -->
+    // %2 = fadd %1, %1
+    // %3 = pow %0, %2
+    if (Op0->hasOneUse() || Op1->hasOneUse() ||
+        (Op1 == Op0 && Op1->hasNUses(2))) {
+      Value *X, *Y, *Z;
+      if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Value(X), m_Value(Y))))
+        if (match(Op1,
+                  m_Intrinsic<Intrinsic::pow>(m_Specific(X), m_Value(Z)))) {
+          auto *Expo = Builder.CreateFAdd(Y, Z);
+          auto *NewPow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, X, Expo);
+          return replaceInstUsesWith(I, NewPow);
+        }
+    }
+
     // 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())

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

;
   %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 double [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call 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
 }
+
+define double @pow_ab_reassoc(double %a, double %b) {
+; CHECK-LABEL: @pow_ab_reassoc(
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd double [[B:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call 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, %1
+  ret double %mul
+}