ADT: Add sentinel tracking and custom tags to ilists

This adds two declarative configuration options for intrusive lists
(available for simple_ilist, iplist, and ilist).  Both of these options
affect ilist_node interoperability and need to be passed both to the
node and the list.  Instead of adding a new traits class, they're
specified as optional template parameters (in any order).

The two options:

 1. Pass ilist_sentinel_tracking<true> or ilist_sentinel_tracking<false>
    to control whether there's a bit on ilist_node "prev" pointer
    indicating whether it's the sentinel.  The default behaviour is to
    use a bit if and only if LLVM_ENABLE_ABI_BREAKING_CHECKS.

 2. Pass ilist_tag<TagA> and ilist_tag<TagB> to allow insertion of a
    single node into two different lists (simultaneously).

I have an immediate use-case for (1) ilist_sentinel_tracking: fixing the
validation semantics of MachineBasicBlock::reverse_iterator to match
ilist::reverse_iterator (ala r280032: see the comments at the end of the
commit message there).  I'm adding (2) ilist_tag in the same commit to
validate that the options framework supports expansion.  Justin Bogner
mentioned this might enable a possible cleanup in SelectionDAG, but I'll
leave this to others to explore.  In the meantime, the unit tests and
the comments for simple_ilist and ilist_node have usage examples.

Note that there's a layer of indirection to support optional,
out-of-order, template paramaters.  Internal classes are templated on an
instantiation of the non-variadic ilist_detail::node_options.
User-facing classes use ilist_detail::compute_node_options to compute
the correct instantiation of ilist_detail::node_options.

The comments for ilist_detail::is_valid_option describe how to add new
options (e.g., ilist_packed_int<int NumBits>).

llvm-svn: 281167

1 files changed, 47 insertions, 7 deletions

diff --git a/llvm/unittests/ADT/IListNodeBaseTest.cpp b/llvm/unittests/ADT/IListNodeBaseTest.cpp
index 0fb1282b21d..8819ab118a5 100644
--- a/llvm/unittests/ADT/IListNodeBaseTest.cpp
+++ b/llvm/unittests/ADT/IListNodeBaseTest.cpp
@@ -14,15 +14,24 @@ using namespace llvm;
 
 namespace {
 
+typedef ilist_node_base<false> RawNode;
+typedef ilist_node_base<true> TrackingNode;
+
 TEST(IListNodeBaseTest, DefaultConstructor) {
-  ilist_node_base A;
+  RawNode A;
   EXPECT_EQ(nullptr, A.getPrev());
   EXPECT_EQ(nullptr, A.getNext());
   EXPECT_FALSE(A.isKnownSentinel());
+
+  TrackingNode TA;
+  EXPECT_EQ(nullptr, TA.getPrev());
+  EXPECT_EQ(nullptr, TA.getNext());
+  EXPECT_FALSE(TA.isKnownSentinel());
+  EXPECT_FALSE(TA.isSentinel());
 }
 
 TEST(IListNodeBaseTest, setPrevAndNext) {
-  ilist_node_base A, B, C;
+  RawNode A, B, C;
   A.setPrev(&B);
   EXPECT_EQ(&B, A.getPrev());
   EXPECT_EQ(nullptr, A.getNext());
@@ -38,23 +47,54 @@ TEST(IListNodeBaseTest, setPrevAndNext) {
   EXPECT_EQ(nullptr, B.getNext());
   EXPECT_EQ(nullptr, C.getPrev());
   EXPECT_EQ(nullptr, C.getNext());
+
+  TrackingNode TA, TB, TC;
+  TA.setPrev(&TB);
+  EXPECT_EQ(&TB, TA.getPrev());
+  EXPECT_EQ(nullptr, TA.getNext());
+  EXPECT_EQ(nullptr, TB.getPrev());
+  EXPECT_EQ(nullptr, TB.getNext());
+  EXPECT_EQ(nullptr, TC.getPrev());
+  EXPECT_EQ(nullptr, TC.getNext());
+
+  TA.setNext(&TC);
+  EXPECT_EQ(&TB, TA.getPrev());
+  EXPECT_EQ(&TC, TA.getNext());
+  EXPECT_EQ(nullptr, TB.getPrev());
+  EXPECT_EQ(nullptr, TB.getNext());
+  EXPECT_EQ(nullptr, TC.getPrev());
+  EXPECT_EQ(nullptr, TC.getNext());
 }
 
 TEST(IListNodeBaseTest, isKnownSentinel) {
-  ilist_node_base A, B;
+  // Without sentinel tracking.
+  RawNode A, B;
   EXPECT_FALSE(A.isKnownSentinel());
   A.setPrev(&B);
   A.setNext(&B);
   EXPECT_EQ(&B, A.getPrev());
   EXPECT_EQ(&B, A.getNext());
+  EXPECT_FALSE(A.isKnownSentinel());
   A.initializeSentinel();
-#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
-  EXPECT_TRUE(A.isKnownSentinel());
-#else
   EXPECT_FALSE(A.isKnownSentinel());
-#endif
   EXPECT_EQ(&B, A.getPrev());
   EXPECT_EQ(&B, A.getNext());
+
+  // With sentinel tracking.
+  TrackingNode TA, TB;
+  EXPECT_FALSE(TA.isKnownSentinel());
+  EXPECT_FALSE(TA.isSentinel());
+  TA.setPrev(&TB);
+  TA.setNext(&TB);
+  EXPECT_EQ(&TB, TA.getPrev());
+  EXPECT_EQ(&TB, TA.getNext());
+  EXPECT_FALSE(TA.isKnownSentinel());
+  EXPECT_FALSE(TA.isSentinel());
+  TA.initializeSentinel();
+  EXPECT_TRUE(TA.isKnownSentinel());
+  EXPECT_TRUE(TA.isSentinel());
+  EXPECT_EQ(&TB, TA.getPrev());
+  EXPECT_EQ(&TB, TA.getNext());
 }
 
 } // end namespace