diff options
author | Stephen Tozer <stephen.tozer@sony.com> | 2024-06-18 19:59:35 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-06-18 19:59:35 +0100 |
commit | 0863bd83e573f5e3e35c5c6b5750ac74f2295f48 (patch) | |
tree | abf2600e2fe968ee025534fee15789cb6dee00de | |
parent | 89fd19509292db64ea6f2fd95e3b7d40cf78b2b1 (diff) | |
download | llvm-0863bd83e573f5e3e35c5c6b5750ac74f2295f48.zip llvm-0863bd83e573f5e3e35c5c6b5750ac74f2295f48.tar.gz llvm-0863bd83e573f5e3e35c5c6b5750ac74f2295f48.tar.bz2 |
[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.
-rw-r--r-- | llvm/include/llvm/ADT/ilist_base.h | 4 | ||||
-rw-r--r-- | llvm/include/llvm/ADT/ilist_iterator.h | 45 | ||||
-rw-r--r-- | llvm/include/llvm/ADT/ilist_node.h | 39 | ||||
-rw-r--r-- | llvm/include/llvm/ADT/ilist_node_base.h | 57 | ||||
-rw-r--r-- | llvm/include/llvm/ADT/ilist_node_options.h | 43 | ||||
-rw-r--r-- | llvm/include/llvm/IR/BasicBlock.h | 10 | ||||
-rw-r--r-- | llvm/include/llvm/IR/Instruction.h | 16 | ||||
-rw-r--r-- | llvm/include/llvm/IR/ValueSymbolTable.h | 4 | ||||
-rw-r--r-- | llvm/lib/IR/BasicBlock.cpp | 5 | ||||
-rw-r--r-- | llvm/lib/IR/Instruction.cpp | 25 | ||||
-rw-r--r-- | llvm/unittests/ADT/IListBaseTest.cpp | 4 | ||||
-rw-r--r-- | llvm/unittests/ADT/IListIteratorBitsTest.cpp | 23 | ||||
-rw-r--r-- | llvm/unittests/ADT/IListIteratorTest.cpp | 21 | ||||
-rw-r--r-- | llvm/unittests/ADT/IListNodeBaseTest.cpp | 98 | ||||
-rw-r--r-- | llvm/unittests/ADT/IListNodeTest.cpp | 14 |
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 |