[InstCombine] reassociate fsub+fsub into fsub+fadd

[spatel]

Summary

As discussed in the motivating PR44509:
https://bugs.llvm.org/show_bug.cgi?id=44509

...we can end up with worse code using fast-math than without. This is because the reassociate pass greedily transforms fsub into fneg/fadd and apparently (based on the regression tests seen here) expects instcombine to clean that up if it wasn't profitable. But we were missing this fold:

(X - Y) - Z --> X - (Y + Z)

There's another, more specific case that I think we should handle as shown in the "fake" fneg test (but missed with a real fneg), but that's another patch. That may be tricky to get right without conflicting with existing transforms for fneg.

[mcberg2017]

Looked at this internally for us and looks ok. LGTM.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

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))
       return replaceInstUsesWith(I, V);
+
+    // (X - Y) - Op1 --> X - (Y + Op1)
+    if (match(Op0, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
+      Value *FAdd = Builder.CreateFAddFMF(Y, Op1, &I);
+      return BinaryOperator::CreateFSubFMF(X, FAdd, &I);
+    }
   }
 
   return nullptr;
 }

llvm/test/Transforms/InstCombine/fsub.ll

;
   %neg = fsub float -0.000000e+00, %x
   call void @use(float %neg)
   %mul = fmul float %y, %neg
   call void @use(float %mul)
   %r = fsub float %z, %mul
   ret float %r
 }
 
+; Negative test - can't reassociate without FMF.
+
 define float @fsub_fsub(float %x, float %y, float %z) {
 ; CHECK-LABEL: @fsub_fsub(
 ; CHECK-NEXT:    [[XY:%.*]] = fsub float [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[XYZ:%.*]] = fsub float [[XY]], [[Z:%.*]]
 ; CHECK-NEXT:    ret float [[XYZ]]
 ;
   %xy = fsub float %x, %y
   %xyz = fsub float %xy, %z
   ret float %xyz
 }
 
+; Negative test - can't reassociate without enough FMF.
+
 define float @fsub_fsub_nsz(float %x, float %y, float %z) {
 ; CHECK-LABEL: @fsub_fsub_nsz(
 ; CHECK-NEXT:    [[XY:%.*]] = fsub float [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[XYZ:%.*]] = fsub nsz float [[XY]], [[Z:%.*]]
 ; CHECK-NEXT:    ret float [[XYZ]]
 ;
   %xy = fsub float %x, %y
   %xyz = fsub nsz float %xy, %z
   ret float %xyz
 }
 
+; Negative test - can't reassociate without enough FMF.
+
 define float @fsub_fsub_reassoc(float %x, float %y, float %z) {
 ; CHECK-LABEL: @fsub_fsub_reassoc(
 ; CHECK-NEXT:    [[XY:%.*]] = fsub float [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[XYZ:%.*]] = fsub reassoc float [[XY]], [[Z:%.*]]
 ; CHECK-NEXT:    ret float [[XYZ]]
 ;
   %xy = fsub float %x, %y
   %xyz = fsub reassoc float %xy, %z
   ret float %xyz
 }
 
 define float @fsub_fsub_nsz_reassoc(float %x, float %y, float %z) {
 ; CHECK-LABEL: @fsub_fsub_nsz_reassoc(
-; CHECK-NEXT:    [[XY:%.*]] = fsub float [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = fsub reassoc nsz float [[XY]], [[Z:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd reassoc nsz float [[Y:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    [[XYZ:%.*]] = fsub reassoc nsz float [[X:%.*]], [[TMP1]]
 ; CHECK-NEXT:    ret float [[XYZ]]
 ;
   %xy = fsub float %x, %y
   %xyz = fsub nsz reassoc float %xy, %z
   ret float %xyz
 }
 
 define <2 x double> @fsub_fsub_fast_vec(<2 x double> %x, <2 x double> %y, <2 x double> %z) {
 ; CHECK-LABEL: @fsub_fsub_fast_vec(
-; CHECK-NEXT:    [[XY:%.*]] = fsub fast <2 x double> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = fsub fast <2 x double> [[XY]], [[Z:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd fast <2 x double> [[Y:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    [[XYZ:%.*]] = fsub fast <2 x double> [[X:%.*]], [[TMP1]]
 ; CHECK-NEXT:    ret <2 x double> [[XYZ]]
 ;
   %xy = fsub fast <2 x double> %x, %y
   %xyz = fsub fast reassoc <2 x double> %xy, %z
   ret <2 x double> %xyz
 }
 
+; Negative test - don't reassociate and increase instructions.
+
 define float @fsub_fsub_nsz_reassoc_extra_use(float %x, float %y, float %z) {
 ; CHECK-LABEL: @fsub_fsub_nsz_reassoc_extra_use(
 ; CHECK-NEXT:    [[XY:%.*]] = fsub float [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(float [[XY]])
 ; CHECK-NEXT:    [[XYZ:%.*]] = fsub reassoc nsz float [[XY]], [[Z:%.*]]
 ; CHECK-NEXT:    ret float [[XYZ]]
 ;
   %xy = fsub float %x, %y

 ;
   %negx = fneg float %x
   %sub = fsub nsz float %negx, %y
   ret float %sub
 }
 
 define float @fake_fneg_fsub_fast(float %x, float %y) {
 ; CHECK-LABEL: @fake_fneg_fsub_fast(
-; CHECK-NEXT:    [[NEGX:%.*]] = fsub float -0.000000e+00, [[X:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = fsub fast float [[NEGX]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd fast float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = fsub fast float -0.000000e+00, [[TMP1]]
 ; CHECK-NEXT:    ret float [[SUB]]
 ;
   %negx = fsub float -0.0, %x
   %sub = fsub fast float %negx, %y
   ret float %sub
 }
 
 define float @fake_fneg_fsub_fast_extra_use(float %x, float %y) {

llvm/test/Transforms/Reassociate/fast-SubReassociate.ll

;
   %P = fsub float %D, %O
   %Q = fadd float %P, 1.200000e+01
   ret float %Q
 }
 
 ; With sub reassociation, constant folding can eliminate the two 12 constants.
 
 define float @test4(float %A, float %B, float %C, float %D) {
-; FIXME: InstCombine should be able to get us to the following:
-; %sum = fadd fast float %B, %A
-; %sum1 = fadd fast float %sum, %C
-; %Q = fsub fast float %D, %sum1
-; ret i32 %Q
 ; CHECK-LABEL: @test4(
-; CHECK-NEXT:    [[B_NEG:%.*]] = fsub fast float -0.000000e+00, [[B:%.*]]
-; CHECK-NEXT:    [[O_NEG:%.*]] = fsub fast float [[B_NEG]], [[A:%.*]]
-; CHECK-NEXT:    [[P:%.*]] = fsub fast float [[O_NEG]], [[C:%.*]]
-; CHECK-NEXT:    [[Q:%.*]] = fadd fast float [[P]], [[D:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd fast float [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = fadd fast float [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    [[Q:%.*]] = fsub fast float [[D:%.*]], [[TMP2]]
 ; CHECK-NEXT:    ret float [[Q]]
 ;
   %M = fadd fast float 1.200000e+01, %A
   %N = fadd fast float %M, %B
   %O = fadd fast float %N, %C
   %P = fsub fast float %D, %O
   %Q = fadd fast float 1.200000e+01, %P
   ret float %Q

llvm/test/Transforms/Reassociate/fast-basictest.ll

;
   %X = fadd reassoc float -1.200000e+01, %A
   %Y = fsub reassoc float %X, %B
   %Z = fadd reassoc float %Y, 1.200000e+01
   ret float %Z
 }
 
 ; With sub reassociation, constant folding can eliminate the uses of %a.
 define float @test20(float %a, float %b, float %c) nounwind  {
-; FIXME: Should be able to generate the below, which may expose more
-;        opportunites for FAdd reassociation.
-; %sum = fadd fast float %c, %b
-; %t7 = fsub fast float 0, %sum
 ; CHECK-LABEL: @test20(
-; CHECK-NEXT:    [[B_NEG:%.*]] = fsub fast float -0.000000e+00, [[B:%.*]]
-; CHECK-NEXT:    [[T7:%.*]] = fsub fast float [[B_NEG]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd fast float [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[T7:%.*]] = fsub fast float -0.000000e+00, [[TMP1]]
 ; CHECK-NEXT:    ret float [[T7]]
 ;
   %t3 = fsub fast float %a, %b
   %t5 = fsub fast float %t3, %c
   %t7 = fsub fast float %t5, %a
   ret float %t7
 }