[InstCombine] Simplify addends reordering logic

[kovdan01]

Summary

Previously some constants were not pushed to the top of the resulting
expression tree as intended by the algorithm. We can remove the logic from
simplifyFAdd and rely on SimplifyAssociativeOrCommutative to do that.

[spatel]

I can't tell if this has a greater effect than shown by the test diff. That diff actually demonstrates a basic missing canonicalization in IR - no fast-math is needed to convert fsub to fadd in that example or any of these more general cases:

define float @fmul_c1(float %x, float %y) {
  %m = fmul float %x, 7.000000e+00
  %r = fsub float %y, %m
  ret float %r
}

define float @fdiv_c0(float %x, float %y) {
  %m = fdiv float 7.000000e+00, %x
  %r = fsub float %y, %m
  ret float %r
}

define float @fdiv_c1(float %x, float %y) {
  %m = fdiv float %x, 7.000000e+00
  %r = fsub float %y, %m
  ret float %r
}

We do have this transform in the backend though (pushing the implicit negation op into the constant operand). For example, if you codegen this with llc for x86, you'll see 3 "addss" instructions and no "subss". Would adding those canonicalizations to IR solve your motivating case(s)?
Or is there a larger example of a change resulting from this patch?

[kovdan01]

In D117302#3246034, @spatel wrote:

I can't tell if this has a greater effect than shown by the test diff. That diff actually demonstrates a basic missing canonicalization in IR - no fast-math is needed to convert fsub to fadd in that example or any of these more general cases:

define float @fmul_c1(float %x, float %y) {
  %m = fmul float %x, 7.000000e+00
  %r = fsub float %y, %m
  ret float %r
}

define float @fdiv_c0(float %x, float %y) {
  %m = fdiv float 7.000000e+00, %x
  %r = fsub float %y, %m
  ret float %r
}

define float @fdiv_c1(float %x, float %y) {
  %m = fdiv float %x, 7.000000e+00
  %r = fsub float %y, %m
  ret float %r
}

We do have this transform in the backend though (pushing the implicit negation op into the constant operand). For example, if you codegen this with llc for x86, you'll see 3 "addss" instructions and no "subss". Would adding those canonicalizations to IR solve your motivating case(s)?
Or is there a larger example of a change resulting from this patch?

Thanks for your comment! I don’t have a larger example that results from this patch and adding the canonicalization that you mentioned will solve my motivation case. I can implement that and submit as a separate patch if that’s applicable for you. Could you please tell me the right place to add the canonicalization to?

Getting back to the current patch – I believe that it is also worth to be merged – at least, in terms of refactoring (having code that is intended to do the same thing in two places looks weird IMHO).

[spatel]

In D117302#3248112, @kovdan01 wrote:

In D117302#3246034, @spatel wrote:

I can't tell if this has a greater effect than shown by the test diff. That diff actually demonstrates a basic missing canonicalization in IR - no fast-math is needed to convert fsub to fadd in that example or any of these more general cases:

define float @fmul_c1(float %x, float %y) {
  %m = fmul float %x, 7.000000e+00
  %r = fsub float %y, %m
  ret float %r
}

define float @fdiv_c0(float %x, float %y) {
  %m = fdiv float 7.000000e+00, %x
  %r = fsub float %y, %m
  ret float %r
}

define float @fdiv_c1(float %x, float %y) {
  %m = fdiv float %x, 7.000000e+00
  %r = fsub float %y, %m
  ret float %r
}

We do have this transform in the backend though (pushing the implicit negation op into the constant operand). For example, if you codegen this with llc for x86, you'll see 3 "addss" instructions and no "subss". Would adding those canonicalizations to IR solve your motivating case(s)?
Or is there a larger example of a change resulting from this patch?

Thanks for your comment! I don’t have a larger example that results from this patch and adding the canonicalization that you mentioned will solve my motivation case. I can implement that and submit as a separate patch if that’s applicable for you. Could you please tell me the right place to add the canonicalization to?

I think it would start from InstCombinerImpl::visitFSub() and be very similar to the specialization that already exists as foldFNegIntoConstant. I already drafted a patch for it while looking at this, so I can clean that up and post it (the harder part is adding a pile of tests to check FMF propagation!).

Getting back to the current patch – I believe that it is also worth to be merged – at least, in terms of refactoring (having code that is intended to do the same thing in two places looks weird IMHO).

I agree. I'm still not sure exactly what happens within FAddCombine, but this patch just removes code, so LGTM.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

540

typo: supper -> super

[spatel]

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

2

I missed that this test is under Reassociate. It's generally wrong for a regression test to run 3 different passes, but it can be a separate cleanup patch.

[kovdan01]

In D117302#3248293, @spatel wrote:

I already drafted a patch for it while looking at this, so I can clean that up and post it (the harder part is adding a pile of tests to check FMF propagation!).

OK, please let me know if you need any help with that. If I understood you correctly, you plan to submit the patch by yourself. If so, could you please mention me in revision to keep me informed? Thanks!

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

540

Fixed

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

2

Got it, will submit a separate patch to fix this

[spatel]

In D117302#3248938, @kovdan01 wrote:

In D117302#3248293, @spatel wrote:

I already drafted a patch for it while looking at this, so I can clean that up and post it (the harder part is adding a pile of tests to check FMF propagation!).

OK, please let me know if you need any help with that. If I understood you correctly, you plan to submit the patch by yourself. If so, could you please mention me in revision to keep me informed? Thanks!

Looking over the regression tests, I noticed that we would miss a factoring optimization if we canonicalize fsub->fadd more often. This would potentially be inverting a fold done by the reassociation pass:

/// Recursively analyze an expression to build a list of instructions that have
/// negative floating-point constant operands. The caller can then transform
/// the list to create positive constants for better reassociation and CSE.

...so I'm not sure if it is worth doing that transform generally.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

 Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) {
   unsigned AddendNum = Addends.size();
   assert(AddendNum <= 4 && "Too many addends");
 
   // For saving intermediate results;
   unsigned NextTmpIdx = 0;
   FAddend TmpResult[3];
 
-  // Points to the constant addend of the resulting simplified expression.
-  // If the resulting expr has constant-addend, this constant-addend is
-  // desirable to reside at the top of the resulting expression tree. Placing
-  // constant close to supper-expr(s) will potentially reveal some optimization
-  // opportunities in super-expr(s).
-  const FAddend *ConstAdd = nullptr;
-
   // Simplified addends are placed <SimpVect>.
   AddendVect SimpVect;
 
   // The outer loop works on one symbolic-value at a time. Suppose the input
   // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ...
   // The symbolic-values will be processed in this order: x, y, z.
   for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) {
 
     const FAddend *ThisAddend = Addends[SymIdx];
     if (!ThisAddend) {
       // This addend was processed before.
       continue;
     }
 
     Value *Val = ThisAddend->getSymVal();
+
+    // If the resulting expr has constant-addend, this constant-addend is
+    // desirable to reside at the top of the resulting expression tree. Placing
+    // constant close to supper-expr(s) will potentially reveal some optimization
+    // opportunities in super-expr(s). Here we do not implement this logic
+    // intentionally and rely on SimplifyAssociativeOrCommutative call later.
+
     unsigned StartIdx = SimpVect.size();
     SimpVect.push_back(ThisAddend);
 
     // The inner loop collects addends sharing same symbolic-value, and these
     // addends will be later on folded into a single addend. Following above
     // example, if the symbolic value "y" is being processed, the inner loop
     // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will
     // be later on folded into "<b1+b2, y>".
for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) {
     if (StartIdx + 1 != SimpVect.size()) {
       FAddend &R = TmpResult[NextTmpIdx ++];
       R = *SimpVect[StartIdx];
       for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++)
         R += *SimpVect[Idx];
 
       // Pop all addends being folded and push the resulting folded addend.
       SimpVect.resize(StartIdx);
-      if (Val) {
-        if (!R.isZero()) {
-          SimpVect.push_back(&R);
-        }
-      } else {
-        // Don't push constant addend at this time. It will be the last element
-        // of <SimpVect>.
-        ConstAdd = &R;
-      }
     }
   }
 
   assert((NextTmpIdx <= array_lengthof(TmpResult) + 1) &&
          "out-of-bound access");
 
-  if (ConstAdd)
-    SimpVect.push_back(ConstAdd);
-
   Value *Result;
   if (!SimpVect.empty())
     Result = createNaryFAdd(SimpVect, InstrQuota);
   else {
     // The addition is folded to 0.0.
     Result = ConstantFP::get(Instr->getType(), 0.0);
   }
 

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -gvn -instcombine -S | FileCheck %s
 
 ; With reassociation, constant folding can eliminate the 12 and -12 constants.
 define float @test1(float %arg) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[ARG_NEG:%.*]] = fneg fast float [[ARG:%.*]]
 ; CHECK-NEXT:    ret float [[ARG_NEG]]
 ;
   %t1 = fsub fast float -1.200000e+01, %arg
;
   %Y = fadd fast float %A ,%B
   %Z = fadd fast float %Y, %C
   ret float %Z
 }
 
 ; Check again with 'reassoc' and 'nsz' ('nsz' not technically required).
 define float @test12_reassoc_nsz(float %X) {
 ; CHECK-LABEL: @test12_reassoc_nsz(
-; CHECK-NEXT:    [[TMP1:%.*]] = fmul reassoc nsz float [[X:%.*]], 3.000000e+00
-; CHECK-NEXT:    [[TMP2:%.*]] = fsub reassoc nsz float 6.000000e+00, [[TMP1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fmul reassoc nsz float [[X:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[TMP2:%.*]] = fadd reassoc nsz float [[TMP1]], 6.000000e+00
 ; CHECK-NEXT:    ret float [[TMP2]]
 ;
   %A = fsub reassoc nsz float 1.000000e+00, %X
   %B = fsub reassoc nsz float 2.000000e+00, %X
   %C = fsub reassoc nsz float 3.000000e+00, %X
   %Y = fadd reassoc nsz float %A ,%B
   %Z = fadd reassoc nsz float %Y, %C
   ret float %Z