[InstCombine] reassociate FP diff of sums into sum of diffs

[spatel]

Summary

(a[0] + a[1] + a[2] + a[3]) - (b[0] + b[1] + b[2] +b[3]) -->
(a[0] - b[0]) + (a[1] - b[1]) + (a[2] - b[2]) + (a[3] - b[3])

This should be the last step in solving PR43953:
https://bugs.llvm.org/show_bug.cgi?id=43953

We started emitting reduction intrinsics with D80867/ rGe50059f6b6b3, so it's a relatively easy pattern match now to re-order those ops.
Also, I have not seen any complaints for the switch to intrinsics yet, so I'll propose to remove the "experimental" tag from the intrinsics soon.

[spatel]

Patch updated:
Corrected the final op - we subtract the 2nd reduction's accumulator variable.

[RKSimon]

LGTM as long as the fast math flags are OK.

I'm not sure if the integer add equivalent combine would be useful (yet)? It probably wouldn't help with PSAD cases tbh.

[spatel]

In D81491#2087527, @RKSimon wrote:

LGTM as long as the fast math flags are OK.

That’s the usual logic - if the final value is relaxed, then we assume that calcs leading to that value are equivalently relaxed. Note that to get mixed optimization flags, you likely need compilation with different optimization flags + LTO + inlining to ever get to the state where instructions in 1 function have different FMF.

I'm not sure if the integer add equivalent combine would be useful (yet)? It probably wouldn't help with PSAD cases tbh.

From an IR perspective, we should have that for consistency, but I have not looked at what happens with codegen on that path yet. I'll take a look at that next.

[nikic]

Also, I have not seen any complaints for the switch to intrinsics yet, so I'll propose to remove the "experimental" tag from the intrinsics soon.

In case you missed it, this was recently discussed at https://groups.google.com/d/msg/llvm-dev/ku7Vs38DJmo/i7SiGMuaAQAJ.

[spatel]

In D81491#2091805, @nikic wrote:

Also, I have not seen any complaints for the switch to intrinsics yet, so I'll propose to remove the "experimental" tag from the intrinsics soon.

In case you missed it, this was recently discussed at https://groups.google.com/d/msg/llvm-dev/ku7Vs38DJmo/i7SiGMuaAQAJ.

Thanks for the reminder! I'll post an update on that thread.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
     Value *Z;
     if (match(Op0, m_OneUse(m_c_FAdd(m_OneUse(m_FSub(m_Value(X), m_Value(Y))),
                                      m_Value(Z))))) {
       Value *XZ = Builder.CreateFAddFMF(X, Z, &I);
       Value *YW = Builder.CreateFAddFMF(Y, Op1, &I);
       return BinaryOperator::CreateFSubFMF(XZ, YW, &I);
     }
 
+    auto m_FaddRdx = [](Value *&Sum, Value *&Vec) {
+      return m_OneUse(
+          m_Intrinsic<Intrinsic::experimental_vector_reduce_v2_fadd>(
+              m_Value(Sum), m_Value(Vec)));
+    };
+    Value *A0, *A1, *V0, *V1;
+    if (match(Op0, m_FaddRdx(A0, V0)) && match(Op1, m_FaddRdx(A1, V1)) &&
+        V0->getType() == V1->getType()) {
+      // Difference of sums is sum of differences:
+      // add_rdx(A0, V0) - add_rdx(A1, V1) --> add_rdx(A0, V0 - V1) + A1
+      Value *Sub = Builder.CreateFSubFMF(V0, V1, &I);
+      Value *Rdx = Builder.CreateIntrinsic(
+          Intrinsic::experimental_vector_reduce_v2_fadd,
+          {A0->getType(), Sub->getType()}, {A0, Sub}, &I);
+      return BinaryOperator::CreateFAddFMF(Rdx, A1, &I);
+    }
+
     if (Instruction *F = factorizeFAddFSub(I, Builder))
       return F;
 
     // TODO: This performs reassociative folds for FP ops. Some fraction of the
     // functionality has been subsumed by simple pattern matching here and in
     // InstSimplify. We should let a dedicated reassociation pass handle more
     // complex pattern matching and remove this from InstCombine.
     if (Value *V = FAddCombine(Builder).simplify(&I))

llvm/test/Transforms/InstCombine/vector-reductions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 declare float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float, <4 x float>)
 declare float @llvm.experimental.vector.reduce.v2.fadd.f32.v8f32(float, <8 x float>)
 declare void @use_f32(float)
 
 define float @diff_of_sums_v4f32(float %a0, <4 x float> %v0, float %a1, <4 x float> %v1) {
 ; CHECK-LABEL: @diff_of_sums_v4f32(
-; CHECK-NEXT:    [[R0:%.*]] = call float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A0:%.*]], <4 x float> [[V0:%.*]])
-; CHECK-NEXT:    [[R1:%.*]] = call float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A1:%.*]], <4 x float> [[V1:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = fsub reassoc nsz float [[R0]], [[R1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fsub reassoc nsz <4 x float> [[V0:%.*]], [[V1:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call reassoc nsz float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A0:%.*]], <4 x float> [[TMP1]])
+; CHECK-NEXT:    [[R:%.*]] = fadd reassoc nsz float [[TMP2]], [[A1:%.*]]
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %r0 = call float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float %a0, <4 x float> %v0)
   %r1 = call float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float %a1, <4 x float> %v1)
   %r = fsub reassoc nsz float %r0, %r1
   ret float %r
 }
 
+; negative test - fsub must allow reassociation
+
 define float @diff_of_sums_v4f32_fmf(float %a0, <4 x float> %v0, float %a1, <4 x float> %v1) {
 ; CHECK-LABEL: @diff_of_sums_v4f32_fmf(
 ; CHECK-NEXT:    [[R0:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A0:%.*]], <4 x float> [[V0:%.*]])
 ; CHECK-NEXT:    [[R1:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A1:%.*]], <4 x float> [[V1:%.*]])
 ; CHECK-NEXT:    [[R:%.*]] = fsub nnan ninf nsz float [[R0]], [[R1]]
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %r0 = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float %a0, <4 x float> %v0)
   %r1 = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float %a1, <4 x float> %v1)
   %r = fsub ninf nnan nsz float %r0, %r1
   ret float %r
 }
 
+; negative test - extra uses could create extra instructions
+
 define float @diff_of_sums_extra_use1(float %a0, <4 x float> %v0, float %a1, <4 x float> %v1) {
 ; CHECK-LABEL: @diff_of_sums_extra_use1(
 ; CHECK-NEXT:    [[R0:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A0:%.*]], <4 x float> [[V0:%.*]])
 ; CHECK-NEXT:    call void @use_f32(float [[R0]])
 ; CHECK-NEXT:    [[R1:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A1:%.*]], <4 x float> [[V1:%.*]])
 ; CHECK-NEXT:    [[R:%.*]] = fsub fast float [[R0]], [[R1]]
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %r0 = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float %a0, <4 x float> %v0)
   call void @use_f32(float %r0)
   %r1 = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float %a1, <4 x float> %v1)
   %r = fsub fast float %r0, %r1
   ret float %r
 }
 
+; negative test - extra uses could create extra instructions
+
 define float @diff_of_sums_extra_use2(float %a0, <4 x float> %v0, float %a1, <4 x float> %v1) {
 ; CHECK-LABEL: @diff_of_sums_extra_use2(
 ; CHECK-NEXT:    [[R0:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A0:%.*]], <4 x float> [[V0:%.*]])
 ; CHECK-NEXT:    [[R1:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A1:%.*]], <4 x float> [[V1:%.*]])
 ; CHECK-NEXT:    call void @use_f32(float [[R1]])
 ; CHECK-NEXT:    [[R:%.*]] = fsub fast float [[R0]], [[R1]]
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %r0 = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float %a0, <4 x float> %v0)
   %r1 = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float %a1, <4 x float> %v1)
   call void @use_f32(float %r1)
   %r = fsub fast float %r0, %r1
   ret float %r
 }
 
+; negative test - can't reassociate different vector types
+
 define float @diff_of_sums_type_mismatch(float %a0, <4 x float> %v0, float %a1, <8 x float> %v1) {
 ; CHECK-LABEL: @diff_of_sums_type_mismatch(
 ; CHECK-NEXT:    [[R0:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float [[A0:%.*]], <4 x float> [[V0:%.*]])
 ; CHECK-NEXT:    [[R1:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v8f32(float [[A1:%.*]], <8 x float> [[V1:%.*]])
 ; CHECK-NEXT:    [[R:%.*]] = fsub fast float [[R0]], [[R1]]
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %r0 = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float %a0, <4 x float> %v0)
   %r1 = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v8f32(float %a1, <8 x float> %v1)
   %r = fsub fast float %r0, %r1
   ret float %r
 }

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions.ll

 
 define i32 @TestVectorsEqualFP_alt(float* noalias %Vec0, float* noalias %Vec1, float %Tolerance) {
 ; CHECK-LABEL: @TestVectorsEqualFP_alt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast float* [[VEC0:%.*]] to <4 x float>*
 ; CHECK-NEXT:    [[TMP1:%.*]] = load <4 x float>, <4 x float>* [[TMP0]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = bitcast float* [[VEC1:%.*]] to <4 x float>*
 ; CHECK-NEXT:    [[TMP3:%.*]] = load <4 x float>, <4 x float>* [[TMP2]], align 4
-; CHECK-NEXT:    [[TMP4:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float 0.000000e+00, <4 x float> [[TMP1]])
-; CHECK-NEXT:    [[TMP5:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float 0.000000e+00, <4 x float> [[TMP3]])
-; CHECK-NEXT:    [[ADD_3:%.*]] = fsub fast float [[TMP4]], [[TMP5]]
-; CHECK-NEXT:    [[CMP3:%.*]] = fcmp fast ole float [[ADD_3]], [[TOLERANCE:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = fsub fast <4 x float> [[TMP1]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = call fast float @llvm.experimental.vector.reduce.v2.fadd.f32.v4f32(float 0.000000e+00, <4 x float> [[TMP4]])
+; CHECK-NEXT:    [[CMP3:%.*]] = fcmp fast ole float [[TMP5]], [[TOLERANCE:%.*]]
 ; CHECK-NEXT:    [[COND:%.*]] = zext i1 [[CMP3]] to i32
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;
 entry:
   br label %for.cond
 
 for.cond:
   %sum.0 = phi float [ 0.000000e+00, %entry ], [ %add, %for.inc ]