ADT: Share code for embedded sentinel traits, NFC

Share code for the (mostly problematic) embedded sentinel traits.
- Move the LLVM_NO_SANITIZE("object-size") attribute to
  ilist_half_embedded_sentinel_traits and ilist_embedded_sentinel_traits
  (previously it spread throughout the code duplication).
- Add an ilist_full_embedded_sentinel_traits which has no UB (but has
  the downside of storing the complete node).
- Replace all the custom sentinel traits in LLVM with a declaration of
  ilist_sentinel_traits that inherits from one of the embedded sentinel
  traits classes.

There are still custom sentinel traits in other LLVM subprojects.  I'll
remove those in a follow-up.

Nothing at all should be changing here, this is just rearranging code.
Note that the final goal here is to remove the sentinel traits
altogether, settling on the memory layout of
ilist_half_embedded_sentinel_traits without the UB.  This intermediate
step moves the logic into ilist.h.

llvm-svn: 278513

10 files changed, 52 insertions, 137 deletions

diff --git a/llvm/include/llvm/ADT/SparseBitVector.h b/llvm/include/llvm/ADT/SparseBitVector.h
index e6e72413da4..4e19b16f61a 100644
--- a/llvm/include/llvm/ADT/SparseBitVector.h
+++ b/llvm/include/llvm/ADT/SparseBitVector.h
@@ -245,20 +245,9 @@ public:
 };
 
 template <unsigned ElementSize>
-struct ilist_traits<SparseBitVectorElement<ElementSize> >
-  : public ilist_default_traits<SparseBitVectorElement<ElementSize> > {
-  typedef SparseBitVectorElement<ElementSize> Element;
-
-  Element *createSentinel() const { return static_cast<Element *>(&Sentinel); }
-  static void destroySentinel(Element *) {}
-
-  Element *provideInitialHead() const { return createSentinel(); }
-  Element *ensureHead(Element *) const { return createSentinel(); }
-  static void noteHead(Element *, Element *) {}
-
-private:
-  mutable ilist_half_node<Element> Sentinel;
-};
+struct ilist_sentinel_traits<SparseBitVectorElement<ElementSize>>
+    : public ilist_half_embedded_sentinel_traits<
+          SparseBitVectorElement<ElementSize>> {};
 
 template <unsigned ElementSize = 128>
 class SparseBitVector {
diff --git a/llvm/include/llvm/ADT/ilist.h b/llvm/include/llvm/ADT/ilist.h
index 6744ddd6c9b..3a431bb9536 100644
--- a/llvm/include/llvm/ADT/ilist.h
+++ b/llvm/include/llvm/ADT/ilist.h
@@ -109,10 +109,11 @@ template <typename NodeTy> class ilist_half_node;
 template <typename NodeTy> class ilist_node;
 
 /// Traits with an embedded ilist_node as a sentinel.
-///
-/// FIXME: The downcast in createSentinel() is UB.
 template <typename NodeTy> struct ilist_embedded_sentinel_traits {
   /// Get hold of the node that marks the end of the list.
+  ///
+  /// FIXME: This downcast is UB.  See llvm.org/PR26753.
+  LLVM_NO_SANITIZE("object-size")
   NodeTy *createSentinel() const {
     // Since i(p)lists always publicly derive from their corresponding traits,
     // placing a data member in this class will augment the i(p)list.  But since
@@ -134,10 +135,11 @@ private:
 };
 
 /// Trait with an embedded ilist_half_node as a sentinel.
-///
-/// FIXME: The downcast in createSentinel() is UB.
 template <typename NodeTy> struct ilist_half_embedded_sentinel_traits {
   /// Get hold of the node that marks the end of the list.
+  ///
+  /// FIXME: This downcast is UB.  See llvm.org/PR26753.
+  LLVM_NO_SANITIZE("object-size")
   NodeTy *createSentinel() const {
     // See comment in ilist_embedded_sentinel_traits::createSentinel().
     return static_cast<NodeTy *>(&Sentinel);
@@ -152,6 +154,20 @@ private:
   mutable ilist_half_node<NodeTy> Sentinel;
 };
 
+/// Traits with an embedded full node as a sentinel.
+template <typename NodeTy> struct ilist_full_embedded_sentinel_traits {
+  /// Get hold of the node that marks the end of the list.
+  NodeTy *createSentinel() const { return &Sentinel; }
+  static void destroySentinel(NodeTy *) {}
+
+  NodeTy *provideInitialHead() const { return createSentinel(); }
+  NodeTy *ensureHead(NodeTy *) const { return createSentinel(); }
+  static void noteHead(NodeTy *, NodeTy *) {}
+
+private:
+  mutable NodeTy Sentinel;
+};
+
 /// ilist_node_traits - A fragment for template traits for intrusive list
 /// that provides default node related operations.
 ///
diff --git a/llvm/include/llvm/Analysis/IVUsers.h b/llvm/include/llvm/Analysis/IVUsers.h
index 031085dddd2..16161be8db0 100644
--- a/llvm/include/llvm/Analysis/IVUsers.h
+++ b/llvm/include/llvm/Analysis/IVUsers.h
@@ -91,32 +91,9 @@ private:
   void deleted() override;
 };
 
-template<> struct ilist_traits<IVStrideUse>
-  : public ilist_default_traits<IVStrideUse> {
-  // createSentinel is used to get hold of a node that marks the end of
-  // the list...
-  // The sentinel is relative to this instance, so we use a non-static
-  // method.
-  IVStrideUse *createSentinel() const {
-    // since i(p)lists always publicly derive from the corresponding
-    // traits, placing a data member in this class will augment i(p)list.
-    // But since the NodeTy is expected to publicly derive from
-    // ilist_node<NodeTy>, there is a legal viable downcast from it
-    // to NodeTy. We use this trick to superpose i(p)list with a "ghostly"
-    // NodeTy, which becomes the sentinel. Dereferencing the sentinel is
-    // forbidden (save the ilist_node<NodeTy>) so no one will ever notice
-    // the superposition.
-    return static_cast<IVStrideUse*>(&Sentinel);
-  }
-  static void destroySentinel(IVStrideUse*) {}
-
-  IVStrideUse *provideInitialHead() const { return createSentinel(); }
-  IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); }
-  static void noteHead(IVStrideUse*, IVStrideUse*) {}
-
-private:
-  mutable ilist_node<IVStrideUse> Sentinel;
-};
+template <>
+struct ilist_sentinel_traits<IVStrideUse>
+    : public ilist_embedded_sentinel_traits<IVStrideUse> {};
 
 class IVUsers {
   friend class IVStrideUse;
diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
index 2923371c100..37a7948c9ef 100644
--- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
@@ -39,24 +39,17 @@ class MachineBranchProbabilityInfo;
 typedef unsigned LaneBitmask;
 
 template <>
+struct ilist_sentinel_traits<MachineInstr>
+    : public ilist_half_embedded_sentinel_traits<MachineInstr> {};
+
+template <>
 struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> {
 private:
-  mutable ilist_half_node<MachineInstr> Sentinel;
-
   // this is only set by the MachineBasicBlock owning the LiveList
   friend class MachineBasicBlock;
   MachineBasicBlock* Parent;
 
 public:
-  MachineInstr *createSentinel() const {
-    return static_cast<MachineInstr*>(&Sentinel);
-  }
-  void destroySentinel(MachineInstr *) const {}
-
-  MachineInstr *provideInitialHead() const { return createSentinel(); }
-  MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); }
-  static void noteHead(MachineInstr*, MachineInstr*) {}
-
   void addNodeToList(MachineInstr* N);
   void removeNodeFromList(MachineInstr* N);
   void transferNodesFromList(ilist_traits &SrcTraits,
diff --git a/llvm/include/llvm/CodeGen/MachineFunction.h b/llvm/include/llvm/CodeGen/MachineFunction.h
index f4c3b5c9ebb..533d659d78b 100644
--- a/llvm/include/llvm/CodeGen/MachineFunction.h
+++ b/llvm/include/llvm/CodeGen/MachineFunction.h
@@ -49,23 +49,12 @@ struct MachinePointerInfo;
 struct WinEHFuncInfo;
 
 template <>
+struct ilist_sentinel_traits<MachineBasicBlock>
+    : public ilist_half_embedded_sentinel_traits<MachineBasicBlock> {};
+
+template <>
 struct ilist_traits<MachineBasicBlock>
     : public ilist_default_traits<MachineBasicBlock> {
-  mutable ilist_half_node<MachineBasicBlock> Sentinel;
-public:
-  // FIXME: This downcast is UB. See llvm.org/PR26753.
-  LLVM_NO_SANITIZE("object-size")
-  MachineBasicBlock *createSentinel() const {
-    return static_cast<MachineBasicBlock*>(&Sentinel);
-  }
-  void destroySentinel(MachineBasicBlock *) const {}
-
-  MachineBasicBlock *provideInitialHead() const { return createSentinel(); }
-  MachineBasicBlock *ensureHead(MachineBasicBlock*) const {
-    return createSentinel();
-  }
-  static void noteHead(MachineBasicBlock*, MachineBasicBlock*) {}
-
   void addNodeToList(MachineBasicBlock* MBB);
   void removeNodeFromList(MachineBasicBlock* MBB);
   void deleteNode(MachineBasicBlock *MBB);
diff --git a/llvm/include/llvm/CodeGen/SelectionDAG.h b/llvm/include/llvm/CodeGen/SelectionDAG.h
index 29cce873c2f..8a89249e92a 100644
--- a/llvm/include/llvm/CodeGen/SelectionDAG.h
+++ b/llvm/include/llvm/CodeGen/SelectionDAG.h
@@ -81,19 +81,11 @@ template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTLis
   }
 };
 
-template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
-private:
-  mutable ilist_half_node<SDNode> Sentinel;
-public:
-  SDNode *createSentinel() const {
-    return static_cast<SDNode*>(&Sentinel);
-  }
-  static void destroySentinel(SDNode *) {}
-
-  SDNode *provideInitialHead() const { return createSentinel(); }
-  SDNode *ensureHead(SDNode*) const { return createSentinel(); }
-  static void noteHead(SDNode*, SDNode*) {}
+template <>
+struct ilist_sentinel_traits<SDNode>
+    : public ilist_half_embedded_sentinel_traits<SDNode> {};
 
+template <> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
   static void deleteNode(SDNode *) {
     llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
   }
diff --git a/llvm/include/llvm/CodeGen/SlotIndexes.h b/llvm/include/llvm/CodeGen/SlotIndexes.h
index 01184dc39b3..6090ecec32a 100644
--- a/llvm/include/llvm/CodeGen/SlotIndexes.h
+++ b/llvm/include/llvm/CodeGen/SlotIndexes.h
@@ -69,18 +69,12 @@ namespace llvm {
   };
 
   template <>
-  struct ilist_traits<IndexListEntry> : public ilist_default_traits<IndexListEntry> {
-  private:
-    mutable ilist_half_node<IndexListEntry> Sentinel;
-  public:
-    IndexListEntry *createSentinel() const {
-      return static_cast<IndexListEntry*>(&Sentinel);
-    }
-    void destroySentinel(IndexListEntry *) const {}
+  struct ilist_sentinel_traits<IndexListEntry>
+      : public ilist_half_embedded_sentinel_traits<IndexListEntry> {};
 
-    IndexListEntry *provideInitialHead() const { return createSentinel(); }
-    IndexListEntry *ensureHead(IndexListEntry*) const { return createSentinel(); }
-    static void noteHead(IndexListEntry*, IndexListEntry*) {}
+  template <>
+  struct ilist_traits<IndexListEntry>
+      : public ilist_default_traits<IndexListEntry> {
     void deleteNode(IndexListEntry *N) {}
 
   private:
diff --git a/llvm/include/llvm/IR/Module.h b/llvm/include/llvm/IR/Module.h
index 632b27e2d0d..ef7e4074176 100644
--- a/llvm/include/llvm/IR/Module.h
+++ b/llvm/include/llvm/IR/Module.h
@@ -37,23 +37,14 @@ class RandomNumberGenerator;
 class StructType;
 template <class PtrType> class SmallPtrSetImpl;
 
+template <>
+struct ilist_sentinel_traits<NamedMDNode>
+    : public ilist_embedded_sentinel_traits<NamedMDNode> {};
+
 template<> struct ilist_traits<NamedMDNode>
   : public ilist_default_traits<NamedMDNode> {
-  // createSentinel is used to get hold of a node that marks the end of
-  // the list...
-  NamedMDNode *createSentinel() const {
-    return static_cast<NamedMDNode*>(&Sentinel);
-  }
-  static void destroySentinel(NamedMDNode*) {}
-
-  NamedMDNode *provideInitialHead() const { return createSentinel(); }
-  NamedMDNode *ensureHead(NamedMDNode*) const { return createSentinel(); }
-  static void noteHead(NamedMDNode*, NamedMDNode*) {}
   void addNodeToList(NamedMDNode *) {}
   void removeNodeFromList(NamedMDNode *) {}
-
-private:
-  mutable ilist_node<NamedMDNode> Sentinel;
 };
 
 /// A Module instance is used to store all the information related to an
diff --git a/llvm/include/llvm/Transforms/Utils/MemorySSA.h b/llvm/include/llvm/Transforms/Utils/MemorySSA.h
index 2caa63feec6..606ecff59c5 100644
--- a/llvm/include/llvm/Transforms/Utils/MemorySSA.h
+++ b/llvm/include/llvm/Transforms/Utils/MemorySSA.h
@@ -171,23 +171,8 @@ private:
 };
 
 template <>
-struct ilist_traits<MemoryAccess> : public ilist_default_traits<MemoryAccess> {
-  /// See details of the instruction class for why this trick works
-  // FIXME: This downcast is UB. See llvm.org/PR26753.
-  LLVM_NO_SANITIZE("object-size")
-  MemoryAccess *createSentinel() const {
-    return static_cast<MemoryAccess *>(&Sentinel);
-  }
-
-  static void destroySentinel(MemoryAccess *) {}
-
-  MemoryAccess *provideInitialHead() const { return createSentinel(); }
-  MemoryAccess *ensureHead(MemoryAccess *) const { return createSentinel(); }
-  static void noteHead(MemoryAccess *, MemoryAccess *) {}
-
-private:
-  mutable ilist_half_node<MemoryAccess> Sentinel;
-};
+struct ilist_sentinel_traits<MemoryAccess>
+    : public ilist_half_embedded_sentinel_traits<MemoryAccess> {};
 
 inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) {
   MA.print(OS);
diff --git a/llvm/lib/Support/YAMLParser.cpp b/llvm/lib/Support/YAMLParser.cpp
index 2b71c596cc4..4d5b750e266 100644
--- a/llvm/lib/Support/YAMLParser.cpp
+++ b/llvm/lib/Support/YAMLParser.cpp
@@ -149,20 +149,9 @@ struct Token : ilist_node<Token> {
 }
 
 namespace llvm {
-template<>
-struct ilist_sentinel_traits<Token> {
-  Token *createSentinel() const {
-    return &Sentinel;
-  }
-  static void destroySentinel(Token*) {}
-
-  Token *provideInitialHead() const { return createSentinel(); }
-  Token *ensureHead(Token*) const { return createSentinel(); }
-  static void noteHead(Token*, Token*) {}
-
-private:
-  mutable Token Sentinel;
-};
+template <>
+struct ilist_sentinel_traits<Token>
+    : public ilist_full_embedded_sentinel_traits<Token> {};
 
 template<>
 struct ilist_node_traits<Token> {