Reassociate: reprocess RedoInsts after each instruction

[aditya_nandakumar]

Summary

Previously the RedoInsts was processed at the end of the block.
However it was possible that it left behind some instructions that
were not canonicalized.
This should guarantee that any previous instruction in the basic
block is canonicalized before we process a new instruction.

[majnemer]

lib/Transforms/Scalar/Reassociate.cpp

2296

Please insert a space between the if and the parenthesis.

test/Transforms/Reassociate/crash2.ll

4–19 ↗

(On Diff #18219)

Your test has no CHECK lines, please consider adding some.

[mehdi_amini]

Taken comments into account: clang-format and CHECK line in the test.

[majnemer]

Why did the old approach fall down on these testcases?

[mehdi_amini]

Hi David,

Let’s consider:

%_0 = add i32 %in, 1
%_1 = mul i32 %in, -2
%_2 = add i32 %_0, %_1
%_3 = add i32 %_1, %_2
%_4 = add i32 %_3, 1
%_5 = add i32 %in, %_3
ret i32 %_5

Now when processing %3, the expression is:

"%1 + %in + 1 + %1”

and it is factorized to:

“%in + 1 + ( 2 * %1)”

the IR becomes:

%_0 = add i32 %in, 1
%_1 = mul i32 %in, -2
%factor = mul i32 %_1, 2
%_2 = add i32 %in, 1
%_3 = add i32 %_2, %factor
%_4 = add i32 %_3, 1
%_5 = add i32 %in, %_3
ret i32 %_5

And %factor was added to the RedoInsts list because we known it might not be canonicalized.
And indeed in this case it is 2*(%1*-2) which can be turned into -4*%1.

Let continue to %5, it will consider

%in + %in + 1 + %factor

It will try to factorize, and list for all of the operands the factors to find some in common.
When processing %factor, the list of factors is

%in * -2 * 2

However this contains two constant and is forbidden because it should have been folded earlier. Because RedoInsts was processed at the end of the block instead of at the end of a transformation this canonicalization would have happened later.

Does it makes sense?

Thanks.

[mehdi_amini]

ping :)

[mcrosier]

I still don't understand why this is the correct approach? Are we missing an optimization without your change?

[mehdi_amini]

Hi Chad,

No we are not missing an optimization without my approach, we are just hitting an assert...

I think it is the right thing to do anyway because I don't see the point of growing a long list of instructions to reprocess for later if you can do it now.

Mehdi

[mehdi_amini]

My fuzzer found a case where we hit this same assert with this patch but not without. So it seems I still have to work on it.... Hold on for the review.

[mehdi_amini]

I had to made significant changes, this is ready for review now!

[majnemer]

lib/Transforms/Scalar/Reassociate.cpp

1956

I think this comment needs to be expanded a bit. Why must we refrain from optimizing the PHI operands?

1957

Please format this a little nicer.

2284

Why is topological in quotes?

2292–2309

Instead of having both RedoInsts and Worklist, what if we had a single SetVector that held both?

2296–2299

This would probably be better as:

SmallSet<Instruction *, 8> Worklist(BI->begin(), BI->end());

[mehdi_amini]

Thanks for your comment. I'll update the patch soon. I found out that I could use the RankMap to simplify what I'm trying to achieve.
I also found another but where we end up with an instruction moved to a new block (and hit an assertion).

lib/Transforms/Scalar/Reassociate.cpp

1956

Because the operand might be locate in a block that wasn't already processed.
I'll relax that by allowing operands that are located in block already processed.

2284

Because we don't have a DAG.

2292–2309

I don't see how would it be possible?

2296–2299

That was my first intention, but it seems that SmallSet does not provide such constructor.

I also tried:

SmallSet<Instruction *, 8> Worklist;
Worklist.insert(BI->begin(), BI->end());

But was bitten by: "candidate function not viable: no known conversion from 'llvm::Instruction' to 'llvm::Instruction *' for 1st argument; take the address of the argument with &"

[mehdi_amini]

Improve the filtering of instructions to reprocess based on basic block rank.
Add a new "crashing" test case that triggered this bug.

[mehdi_amini]

Reuse the RPOT iterator with BuildRankMap() for efficiency purpose.

Note, this patch has been ran over the weekend on my fuzzer without any
new crash.

[mehdi_amini]

Clear the RedoInsts immediately, even when erasing an instruction.

[mehdi_amini]

FYI: Still 3 of these tests are crashing as of now (r253245).

[dexonsmith]

(Wow, this is from a while ago.)

If three of these tests are crashing, shouldn't we just commit the fix?
(Does it still apply?)

Chad, do you still have concerns? Is it about compile time or something
else?

[qcolombet]

Hi Mehdi,

Please consider merging the test files. They all have the same test line and as far as I know you are fixing the source of one crash, not eight.
Also please:

• Add check lines.
• Use opt -instnamer to get rid of the %[num] variables.

My 2c.

Thanks,
-Quentin

[mehdi_amini]

Only 3 test are still crashing now, but at the time I wrote the patch, I iterated on a fuzzer and these six tests (not eight) were stressing different patterns and different part of reassociate, so they're absolutely not redundant.

I'm not sure either what CHECK line to put for a compiler crash non-regression, there are multiple cases in the test suite like this where FileCheck is not involved.

[mehdi_amini]

(and the fact that 3 tests were fixed in the meantime shows that they're independent)

[aditya_nandakumar]

Chad, what needs to be done here?

[echristo]

What Quentin meant in his review was that you should concatenate all of the tests in a single file and run them that way, in general that's "accepted practice" for the project. I'm adding David as a reviewer as he's been doing that. Once you merge the testcases and David says ok, then we're good.

Thanks!

[mcrosier]

Sorry, this one fell completely off my radar.

Per Quentin/Eric, I would merge all the tests into a single file. Quentin's suggestion to use the instnamer seems fairly reasonable as well.

I'd like to hear David's comments before providing a LGTM as he has actually reviewed this patch in earnest.

I assume this should also be merged into the 3.8 branch, if we're actually crashing without this fix.

lib/Transforms/Scalar/Reassociate.cpp

2264

A "Topological" what? A "Topological" ranking... The sentences seems incomplete.

2265

were processed before -> have been processed. (Or something similar)

2293

No need for extra curly brackets.

2304

No need for extra curly brackets.

[aditya_nandakumar]

Updated based on feedback.

[aditya_nandakumar]

Ping?

[majnemer]

Sorry for the delay, I'll take a look today.

[majnemer]

lib/Transforms/Scalar/Reassociate.cpp

2265

ben -> been ?

2301–2302

Is it possible for I to equal II ? Removing this check doesn't seem to make any tests fail.

test/Transforms/Reassociate/prev_insts_canonicalized.ll

2

I'd follow the pattern used by the other tests:

; RUN: opt < %s -reassociate -S | FileCheck %s

This will ensure that the test's filename will not show up in the test's output.

[aditya_nandakumar]

Updated based on feedback

lib/Transforms/Scalar/Reassociate.cpp

public:
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       AU.addPreserved<GlobalsAAWrapperPass>();
     }
   private:
-    void BuildRankMap(Function &F);
+    void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
+
     unsigned getRank(Value *V);
     void canonicalizeOperands(Instruction *I);
     void ReassociateExpression(BinaryOperator *I);
     void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
     Value *OptimizeExpression(BinaryOperator *I,
                               SmallVectorImpl<ValueEntry> &Ops);
     Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops);
     Value *OptimizeXor(Instruction *I, SmallVectorImpl<ValueEntry> &Ops);
if (V->hasOneUse() && isa<Instruction>(V) &&
       (cast<Instruction>(V)->getOpcode() == Opcode1 ||
        cast<Instruction>(V)->getOpcode() == Opcode2) &&
       (!isa<FPMathOperator>(V) ||
        cast<Instruction>(V)->hasUnsafeAlgebra()))
     return cast<BinaryOperator>(V);
   return nullptr;
 }
 
-void Reassociate::BuildRankMap(Function &F) {
+void Reassociate::BuildRankMap(Function &F,
+                               ReversePostOrderTraversal<Function *> &RPOT) {
   unsigned i = 2;
 
   // Assign distinct ranks to function arguments.
   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
     ValueRankMap[&*I] = ++i;
     DEBUG(dbgs() << "Calculated Rank[" << I->getName() << "] = " << i << "\n");
   }
 
-  ReversePostOrderTraversal<Function*> RPOT(&F);
   for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
          E = RPOT.end(); I != E; ++I) {
     BasicBlock *BB = *I;
     unsigned BBRank = RankMap[BB] = ++i << 16;
 
     // Walk the basic block, adding precomputed ranks for any instructions that
     // we cannot move.  This ensures that the ranks for these instructions are
     // all different in the block.

 /// 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();
   // Optimize its operands.
   SmallPtrSet<Instruction *, 8> Visited; // Detect self-referential nodes.
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) {
       // If this is a node in an expression tree, climb to the expression root
       // and add that since that's where optimization actually happens.
       unsigned Opcode = Op->getOpcode();
       while (Op->hasOneUse() && Op->user_back()->getOpcode() == Opcode &&
              Visited.insert(Op).second)
         Op = Op->user_back();
void Reassociate::ReassociateExpression(BinaryOperator *I) {
   // the expression tree, removing any unneeded nodes.
   RewriteExprTree(I, Ops);
 }
 
 bool Reassociate::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
-  // Calculate the rank map for F
-  BuildRankMap(F);
+  // Reassociate needs for each instruction to have its operands already
+  // processed, so we first perform a RPOT of the basic blocks so that
+  // when we process a basic block, all its dominators have been processed
+  // before.
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  BuildRankMap(F, RPOT);
 
   MadeChange = false;
-  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
+  for (BasicBlock *BI : RPOT) {
+    // Use a worklist to keep track of which instructions have been processed
+    // (and which insts won't be optimized again) so when redoing insts,
+    // optimize insts rightaway which won't be processed later.
+    SmallSet<Instruction *, 8> Worklist;
+
+    // Insert all instructions in the BB
+    for (Instruction &I : *BI)
+      Worklist.insert(&I);
+
     // Optimize every instruction in the basic block.
-    for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; )
+    for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;) {
+      // This instruction has been processed.
+      Worklist.erase(&*II);
       if (isInstructionTriviallyDead(&*II)) {
         EraseInst(&*II++);
       } else {
         OptimizeInst(&*II);
         assert(II->getParent() == BI && "Moved to a different block!");
         ++II;
       }
 
-    // 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.
+      // If the above optimizations produced new instructions to optimize or
+      // made modifications which need to be redone, do them now if they won't
+      // be handled later.
       while (!RedoInsts.empty()) {
         Instruction *I = RedoInsts.pop_back_val();
+        // Process instructions that won't be processed later, either
+        // inside the block itself or in another basic block (based on rank),
+        // since these will be processed later.
+        if ((I->getParent() != BI || !Worklist.count(I)) &&
+            RankMap[I->getParent()] <= RankMap[BI]) {
           if (isInstructionTriviallyDead(I))
             EraseInst(I);
           else
             OptimizeInst(I);
         }
       }
+    }
+  }
 
   // We are done with the rank map.
   RankMap.clear();
   ValueRankMap.clear();
 
   return MadeChange;
 }

test/Transforms/Reassociate/prev_insts_canonicalized.ll

+; RUN: opt < %s -reassociate -S | FileCheck %s
+
+; These tests make sure that before processing insts
+; any previous instructions are already canonicalized.
+define i32 @foo(i32 %in) {
+; CHECK-LABEL: @foo
+; CHECK-NEXT: %factor = mul i32 %in, -4
+; CHECK-NEXT: %factor1 = mul i32 %in, 2
+; CHECK-NEXT: %_3 = add i32 %factor, 1
+; CHECK-NEXT: %_5 = add i32 %_3, %factor1
+; CHECK-NEXT: ret i32 %_5
+  %_0 = add i32 %in, 1
+  %_1 = mul i32 %in, -2
+  %_2 = add i32 %_0, %_1
+  %_3 = add i32 %_1, %_2
+  %_4 = add i32 %_3, 1
+  %_5 = add i32 %in, %_3
+  ret i32 %_5
+}
+
+; CHECK-LABEL: @foo1
+define void @foo1(float %in, i1 %cmp) {
+wrapper_entry:
+  br label %foo1
+
+for.body:
+  %0 = fadd float %in1, %in1
+  br label %foo1
+
+foo1:
+  %_0 = fmul fast float %in, -3.000000e+00
+  %_1 = fmul fast float %_0, 3.000000e+00
+  %in1 = fadd fast float -3.000000e+00, %_1
+  %in1use = fadd fast float %in1, %in1
+  br label %for.body
+
+
+}
+
+; CHECK-LABEL: @foo2
+define void @foo2(float %in, i1 %cmp) {
+wrapper_entry:
+  br label %for.body
+
+for.body:
+; If the operands of the phi are sheduled for processing before
+; foo1 is processed, the invariant of reassociate are not preserved
+  %unused = phi float [%in1, %foo1], [undef, %wrapper_entry]
+  br label %foo1
+
+foo1:
+  %_0 = fmul fast float %in, -3.000000e+00
+  %_1 = fmul fast float %_0, 3.000000e+00
+  %in1 = fadd fast float -3.000000e+00, %_1
+  %in1use = fadd fast float %in1, %in1
+  br label %for.body
+}

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

 ; RUN: opt < %s -reassociate -S | FileCheck %s
 ; CHECK-LABEL: faddsubAssoc1
-; CHECK: [[TMP1:%tmp.*]] = fmul fast half %a, 0xH4500
-; CHECK: [[TMP2:%tmp.*]] = fmul fast half %b, 0xH4500
-; CHECK: fsub fast half [[TMP2]], [[TMP1]]
+; CHECK: [[TMP1:%.*]] = fsub fast half 0xH8000, %a
+; CHECK: [[TMP2:%.*]] = fadd fast half %b, [[TMP1]]
+; CHECK: fmul fast half [[TMP2]], 0xH4500
 ; CHECK: ret
 ; Input is A op (B op C)
 define half @faddsubAssoc1(half %a, half %b) {
   %tmp1 = fmul fast half %b, 0xH4200 ; 3*b
   %tmp2 = fmul fast half %a, 0xH4500 ; 5*a
   %tmp3 = fmul fast half %b, 0xH4000 ; 2*b
   %tmp4 = fsub fast half %tmp2, %tmp1 ; 5 * a - 3 * b
   %tmp5 = fsub fast half %tmp3, %tmp4 ; 2 * b - ( 5 * a - 3 * b)

test/Transforms/Reassociate/xor_reassoc.ll

 ;  (x | c1) ^ (x & c1) = x ^ c1
 define i32 @xor_special2(i32 %x, i32 %y) {
   %or = or i32 %x, 123
   %xor = xor i32 %or, %y
   %and = and i32 %x, 123
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 ; CHECK-LABEL: @xor_special2(
-; CHECK: %xor = xor i32 %x, 123
-; CHECK: %xor1 = xor i32 %xor, %y
+; CHECK: %xor = xor i32 %y, 123
+; CHECK: %xor1 = xor i32 %xor, %x
 ; CHECK: ret i32 %xor1
 }
 
 ; (x | c1) ^ (x | c1) => 0
 define i32 @xor_special3(i32 %x) {
   %or = or i32 %x, 123
   %or1 = or i32 %x, 123
   %xor = xor i32 %or, %or1