[ADT][DebugInfo][RemoveDIs] Permit extra flags in ilist_iterator's for communicating debug-info facts

[jmorse]

Summary

Hi,

This patch adds a new ilist_iterator -like class that can carry two extra bits as well as the usual node pointer. The rationale behind having these extra bits can be found here [0], the tl;dr being that they're needed to signal whether a "position" in a BasicBlock includes any debug-info before or after the iterator. It's fundamental to removing debug intrinsics, because we need to be able to signal extra information about "positions" in the block.

Major observations: this entirely duplicates ilist_iterator. I took a shot at re-use via inheritance, however there are so many places where the iterator type is re-constructed that most of the class has to be re-implemented anyway. I feel that de-duplicating these types would be a false economy, especially given that LLVM doesn't actively develop this iterator type on a regular basis.

I've made it enable-able through the existing ilist_node options interface, which means there are a fair few sites where the instruction-list type needs to be updated; I think this is just a one-off cost. By default everything will use ilist_iterator, except instruction lists that will use ilist_iterator_w_bits.

I've also made the "new bits" disable-able with a CMAKE flag, and off by default. The exact cost of these bits being present is something like 0.1% according to the LLVM compile-time-tracker (more than offset by future savings), but given that this overall (removing debug intrinsics) feature is going to be in development and evaluation for a while, it doesn't make sense for the compile-time cost to be paid up front.

~

On to the actual patch: as mentioned, this completely duplicates ilist_iterator, adding only the head-and-tail bits plus the accessors to them. There's a moderate amount of plumbing to join up the ilist_node options with selecting the correct iterator. Quite a lot of the change is normalising the different ways the instruction list can be named in different scenarios.

In terms of the functional changes: BasicBlock::begin and getFirstInsertionPt now will return iterators with the "head" bit set, signalling that the iterator was intended to include the debug-info at the start of the block. I've added a small unit-test to ensure that this information is stored, and preserved across copy-construction and assignment. Increment and decrement operations naturally construct a new iterator, dropping the head/tail bits in the process: this is the desired behaviour, as once the iterator is modified it's no longer intended to be at the "head" of the block.

For test coverage, the bit-setting facility is the only change in behaviour that exists, hence the small unit test. This only actually tests anything useful if the CMake flag is set to enable the presence of these bits. With this patch uploaded, I'm going to do some prodding to see whether we can get one of the sie buildbots running with this flag.

[0] https://discourse.llvm.org/t/rfc-instruction-api-changes-needed-to-eliminate-debug-intrinsics-from-ir/68939

[jmorse]

Add setHeadBit(true) to the getFirstNonPHIIt accessors I've added, to return the position of the first non-PHI at the start of the block.

[Orlando]

LGTM (pending clang-formatting if not already, plus a few nits).

The exact cost of these bits being present is something like 0.1% according to the LLVM compile-time-tracker (more than offset by future savings), but given that this overall (removing debug intrinsics) feature is going to be in development and evaluation for a while, it doesn't make sense for the compile-time cost to be paid up front.

This makes sense to me.

llvm/CMakeLists.txt

647

nit: no ilist_iterator's -> ilist_iterators, but the singular instead works too imo.

llvm/include/llvm/IR/SymbolTableListTraits.h

114–118

has this been clang-formatted?

llvm/lib/IR/BasicBlock.cpp

224

Worth copying the comment you added to getFirstInsertionPt here too?

llvm/unittests/ADT/IListIteratorBitsTest.cpp

100–101

Comment floated here from elsewhere?

[jmorse]

(NB: I'm also going to try and get one of our buildbots building with the cmake flag set so that this doesn't immediately commit uncovered code.)

[jmorse]

Said buildbot PR: https://github.com/llvm/llvm-zorg/pull/48

(I've still got the comment-fixes to make too)

[jmorse]

@dyung has set up a buildbot for this (thanks Doug!), landing shortly.

llvm/include/llvm/IR/SymbolTableListTraits.h

114–118

It has!

llvm/lib/IR/BasicBlock.cpp

224

So done.

llvm/unittests/ADT/IListIteratorBitsTest.cpp

100–101

It's a description of the tests that are below; I think I wrote out the comment to outline what I wanted to test for, then repeated the comments below... I'll just delete it.

llvm/CMakeLists.txt

 endif( LLVM_USE_INTEL_JITEVENTS )
 
 option(LLVM_USE_OPROFILE
   "Use opagent JIT interface to inform OProfile about JIT code" OFF)
 
 option(LLVM_EXTERNALIZE_DEBUGINFO
   "Generate dSYM files and strip executables and libraries (Darwin Only)" OFF)
 
+option(LLVM_EXPERIMENTAL_DEBUGINFO_ITERATORS
+  "Add extra Booleans to ilist_iterators to communicate facts for debug-info" OFF)
+
 set(LLVM_CODESIGNING_IDENTITY "" CACHE STRING
   "Sign executables and dylibs with the given identity or skip if empty (Darwin Only)")
 
 # If enabled, verify we are on a platform that supports oprofile.
 if( LLVM_USE_OPROFILE )
   if( NOT CMAKE_SYSTEM_NAME MATCHES "Linux" )
     message(FATAL_ERROR "OProfile support is available on Linux only.")
   endif( NOT CMAKE_SYSTEM_NAME MATCHES "Linux" )

llvm/cmake/modules/HandleLLVMOptions.cmake

CHECK_CXX_SOURCE_COMPILES("
     }" CXX_SUPPORTS_GLIBCXX_DEBUG)
   if(CXX_SUPPORTS_GLIBCXX_DEBUG)
     add_compile_definitions(_GLIBCXX_DEBUG)
   else()
     add_compile_definitions(_GLIBCXX_ASSERTIONS)
   endif()
 endif()
 
+if(LLVM_EXPERIMENTAL_DEBUGINFO_ITERATORS)
+  add_compile_definitions(EXPERIMENTAL_DEBUGINFO_ITERATORS)
+endif()
+
 if (LLVM_ENABLE_STRICT_FIXED_SIZE_VECTORS)
   add_compile_definitions(STRICT_FIXED_SIZE_VECTORS)
 endif()
 
 string(TOUPPER "${LLVM_ABI_BREAKING_CHECKS}" uppercase_LLVM_ABI_BREAKING_CHECKS)
 
 if( uppercase_LLVM_ABI_BREAKING_CHECKS STREQUAL "WITH_ASSERTS" )
   if( LLVM_ENABLE_ASSERTIONS )

llvm/include/llvm/ADT/ilist_iterator.h

public:
 
   /// Get the underlying ilist_node.
   node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
 
   /// Check for end.  Only valid if ilist_sentinel_tracking<true>.
   bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
 };
 
+/// Iterator for intrusive lists  based on ilist_node. Much like ilist_iterator,
+/// 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> {
+  friend ilist_iterator_w_bits<OptionsT, IsReverse, !IsConst>;
+  friend ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>;
+  friend ilist_iterator<OptionsT, !IsReverse, !IsConst>;
+
+  using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
+  using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
+
+public:
+  using value_type = typename Traits::value_type;
+  using pointer = typename Traits::pointer;
+  using reference = typename Traits::reference;
+  using difference_type = ptrdiff_t;
+  using iterator_category = std::bidirectional_iterator_tag;
+  using const_pointer = typename OptionsT::const_pointer;
+  using const_reference = typename OptionsT::const_reference;
+
+private:
+  using node_pointer = typename Traits::node_pointer;
+  using node_reference = typename Traits::node_reference;
+
+  node_pointer NodePtr = nullptr;
+
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+  // (Default: Off) Allow extra position-information flags to be stored
+  // in iterators, in aid of removing debug-info intrinsics from LLVM.
+
+  /// Is this position intended to contain any debug-info immediately before
+  /// the position?
+  mutable bool HeadInclusiveBit = false;
+  /// Is this position intended to contain any debug-info immediately after
+  /// the position?
+  mutable bool TailInclusiveBit = false;
+#endif
+
+public:
+  /// Create from an ilist_node.
+  explicit ilist_iterator_w_bits(node_reference N) : NodePtr(&N) {}
+
+  explicit ilist_iterator_w_bits(pointer NP)
+      : NodePtr(Access::getNodePtr(NP)) {}
+  explicit ilist_iterator_w_bits(reference NR)
+      : NodePtr(Access::getNodePtr(&NR)) {}
+  ilist_iterator_w_bits() = default;
+
+  // This is templated so that we can allow constructing a const iterator from
+  // a nonconst iterator...
+  template <bool RHSIsConst>
+  ilist_iterator_w_bits(
+      const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS,
+      std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr)
+      : NodePtr(RHS.NodePtr) {
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+    HeadInclusiveBit = RHS.HeadInclusiveBit;
+    TailInclusiveBit = RHS.TailInclusiveBit;
+#endif
+  }
+
+  // This is templated so that we can allow assigning to a const iterator from
+  // a nonconst iterator...
+  template <bool RHSIsConst>
+  std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator_w_bits &>
+  operator=(const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS) {
+    NodePtr = RHS.NodePtr;
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+    HeadInclusiveBit = RHS.HeadInclusiveBit;
+    TailInclusiveBit = RHS.TailInclusiveBit;
+#endif
+    return *this;
+  }
+
+  /// Explicit conversion between forward/reverse iterators.
+  ///
+  /// Translate between forward and reverse iterators without changing range
+  /// boundaries.  The resulting iterator will dereference (and have a handle)
+  /// to the previous node, which is somewhat unexpected; but converting the
+  /// two endpoints in a range will give the same range in reverse.
+  ///
+  /// This matches std::reverse_iterator conversions.
+  explicit ilist_iterator_w_bits(
+      const ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> &RHS)
+      : ilist_iterator_w_bits(++RHS.getReverse()) {}
+
+  /// Get a reverse iterator to the same node.
+  ///
+  /// Gives a reverse iterator that will dereference (and have a handle) to the
+  /// same node.  Converting the endpoint iterators in a range will give a
+  /// different range; for range operations, use the explicit conversions.
+  ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> getReverse() const {
+    if (NodePtr)
+      return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>(*NodePtr);
+    return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>();
+  }
+
+  /// Const-cast.
+  ilist_iterator_w_bits<OptionsT, IsReverse, false> getNonConst() const {
+    if (NodePtr) {
+      auto New = ilist_iterator_w_bits<OptionsT, IsReverse, false>(
+          const_cast<typename ilist_iterator_w_bits<OptionsT, IsReverse,
+                                                    false>::node_reference>(
+              *NodePtr));
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+      New.HeadInclusiveBit = HeadInclusiveBit;
+      New.TailInclusiveBit = TailInclusiveBit;
+#endif
+      return New;
+    }
+    return ilist_iterator_w_bits<OptionsT, IsReverse, false>();
+  }
+
+  // Accessors...
+  reference operator*() const {
+    assert(!NodePtr->isKnownSentinel());
+    return *Access::getValuePtr(NodePtr);
+  }
+  pointer operator->() const { return &operator*(); }
+
+  // Comparison operators
+  friend bool operator==(const ilist_iterator_w_bits &LHS,
+                         const ilist_iterator_w_bits &RHS) {
+    return LHS.NodePtr == RHS.NodePtr;
+  }
+  friend bool operator!=(const ilist_iterator_w_bits &LHS,
+                         const ilist_iterator_w_bits &RHS) {
+    return LHS.NodePtr != RHS.NodePtr;
+  }
+
+  // Increment and decrement operators...
+  ilist_iterator_w_bits &operator--() {
+    NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+    HeadInclusiveBit = false;
+    TailInclusiveBit = false;
+#endif
+    return *this;
+  }
+  ilist_iterator_w_bits &operator++() {
+    NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+    HeadInclusiveBit = false;
+    TailInclusiveBit = false;
+#endif
+    return *this;
+  }
+  ilist_iterator_w_bits operator--(int) {
+    ilist_iterator_w_bits tmp = *this;
+    --*this;
+    return tmp;
+  }
+  ilist_iterator_w_bits operator++(int) {
+    ilist_iterator_w_bits tmp = *this;
+    ++*this;
+    return tmp;
+  }
+
+  /// Get the underlying ilist_node.
+  node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
+
+  /// Check for end.  Only valid if ilist_sentinel_tracking<true>.
+  bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
+
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+  bool getHeadBit() const { return HeadInclusiveBit; }
+  bool getTailBit() const { return TailInclusiveBit; }
+  void setHeadBit(bool SetBit) const { HeadInclusiveBit = SetBit; }
+  void setTailBit(bool SetBit) const { TailInclusiveBit = SetBit; }
+#else
+  // Store and return no information if we're not using this feature.
+  bool getHeadBit() const { return false; }
+  bool getTailBit() const { return false; }
+  void setHeadBit(bool SetBit) const { (void)SetBit; }
+  void setTailBit(bool SetBit) const { (void)SetBit; }
+#endif
+};
+
 template <typename From> struct simplify_type;
 
 /// Allow ilist_iterators to convert into pointers to a node automatically when
 /// used by the dyn_cast, cast, isa mechanisms...
 ///
 /// FIXME: remove this, since there is no implicit conversion to NodeTy.
 template <class OptionsT, bool IsConst>
 struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
   using iterator = ilist_iterator<OptionsT, false, IsConst>;
   using SimpleType = typename iterator::pointer;
 
   static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
 };
 template <class OptionsT, bool IsConst>
 struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
     : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
 
+// ilist_iterator_w_bits should also be accessible via isa/dyn_cast.
+template <class OptionsT, bool IsConst>
+struct simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {
+  using iterator = ilist_iterator_w_bits<OptionsT, false, IsConst>;
+  using SimpleType = typename iterator::pointer;
+
+  static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
+};
+template <class OptionsT, bool IsConst>
+struct simplify_type<const ilist_iterator_w_bits<OptionsT, false, IsConst>>
+    : simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {};
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_ILIST_ITERATOR_H

llvm/include/llvm/ADT/ilist_node.h

 
 namespace ilist_detail {
 
 struct NodeAccess;
 
 } // end namespace ilist_detail
 
 template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
+template <class OptionsT, bool IsReverse, bool IsConst>
+class ilist_iterator_w_bits;
 template <class OptionsT> class ilist_sentinel;
 
+// Selector for which iterator type to pick given the iterator-bits node option.
+template <bool use_iterator_bits, typename Opts, bool arg1, bool arg2>
+class ilist_select_iterator_type {
+public:
+  using type = ilist_iterator<Opts, arg1, arg2>;
+};
+template <typename Opts, bool arg1, bool arg2>
+class ilist_select_iterator_type<true, Opts, arg1, arg2> {
+public:
+  using type = ilist_iterator_w_bits<Opts, arg1, arg2>;
+};
+
 /// Implementation for an ilist node.
 ///
 /// Templated on an appropriate \a ilist_detail::node_options, usually computed
 /// by \a ilist_detail::compute_node_options.
 ///
 /// 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 {
   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;
 
   friend typename OptionsT::list_base_type;
   friend struct ilist_detail::NodeAccess;
   friend class ilist_sentinel<OptionsT>;
+
   friend class ilist_iterator<OptionsT, false, false>;
   friend class ilist_iterator<OptionsT, false, true>;
   friend class ilist_iterator<OptionsT, true, false>;
   friend class ilist_iterator<OptionsT, true, true>;
+  friend class ilist_iterator_w_bits<OptionsT, false, false>;
+  friend class ilist_iterator_w_bits<OptionsT, false, true>;
+  friend class ilist_iterator_w_bits<OptionsT, true, false>;
+  friend class ilist_iterator_w_bits<OptionsT, true, true>;
 
 protected:
-  using self_iterator = ilist_iterator<OptionsT, false, false>;
-  using const_self_iterator = ilist_iterator<OptionsT, false, true>;
-  using reverse_self_iterator = ilist_iterator<OptionsT, true, false>;
-  using const_reverse_self_iterator = ilist_iterator<OptionsT, true, true>;
+  using self_iterator =
+      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
+                                          false, false>::type;
+  using const_self_iterator =
+      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
+                                          false, true>::type;
+  using reverse_self_iterator =
+      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
+                                          true, false>::type;
+  using const_reverse_self_iterator =
+      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
+                                          true, true>::type;
 
   ilist_node_impl() = default;
 
 private:
   ilist_node_impl *getPrev() {
     return static_cast<ilist_node_impl *>(node_base_type::getPrev());
   }
 

llvm/include/llvm/ADT/ilist_node_options.h

 template <bool EnableSentinelTracking> struct ilist_sentinel_tracking {};
 
 /// Option to specify a tag for the node type.
 ///
 /// This option allows a single value type to be inserted in multiple lists
 /// simultaneously.  See \a ilist_node for usage examples.
 template <class Tag> struct ilist_tag {};
 
+/// Option to add extra bits to the ilist_iterator.
+///
+/// Some use-cases (debug-info) need to know whether a position is intended
+/// to be half-open or fully open, i.e. whether to include any immediately
+/// adjacent debug-info in an operation. This option adds two bits to the
+/// iterator class to store that information.
+template <bool ExtraIteratorBits> struct ilist_iterator_bits {};
+
 namespace ilist_detail {
 
 /// Helper trait for recording whether an option is specified explicitly.
 template <bool IsExplicit> struct explicitness {
   static const bool is_explicit = IsExplicit;
 };
 typedef explicitness<true> is_explicit;
 typedef explicitness<false> is_implicit;

 };
 template <class Option1, class... Options>
 struct extract_tag<Option1, Options...> : extract_tag<Options...> {};
 template <> struct extract_tag<> {
   typedef void type;
 };
 template <class Tag> struct is_valid_option<ilist_tag<Tag>> : std::true_type {};
 
+/// Extract iterator bits option.
+///
+/// Look through \p Options for the \a ilist_iterator_bits option. Defaults
+/// to false.
+template <class... Options> struct extract_iterator_bits;
+template <bool IteratorBits, class... Options>
+struct extract_iterator_bits<ilist_iterator_bits<IteratorBits>, Options...>
+    : std::integral_constant<bool, IteratorBits> {};
+template <class Option1, class... Options>
+struct extract_iterator_bits<Option1, Options...>
+    : extract_iterator_bits<Options...> {};
+template <> struct extract_iterator_bits<> : std::false_type, is_implicit {};
+template <bool IteratorBits>
+struct is_valid_option<ilist_iterator_bits<IteratorBits>> : std::true_type {};
+
 /// Check whether options are valid.
 ///
 /// The conjunction of \a is_valid_option on each individual option.
 template <class... Options> struct check_options;
 template <> struct check_options<> : std::true_type {};
 template <class Option1, class... Options>
 struct check_options<Option1, Options...>
     : std::integral_constant<bool, is_valid_option<Option1>::value &&
                                        check_options<Options...>::value> {};
 
 /// Traits for options for \a ilist_node.
 ///
 /// This is usually computed via \a compute_node_options.
 template <class T, bool EnableSentinelTracking, bool IsSentinelTrackingExplicit,
-          class TagT>
+          class TagT, bool HasIteratorBits>
 struct node_options {
   typedef T value_type;
   typedef T *pointer;
   typedef T &reference;
   typedef const T *const_pointer;
   typedef const T &const_reference;
 
   static const bool enable_sentinel_tracking = EnableSentinelTracking;
   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;
 };
 
 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>
+                       typename extract_tag<Options...>::type,
+                       extract_iterator_bits<Options...>::value>
       type;
 };
 
 } // end namespace ilist_detail
 } // end namespace llvm
 
 #endif // LLVM_ADT_ILIST_NODE_OPTIONS_H

llvm/include/llvm/ADT/simple_ilist.h

class simple_ilist
   ilist_sentinel<OptionsT> Sentinel;
 
 public:
   using value_type = typename OptionsT::value_type;
   using pointer = typename OptionsT::pointer;
   using reference = typename OptionsT::reference;
   using const_pointer = typename OptionsT::const_pointer;
   using const_reference = typename OptionsT::const_reference;
-  using iterator = ilist_iterator<OptionsT, false, false>;
-  using const_iterator = ilist_iterator<OptionsT, false, true>;
-  using reverse_iterator = ilist_iterator<OptionsT, true, false>;
-  using const_reverse_iterator = ilist_iterator<OptionsT, true, true>;
+  using iterator =
+      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
+                                          false, false>::type;
+  using const_iterator =
+      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
+                                          false, true>::type;
+  using reverse_iterator =
+      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
+                                          true, false>::type;
+  using const_reverse_iterator =
+      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
+                                          true, true>::type;
   using size_type = size_t;
   using difference_type = ptrdiff_t;
 
   simple_ilist() = default;
   ~simple_ilist() = default;
 
   // No copy constructors.
   simple_ilist(const simple_ilist &) = delete;

llvm/include/llvm/IR/BasicBlock.h

 /// instructions may not occur in the middle of basic blocks, and must terminate
 /// the blocks. The BasicBlock class allows malformed basic blocks to occur
 /// because it may be useful in the intermediate stage of constructing or
 /// modifying a program. However, the verifier will ensure that basic blocks are
 /// "well formed".
 class BasicBlock final : public Value, // Basic blocks are data objects also
                          public ilist_node_with_parent<BasicBlock, Function> {
 public:
-  using InstListType = SymbolTableList<Instruction>;
+  using InstListType = SymbolTableList<Instruction, ilist_iterator_bits<true>>;
 
 private:
   friend class BlockAddress;
   friend class SymbolTableListTraits<BasicBlock>;
 
   InstListType InstList;
   Function *Parent;
 
public:
   /// Instruction iterators...
   using iterator = InstListType::iterator;
   using const_iterator = InstListType::const_iterator;
   using reverse_iterator = InstListType::reverse_iterator;
   using const_reverse_iterator = InstListType::const_reverse_iterator;
 
   // These functions and classes need access to the instruction list.
   friend void Instruction::removeFromParent();
-  friend iplist<Instruction>::iterator Instruction::eraseFromParent();
+  friend BasicBlock::iterator Instruction::eraseFromParent();
   friend BasicBlock::iterator Instruction::insertInto(BasicBlock *BB,
                                                       BasicBlock::iterator It);
-  friend class llvm::SymbolTableListTraits<llvm::Instruction>;
-  friend class llvm::ilist_node_with_parent<llvm::Instruction, llvm::BasicBlock>;
+  friend class llvm::SymbolTableListTraits<llvm::Instruction,
+                                           ilist_iterator_bits<true>>;
+  friend class llvm::ilist_node_with_parent<llvm::Instruction, llvm::BasicBlock,
+                                            ilist_iterator_bits<true>>;
 
   /// Creates a new BasicBlock.
   ///
   /// If the Parent parameter is specified, the basic block is automatically
   /// inserted at either the end of the function (if InsertBefore is 0), or
   /// before the specified basic block.
   static BasicBlock *Create(LLVMContext &Context, const Twine &Name = "",
                             Function *Parent = nullptr,
return const_cast<Instruction *>(
                        static_cast<const BasicBlock *>(this)->getFirstNonPHI());
   }
 
   /// Iterator returning form of getFirstNonPHI. Installed as a placeholder for
   /// the RemoveDIs project that will eventually remove debug intrinsics.
   InstListType::const_iterator getFirstNonPHIIt() const;
   InstListType::iterator getFirstNonPHIIt() {
     BasicBlock::iterator It =
         static_cast<const BasicBlock *>(this)->getFirstNonPHIIt().getNonConst();
+    It.setHeadBit(true);
     return It;
   }
 
   /// Returns a pointer to the first instruction in this block that is not a
   /// PHINode or a debug intrinsic, or any pseudo operation if \c SkipPseudoOp
   /// is true.
   const Instruction *getFirstNonPHIOrDbg(bool SkipPseudoOp = true) const;
   Instruction *getFirstNonPHIOrDbg(bool SkipPseudoOp = true) {
public:
   /// AssemblyAnnotationWriter.
   void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW = nullptr,
              bool ShouldPreserveUseListOrder = false,
              bool IsForDebug = false) const;
 
   //===--------------------------------------------------------------------===//
   /// Instruction iterator methods
   ///
-  inline iterator                begin()       { return InstList.begin(); }
-  inline const_iterator          begin() const { return InstList.begin(); }
+  inline iterator begin() {
+    iterator It = InstList.begin();
+    // Set the head-inclusive bit to indicate that this iterator includes
+    // any debug-info at the start of the block. This is a no-op unless the
+    // appropriate CMake flag is set.
+    It.setHeadBit(true);
+    return It;
+  }
+  inline const_iterator begin() const {
+    const_iterator It = InstList.begin();
+    It.setHeadBit(true);
+    return It;
+  }
   inline iterator                end  ()       { return InstList.end();   }
   inline const_iterator          end  () const { return InstList.end();   }
 
   inline reverse_iterator        rbegin()       { return InstList.rbegin(); }
   inline const_reverse_iterator  rbegin() const { return InstList.rbegin(); }
   inline reverse_iterator        rend  ()       { return InstList.rend();   }
   inline const_reverse_iterator  rend  () const { return InstList.rend();   }
 

llvm/include/llvm/IR/GlobalAlias.h

 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/IR/Value.h"
 
 namespace llvm {
 
 class Twine;
 class Module;
-template <typename ValueSubClass> class SymbolTableListTraits;
+template <typename ValueSubClass, typename... Args> class SymbolTableListTraits;
 
 class GlobalAlias : public GlobalValue, public ilist_node<GlobalAlias> {
   friend class SymbolTableListTraits<GlobalAlias>;
 
   GlobalAlias(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage,
               const Twine &Name, Constant *Aliasee, Module *Parent);
 
 public:

llvm/include/llvm/IR/GlobalIFunc.h

 #include "llvm/IR/Value.h"
 
 namespace llvm {
 
 class Twine;
 class Module;
 
 // Traits class for using GlobalIFunc in symbol table in Module.
-template <typename ValueSubClass> class SymbolTableListTraits;
+template <typename ValueSubClass, typename... Args> class SymbolTableListTraits;
 
 class GlobalIFunc final : public GlobalObject, public ilist_node<GlobalIFunc> {
   friend class SymbolTableListTraits<GlobalIFunc>;
 
   GlobalIFunc(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage,
               const Twine &Name, Constant *Resolver, Module *Parent);
 
 public:

llvm/include/llvm/IR/GlobalVariable.h

 #include <cassert>
 #include <cstddef>
 
 namespace llvm {
 
 class Constant;
 class Module;
 
-template <typename ValueSubClass> class SymbolTableListTraits;
+template <typename ValueSubClass, typename... Args> class SymbolTableListTraits;
 class DIGlobalVariableExpression;
 
 class GlobalVariable : public GlobalObject, public ilist_node<GlobalVariable> {
   friend class SymbolTableListTraits<GlobalVariable>;
 
   AttributeSet Attrs;
   bool isConstantGlobal : 1;                   // Is this a global constant?
   bool isExternallyInitializedConstant : 1;    // Is this a global whose value

llvm/include/llvm/IR/Instruction.h

 class Module;
 struct AAMDNodes;
 
 template <> struct ilist_alloc_traits<Instruction> {
   static inline void deleteNode(Instruction *V);
 };
 
 class Instruction : public User,
-                    public ilist_node_with_parent<Instruction, BasicBlock> {
+                    public ilist_node_with_parent<Instruction, BasicBlock,
+                                                  ilist_iterator_bits<true>> {
+public:
+  using InstListType = SymbolTableList<Instruction, ilist_iterator_bits<true>>;
+private:
   BasicBlock *Parent;
   DebugLoc DbgLoc;                         // 'dbg' Metadata cache.
 
   /// Relative order of this instruction in its parent basic block. Used for
   /// O(1) local dominance checks between instructions.
   mutable unsigned Order = 0;
 
 protected:
public:
 
   /// This method unlinks 'this' from the containing basic block, but does not
   /// delete it.
   void removeFromParent();
 
   /// This method unlinks 'this' from the containing basic block and deletes it.
   ///
   /// \returns an iterator pointing to the element after the erased one
-  SymbolTableList<Instruction>::iterator eraseFromParent();
+  InstListType::iterator eraseFromParent();
 
   /// Insert an unlinked instruction into a basic block immediately before
   /// the specified instruction.
   void insertBefore(Instruction *InsertPos);
-  void insertBefore(SymbolTableList<Instruction>::iterator InsertPos) {
+  void insertBefore(InstListType::iterator InsertPos) {
     insertBefore(&*InsertPos);
   }
 
   /// Insert an unlinked instruction into a basic block immediately after the
   /// specified instruction.
   void insertAfter(Instruction *InsertPos);
 
   /// Inserts an unlinked instruction into \p ParentBB at position \p It and
   /// returns the iterator of the inserted instruction.
-  SymbolTableList<Instruction>::iterator
-  insertInto(BasicBlock *ParentBB, SymbolTableList<Instruction>::iterator It);
+  InstListType::iterator insertInto(BasicBlock *ParentBB,
+                                    InstListType::iterator It);
 
-  void insertBefore(BasicBlock &BB,
-                    SymbolTableList<Instruction>::iterator InsertPos) {
+  void insertBefore(BasicBlock &BB, InstListType::iterator InsertPos) {
     insertInto(&BB, InsertPos);
   }
 
   /// Unlink this instruction from its current basic block and insert it into
   /// the basic block that MovePos lives in, right before MovePos.
   void moveBefore(Instruction *MovePos);
 
   /// Perform a \ref moveBefore operation, while signalling that the caller
   /// intends to preserve the original ordering of instructions. This implicitly
   /// means that any adjacent debug-info should move with this instruction.
   /// This method is currently a no-op placeholder, but it will become meaningful
   /// when the "RemoveDIs" project is enabled.
   void moveBeforePreserving(Instruction *MovePos) {
     moveBefore(MovePos);
   }
 
   /// Unlink this instruction and insert into BB before I.
   ///
   /// \pre I is a valid iterator into BB.
-  void moveBefore(BasicBlock &BB, SymbolTableList<Instruction>::iterator I);
+  void moveBefore(BasicBlock &BB, InstListType::iterator I);
 
   /// (See other overload for moveBeforePreserving).
-  void moveBeforePreserving(BasicBlock &BB, SymbolTableList<Instruction>::iterator I) {
+  void moveBeforePreserving(BasicBlock &BB, InstListType::iterator I) {
     moveBefore(BB, I);
   }
 
   /// Unlink this instruction from its current basic block and insert it into
   /// the basic block that MovePos lives in, right after MovePos.
   void moveAfter(Instruction *MovePos);
 
   /// See \ref moveBeforePreserving .
#include "llvm/IR/Instruction.def"
   enum OtherOps {
 #define  FIRST_OTHER_INST(N)             OtherOpsBegin = N,
 #define HANDLE_OTHER_INST(N, OPC, CLASS) OPC = N,
 #define   LAST_OTHER_INST(N)             OtherOpsEnd = N+1
 #include "llvm/IR/Instruction.def"
   };
 
 private:
-  friend class SymbolTableListTraits<Instruction>;
+  friend class SymbolTableListTraits<Instruction, ilist_iterator_bits<true>>;
   friend class BasicBlock; // For renumbering.
 
   // Shadow Value::setValueSubclassData with a private forwarding method so that
   // subclasses cannot accidentally use it.
   void setValueSubclassData(unsigned short D) {
     Value::setValueSubclassData(D);
   }
 

llvm/include/llvm/IR/Instructions.h

public:
   SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I);
 
   /// Delegate the call to the underlying SwitchInst::addCase() and set the
   /// specified branch weight for the added case.
   void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W);
 
   /// Delegate the call to the underlying SwitchInst::eraseFromParent() and mark
   /// this object to not touch the underlying SwitchInst in destructor.
-  SymbolTableList<Instruction>::iterator eraseFromParent();
+  Instruction::InstListType::iterator eraseFromParent();
 
   void setSuccessorWeight(unsigned idx, CaseWeightOpt W);
   CaseWeightOpt getSuccessorWeight(unsigned idx);
 
   static CaseWeightOpt getSuccessorWeight(const SwitchInst &SI, unsigned idx);
 };
 
 template <>

llvm/include/llvm/IR/SymbolTableListTraits.h

 DEFINE_SYMBOL_TABLE_PARENT_TYPE(BasicBlock, Function)
 DEFINE_SYMBOL_TABLE_PARENT_TYPE(Argument, Function)
 DEFINE_SYMBOL_TABLE_PARENT_TYPE(Function, Module)
 DEFINE_SYMBOL_TABLE_PARENT_TYPE(GlobalVariable, Module)
 DEFINE_SYMBOL_TABLE_PARENT_TYPE(GlobalAlias, Module)
 DEFINE_SYMBOL_TABLE_PARENT_TYPE(GlobalIFunc, Module)
 #undef DEFINE_SYMBOL_TABLE_PARENT_TYPE
 
-template <typename NodeTy> class SymbolTableList;
+template <typename NodeTy, typename... Args> class SymbolTableList;
 
 // ValueSubClass   - The type of objects that I hold, e.g. Instruction.
 // ItemParentClass - The type of object that owns the list, e.g. BasicBlock.
+// OptionsT        - Extra options to ilist nodes.
 //
-template <typename ValueSubClass>
+template <typename ValueSubClass, typename... Args>
 class SymbolTableListTraits : public ilist_alloc_traits<ValueSubClass> {
-  using ListTy = SymbolTableList<ValueSubClass>;
-  using iterator = typename simple_ilist<ValueSubClass>::iterator;
+  using ListTy = SymbolTableList<ValueSubClass, Args...>;
+  using iterator = typename simple_ilist<ValueSubClass, Args...>::iterator;
   using ItemParentClass =
       typename SymbolTableListParentType<ValueSubClass>::type;
 
 public:
   SymbolTableListTraits() = default;
 
 private:
   /// getListOwner - Return the object that owns this list.  If this is a list
public:
   static ValueSymbolTable *toPtr(ValueSymbolTable &R) { return &R; }
 };
 
 /// List that automatically updates parent links and symbol tables.
 ///
 /// When nodes are inserted into and removed from this list, the associated
 /// symbol table will be automatically updated.  Similarly, parent links get
 /// updated automatically.
-template <class T>
-class SymbolTableList
-    : public iplist_impl<simple_ilist<T>, SymbolTableListTraits<T>> {};
+template <class T, typename... Args>
+class SymbolTableList : public iplist_impl<simple_ilist<T, Args...>,
+                                           SymbolTableListTraits<T, Args...>> {
+};
 
 } // end namespace llvm
 
 #endif // LLVM_IR_SYMBOLTABLELISTTRAITS_H

llvm/include/llvm/IR/ValueSymbolTable.h

 
 class Argument;
 class BasicBlock;
 class Function;
 class GlobalAlias;
 class GlobalIFunc;
 class GlobalVariable;
 class Instruction;
+template <bool ExtraIteratorBits> struct ilist_iterator_bits;
 template <unsigned InternalLen> class SmallString;
-template <typename ValueSubClass> class SymbolTableListTraits;
+template <typename ValueSubClass, typename ... Args> class SymbolTableListTraits;
 
 /// This class provides a symbol table of name/value pairs. It is essentially
 /// a std::map<std::string,Value*> but has a controlled interface provided by
 /// LLVM as well as ensuring uniqueness of names.
 ///
 class ValueSymbolTable {
   friend class SymbolTableListTraits<Argument>;
   friend class SymbolTableListTraits<BasicBlock>;
   friend class SymbolTableListTraits<Function>;
   friend class SymbolTableListTraits<GlobalAlias>;
   friend class SymbolTableListTraits<GlobalIFunc>;
   friend class SymbolTableListTraits<GlobalVariable>;
-  friend class SymbolTableListTraits<Instruction>;
+  friend class SymbolTableListTraits<Instruction, ilist_iterator_bits<true>>;
   friend class Value;
 
 /// @name Types
 /// @{
 public:
   /// A mapping of names to values.
   using ValueMap = StringMap<Value*>;
 

llvm/lib/IR/BasicBlock.cpp

 }
 
 template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
   BB->invalidateOrders();
 }
 
 // Explicit instantiation of SymbolTableListTraits since some of the methods
 // are not in the public header file...
-template class llvm::SymbolTableListTraits<Instruction>;
+template class llvm::SymbolTableListTraits<Instruction,
+                                           ilist_iterator_bits<true>>;
 
 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
                        BasicBlock *InsertBefore)
   : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
 
   if (NewParent)
     insertInto(NewParent, InsertBefore);
   else

 
 const Instruction* BasicBlock::getFirstNonPHI() const {
   for (const Instruction &I : *this)
     if (!isa<PHINode>(I))
       return &I;
   return nullptr;
 }
 
 BasicBlock::const_iterator BasicBlock::getFirstNonPHIIt() const {
-  return getFirstNonPHI()->getIterator();
+  const Instruction *I = getFirstNonPHI();
+  BasicBlock::const_iterator It = I->getIterator();
+  // Set the head-inclusive bit to indicate that this iterator includes
+  // any debug-info at the start of the block. This is a no-op unless the
+  // appropriate CMake flag is set.
+  It.setHeadBit(true);
+  return It;
 }
 
 const Instruction *BasicBlock::getFirstNonPHIOrDbg(bool SkipPseudoOp) const {
   for (const Instruction &I : *this) {
     if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
       continue;
 
     if (SkipPseudoOp && isa<PseudoProbeInst>(I))

 
 BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
   const Instruction *FirstNonPHI = getFirstNonPHI();
   if (!FirstNonPHI)
     return end();
 
   const_iterator InsertPt = FirstNonPHI->getIterator();
   if (InsertPt->isEHPad()) ++InsertPt;
+  // Set the head-inclusive bit to indicate that this iterator includes
+  // any debug-info at the start of the block. This is a no-op unless the
+  // appropriate CMake flag is set.
+  InsertPt.setHeadBit(true);
   return InsertPt;
 }
 
 BasicBlock::const_iterator BasicBlock::getFirstNonPHIOrDbgOrAlloca() const {
   const Instruction *FirstNonPHI = getFirstNonPHI();
   if (!FirstNonPHI)
     return end();
 

llvm/lib/IR/Instruction.cpp

 const Function *Instruction::getFunction() const {
   return getParent()->getParent();
 }
 
 void Instruction::removeFromParent() {
   getParent()->getInstList().remove(getIterator());
 }
 
-iplist<Instruction>::iterator Instruction::eraseFromParent() {
+BasicBlock::iterator Instruction::eraseFromParent() {
   return getParent()->getInstList().erase(getIterator());
 }
 
 /// Insert an unlinked instruction into a basic block immediately before the
 /// specified instruction.
 void Instruction::insertBefore(Instruction *InsertPos) {
   insertInto(InsertPos->getParent(), InsertPos->getIterator());
 }

 void Instruction::moveBefore(Instruction *MovePos) {
   moveBefore(*MovePos->getParent(), MovePos->getIterator());
 }
 
 void Instruction::moveAfter(Instruction *MovePos) {
   moveBefore(*MovePos->getParent(), ++MovePos->getIterator());
 }
 
-void Instruction::moveBefore(BasicBlock &BB,
-                             SymbolTableList<Instruction>::iterator I) {
+void Instruction::moveBefore(BasicBlock &BB, InstListType::iterator I) {
   assert(I == BB.end() || I->getParent() == &BB);
   BB.splice(I, getParent(), getIterator());
 }
 
 bool Instruction::comesBefore(const Instruction *Other) const {
   assert(Parent && Other->Parent &&
          "instructions without BB parents have no order");
   assert(Parent == Other->Parent && "cross-BB instruction order comparison");

llvm/lib/IR/Instructions.cpp

if (!Weights && W && *W) {
     Changed = true;
     Weights->push_back(W.value_or(0));
   }
   if (Weights)
     assert(SI.getNumSuccessors() == Weights->size() &&
            "num of prof branch_weights must accord with num of successors");
 }
 
-SymbolTableList<Instruction>::iterator
+Instruction::InstListType::iterator
 SwitchInstProfUpdateWrapper::eraseFromParent() {
   // Instruction is erased. Mark as unchanged to not touch it in the destructor.
   Changed = false;
   if (Weights)
     Weights->resize(0);
   return SI.eraseFromParent();
 }
 

llvm/lib/IR/SymbolTableListTraitsImpl.h

 /// Notify basic blocks when an instruction is inserted.
 template <typename ParentClass>
 inline void invalidateParentIListOrdering(ParentClass *Parent) {}
 template <> void invalidateParentIListOrdering(BasicBlock *BB);
 
 /// setSymTabObject - This is called when (f.e.) the parent of a basic block
 /// changes.  This requires us to remove all the instruction symtab entries from
 /// the current function and reinsert them into the new function.
-template <typename ValueSubClass>
+template <typename ValueSubClass, typename... Args>
 template <typename TPtr>
-void SymbolTableListTraits<ValueSubClass>::setSymTabObject(TPtr *Dest,
+void SymbolTableListTraits<ValueSubClass, Args...>::setSymTabObject(TPtr *Dest,
                                                                     TPtr Src) {
   // Get the old symtab and value list before doing the assignment.
   ValueSymbolTable *OldST = getSymTab(getListOwner());
 
   // Do it.
   *Dest = Src;
 
   // Get the new SymTab object.
   ValueSymbolTable *NewST = getSymTab(getListOwner());
void SymbolTableListTraits<ValueSubClass, Args...>::setSymTabObject(TPtr *Dest,
   }
 
   if (NewST) {
     // Add all of the items to the new symtab.
     for (auto I = ItemList.begin(); I != ItemList.end(); ++I)
       if (I->hasName())
         NewST->reinsertValue(&*I);
   }
-
 }
 
-template <typename ValueSubClass>
-void SymbolTableListTraits<ValueSubClass>::addNodeToList(ValueSubClass *V) {
+template <typename ValueSubClass, typename... Args>
+void SymbolTableListTraits<ValueSubClass, Args...>::addNodeToList(
+    ValueSubClass *V) {
   assert(!V->getParent() && "Value already in a container!!");
   ItemParentClass *Owner = getListOwner();
   V->setParent(Owner);
   invalidateParentIListOrdering(Owner);
   if (V->hasName())
     if (ValueSymbolTable *ST = getSymTab(Owner))
       ST->reinsertValue(V);
 }
 
-template <typename ValueSubClass>
-void SymbolTableListTraits<ValueSubClass>::removeNodeFromList(
+template <typename ValueSubClass, typename... Args>
+void SymbolTableListTraits<ValueSubClass, Args...>::removeNodeFromList(
     ValueSubClass *V) {
   V->setParent(nullptr);
   if (V->hasName())
     if (ValueSymbolTable *ST = getSymTab(getListOwner()))
       ST->removeValueName(V->getValueName());
 }
 
-template <typename ValueSubClass>
-void SymbolTableListTraits<ValueSubClass>::transferNodesFromList(
+template <typename ValueSubClass, typename... Args>
+void SymbolTableListTraits<ValueSubClass, Args...>::transferNodesFromList(
     SymbolTableListTraits &L2, iterator first, iterator last) {
   // Transfering nodes, even within the same BB, invalidates the ordering. The
   // list that we removed the nodes from still has a valid ordering.
   ItemParentClass *NewIP = getListOwner();
   invalidateParentIListOrdering(NewIP);
 
   // Nothing else needs to be done if we're reording nodes within the same list.
   ItemParentClass *OldIP = L2.getListOwner();

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   FallibleIteratorTest.cpp
   FloatingPointMode.cpp
   FoldingSet.cpp
   FunctionExtrasTest.cpp
   FunctionRefTest.cpp
   HashingTest.cpp
   IListBaseTest.cpp
   IListIteratorTest.cpp
+  IListIteratorBitsTest.cpp
   IListNodeBaseTest.cpp
   IListNodeTest.cpp
   IListSentinelTest.cpp
   IListTest.cpp
   ImmutableListTest.cpp
   ImmutableMapTest.cpp
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp

llvm/unittests/ADT/IListIteratorBitsTest.cpp

+//==- unittests/ADT/IListIteratorBitsTest.cpp - ilist_iterator_w_bits tests -=//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/simple_ilist.h"
+#include "gtest/gtest.h"
+
+// Test that ilist_iterator_w_bits can be used to store extra information about
+// what we're iterating over, that it's only enabled when given the relevant
+// option, and it can be fed into various iteration utilities.
+
+using namespace llvm;
+
+namespace {
+
+class dummy;
+
+struct Node : ilist_node<Node, ilist_iterator_bits<true>> {
+  friend class dummy;
+};
+
+struct PlainNode : ilist_node<PlainNode> {
+  friend class dummy;
+};
+
+TEST(IListIteratorBitsTest, DefaultConstructor) {
+  simple_ilist<Node, ilist_iterator_bits<true>>::iterator I;
+  simple_ilist<Node, ilist_iterator_bits<true>>::reverse_iterator RI;
+  simple_ilist<Node, ilist_iterator_bits<true>>::const_iterator CI;
+  simple_ilist<Node, ilist_iterator_bits<true>>::const_reverse_iterator CRI;
+  EXPECT_EQ(nullptr, I.getNodePtr());
+  EXPECT_EQ(nullptr, CI.getNodePtr());
+  EXPECT_EQ(nullptr, RI.getNodePtr());
+  EXPECT_EQ(nullptr, CRI.getNodePtr());
+  EXPECT_EQ(I, I);
+  EXPECT_EQ(I, CI);
+  EXPECT_EQ(CI, I);
+  EXPECT_EQ(CI, CI);
+  EXPECT_EQ(RI, RI);
+  EXPECT_EQ(RI, CRI);
+  EXPECT_EQ(CRI, RI);
+  EXPECT_EQ(CRI, CRI);
+  EXPECT_EQ(I, RI.getReverse());
+  EXPECT_EQ(RI, I.getReverse());
+}
+
+TEST(IListIteratorBitsTest, ConsAndAssignment) {
+  simple_ilist<Node, ilist_iterator_bits<true>> L;
+  Node A;
+  L.insert(L.end(), A);
+
+  simple_ilist<Node, ilist_iterator_bits<true>>::iterator I, I2;
+
+// Two sets of tests: if we've compiled in the iterator bits, then check that
+// HeadInclusiveBit and TailInclusiveBit are preserved on assignment and copy
+// construction, but not on other operations.
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+  I = L.begin();
+  EXPECT_FALSE(I.getHeadBit());
+  EXPECT_FALSE(I.getTailBit());
+  I.setHeadBit(true);
+  I.setTailBit(true);
+  EXPECT_TRUE(I.getHeadBit());
+  EXPECT_TRUE(I.getTailBit());
+
+  ++I;
+
+  EXPECT_FALSE(I.getHeadBit());
+  EXPECT_FALSE(I.getTailBit());
+
+  I = L.begin();
+  I.setHeadBit(true);
+  I.setTailBit(true);
+  I2 = I;
+  EXPECT_TRUE(I2.getHeadBit());
+  EXPECT_TRUE(I2.getTailBit());
+
+  I = L.begin();
+  I.setHeadBit(true);
+  I.setTailBit(true);
+  simple_ilist<Node, ilist_iterator_bits<true>>::iterator I3(I);
+  EXPECT_TRUE(I3.getHeadBit());
+  EXPECT_TRUE(I3.getTailBit());
+#else
+  // The calls should be available, but shouldn't actually store information.
+  I = L.begin();
+  EXPECT_FALSE(I.getHeadBit());
+  EXPECT_FALSE(I.getTailBit());
+  I.setHeadBit(true);
+  I.setTailBit(true);
+  EXPECT_FALSE(I.getHeadBit());
+  EXPECT_FALSE(I.getTailBit());
+  // Suppress warnings as we don't test with this variable.
+  (void)I2;
+#endif
+}
+
+class dummy {
+  // Test that we get an ilist_iterator_w_bits out of the node given that the
+  // options are enabled.
+  using node_options = typename ilist_detail::compute_node_options<
+      Node, ilist_iterator_bits<true>>::type;
+  static_assert(std::is_same<Node::self_iterator,
+                             llvm::ilist_iterator_w_bits<node_options, false,
+                                                         false>>::value);
+
+  // Now test that a plain node, without the option, gets a plain
+  // ilist_iterator.
+  using plain_node_options =
+      typename ilist_detail::compute_node_options<PlainNode>::type;
+  static_assert(std::is_same<
+                PlainNode::self_iterator,
+                llvm::ilist_iterator<plain_node_options, false, false>>::value);
+};
+
+TEST(IListIteratorBitsTest, RangeIteration) {
+  // Check that we can feed ilist_iterator_w_bits into make_range and similar.
+  // Plus, we should be able to convert it to a reverse iterator and use that.
+  simple_ilist<Node, ilist_iterator_bits<true>> L;
+  Node A;
+  L.insert(L.end(), A);
+
+  for (Node &N : make_range(L.begin(), L.end()))
+    (void)N;
+
+  simple_ilist<Node, ilist_iterator_bits<true>>::iterator It =
+      L.begin()->getIterator();
+  auto RevIt = It.getReverse();
+
+  for (Node &N : make_range(RevIt, L.rend()))
+    (void)N;
+}
+
+} // end namespace