[LLVM] Add option to store Parent-pointer in ilist_node_base (#94224)

This patch adds a new option for `ilist`, `ilist_parent<ParentTy>`, that
enables storing an additional pointer in the `ilist_node_base` type to a
specified "parent" type, and uses that option for `Instruction`.

This is distinct from the `ilist_node_with_parent` class, despite their
apparent similarities. The `ilist_node_with_parent` class is a subclass
of `ilist_node` that requires its own subclasses to define a `getParent`
method, which is then used by the owning `ilist` for some of its
operations; it is purely an interface declaration. The `ilist_parent`
option on the other hand is concerned with data, adding a parent field
to the `ilist_node_base` class.

Currently, we can use `BasicBlock::iterator` to insert instructions,
_except_ when either the iterator is invalid (`NodePtr=0x0`), or when
the iterator points to a sentinel value (`BasicBlock::end()`). This patch
results in the sentinel value also having a valid pointer to its owning
basic block, which allows us to use iterators for all insertions,
without needing to store or pass an extra `BasicBlock *BB` argument
alongside it.

15 files changed, 345 insertions, 63 deletions

diff --git a/llvm/include/llvm/ADT/ilist_base.h b/llvm/include/llvm/ADT/ilist_base.h
index b8c098b..000253a 100644
--- a/llvm/include/llvm/ADT/ilist_base.h
+++ b/llvm/include/llvm/ADT/ilist_base.h
@@ -15,9 +15,9 @@
 namespace llvm {
 
 /// Implementations of list algorithms using ilist_node_base.
-template <bool EnableSentinelTracking> class ilist_base {
+template <bool EnableSentinelTracking, class ParentPtrTy> class ilist_base {
 public:
-  using node_base_type = ilist_node_base<EnableSentinelTracking>;
+  using node_base_type = ilist_node_base<EnableSentinelTracking, ParentPtrTy>;
 
   static void insertBeforeImpl(node_base_type &Next, node_base_type &N) {
     node_base_type &Prev = *Next.getPrev();
diff --git a/llvm/include/llvm/ADT/ilist_iterator.h b/llvm/include/llvm/ADT/ilist_iterator.h
index 2393c4d..16a45b5 100644
--- a/llvm/include/llvm/ADT/ilist_iterator.h
+++ b/llvm/include/llvm/ADT/ilist_iterator.h
@@ -50,14 +50,44 @@ template <> struct IteratorHelper<true> : ilist_detail::NodeAccess {
   template <class T> static void decrement(T *&I) { I = Access::getNext(*I); }
 };
 
+/// Mixin class used to add a \a getNodeParent() function to iterators iff the
+/// list uses \a ilist_parent, calling through to the node's \a getParent(). For
+/// more details see \a ilist_node.
+template <class IteratorTy, class ParentPtrTy, bool IsConst>
+class iterator_parent_access;
+template <class IteratorTy, class ParentPtrTy>
+class iterator_parent_access<IteratorTy, ParentPtrTy, true> {
+public:
+  inline const ParentPtrTy getNodeParent() const {
+    return static_cast<IteratorTy *>(this)->NodePtr->getParent();
+  }
+};
+template <class IteratorTy, class ParentPtrTy>
+class iterator_parent_access<IteratorTy, ParentPtrTy, false> {
+public:
+  inline ParentPtrTy getNodeParent() {
+    return static_cast<IteratorTy *>(this)->NodePtr->getParent();
+  }
+};
+template <class IteratorTy>
+class iterator_parent_access<IteratorTy, void, true> {};
+template <class IteratorTy>
+class iterator_parent_access<IteratorTy, void, false> {};
+
 } // end namespace ilist_detail
 
 /// Iterator for intrusive lists  based on ilist_node.
 template <class OptionsT, bool IsReverse, bool IsConst>
-class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> {
+class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT>,
+                       public ilist_detail::iterator_parent_access<
+                           ilist_iterator<OptionsT, IsReverse, IsConst>,
+                           typename OptionsT::parent_ptr_ty, IsConst> {
   friend ilist_iterator<OptionsT, IsReverse, !IsConst>;
   friend ilist_iterator<OptionsT, !IsReverse, IsConst>;
   friend ilist_iterator<OptionsT, !IsReverse, !IsConst>;
+  friend ilist_detail::iterator_parent_access<
+                           ilist_iterator<OptionsT, IsReverse, IsConst>,
+                           typename OptionsT::parent_ptr_ty, IsConst>;
 
   using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
   using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
@@ -168,6 +198,8 @@ public:
     return tmp;
   }
 
+  bool isValid() const { return NodePtr; }
+
   /// Get the underlying ilist_node.
   node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
 
@@ -179,10 +211,17 @@ public:
 /// but with the addition of two bits recording whether this position (when in
 /// a range) is half or fully open.
 template <class OptionsT, bool IsReverse, bool IsConst>
-class ilist_iterator_w_bits : ilist_detail::SpecificNodeAccess<OptionsT> {
+class ilist_iterator_w_bits
+    : ilist_detail::SpecificNodeAccess<OptionsT>,
+      public ilist_detail::iterator_parent_access<
+          ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>,
+          typename OptionsT::parent_ptr_ty, IsConst> {
   friend ilist_iterator_w_bits<OptionsT, IsReverse, !IsConst>;
   friend ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>;
   friend ilist_iterator<OptionsT, !IsReverse, !IsConst>;
+  friend ilist_detail::iterator_parent_access<
+                           ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>,
+                           typename OptionsT::parent_ptr_ty, IsConst>;
 
   using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
   using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
@@ -319,6 +358,8 @@ public:
     return tmp;
   }
 
+  bool isValid() const { return NodePtr; }
+
   /// Get the underlying ilist_node.
   node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
 
diff --git a/llvm/include/llvm/ADT/ilist_node.h b/llvm/include/llvm/ADT/ilist_node.h
index 3b6f0dc..209fd20 100644
--- a/llvm/include/llvm/ADT/ilist_node.h
+++ b/llvm/include/llvm/ADT/ilist_node.h
@@ -24,6 +24,23 @@ namespace ilist_detail {
 
 struct NodeAccess;
 
+/// Mixin base class that is used to add \a getParent() and
+/// \a setParent(ParentPtrTy) methods to \a ilist_node_impl iff \a ilist_parent
+/// has been set in the list options.
+template <class NodeTy, class ParentPtrTy> class node_parent_access {
+public:
+  inline const ParentPtrTy getParent() const {
+    return static_cast<const NodeTy *>(this)->getNodeBaseParent();
+  }
+  inline ParentPtrTy getParent() {
+    return static_cast<NodeTy *>(this)->getNodeBaseParent();
+  }
+  void setParent(ParentPtrTy Parent) {
+    return static_cast<NodeTy *>(this)->setNodeBaseParent(Parent);
+  }
+};
+template <class NodeTy> class node_parent_access<NodeTy, void> {};
+
 } // end namespace ilist_detail
 
 template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
@@ -51,7 +68,11 @@ public:
 /// This is a wrapper around \a ilist_node_base whose main purpose is to
 /// provide type safety: you can't insert nodes of \a ilist_node_impl into the
 /// wrong \a simple_ilist or \a iplist.
-template <class OptionsT> class ilist_node_impl : OptionsT::node_base_type {
+template <class OptionsT>
+class ilist_node_impl
+    : OptionsT::node_base_type,
+      public ilist_detail::node_parent_access<
+          ilist_node_impl<OptionsT>, typename OptionsT::parent_ptr_ty> {
   using value_type = typename OptionsT::value_type;
   using node_base_type = typename OptionsT::node_base_type;
   using list_base_type = typename OptionsT::list_base_type;
@@ -60,6 +81,8 @@ template <class OptionsT> class ilist_node_impl : OptionsT::node_base_type {
   friend struct ilist_detail::NodeAccess;
   friend class ilist_sentinel<OptionsT>;
 
+  friend class ilist_detail::node_parent_access<
+      ilist_node_impl<OptionsT>, typename OptionsT::parent_ptr_ty>;
   friend class ilist_iterator<OptionsT, false, false>;
   friend class ilist_iterator<OptionsT, false, true>;
   friend class ilist_iterator<OptionsT, true, false>;
@@ -171,6 +194,20 @@ public:
 /// }
 /// \endexample
 ///
+/// When the \a ilist_parent<ParentTy> option is passed to an ilist_node and the
+/// owning ilist, each node contains a pointer to the ilist's owner. This adds
+/// \a getParent() and \a setParent(ParentTy*) methods to the ilist_node, which
+/// will be used for node access by the ilist if the node class publicly
+/// inherits from \a ilist_node_with_parent. By default, setParent() is not
+/// automatically called by the ilist; a SymbolTableList will call setParent()
+/// on inserted nodes, but the sentinel must still be manually set after the
+/// list is created (e.g. SymTabList.end()->setParent(Parent)).
+///
+/// The primary benefit of using ilist_parent is that a parent
+/// pointer will be stored in the sentinel, meaning that you can safely use \a
+/// ilist_iterator::getNodeParent() to get the node parent from any valid (i.e.
+/// non-null) iterator, even one that points to a sentinel value.
+///
 /// See \a is_valid_option for steps on adding a new option.
 template <class T, class... Options>
 class ilist_node
diff --git a/llvm/include/llvm/ADT/ilist_node_base.h b/llvm/include/llvm/ADT/ilist_node_base.h
index f6c518e..caad87c 100644
--- a/llvm/include/llvm/ADT/ilist_node_base.h
+++ b/llvm/include/llvm/ADT/ilist_node_base.h
@@ -13,40 +13,61 @@
 
 namespace llvm {
 
-/// Base class for ilist nodes.
-///
-/// Optionally tracks whether this node is the sentinel.
-template <bool EnableSentinelTracking> class ilist_node_base;
+namespace ilist_detail {
+
+template <class NodeBase, bool EnableSentinelTracking> class node_base_prevnext;
 
-template <> class ilist_node_base<false> {
-  ilist_node_base *Prev = nullptr;
-  ilist_node_base *Next = nullptr;
+template <class NodeBase> class node_base_prevnext<NodeBase, false> {
+  NodeBase *Prev = nullptr;
+  NodeBase *Next = nullptr;
 
 public:
-  void setPrev(ilist_node_base *Prev) { this->Prev = Prev; }
-  void setNext(ilist_node_base *Next) { this->Next = Next; }
-  ilist_node_base *getPrev() const { return Prev; }
-  ilist_node_base *getNext() const { return Next; }
+  void setPrev(NodeBase *Prev) { this->Prev = Prev; }
+  void setNext(NodeBase *Next) { this->Next = Next; }
+  NodeBase *getPrev() const { return Prev; }
+  NodeBase *getNext() const { return Next; }
 
   bool isKnownSentinel() const { return false; }
   void initializeSentinel() {}
 };
 
-template <> class ilist_node_base<true> {
-  PointerIntPair<ilist_node_base *, 1> PrevAndSentinel;
-  ilist_node_base *Next = nullptr;
+template <class NodeBase> class node_base_prevnext<NodeBase, true> {
+  PointerIntPair<NodeBase *, 1> PrevAndSentinel;
+  NodeBase *Next = nullptr;
 
 public:
-  void setPrev(ilist_node_base *Prev) { PrevAndSentinel.setPointer(Prev); }
-  void setNext(ilist_node_base *Next) { this->Next = Next; }
-  ilist_node_base *getPrev() const { return PrevAndSentinel.getPointer(); }
-  ilist_node_base *getNext() const { return Next; }
+  void setPrev(NodeBase *Prev) { PrevAndSentinel.setPointer(Prev); }
+  void setNext(NodeBase *Next) { this->Next = Next; }
+  NodeBase *getPrev() const { return PrevAndSentinel.getPointer(); }
+  NodeBase *getNext() const { return Next; }
 
   bool isSentinel() const { return PrevAndSentinel.getInt(); }
   bool isKnownSentinel() const { return isSentinel(); }
   void initializeSentinel() { PrevAndSentinel.setInt(true); }
 };
 
+template <class ParentPtrTy> class node_base_parent {
+  ParentPtrTy Parent = nullptr;
+
+public:
+  void setNodeBaseParent(ParentPtrTy Parent) { this->Parent = Parent; }
+  inline const ParentPtrTy getNodeBaseParent() const { return Parent; }
+  inline ParentPtrTy getNodeBaseParent() { return Parent; }
+};
+template <> class node_base_parent<void> {};
+
+} // end namespace ilist_detail
+
+/// Base class for ilist nodes.
+///
+/// Optionally tracks whether this node is the sentinel.
+template <bool EnableSentinelTracking, class ParentPtrTy>
+class ilist_node_base
+    : public ilist_detail::node_base_prevnext<
+          ilist_node_base<EnableSentinelTracking, ParentPtrTy>,
+          EnableSentinelTracking>,
+      public ilist_detail::node_base_parent<ParentPtrTy> {};
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_ILIST_NODE_BASE_H
diff --git a/llvm/include/llvm/ADT/ilist_node_options.h b/llvm/include/llvm/ADT/ilist_node_options.h
index e6e1068..aa32162 100644
--- a/llvm/include/llvm/ADT/ilist_node_options.h
+++ b/llvm/include/llvm/ADT/ilist_node_options.h
@@ -15,8 +15,8 @@
 
 namespace llvm {
 
-template <bool EnableSentinelTracking> class ilist_node_base;
-template <bool EnableSentinelTracking> class ilist_base;
+template <bool EnableSentinelTracking, class ParentPtrTy> class ilist_node_base;
+template <bool EnableSentinelTracking, class ParentPtrTy> class ilist_base;
 
 /// Option to choose whether to track sentinels.
 ///
@@ -39,6 +39,19 @@ template <class Tag> struct ilist_tag {};
 /// iterator class to store that information.
 template <bool ExtraIteratorBits> struct ilist_iterator_bits {};
 
+/// Option to add a pointer to this list's owner in every node.
+///
+/// This option causes the \a ilist_base_node for this list to contain a pointer
+/// ParentTy *Parent, returned by \a ilist_base_node::getNodeBaseParent() and
+/// set by \a ilist_base_node::setNodeBaseParent(ParentTy *Parent). The parent
+/// value is not set automatically; the ilist owner should set itself as the
+/// parent of the list sentinel, and the parent should be set on each node
+/// inserted into the list. This value is also not used by
+/// \a ilist_node_with_parent::getNodeParent(), but is used by \a
+/// ilist_iterator::getNodeParent(), which allows the parent to be fetched from
+/// any valid (non-null) iterator to this list, including the sentinel.
+template <class ParentTy> struct ilist_parent {};
+
 namespace ilist_detail {
 
 /// Helper trait for recording whether an option is specified explicitly.
@@ -114,6 +127,21 @@ template <> struct extract_iterator_bits<> : std::false_type, is_implicit {};
 template <bool IteratorBits>
 struct is_valid_option<ilist_iterator_bits<IteratorBits>> : std::true_type {};
 
+/// Extract node parent option.
+///
+/// Look through \p Options for the \a ilist_parent option, pulling out the
+/// custom parent type, using void as a default.
+template <class... Options> struct extract_parent;
+template <class ParentTy, class... Options>
+struct extract_parent<ilist_parent<ParentTy>, Options...> {
+  typedef ParentTy *type;
+};
+template <class Option1, class... Options>
+struct extract_parent<Option1, Options...> : extract_parent<Options...> {};
+template <> struct extract_parent<> { typedef void type; };
+template <class ParentTy>
+struct is_valid_option<ilist_parent<ParentTy>> : std::true_type {};
+
 /// Check whether options are valid.
 ///
 /// The conjunction of \a is_valid_option on each individual option.
@@ -128,7 +156,7 @@ struct check_options<Option1, Options...>
 ///
 /// This is usually computed via \a compute_node_options.
 template <class T, bool EnableSentinelTracking, bool IsSentinelTrackingExplicit,
-          class TagT, bool HasIteratorBits>
+          class TagT, bool HasIteratorBits, class ParentPtrTy>
 struct node_options {
   typedef T value_type;
   typedef T *pointer;
@@ -140,15 +168,18 @@ struct node_options {
   static const bool is_sentinel_tracking_explicit = IsSentinelTrackingExplicit;
   static const bool has_iterator_bits = HasIteratorBits;
   typedef TagT tag;
-  typedef ilist_node_base<enable_sentinel_tracking> node_base_type;
-  typedef ilist_base<enable_sentinel_tracking> list_base_type;
+  typedef ParentPtrTy parent_ptr_ty;
+  typedef ilist_node_base<enable_sentinel_tracking, parent_ptr_ty>
+      node_base_type;
+  typedef ilist_base<enable_sentinel_tracking, parent_ptr_ty> list_base_type;
 };
 
 template <class T, class... Options> struct compute_node_options {
   typedef node_options<T, extract_sentinel_tracking<Options...>::value,
                        extract_sentinel_tracking<Options...>::is_explicit,
                        typename extract_tag<Options...>::type,
-                       extract_iterator_bits<Options...>::value>
+                       extract_iterator_bits<Options...>::value,
+                       typename extract_parent<Options...>::type>
       type;
 };
 
diff --git a/llvm/include/llvm/IR/BasicBlock.h b/llvm/include/llvm/IR/BasicBlock.h
index e122096..80067f2 100644
--- a/llvm/include/llvm/IR/BasicBlock.h
+++ b/llvm/include/llvm/IR/BasicBlock.h
@@ -59,7 +59,8 @@ class DbgMarker;
 class BasicBlock final : public Value, // Basic blocks are data objects also
                          public ilist_node_with_parent<BasicBlock, Function> {
 public:
-  using InstListType = SymbolTableList<Instruction, ilist_iterator_bits<true>>;
+  using InstListType = SymbolTableList<Instruction, ilist_iterator_bits<true>,
+                                       ilist_parent<BasicBlock>>;
   /// Flag recording whether or not this block stores debug-info in the form
   /// of intrinsic instructions (false) or non-instruction records (true).
   bool IsNewDbgInfoFormat;
@@ -172,10 +173,11 @@ public:
   friend BasicBlock::iterator Instruction::eraseFromParent();
   friend BasicBlock::iterator Instruction::insertInto(BasicBlock *BB,
                                                       BasicBlock::iterator It);
-  friend class llvm::SymbolTableListTraits<llvm::Instruction,
-                                           ilist_iterator_bits<true>>;
+  friend class llvm::SymbolTableListTraits<
+      llvm::Instruction, ilist_iterator_bits<true>, ilist_parent<BasicBlock>>;
   friend class llvm::ilist_node_with_parent<llvm::Instruction, llvm::BasicBlock,
-                                            ilist_iterator_bits<true>>;
+                                            ilist_iterator_bits<true>,
+                                            ilist_parent<BasicBlock>>;
 
   // Friendly methods that need to access us for the maintenence of
   // debug-info attachments.
diff --git a/llvm/include/llvm/IR/Instruction.h b/llvm/include/llvm/IR/Instruction.h
index 249be27..0b636fc7 100644
--- a/llvm/include/llvm/IR/Instruction.h
+++ b/llvm/include/llvm/IR/Instruction.h
@@ -46,11 +46,13 @@ getDbgRecordRange(DbgMarker *);
 
 class Instruction : public User,
                     public ilist_node_with_parent<Instruction, BasicBlock,
-                                                  ilist_iterator_bits<true>> {
+                                                  ilist_iterator_bits<true>,
+                                                  ilist_parent<BasicBlock>> {
 public:
-  using InstListType = SymbolTableList<Instruction, ilist_iterator_bits<true>>;
+  using InstListType = SymbolTableList<Instruction, ilist_iterator_bits<true>,
+                                       ilist_parent<BasicBlock>>;
+
 private:
-  BasicBlock *Parent;
   DebugLoc DbgLoc;                         // 'dbg' Metadata cache.
 
   /// Relative order of this instruction in its parent basic block. Used for
@@ -149,9 +151,6 @@ public:
   Instruction       *user_back()       { return cast<Instruction>(*user_begin());}
   const Instruction *user_back() const { return cast<Instruction>(*user_begin());}
 
-  inline const BasicBlock *getParent() const { return Parent; }
-  inline       BasicBlock *getParent()       { return Parent; }
-
   /// Return the module owning the function this instruction belongs to
   /// or nullptr it the function does not have a module.
   ///
@@ -980,7 +979,8 @@ public:
   };
 
 private:
-  friend class SymbolTableListTraits<Instruction, ilist_iterator_bits<true>>;
+  friend class SymbolTableListTraits<Instruction, ilist_iterator_bits<true>,
+                                     ilist_parent<BasicBlock>>;
   friend class BasicBlock; // For renumbering.
 
   // Shadow Value::setValueSubclassData with a private forwarding method so that
@@ -993,8 +993,6 @@ private:
     return Value::getSubclassDataFromValue();
   }
 
-  void setParent(BasicBlock *P);
-
 protected:
   // Instruction subclasses can stick up to 15 bits of stuff into the
   // SubclassData field of instruction with these members.
diff --git a/llvm/include/llvm/IR/ValueSymbolTable.h b/llvm/include/llvm/IR/ValueSymbolTable.h
index 6350f6a..cd1dbbe 100644
--- a/llvm/include/llvm/IR/ValueSymbolTable.h
+++ b/llvm/include/llvm/IR/ValueSymbolTable.h
@@ -28,6 +28,7 @@ class GlobalIFunc;
 class GlobalVariable;
 class Instruction;
 template <bool ExtraIteratorBits> struct ilist_iterator_bits;
+template <class ParentTy> struct ilist_parent;
 template <unsigned InternalLen> class SmallString;
 template <typename ValueSubClass, typename ... Args> class SymbolTableListTraits;
 
@@ -42,7 +43,8 @@ class ValueSymbolTable {
   friend class SymbolTableListTraits<GlobalAlias>;
   friend class SymbolTableListTraits<GlobalIFunc>;
   friend class SymbolTableListTraits<GlobalVariable>;
-  friend class SymbolTableListTraits<Instruction, ilist_iterator_bits<true>>;
+  friend class SymbolTableListTraits<Instruction, ilist_iterator_bits<true>,
+                                     ilist_parent<BasicBlock>>;
   friend class Value;
 
 /// @name Types
diff --git a/llvm/lib/IR/BasicBlock.cpp b/llvm/lib/IR/BasicBlock.cpp
index aea9425..de32771 100644
--- a/llvm/lib/IR/BasicBlock.cpp
+++ b/llvm/lib/IR/BasicBlock.cpp
@@ -175,8 +175,8 @@ template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
 
 // Explicit instantiation of SymbolTableListTraits since some of the methods
 // are not in the public header file...
-template class llvm::SymbolTableListTraits<Instruction,
-                                           ilist_iterator_bits<true>>;
+template class llvm::SymbolTableListTraits<
+    Instruction, ilist_iterator_bits<true>, ilist_parent<BasicBlock>>;
 
 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
                        BasicBlock *InsertBefore)
@@ -189,6 +189,7 @@ BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
     assert(!InsertBefore &&
            "Cannot insert block before another block with no function!");
 
+  end().getNodePtr()->setParent(this);
   setName(Name);
   if (NewParent)
     setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat);
diff --git a/llvm/lib/IR/Instruction.cpp b/llvm/lib/IR/Instruction.cpp
index aec927a..de0de13 100644
--- a/llvm/lib/IR/Instruction.cpp
+++ b/llvm/lib/IR/Instruction.cpp
@@ -27,8 +27,7 @@ using namespace llvm;
 
 Instruction::Instruction(Type *ty, unsigned it, Use *Ops, unsigned NumOps,
                          InstListType::iterator InsertBefore)
-    : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(nullptr) {
-
+    : User(ty, Value::InstructionVal + it, Ops, NumOps) {
   // When called with an iterator, there must be a block to insert into.
   BasicBlock *BB = InsertBefore->getParent();
   assert(BB && "Instruction to insert before is not in a basic block!");
@@ -37,7 +36,7 @@ Instruction::Instruction(Type *ty, unsigned it, Use *Ops, unsigned NumOps,
 
 Instruction::Instruction(Type *ty, unsigned it, Use *Ops, unsigned NumOps,
                          Instruction *InsertBefore)
-  : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(nullptr) {
+    : User(ty, Value::InstructionVal + it, Ops, NumOps) {
 
   // If requested, insert this instruction into a basic block...
   if (InsertBefore) {
@@ -49,15 +48,14 @@ Instruction::Instruction(Type *ty, unsigned it, Use *Ops, unsigned NumOps,
 
 Instruction::Instruction(Type *ty, unsigned it, Use *Ops, unsigned NumOps,
                          BasicBlock *InsertAtEnd)
-    : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(nullptr) {
-
+    : User(ty, Value::InstructionVal + it, Ops, NumOps) {
   // If requested, append this instruction into the basic block.
   if (InsertAtEnd)
     insertInto(InsertAtEnd, InsertAtEnd->end());
 }
 
 Instruction::~Instruction() {
-  assert(!Parent && "Instruction still linked in the program!");
+  assert(!getParent() && "Instruction still linked in the program!");
 
   // Replace any extant metadata uses of this instruction with undef to
   // preserve debug info accuracy. Some alternatives include:
@@ -76,10 +74,6 @@ Instruction::~Instruction() {
   setMetadata(LLVMContext::MD_DIAssignID, nullptr);
 }
 
-void Instruction::setParent(BasicBlock *P) {
-  Parent = P;
-}
-
 const Module *Instruction::getModule() const {
   return getParent()->getModule();
 }
@@ -96,7 +90,7 @@ void Instruction::removeFromParent() {
 }
 
 void Instruction::handleMarkerRemoval() {
-  if (!Parent->IsNewDbgInfoFormat || !DebugMarker)
+  if (!getParent()->IsNewDbgInfoFormat || !DebugMarker)
     return;
 
   DebugMarker->removeMarker();
@@ -329,11 +323,12 @@ void Instruction::dropOneDbgRecord(DbgRecord *DVR) {
 }
 
 bool Instruction::comesBefore(const Instruction *Other) const {
-  assert(Parent && Other->Parent &&
+  assert(getParent() && Other->getParent() &&
          "instructions without BB parents have no order");
-  assert(Parent == Other->Parent && "cross-BB instruction order comparison");
-  if (!Parent->isInstrOrderValid())
-    Parent->renumberInstructions();
+  assert(getParent() == Other->getParent() &&
+         "cross-BB instruction order comparison");
+  if (!getParent()->isInstrOrderValid())
+    const_cast<BasicBlock *>(getParent())->renumberInstructions();
   return Order < Other->Order;
 }
 
diff --git a/llvm/unittests/ADT/IListBaseTest.cpp b/llvm/unittests/ADT/IListBaseTest.cpp
index 1c55eac..bd91568 100644
--- a/llvm/unittests/ADT/IListBaseTest.cpp
+++ b/llvm/unittests/ADT/IListBaseTest.cpp
@@ -16,8 +16,10 @@ namespace {
 // Test fixture.
 template <typename T> class IListBaseTest : public ::testing::Test {};
 
+class Parent;
+
 // Test variants with the same test.
-typedef ::testing::Types<ilist_base<false>, ilist_base<true>>
+typedef ::testing::Types<ilist_base<false, void>, ilist_base<true, void>, ilist_base<false, Parent*>, ilist_base<true, Parent*>>
     IListBaseTestTypes;
 TYPED_TEST_SUITE(IListBaseTest, IListBaseTestTypes, );
 
diff --git a/llvm/unittests/ADT/IListIteratorBitsTest.cpp b/llvm/unittests/ADT/IListIteratorBitsTest.cpp
index 8ae73b1..97c14265 100644
--- a/llvm/unittests/ADT/IListIteratorBitsTest.cpp
+++ b/llvm/unittests/ADT/IListIteratorBitsTest.cpp
@@ -27,6 +27,11 @@ struct PlainNode : ilist_node<PlainNode> {
   friend class dummy;
 };
 
+class Parent {};
+struct ParentNode
+    : ilist_node<ParentNode, ilist_iterator_bits<true>, ilist_parent<Parent>> {
+};
+
 TEST(IListIteratorBitsTest, DefaultConstructor) {
   simple_ilist<Node, ilist_iterator_bits<true>>::iterator I;
   simple_ilist<Node, ilist_iterator_bits<true>>::reverse_iterator RI;
@@ -121,4 +126,22 @@ TEST(IListIteratorBitsTest, RangeIteration) {
     (void)N;
 }
 
+TEST(IListIteratorBitsTest, GetParent) {
+  simple_ilist<ParentNode, ilist_iterator_bits<true>, ilist_parent<Parent>> L;
+  Parent P;
+  ParentNode A;
+
+  // Parents are not set automatically.
+  A.setParent(&P);
+  L.insert(L.end(), A);
+  L.end().getNodePtr()->setParent(&P);
+
+  // Check we can get the node parent from all iterators, including for the
+  // sentinel.
+  EXPECT_EQ(&P, L.begin().getNodeParent());
+  EXPECT_EQ(&P, L.end().getNodeParent());
+  EXPECT_EQ(&P, L.rbegin().getNodeParent());
+  EXPECT_EQ(&P, L.rend().getNodeParent());
+}
+
 } // end namespace
diff --git a/llvm/unittests/ADT/IListIteratorTest.cpp b/llvm/unittests/ADT/IListIteratorTest.cpp
index bd638a8..fd420b9 100644
--- a/llvm/unittests/ADT/IListIteratorTest.cpp
+++ b/llvm/unittests/ADT/IListIteratorTest.cpp
@@ -13,7 +13,10 @@ using namespace llvm;
 
 namespace {
 
+class Parent {};
+
 struct Node : ilist_node<Node> {};
+struct ParentNode : ilist_node<ParentNode, ilist_parent<Parent>> {};
 
 TEST(IListIteratorTest, DefaultConstructor) {
   simple_ilist<Node>::iterator I;
@@ -168,4 +171,22 @@ TEST(IListIteratorTest, ReverseConstructor) {
                 "unexpected implicit conversion");
 }
 
+TEST(IListIteratorTest, GetParent) {
+  simple_ilist<ParentNode, ilist_parent<Parent>> L;
+  Parent P;
+  ParentNode A;
+
+  // Parents are not set automatically.
+  A.setParent(&P);
+  L.insert(L.end(), A);
+  L.end().getNodePtr()->setParent(&P);
+
+  // Check we can get the node parent from all iterators, including for the
+  // sentinel.
+  EXPECT_EQ(&P, L.begin().getNodeParent());
+  EXPECT_EQ(&P, L.end().getNodeParent());
+  EXPECT_EQ(&P, L.rbegin().getNodeParent());
+  EXPECT_EQ(&P, L.rend().getNodeParent());
+}
+
 } // end namespace
diff --git a/llvm/unittests/ADT/IListNodeBaseTest.cpp b/llvm/unittests/ADT/IListNodeBaseTest.cpp
index 65f85fc..07f397d 100644
--- a/llvm/unittests/ADT/IListNodeBaseTest.cpp
+++ b/llvm/unittests/ADT/IListNodeBaseTest.cpp
@@ -13,8 +13,12 @@ using namespace llvm;
 
 namespace {
 
-typedef ilist_node_base<false> RawNode;
-typedef ilist_node_base<true> TrackingNode;
+class Parent {};
+
+typedef ilist_node_base<false, void> RawNode;
+typedef ilist_node_base<true, void> TrackingNode;
+typedef ilist_node_base<false, Parent*> ParentNode;
+typedef ilist_node_base<true, Parent*> ParentTrackingNode;
 
 TEST(IListNodeBaseTest, DefaultConstructor) {
   RawNode A;
@@ -27,6 +31,19 @@ TEST(IListNodeBaseTest, DefaultConstructor) {
   EXPECT_EQ(nullptr, TA.getNext());
   EXPECT_FALSE(TA.isKnownSentinel());
   EXPECT_FALSE(TA.isSentinel());
+
+  ParentNode PA;
+  EXPECT_EQ(nullptr, PA.getPrev());
+  EXPECT_EQ(nullptr, PA.getNext());
+  EXPECT_EQ(nullptr, PA.getNodeBaseParent());
+  EXPECT_FALSE(PA.isKnownSentinel());
+
+  ParentTrackingNode PTA;
+  EXPECT_EQ(nullptr, PTA.getPrev());
+  EXPECT_EQ(nullptr, PTA.getNext());
+  EXPECT_EQ(nullptr, PTA.getNodeBaseParent());
+  EXPECT_FALSE(PTA.isKnownSentinel());
+  EXPECT_FALSE(PTA.isSentinel());
 }
 
 TEST(IListNodeBaseTest, setPrevAndNext) {
@@ -63,6 +80,41 @@ TEST(IListNodeBaseTest, setPrevAndNext) {
   EXPECT_EQ(nullptr, TB.getNext());
   EXPECT_EQ(nullptr, TC.getPrev());
   EXPECT_EQ(nullptr, TC.getNext());
+
+  ParentNode PA, PB, PC;
+  PA.setPrev(&PB);
+  EXPECT_EQ(&PB, PA.getPrev());
+  EXPECT_EQ(nullptr, PA.getNext());
+  EXPECT_EQ(nullptr, PB.getPrev());
+  EXPECT_EQ(nullptr, PB.getNext());
+  EXPECT_EQ(nullptr, PC.getPrev());
+  EXPECT_EQ(nullptr, PC.getNext());
+
+  PA.setNext(&PC);
+  EXPECT_EQ(&PB, PA.getPrev());
+  EXPECT_EQ(&PC, PA.getNext());
+  EXPECT_EQ(nullptr, PB.getPrev());
+  EXPECT_EQ(nullptr, PB.getNext());
+  EXPECT_EQ(nullptr, PC.getPrev());
+  EXPECT_EQ(nullptr, PC.getNext());
+
+  ParentTrackingNode PTA, PTB, PTC;
+  PTA.setPrev(&PTB);
+  EXPECT_EQ(&PTB, PTA.getPrev());
+  EXPECT_EQ(nullptr, PTA.getNext());
+  EXPECT_EQ(nullptr, PTB.getPrev());
+  EXPECT_EQ(nullptr, PTB.getNext());
+  EXPECT_EQ(nullptr, PTC.getPrev());
+  EXPECT_EQ(nullptr, PTC.getNext());
+
+  PTA.setNext(&PTC);
+  EXPECT_EQ(&PTB, PTA.getPrev());
+  EXPECT_EQ(&PTC, PTA.getNext());
+  EXPECT_EQ(nullptr, PTB.getPrev());
+  EXPECT_EQ(nullptr, PTB.getNext());
+  EXPECT_EQ(nullptr, PTC.getPrev());
+  EXPECT_EQ(nullptr, PTC.getNext());
+
 }
 
 TEST(IListNodeBaseTest, isKnownSentinel) {
@@ -94,6 +146,48 @@ TEST(IListNodeBaseTest, isKnownSentinel) {
   EXPECT_TRUE(TA.isSentinel());
   EXPECT_EQ(&TB, TA.getPrev());
   EXPECT_EQ(&TB, TA.getNext());
+
+  // Without sentinel tracking (with Parent).
+  ParentNode PA, PB;
+  EXPECT_FALSE(PA.isKnownSentinel());
+  PA.setPrev(&PB);
+  PA.setNext(&PB);
+  EXPECT_EQ(&PB, PA.getPrev());
+  EXPECT_EQ(&PB, PA.getNext());
+  EXPECT_FALSE(PA.isKnownSentinel());
+  PA.initializeSentinel();
+  EXPECT_FALSE(PA.isKnownSentinel());
+  EXPECT_EQ(&PB, PA.getPrev());
+  EXPECT_EQ(&PB, PA.getNext());
+
+  // With sentinel tracking (with Parent).
+  ParentTrackingNode PTA, PTB;
+  EXPECT_FALSE(PTA.isKnownSentinel());
+  EXPECT_FALSE(PTA.isSentinel());
+  PTA.setPrev(&PTB);
+  PTA.setNext(&PTB);
+  EXPECT_EQ(&PTB, PTA.getPrev());
+  EXPECT_EQ(&PTB, PTA.getNext());
+  EXPECT_FALSE(PTA.isKnownSentinel());
+  EXPECT_FALSE(PTA.isSentinel());
+  PTA.initializeSentinel();
+  EXPECT_TRUE(PTA.isKnownSentinel());
+  EXPECT_TRUE(PTA.isSentinel());
+  EXPECT_EQ(&PTB, PTA.getPrev());
+  EXPECT_EQ(&PTB, PTA.getNext());
+}
+
+TEST(IListNodeBaseTest, setNodeBaseParent) {
+  Parent Par;
+  ParentNode PA;
+  EXPECT_EQ(nullptr, PA.getNodeBaseParent());
+  PA.setNodeBaseParent(&Par);
+  EXPECT_EQ(&Par, PA.getNodeBaseParent());
+
+  ParentTrackingNode PTA;
+  EXPECT_EQ(nullptr, PTA.getNodeBaseParent());
+  PTA.setNodeBaseParent(&Par);
+  EXPECT_EQ(&Par, PTA.getNodeBaseParent());
 }
 
 } // end namespace
diff --git a/llvm/unittests/ADT/IListNodeTest.cpp b/llvm/unittests/ADT/IListNodeTest.cpp
index 057eabb..0a5da12 100644
--- a/llvm/unittests/ADT/IListNodeTest.cpp
+++ b/llvm/unittests/ADT/IListNodeTest.cpp
@@ -19,6 +19,8 @@ struct Node;
 
 struct TagA {};
 struct TagB {};
+struct ParentA {};
+struct ParentB {};
 
 TEST(IListNodeTest, Options) {
   static_assert(
@@ -63,6 +65,18 @@ TEST(IListNodeTest, Options) {
                      compute_node_options<Node, ilist_tag<TagA>,
                                           ilist_sentinel_tracking<true>>::type>,
       "order shouldn't matter with real tags");
+  static_assert(
+      !std::is_same_v<compute_node_options<Node>::type,
+                      compute_node_options<Node, ilist_parent<void>>::type>,
+      "void parent is different to no parent");
+  static_assert(
+      !std::is_same_v<compute_node_options<Node, ilist_parent<ParentA>>::type,
+                      compute_node_options<Node, ilist_parent<void>>::type>,
+      "ParentA is not void");
+  static_assert(
+      !std::is_same_v<compute_node_options<Node, ilist_parent<ParentA>>::type,
+                      compute_node_options<Node, ilist_parent<ParentB>>::type>,
+      "ParentA is not ParentB");
 }
 
 } // end namespace