[Reassociate] try harder to convert negative FP constants to positive

[spatel]

Summary

This is an extension of a transform that tries to produce positive floating-point constants to improve canonicalization (and hopefully lead to more reassociation and CSE).

The original patches were:
D4904
D5363 (rL221721)

But as the test diffs show, these were limited to basic patterns by walking from an instruction to its single user rather than recursively moving up the def-use sequence. No fast-math is required here because we're only rearranging implicit FP negations in intermediate ops.

A motivating bug is:
https://bugs.llvm.org/show_bug.cgi?id=32939
...but unfortunately the transform in that example gets inverted in the backend, so we end up with the same code. I'll investigate that case as a follow-up, but I think the changes here can be viewed as an independent improvement.

[spatel]

llvm/test/Transforms/Reassociate/reassoc-intermediate-fnegs.ll

9–12 ↗

(On Diff #214158)

I stepped through this case, and we don't remove the negative constant because ShouldBreakUpSubtract() is true. Even with the positive constant, we failed to factorize, so this needs work either way.

[mcberg2017]

llvm/lib/Transforms/Scalar/Reassociate.cpp

2014 ↗

(On Diff #214158)

How about in place of the assert, logic to bypass candidates that meet these constraints. It should not happen given how the candidate list is built, however this would ensure if something did get in we would not process it for release builds.

2021 ↗

(On Diff #214158)

Same here...

[mcberg2017]

I worked through some of the tests, but would like another set of eyes to verify. Doing a quick internal validation with this for regressions.

llvm/lib/Transforms/Scalar/Reassociate.cpp

2014 ↗

(On Diff #214158)

Actually this is fine as it is...

[mcberg2017]

We have some stir(some regressions - a few instructions here and there), however the change is overall beneficial for us.

LGTM.

[spatel]

In D65954#1621623, @mcberg2017 wrote:

We have some stir(some regressions - a few instructions here and there), however the change is overall beneficial for us.

LGTM.

Thanks! If you can share any of those tests that regressed, I can dig further into this pass to see if we can improve them.

[mcberg2017]

Tell you what, I don't want to hold up this patch. I will see if I can abstract a test example into common form for a public target with an example or two and send it to you offline.

[mcberg2017]

Just to close the loop, the issues I saw are internal manifested only, they do not port to other targets.

llvm/trunk/include/llvm/Transforms/Scalar/Reassociate.h

private:
   Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder,
                                  SmallVectorImpl<reassociate::Factor> &Factors);
   Value *OptimizeMul(BinaryOperator *I,
                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
   Value *RemoveFactorFromExpression(Value *V, Value *Factor);
   void EraseInst(Instruction *I);
   void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts);
   void OptimizeInst(Instruction *I);
-  Instruction *canonicalizeNegConstExpr(Instruction *I);
+  Instruction *canonicalizeNegFPConstantsForOp(Instruction *I, Instruction *Op,
+                                               Value *OtherOp);
+  Instruction *canonicalizeNegFPConstants(Instruction *I);
   void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H

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

if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) {
       // of dominance.
       if (ValueRankMap.find(Op) != ValueRankMap.end())
         RedoInsts.insert(Op);
     }
 
   MadeChange = true;
 }
 
-// Canonicalize expressions of the following form:
-//  x + (-Constant * y) -> x - (Constant * y)
-//  x - (-Constant * y) -> x + (Constant * y)
-Instruction *ReassociatePass::canonicalizeNegConstExpr(Instruction *I) {
-  if (!I->hasOneUse() || I->getType()->isVectorTy())
-    return nullptr;
-
-  // Must be a fmul or fdiv instruction.
-  unsigned Opcode = I->getOpcode();
-  if (Opcode != Instruction::FMul && Opcode != Instruction::FDiv)
-    return nullptr;
-
-  auto *C0 = dyn_cast<ConstantFP>(I->getOperand(0));
-  auto *C1 = dyn_cast<ConstantFP>(I->getOperand(1));
-
-  // Both operands are constant, let it get constant folded away.
-  if (C0 && C1)
-    return nullptr;
-
-  ConstantFP *CF = C0 ? C0 : C1;
-
-  // Must have one constant operand.
-  if (!CF)
-    return nullptr;
+/// 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.
+static void getNegatibleInsts(Value *V,
+                              SmallVectorImpl<Instruction *> &Candidates) {
+  // Handle only one-use instructions. Combining negations does not justify
+  // replicating instructions.
+  Instruction *I;
+  if (!match(V, m_OneUse(m_Instruction(I))))
+    return;
 
-  // Must be a negative ConstantFP.
-  if (!CF->isNegative())
-    return nullptr;
+  // Handle expressions of multiplications and divisions.
+  // TODO: This could look through floating-point casts.
+  const APFloat *C;
+  switch (I->getOpcode()) {
+    case Instruction::FMul:
+      // Not expecting non-canonical code here. Bail out and wait.
+      if (match(I->getOperand(0), m_Constant()))
+        break;
 
-  // User must be a binary operator with one or more uses.
-  Instruction *User = I->user_back();
-  if (!isa<BinaryOperator>(User) || User->use_empty())
-    return nullptr;
+      if (match(I->getOperand(1), m_APFloat(C)) && C->isNegative()) {
+        Candidates.push_back(I);
+        LLVM_DEBUG(dbgs() << "FMul with negative constant: " << *I << '\n');
+      }
+      getNegatibleInsts(I->getOperand(0), Candidates);
+      getNegatibleInsts(I->getOperand(1), Candidates);
+      break;
+    case Instruction::FDiv:
+      // Not expecting non-canonical code here. Bail out and wait.
+      if (match(I->getOperand(0), m_Constant()) &&
+          match(I->getOperand(1), m_Constant()))
+        break;
 
-  unsigned UserOpcode = User->getOpcode();
-  if (UserOpcode != Instruction::FAdd && UserOpcode != Instruction::FSub)
-    return nullptr;
+      if ((match(I->getOperand(0), m_APFloat(C)) && C->isNegative()) ||
+          (match(I->getOperand(1), m_APFloat(C)) && C->isNegative())) {
+        Candidates.push_back(I);
+        LLVM_DEBUG(dbgs() << "FDiv with negative constant: " << *I << '\n');
+      }
+      getNegatibleInsts(I->getOperand(0), Candidates);
+      getNegatibleInsts(I->getOperand(1), Candidates);
+      break;
+    default:
+      break;
+  }
+}
 
-  // Subtraction is not commutative. Explicitly, the following transform is
-  // not valid: (-Constant * y) - x  -> x + (Constant * y)
-  if (!User->isCommutative() && User->getOperand(1) != I)
+/// Given an fadd/fsub with an operand that is a one-use instruction
+/// (the fadd/fsub), try to change negative floating-point constants into
+/// positive constants to increase potential for reassociation and CSE.
+Instruction *ReassociatePass::canonicalizeNegFPConstantsForOp(Instruction *I,
+                                                              Instruction *Op,
+                                                              Value *OtherOp) {
+  assert((I->getOpcode() == Instruction::FAdd ||
+          I->getOpcode() == Instruction::FSub) && "Expected fadd/fsub");
+
+  // Collect instructions with negative FP constants from the subtree that ends
+  // in Op.
+  SmallVector<Instruction *, 4> Candidates;
+  getNegatibleInsts(Op, Candidates);
+  if (Candidates.empty())
     return nullptr;
 
   // Don't canonicalize x + (-Constant * y) -> x - (Constant * y), if the
   // resulting subtract will be broken up later.  This can get us into an
   // infinite loop during reassociation.
-  if (UserOpcode == Instruction::FAdd && ShouldBreakUpSubtract(User))
+  bool IsFSub = I->getOpcode() == Instruction::FSub;
+  bool NeedsSubtract = !IsFSub && Candidates.size() % 2 == 1;
+  if (NeedsSubtract && ShouldBreakUpSubtract(I))
     return nullptr;
 
-  // Change the sign of the constant.
-  APFloat Val = CF->getValueAPF();
-  Val.changeSign();
-  I->setOperand(C0 ? 0 : 1, ConstantFP::get(CF->getContext(), Val));
-
-  // Canonicalize I to RHS to simplify the next bit of logic. E.g.,
-  // ((-Const*y) + x) -> (x + (-Const*y)).
-  if (User->getOperand(0) == I && User->isCommutative())
-    cast<BinaryOperator>(User)->swapOperands();
-
-  Value *Op0 = User->getOperand(0);
-  Value *Op1 = User->getOperand(1);
-  BinaryOperator *NI;
-  switch (UserOpcode) {
-  default:
-    llvm_unreachable("Unexpected Opcode!");
-  case Instruction::FAdd:
-    NI = BinaryOperator::CreateFSub(Op0, Op1);
-    NI->setFastMathFlags(cast<FPMathOperator>(User)->getFastMathFlags());
-    break;
-  case Instruction::FSub:
-    NI = BinaryOperator::CreateFAdd(Op0, Op1);
-    NI->setFastMathFlags(cast<FPMathOperator>(User)->getFastMathFlags());
-    break;
+  for (Instruction *Negatible : Candidates) {
+    const APFloat *C;
+    if (match(Negatible->getOperand(0), m_APFloat(C))) {
+      assert(!match(Negatible->getOperand(1), m_Constant()) &&
+             "Expecting only 1 constant operand");
+      assert(C->isNegative() && "Expected negative FP constant");
+      Negatible->setOperand(0, ConstantFP::get(Negatible->getType(), abs(*C)));
+      MadeChange = true;
     }
+    if (match(Negatible->getOperand(1), m_APFloat(C))) {
+      assert(!match(Negatible->getOperand(0), m_Constant()) &&
+             "Expecting only 1 constant operand");
+      assert(C->isNegative() && "Expected negative FP constant");
+      Negatible->setOperand(1, ConstantFP::get(Negatible->getType(), abs(*C)));
+      MadeChange = true;
+    }
+  }
+  assert(MadeChange == true && "Negative constant candidate was not changed");
 
-  NI->insertBefore(User);
-  NI->setName(User->getName());
-  User->replaceAllUsesWith(NI);
-  NI->setDebugLoc(I->getDebugLoc());
+  // Negations cancelled out.
+  if (Candidates.size() % 2 == 0)
+    return I;
+
+  // Negate the final operand in the expression by flipping the opcode of this
+  // fadd/fsub.
+  assert(Candidates.size() % 2 == 1 && "Expected odd number");
+  IRBuilder<> Builder(I);
+  Value *NewInst = IsFSub ? Builder.CreateFAddFMF(OtherOp, Op, I)
+                          : Builder.CreateFSubFMF(OtherOp, Op, I);
+  I->replaceAllUsesWith(NewInst);
   RedoInsts.insert(I);
-  MadeChange = true;
-  return NI;
+  return dyn_cast<Instruction>(NewInst);
+}
+
+/// Canonicalize expressions that contain a negative floating-point constant
+/// of the following form:
+///   OtherOp + (subtree) -> OtherOp {+/-} (canonical subtree)
+///   (subtree) + OtherOp -> OtherOp {+/-} (canonical subtree)
+///   OtherOp - (subtree) -> OtherOp {+/-} (canonical subtree)
+///
+/// The fadd/fsub opcode may be switched to allow folding a negation into the
+/// input instruction.
+Instruction *ReassociatePass::canonicalizeNegFPConstants(Instruction *I) {
+  LLVM_DEBUG(dbgs() << "Combine negations for: " << *I << '\n');
+  Value *X;
+  Instruction *Op;
+  if (match(I, m_FAdd(m_Value(X), m_OneUse(m_Instruction(Op)))))
+    if (Instruction *R = canonicalizeNegFPConstantsForOp(I, Op, X))
+      I = R;
+  if (match(I, m_FAdd(m_OneUse(m_Instruction(Op)), m_Value(X))))
+    if (Instruction *R = canonicalizeNegFPConstantsForOp(I, Op, X))
+      I = R;
+  if (match(I, m_FSub(m_Value(X), m_OneUse(m_Instruction(Op)))))
+    if (Instruction *R = canonicalizeNegFPConstantsForOp(I, Op, X))
+      I = R;
+  return I;
 }
 
 /// Inspect and optimize the given instruction. Note that erasing
 /// instructions is not allowed.
 void ReassociatePass::OptimizeInst(Instruction *I) {
   // Only consider operations that we understand.
   if (!isa<UnaryOperator>(I) && !isa<BinaryOperator>(I))
     return;
 
   if (I->getOpcode() == Instruction::Shl && isa<ConstantInt>(I->getOperand(1)))
     // If an operand of this shift is a reassociable multiply, or if the shift
     // is used by a reassociable multiply or add, turn into a multiply.
     if (isReassociableOp(I->getOperand(0), Instruction::Mul) ||
         (I->hasOneUse() &&
          (isReassociableOp(I->user_back(), Instruction::Mul) ||
           isReassociableOp(I->user_back(), Instruction::Add)))) {
       Instruction *NI = ConvertShiftToMul(I);
       RedoInsts.insert(I);
       MadeChange = true;
       I = NI;
     }
 
-  // Canonicalize negative constants out of expressions.
-  if (Instruction *Res = canonicalizeNegConstExpr(I))
-    I = Res;
-
   // Commute binary operators, to canonicalize the order of their operands.
   // This can potentially expose more CSE opportunities, and makes writing other
   // transformations simpler.
   if (I->isCommutative())
     canonicalizeOperands(I);
 
+  // Canonicalize negative constants out of expressions.
+  if (Instruction *Res = canonicalizeNegFPConstants(I))
+    I = Res;
+
   // Don't optimize floating-point instructions unless they are 'fast'.
   if (I->getType()->isFPOrFPVectorTy() && !I->isFast())
     return;
 
   // Do not reassociate boolean (i1) expressions.  We want to preserve the
   // original order of evaluation for short-circuited comparisons that
   // SimplifyCFG has folded to AND/OR expressions.  If the expression
   // is not further optimized, it is likely to be transformed back to a

llvm/trunk/test/Transforms/Reassociate/canonicalize-neg-const.ll

;
   %mul5 = fmul fast double %pow2, 5.000000e-01
   %sub1 = fsub fast double %sub, %mul5
   %add = fadd fast double %sub1, %sub1
   ret double %add
 }
 
 define double @fadd_fmul_neg_const1(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_fmul_neg_const1(
-; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[B:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[B:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[MUL0]], [[C:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = fadd double [[A:%.*]], [[MUL1]]
-; CHECK-NEXT:    ret double [[ADD]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fsub double [[A:%.*]], [[MUL1]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %mul0 = fmul double %b, -3.0
   %mul1 = fmul double %mul0, %c
   %add = fadd double %mul1, %a
   ret double %add
 }
 
 define double @fadd_fmul_neg_const2(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_fmul_neg_const2(
-; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[MUL0]], [[B:%.*]]
 ; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[MUL1]], 4.000000e+00
-; CHECK-NEXT:    [[ADD1:%.*]] = fsub double [[A]], [[MUL2]]
-; CHECK-NEXT:    ret double [[ADD1]]
+; CHECK-NEXT:    [[ADD:%.*]] = fadd double [[A]], [[MUL2]]
+; CHECK-NEXT:    ret double [[ADD]]
 ;
   %mul0 = fmul double %a, -3.0
   %mul1 = fmul double %mul0, %b
   %mul2 = fmul double %mul1, -4.0
   %add = fadd double %mul2, %a
   ret double %add
 }
 
 define double @fadd_fmul_neg_const3(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_fmul_neg_const3(
-; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[MUL0]], [[B:%.*]]
-; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[MUL1]], -4.000000e+00
+; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[MUL1]], 4.000000e+00
 ; CHECK-NEXT:    [[MUL3:%.*]] = fmul double [[MUL2]], 5.000000e+00
-; CHECK-NEXT:    [[ADD1:%.*]] = fsub double [[C:%.*]], [[MUL3]]
-; CHECK-NEXT:    ret double [[ADD1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fsub double [[C:%.*]], [[MUL3]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %mul0 = fmul double %a, -3.0
   %mul1 = fmul double %mul0, %b
   %mul2 = fmul double %mul1, -4.0
   %mul3 = fmul double %mul2, -5.0
   %add = fadd double %mul3, %c
   ret double %add
 }
 
 define double @fsub_fmul_neg_const1(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fsub_fmul_neg_const1(
-; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[B:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[B:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[MUL0]], [[C:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[A:%.*]], [[MUL1]]
-; CHECK-NEXT:    ret double [[SUB]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd double [[A:%.*]], [[MUL1]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %mul0 = fmul double %b, -3.0
   %mul1 = fmul double %mul0, %c
   %sub = fsub double %a, %mul1
   ret double %sub
 }
 
 define double @fsub_fmul_neg_const2(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fsub_fmul_neg_const2(
-; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[MUL0]], [[B:%.*]]
 ; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[MUL1]], 4.000000e+00
-; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[A]], [[MUL2]]
-; CHECK-NEXT:    ret double [[SUB]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd double [[A]], [[MUL2]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %mul0 = fmul double %a, -3.0
   %mul1 = fmul double %mul0, %b
   %mul2 = fmul double %mul1, 4.0
   %sub = fsub double %a, %mul2
   ret double %sub
 }
 
 define double @fsub_fmul_neg_const3(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fsub_fmul_neg_const3(
 ; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[MUL0]], [[B:%.*]]
-; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[MUL1]], -4.000000e+00
+; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[MUL1]], 4.000000e+00
 ; CHECK-NEXT:    [[MUL3:%.*]] = fmul double [[MUL2]], 5.000000e+00
-; CHECK-NEXT:    [[SUB1:%.*]] = fadd double [[C:%.*]], [[MUL3]]
-; CHECK-NEXT:    ret double [[SUB1]]
+; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[C:%.*]], [[MUL3]]
+; CHECK-NEXT:    ret double [[SUB]]
 ;
   %mul0 = fmul double %a, 3.0
   %mul1 = fmul double %mul0, %b
   %mul2 = fmul double %mul1, -4.0
   %mul3 = fmul double %mul2, -5.0
   %sub = fsub double %c, %mul3
   ret double %sub
 }
 
 define double @fadd_fdiv_neg_const1(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_fdiv_neg_const1(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double [[B:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double [[B:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[DIV0]], [[C:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = fadd double [[A:%.*]], [[DIV1]]
-; CHECK-NEXT:    ret double [[ADD]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fsub double [[A:%.*]], [[DIV1]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %div0 = fdiv double %b, -3.0
   %div1 = fdiv double %div0, %c
   %add = fadd double %div1, %a
   ret double %add
 }
 
 define double @fadd_fdiv_neg_const2(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_fdiv_neg_const2(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double -3.000000e+00, [[A:%.*]]
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double 3.000000e+00, [[A:%.*]]
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[DIV0]], [[B:%.*]]
 ; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double [[DIV1]], 7.000000e+00
-; CHECK-NEXT:    [[ADD1:%.*]] = fsub double [[A]], [[DIV2]]
-; CHECK-NEXT:    ret double [[ADD1]]
+; CHECK-NEXT:    [[ADD:%.*]] = fadd double [[A]], [[DIV2]]
+; CHECK-NEXT:    ret double [[ADD]]
 ;
   %div0 = fdiv double -3.0, %a
   %div1 = fdiv double %div0, %b
   %div2 = fdiv double %div1, -7.0
   %add = fadd double %div2, %a
   ret double %add
 }
 
 define double @fadd_fdiv_neg_const3(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_fdiv_neg_const3(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double [[A:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double [[A:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[DIV0]], [[B:%.*]]
-; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double -4.000000e+00, [[DIV1]]
+; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double 4.000000e+00, [[DIV1]]
 ; CHECK-NEXT:    [[DIV3:%.*]] = fdiv double [[DIV2]], 5.000000e+00
 ; CHECK-NEXT:    [[ADD:%.*]] = fadd double [[C:%.*]], [[DIV3]]
 ; CHECK-NEXT:    ret double [[ADD]]
 ;
   %div0 = fdiv double %a, -3.0
   %div1 = fdiv double %div0, %b
   %div2 = fdiv double -4.0, %div1
   %div3 = fdiv double %div2, 5.0
   %add = fadd double %div3, %c
   ret double %add
 }
 
 define double @fsub_fdiv_neg_const1(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fsub_fdiv_neg_const1(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double [[B:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double [[B:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[DIV0]], [[C:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[A:%.*]], [[DIV1]]
-; CHECK-NEXT:    ret double [[SUB]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd double [[A:%.*]], [[DIV1]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %div0 = fdiv double %b, -3.0
   %div1 = fdiv double %div0, %c
   %sub = fsub double %a, %div1
   ret double %sub
 }
 
 define double @fsub_fdiv_neg_const2(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fsub_fdiv_neg_const2(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double -3.000000e+00, [[A:%.*]]
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double 3.000000e+00, [[A:%.*]]
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[DIV0]], [[B:%.*]]
 ; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double [[DIV1]], 7.000000e+00
-; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[A]], [[DIV2]]
-; CHECK-NEXT:    ret double [[SUB]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd double [[A]], [[DIV2]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %div0 = fdiv double -3.0, %a
   %div1 = fdiv double %div0, %b
   %div2 = fdiv double %div1, 7.0
   %sub = fsub double %a, %div2
   ret double %sub
 }
 
 define double @fsub_fdiv_neg_const3(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fsub_fdiv_neg_const3(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double -3.000000e+00, [[A:%.*]]
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double 3.000000e+00, [[A:%.*]]
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[DIV0]], [[B:%.*]]
-; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double [[DIV1]], -7.000000e+00
+; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double [[DIV1]], 7.000000e+00
 ; CHECK-NEXT:    [[DIV3:%.*]] = fdiv double 5.000000e+00, [[DIV2]]
-; CHECK-NEXT:    [[SUB1:%.*]] = fadd double [[C:%.*]], [[DIV3]]
-; CHECK-NEXT:    ret double [[SUB1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd double [[C:%.*]], [[DIV3]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %div0 = fdiv double -3.0, %a
   %div1 = fdiv double %div0, %b
   %div2 = fdiv double %div1, -7.0
   %div3 = fdiv double -5.0, %div2
   %sub = fsub double %c, %div3
   ret double %sub
 }
 
 define double @fadd_mix_neg_const1(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_mix_neg_const1(
-; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[B:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[B:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[MUL0]], [[C:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = fadd double [[A:%.*]], [[DIV1]]
-; CHECK-NEXT:    ret double [[ADD]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fsub double [[A:%.*]], [[DIV1]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %mul0 = fmul double %b, -3.0
   %div1 = fdiv double %mul0, %c
   %add = fadd double %div1, %a
   ret double %add
 }
 
 define double @fadd_mix_neg_const2(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_mix_neg_const2(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double -3.000000e+00, [[A:%.*]]
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double 3.000000e+00, [[A:%.*]]
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[DIV0]], [[B:%.*]]
 ; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double [[MUL1]], 5.000000e+00
-; CHECK-NEXT:    [[ADD1:%.*]] = fsub double [[A]], [[DIV2]]
-; CHECK-NEXT:    ret double [[ADD1]]
+; CHECK-NEXT:    [[ADD:%.*]] = fadd double [[A]], [[DIV2]]
+; CHECK-NEXT:    ret double [[ADD]]
 ;
   %div0 = fdiv double -3.0, %a
   %mul1 = fmul double %div0, %b
   %div2 = fdiv double %mul1, -5.0
   %add = fadd double %div2, %a
   ret double %add
 }
 
 define double @fadd_mix_neg_const3(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_mix_neg_const3(
-; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[MUL0]], [[B:%.*]]
-; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[DIV1]], -4.000000e+00
+; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[DIV1]], 4.000000e+00
 ; CHECK-NEXT:    [[DIV3:%.*]] = fdiv double [[MUL2]], 5.000000e+00
-; CHECK-NEXT:    [[ADD1:%.*]] = fsub double [[C:%.*]], [[DIV3]]
-; CHECK-NEXT:    ret double [[ADD1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fsub double [[C:%.*]], [[DIV3]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %mul0 = fmul double %a, -3.0
   %div1 = fdiv double %mul0, %b
   %mul2 = fmul double -4.0, %div1
   %div3 = fdiv double %mul2, -5.0
   %add = fadd double %div3, %c
   ret double %add
 }
 
 define double @fsub_mix_neg_const1(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fsub_mix_neg_const1(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double [[B:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double [[B:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[DIV0]], [[C:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[A:%.*]], [[MUL1]]
-; CHECK-NEXT:    ret double [[SUB]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd double [[A:%.*]], [[MUL1]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %div0 = fdiv double %b, -3.0
   %mul1 = fmul double %div0, %c
   %sub = fsub double %a, %mul1
   ret double %sub
 }
 define double @fsub_mix_neg_const2(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fsub_mix_neg_const2(
-; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], -3.000000e+00
+; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], 3.000000e+00
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[MUL0]], [[B:%.*]]
 ; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[DIV1]], 5.000000e+00
-; CHECK-NEXT:    [[SUB1:%.*]] = fadd double [[A]], [[MUL2]]
-; CHECK-NEXT:    ret double [[SUB1]]
+; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[A]], [[MUL2]]
+; CHECK-NEXT:    ret double [[SUB]]
 ;
   %mul0 = fmul double -3.0, %a
   %div1 = fdiv double %mul0, %b
   %mul2 = fmul double %div1, -5.0
   %sub = fsub double %a, %mul2
   ret double %sub
 }
 
 define double @fsub_mix_neg_const3(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fsub_mix_neg_const3(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double -3.000000e+00, [[A:%.*]]
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double 3.000000e+00, [[A:%.*]]
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[DIV0]], [[B:%.*]]
-; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double [[MUL1]], -7.000000e+00
+; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double [[MUL1]], 7.000000e+00
 ; CHECK-NEXT:    [[MUL3:%.*]] = fmul double [[DIV2]], 5.000000e+00
-; CHECK-NEXT:    [[SUB1:%.*]] = fadd double [[C:%.*]], [[MUL3]]
-; CHECK-NEXT:    ret double [[SUB1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd double [[C:%.*]], [[MUL3]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %div0 = fdiv double -3.0, %a
   %mul1 = fmul double %div0, %b
   %div2 = fdiv double %mul1, -7.0
   %mul3 = fmul double -5.0, %div2
   %sub = fsub double %c, %mul3
   ret double %sub
 }
 
 define double @fadd_both_ops_mix_neg_const1(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_both_ops_mix_neg_const1(
 ; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[B:%.*]], -3.000000e+00
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[MUL0]], [[C:%.*]]
-; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[A:%.*]], -4.000000e+00
+; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[A:%.*]], 4.000000e+00
 ; CHECK-NEXT:    [[DIV3:%.*]] = fdiv double [[MUL2]], [[C]]
-; CHECK-NEXT:    [[ADD:%.*]] = fadd double [[DIV1]], [[DIV3]]
-; CHECK-NEXT:    ret double [[ADD]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fsub double [[DIV1]], [[DIV3]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %mul0 = fmul double %b, -3.0
   %div1 = fdiv double %mul0, %c
   %mul2 = fmul double %a, -4.0
   %div3 = fdiv double %mul2, %c
   %add = fadd double %div1, %div3
   ret double %add
 }
 
 define double @fadd_both_ops_mix_neg_const2(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_both_ops_mix_neg_const2(
-; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double -3.000000e+00, [[A:%.*]]
+; CHECK-NEXT:    [[DIV0:%.*]] = fdiv double 3.000000e+00, [[A:%.*]]
 ; CHECK-NEXT:    [[MUL1:%.*]] = fmul double [[DIV0]], [[B:%.*]]
 ; CHECK-NEXT:    [[DIV2:%.*]] = fdiv double [[MUL1]], 7.000000e+00
-; CHECK-NEXT:    [[DIV3:%.*]] = fdiv double -5.000000e+00, [[C:%.*]]
+; CHECK-NEXT:    [[DIV3:%.*]] = fdiv double 5.000000e+00, [[C:%.*]]
 ; CHECK-NEXT:    [[MUL4:%.*]] = fmul double [[B]], [[DIV3]]
-; CHECK-NEXT:    [[DIV5:%.*]] = fdiv double [[MUL4]], -6.000000e+00
-; CHECK-NEXT:    [[ADD1:%.*]] = fsub double [[DIV5]], [[DIV2]]
-; CHECK-NEXT:    ret double [[ADD1]]
+; CHECK-NEXT:    [[DIV5:%.*]] = fdiv double [[MUL4]], 6.000000e+00
+; CHECK-NEXT:    [[ADD:%.*]] = fadd double [[DIV2]], [[DIV5]]
+; CHECK-NEXT:    ret double [[ADD]]
 ;
   %div0 = fdiv double -3.0, %a
   %mul1 = fmul double %div0, %b
   %div2 = fdiv double %mul1, -7.0
   %div3 = fdiv double -5.0, %c
   %mul4 = fmul double %div3, %b
   %div5 = fdiv double %mul4, -6.0
   %add = fadd double %div2, %div5
   ret double %add
 }
 
 define double @fadd_both_opsmix_neg_const3(double %a, double %b, double %c) {
 ; CHECK-LABEL: @fadd_both_opsmix_neg_const3(
 ; CHECK-NEXT:    [[MUL0:%.*]] = fmul double [[A:%.*]], -3.000000e+00
 ; CHECK-NEXT:    [[DIV1:%.*]] = fdiv double [[MUL0]], [[B:%.*]]
 ; CHECK-NEXT:    [[MUL2:%.*]] = fmul double [[DIV1]], -4.000000e+00
-; CHECK-NEXT:    [[DIV3:%.*]] = fdiv double [[MUL2]], 5.000000e+00
-; CHECK-NEXT:    [[MUL4:%.*]] = fmul double [[C:%.*]], -6.000000e+00
+; CHECK-NEXT:    [[DIV3:%.*]] = fdiv double [[MUL2]], -5.000000e+00
+; CHECK-NEXT:    [[MUL4:%.*]] = fmul double [[C:%.*]], 6.000000e+00
 ; CHECK-NEXT:    [[DIV5:%.*]] = fdiv double [[MUL4]], [[B]]
-; CHECK-NEXT:    [[MUL6:%.*]] = fmul double [[DIV5]], -7.000000e+00
-; CHECK-NEXT:    [[MUL7:%.*]] = fdiv double [[MUL6]], -9.000000e+00
-; CHECK-NEXT:    [[ADD1:%.*]] = fsub double [[MUL7]], [[DIV3]]
-; CHECK-NEXT:    ret double [[ADD1]]
+; CHECK-NEXT:    [[MUL6:%.*]] = fmul double [[DIV5]], 7.000000e+00
+; CHECK-NEXT:    [[MUL7:%.*]] = fdiv double [[MUL6]], 9.000000e+00
+; CHECK-NEXT:    [[TMP1:%.*]] = fsub double [[DIV3]], [[MUL7]]
+; CHECK-NEXT:    ret double [[TMP1]]
 ;
   %mul0 = fmul double %a, -3.0
   %div1 = fdiv double %mul0, %b
   %mul2 = fmul double -4.0, %div1
   %div3 = fdiv double %mul2, -5.0
   %mul4 = fmul double %c, -6.0
   %div5 = fdiv double %mul4, %b
   %mul6 = fmul double -7.0, %div5
   %mul7 = fdiv double %mul6, -9.0
   %add = fadd double %div3, %mul7
   ret double %add
 }

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

;
   ret <2 x double> %4
 }
 
 ; Check -(-(z*40)*a) -> a*40*z.
 
 define <2 x float> @test10(<2 x float> %a, <2 x float> %b, <2 x float> %z) {
 ; CHECK-LABEL: @test10(
 ; CHECK-NEXT:    [[TMP1:%.*]] = fsub fast <2 x float> zeroinitializer, zeroinitializer
-; CHECK-NEXT:    [[E:%.*]] = fmul fast <2 x float> [[A:%.*]], <float 4.000000e+01, float 4.000000e+01>
-; CHECK-NEXT:    [[F:%.*]] = fmul fast <2 x float> [[E]], [[Z:%.*]]
-; CHECK-NEXT:    ret <2 x float> [[F]]
+; CHECK-NEXT:    [[C:%.*]] = fmul fast <2 x float> [[A:%.*]], <float 4.000000e+01, float 4.000000e+01>
+; CHECK-NEXT:    [[E:%.*]] = fmul fast <2 x float> [[C]], [[Z:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = fadd fast <2 x float> [[E]], zeroinitializer
+; CHECK-NEXT:    ret <2 x float> [[TMP2]]
 ;
   %d = fmul fast <2 x float> %z, <float 4.000000e+01, float 4.000000e+01>
   %c = fsub fast <2 x float> <float 0.000000e+00, float 0.000000e+00>, %d
   %e = fmul fast <2 x float> %a, %c
   %f = fsub fast <2 x float> <float 0.000000e+00, float 0.000000e+00>, %e
   ret <2 x float> %f
 }
 
;
   %f = fneg reassoc <2 x float> %e
   ret <2 x float> %f
 }
 
 ; Check x*y+y*x -> x*y*2.
 
 define <2 x double> @test11(<2 x double> %x, <2 x double> %y) {
 ; CHECK-LABEL: @test11(
-; CHECK-NEXT:    [[FACTOR:%.*]] = fmul fast <2 x double> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[FACTOR:%.*]] = fmul fast <2 x double> [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast <2 x double> [[FACTOR]], <double 2.000000e+00, double 2.000000e+00>
 ; CHECK-NEXT:    ret <2 x double> [[REASS_MUL]]
 ;
   %1 = fmul fast <2 x double> %x, %y
   %2 = fmul fast <2 x double> %y, %x
   %3 = fadd fast <2 x double> %1, %2
   ret <2 x double> %3
 }

 ; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i64> [[MUL]], <i64 5, i64 5>
 ; CHECK-NEXT:    ret <2 x i64> [[SHL]]
 ;
   %mul = mul <2 x i64> %c, %b
   %shl = shl <2 x i64> %mul, <i64 5, i64 5>
   ret <2 x i64> %shl
 }
 
-; FIXME: expressions with a negative const should be canonicalized to assist
-; further reassociation.
-; We would expect (-5*b)+a -> a-(5*b) but only the constant operand is commuted.
+; (-5*b)+a -> a-(5*b)
 
 define <4 x float> @test13(<4 x float> %a, <4 x float> %b) {
 ; CHECK-LABEL: @test13(
-; CHECK-NEXT:    [[MUL:%.*]] = fmul fast <4 x float> [[B:%.*]], <float -5.000000e+00, float -5.000000e+00, float -5.000000e+00, float -5.000000e+00>
-; CHECK-NEXT:    [[ADD:%.*]] = fadd fast <4 x float> [[MUL]], [[A:%.*]]
-; CHECK-NEXT:    ret <4 x float> [[ADD]]
+; CHECK-NEXT:    [[MUL:%.*]] = fmul fast <4 x float> [[B:%.*]], <float 5.000000e+00, float 5.000000e+00, float 5.000000e+00, float 5.000000e+00>
+; CHECK-NEXT:    [[TMP1:%.*]] = fsub fast <4 x float> [[A:%.*]], [[MUL]]
+; CHECK-NEXT:    ret <4 x float> [[TMP1]]
 ;
   %mul = fmul fast <4 x float> <float -5.000000e+00, float -5.000000e+00, float -5.000000e+00, float -5.000000e+00>, %b
   %add = fadd fast <4 x float> %mul, %a
   ret <4 x float> %add
 }
 
 ; Break up subtract to assist further reassociation.
 ; Check a+b-c -> a+b+-c.

llvm/trunk/test/Transforms/Reassociate/reassoc-intermediate-fnegs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -reassociate -S | FileCheck %s
 
-; Input is A op (B op C)
+; B * 5 + A * -5
+; TODO: (B - A) * 5
 
 define half @faddsubAssoc1(half %a, half %b) {
 ; CHECK-LABEL: @faddsubAssoc1(
-; CHECK-NEXT:    [[T2_NEG:%.*]] = fmul fast half [[A:%.*]], 0xH4500
+; CHECK-NEXT:    [[T2_NEG:%.*]] = fmul fast half [[A:%.*]], 0xHC500
 ; CHECK-NEXT:    [[REASS_MUL:%.*]] = fmul fast half [[B:%.*]], 0xH4500
-; CHECK-NEXT:    [[T51:%.*]] = fsub fast half [[REASS_MUL]], [[T2_NEG]]
 ; CHECK-NEXT:    [[T5:%.*]] = fadd fast half [[REASS_MUL]], [[T2_NEG]]
-; CHECK-NEXT:    ret half [[T51]]
+; CHECK-NEXT:    ret half [[T5]]
 ;
   %t1 = fmul fast half %b, 0xH4200 ; 3*b
   %t2 = fmul fast half %a, 0xH4500 ; 5*a
   %t3 = fmul fast half %b, 0xH4000 ; 2*b
   %t4 = fsub fast half %t2, %t1 ; 5 * a - 3 * b
   %t5 = fsub fast half %t3, %t4 ; 2 * b - ( 5 * a - 3 * b)
   ret half %t5 ; = 5 * (b - a)
 }
 
-; Input is (A op B) op C
+; B + A * 5
 
 define half @faddsubAssoc2(half %a, half %b) {
 ; CHECK-LABEL: @faddsubAssoc2(
 ; CHECK-NEXT:    [[T2:%.*]] = fmul fast half [[A:%.*]], 0xH4500
 ; CHECK-NEXT:    [[T5:%.*]] = fadd fast half [[B:%.*]], [[T2]]
 ; CHECK-NEXT:    ret half [[T5]]
 ;
   %t1 = fmul fast half %b, 0xH4200 ; 3*b
   %t2 = fmul fast half %a, 0xH4500 ; 5*a
   %t3 = fmul fast half %b, 0xH4000 ; 2*b
   %t4 = fadd fast half %t2, %t1 ; 5 * a + 3 * b
   %t5 = fsub fast half %t4, %t3 ; (5 * a + 3 * b) - (2 * b)
   ret half %t5 ; = 5 * a + b
 }