[DAG] Prevent Stale nodes from entering worklist

[niravd]

Summary

Add check that deleted nodes do not get added to worklist. This can
occur when a node's operand is simplified to an existing node.

This fixes PR32108.

[hfinkel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

140

What does "causes redundancies" mean?

[jyknight]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

140

I'd suggest to put an assert here instead, and put an if (opcode==ISD::DELETED_NODE) in the caller that requires it.

[niravd]

Move check to offending line and add assertion to AddToWorklist

[hfinkel]

LGTM

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

class DAGCombiner {
 
     /// Call the node-specific routine that folds each particular type of node.
     SDValue visit(SDNode *N);
 
   public:
     /// Add to the worklist making sure its instance is at the back (next to be
     /// processed.)
     void AddToWorklist(SDNode *N) {
+      assert(N->getOpcode() != ISD::DELETED_NODE &&
+             "Deleted Node added to Worklist");
+
       // Skip handle nodes as they can't usefully be combined and confuse the
       // zero-use deletion strategy.
       if (N->getOpcode() == ISD::HANDLENODE)
         return;
 
       if (WorklistMap.insert(std::make_pair(N, Worklist.size())).second)
         Worklist.push_back(N);
     }
 
     /// Remove all instances of N from the worklist.
     void removeFromWorklist(SDNode *N) {
       CombinedNodes.erase(N);
 
       auto It = WorklistMap.find(N);
if (Shorter.getNode())
                                Ptr, ST->getMemoryVT(), ST->getMemOperand());
 
     // Otherwise, see if we can simplify the operation with
     // SimplifyDemandedBits, which only works if the value has a single use.
     if (SimplifyDemandedBits(
             Value,
             APInt::getLowBitsSet(Value.getScalarValueSizeInBits(),
                                  ST->getMemoryVT().getScalarSizeInBits()))) {
-      // Re-visit the store if anything changed; SimplifyDemandedBits
-      // will add Value's node back to the worklist if necessary, but
-      // we also need to re-visit the Store node itself.
+      // Re-visit the store if anything changed and the store hasn't
+      // been merged with another node (N is deleted)␘;
+      // SimplifyDemandedBits will add Value's node back to the
+      // worklist if necessary, but we also need to re-visit the Store
+      // node itself.
+      if (N->getOpcode() != ISD::DELETED_NODE)
         AddToWorklist(N);
       return SDValue(N, 0);
     }
   }
 
   // If this is a load followed by a store to the same location, then the store
   // is dead/noop.
   if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(Value)) {
     if (Ld->getBasePtr() == Ptr && ST->getMemoryVT() == Ld->getMemoryVT() &&

test/CodeGen/X86/pr32108.ll

+; RUN: llc -march=x86-64 %s -o -
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @autogen_SD1794() {
+BB:
+  %Cmp45 = icmp slt <4 x i32> undef, undef
+  br label %CF243
+
+CF243:                                            ; preds = %CF243, %BB
+  br i1 undef, label %CF243, label %CF257
+
+CF257:                                            ; preds = %CF243
+  %Shuff144 = shufflevector <4 x i1> undef, <4 x i1> %Cmp45, <4 x i32> <i32 undef, i32 undef, i32 5, i32 undef>
+  br label %CF244
+
+CF244:                                            ; preds = %CF244, %CF257
+  %Shuff182 = shufflevector <4 x i1> %Shuff144, <4 x i1> zeroinitializer, <4 x i32> <i32 3, i32 5, i32 7, i32 undef>
+  br label %CF244
+}