ADT: Split ilist_node_traits into alloc and callback, NFC
Many lists want to override only allocation semantics, or callbacks for
iplist. Split these up to prevent code duplication.
- Specialize ilist_alloc_traits to change the implementations of
deleteNode() and createNode().
- One common desire is to do nothing deleteNode() and disable
createNode(). Specialize ilist_alloc_traits to inherit from
ilist_noalloc_traits for that behaviour.
- Specialize ilist_callback_traits to use the addNodeToList(),
removeNodeFromList(), and transferNodesFromList() callbacks.
As a drive-by, add some coverage to the callback-related unit tests.
llvm-svn: 280128
diff --git a/llvm/include/llvm/ADT/ilist.h b/llvm/include/llvm/ADT/ilist.h
index 14660b2..e8d1120 100644
--- a/llvm/include/llvm/ADT/ilist.h
+++ b/llvm/include/llvm/ADT/ilist.h
@@ -33,27 +33,57 @@
namespace llvm {
-/// A fragment for template traits for intrusive list that provides default
-/// node related operations.
+/// Use new/delete by default for iplist and ilist.
///
-/// TODO: Split up (alloc vs. callback) and delete.
-template <typename NodeTy> struct ilist_node_traits {
+/// Specialize this to get different behaviour for allocation-related API. (If
+/// you really want new/delete, consider just using std::list.)
+///
+/// \see ilist_noalloc_traits
+template <typename NodeTy> struct ilist_alloc_traits {
static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
static void deleteNode(NodeTy *V) { delete V; }
+};
+/// Custom traits to disable node creation and do nothing on deletion.
+///
+/// Specialize ilist_alloc_traits to inherit from this to disable the
+/// non-intrusive parts of iplist and/or ilist. It has no createNode function,
+/// and deleteNode does nothing.
+///
+/// \code
+/// template <>
+/// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {};
+/// \endcode
+template <typename NodeTy> struct ilist_noalloc_traits {
+ static void deleteNode(NodeTy *V) {}
+};
+
+/// Callbacks do nothing by default in iplist and ilist.
+///
+/// Specialize this for to use callbacks for when nodes change their list
+/// membership.
+template <typename NodeTy> struct ilist_callback_traits {
void addNodeToList(NodeTy *) {}
void removeNodeFromList(NodeTy *) {}
/// Callback before transferring nodes to this list.
///
/// \pre \c this!=&OldList
- void transferNodesFromList(ilist_node_traits &OldList,
- ilist_iterator<NodeTy> /*first*/,
- ilist_iterator<NodeTy> /*last*/) {
+ template <class Iterator>
+ void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/,
+ Iterator /*last*/) {
(void)OldList;
}
};
+/// A fragment for template traits for intrusive list that provides default
+/// node related operations.
+///
+/// TODO: Remove this layer of indirection. It's not necessary.
+template <typename NodeTy>
+struct ilist_node_traits : ilist_alloc_traits<NodeTy>,
+ ilist_callback_traits<NodeTy> {};
+
/// Default template traits for intrusive list.
///
/// By inheriting from this, you can easily use default implementations for all
diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
index 60268b1..6333f55 100644
--- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
@@ -38,22 +38,20 @@
// Forward declaration to avoid circular include problem with TargetRegisterInfo
typedef unsigned LaneBitmask;
-template <>
-struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> {
+template <> struct ilist_traits<MachineInstr> {
private:
- // this is only set by the MachineBasicBlock owning the LiveList
- friend class MachineBasicBlock;
- MachineBasicBlock* Parent;
+ friend class MachineBasicBlock; // Set by the owning MachineBasicBlock.
+ MachineBasicBlock *Parent;
public:
- void addNodeToList(MachineInstr* N);
- void removeNodeFromList(MachineInstr* N);
- void transferNodesFromList(ilist_traits &SrcTraits,
- ilist_iterator<MachineInstr> First,
- ilist_iterator<MachineInstr> Last);
- void deleteNode(MachineInstr *N);
-private:
- void createNode(const MachineInstr &);
+ void addNodeToList(MachineInstr *N);
+ void removeNodeFromList(MachineInstr *N);
+ template <class Iterator>
+ void transferNodesFromList(ilist_traits &OldList, Iterator First,
+ Iterator Last);
+
+ void deleteNode(MachineInstr *MI);
+ // Leave out createNode...
};
class MachineBasicBlock
@@ -697,7 +695,7 @@
BranchProbability getSuccProbability(const_succ_iterator Succ) const;
// Methods used to maintain doubly linked list of blocks...
- friend struct ilist_traits<MachineBasicBlock>;
+ friend struct ilist_callback_traits<MachineBasicBlock>;
// Machine-CFG mutators
diff --git a/llvm/include/llvm/CodeGen/MachineFunction.h b/llvm/include/llvm/CodeGen/MachineFunction.h
index b6c1a08..e3c11cc 100644
--- a/llvm/include/llvm/CodeGen/MachineFunction.h
+++ b/llvm/include/llvm/CodeGen/MachineFunction.h
@@ -48,14 +48,19 @@
struct MachinePointerInfo;
struct WinEHFuncInfo;
-template <>
-struct ilist_traits<MachineBasicBlock>
- : public ilist_default_traits<MachineBasicBlock> {
+template <> struct ilist_alloc_traits<MachineBasicBlock> {
+ void deleteNode(MachineBasicBlock *MBB);
+ // Disallow createNode...
+};
+
+template <> struct ilist_callback_traits<MachineBasicBlock> {
void addNodeToList(MachineBasicBlock* MBB);
void removeNodeFromList(MachineBasicBlock* MBB);
- void deleteNode(MachineBasicBlock *MBB);
-private:
- void createNode(const MachineBasicBlock &);
+
+ template <class Iterator>
+ void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator) {
+ llvm_unreachable("Never transfer between lists");
+ }
};
/// MachineFunctionInfo - This class can be derived from and used by targets to
diff --git a/llvm/include/llvm/CodeGen/MachineInstr.h b/llvm/include/llvm/CodeGen/MachineInstr.h
index c76bcde..264a91b 100644
--- a/llvm/include/llvm/CodeGen/MachineInstr.h
+++ b/llvm/include/llvm/CodeGen/MachineInstr.h
@@ -118,7 +118,7 @@
// Intrusive list support
friend struct ilist_traits<MachineInstr>;
- friend struct ilist_traits<MachineBasicBlock>;
+ friend struct ilist_callback_traits<MachineBasicBlock>;
void setParent(MachineBasicBlock *P) { Parent = P; }
/// This constructor creates a copy of the given
diff --git a/llvm/include/llvm/CodeGen/SelectionDAG.h b/llvm/include/llvm/CodeGen/SelectionDAG.h
index cabcac4..788132d 100644
--- a/llvm/include/llvm/CodeGen/SelectionDAG.h
+++ b/llvm/include/llvm/CodeGen/SelectionDAG.h
@@ -81,12 +81,11 @@
}
};
-template <> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
+template <> struct ilist_alloc_traits<SDNode> {
static void deleteNode(SDNode *) {
llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
}
-private:
- static void createNode(const SDNode &);
+ // Don't implement createNode...
};
/// Keeps track of dbg_value information through SDISel. We do
diff --git a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
index 96ef061..ceeefc4 100644
--- a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -49,7 +49,6 @@
class MCSymbol;
template <typename T> struct DenseMapInfo;
template <typename T> struct simplify_type;
-template <typename T> struct ilist_traits;
void checkForCycles(const SDNode *N, const SelectionDAG *DAG = nullptr,
bool force = false);
@@ -503,7 +502,6 @@
static const EVT *getValueTypeList(EVT VT);
friend class SelectionDAG;
- friend struct ilist_traits<SDNode>;
// TODO: unfriend HandleSDNode once we fix its operand handling.
friend class HandleSDNode;
diff --git a/llvm/include/llvm/CodeGen/SlotIndexes.h b/llvm/include/llvm/CodeGen/SlotIndexes.h
index 57fb2df..f6cacae 100644
--- a/llvm/include/llvm/CodeGen/SlotIndexes.h
+++ b/llvm/include/llvm/CodeGen/SlotIndexes.h
@@ -69,13 +69,8 @@
};
template <>
- struct ilist_traits<IndexListEntry>
- : public ilist_default_traits<IndexListEntry> {
- void deleteNode(IndexListEntry *N) {}
-
- private:
- void createNode(const IndexListEntry &);
- };
+ struct ilist_alloc_traits<IndexListEntry>
+ : public ilist_noalloc_traits<IndexListEntry> {};
/// SlotIndex - An opaque wrapper around machine indexes.
class SlotIndex {
diff --git a/llvm/include/llvm/IR/Metadata.h b/llvm/include/llvm/IR/Metadata.h
index 91f43d3..0ce8882 100644
--- a/llvm/include/llvm/IR/Metadata.h
+++ b/llvm/include/llvm/IR/Metadata.h
@@ -1247,7 +1247,6 @@
///
/// TODO: Inherit from Metadata.
class NamedMDNode : public ilist_node<NamedMDNode> {
- friend struct ilist_traits<NamedMDNode>;
friend class LLVMContextImpl;
friend class Module;
NamedMDNode(const NamedMDNode &) = delete;
diff --git a/llvm/include/llvm/IR/Module.h b/llvm/include/llvm/IR/Module.h
index d3b56ee..f51d02e 100644
--- a/llvm/include/llvm/IR/Module.h
+++ b/llvm/include/llvm/IR/Module.h
@@ -37,12 +37,6 @@
class StructType;
template <class PtrType> class SmallPtrSetImpl;
-template<> struct ilist_traits<NamedMDNode>
- : public ilist_default_traits<NamedMDNode> {
- void addNodeToList(NamedMDNode *) {}
- void removeNodeFromList(NamedMDNode *) {}
-};
-
/// A Module instance is used to store all the information related to an
/// LLVM module. Modules are the top level container of all other LLVM
/// Intermediate Representation (IR) objects. Each module directly contains a
diff --git a/llvm/include/llvm/IR/SymbolTableListTraits.h b/llvm/include/llvm/IR/SymbolTableListTraits.h
index 87364aa..673f168 100644
--- a/llvm/include/llvm/IR/SymbolTableListTraits.h
+++ b/llvm/include/llvm/IR/SymbolTableListTraits.h
@@ -60,7 +60,7 @@
// ItemParentClass - The type of object that owns the list, e.g. BasicBlock.
//
template <typename ValueSubClass>
-class SymbolTableListTraits : public ilist_node_traits<ValueSubClass> {
+class SymbolTableListTraits : public ilist_alloc_traits<ValueSubClass> {
typedef SymbolTableList<ValueSubClass> ListTy;
typedef ilist_iterator<ValueSubClass, false> iterator;
typedef
diff --git a/llvm/include/llvm/MC/MCSection.h b/llvm/include/llvm/MC/MCSection.h
index a8d7af9..714773a 100644
--- a/llvm/include/llvm/MC/MCSection.h
+++ b/llvm/include/llvm/MC/MCSection.h
@@ -31,16 +31,9 @@
class MCSymbol;
class raw_ostream;
-template<>
-struct ilist_node_traits<MCFragment> {
- MCFragment *createNode(const MCFragment &V);
+template <> struct ilist_alloc_traits<MCFragment> {
static void deleteNode(MCFragment *V);
-
- void addNodeToList(MCFragment *) {}
- void removeNodeFromList(MCFragment *) {}
- void transferNodesFromList(ilist_node_traits & /*SrcTraits*/,
- ilist_iterator<MCFragment> /*first*/,
- ilist_iterator<MCFragment> /*last*/) {}
+ // Leave out createNode...
};
/// Instances of this class represent a uniqued identifier for a section in the
diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
index 8d34360..1788d7c 100644
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -74,7 +74,8 @@
/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
/// gets the next available unique MBB number. If it is removed from a
/// MachineFunction, it goes back to being #-1.
-void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock *N) {
+void ilist_callback_traits<MachineBasicBlock>::addNodeToList(
+ MachineBasicBlock *N) {
MachineFunction &MF = *N->getParent();
N->Number = MF.addToMBBNumbering(N);
@@ -85,7 +86,8 @@
I->AddRegOperandsToUseLists(RegInfo);
}
-void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock *N) {
+void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList(
+ MachineBasicBlock *N) {
N->getParent()->removeFromMBBNumbering(N->Number);
N->Number = -1;
}
@@ -116,10 +118,11 @@
/// When moving a range of instructions from one MBB list to another, we need to
/// update the parent pointers and the use/def lists.
-void ilist_traits<MachineInstr>::
-transferNodesFromList(ilist_traits<MachineInstr> &FromList,
- ilist_iterator<MachineInstr> First,
- ilist_iterator<MachineInstr> Last) {
+template <>
+void ilist_traits<MachineInstr>::transferNodesFromList<
+ ilist<MachineInstr>::iterator>(ilist_traits<MachineInstr> &FromList,
+ ilist<MachineInstr>::iterator First,
+ ilist<MachineInstr>::iterator Last) {
assert(Parent->getParent() == FromList.Parent->getParent() &&
"MachineInstr parent mismatch!");
assert(this != &FromList && "Called without a real transfer...");
@@ -131,7 +134,7 @@
First->setParent(Parent);
}
-void ilist_traits<MachineInstr>::deleteNode(MachineInstr* MI) {
+void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {
assert(!MI->getParent() && "MI is still in a block!");
Parent->getParent()->DeleteMachineInstr(MI);
}
diff --git a/llvm/lib/CodeGen/MachineFunction.cpp b/llvm/lib/CodeGen/MachineFunction.cpp
index c8039f5..7f1bb92 100644
--- a/llvm/lib/CodeGen/MachineFunction.cpp
+++ b/llvm/lib/CodeGen/MachineFunction.cpp
@@ -86,7 +86,7 @@
// Out-of-line virtual method.
MachineFunctionInfo::~MachineFunctionInfo() {}
-void ilist_traits<MachineBasicBlock>::deleteNode(MachineBasicBlock *MBB) {
+void ilist_alloc_traits<MachineBasicBlock>::deleteNode(MachineBasicBlock *MBB) {
MBB->getParent()->DeleteMachineBasicBlock(MBB);
}
diff --git a/llvm/lib/MC/MCFragment.cpp b/llvm/lib/MC/MCFragment.cpp
index e2c4b22..8ff8f8a 100644
--- a/llvm/lib/MC/MCFragment.cpp
+++ b/llvm/lib/MC/MCFragment.cpp
@@ -232,9 +232,7 @@
/* *** */
-void ilist_node_traits<MCFragment>::deleteNode(MCFragment *V) {
- V->destroy();
-}
+void ilist_alloc_traits<MCFragment>::deleteNode(MCFragment *V) { V->destroy(); }
MCFragment::~MCFragment() { }
diff --git a/llvm/lib/Support/YAMLParser.cpp b/llvm/lib/Support/YAMLParser.cpp
index 7490f1a..c083e1f 100644
--- a/llvm/lib/Support/YAMLParser.cpp
+++ b/llvm/lib/Support/YAMLParser.cpp
@@ -149,22 +149,15 @@
}
namespace llvm {
-template<>
-struct ilist_node_traits<Token> {
+template <> struct ilist_alloc_traits<Token> {
Token *createNode(const Token &V) {
return new (Alloc.Allocate<Token>()) Token(V);
}
static void deleteNode(Token *V) { V->~Token(); }
- void addNodeToList(Token *) {}
- void removeNodeFromList(Token *) {}
- void transferNodesFromList(ilist_node_traits & /*SrcTraits*/,
- ilist_iterator<Token> /*first*/,
- ilist_iterator<Token> /*last*/) {}
-
BumpPtrAllocator Alloc;
};
-}
+} // end namespace llvm
typedef ilist<Token> TokenQueueT;
diff --git a/llvm/unittests/ADT/IListTest.cpp b/llvm/unittests/ADT/IListTest.cpp
index 64096ee..d7cf980 100644
--- a/llvm/unittests/ADT/IListTest.cpp
+++ b/llvm/unittests/ADT/IListTest.cpp
@@ -167,6 +167,7 @@
struct NodeWithCallback : ilist_node<NodeWithCallback> {
int Value = 0;
bool IsInList = false;
+ bool WasTransferred = false;
NodeWithCallback() = default;
NodeWithCallback(int Value) : Value(Value) {}
@@ -176,29 +177,44 @@
} // end namespace
namespace llvm {
-template <>
-struct ilist_traits<NodeWithCallback>
- : public ilist_node_traits<NodeWithCallback> {
+template <> struct ilist_callback_traits<NodeWithCallback> {
void addNodeToList(NodeWithCallback *N) { N->IsInList = true; }
void removeNodeFromList(NodeWithCallback *N) { N->IsInList = false; }
+ template <class Iterator>
+ void transferNodesFromList(ilist_callback_traits &Other, Iterator First,
+ Iterator Last) {
+ for (; First != Last; ++First) {
+ First->WasTransferred = true;
+ Other.removeNodeFromList(&*First);
+ addNodeToList(&*First);
+ }
+ }
};
} // end namespace llvm
namespace {
TEST(IListTest, addNodeToList) {
- ilist<NodeWithCallback> L;
+ ilist<NodeWithCallback> L1, L2;
NodeWithCallback N(7);
ASSERT_FALSE(N.IsInList);
+ ASSERT_FALSE(N.WasTransferred);
- L.insert(L.begin(), &N);
- ASSERT_EQ(1u, L.size());
- ASSERT_EQ(&N, &*L.begin());
+ L1.insert(L1.begin(), &N);
+ ASSERT_EQ(1u, L1.size());
+ ASSERT_EQ(&N, &L1.front());
ASSERT_TRUE(N.IsInList);
+ ASSERT_FALSE(N.WasTransferred);
- L.remove(&N);
- ASSERT_EQ(0u, L.size());
+ L2.splice(L2.end(), L1);
+ ASSERT_EQ(&N, &L2.front());
+ ASSERT_TRUE(N.IsInList);
+ ASSERT_TRUE(N.WasTransferred);
+
+ L1.remove(&N);
+ ASSERT_EQ(0u, L1.size());
ASSERT_FALSE(N.IsInList);
+ ASSERT_TRUE(N.WasTransferred);
}
struct PrivateNode : private ilist_node<PrivateNode> {