[Reassociate] Handle unary FNeg in the Reassociate pass

[cameron.mcinally]

Correct comment. Should be 'nnan', not 'nnan and nsz'.

[craig.topper]

llvm/lib/Transforms/Scalar/Reassociate.cpp

1974

Update comment

1985

If User is a unary FNeg, I assume isCommutative would be false and this getOperand call will access an operand that doesn't exist.

[cameron.mcinally]

llvm/lib/Transforms/Scalar/Reassociate.cpp

1974

Bah, these two changes weren't supposed to be a part of this patch. Just an oversight and will update...

[cameron.mcinally]

Remove unintentional changes. Also fix up a poor naming choice.

llvm/lib/Transforms/Scalar/Reassociate.cpp

else {
     BinaryOperator *Res = BinaryOperator::CreateFNeg(S1, Name, InsertBefore);
     Res->setFastMathFlags(cast<FPMathOperator>(FlagsOp)->getFastMathFlags());
     return Res;
   }
 }
 
 /// Replace 0-X with X*-1.
 static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) {
+  assert((isa<UnaryOperator>(Neg) || isa<BinaryOperator>(Neg)) &&
+         "Expected a Negate!");
+  // It's not safe to lower a unary FNeg into a FMul by -1.0. However,
+  // we can only reach this function with fast flags set, so it's
+  // safe to do with nnan.
+  assert((!isa<FPMathOperator>(Neg) || Neg->isFast()) &&
+          "Expecting FastMathFlags!");
+  unsigned OpNo = isa<BinaryOperator>(Neg) ? 1 : 0;
   Type *Ty = Neg->getType();
   Constant *NegOne = Ty->isIntOrIntVectorTy() ?
     ConstantInt::getAllOnesValue(Ty) : ConstantFP::get(Ty, -1.0);
 
-  BinaryOperator *Res = CreateMul(Neg->getOperand(1), NegOne, "", Neg, Neg);
-  Neg->setOperand(1, Constant::getNullValue(Ty)); // Drop use of op.
+  BinaryOperator *Res = CreateMul(Neg->getOperand(OpNo), NegOne, "", Neg, Neg);
+  Neg->setOperand(OpNo, Constant::getNullValue(Ty)); // Drop use of op.
   Res->takeName(Neg);
   Neg->replaceAllUsesWith(Res);
   Res->setDebugLoc(Neg->getDebugLoc());
   return Res;
 }
 
 /// Returns k such that lambda(2^Bitwidth) = 2^k, where lambda is the Carmichael
 /// function. This means that x^(2^k) === 1 mod 2^Bitwidth for

 /// For example, if you visit operands recursively starting from a leaf node
 /// then you will never see such an undef operand unless you get back to 'I',
 /// which requires passing through a phi node.
 ///
 /// Note that this routine may also mutate binary operators of the wrong type
 /// that have all uses inside the expression (i.e. only used by non-leaf nodes
 /// of the expression) if it can turn them into binary operators of the right
 /// type and thus make the expression bigger.
-static bool LinearizeExprTree(BinaryOperator *I,
+static bool LinearizeExprTree(Instruction *I,
                               SmallVectorImpl<RepeatedValue> &Ops) {
+  assert((isa<UnaryOperator>(I) || isa<BinaryOperator>(I)) &&
+         "Expected a UnaryOperator or BinaryOperator!");
   LLVM_DEBUG(dbgs() << "LINEARIZE: " << *I << '\n');
   unsigned Bitwidth = I->getType()->getScalarType()->getPrimitiveSizeInBits();
   unsigned Opcode = I->getOpcode();
   assert(I->isAssociative() && I->isCommutative() &&
          "Expected an associative and commutative operation!");
 
   // Visit all operands of the expression, keeping track of their weight (the
   // number of paths from the expression root to the operand, or if you like
   // the number of times that operand occurs in the linearized expression).
   // For example, if I = X + A, where X = A + B, then I, X and B have weight 1
   // while A has weight two.
 
   // Worklist of non-leaf nodes (their operands are in the expression too) along
   // with their weights, representing a certain number of paths to the operator.
   // If an operator occurs in the worklist multiple times then we found multiple
   // ways to get to it.
-  SmallVector<std::pair<BinaryOperator*, APInt>, 8> Worklist; // (Op, Weight)
+  SmallVector<std::pair<Instruction*, APInt>, 8> Worklist; // (Op, Weight)
   Worklist.push_back(std::make_pair(I, APInt(Bitwidth, 1)));
   bool Changed = false;
 
   // Leaves of the expression are values that either aren't the right kind of
   // operation (eg: a constant, or a multiply in an add tree), or are, but have
   // some uses that are not inside the expression.  For example, in I = X + X,
   // X = A + B, the value X has two uses (by I) that are in the expression.  If
   // X has any other uses, for example in a return instruction, then we consider
static bool LinearizeExprTree(Instruction *I,
   using LeafMap = DenseMap<Value *, APInt>;
   LeafMap Leaves; // Leaf -> Total weight so far.
   SmallVector<Value *, 8> LeafOrder; // Ensure deterministic leaf output order.
 
 #ifndef NDEBUG
   SmallPtrSet<Value *, 8> Visited; // For sanity checking the iteration scheme.
 #endif
   while (!Worklist.empty()) {
-    std::pair<BinaryOperator*, APInt> P = Worklist.pop_back_val();
+    std::pair<Instruction*, APInt> P = Worklist.pop_back_val();
     I = P.first; // We examine the operands of this binary operator.
 
-    for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx) { // Visit operands.
+    for (unsigned OpIdx = 0; OpIdx < I->getNumOperands(); ++OpIdx) { // Visit operands.
       Value *Op = I->getOperand(OpIdx);
       APInt Weight = P.second; // Number of paths to this operand.
       LLVM_DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n");
       assert(!Op->use_empty() && "No uses, so how did we get to it?!");
 
       // If this is a binary operation of the right kind with only one use then
       // add its operands to the expression.
       if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) {
#endif
               cast<Instruction>(Op)->getOpcode() != Opcode
               || (isa<FPMathOperator>(Op) &&
                   !cast<Instruction>(Op)->isFast())) &&
              "Should have been handled above!");
       assert(Op->hasOneUse() && "Has uses outside the expression tree!");
 
       // If this is a multiply expression, turn any internal negations into
       // multiplies by -1 so they can be reassociated.
-      if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op))
-        if ((Opcode == Instruction::Mul && match(BO, m_Neg(m_Value()))) ||
-            (Opcode == Instruction::FMul && match(BO, m_FNeg(m_Value())))) {
+      if (Instruction *Tmp = dyn_cast<Instruction>(Op))
+        if ((Opcode == Instruction::Mul && match(Tmp, m_Neg(m_Value()))) ||
+            (Opcode == Instruction::FMul && match(Tmp, m_FNeg(m_Value())))) {
           LLVM_DEBUG(dbgs()
                      << "MORPH LEAF: " << *Op << " (" << Weight << ") TO ");
-          BO = LowerNegateToMultiply(BO);
-          LLVM_DEBUG(dbgs() << *BO << '\n');
-          Worklist.push_back(std::make_pair(BO, Weight));
+          Tmp = LowerNegateToMultiply(Tmp);
+          LLVM_DEBUG(dbgs() << *Tmp << '\n');
+          Worklist.push_back(std::make_pair(Tmp, Weight));
           Changed = true;
           continue;
         }
 
       // Failed to morph into an expression of the right type.  This really is
       // a leaf.
       LLVM_DEBUG(dbgs() << "ADD LEAF: " << *Op << " (" << Weight << ")\n");
       assert(!isReassociableOp(Op, Opcode) && "Value was morphed?");
Instruction *ReassociatePass::canonicalizeNegConstExpr(Instruction *I) {
   // Must have one constant operand.
   if (!CF)
     return nullptr;
 
   // Must be a negative ConstantFP.
   if (!CF->isNegative())
     return nullptr;
 
   // 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;
 
   unsigned UserOpcode = User->getOpcode();
   if (UserOpcode != Instruction::FAdd && UserOpcode != Instruction::FSub)
     return nullptr;
 
   // Subtraction is not commutative. Explicitly, the following transform is
   // not valid: (-Constant * y) - x  -> x + (Constant * y)
   if (!User->isCommutative() && User->getOperand(1) != I)
     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))
     return nullptr;
 
Instruction *ReassociatePass::canonicalizeNegConstExpr(Instruction *I) {
   MadeChange = true;
   return NI;
 }
 
 /// 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<BinaryOperator>(I))
+  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) ||
if (ShouldBreakUpSubtract(I)) {
           if (BinaryOperator *Tmp = dyn_cast<BinaryOperator>(U))
             RedoInsts.insert(Tmp);
         }
         RedoInsts.insert(I);
         MadeChange = true;
         I = NI;
       }
     }
-  } else if (I->getOpcode() == Instruction::FSub) {
+  } else if (I->getOpcode() == Instruction::FNeg ||
+             I->getOpcode() == Instruction::FSub) {
     if (ShouldBreakUpSubtract(I)) {
       Instruction *NI = BreakUpSubtract(I, RedoInsts);
       RedoInsts.insert(I);
       MadeChange = true;
       I = NI;
     } else if (match(I, m_FNeg(m_Value()))) {
       // Otherwise, this is a negation.  See if the operand is a multiply tree
       // and if this is not an inner node of a multiply tree.
-      if (isReassociableOp(I->getOperand(1), Instruction::FMul) &&
+      Value *Op = isa<BinaryOperator>(I) ? I->getOperand(1) :
+                                           I->getOperand(0);
+      if (isReassociableOp(Op, Instruction::FMul) &&
           (!I->hasOneUse() ||
            !isReassociableOp(I->user_back(), Instruction::FMul))) {
         // If the negate was simplified, revisit the users to see if we can
         // reassociate further.
         Instruction *NI = LowerNegateToMultiply(I);
         for (User *U : NI->users()) {
           if (BinaryOperator *Tmp = dyn_cast<BinaryOperator>(U))
             RedoInsts.insert(Tmp);

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

 ;
   %d = fmul fast float %z, 4.000000e+01
   %c = fsub fast float 0.000000e+00, %d
   %e = fmul fast float %a, %c
   %f = fsub fast float 0.000000e+00, %e
   ret float %f
 }
 
-; FIXME: This reassociation is not working.
 define float @test18_unary_fneg(float %a, float %b, float %z) {
 ; CHECK-LABEL: @test18_unary_fneg(
-; CHECK-NEXT:    [[C:%.*]] = fmul fast float [[Z:%.*]], -4.000000e+01
-; CHECK-NEXT:    [[E:%.*]] = fmul fast float [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[F:%.*]] = fneg fast float [[E]]
+; CHECK-NEXT:    [[E:%.*]] = fmul fast float [[A:%.*]], 4.000000e+01
+; CHECK-NEXT:    [[F:%.*]] = fmul fast float [[E]], [[Z:%.*]]
 ; CHECK-NEXT:    ret float [[F]]
 ;
   %d = fmul fast float %z, 4.000000e+01
   %c = fneg fast float %d
   %e = fmul fast float %a, %c
   %f = fneg fast float %e
   ret float %f
 }
 
 define float @test18_reassoc(float %a, float %b, float %z) {
 ; CHECK-LABEL: @test18_reassoc(
 ; CHECK-NEXT:    [[D:%.*]] = fmul reassoc float [[Z:%.*]], 4.000000e+01
 ; CHECK-NEXT:    [[C:%.*]] = fsub reassoc float 0.000000e+00, [[D]]
 ; CHECK-NEXT:    [[E:%.*]] = fmul reassoc float [[C]], [[A:%.*]]
 ; CHECK-NEXT:    [[F:%.*]] = fsub reassoc float 0.000000e+00, [[E]]
 ; CHECK-NEXT:    ret float [[F]]
 ;
   %d = fmul reassoc float %z, 4.000000e+01
   %c = fsub reassoc float 0.000000e+00, %d
   %e = fmul reassoc float %a, %c
   %f = fsub reassoc float 0.000000e+00, %e
   ret float %f
 }
 
+; It is not safe to reassociate unary fneg without nnan.
+define float @test18_reassoc_unary_fneg(float %a, float %b, float %z) {
+; CHECK-LABEL: @test18_reassoc_unary_fneg(
+; CHECK-NEXT:    [[C:%.*]] = fmul reassoc float [[Z:%.*]], -4.000000e+01
+; CHECK-NEXT:    [[E:%.*]] = fmul reassoc float [[C]], [[A:%.*]]
+; CHECK-NEXT:    [[F:%.*]] = fneg reassoc float [[E]]
+; CHECK-NEXT:    ret float [[F]]
+;
+  %d = fmul reassoc float %z, 4.000000e+01
+  %c = fneg reassoc float %d
+  %e = fmul reassoc float %a, %c
+  %f = fneg reassoc float %e
+  ret float %f
+}
+
 ; With sub reassociation, constant folding can eliminate the 12 and -12 constants.
 define float @test19(float %A, float %B) {
 ; CHECK-LABEL: @test19(
 ; CHECK-NEXT:    [[Z:%.*]] = fsub fast float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret float [[Z]]
 ;
   %X = fadd fast float -1.200000e+01, %A
   %Y = fsub fast float %X, %B