[NaryReassociate] Detect deleted instr with WeakTrackingVH

[Ka-Ka]

Summary

If NaryReassociate succeed it will, when replacing the old instruction
with the new instruction, also recursively delete trivially
dead instructions from the old instruction. However, if the input to the
NaryReassociate pass contain dead code it is not save to recursively
delete trivially deadinstructions as it might lead to deleting the newly
created instruction.

This patch will fix the problem by using WeakTrackingVH to detect this
rare case, when the newly created instruction is dead, and it will then
restart the basic block iteration from the beginning.

This fixes pr37539

[tra]

@sanjoy is more familiar with this, so I've asked him to take a look.

test/Transforms/NaryReassociate/pr37539.ll

9 ↗

(On Diff #147779)

You may want to replace it with CHECK: [[BB1]]
Same for BB7 below.

[sanjoy]

lib/Transforms/Scalar/NaryReassociate.cpp

243 ↗

(On Diff #147779)

You probably want WeakVH instead of WeakTrackingVH here. However, did you consider lazily deleting &*I instead of doing them in this loop? You could keep an std::vector of WeakVHs that are pending delete and delete them after leaving this loop.

[Ka-Ka]

The reason for me to use WeakTrackingVH instead of WeakVH from the beginning was only that it was used elsewhere in the file. However as you point out WeakVH should be fine as RAUW is not used in RecursivelyDeleteTriviallyDeadInstructions(). I adjust the code to use WeakVH.

I did considered using the lazy approach. I actually tried it out, but it seems like the algorithm used here actually require RecursivelyDeleteTriviallyDeadInstructions to be used in the loop. I end up with infinite loops when trying the lazy approach. As I'm not really familiar with the the algorithm used, I instead made this minimal change to fix the problem I saw in pr37539.

I updated the testcase according to what was suggested in the review.

[sanjoy]

In D47139#1109102, @Ka-Ka wrote:

I end up with infinite loops when trying the lazy approach. As I'm not really familiar with the the algorithm used, I instead made this minimal change to fix the problem I saw in pr37539.

I see. However, the current patch is also risky in the same way (in that it looks like it may lead to infinite loops), but I don't know the algorithm here either. Unless the current patch is clearly not going to introduce infinite loops in your understanding, I'd suggest taking a closer look at making the lazy deletion work, or have some other scheme of avoiding the reset-to-beginning behavior.

lib/Transforms/Scalar/NaryReassociate.cpp

251 ↗

(On Diff #148166)

This bit me is worrying me somewhat -- can this lead to an infinite loop (where we reassociate from A to B then back)?

[Ka-Ka]

lib/Transforms/Scalar/NaryReassociate.cpp

251 ↗

(On Diff #148166)

I agree that restarting the iteration from BB->begin() is kind of ugly, but it will not lead to a infinite loop. The reason why is that RecursivelyDeleteTriviallyDeadInstructions() is starting deleting from 'I' that is a part of BB (as it looked from the beginning). We end up in this if clause if we, when recursively deleting, end up deleting 'NewI' (the instruction that should replace 'I'). However, as at least 'I' and 'NewI' was deleted, the basic block BB have always shrunk when restarting the iteration from BB-begin().

[sanjoy]

lgtm

lib/Transforms/Scalar/NaryReassociate.cpp

251 ↗

(On Diff #148166)

SGTM.

llvm/trunk/lib/Transforms/Scalar/NaryReassociate.cpp

for (const auto Node : depth_first(DT)) {
     BasicBlock *BB = Node->getBlock();
     for (auto I = BB->begin(); I != BB->end(); ++I) {
       if (SE->isSCEVable(I->getType()) && isPotentiallyNaryReassociable(&*I)) {
         const SCEV *OldSCEV = SE->getSCEV(&*I);
         if (Instruction *NewI = tryReassociate(&*I)) {
           Changed = true;
           SE->forgetValue(&*I);
           I->replaceAllUsesWith(NewI);
-          // If SeenExprs constains I's WeakTrackingVH, that entry will be
-          // replaced with
-          // nullptr.
+          WeakVH NewIExist = NewI;
+          // If SeenExprs/NewIExist contains I's WeakTrackingVH/WeakVH, that
+          // entry will be replaced with nullptr if deleted.
           RecursivelyDeleteTriviallyDeadInstructions(&*I, TLI);
+          if (!NewIExist) {
+            // Rare occation where the new instruction (NewI) have been removed,
+            // probably due to parts of the input code was dead from the
+            // beginning, reset the iterator and start over from the beginning
+            I = BB->begin();
+            continue;
+          }
           I = NewI->getIterator();
         }
         // Add the rewritten instruction to SeenExprs; the original instruction
         // is deleted.
         const SCEV *NewSCEV = SE->getSCEV(&*I);
         SeenExprs[NewSCEV].push_back(WeakTrackingVH(&*I));
         // Ideally, NewSCEV should equal OldSCEV because tryReassociate(I)
         // is equivalent to I. However, ScalarEvolution::getSCEV may

llvm/trunk/test/Transforms/NaryReassociate/pr37539.ll

+; RUN: opt < %s -nary-reassociate -S -o - | FileCheck %s
+
+; The test check that compilation does not segv (see pr37539).
+
+define void @f1() {
+; CHECK-LABEL: @f1(
+; CHECK-NEXT:    br label %[[BB1:.*]]
+; CHECK:         [[BB1]]
+; CHECK-NEXT:    [[P1:%.*]] = phi i16 [ 0, [[TMP0:%.*]] ], [ [[A1:%.*]], %[[BB1]] ]
+; CHECK-NEXT:    [[SCEVGEP_OFFS:%.*]] = add i16 2, 0
+; CHECK-NEXT:    [[A1]] = add i16 [[P1]], [[SCEVGEP_OFFS]]
+; CHECK-NEXT:    br i1 false, label %[[BB1]], label %[[BB7:.*]]
+; CHECK:         [[BB7]]
+; CHECK-NEXT:    ret void
+;
+  br label %bb1
+
+bb1:
+  %p1 = phi i16 [ 0, %0 ], [ %a1, %bb1 ]
+  %p2 = phi i16 [ 0, %0 ], [ %a2, %bb1 ]
+  %scevgep.offs = add i16 2, 0
+  %a1 = add i16 %p1, %scevgep.offs
+  %scevgep.offs5 = add i16 2, 0
+  %a2 = add i16 %p2, %scevgep.offs5
+  br i1 false, label %bb1, label %bb7
+
+bb7:
+  ret void
+}