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, 70 insertions, 0 deletions

diff --git a/llvm/unittests/ADT/IListNodeTest.cpp b/llvm/unittests/ADT/IListNodeTest.cpp
new file mode 100644
index 00000000000..51bebc21ce6
--- /dev/null
+++ b/llvm/unittests/ADT/IListNodeTest.cpp
@@ -0,0 +1,70 @@
+//===- unittests/ADT/IListNodeTest.cpp - ilist_node unit tests ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/ilist_node.h"
+#include "gtest/gtest.h"
+#include <type_traits>
+
+using namespace llvm;
+using namespace llvm::ilist_detail;
+
+namespace {
+
+struct Node;
+
+struct TagA {};
+struct TagB {};
+
+TEST(IListNodeTest, Options) {
+  static_assert(
+      std::is_same<compute_node_options<Node>::type,
+                   compute_node_options<Node, ilist_tag<void>>::type>::value,
+      "default tag is void");
+  static_assert(
+      !std::is_same<compute_node_options<Node, ilist_tag<TagA>>::type,
+                    compute_node_options<Node, ilist_tag<void>>::type>::value,
+      "default tag is void, different from TagA");
+  static_assert(
+      !std::is_same<compute_node_options<Node, ilist_tag<TagA>>::type,
+                    compute_node_options<Node, ilist_tag<TagB>>::type>::value,
+      "TagA is not TagB");
+  static_assert(
+      std::is_same<
+          compute_node_options<Node, ilist_sentinel_tracking<false>>::type,
+          compute_node_options<Node, ilist_sentinel_tracking<false>,
+                               ilist_tag<void>>::type>::value,
+      "default tag is void, even with sentinel tracking off");
+  static_assert(
+      std::is_same<
+          compute_node_options<Node, ilist_sentinel_tracking<false>>::type,
+          compute_node_options<Node, ilist_tag<void>,
+                               ilist_sentinel_tracking<false>>::type>::value,
+      "order shouldn't matter");
+  static_assert(
+      std::is_same<
+          compute_node_options<Node, ilist_sentinel_tracking<true>>::type,
+          compute_node_options<Node, ilist_sentinel_tracking<true>,
+                               ilist_tag<void>>::type>::value,
+      "default tag is void, even with sentinel tracking on");
+  static_assert(
+      std::is_same<
+          compute_node_options<Node, ilist_sentinel_tracking<true>>::type,
+          compute_node_options<Node, ilist_tag<void>,
+                               ilist_sentinel_tracking<true>>::type>::value,
+      "order shouldn't matter");
+  static_assert(
+      std::is_same<
+          compute_node_options<Node, ilist_sentinel_tracking<true>,
+                               ilist_tag<TagA>>::type,
+          compute_node_options<Node, ilist_tag<TagA>,
+                               ilist_sentinel_tracking<true>>::type>::value,
+      "order shouldn't matter with real tags");
+}
+
+} // end namespace