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

2276

Please insert a space between the if and the parenthesis.

test/Transforms/Reassociate/crash2.ll

4–19

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

1954

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

1955

Please format this a little nicer.

2266

Why is topological in quotes?

2272–2284

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

2278–2281

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

1954

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.

2266

Because we don't have a DAG.

2272–2284

I don't see how would it be possible?

2278–2281

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

2259

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

2260

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

2275

No need for extra curly brackets.

2284

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

2261

ben -> been ?

2281–2282

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

1 ↗

(On Diff #45013)

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

 /// 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) {
   RewriteExprTree(I, Ops);
 }
 
 bool Reassociate::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
   // Calculate the rank map for F
   BuildRankMap(F);
 
   MadeChange = false;
   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
     // 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; ) {
       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.
       while (!RedoInsts.empty()) {
         Instruction *I = RedoInsts.pop_back_val();
+        if(I==II)
+          // Will be processed next iteration on the basic block
+          continue;
         if (isInstructionTriviallyDead(I))
           EraseInst(I);
         else
           OptimizeInst(I);
       }
     }
+  }
 
   // We are done with the rank map.
   RankMap.clear();
   ValueRankMap.clear();
 
   return MadeChange;
 }

test/Transforms/Reassociate/crash2.ll

+; RUN: opt -reassociate -disable-output < %s
+; ModuleID = 'bugpoint-reduced-simplified.bc'
+
+define i32 @foo() {
+wrapper_entry:
+  %0 = udiv i32 1, undef
+  %1 = mul i32 undef, %0
+  %2 = add i32 %1, undef
+  %3 = add i32 %2, 1
+  %4 = add i32 %3, undef
+  %5 = add i32 %3, 1
+  %6 = mul i32 %4, -2
+  %7 = add i32 %5, %6
+  %8 = add i32 %6, %7
+  ; this instruction is intentionally dead
+  %9 = add i32 %8, 1
+  %10 = add i32 undef, %8
+  ret i32 %10
+}