[Reassociate]: Add intermediate subtract instructions created while negating to be redone later for more reassociate opportunities

[aditya_nandakumar]

Summary

This is tackling the same issue as in http://reviews.llvm.org/D12096. Reassociate is currently unable to simplify expressions such as (2 * b - (5 * a - 3 * b))
As David Majnemer pointed out, running reassociate twice did simplify the same.
Redoing the intermediate instructions created while breaking up a subtract (Negating) can open up more opportunities for reassociation and in this case simplifies the above expression to 5 * (b - a)

[majnemer]

This approach looks reasonable to me but I'd appreciate it if @dberlin or @chandlerc could take a look.

[mcrosier]

Thanks for working on this, Aditya. I tend to agree with David; I much prefer this solution over the InstCombine equivalent. I added a few minor nits, but overall this looks good.

lib/Transforms/Scalar/Reassociate.cpp

886–890

Perhaps,

/// Also add intermediate instructions to the redo list that are modified while pushing the negates through adds. These will be revisited to see if additional opportunities have been exposed.

927

open up -> expose

2110

Perhaps something like:

// If the negate was simplified, revisit the users to see if we can reassociate further.

2133

Perhaps something like:

// If the negate was simplified, revisit the users to see if we can reassociate further.

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

2 ↗

(On Diff #33149)

Please use the CHECK-LABEL directive.

17 ↗

(On Diff #33149)

CHECK-LABEL:

[aditya_nandakumar]

Thanks Chad. I will fix the comments shortly.
I think I might have found another convergence issue with reassociate. I expect when the pass finishes, running reassociate again should not make any changes (the output should already be in canonicalized form - please correct me if this is not a valid expectation). It currently takes three runs of reassociate for the output to converge while running secondary.ll (above change). Should this also be tackled in this change?

[mcrosier]

In D12345#233382, @aditya_nandakumar wrote:

I expect when the pass finishes, running reassociate again should not make any changes (the output should already be in canonicalized form - please correct me if this is not a valid expectation).

I think this should be the goal, but, as you're finding out, this isn't reality. IIRC, a similar question was asked and I believe David provided a similar comment. The approach you're taking seems to be moving us closer and that's a good thing. We just need to make sure we're not going overboard; we should only revisit things that have changed and only when that change is likely to expose other opportunities.

[aditya_nandakumar]

I see. I'll try to see what it takes for the above case to converge in one iteration.
The reason I asked is because I see reduction in instruction count (assembly) in several tests when I change the pass pipeline to have 2 reassociates(consecutive) vs just one. I will try and narrow down the patterns/cases which the second reassociate is exposing and/or cases which instcombine is missing.

[• dberlin]

First, you can get it to converge in O(size of the largest SCC of the
expressions being evaluated). Right now, reassociate does not look
through phi nodes, so that size will be 1 :)
Thus, it is possible to converge in one iteration with the right ordering.

Second, rather than spend lots of time on that, i would suggest other
approaches, Jingyu recently suggested a global reassociation algorithm
(https://docs.google.com/document/d/1momWzKFf4D6h8H3YlfgKQ3qeZy5ayvMRh6yR-Xn2hUE/edit#heading=h.pc7256itmioz)

(These are extensions of the existing n-ary reassociate)

This is likely a much better approach than trying to make the local
reassociation pass that reprocess things repeatedly, or even once,
because the *output* will be better :)

In particular,
A. I expect what is there now will not fixpoint in all cases, you'd
have to fix some things.
B. We already know the heuristics the local reassociation uses are
not only "bad for CSE" in a lot of cases, we know they are optimally
bad in a lot of cases

(IE it will transform things into the least canonical form).

For example:

; foo(a + c);
; foo((a + (b + c));

Reassociate on both:

RAIn: add i32 [ %a, #3] [ %c, #5]
RAOut: add i32 [ %c, #5] [ %a, #3]

and
for the second:
RAIn: add i32 [ %a, #3] [ %b, #4] [ %c, #5]
RAOut: add i32 [ %c, #5] [ %b, #4] [ %a, #3]

(IE c+ a, (c + b) + a)

The longer the expression, the worse it gets.

It is not possible to fix this without a global view of the
expressions, because you need to know "how i i pair the expressions
the last time i saw them" so you can pair them the same way.

Local reassociate, being a local algorithm, only has info about the
current expression chain, and thus, can't do something like this.

TL; DR While this patch seems great, doing a lot of work on local
reassociate is probably a mistake. Even if you get it to converge in
one iteration (which should be possible given processing), it'll still
give not great results in a lot of cases.

This was also all discussed a few times on the mailing list, if you
look back over threads mentioning reassociate.

[aditya_nandakumar]

Thanks Daniel. I definitely missed that conversation on the mailing list and I see the drawbacks of the local reassociate. I'll try seeing what little needs to be done to converge in the couple cases that I have (one above) and a superficial look at why the second reassociate improves codegen.
Is there already an implementation for global reassociate?

[resistor]

Ping? Was there any further feedback on this? We're seeing pretty horrible regressions caused by this.

[• dberlin]

I'm confused ;-)

The last status i saw was: "I'll try seeing what little needs to be done to
converge in the couple cases that I have (one above) and a superficial look
at why the second reassociate improves codegen."

I saw no update on that ;-)

and
"Is there already an implementation for global reassociate?"

Which i missed.

The answer to this is yes". N-Ary reassociate is already in tree, and
making it "better" shouldn't be that hard (if it turns out to be hard,
great, let's hack up local reassociate if we have to)

[resistor]

In D12345#288471, @dberlin wrote:

The last status i saw was: "I'll try seeing what little needs to be done to
converge in the couple cases that I have (one above) and a superficial look
at why the second reassociate improves codegen."

I saw no update on that ;-)

Would it be reasonable to stage that investigation? AFAICT the changes already proposed (with Chad's comments incorporated) are a strict improvement, and I at least am seeing pretty severe performance regressions from their absence. Would you be alright with going ahead and landing those?

and
"Is there already an implementation for global reassociate?"

Which i missed.

The answer to this is yes". N-Ary reassociate is already in tree, and
making it "better" shouldn't be that hard (if it turns out to be hard,
great, let's hack up local reassociate if we have to)

For my use case, at least, N-ary reassociation is not really appropriate as I also heavily depend on reassociation of floating point arithmetic. So, I'm stuck with local reassociation, and the problem described here is making today's LLVM integer factors worse than last year's for me.

[aditya_nandakumar]

Thanks Owen. Sorry about not updating this. This patch caused some regressions on some tests and I hadn't fully figured out/isolated the regression.

[hfinkel]

In D12345#301762, @aditya_nandakumar wrote:

Thanks Owen. Sorry about not updating this. This patch caused some regressions on some tests and I hadn't fully figured out/isolated the regression.

What kinds of regressions? Can you replicate these by running Reassociate twice in an otherwise-standard pipeline? We really should get this figured out.

Danny, are you proposing that we extend N-ary reassociation to work on floating-point values?

[aditya_nandakumar]

There were both improvements in instruction count as well as reduction with this patch on our internal test suite.

[aditya_nandakumar]

Modifying our pass pipeline to do reassociate twice resulted in some differences in Instruction count. On investigating why the second reassociate made a difference, I found that sometimes, when we revisit instructions, valid instruction tree roots don't get simplified (for eg factorize) when they get revisited before dead instructions as there are additional uses(false).
This patch tries to erase dead instructions before we try and redo the instructions. This improves codegen slightly (lesser instruction count) and takes Reassociate pass closer to being Idempotent.

[mcrosier]

lib/Transforms/Scalar/Reassociate.cpp

613

I assume this condition was removed because it will always be true, correct? If so, please commit this in isolation.

1931

How about:

Remove dead instructions and if any operands are trivially dead add them to
Insts so they will be removed as well.

1934

Ins -> Insts

1936

Can we use a for loop to loop over all the Instruction operands, rather than pushing/poping each operand onto/off of a SetVector?

2277

Please add a period. Comments should be written with proper capitalization, punctuation, etc.

2279

How about something like:

Iterate over all instructions to be reevaluated and remove trivially dead
instructions. If any operand of the trivially dead instruction becomes
dead mark it for deletion as well. Continue this process until all trivially
dead instructions have been removed.

2291

Please add a period.

2295

Please don't add extra curly brackets.

[aditya_nandakumar]

lib/Transforms/Scalar/Reassociate.cpp

613

Yes - I'll remove it and commit it separately

[aditya_nandakumar]

Updated based on feedback.

[mcrosier]

LGTM once the minor nits have been fixed.

lib/Transforms/Scalar/Reassociate.cpp

186

To conform to the surrounding coding style, would you mind adding argument names?

test/Transforms/Reassociate/factorize-again.ll

2

You can probably drop this comment.

4

Please use a CHECK-LABEL directive.

27

Drop comment

28

Remove dead "#0"

[aditya_nandakumar]

Committed in r256773.

[mcrosier]

Aditya,
Once committed (r256773) please be sure to close the Phabricator review.

Chad

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 RecursivelyEraseDeadInsts(Instruction *,
+                                   SetVector<AssertingVH<Instruction>> &);
     void OptimizeInst(Instruction *I);
     Instruction *canonicalizeNegConstExpr(Instruction *I);
   };
 }
 
 XorOpnd::XorOpnd(Value *V) {
   assert(!isa<ConstantInt>(V) && "No ConstantInt");
   OrigVal = V;
for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx) { // Visit operands.
           // This value has uses not accounted for by the expression, so it is
           // not safe to modify.  Mark it as being a leaf.
           DEBUG(dbgs() << "ADD USES LEAF: " << *Op << " (" << Weight << ")\n");
           LeafOrder.push_back(Op);
           Leaves[Op] = Weight;
           continue;
         }
         // No uses outside the expression, try morphing it.
       } else if (It != Leaves.end()) {
         // Already in the leaf map.
         assert(Visited.count(Op) && "In leaf map but not visited!");
 
         // Update the number of paths to the leaf.
         IncorporateWeight(It->second, Weight, Opcode);
 
 #if 0   // TODO: Re-enable once PR13021 is fixed.
         // The leaf already has one use from inside the expression.  As we want
void Reassociate::RewriteExprTree(BinaryOperator *I,
   for (unsigned i = 0, e = NodesToRewrite.size(); i != e; ++i)
     RedoInsts.insert(NodesToRewrite[i]);
 }
 
 /// Insert instructions before the instruction pointed to by BI,
 /// that computes the negative version of the value specified.  The negative
 /// version of the value is returned, and BI is left pointing at the instruction
 /// that should be processed next by the reassociation pass.
 /// Also add intermediate instructions to the redo list that are modified while
 /// pushing the negates through adds.  These will be revisited to see if
 /// additional opportunities have been exposed.
 static Value *NegateValue(Value *V, Instruction *BI,
                           SetVector<AssertingVH<Instruction>> &ToRedo) {
   if (Constant *C = dyn_cast<Constant>(V)) {
     if (C->getType()->isFPOrFPVectorTy()) {
       return ConstantExpr::getFNeg(C);
     }
     return ConstantExpr::getNeg(C);
   }
 
 
if (BinaryOperator *I =
     // not dominate the old add instruction in general.  By moving it, we are
     // assured that the neg instructions we just inserted dominate the
     // instruction we are about to insert after them.
     //
     I->moveBefore(BI);
     I->setName(I->getName()+".neg");
 
     // Add the intermediate negates to the redo list as processing them later
     // could expose more reassociating opportunities.
     ToRedo.insert(I);
     return I;
   }
 
   // Okay, we need to materialize a negated version of V with an instruction.
   // Scan the use lists of V to see if we have one already.
   for (User *U : V->users()) {
     if (!BinaryOperator::isNeg(U) && !BinaryOperator::isFNeg(U))
case Instruction::FMul:
     break;
   }
 
   if (Ops.size() != NumOps)
     return OptimizeExpression(I, Ops);
   return nullptr;
 }
 
+// Remove dead instructions and if any operands are trivially dead add them to
+// Insts so they will be removed as well.
+void Reassociate::RecursivelyEraseDeadInsts(
+    Instruction *I, SetVector<AssertingVH<Instruction>> &Insts) {
+  assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
+  SmallVector<Value *, 4> Ops(I->op_begin(), I->op_end());
+  ValueRankMap.erase(I);
+  Insts.remove(I);
+  RedoInsts.remove(I);
+  I->eraseFromParent();
+  for (auto Op : Ops)
+    if (Instruction *OpInst = dyn_cast<Instruction>(Op))
+      if (OpInst->use_empty())
+        Insts.insert(OpInst);
+}
+
 /// Zap the given instruction, adding interesting operands to the work list.
 void Reassociate::EraseInst(Instruction *I) {
   assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
   SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
   // Erase the dead instruction.
   ValueRankMap.erase(I);
   RedoInsts.remove(I);
   I->eraseFromParent();
if (ShouldBreakUpSubtract(I)) {
       I = NI;
     } else if (BinaryOperator::isNeg(I)) {
       // 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::Mul) &&
           (!I->hasOneUse() ||
            !isReassociableOp(I->user_back(), Instruction::Mul))) {
         Instruction *NI = LowerNegateToMultiply(I);
         // If the negate was simplified, revisit the users to see if we can
         // reassociate further.
         for (User *U : NI->users()) {
           if (BinaryOperator *Tmp = dyn_cast<BinaryOperator>(U))
             RedoInsts.insert(Tmp);
         }
         RedoInsts.insert(I);
         MadeChange = true;
         I = NI;
       }
     }
   } else if (I->getOpcode() == Instruction::FSub) {
     if (ShouldBreakUpSubtract(I)) {
       Instruction *NI = BreakUpSubtract(I, RedoInsts);
       RedoInsts.insert(I);
       MadeChange = true;
       I = NI;
     } else if (BinaryOperator::isFNeg(I)) {
       // 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) &&
           (!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);
         }
         RedoInsts.insert(I);
         MadeChange = true;
for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; )
       if (isInstructionTriviallyDead(&*II)) {
         EraseInst(&*II++);
       } else {
         OptimizeInst(&*II);
         assert(II->getParent() == BI && "Moved to a different block!");
         ++II;
       }
 
-    // If this produced extra instructions to optimize, handle them now.
+    // Make a copy of all the instructions to be redone so we can remove dead
+    // instructions.
+    SetVector<AssertingVH<Instruction>> ToRedo(RedoInsts);
+    // Iterate over all instructions to be reevaluated and remove trivially dead
+    // instructions. If any operand of the trivially dead instruction becomes
+    // dead mark it for deletion as well. Continue this process until all
+    // trivially dead instructions have been removed.
+    while (!ToRedo.empty()) {
+      Instruction *I = ToRedo.pop_back_val();
+      if (isInstructionTriviallyDead(I))
+        RecursivelyEraseDeadInsts(I, ToRedo);
+    }
+
+    // Now that we have removed dead instructions, we can reoptimize the
+    // remaining instructions.
     while (!RedoInsts.empty()) {
       Instruction *I = RedoInsts.pop_back_val();
       if (isInstructionTriviallyDead(I))
         EraseInst(I);
       else
         OptimizeInst(I);
     }
   }
 
   // We are done with the rank map.
   RankMap.clear();
   ValueRankMap.clear();
 
   return MadeChange;
 }

test/Transforms/Reassociate/factorize-again.ll

+; RUN: opt -S -reassociate < %s | FileCheck %s
+; ModuleID = 'bugpoint-reduced-simplified.bc'
+
+; CHECK: main
+; CHECK: %2 = fsub
+; CHECK: %3 = fsub
+; CHECK: fadd fast float %3, %2
+define void @main(float, float) {
+wrapper_entry:
+  %2 = fsub float undef, %0
+  %3 = fsub float undef, %1
+  %4 = call float @llvm.rsqrt.f32(float undef)
+  %5 = fmul fast float undef, %4
+  %6 = fmul fast float %2, %4
+  %7 = fmul fast float %3, %4
+  %8 = fmul fast float %5, undef
+  %9 = fmul fast float %6, undef
+  %10 = fmul fast float %7, undef
+  %11 = fadd fast float %8, %9
+  %12 = fadd fast float %11, %10
+  %13 = call float @foo2(float %12, float 0.000000e+00)
+  %mul36 = fmul fast float %13, 1.500000e+00
+  call void @foo1(i32 4, float %mul36)
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @foo1(i32, float) #0
+
+; Function Attrs: nounwind readnone
+declare float @foo2(float, float) #1
+
+; Function Attrs: nounwind readnone
+declare float @llvm.rsqrt.f32(float) #1
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { nounwind readnone }
+

test/Transforms/Reassociate/secondary.ll

 ; RUN: opt -S -reassociate < %s | FileCheck %s
 ; rdar://9167457
 
 ; Reassociate shouldn't break this testcase involving a secondary
 ; reassociation.
 
 ; CHECK:     define
 ; CHECK-NOT: undef
-; CHECK:     %factor = mul i32 %tmp3.neg, 2
+; CHECK:     %factor = mul i32 %tmp3, -2
 ; CHECK-NOT: undef
 ; CHECK:     }
 
 define void @x0f2f640ab6718391b59ce96d9fdeda54(i32 %arg, i32 %arg1, i32 %arg2, i32* %.out) nounwind {
 _:
   %tmp = sub i32 %arg, %arg1
   %tmp3 = mul i32 %tmp, -1268345047
   %tmp4 = add i32 %tmp3, 2014710503
   %tmp5 = add i32 %tmp3, -1048397418
   %tmp6 = sub i32 %tmp4, %tmp5
   %tmp7 = sub i32 -2014710503, %tmp3
   %tmp8 = add i32 %tmp6, %tmp7
   store i32 %tmp8, i32* %.out
   ret void
 }