Prevent RemoveDeadNodes from deleted already deleted node.

[niravd]

Summary

This prevents against assertion errors like PR32659 which occur from a
replacement deleting a node after it's been added to the list argument
of RemoveDeadNodes.

[spatel]

The code change seems safe, but the test doesn't fail with recent trunk (I tried r304685).

Is there still a way to expose the bug? If not, can we just assert that no deleted node can get this far?

[niravd]

Is there still a way to expose the bug?

I'm reasonably there's a sequence that could trigger the bug in some backend, but I don't think I can generate it. The failing test was dealing with a net of TokenFactors fusedin a single instruction which wasn't being simplified.

If not, can we just assert that no deleted node can get this far?

Unfortunately no. The original bug is that we're triggering on a deleted_node a bit further down in deallocation. the caller of the changed function is builds up a list of nodes to delete after having moved some of the the users of the added nodes' values. But it's possible that moving those values will cause a previously added node to be deleted. I could filter the node vector on the caller side and prune there, but that's just a un-loopfused version of this.

[spatel]

OK - please include the explanation in the commit message. LGTM.

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
 /// given list, and any nodes that become unreachable as a result.
 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
 
   // Process the worklist, deleting the nodes and adding their uses to the
   // worklist.
   while (!DeadNodes.empty()) {
     SDNode *N = DeadNodes.pop_back_val();
+    // Skip to next node if we've already managed to delete the node. This could
+    // happen if replacing a node causes a node previously added to the node to
+    // be deleted.
+    if (N->getOpcode() == ISD::DELETED_NODE)
+      continue;
 
     for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
       DUL->NodeDeleted(N, nullptr);
 
     // Take the node out of the appropriate CSE map.
     RemoveNodeFromCSEMaps(N);
 
     // Next, brutally remove the operand list.  This is safe to do, as there are

llvm/trunk/test/CodeGen/X86/pr32659.ll

+; RUN: llc -o - %s | FileCheck %s
+target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
+target triple = "i386-unknown-linux-gnu"
+
+@a = external global i32, align 4
+@d = external global i32*, align 4
+@k = external global i32**, align 4
+@j = external global i32***, align 4
+@h = external global i32, align 4
+@c = external global i32, align 4
+@i = external global i32, align 4
+@b = external global i32, align 4
+@f = external global i64, align 8
+@e = external global i64, align 8
+@g = external global i32, align 4
+
+; Function Attrs: norecurse nounwind optsize readnone
+declare i32 @fn1(i32 returned) #0
+
+
+; CHECK-LABEL: fn2
+; CHECK: calll putchar
+; CHECK: addl $1,
+; CHECK: adcl $0,
+; Function Attrs: nounwind optsize
+define void @fn2() #1 {
+entry:
+  %putchar = tail call i32 @putchar(i32 48)
+  %0 = load volatile i32, i32* @h, align 4
+  %1 = load i32, i32* @c, align 4, !tbaa !2
+  %2 = load i32***, i32**** @j, align 4
+  %3 = load i32**, i32*** %2, align 4
+  %4 = load i32*, i32** %3, align 4
+  %5 = load i32, i32* %4, align 4
+  %cmp = icmp sgt i32 %1, %5
+  %conv = zext i1 %cmp to i32
+  %6 = load i32, i32* @i, align 4
+  %cmp1 = icmp sgt i32 %6, %conv
+  %conv2 = zext i1 %cmp1 to i32
+  store i32 %conv2, i32* @b, align 4
+  %cmp3 = icmp sgt i32 %0, %conv2
+  %conv4 = zext i1 %cmp3 to i32
+  %7 = load i32, i32* @a, align 4
+  %or = xor i32 %7, %conv4
+  store i32 %or, i32* @a, align 4
+  %8 = load i32*, i32** @d, align 4
+  %9 = load i32, i32* %8, align 4
+  %conv6 = sext i32 %9 to i64
+  %10 = load i64, i64* @e, align 8
+  %and = and i64 %10, %conv6
+  store i64 %and, i64* @e, align 8
+  %11 = load i32, i32* @g, align 4
+  %dec = add nsw i32 %11, -1
+  store i32 %dec, i32* @g, align 4
+  %12 = load i64, i64* @f, align 8
+  %inc = add nsw i64 %12, 1
+  store i64 %inc, i64* @f, align 8
+  ret void
+}
+
+; Function Attrs: nounwind optsize
+declare i32 @main() #1
+
+; Function Attrs: nounwind
+declare i32 @putchar(i32) #2
+
+attributes #0 = { optsize readnone }
+attributes #1 = { optsize }
+attributes #2 = { nounwind }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"NumRegisterParameters", i32 0}
+!1 = !{!"clang version 5.0.0 (trunk 300074) (llvm/trunk 300078)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}
+!6 = !{!7, !7, i64 0}
+!7 = !{!"any pointer", !4, i64 0}
+!8 = !{!9, !9, i64 0}
+!9 = !{!"long long", !4, i64 0}