[PR28367][Reassociation] Avoid iterator invalidation when negating value.

[mcrosier]

Summary

When trying to negate a value, V, we try to avoid materializing the negated value by scanning the use list of V to see if we already have one. If we do find a negated version and that version is in the block we're currently optimizing, moving that instruction may invalidate our iterator.

Example:

define void @fn1(i32 %a, i1 %c, i32* %ptr)  {
entry:
  br label %for.cond

for.cond:
  %d.0 = phi i32 [ 1, %entry ], [ 2, %for.body ]
  br i1 %c, label %for.end, label %for.body

for.body:
  %sub1 = sub i32 %a, %d.0
  %dead1 = add i32 %sub1, 1
  %dead2 = mul i32 %dead1, 3
  %dead3 = mul i32 %dead2, %sub1
  %sub2 = sub nsw i32 0, %d.0
  store i32 %sub2, i32* %ptr, align 4
  br label %for.cond

for.end:
  ret void
}

The invalidation occurs as follows:

1. Assume we're optimizing %dead3, which is trivially dead.
2. The BB iterator is incremented (now pointing to %sub2) and EraseInst is called to delete %dead3.
3. When the %dead3 instruction is removed its operand %sub1 is added to the RedoInst list.
4. When %sub1 is reoptimized the ShouldBreakUpSubtract() function returns true and the BreakUpSubtract() function is called. This didn't happen the first time %sub1 was optimized because it had more than one use (i.e., %dead1 and %dead3).
5. The NegateValue() function then hoists the %sub2 (as it is the negated form of %d.0) instruction into the for.cond block invalidating the iterator and causing the assertion. Without the assert we would dereference an invalid iterator and segfault.

Please take a look,
Chad

[hans]

Eli: Do you have time to take a look at this? It's one of the last 3.9-blocking bugs.

[mcrosier]

FWIW, I looked at the code gen differences on AArch64 and found no changes in SPEC2000 and SPEC2006 and only 4 changes in the llvm-test-suite. Of those changes 3 of the 4 were net wins in terms of removed static instructions.

[efriedma]

I'm not really happy with this patch... you're basically disabling the CSE optimization for what seems like the most important case.

That said, I'm not sure the CSE optimization is actually necessary given the current state of reassociate. The "look for an existing negation" code was added in r92373 to fix test/Transforms/Reassociate/basictest.ll @test12... and that test apparently still passes with this patch. Maybe it would make sense to just delete the whole loop to look for an existing negate?

Another way to fix the iterator invalidation problem would be to revert r258830, I think.

FYI, this is basically my first time reading the reassociate code, so I might be missing something.

[mcrosier]

In D23464#517105, @efriedma wrote:

I'm not really happy with this patch... you're basically disabling the CSE optimization for what seems like the most important case.

I don't disagree, but I didn't find this to really matter in my testing (see my comments from a few minutes ago).

That said, I'm not sure the CSE optimization is actually necessary given the current state of reassociate. The "look for an existing negation" code was added in r92373 to fix test/Transforms/Reassociate/basictest.ll @test12... and that test apparently still passes with this patch. Maybe it would make sense to just delete the whole loop to look for an existing negate?

I tried that as well and I'm not opposed to this solution. However, that did cause 4 Reassociation lit tests to regress and it resulted in a bit more code gen changes (i.e., still no changes to SPEC, but I see about 10 changes in the llvm-test-suite).

Another way to fix the iterator invalidation problem would be to revert r258830, I think.

My gut tells me r258830 only exposed the problem and that it would still exist after a revert (but much less likely to happen). IIRC, @aditya_nandakumar and @resistor also indicated this commit was necessary to address a performance critical issue they were seeing.

FYI, this is basically my first time reading the reassociate code, so I might be missing something.

No problem; I appreciate the review.

[efriedma]

In D23464#517145, @mcrosier wrote:

My gut tells me r258830 only exposed the problem and that it would still exist after a revert (but much less likely to happen).

Without r258830, the only live basic block iterator points at the current instruction itself, which will never be moved. (A pointer to the instruction itself won't be invalidated by moving it.)

In terms of coming up with a safe patch to merge into 3.9, this seems like the right patch. I still think it's ugly. :)

---

On a sort of related note, it might be worth experimenting with the iteration order of Reassociate at some point... it's possible that it would improve the generated code to iterate backwards over basic blocks.

[mcrosier]

Neither Eli or I are particularly thrilled with this solution and Eli convinced me reverting r258830 would fix the regression. Therefore, I'm abandoning this change and have reverted r258830 in r278938.

[aditya_nandakumar]

Thanks Chad for reverting r258830. I apologize I didn’t see this email earlier.

This revert is causing some codegen regressions - I’ll look into this.

[tigerleapgorge]

In D23464#520974, @aditya_nandakumar wrote:

Thanks Chad for reverting r258830. I apologize I didn’t see this email earlier.

This revert is causing some codegen regressions - I’ll look into this.

Hello Aditya,

I came across a SLP vectorizer ICE bug related to this commit.
I opened a LLVM bug but could not add you into the CC list.
https://llvm.org/bugs/show_bug.cgi?id=30626

TLDR version on the history of this crash.

1. ICE started at commit r253240.
2. ICE went away at commit r258830.
3. ICE resurfaced when commit r258830 was reverted at r278938.
4. As of today, this ICE still exists.

I would greatly appreciate your insight.

Thank you.

lib/Transforms/Scalar/Reassociate.cpp

for (User *U : V->users()) {
     // non-instruction value) or right after the definition.  These negates will
     // be zapped by reassociate later, so we don't need much finesse here.
     BinaryOperator *TheNeg = cast<BinaryOperator>(U);
 
     // Verify that the negate is in this function, V might be a constant expr.
     if (TheNeg->getParent()->getParent() != BI->getParent()->getParent())
       continue;
 
+    // Don't move the negate if it's in the block we're currently optimizing as
+    // this may invalidate our iterator.
+    if (TheNeg->getParent() == BI->getParent())
+      continue;
+
     BasicBlock::iterator InsertPt;
     if (Instruction *InstInput = dyn_cast<Instruction>(V)) {
       if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) {
         InsertPt = II->getNormalDest()->begin();
       } else {
         InsertPt = ++InstInput->getIterator();
       }
       while (isa<PHINode>(InsertPt)) ++InsertPt;
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 ReassociatePass::EraseInst(Instruction *I) {
   assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
+  DEBUG(dbgs() << "Erasing dead inst: "; I->dump());
+
   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)

test/Transforms/Reassociate/invalid-iterator.ll

+; RUN: opt < %s -reassociate -die -S | FileCheck %s
+
+; PR28367
+; Check to make sure %sub2 isn't moved from for.body.  Doing so would invalidate
+; the iterator.
+
+; CHECK-LABEL: @fn1
+; CHECK: for.body:
+; CHECK-NEXT:   %sub2 = sub nsw i32 0, %d.0
+; CHECK-NEXT:   store i32 %sub2, i32* %ptr, align 4
+define void @fn1(i32 %a, i1 %c, i32* %ptr)  {
+entry:
+  br label %for.cond
+
+for.cond:
+  %d.0 = phi i32 [ 1, %entry ], [ 2, %for.body ]
+  br i1 %c, label %for.end, label %for.body
+
+for.body:
+  %sub1 = sub i32 %a, %d.0
+  %dead1 = add i32 %sub1, 1
+  %dead2 = mul i32 %dead1, 3
+  %dead3 = mul i32 %dead2, %sub1
+  %sub2 = sub nsw i32 0, %d.0
+  store i32 %sub2, i32* %ptr, align 4
+  br label %for.cond
+
+for.end:
+  ret void
+}