ADT: Remove UB in ilist (and use a circular linked list)

[dexonsmith]

Summary

This removes the undefined behaviour (UB) in ilist/ilist_node/etc.,
mainly by removing (gutting) the ilist_sentinel_traits customization
point and canonicalizing on a single, efficient memory layout.

The new ilist is a doubly-linked circular list.

• ilist_node_base has two ilist_node_base*: Next and Prev. Size-of: two pointers.
• ilist_node<T> (size-of: two pointers) is a type-safe wrapper around ilist_node_base.
• ilist_iterator<T> (size-of: two pointers) operates on an ilist_node<T>*, and downcasts to T* on dereference.
• ilist_sentinel<T> (size-of: two pointers) is a wrapper around ilist_node<T> that has some extra API for list management.
• ilist<T> (size-of: two pointers) has an ilist_sentinel<T>, whose address is returned for end().

The new memory layout matches ilist_half_embedded_sentinel_traits<T>
exactly. The Head pointer that previously lived in ilist<T> is
effectively glued to the ilist_half_node<T> that lived in
ilist_half_embedded_sentinel_traits<T>, becoming the Next and Prev in
the ilist_sentinel_node<T>, respectively. sizeof(ilist<T>) is now the
size of two pointers, and there is never any additional storage for a
sentinel.

This is a much simpler design for a doubly-linked list, removing most of
the corner cases of list manipulation (add, remove, etc.). In follow-up
commits, I intend to move as many algorithms as possible into a
non-templated base class (ilist_base) to reduce code size.

Moreover, this fixes the UB in ilist_iterator/getNext/getPrev
operations. Previously, ilist_iterator<T> operated on a T*, even when
the sentinel was not of type T (i.e., ilist_embedded_sentinel_traits and
ilist_half_embedded_sentinel_traits). This added UB to all operations
involving end(). Now, ilist_iterator<T> operates on an ilist_node<T>*,
and only downcasts when the full type is guaranteed to be T*.

What did we lose? There used to be a crash (in some configurations) on
++end(). Curiously (via UB), ++end() would return begin() for users of
ilist_half_embedded_sentinel_traits<T>, but otherwise ++end() would
cause a nice dependable nullptr dereference, crashing instead of a
possible infinite loop. Options:

1. Lose that behaviour.
2. Keep it, by stealing a bit from Prev in asserts builds.
3. Crash on dereference instead, using the same technique.

Hans convinced me (because of the number of problems this and r278532
exposed on Windows) that we really need some assertion here, at least in
the short term. I've opted for #3 since I think it catches more bugs.

I added only a couple of unit tests to root out specific bugs I hit
during bring-up, but otherwise this is tested implicitly via the
extensive usage throughout LLVM.

Planned follow-ups:

• Remove ilist_*sentinel_traits<T>. Here I've just gutted them to prevent build failures in sub-projects. Once I stop referring to them in sub-projects, I'll come back and delete them.
• Add ilist_base and move algorithms there.

Eventually, there are other interesting directions:

• Remove ilist_traits::createNode, by deleting the remaining API that creates nodes. Intrusive lists shouldn't be creating nodes themselves.
• Remove ilist_traits::deleteNode, by (1) asserting that lists are empty on destruction and (2) changing API that calls it to take a Deleter functor (intrusive lists shouldn't be in the memory management business).
• Reconfigure the remaining callback traits (addNodeToList, etc.) to be higher-level, pulling out a simple_ilist<T> that is much easier to read and understand.
• Allow tags (e.g., ilist_node<T,tag1> and ilist_node<T,tag2>) so that T can be a member of multiple intrusive lists.

[dexonsmith]

Another direction I plan to pursue rather quickly is "fixing" reverse iterators, so that rbegin().getNodePtr()==&*rbegin(). This allows much simpler logic when erasing elements during a reverse traversal.

[dexonsmith]

Oh, this fixes PR26753:
http://llvm.org/pr26753

[mehdi_amini]

LGTM overall, with a few inline comments that you should look at.

include/llvm/ADT/ilist.h

17–18

Stalled comment about createSentinel()?

26–28

It seems to be one of the main change in the model: before it was possible to create a list from something that would not inherit from ilist_node right?
I guess we don't lose much...

236

Stalled assert (at least assert message)?

323–324

Could be removed?

404–405

I'm not sure this is true, ++it will just work fine, but it will be in a "default constructed" state (NodePtr being a nullptr).
Only ilist_iterator &operator--() is asserting right now (incidentally, see previous comment).

470

Are these different from first and last?

[dexonsmith]

Updated to address comments from Justin and Mehdi, but I'll wait to commit until Monday. Hans volunteered to run tests on Windows pre-commit. r278532 (up to r278539) somehow exposed a number of bugs in the backends (see r278572, r278577, and r278587), and I suspect this could expose others.

[hans]

I tried this out on Windows.

Some tests are currently red with ToT: http://lab.llvm.org:8011/builders/clang-x86-win2008-selfhost/builds/9727
On my machine, only CodeGen/AMDGPU/amdgpu.private-memory.ll fails.

When I apply this patch, CodeGen/AMDGPU/predicate-dp4.ll starts hanging, but that's the only change I get.

[dexonsmith]

Hans ran the tests yesterday on Windows, and an end() dereference manifested as an infinite loop. He has convinced me we really need some assertions to root out long-standing bugs that the optimizers may suddenly be exploiting. Hans suggested asserting in operator*() and that makes sense to me.

• I'm updating the summary here on Phab to match my working commit message (options #1, #2 and #3 have changed).
• The updated patch asserts that the sentinel is never dereferenced (it uses a PointerIntPair to pack IsSentinel into Prev).
• I'm working on fixing the (many, many) crashes that this gives when running 'check'.
• I'll post back here when 'check' and 'check-clang' are clean. At that point I'll try a bootstrap of 'clang' on Darwin/x86_64, since this is exposing a lot of bugs and I don't entirely trust our lit-test coverage. Volunteers for other configurations welcome! (Otherwise I'll leave it to the bots.)

[hans]

In D23466#517296, @dexonsmith wrote:

• I'll post back here when 'check' and 'check-clang' are clean. At that point I'll try a bootstrap of 'clang' on Darwin/x86_64, since this is exposing a lot of bugs and I don't entirely trust our lit-test coverage. Volunteers for other configurations welcome! (Otherwise I'll leave it to the bots.)

I'll be happy to test a Linux bootstrap and on Chromium.

[dexonsmith]

Thanks Hans!

'check' is clean on Darwin as of r278887. 'check-lld' is also clean. I'm currently running 'check-clang' on one box and optimistically running 'tools/clang/cmake/caches/3-stage.cmake' to run 'stage3-clang' on another in parallel (llvm/clang/compiler-rt/libcxx at r278887 + this patch, using -DCMAKE_BUILD_TYPE=RelWithDebInfo -DLLVM_ENABLE_ASSERTIONS=ON). Assuming everything just works I hope to commit tomorrow, but I'll wait to hear back from Hans.

[dexonsmith]

'check-clang' failed one test. As of r278898, it's also clean.

[hans]

In D23466#517620, @dexonsmith wrote:

'check-clang' failed one test. As of r278898, it's also clean.

I applied your patch on Windows and ran llvm and clang's lit tests and a chromium build with no issues :-)

[dexonsmith]

Committed in r278974!

include/llvm/ADT/ilist.h

 //==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines classes to implement an intrusive doubly linked list class
 // (i.e. each node of the list must contain a next and previous field for the
 // list.
 //
 // The ilist class itself should be a plug in replacement for list.  This list
 // replacement does not provide a constant time size() method, so be careful to
 // use empty() when you really want to know if it's empty.
 //
-// The ilist class is implemented by allocating a 'tail' node when the list is
-// created (using ilist_traits<>::createSentinel()).  This tail node is
-// absolutely required because the user must be able to compute end()-1. Because
-// of this, users of the direct next/prev links will see an extra link on the
-// end of the list, which should be ignored.
+// The ilist class is implemented as a circular list.  The list itself contains
+// a sentinel node, whose Next points at begin() and whose Prev points at
+// rbegin().  The sentinel node itself serves as end() and rend().
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_ILIST_H
 #define LLVM_ADT_ILIST_H
 
+#include "llvm/ADT/ilist_node.h"
 #include "llvm/Support/Compiler.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <type_traits>
 
 namespace llvm {
 
 template<typename NodeTy, typename Traits> class iplist;
 template<typename NodeTy> class ilist_iterator;
 
-/// An access class for next/prev on ilist_nodes.
+/// An access class for ilist_node private API.
 ///
 /// This gives access to the private parts of ilist nodes.  Nodes for an ilist
 /// should friend this class if they inherit privately from ilist_node.
 ///
-/// It's strongly discouraged to *use* this class outside of ilist
+/// It's strongly discouraged to *use* this class outside of the ilist
 /// implementation.
 struct ilist_node_access {
-  template <typename NodeTy> static NodeTy *getPrev(NodeTy *N) {
+  template <typename T> static ilist_node<T> *getNodePtr(T *N) { return N; }
+  template <typename T> static const ilist_node<T> *getNodePtr(const T *N) {
+    return N;
+  }
+
+  template <typename T> static ilist_node<T> *getPrev(ilist_node<T> *N) {
     return N->getPrev();
   }
-  template <typename NodeTy> static NodeTy *getNext(NodeTy *N) {
+  template <typename T> static ilist_node<T> *getNext(ilist_node<T> *N) {
     return N->getNext();
   }
-  template <typename NodeTy> static const NodeTy *getPrev(const NodeTy *N) {
+  template <typename T> static const ilist_node<T> *getPrev(const ilist_node<T> *N) {
     return N->getPrev();
   }
-  template <typename NodeTy> static const NodeTy *getNext(const NodeTy *N) {
+  template <typename T> static const ilist_node<T> *getNext(const ilist_node<T> *N) {
     return N->getNext();
   }
 
-  template <typename NodeTy> static void setPrev(NodeTy *N, NodeTy *Prev) {
+  template <typename T> static void setPrev(ilist_node<T> *N, ilist_node<T> *Prev) {
     N->setPrev(Prev);
   }
-  template <typename NodeTy> static void setNext(NodeTy *N, NodeTy *Next) {
+  template <typename T> static void setNext(ilist_node<T> *N, ilist_node<T> *Next) {
     N->setNext(Next);
   }
-  template <typename NodeTy> static void setPrev(NodeTy *N, std::nullptr_t) {
+  template <typename T> static void setPrev(ilist_node<T> *N, std::nullptr_t) {
     N->setPrev(nullptr);
   }
-  template <typename NodeTy> static void setNext(NodeTy *N, std::nullptr_t) {
+  template <typename T> static void setNext(ilist_node<T> *N, std::nullptr_t) {
     N->setNext(nullptr);
   }
 };
 
 namespace ilist_detail {
 
 template <class T> T &make();
 
 /// Type trait to check for a traits class that has a getNext member (as a
 /// canary for any of the ilist_nextprev_traits API).
 template <class TraitsT, class NodeT> struct HasGetNext {
   typedef char Yes[1];
   typedef char No[2];
   template <size_t N> struct SFINAE {};
 
   template <class U>
   static Yes &hasGetNext(
       SFINAE<sizeof(static_cast<NodeT *>(make<U>().getNext(&make<NodeT>())))>
           * = 0);
   template <class U> static No &hasGetNext(...);
 
   static const bool value = sizeof(hasGetNext<TraitsT>(nullptr)) == sizeof(Yes);
 };
 
-} // end namespace ilist_detail
-
-template<typename NodeTy>
-struct ilist_traits;
-
-/// ilist_sentinel_traits - A fragment for template traits for intrusive list
-/// that provides default sentinel implementations for common operations.
-///
-/// ilist_sentinel_traits implements a lazy dynamic sentinel allocation
-/// strategy. The sentinel is stored in the prev field of ilist's Head.
-///
-template<typename NodeTy>
-struct ilist_sentinel_traits {
-  /// createSentinel - create the dynamic sentinel
-  static NodeTy *createSentinel() { return new NodeTy(); }
-
-  /// destroySentinel - deallocate the dynamic sentinel
-  static void destroySentinel(NodeTy *N) { delete N; }
-
-  /// provideInitialHead - when constructing an ilist, provide a starting
-  /// value for its Head
-  /// @return null node to indicate that it needs to be allocated later
-  static NodeTy *provideInitialHead() { return nullptr; }
-
-  /// ensureHead - make sure that Head is either already
-  /// initialized or assigned a fresh sentinel
-  /// @return the sentinel
-  static NodeTy *ensureHead(NodeTy *&Head) {
-    if (!Head) {
-      Head = ilist_traits<NodeTy>::createSentinel();
-      ilist_traits<NodeTy>::noteHead(Head, Head);
-      ilist_node_access::setNext(Head, nullptr);
-      return Head;
-    }
-    return ilist_node_access::getPrev(Head);
-  }
-
-  /// noteHead - stash the sentinel into its default location
-  static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) {
-    ilist_node_access::setPrev(NewHead, Sentinel);
-  }
-};
-
-template <typename NodeTy> class ilist_half_node;
-template <typename NodeTy> class ilist_node;
+/// Type trait to check for a traits class that has a createSentinel member (as
+/// a canary for any of the ilist_sentinel_traits API).
+template <class TraitsT> struct HasCreateSentinel {
+  typedef char Yes[1];
+  typedef char No[2];
+  template <size_t N> struct SFINAE {};
 
-/// Traits with an embedded ilist_node as a sentinel.
-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
-    // the NodeTy is expected to be publicly derive from ilist_node<NodeTy>,
-    // there is a legal viable downcast from it to NodeTy. We use this trick to
-    // superimpose an 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<NodeTy *>(&Sentinel);
-  }
-  static void destroySentinel(NodeTy *) {}
-
-  NodeTy *provideInitialHead() const { return createSentinel(); }
-  NodeTy *ensureHead(NodeTy *) const { return createSentinel(); }
-  static void noteHead(NodeTy *, NodeTy *) {}
+  template <class U>
+  static Yes &
+  hasCreateSentinel(SFINAE<sizeof(make<U>().createSentinel())> * = 0);
+  template <class U> static No &hasCreateSentinel(...);
 
-private:
-  mutable ilist_node<NodeTy> Sentinel;
+  static const bool value =
+      sizeof(hasCreateSentinel<TraitsT>(nullptr)) == sizeof(Yes);
 };
 
-/// Trait with an embedded ilist_half_node as a sentinel.
-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);
-  }
-  static void destroySentinel(NodeTy *) {}
-
-  NodeTy *provideInitialHead() const { return createSentinel(); }
-  NodeTy *ensureHead(NodeTy *) const { return createSentinel(); }
-  static void noteHead(NodeTy *, NodeTy *) {}
-
-private:
-  mutable ilist_half_node<NodeTy> Sentinel;
-};
+} // end namespace ilist_detail
 
-/// 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 *) {}
+template <typename NodeTy> struct ilist_traits;
 
-private:
-  mutable NodeTy Sentinel;
-};
+// TODO: Delete uses from subprojects, then delete these.
+template <typename NodeTy> struct ilist_sentinel_traits {};
+template <typename NodeTy> struct ilist_embedded_sentinel_traits {};
+template <typename NodeTy> struct ilist_half_embedded_sentinel_traits {};
+template <typename NodeTy> struct ilist_full_embedded_sentinel_traits {};
 
 /// ilist_node_traits - A fragment for template traits for intrusive list
 /// that provides default node related operations.
 ///
 template<typename NodeTy>
 struct ilist_node_traits {
   static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
   static void deleteNode(NodeTy *V) { delete V; }
 
   void addNodeToList(NodeTy *) {}
   void removeNodeFromList(NodeTy *) {}
   void transferNodesFromList(ilist_node_traits &    /*SrcTraits*/,
                              ilist_iterator<NodeTy> /*first*/,
                              ilist_iterator<NodeTy> /*last*/) {}
 };
 
 /// ilist_default_traits - Default template traits for intrusive list.
 /// By inheriting from this, you can easily use default implementations
 /// for all common operations.
 ///
 template <typename NodeTy>
-struct ilist_default_traits : public ilist_sentinel_traits<NodeTy>,
-                              public ilist_node_traits<NodeTy> {};
+struct ilist_default_traits : public ilist_node_traits<NodeTy> {};
 
 // Template traits for intrusive list.  By specializing this template class, you
 // can change what next/prev fields are used to store the links...
 template<typename NodeTy>
 struct ilist_traits : public ilist_default_traits<NodeTy> {};
 
 // Const traits are the same as nonconst traits...
 template<typename Ty>
public:
   typedef typename std::add_const<value_type>::type *const_pointer;
   typedef typename std::add_const<value_type>::type &const_reference;
 
   typedef typename ilist_detail::ConstCorrectNodeType<NodeTy>::type node_type;
   typedef node_type *node_pointer;
   typedef node_type &node_reference;
 
 private:
-  pointer NodePtr;
+  node_pointer NodePtr = nullptr;
 
 public:
   /// Create from an ilist_node.
-  explicit ilist_iterator(node_reference N)
-      : NodePtr(static_cast<NodeTy *>(&N)) {}
+  explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
 
   explicit ilist_iterator(pointer NP) : NodePtr(NP) {}
   explicit ilist_iterator(reference NR) : NodePtr(&NR) {}
-  ilist_iterator() : NodePtr(nullptr) {}
+  ilist_iterator() = default;
 
   // This is templated so that we can allow constructing a const iterator from
   // a nonconst iterator...
   template <class node_ty>
   ilist_iterator(
       const ilist_iterator<node_ty> &RHS,
       typename std::enable_if<std::is_convertible<node_ty *, NodeTy *>::value,
                               void *>::type = nullptr)
-      : NodePtr(RHS.getNodePtrUnchecked()) {}
+      : NodePtr(RHS.getNodePtr()) {}
 
   // This is templated so that we can allow assigning to a const iterator from
   // a nonconst iterator...
   template <class node_ty>
   const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) {
-    NodePtr = RHS.getNodePtrUnchecked();
+    NodePtr = RHS.getNodePtr();
     return *this;
   }
 
   void reset(pointer NP) { NodePtr = NP; }
 
   // Accessors...
-  reference operator*() const { return *NodePtr; }
+  reference operator*() const {
+    assert(!NodePtr->isKnownSentinel());
+    return static_cast<NodeTy &>(*getNodePtr());
+  }
   pointer operator->() const { return &operator*(); }
 
   // Comparison operators
   friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
     return LHS.NodePtr == RHS.NodePtr;
   }
   friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
     return LHS.NodePtr != RHS.NodePtr;
   }
 
   // Increment and decrement operators...
   ilist_iterator &operator--() {
     NodePtr = ilist_node_access::getPrev(NodePtr);
     assert(NodePtr && "--'d off the beginning of an ilist!");
     return *this;
   }
   ilist_iterator &operator++() {
     NodePtr = ilist_node_access::getNext(NodePtr);
     return *this;
   }
   ilist_iterator operator--(int) {
     ilist_iterator tmp = *this;
     --*this;
     return tmp;
   }
   ilist_iterator operator++(int) {
     ilist_iterator tmp = *this;
     ++*this;
     return tmp;
   }
 
   /// Get the underlying ilist_node.
   node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
-
-  // Internal interface, do not use...
-  pointer getNodePtrUnchecked() const { return NodePtr; }
 };
 
 // Allow ilist_iterators to convert into pointers to a node automatically when
 // used by the dyn_cast, cast, isa mechanisms...
 
 template<typename From> struct simplify_type;
 
 template<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > {
template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > {
   static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) {
     return &*Node;
   }
 };
 
 
 //===----------------------------------------------------------------------===//
 //
-/// iplist - The subset of list functionality that can safely be used on nodes
-/// of polymorphic types, i.e. a heterogeneous list with a common base class that
-/// holds the next/prev pointers.  The only state of the list itself is a single
-/// pointer to the head of the list.
-///
-/// This list can be in one of three interesting states:
-/// 1. The list may be completely unconstructed.  In this case, the head
-///    pointer is null.  When in this form, any query for an iterator (e.g.
-///    begin() or end()) causes the list to transparently change to state #2.
-/// 2. The list may be empty, but contain a sentinel for the end iterator. This
-///    sentinel is created by the Traits::createSentinel method and is a link
-///    in the list.  When the list is empty, the pointer in the iplist points
-///    to the sentinel.  Once the sentinel is constructed, it
-///    is not destroyed until the list is.
-/// 3. The list may contain actual objects in it, which are stored as a doubly
-///    linked list of nodes.  One invariant of the list is that the predecessor
-///    of the first node in the list always points to the last node in the list,
-///    and the successor pointer for the sentinel (which always stays at the
-///    end of the list) is always null.
-///
+/// The subset of list functionality that can safely be used on nodes of
+/// polymorphic types, i.e. a heterogeneous list with a common base class that
+/// holds the next/prev pointers.  The only state of the list itself is an
+/// ilist_sentinel, which holds pointers to the first and last nodes in the
+/// list.
 template <typename NodeTy, typename Traits = ilist_traits<NodeTy>>
 class iplist : public Traits, ilist_node_access {
+  // TODO: Drop these assertions anytime after 4.1 is branched.
 #if !defined(_MSC_VER)
   // FIXME: This fails in MSVC, but it's worth keeping around to help
   // non-Windows users root out bugs in their ilist_traits.
   static_assert(!ilist_detail::HasGetNext<Traits, NodeTy>::value,
                 "ilist next and prev links are not customizable!");
+  static_assert(!ilist_detail::HasCreateSentinel<Traits>::value,
+                "ilist sentinel is not customizable!");
 #endif
 
-  mutable NodeTy *Head;
+  ilist_sentinel<NodeTy> Sentinel;
 
-  // Use the prev node pointer of 'head' as the tail pointer.  This is really a
-  // circularly linked list where we snip the 'next' link from the sentinel node
-  // back to the first node in the list (to preserve assertions about going off
-  // the end of the list).
-  NodeTy *getTail() { return this->ensureHead(Head); }
-  const NodeTy *getTail() const { return this->ensureHead(Head); }
-  void setTail(NodeTy *N) const { this->noteHead(Head, N); }
-
-  /// CreateLazySentinel - This method verifies whether the sentinel for the
-  /// list has been created and lazily makes it if not.
-  void CreateLazySentinel() const {
-    this->ensureHead(Head);
-  }
+  typedef ilist_node<NodeTy> node_type;
+  typedef const ilist_node<NodeTy> const_node_type;
 
   static bool op_less(NodeTy &L, NodeTy &R) { return L < R; }
   static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; }
 
-  // No fundamental reason why iplist can't be copyable, but the default
-  // copy/copy-assign won't do.
+  // Copying intrusively linked nodes doesn't make sense.
   iplist(const iplist &) = delete;
   void operator=(const iplist &) = delete;
 
 public:
   typedef NodeTy *pointer;
   typedef const NodeTy *const_pointer;
   typedef NodeTy &reference;
   typedef const NodeTy &const_reference;
   typedef NodeTy value_type;
   typedef ilist_iterator<NodeTy> iterator;
   typedef ilist_iterator<const NodeTy> const_iterator;
   typedef size_t size_type;
   typedef ptrdiff_t difference_type;
   typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
   typedef std::reverse_iterator<iterator>  reverse_iterator;
 
-  iplist() : Head(this->provideInitialHead()) {}
-  ~iplist() {
-    if (!Head) return;
-    clear();
-    Traits::destroySentinel(getTail());
-  }
+  iplist() = default;
+  ~iplist() { clear(); }
 
   // Iterator creation methods.
-  iterator begin() {
-    CreateLazySentinel();
-    return iterator(Head);
-  }
-  const_iterator begin() const {
-    CreateLazySentinel();
-    return const_iterator(Head);
-  }
-  iterator end() {
-    CreateLazySentinel();
-    return iterator(getTail());
-  }
-  const_iterator end() const {
-    CreateLazySentinel();
-    return const_iterator(getTail());
-  }
+  iterator begin() { return ++iterator(Sentinel); }
+  const_iterator begin() const { return ++const_iterator(Sentinel); }
+  iterator end() { return iterator(Sentinel); }
+  const_iterator end() const { return const_iterator(Sentinel); }
 
   // reverse iterator creation methods.
   reverse_iterator rbegin()            { return reverse_iterator(end()); }
   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
   reverse_iterator rend()              { return reverse_iterator(begin()); }
   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
 
 
   // Miscellaneous inspection routines.
   size_type max_size() const { return size_type(-1); }
-  bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {
-    return !Head || Head == getTail();
-  }
+  bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return Sentinel.empty(); }
 
   // Front and back accessor functions...
   reference front() {
     assert(!empty() && "Called front() on empty list!");
-    return *Head;
+    return *begin();
   }
   const_reference front() const {
     assert(!empty() && "Called front() on empty list!");
-    return *Head;
+    return *begin();
   }
   reference back() {
     assert(!empty() && "Called back() on empty list!");
-    return *this->getPrev(getTail());
+    return *--end();
   }
   const_reference back() const {
     assert(!empty() && "Called back() on empty list!");
-    return *this->getPrev(getTail());
+    return *--end();
   }
 
   void swap(iplist &RHS) {
     assert(0 && "Swap does not use list traits callback correctly yet!");
-    std::swap(Head, RHS.Head);
+    std::swap(Sentinel, RHS.Sentinel);
   }
 
   iterator insert(iterator where, NodeTy *New) {
-    NodeTy *CurNode = where.getNodePtrUnchecked();
-    NodeTy *PrevNode = this->getPrev(CurNode);
-    this->setNext(New, CurNode);
-    this->setPrev(New, PrevNode);
-
-    if (CurNode != Head)  // Is PrevNode off the beginning of the list?
-      this->setNext(PrevNode, New);
-    else
-      Head = New;
-    this->setPrev(CurNode, New);
+    node_type *NewN = this->getNodePtr(New);
+    node_type *Next = where.getNodePtr();
+    node_type *Prev = this->getPrev(Next);
+    this->setNext(NewN, Next);
+    this->setPrev(NewN, Prev);
+    this->setNext(Prev, NewN);
+    this->setPrev(Next, NewN);
 
     this->addNodeToList(New);  // Notify traits that we added a node...
     return iterator(New);
   }
 
   iterator insert(iterator where, const NodeTy &New) {
     return this->insert(where, new NodeTy(New));
   }
 
   iterator insertAfter(iterator where, NodeTy *New) {
     if (empty())
       return insert(begin(), New);
     else
       return insert(++where, New);
   }
 
   NodeTy *remove(iterator &IT) {
     assert(IT != end() && "Cannot remove end of list!");
     NodeTy *Node = &*IT;
-    NodeTy *NextNode = this->getNext(Node);
-    NodeTy *PrevNode = this->getPrev(Node);
+    node_type *Base = this->getNodePtr(Node);
+    node_type *Next = this->getNext(Base);
+    node_type *Prev = this->getPrev(Base);
 
-    if (Node != Head)  // Is PrevNode off the beginning of the list?
-      this->setNext(PrevNode, NextNode);
-    else
-      Head = NextNode;
-    this->setPrev(NextNode, PrevNode);
-    IT.reset(NextNode);
+    this->setNext(Prev, Next);
+    this->setPrev(Next, Prev);
+    IT = iterator(*Next);
     this->removeNodeFromList(Node);  // Notify traits that we removed a node...
 
     // Set the next/prev pointers of the current node to null.  This isn't
     // strictly required, but this catches errors where a node is removed from
     // an ilist (and potentially deleted) with iterators still pointing at it.
-    // When those iterators are incremented or decremented, they will assert on
-    // the null next/prev pointer instead of "usually working".
-    this->setNext(Node, nullptr);
-    this->setPrev(Node, nullptr);
+    // After those iterators are incremented or decremented, they become
+    // default-constructed iterators, and will assert on increment, decrement,
+    // and dereference instead of "usually working".
+    this->setNext(Base, nullptr);
+    this->setPrev(Base, nullptr);
     return Node;
   }
 
   NodeTy *remove(const iterator &IT) {
     iterator MutIt = IT;
     return remove(MutIt);
   }
 
public:
   iterator erase(NodeTy *IT) { return erase(iterator(IT)); }
   iterator erase(NodeTy &IT) { return erase(iterator(IT)); }
 
   /// Remove all nodes from the list like clear(), but do not call
   /// removeNodeFromList() or deleteNode().
   ///
   /// This should only be used immediately before freeing nodes in bulk to
   /// avoid traversing the list and bringing all the nodes into cache.
-  void clearAndLeakNodesUnsafely() {
-    if (Head) {
-      Head = getTail();
-      this->setPrev(Head, Head);
-    }
-  }
+  void clearAndLeakNodesUnsafely() { Sentinel.reset(); }
 
 private:
   // transfer - The heart of the splice function.  Move linked list nodes from
   // [first, last) into position.
   //
   void transfer(iterator position, iplist &L2, iterator first, iterator last) {
     assert(first != last && "Should be checked by callers");
     // Position cannot be contained in the range to be transferred.
-    // Check for the most common mistake.
     assert(position != first &&
+           // Check for the most common mistake.
            "Insertion point can't be one of the transferred nodes");
 
-    if (position != last) {
-      // Note: we have to be careful about the case when we move the first node
-      // in the list.  This node is the list sentinel node and we can't move it.
-      NodeTy *ThisSentinel = getTail();
-      setTail(nullptr);
-      NodeTy *L2Sentinel = L2.getTail();
-      L2.setTail(nullptr);
-
-      // Remove [first, last) from its old position.
-      NodeTy *First = &*first, *Prev = this->getPrev(First);
-      NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next);
-      if (Prev)
-        this->setNext(Prev, Next);
-      else
-        L2.Head = Next;
-      this->setPrev(Next, Prev);
+    if (position == last)
+      return;
+
+    // Get raw hooks to the first and final nodes being transferred.
+    node_type *First = first.getNodePtr();
+    node_type *Final = (--last).getNodePtr();
+
+    // Detach from old list/position.
+    node_type *Prev = this->getPrev(First);
+    node_type *Next = this->getNext(Final);
 
-      // Splice [first, last) into its new position.
-      NodeTy *PosNext = position.getNodePtrUnchecked();
-      NodeTy *PosPrev = this->getPrev(PosNext);
-
-      // Fix head of list...
-      if (PosPrev)
-        this->setNext(PosPrev, First);
-      else
-        Head = First;
-      this->setPrev(First, PosPrev);
-
-      // Fix end of list...
-      this->setNext(Last, PosNext);
-      this->setPrev(PosNext, Last);
-
-      this->transferNodesFromList(L2, iterator(First), iterator(PosNext));
-
-      // Now that everything is set, restore the pointers to the list sentinels.
-      L2.setTail(L2Sentinel);
-      setTail(ThisSentinel);
-    }
+    // Splice [First, Final] into its new list/position.
+    Next = position.getNodePtr();
+    Prev = this->getPrev(Next);
+    this->setNext(Final, Next);
+    this->setPrev(First, Prev);
+    this->setNext(Prev, First);
+    this->setPrev(Next, Final);
+
+    // Callback.  Note that the nodes have moved from before-last to
+    // before-position.
+    this->transferNodesFromList(L2, first, position);
   }
 
 public:
 
   //===----------------------------------------------------------------------===
   // Functionality derived from other functions defined above...
   //
 
   size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const {
-    if (!Head) return 0; // Don't require construction of sentinel if empty.
     return std::distance(begin(), end());
   }
 
   iterator erase(iterator first, iterator last) {
     while (first != last)
       first = erase(first);
     return last;
   }
 
-  void clear() { if (Head) erase(begin(), end()); }
+  void clear() { erase(begin(), end()); }
 
   // Front and back inserters...
   void push_front(NodeTy *val) { insert(begin(), val); }
   void push_back(NodeTy *val) { insert(end(), val); }
   void pop_front() {
     assert(!empty() && "pop_front() on empty list!");
     erase(begin());
   }

include/llvm/ADT/ilist_node.h

 // This file defines the ilist_node class template, which is a convenient
 // base class for creating classes that can be used with ilists.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_ILIST_NODE_H
 #define LLVM_ADT_ILIST_NODE_H
 
+#include <llvm/ADT/PointerIntPair.h>
+
 namespace llvm {
 
 template<typename NodeTy>
 struct ilist_traits;
 template <typename NodeTy> struct ilist_embedded_sentinel_traits;
 template <typename NodeTy> struct ilist_half_embedded_sentinel_traits;
 
-/// ilist_half_node - Base class that provides prev services for sentinels.
-///
-template<typename NodeTy>
-class ilist_half_node {
-  friend struct ilist_traits<NodeTy>;
-  friend struct ilist_half_embedded_sentinel_traits<NodeTy>;
-  NodeTy *Prev;
-protected:
-  NodeTy *getPrev() { return Prev; }
-  const NodeTy *getPrev() const { return Prev; }
-  void setPrev(NodeTy *P) { Prev = P; }
-  ilist_half_node() : Prev(nullptr) {}
+/// Base class for ilist nodes.
+struct ilist_node_base {
+#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
+  PointerIntPair<ilist_node_base *, 1> PrevAndSentinel;
+
+  void setPrev(ilist_node_base *Prev) { PrevAndSentinel.setPointer(Prev); }
+  ilist_node_base *getPrev() const { return PrevAndSentinel.getPointer(); }
+
+  bool isKnownSentinel() const { return PrevAndSentinel.getInt(); }
+  void initializeSentinel() { PrevAndSentinel.setInt(true); }
+#else
+  ilist_node_base *Prev = nullptr;
+
+  void setPrev(ilist_node_base *Prev) { this->Prev = Prev; }
+  ilist_node_base *getPrev() const { return Prev; }
+
+  bool isKnownSentinel() const { return false; }
+  void initializeSentinel() {}
+#endif
+
+  ilist_node_base *Next = nullptr;
 };
 
 struct ilist_node_access;
 template <typename NodeTy> class ilist_iterator;
+template <typename NodeTy> class ilist_sentinel;
 
-/// Base class that provides next/prev services for ilist nodes.
-template<typename NodeTy>
-class ilist_node : private ilist_half_node<NodeTy> {
+/// Templated wrapper class.
+template <typename NodeTy> class ilist_node : ilist_node_base {
   friend struct ilist_node_access;
   friend struct ilist_traits<NodeTy>;
   friend struct ilist_half_embedded_sentinel_traits<NodeTy>;
   friend struct ilist_embedded_sentinel_traits<NodeTy>;
-  NodeTy *Next;
-  NodeTy *getNext() { return Next; }
-  const NodeTy *getNext() const { return Next; }
-  void setNext(NodeTy *N) { Next = N; }
+  friend class ilist_iterator<NodeTy>;
+  friend class ilist_sentinel<NodeTy>;
+
 protected:
-  ilist_node() : Next(nullptr) {}
+  ilist_node() = default;
 
-public:
-  ilist_iterator<NodeTy> getIterator() {
-    // FIXME: Stop downcasting to create the iterator (potential UB).
-    return ilist_iterator<NodeTy>(static_cast<NodeTy *>(this));
+private:
+  ilist_node *getPrev() {
+    return static_cast<ilist_node *>(ilist_node_base::getPrev());
   }
+  ilist_node *getNext() { return static_cast<ilist_node *>(Next); }
+
+  const ilist_node *getPrev() const {
+    return static_cast<ilist_node *>(ilist_node_base::getPrev());
+  }
+  const ilist_node *getNext() const { return static_cast<ilist_node *>(Next); }
+
+  void setPrev(ilist_node *N) { ilist_node_base::setPrev(N); }
+  void setNext(ilist_node *N) { Next = N; }
+
+public:
+  ilist_iterator<NodeTy> getIterator() { return ilist_iterator<NodeTy>(*this); }
   ilist_iterator<const NodeTy> getIterator() const {
-    // FIXME: Stop downcasting to create the iterator (potential UB).
-    return ilist_iterator<const NodeTy>(static_cast<const NodeTy *>(this));
+    return ilist_iterator<const NodeTy>(*this);
   }
+
+  using ilist_node_base::isKnownSentinel;
+};
+
+template <typename NodeTy> class ilist_sentinel : public ilist_node<NodeTy> {
+public:
+  ilist_sentinel() {
+    ilist_node_base::initializeSentinel();
+    reset();
+  }
+
+  void reset() {
+    this->setPrev(this);
+    this->setNext(this);
+  }
+
+  bool empty() const { return this == this->getPrev(); }
 };
 
 /// An ilist node that can access its parent list.
 ///
 /// Requires \c NodeTy to have \a getParent() to find the parent node, and the
 /// \c ParentTy to have \a getSublistAccess() to get a reference to the list.
 template <typename NodeTy, typename ParentTy>
 class ilist_node_with_parent : public ilist_node<NodeTy> {

unittests/ADT/ilistTest.cpp

TEST(ilistTest, UnsafeClear) {
   // List is still functional.
   List.push_back(5);
   List.push_back(6);
   ASSERT_EQ(2u, List.size());
   EXPECT_EQ(5, List.front().Value);
   EXPECT_EQ(6, List.back().Value);
 }
 
+struct NodeWithCallback : ilist_node<NodeWithCallback> {
+  int Value = 0;
+  bool IsInList = false;
+
+  NodeWithCallback() = default;
+  NodeWithCallback(int Value) : Value(Value) {}
+  NodeWithCallback(const NodeWithCallback &) = delete;
+};
+
+} // end namespace
+
+namespace llvm {
+template <>
+struct ilist_traits<NodeWithCallback>
+    : public ilist_node_traits<NodeWithCallback> {
+  void addNodeToList(NodeWithCallback *N) { N->IsInList = true; }
+  void removeNodeFromList(NodeWithCallback *N) { N->IsInList = false; }
+};
+} // end namespace llvm
+
+namespace {
+
+TEST(ilistTest, addNodeToList) {
+  ilist<NodeWithCallback> L;
+  NodeWithCallback N(7);
+  ASSERT_FALSE(N.IsInList);
+
+  L.insert(L.begin(), &N);
+  ASSERT_EQ(1u, L.size());
+  ASSERT_EQ(&N, &*L.begin());
+  ASSERT_TRUE(N.IsInList);
+
+  L.remove(&N);
+  ASSERT_EQ(0u, L.size());
+  ASSERT_FALSE(N.IsInList);
 }
+
+struct PrivateNode : private ilist_node<PrivateNode> {
+  friend struct llvm::ilist_node_access;
+
+  int Value = 0;
+
+  PrivateNode() = default;
+  PrivateNode(int Value) : Value(Value) {}
+  PrivateNode(const PrivateNode &) = delete;
+};
+
+TEST(ilistTest, privateNode) {
+  // Instantiate various APIs to be sure they're callable when ilist_node is
+  // inherited privately.
+  ilist<NodeWithCallback> L;
+  NodeWithCallback N(7);
+  L.insert(L.begin(), &N);
+  ++L.begin();
+  (void)*L.begin();
+  (void)(L.begin() == L.end());
+
+  ilist<NodeWithCallback> L2;
+  L2.splice(L2.end(), L);
+  L2.remove(&N);
+}
+
+} // end namespace