Reassociate x + -0.1234 * y into x - 0.1234 * y

[erikjv]

Summary

This does not require -ffast-math, and it gives CSE/GVN more options to
eliminate duplicate expressions in, e.g.:

return ((x + 0.1234 * y) * (x - 0.1234 * y));

[mcrosier]

This may need to be rebased after r215647.

[erikjv]

Rebased on top of r215647.

[mcrosier]

Hi Erik,
My suggestions were easier to see in a patch, so see attached. I cleaned
it up a bit then ran it through clang-format. NFCI. If you'd like to
add/edit anything, please do.

Upload the revised patch and I'll review and approve.

Regards,

Chad

Rebased on top of r215647.

http://reviews.llvm.org/D4904

Files:

lib/Target/README.txt
lib/Transforms/Scalar/Reassociate.cpp
test/Transforms/Reassociate/liftsign.ll

• erikjv.patch7 KBDownload

[erikjv]

Hi Chad,

I merged in your patch. I also got rid of the "only do it for
non-fast-math". It was bogus, and only there to hide the fact that I
didn't set/copy any math flags to the newly created binop.

[mcrosier]

LGTM. Let me know if you need me to push the commit.

Chad

lib/Transforms/Scalar/Reassociate.cpp

1986 ↗

(On Diff #12543)

We can be more generic here:
FAdd(x, FMul(-ConstantFP, y)) -> FSub(x, FMul(ConstantFP, y))

I actually prefer

// Reassociate: x + -ConstantFP * y -> x - ConstantFP * y

but I'll let you decide.

[erikjv]

Closed by commit rL216169 (authored by @erikjv).

llvm/trunk/lib/Target/README.txt

 } 
 
 This requires reassociating to forms of expressions that are already available,
 something that reassoc doesn't think about yet.
 
 
 //===---------------------------------------------------------------------===//
 
-This function: (derived from GCC PR19988)
-double foo(double x, double y) {
-  return ((x + 0.1234 * y) * (x + -0.1234 * y));
-}
-
-compiles to:
-_foo:
-  movapd  %xmm1, %xmm2
-  mulsd LCPI1_1(%rip), %xmm1
-  mulsd LCPI1_0(%rip), %xmm2
-  addsd %xmm0, %xmm1
-  addsd %xmm0, %xmm2
-  movapd  %xmm1, %xmm0
-  mulsd %xmm2, %xmm0
-  ret
-
-Reassociate should be able to turn it into:
-
-double foo(double x, double y) {
-  return ((x + 0.1234 * y) * (x - 0.1234 * y));
-}
-
-Which allows the multiply by constant to be CSE'd, producing:
-
-_foo:
-  mulsd LCPI1_0(%rip), %xmm1
-  movapd  %xmm1, %xmm2
-  addsd %xmm0, %xmm2
-  subsd %xmm1, %xmm0
-  mulsd %xmm2, %xmm0
-  ret
-
-This doesn't need -ffast-math support at all.  This is particularly bad because
-the llvm-gcc frontend is canonicalizing the later into the former, but clang
-doesn't have this problem.
-
-//===---------------------------------------------------------------------===//
-
 These two functions should generate the same code on big-endian systems:
 
 int g(int *j,int *l)  {  return memcmp(j,l,4);  }
 int h(int *j, int *l) {  return *j - *l; }
 
 this could be done in SelectionDAGISel.cpp, along with other special cases,
 for 1,2,4,8 bytes.
 

llvm/trunk/lib/Transforms/Scalar/Reassociate.cpp

bool CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2,
                         APInt &ConstOpnd, Value *&Res);
     bool collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops,
                                 SmallVectorImpl<Factor> &Factors);
     Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder,
                                    SmallVectorImpl<Factor> &Factors);
     Value *OptimizeMul(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
     Value *RemoveFactorFromExpression(Value *V, Value *Factor);
     void EraseInst(Instruction *I);
+    void optimizeFAddNegExpr(ConstantFP *ConstOperand, Instruction *I,
+                             int OperandNr);
     void OptimizeInst(Instruction *I);
   };
 }
 
 XorOpnd::XorOpnd(Value *V) {
   assert(!isa<ConstantInt>(V) && "No ConstantInt");
   OrigVal = V;
   Instruction *I = dyn_cast<Instruction>(V);
if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) {
       unsigned Opcode = Op->getOpcode();
       while (Op->hasOneUse() && Op->user_back()->getOpcode() == Opcode &&
              Visited.insert(Op))
         Op = Op->user_back();
       RedoInsts.insert(Op);
     }
 }
 
+void Reassociate::optimizeFAddNegExpr(ConstantFP *ConstOperand, Instruction *I,
+                                      int OperandNr) {
+  // Change the sign of the constant.
+  APFloat Val = ConstOperand->getValueAPF();
+  Val.changeSign();
+  I->setOperand(0, ConstantFP::get(ConstOperand->getContext(), Val));
+
+  assert(I->hasOneUse() && "Only a single use can be replaced.");
+  Instruction *Parent = I->user_back();
+
+  Value *OtherOperand = Parent->getOperand(1 - OperandNr);
+
+  unsigned Opcode = Parent->getOpcode();
+  assert(Opcode == Instruction::FAdd ||
+         (Opcode == Instruction::FSub && Parent->getOperand(1) == I));
+
+  BinaryOperator *NI = Opcode == Instruction::FAdd
+                           ? BinaryOperator::CreateFSub(OtherOperand, I)
+                           : BinaryOperator::CreateFAdd(OtherOperand, I);
+  NI->setFastMathFlags(cast<FPMathOperator>(Parent)->getFastMathFlags());
+  NI->insertBefore(Parent);
+  NI->setName(Parent->getName() + ".repl");
+  Parent->replaceAllUsesWith(NI);
+  NI->setDebugLoc(I->getDebugLoc());
+  MadeChange = true;
+}
+
 /// OptimizeInst - Inspect and optimize the given instruction. Note that erasing
 /// instructions is not allowed.
 void Reassociate::OptimizeInst(Instruction *I) {
   // Only consider operations that we understand.
   if (!isa<BinaryOperator>(I))
     return;
 
   if (I->getOpcode() == Instruction::Shl && isa<ConstantInt>(I->getOperand(1)))
if (I->getOpcode() == Instruction::Shl && isa<ConstantInt>(I->getOperand(1)))
     }
 
   // Commute floating point binary operators, to canonicalize the order of their
   // operands.  This can potentially expose more CSE opportunities, and makes
   // writing other transformations simpler.
   if (I->getType()->isFloatingPointTy() || I->getType()->isVectorTy()) {
 
     // FAdd and FMul can be commuted.
-    if (I->getOpcode() == Instruction::FMul ||
-        I->getOpcode() == Instruction::FAdd) {
+    unsigned Opcode = I->getOpcode();
+    if (Opcode == Instruction::FMul || Opcode == Instruction::FAdd) {
       Value *LHS = I->getOperand(0);
       Value *RHS = I->getOperand(1);
       unsigned LHSRank = getRank(LHS);
       unsigned RHSRank = getRank(RHS);
 
       // Sort the operands by rank.
       if (RHSRank < LHSRank) {
         I->setOperand(0, RHS);
         I->setOperand(1, LHS);
       }
     }
 
+    // Reassociate: x + -ConstantFP * y -> x - ConstantFP * y
+    // The FMul can also be an FDiv, and FAdd can be a FSub.
+    if (Opcode == Instruction::FMul || Opcode == Instruction::FDiv) {
+      if (ConstantFP *LHSConst = dyn_cast<ConstantFP>(I->getOperand(0))) {
+        if (LHSConst->isNegative() && I->hasOneUse()) {
+          Instruction *Parent = I->user_back();
+          if (Parent->getOpcode() == Instruction::FAdd) {
+            if (Parent->getOperand(0) == I)
+              optimizeFAddNegExpr(LHSConst, I, 0);
+            else if (Parent->getOperand(1) == I)
+              optimizeFAddNegExpr(LHSConst, I, 1);
+          } else if (Parent->getOpcode() == Instruction::FSub)
+            if (Parent->getOperand(1) == I)
+              optimizeFAddNegExpr(LHSConst, I, 1);
+        }
+      }
+    }
+
     // FIXME: We should commute vector instructions as well.  However, this 
     // requires further analysis to determine the effect on later passes.
 
     // Don't try to optimize vector instructions or anything that doesn't have
     // unsafe algebra.
     if (I->getType()->isVectorTy() || !I->hasUnsafeAlgebra())
       return;
   }

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

; CHECK-NEXT: ret float
   %C = fmul fast float %X1, %X3  ; X1*X3
   %D = fadd fast float %B, %C    ; -X1*X2 + X1*X3 -> X1*(X3-X2)
   ret float %D
 }
 
 define float @test14(float %X1, float %X2) {
 ; CHECK-LABEL: @test14
 ; CHECK-NEXT: fsub fast float %X1, %X2
-; CHECK-NEXT: fmul fast float %tmp, 4.700000e+01
+; CHECK-NEXT: fmul fast float %1, 4.700000e+01
 ; CHECK-NEXT: ret float
 
   %B = fmul fast float %X1, 47.   ; X1*47
   %C = fmul fast float %X2, -47.  ; X2*-47
   %D = fadd fast float %B, %C    ; X1*47 + X2*-47 -> 47*(X1-X2)
   ret float %D
 }
 

llvm/trunk/test/Transforms/Reassociate/liftsign.ll

+; RUN: opt -reassociate -gvn -S < %s | FileCheck %s
+
+; (x + 0.1234 * y) * (x + -0.1234 * y) -> (x + 0.1234 * y) * (x - 0.1234 * y)
+; so CSE can simplify it further
+define double @lift_sign1(double %x, double %y) nounwind readnone ssp uwtable {
+; CHECK-LABEL: @lift_sign1(
+  %mul = fmul double 1.234000e-01, %y
+  %add = fadd double %mul, %x
+  %mul1 = fmul double -1.234000e-01, %y
+  %add2 = fadd double %mul1, %x
+  %mul3 = fmul double %add, %add2
+; CHECK-NOT: %mul1 = fmul double -1.234000e-01, %y
+; CHECK-NOT: %add2 = fadd %mul1, %x
+; CHECK: %add2.repl = fsub double %x, %mul
+; CHECK: %mul3 = fmul double %add, %add2
+ret double %mul3
+}
+
+; (x + -0.1234 * y) * (x + -0.1234 * y) -> (x - 0.1234 * y) * (x - 0.1234 * y)
+; GVN can then rewrite it even further
+define double @lift_sign2(double %x, double %y) nounwind readnone ssp uwtable {
+; CHECK-LABEL: @lift_sign2(
+  %mul = fmul double %y, -1.234000e-01
+  %add = fadd double %mul, %x
+  %mul1 = fmul double %y, -1.234000e-01
+  %add2 = fadd double %mul1, %x
+  %mul3 = fmul double %add, %add2
+; CHECK-NOT: %mul = fmul double %y, -1.234000e-01
+; CHECK-NOT: %add = fadd double %mul, %x
+; CHECK-NOT: %mul1 = fmul double %y, -1.234000e-01
+; CHECK-NOT: %add2 = fadd double %mul1, %x
+; CHECK-NOT: %mul3 = fmul double %add, %add2
+; CHECK: %mul = fmul double 1.234000e-01, %y
+; CHECK: %add.repl = fsub double %x, %mul
+; CHECK: %mul3 = fmul double %add.repl, %add.repl
+  ret double %mul3
+}
+
+; (x + 0.1234 * y) * (x - -0.1234 * y) -> (x + 0.1234 * y) * (x + 0.1234 * y)
+define double @lift_sign3(double %x, double %y) nounwind readnone ssp uwtable {
+; CHECK-LABEL: @lift_sign3(
+  %mul = fmul double %y, 1.234000e-01
+  %add = fadd double %mul, %x
+  %mul1 = fmul double %y, -1.234000e-01
+  %add2 = fsub double %x, %mul1
+  %mul3 = fmul double %add, %add2
+; CHECK-NOT: %mul1 = fmul double %y, -1.234000e-01
+; CHECK-NOT: %add2 = fsub double %x, %mul1
+; CHECK-NOT: %mul3 = fmul double %add, %add2
+; CHECK: %mul3 = fmul double %add, %add
+  ret double %mul3
+}
+
+; (x + 0.1234 / y) * (x + -0.1234 / y) -> (x + 0.1234 / y) * (x - 0.1234 / y)
+; so CSE can simplify it further
+define double @lift_sign4(double %x, double %y) nounwind readnone ssp uwtable {
+; CHECK-LABEL: @lift_sign4(
+  %div = fdiv double 1.234000e-01, %y
+  %add = fadd double %div, %x
+  %div1 = fdiv double -1.234000e-01, %y
+  %add2 = fadd double %div1, %x
+  %mul3 = fmul double %add, %add2
+; CHECK-NOT: %div1 = fdiv double -1.234000e-01, %y
+; CHECK-NOT: %add2 = fadd double %div1, %x
+; CHECK-NOT: %mul3 = fmul double %add, %add2
+; CHECK: %add2.repl = fsub double %x, %div
+; CHECK: %mul3 = fmul double %add, %add2.repl
+  ret double %mul3
+}