[DAG] Set up infrastructure to avoid smart constructor-based dangling nodes

[niravd]

Summary

Various SelectionDAG non-combine operations (e.g. the getNode smart
constructor and legalization) may leave dangling nodes by applying
optimizations without fully pruning unused result values. This results
in nodes that are never added to the worklist and therefore can not be
pruned.

Add a node inserter for the combiner to make sure such nodes have the
chance of being pruned. This allows a number of additional peephole
optimizations.

[niravd]

Rebase after some cleanups. Add comments on regressions test cases. Most of these are exposing PR40881. '
The remain case (vsel-cmp-load.ll) appears to be a missing revisitation some nodes

[niravd]

Ping.

[jyknight]

Could you add a comment to the CL description noting that a bunch of the calls to AddToWorklist in DAGCombiner.cpp that follow a DAG.getNode() are now redundant, and should be cleaned up in the future.

llvm/test/CodeGen/X86/3addr-or.ll

21 ↗

(On Diff #188609)

These are all due to PR40881? Please add PR references to all the FIXME comments if possible.

[niravd]

Address James' comments.

[niravd]

Ping/

[niravd]

Ping.

[niravd]

Rebase to tip before landing.

[niravd]

Landed in rL356996

[niravd]

Initial commit reverted due to Halide compile time explosion.

[niravd]

Defer Worklist modification in NodeInserter to follow up patch (D58070).

[jyknight]

Looks fine again.

llvm/trunk/include/llvm/CodeGen/SelectionDAG.h

struct DAGUpdateListener {
     }
 
     /// The node N that was deleted and, if E is not null, an
     /// equivalent node E that replaced it.
     virtual void NodeDeleted(SDNode *N, SDNode *E);
 
     /// The node N that was updated.
     virtual void NodeUpdated(SDNode *N);
+
+    /// The node N that was inserted.
+    virtual void NodeInserted(SDNode *N);
   };
 
   struct DAGNodeDeletedListener : public DAGUpdateListener {
     std::function<void(SDNode *, SDNode *)> Callback;
 
     DAGNodeDeletedListener(SelectionDAG &DAG,
                            std::function<void(SDNode *, SDNode *)> Callback)
         : DAGUpdateListener(DAG), Callback(std::move(Callback)) {}

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

public:
   explicit WorklistRemover(DAGCombiner &dc)
     : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
 
   void NodeDeleted(SDNode *N, SDNode *E) override {
     DC.removeFromWorklist(N);
   }
 };
 
+class WorklistInserter : public SelectionDAG::DAGUpdateListener {
+  DAGCombiner &DC;
+
+public:
+  explicit WorklistInserter(DAGCombiner &dc)
+      : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
+
+  // This should eventually be pruning.
+  void NodeInserted(SDNode *N) override { }
+};
+
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 //  TargetLowering::DAGCombinerInfo implementation
 //===----------------------------------------------------------------------===//
 
 void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) {
   ((DAGCombiner*)DC)->AddToWorklist(N);

 //===----------------------------------------------------------------------===//
 
 void DAGCombiner::Run(CombineLevel AtLevel) {
   // set the instance variables, so that the various visit routines may use it.
   Level = AtLevel;
   LegalOperations = Level >= AfterLegalizeVectorOps;
   LegalTypes = Level >= AfterLegalizeTypes;
 
+  WorklistInserter AddNodes(*this);
+
   // Add all the dag nodes to the worklist.
   for (SDNode &Node : DAG.allnodes())
     AddToWorklist(&Node);
 
   // Create a dummy node (which is not added to allnodes), that adds a reference
   // to the root node, preventing it from being deleted, and tracking any
   // changes of the root.
   HandleSDNode Dummy(DAG.getRoot());

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

 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
   SDVTList Res = {VTs, NumVTs};
   return Res;
 }
 
 // Default null implementations of the callbacks.
 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
+void SelectionDAG::DAGUpdateListener::NodeInserted(SDNode *) {}
 
 void SelectionDAG::DAGNodeDeletedListener::anchor() {}
 
 #define DEBUG_TYPE "selectiondag"
 
 static cl::opt<bool> EnableMemCpyDAGOpt("enable-memcpy-dag-opt",
        cl::Hidden, cl::init(true),
        cl::desc("Gang up loads and stores generated by inlining of memcpy"));

 /// Handles insertion into the all nodes list and CSE map, as well as
 /// verification and other common operations when a new node is allocated.
 void SelectionDAG::InsertNode(SDNode *N) {
   AllNodes.push_back(N);
 #ifndef NDEBUG
   N->PersistentId = NextPersistentId++;
   VerifySDNode(N);
 #endif
+  for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
+    DUL->NodeInserted(N);
 }
 
 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
 /// correspond to it.  This is useful when we're about to delete or repurpose
 /// the node.  We don't want future request for structurally identical nodes
 /// to return N anymore.
 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
   bool Erased = false;