ADT: Split ilist_node_traits into alloc and callback, NFC

Many lists want to override only allocation semantics, or callbacks for
iplist.  Split these up to prevent code duplication.
- Specialize ilist_alloc_traits to change the implementations of
  deleteNode() and createNode().
- One common desire is to do nothing deleteNode() and disable
  createNode().  Specialize ilist_alloc_traits to inherit from
  ilist_noalloc_traits for that behaviour.
- Specialize ilist_callback_traits to use the addNodeToList(),
  removeNodeFromList(), and transferNodesFromList() callbacks.

As a drive-by, add some coverage to the callback-related unit tests.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@280128 91177308-0d34-0410-b5e6-96231b3b80d8

11 files changed, 68 insertions, 57 deletions

diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h
index 14660b2b84d..e8d112043d7 100644
--- a/include/llvm/ADT/ilist.h
+++ b/include/llvm/ADT/ilist.h
@@ -33,27 +33,57 @@
 
 namespace llvm {
 
-/// A fragment for template traits for intrusive list that provides default
-/// node related operations.
+/// Use new/delete by default for iplist and ilist.
 ///
-/// TODO: Split up (alloc vs. callback) and delete.
-template <typename NodeTy> struct ilist_node_traits {
+/// Specialize this to get different behaviour for allocation-related API.  (If
+/// you really want new/delete, consider just using std::list.)
+///
+/// \see ilist_noalloc_traits
+template <typename NodeTy> struct ilist_alloc_traits {
   static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
   static void deleteNode(NodeTy *V) { delete V; }
+};
+
+/// Custom traits to disable node creation and do nothing on deletion.
+///
+/// Specialize ilist_alloc_traits to inherit from this to disable the
+/// non-intrusive parts of iplist and/or ilist.  It has no createNode function,
+/// and deleteNode does nothing.
+///
+/// \code
+/// template <>
+/// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {};
+/// \endcode
+template <typename NodeTy> struct ilist_noalloc_traits {
+  static void deleteNode(NodeTy *V) {}
+};
 
+/// Callbacks do nothing by default in iplist and ilist.
+///
+/// Specialize this for to use callbacks for when nodes change their list
+/// membership.
+template <typename NodeTy> struct ilist_callback_traits {
   void addNodeToList(NodeTy *) {}
   void removeNodeFromList(NodeTy *) {}
 
   /// Callback before transferring nodes to this list.
   ///
   /// \pre \c this!=&OldList
-  void transferNodesFromList(ilist_node_traits &OldList,
-                             ilist_iterator<NodeTy> /*first*/,
-                             ilist_iterator<NodeTy> /*last*/) {
+  template <class Iterator>
+  void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/,
+                             Iterator /*last*/) {
     (void)OldList;
   }
 };
 
+/// A fragment for template traits for intrusive list that provides default
+/// node related operations.
+///
+/// TODO: Remove this layer of indirection.  It's not necessary.
+template <typename NodeTy>
+struct ilist_node_traits : ilist_alloc_traits<NodeTy>,
+                           ilist_callback_traits<NodeTy> {};
+
 /// Default template traits for intrusive list.
 ///
 /// By inheriting from this, you can easily use default implementations for all
diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h
index 60268b1aafd..6333f55bc21 100644
--- a/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/include/llvm/CodeGen/MachineBasicBlock.h
@@ -38,22 +38,20 @@ class MachineBranchProbabilityInfo;
 // Forward declaration to avoid circular include problem with TargetRegisterInfo
 typedef unsigned LaneBitmask;
 
-template <>
-struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> {
+template <> struct ilist_traits<MachineInstr> {
 private:
-  // this is only set by the MachineBasicBlock owning the LiveList
-  friend class MachineBasicBlock;
-  MachineBasicBlock* Parent;
+  friend class MachineBasicBlock; // Set by the owning MachineBasicBlock.
+  MachineBasicBlock *Parent;
 
 public:
-  void addNodeToList(MachineInstr* N);
-  void removeNodeFromList(MachineInstr* N);
-  void transferNodesFromList(ilist_traits &SrcTraits,
-                             ilist_iterator<MachineInstr> First,
-                             ilist_iterator<MachineInstr> Last);
-  void deleteNode(MachineInstr *N);
-private:
-  void createNode(const MachineInstr &);
+  void addNodeToList(MachineInstr *N);
+  void removeNodeFromList(MachineInstr *N);
+  template <class Iterator>
+  void transferNodesFromList(ilist_traits &OldList, Iterator First,
+                             Iterator Last);
+
+  void deleteNode(MachineInstr *MI);
+  // Leave out createNode...
 };
 
 class MachineBasicBlock
@@ -697,7 +695,7 @@ private:
   BranchProbability getSuccProbability(const_succ_iterator Succ) const;
 
   // Methods used to maintain doubly linked list of blocks...
-  friend struct ilist_traits<MachineBasicBlock>;
+  friend struct ilist_callback_traits<MachineBasicBlock>;
 
   // Machine-CFG mutators
 
diff --git a/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h
index b6c1a08c98e..e3c11ccfe88 100644
--- a/include/llvm/CodeGen/MachineFunction.h
+++ b/include/llvm/CodeGen/MachineFunction.h
@@ -48,14 +48,19 @@ class TargetRegisterClass;
 struct MachinePointerInfo;
 struct WinEHFuncInfo;
 
-template <>
-struct ilist_traits<MachineBasicBlock>
-    : public ilist_default_traits<MachineBasicBlock> {
+template <> struct ilist_alloc_traits<MachineBasicBlock> {
+  void deleteNode(MachineBasicBlock *MBB);
+  // Disallow createNode...
+};
+
+template <> struct ilist_callback_traits<MachineBasicBlock> {
   void addNodeToList(MachineBasicBlock* MBB);
   void removeNodeFromList(MachineBasicBlock* MBB);
-  void deleteNode(MachineBasicBlock *MBB);
-private:
-  void createNode(const MachineBasicBlock &);
+
+  template <class Iterator>
+  void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator) {
+    llvm_unreachable("Never transfer between lists");
+  }
 };
 
 /// MachineFunctionInfo - This class can be derived from and used by targets to
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index c76bcdedf0e..264a91ba4cb 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -118,7 +118,7 @@ private:
 
   // Intrusive list support
   friend struct ilist_traits<MachineInstr>;
-  friend struct ilist_traits<MachineBasicBlock>;
+  friend struct ilist_callback_traits<MachineBasicBlock>;
   void setParent(MachineBasicBlock *P) { Parent = P; }
 
   /// This constructor creates a copy of the given
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index cabcac430fd..788132d45f7 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -81,12 +81,11 @@ template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTLis
   }
 };
 
-template <> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
+template <> struct ilist_alloc_traits<SDNode> {
   static void deleteNode(SDNode *) {
     llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
   }
-private:
-  static void createNode(const SDNode &);
+  // Don't implement createNode...
 };
 
 /// Keeps track of dbg_value information through SDISel.  We do
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index 96ef061ef81..ceeefc49dbf 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -49,7 +49,6 @@ class Value;
 class MCSymbol;
 template <typename T> struct DenseMapInfo;
 template <typename T> struct simplify_type;
-template <typename T> struct ilist_traits;
 
 void checkForCycles(const SDNode *N, const SelectionDAG *DAG = nullptr,
                     bool force = false);
@@ -503,7 +502,6 @@ private:
   static const EVT *getValueTypeList(EVT VT);
 
   friend class SelectionDAG;
-  friend struct ilist_traits<SDNode>;
   // TODO: unfriend HandleSDNode once we fix its operand handling.
   friend class HandleSDNode;
 
diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h
index 57fb2df37da..f6cacae9ea0 100644
--- a/include/llvm/CodeGen/SlotIndexes.h
+++ b/include/llvm/CodeGen/SlotIndexes.h
@@ -69,13 +69,8 @@ namespace llvm {
   };
 
   template <>
-  struct ilist_traits<IndexListEntry>
-      : public ilist_default_traits<IndexListEntry> {
-    void deleteNode(IndexListEntry *N) {}
-
-  private:
-    void createNode(const IndexListEntry &);
-  };
+  struct ilist_alloc_traits<IndexListEntry>
+      : public ilist_noalloc_traits<IndexListEntry> {};
 
   /// SlotIndex - An opaque wrapper around machine indexes.
   class SlotIndex {
diff --git a/include/llvm/IR/Metadata.h b/include/llvm/IR/Metadata.h
index 91f43d342d2..0ce88829214 100644
--- a/include/llvm/IR/Metadata.h
+++ b/include/llvm/IR/Metadata.h
@@ -1247,7 +1247,6 @@ public:
 ///
 /// TODO: Inherit from Metadata.
 class NamedMDNode : public ilist_node<NamedMDNode> {
-  friend struct ilist_traits<NamedMDNode>;
   friend class LLVMContextImpl;
   friend class Module;
   NamedMDNode(const NamedMDNode &) = delete;
diff --git a/include/llvm/IR/Module.h b/include/llvm/IR/Module.h
index d3b56ee3247..f51d02ee122 100644
--- a/include/llvm/IR/Module.h
+++ b/include/llvm/IR/Module.h
@@ -37,12 +37,6 @@ class RandomNumberGenerator;
 class StructType;
 template <class PtrType> class SmallPtrSetImpl;
 
-template<> struct ilist_traits<NamedMDNode>
-  : public ilist_default_traits<NamedMDNode> {
-  void addNodeToList(NamedMDNode *) {}
-  void removeNodeFromList(NamedMDNode *) {}
-};
-
 /// A Module instance is used to store all the information related to an
 /// LLVM module. Modules are the top level container of all other LLVM
 /// Intermediate Representation (IR) objects. Each module directly contains a
diff --git a/include/llvm/IR/SymbolTableListTraits.h b/include/llvm/IR/SymbolTableListTraits.h
index 87364aa32cd..673f168dd69 100644
--- a/include/llvm/IR/SymbolTableListTraits.h
+++ b/include/llvm/IR/SymbolTableListTraits.h
@@ -60,7 +60,7 @@ template <typename NodeTy> class SymbolTableList;
 // ItemParentClass - The type of object that owns the list, e.g. BasicBlock.
 //
 template <typename ValueSubClass>
-class SymbolTableListTraits : public ilist_node_traits<ValueSubClass> {
+class SymbolTableListTraits : public ilist_alloc_traits<ValueSubClass> {
   typedef SymbolTableList<ValueSubClass> ListTy;
   typedef ilist_iterator<ValueSubClass, false> iterator;
   typedef
diff --git a/include/llvm/MC/MCSection.h b/include/llvm/MC/MCSection.h
index a8d7af9bd65..714773acf5f 100644
--- a/include/llvm/MC/MCSection.h
+++ b/include/llvm/MC/MCSection.h
@@ -31,16 +31,9 @@ class MCSection;
 class MCSymbol;
 class raw_ostream;
 
-template<>
-struct ilist_node_traits<MCFragment> {
-  MCFragment *createNode(const MCFragment &V);
+template <> struct ilist_alloc_traits<MCFragment> {
   static void deleteNode(MCFragment *V);
-
-  void addNodeToList(MCFragment *) {}
-  void removeNodeFromList(MCFragment *) {}
-  void transferNodesFromList(ilist_node_traits &    /*SrcTraits*/,
-                             ilist_iterator<MCFragment> /*first*/,
-                             ilist_iterator<MCFragment> /*last*/) {}
+  // Leave out createNode...
 };
 
 /// Instances of this class represent a uniqued identifier for a section in the