From fed90b6d097d50881afb45e4d79f430db66dd741 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Mon, 28 Jul 2008 21:51:04 +0000 Subject: Fold the useful features of alist and alist_node into ilist, and a new ilist_node class, and remove them. Unlike alist_node, ilist_node doesn't attempt to manage storage itself, so it avoids the associated problems, including being opaque in gdb. Adjust the Recycler class so that it doesn't depend on alist_node. Also, change it to use explicit Size and Align parameters, allowing it to work when the largest-sized node doesn't have the greatest alignment requirement. Change MachineInstr's MachineMemOperand list from a pool-backed alist to a std::list for now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54146 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/SparseBitVector.h | 38 +--- include/llvm/ADT/alist.h | 296 -------------------------- include/llvm/ADT/alist_node.h | 123 ----------- include/llvm/ADT/ilist.h | 35 ++- include/llvm/ADT/ilist_node.h | 43 ++++ include/llvm/Analysis/AliasSetTracker.h | 19 +- include/llvm/Argument.h | 12 +- include/llvm/BasicBlock.h | 14 +- include/llvm/Bitcode/Archive.h | 16 +- include/llvm/CodeGen/MachineBasicBlock.h | 32 +-- include/llvm/CodeGen/MachineFunction.h | 29 +-- include/llvm/CodeGen/MachineInstr.h | 22 +- include/llvm/CodeGen/SelectionDAG.h | 58 +++-- include/llvm/CodeGen/SelectionDAGISel.h | 2 +- include/llvm/CodeGen/SelectionDAGNodes.h | 32 +-- include/llvm/Function.h | 15 +- include/llvm/GlobalAlias.h | 13 +- include/llvm/GlobalVariable.h | 13 +- include/llvm/Instruction.h | 15 +- include/llvm/Support/Recycler.h | 92 ++++---- include/llvm/Support/RecyclingAllocator.h | 5 +- include/llvm/SymbolTableListTraits.h | 18 +- lib/Archive/Archive.cpp | 4 +- lib/Archive/ArchiveReader.cpp | 2 - lib/CodeGen/LiveIntervalAnalysis.cpp | 2 +- lib/CodeGen/MachineBasicBlock.cpp | 36 ++-- lib/CodeGen/MachineFunction.cpp | 20 +- lib/CodeGen/MachineInstr.cpp | 9 +- lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 98 ++++----- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 29 ++- lib/Support/Allocator.cpp | 6 +- lib/VMCore/BasicBlock.cpp | 5 +- lib/VMCore/SymbolTableListTraitsImpl.h | 2 +- 33 files changed, 340 insertions(+), 815 deletions(-) delete mode 100644 include/llvm/ADT/alist.h delete mode 100644 include/llvm/ADT/alist_node.h create mode 100644 include/llvm/ADT/ilist_node.h diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index adeb541d3d..efd0accaad 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -39,7 +39,8 @@ namespace llvm { template -struct SparseBitVectorElement { +struct SparseBitVectorElement + : ilist_node > { public: typedef unsigned long BitWord; enum { @@ -48,56 +49,23 @@ public: BITS_PER_ELEMENT = ElementSize }; - SparseBitVectorElement *getNext() const { - return Next; - } - SparseBitVectorElement *getPrev() const { - return Prev; - } - - void setNext(SparseBitVectorElement *RHS) { - Next = RHS; - } - void setPrev(SparseBitVectorElement *RHS) { - Prev = RHS; - } - private: - SparseBitVectorElement *Next; - SparseBitVectorElement *Prev; // Index of Element in terms of where first bit starts. unsigned ElementIndex; BitWord Bits[BITWORDS_PER_ELEMENT]; // Needed for sentinels + friend class ilist_sentinel_traits; SparseBitVectorElement() { ElementIndex = ~0U; memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); } - friend struct ilist_traits >; public: explicit SparseBitVectorElement(unsigned Idx) { ElementIndex = Idx; memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); } - ~SparseBitVectorElement() { - } - - // Copy ctor. - SparseBitVectorElement(const SparseBitVectorElement &RHS) { - ElementIndex = RHS.ElementIndex; - std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits); - } - - // Assignment - SparseBitVectorElement& operator=(const SparseBitVectorElement& RHS) { - ElementIndex = RHS.ElementIndex; - std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits); - - return *this; - } - // Comparison. bool operator==(const SparseBitVectorElement &RHS) const { if (ElementIndex != RHS.ElementIndex) diff --git a/include/llvm/ADT/alist.h b/include/llvm/ADT/alist.h deleted file mode 100644 index 1af3e4a5c0..0000000000 --- a/include/llvm/ADT/alist.h +++ /dev/null @@ -1,296 +0,0 @@ -//==- llvm/ADT/alist.h - Linked lists with hooks -----------------*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the alist class template, and related infrastructure. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ADT_ALIST_H -#define LLVM_ADT_ALIST_H - -#include "llvm/ADT/alist_node.h" -#include "llvm/ADT/STLExtras.h" - -namespace llvm { - -/// alist_iterator - An iterator class for alist. -/// -template > > -class alist_iterator : public bidirectional_iterator { -public: - typedef bidirectional_iterator super; - typedef alist_node NodeTy; - -private: - /// NodeIter - The underlying iplist iterator that is being wrapped. - NodeIterT NodeIter; - -public: - typedef size_t size_type; - - // FIX for MSVC++. This should be reviewed more. - // typedef typename super::pointer pointer; - typedef ValueT* pointer; - - typedef typename super::reference reference; - - alist_iterator(NodeIterT NI) : NodeIter(NI) {} - alist_iterator(pointer EP) : NodeIter(NodeTy::getNode(EP)) {} - alist_iterator() : NodeIter() {} - - // This is templated so that we can allow constructing a const iterator from - // a nonconst iterator... - template - alist_iterator(const alist_iterator &RHS) - : NodeIter(RHS.getNodeIterUnchecked()) {} - - // This is templated so that we can allow assigning to a const iterator from - // a nonconst iterator... - template - const alist_iterator &operator=(const alist_iterator &RHS) { - NodeIter = RHS.getNodeIterUnchecked(); - return *this; - } - - operator pointer() const { return NodeIter->getElement((T*)0); } - - reference operator*() const { return *NodeIter->getElement((T*)0); } - pointer operator->() const { return &operator*(); } - - bool operator==(const alist_iterator &RHS) const { - return NodeIter == RHS.NodeIter; - } - bool operator!=(const alist_iterator &RHS) const { - return NodeIter != RHS.NodeIter; - } - - alist_iterator &operator--() { - --NodeIter; - return *this; - } - alist_iterator &operator++() { - ++NodeIter; - return *this; - } - alist_iterator operator--(int) { - alist_iterator tmp = *this; - --*this; - return tmp; - } - alist_iterator operator++(int) { - alist_iterator tmp = *this; - ++*this; - return tmp; - } - - NodeIterT getNodeIterUnchecked() const { return NodeIter; } -}; - -// do not implement. this is to catch errors when people try to use -// them as random access iterators -template -void operator-(int, alist_iterator); -template -void operator-(alist_iterator,int); - -template -void operator+(int, alist_iterator); -template -void operator+(alist_iterator,int); - -// operator!=/operator== - Allow mixed comparisons without dereferencing -// the iterator, which could very likely be pointing to end(). -template -bool operator!=(T* LHS, const alist_iterator &RHS) { - return LHS != RHS.getNodeIterUnchecked().getNodePtrUnchecked() - ->getElement((T*)0); -} -template -bool operator==(T* LHS, const alist_iterator &RHS) { - return LHS == RHS.getNodeIterUnchecked().getNodePtrUnchecked() - ->getElement((T*)0); -} - -// Allow alist_iterators to convert into pointers to a node automatically when -// used by the dyn_cast, cast, isa mechanisms... - -template struct simplify_type; - -template -struct simplify_type > { - typedef alist_node NodeTy; - typedef NodeTy* SimpleType; - - static SimpleType - getSimplifiedValue(const alist_iterator &Node) { - return &*Node; - } -}; -template -struct simplify_type > { - typedef alist_node NodeTy; - typedef NodeTy* SimpleType; - - static SimpleType - getSimplifiedValue(const alist_iterator &Node) { - return &*Node; - } -}; - -/// Template traits for alist. By specializing this template class, you -/// can register custom actions to be run when a node is added to or removed -/// from an alist. A common use of this is to update parent pointers. -/// -template -class alist_traits { -public: - typedef alist_iterator iterator; - - void addNodeToList(T *) {} - void removeNodeFromList(T *) {} - void transferNodesFromList(alist_traits &, iterator, iterator) {} - void deleteNode(T *E) { delete alist_node::getNode(E); } -}; - -/// alist - This class is an ilist-style container that automatically -/// adds the next/prev pointers. It is designed to work in cooperation -/// with . -/// -template -class alist { -public: - typedef alist_node NodeTy; - typedef typename ilist::size_type size_type; - -private: - /// NodeListTraits - ilist traits for NodeList. - /// - struct NodeListTraits : ilist_traits > { - alist_traits UserTraits; - - void addNodeToList(NodeTy *N) { - UserTraits.addNodeToList(N->getElement((T*)0)); - } - void removeNodeFromList(NodeTy *N) { - UserTraits.removeNodeFromList(N->getElement((T*)0)); - } - void transferNodesFromList(iplist &L2, - ilist_iterator first, - ilist_iterator last) { - UserTraits.transferNodesFromList(L2.UserTraits, - iterator(first), - iterator(last)); - } - }; - - /// NodeList - Doubly-linked list of nodes that have constructed - /// contents and may be in active use. - /// - iplist NodeList; - -public: - ~alist() { clear(); } - - typedef alist_iterator > - iterator; - typedef alist_iterator > - const_iterator; - typedef std::reverse_iterator reverse_iterator; - typedef std::reverse_iterator const_reverse_iterator; - - iterator begin() { return iterator(NodeList.begin()); } - iterator end() { return iterator(NodeList.end()); } - const_iterator begin() const { return const_iterator(NodeList.begin()); } - const_iterator end() const { return const_iterator(NodeList.end()); } - reverse_iterator rbegin() { return reverse_iterator(NodeList.rbegin()); } - reverse_iterator rend() { return reverse_iterator(NodeList.rend()); } - const_reverse_iterator rbegin() const { - return const_reverse_iterator(NodeList.rbegin()); - } - const_reverse_iterator rend() const { - return const_reverse_iterator(NodeList.rend()); - } - - typedef T& reference; - typedef const T& const_reference; - reference front() { return *NodeList.front().getElement((T*)0); } - reference back() { return *NodeList.back().getElement((T*)0); } - const_reference front() const { return *NodeList.front().getElement((T*)0); } - const_reference back() const { return *NodeList.back().getElement((T*)0); } - - bool empty() const { return NodeList.empty(); } - size_type size() const { return NodeList.size(); } - - void push_front(T *E) { - NodeTy *N = alist_node::getNode(E); - assert(N->getPrev() == 0); - assert(N->getNext() == 0); - NodeList.push_front(N); - } - void push_back(T *E) { - NodeTy *N = alist_node::getNode(E); - assert(N->getPrev() == 0); - assert(N->getNext() == 0); - NodeList.push_back(N); - } - iterator insert(iterator I, T *E) { - NodeTy *N = alist_node::getNode(E); - assert(N->getPrev() == 0); - assert(N->getNext() == 0); - return iterator(NodeList.insert(I.getNodeIterUnchecked(), N)); - } - void splice(iterator where, alist &Other) { - NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList); - } - void splice(iterator where, alist &Other, iterator From) { - NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList, - From.getNodeIterUnchecked()); - } - void splice(iterator where, alist &Other, iterator From, - iterator To) { - NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList, - From.getNodeIterUnchecked(), To.getNodeIterUnchecked()); - } - - void pop_front() { - erase(NodeList.begin()); - } - void pop_back() { - erase(prior(NodeList.end())); - } - iterator erase(iterator I) { - iterator Next = next(I); - NodeTy *N = NodeList.remove(I.getNodeIterUnchecked()); - NodeList.UserTraits.deleteNode(N->getElement((T*)0)); - return Next; - } - iterator erase(iterator first, iterator last) { - while (first != last) - first = erase(first); - return last; - } - - T *remove(T *E) { - NodeTy *N = alist_node::getNode(E); - return NodeList.remove(N)->getElement((T*)0); - } - - void clear() { - while (!empty()) pop_front(); - } - - alist_traits &getTraits() { - return NodeList.UserTraits; - } -}; - -} - -#endif diff --git a/include/llvm/ADT/alist_node.h b/include/llvm/ADT/alist_node.h deleted file mode 100644 index fcdf22c45c..0000000000 --- a/include/llvm/ADT/alist_node.h +++ /dev/null @@ -1,123 +0,0 @@ -//==- llvm/ADT/alist_node.h - Next/Prev helper class for alist ---*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the alist_node class template, which is used by the alist -// class template to provide next/prev pointers for arbitrary objects. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ADT_ALIST_NODE_H -#define LLVM_ADT_ALIST_NODE_H - -#include "llvm/ADT/ilist.h" -#include "llvm/Support/AlignOf.h" -#include "llvm/Support/DataTypes.h" -#include - -namespace llvm { - -/// alist_node - This is a utility class used by alist. It holds prev and next -/// pointers for use with ilists, as well as storage for objects as large as -/// LargestT, that are in T's inheritance tree. -/// -template -class alist_node { - alist_node *Prev, *Next; - -public: - alist_node() : Prev(0), Next(0) {} - - alist_node *getPrev() const { return Prev; } - alist_node *getNext() const { return Next; } - void setPrev(alist_node *N) { Prev = N; } - void setNext(alist_node *N) { Next = N; } - - union { - char Bytes[sizeof(LargestT)]; - long long L; - void *P; - } Storage; - - template - SubClass *getElement(SubClass *) { - assert(sizeof(SubClass) <= sizeof(LargestT)); - return reinterpret_cast(&Storage.Bytes); - } - - template - const SubClass *getElement(SubClass *) const { - assert(sizeof(SubClass) <= sizeof(LargestT)); - return reinterpret_cast(&Storage.Bytes); - } - - // This code essentially does offsetof, but actual offsetof hits an ICE in - // GCC 4.0 relating to offsetof being used inside a template. - static alist_node* getNode(T *D) { - return reinterpret_cast(reinterpret_cast(D) - - (uintptr_t)&getNull()->Storage); - } - static const alist_node* getNode(const T *D) { - return reinterpret_cast(reinterpret_cast(D) - - (uintptr_t)&getNull()->Storage); - } -private: - static alist_node* getNull() { return 0; } -}; - -// A specialization of ilist_traits for alist_nodes. -template -class ilist_traits > { -public: - typedef alist_node NodeTy; - -protected: - // Allocate a sentinel inside the traits class. This works - // because iplist carries an instance of the traits class. - NodeTy Sentinel; - -public: - static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); } - static NodeTy *getNext(NodeTy *N) { return N->getNext(); } - static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); } - static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); } - - static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); } - static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); } - - NodeTy *createSentinel() const { - assert(Sentinel.getPrev() == 0); - assert(Sentinel.getNext() == 0); - return const_cast(&Sentinel); - } - - void destroySentinel(NodeTy *N) { - assert(N == &Sentinel); N = N; - Sentinel.setPrev(0); - Sentinel.setNext(0); - } - - void addNodeToList(NodeTy *) {} - void removeNodeFromList(NodeTy *) {} - void transferNodesFromList(iplist &, - ilist_iterator /*first*/, - ilist_iterator /*last*/) {} - - // Ideally we wouldn't implement this, but ilist's clear calls it, - // which is called from ilist's destructor. We won't ever call - // either of those with a non-empty list, but statically this - // method needs to exist. - void deleteNode(NodeTy *) { assert(0); } - -private: - static NodeTy *createNode(const NodeTy &V); // do not implement -}; - -} - -#endif diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index 41253e030c..3ffc8010ee 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -47,10 +47,11 @@ namespace llvm { template class iplist; template class ilist_iterator; -// Template traits for intrusive list. By specializing this template class, you -// can change what next/prev fields are used to store the links... +/// ilist_nextprev_traits - A fragment for template traits for intrusive list +/// that provides default next/prev implementations for common operations. +/// template -struct ilist_traits { +struct ilist_nextprev_traits { static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); } static NodeTy *getNext(NodeTy *N) { return N->getNext(); } static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); } @@ -58,25 +59,43 @@ struct ilist_traits { static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); } static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); } +}; - static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); } - static void deleteNode(NodeTy *V) { delete V; } - +/// ilist_sentinel_traits - A fragment for template traits for intrusive list +/// that provides default sentinel implementations for common operations. +/// +template +struct ilist_sentinel_traits { static NodeTy *createSentinel() { return new NodeTy(); } static void destroySentinel(NodeTy *N) { delete N; } +}; + +/// ilist_default_traits - Default template traits for intrusive list. +/// By inheriting from this, you can easily use default implementations +/// for all common operations. +/// +template +struct ilist_default_traits : ilist_nextprev_traits, + ilist_sentinel_traits { + static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); } + static void deleteNode(NodeTy *V) { delete V; } void addNodeToList(NodeTy *NTy) {} void removeNodeFromList(NodeTy *NTy) {} - void transferNodesFromList(iplist &L2, + void transferNodesFromList(ilist_default_traits &SrcTraits, ilist_iterator first, ilist_iterator last) {} }; +// Template traits for intrusive list. By specializing this template class, you +// can change what next/prev fields are used to store the links... +template +struct ilist_traits : ilist_default_traits {}; + // Const traits are the same as nonconst traits... template struct ilist_traits : public ilist_traits {}; - //===----------------------------------------------------------------------===// // ilist_iterator - Iterator for intrusive list. // diff --git a/include/llvm/ADT/ilist_node.h b/include/llvm/ADT/ilist_node.h new file mode 100644 index 0000000000..9e60311706 --- /dev/null +++ b/include/llvm/ADT/ilist_node.h @@ -0,0 +1,43 @@ +//==-- llvm/ADT/ilist_node.h - Intrusive Linked List Helper ------*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the ilist_node class template, which is a convenient +// base class for creating classes that can be used with ilists. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_NODE_H +#define LLVM_ADT_ILIST_NODE_H + +namespace llvm { + +template +struct ilist_nextprev_traits; + +/// ilist_node - Base class that provides next/prev services for nodes +/// that use ilist_nextprev_traits or ilist_default_traits. +/// +template +class ilist_node { +private: + friend struct ilist_nextprev_traits; + NodeTy *Prev, *Next; + NodeTy *getPrev() { return Prev; } + NodeTy *getNext() { return Next; } + const NodeTy *getPrev() const { return Prev; } + const NodeTy *getNext() const { return Next; } + void setPrev(NodeTy *N) { Prev = N; } + void setNext(NodeTy *N) { Next = N; } +protected: + ilist_node() : Prev(0), Next(0) {} +}; + +} // End llvm namespace + +#endif diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index d9e45ce9a1..2dcc2bebe0 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -22,6 +22,7 @@ #include "llvm/ADT/iterator.h" #include "llvm/ADT/hash_map.h" #include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" namespace llvm { @@ -33,7 +34,7 @@ class VAArgInst; class AliasSetTracker; class AliasSet; -class AliasSet { +class AliasSet : public ilist_node { friend class AliasSetTracker; class PointerRec; @@ -118,12 +119,6 @@ class AliasSet { // Volatile - True if this alias set contains volatile loads or stores. bool Volatile : 1; - friend struct ilist_traits; - AliasSet *getPrev() const { return Prev; } - AliasSet *getNext() const { return Next; } - void setPrev(AliasSet *P) { Prev = P; } - void setNext(AliasSet *N) { Next = N; } - void addRef() { ++RefCount; } void dropRef(AliasSetTracker &AST) { assert(RefCount >= 1 && "Invalid reference count detected!"); @@ -197,15 +192,15 @@ public: }; private: - // Can only be created by AliasSetTracker + // Can only be created by AliasSetTracker. Also, ilist creates one + // to serve as a sentinel. + friend struct ilist_sentinel_traits; AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0), AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) { } - AliasSet(const AliasSet &AS) { - assert(0 && "Copy ctor called!?!?!"); - abort(); - } + AliasSet(const AliasSet &AS); // do not implement + void operator=(const AliasSet &AS); // do not implement HashNodePair *getSomePointer() const { return PtrList; diff --git a/include/llvm/Argument.h b/include/llvm/Argument.h index d203a935bd..650bee3d10 100644 --- a/include/llvm/Argument.h +++ b/include/llvm/Argument.h @@ -27,12 +27,9 @@ template /// in the body of a function, it represents the value of the actual argument /// the function was called with. /// @brief LLVM Argument representation -class Argument : public Value { // Defined in the Function.cpp file +class Argument : public Value, public ilist_node { Function *Parent; - Argument *Prev, *Next; // Next and Prev links for our intrusive linked list - void setNext(Argument *N) { Next = N; } - void setPrev(Argument *N) { Prev = N; } friend class SymbolTableListTraits; void setParent(Function *parent); @@ -80,13 +77,6 @@ public: static inline bool classof(const Value *V) { return V->getValueID() == ArgumentVal; } - -private: - // getNext/Prev - Return the next or previous argument in the list. - Argument *getNext() { return Next; } - const Argument *getNext() const { return Next; } - Argument *getPrev() { return Prev; } - const Argument *getPrev() const { return Prev; } }; } // End llvm namespace diff --git a/include/llvm/BasicBlock.h b/include/llvm/BasicBlock.h index 108f43a767..47478f2009 100644 --- a/include/llvm/BasicBlock.h +++ b/include/llvm/BasicBlock.h @@ -49,17 +49,15 @@ template<> struct ilist_traits /// modifying a program. However, the verifier will ensure that basic blocks /// are "well formed". /// @brief LLVM Basic Block Representation -class BasicBlock : public Value { // Basic blocks are data objects also +class BasicBlock : public Value, // Basic blocks are data objects also + public ilist_node { public: typedef iplist InstListType; private : InstListType InstList; - BasicBlock *Prev, *Next; // Next and Prev links for our intrusive linked list Function *Parent; void setParent(Function *parent); - void setNext(BasicBlock *N) { Next = N; } - void setPrev(BasicBlock *N) { Prev = N; } friend class SymbolTableListTraits; BasicBlock(const BasicBlock &); // Do not implement @@ -204,14 +202,6 @@ public: BasicBlock *Obj = 0; return unsigned(reinterpret_cast(&Obj->InstList)); } - -private: - // getNext/Prev - Return the next or previous basic block in the list. Access - // these with Function::iterator. - BasicBlock *getNext() { return Next; } - const BasicBlock *getNext() const { return Next; } - BasicBlock *getPrev() { return Prev; } - const BasicBlock *getPrev() const { return Prev; } }; inline int diff --git a/include/llvm/Bitcode/Archive.h b/include/llvm/Bitcode/Archive.h index 91684c62e2..6ba11531dd 100644 --- a/include/llvm/Bitcode/Archive.h +++ b/include/llvm/Bitcode/Archive.h @@ -18,6 +18,7 @@ #define LLVM_BITCODE_ARCHIVE_H #include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" #include "llvm/System/Path.h" #include #include @@ -39,7 +40,7 @@ class ArchiveMemberHeader; // Internal implementation class /// construct ArchiveMember instances. You should obtain them from the methods /// of the Archive class instead. /// @brief This class represents a single archive member. -class ArchiveMember { +class ArchiveMember : public ilist_node { /// @name Types /// @{ public: @@ -164,23 +165,10 @@ class ArchiveMember { /// @brief Replace contents of archive member with a new file. bool replaceWith(const sys::Path &aFile, std::string* ErrMsg); - /// @} - /// @name ilist methods - do not use - /// @{ - public: - const ArchiveMember *getNext() const { return next; } - const ArchiveMember *getPrev() const { return prev; } - ArchiveMember *getNext() { return next; } - ArchiveMember *getPrev() { return prev; } - void setPrev(ArchiveMember* p) { prev = p; } - void setNext(ArchiveMember* n) { next = n; } - /// @} /// @name Data /// @{ private: - ArchiveMember* next; ///< Pointer to next archive member - ArchiveMember* prev; ///< Pointer to previous archive member Archive* parent; ///< Pointer to parent archive sys::PathWithStatus path; ///< Path of file containing the member sys::FileStatus info; ///< Status info (size,mode,date) diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index f0f9d54af5..8ee75c9c9f 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -19,30 +19,34 @@ #include "llvm/Support/Streams.h" namespace llvm { - class MachineFunction; + +class BasicBlock; +class MachineFunction; template <> -struct alist_traits { -protected: +class ilist_traits : public ilist_default_traits { + mutable MachineInstr Sentinel; + // this is only set by the MachineBasicBlock owning the LiveList friend class MachineBasicBlock; MachineBasicBlock* Parent; - typedef alist_iterator iterator; - public: - alist_traits() : Parent(0) { } + MachineInstr *createSentinel() const { return &Sentinel; } + void destroySentinel(MachineInstr *) const {} void addNodeToList(MachineInstr* N); void removeNodeFromList(MachineInstr* N); - void transferNodesFromList(alist_traits &, iterator, iterator); + void transferNodesFromList(ilist_traits &SrcTraits, + ilist_iterator first, + ilist_iterator last); void deleteNode(MachineInstr *N); +private: + void createNode(const MachineInstr &); }; -class BasicBlock; - -class MachineBasicBlock { - typedef alist Instructions; +class MachineBasicBlock : public ilist_node { + typedef ilist Instructions; Instructions Insts; const BasicBlock *BB; int Number; @@ -65,6 +69,10 @@ class MachineBasicBlock { /// exception handler. bool IsLandingPad; + // Intrusive list support + friend class ilist_sentinel_traits; + MachineBasicBlock() {} + explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); ~MachineBasicBlock(); @@ -287,7 +295,7 @@ public: void setNumber(int N) { Number = N; } private: // Methods used to maintain doubly linked list of blocks... - friend struct alist_traits; + friend struct ilist_traits; // Machine-CFG mutators diff --git a/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h index 98f3a94839..7b24600b49 100644 --- a/include/llvm/CodeGen/MachineFunction.h +++ b/include/llvm/CodeGen/MachineFunction.h @@ -18,7 +18,7 @@ #ifndef LLVM_CODEGEN_MACHINEFUNCTION_H #define LLVM_CODEGEN_MACHINEFUNCTION_H -#include "llvm/ADT/alist.h" +#include "llvm/ADT/ilist.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/Support/Annotation.h" #include "llvm/Support/Allocator.h" @@ -34,15 +34,18 @@ class MachineConstantPool; class MachineJumpTableInfo; template <> -class alist_traits { - typedef alist_iterator iterator; +class ilist_traits + : public ilist_default_traits { + mutable MachineBasicBlock Sentinel; public: + MachineBasicBlock *createSentinel() const { return &Sentinel; } + void destroySentinel(MachineBasicBlock *) const {} + void addNodeToList(MachineBasicBlock* MBB); void removeNodeFromList(MachineBasicBlock* MBB); - void transferNodesFromList(alist_traits &, - iterator, - iterator) {} void deleteNode(MachineBasicBlock *MBB); +private: + void createNode(const MachineBasicBlock &); }; /// MachineFunctionInfo - This class can be derived from and used by targets to @@ -87,11 +90,8 @@ class MachineFunction : private Annotation { // Allocation management for basic blocks in function. Recycler BasicBlockRecycler; - // Allocation management for memoperands in function. - Recycler MemOperandRecycler; - // List of machine basic blocks in function - typedef alist BasicBlockListType; + typedef ilist BasicBlockListType; BasicBlockListType BasicBlocks; public: @@ -302,15 +302,6 @@ public: /// DeleteMachineBasicBlock - Delete the given MachineBasicBlock. /// void DeleteMachineBasicBlock(MachineBasicBlock *MBB); - - /// CreateMachineMemOperand - Allocate a new MachineMemOperand. Use this - /// instead of `new MachineMemOperand'. - /// - MachineMemOperand *CreateMachineMemOperand(const MachineMemOperand &MMO); - - /// DeleteMachineMemOperand - Delete the given MachineMemOperand. - /// - void DeleteMachineMemOperand(MachineMemOperand *MMO); }; //===--------------------------------------------------------------------===// diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h index 31f4974699..bcbcf316d0 100644 --- a/include/llvm/CodeGen/MachineInstr.h +++ b/include/llvm/CodeGen/MachineInstr.h @@ -16,9 +16,12 @@ #ifndef LLVM_CODEGEN_MACHINEINSTR_H #define LLVM_CODEGEN_MACHINEINSTR_H -#include "llvm/ADT/alist.h" +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineMemOperand.h" +#include #include namespace llvm { @@ -31,13 +34,13 @@ class MachineFunction; //===----------------------------------------------------------------------===// /// MachineInstr - Representation of each machine instruction. /// -class MachineInstr { +class MachineInstr : public ilist_node { const TargetInstrDesc *TID; // Instruction descriptor. unsigned short NumImplicitOps; // Number of implicit operands (which // are determined at construction time). std::vector Operands; // the operands - alist MemOperands; // information on memory references + std::list MemOperands; // information on memory references MachineBasicBlock *Parent; // Pointer to the owning basic block. // OperandComplete - Return true if it's illegal to add a new operand @@ -47,8 +50,9 @@ class MachineInstr { void operator=(const MachineInstr&); // DO NOT IMPLEMENT // Intrusive list support - friend struct alist_traits; - friend struct alist_traits; + friend struct ilist_traits; + friend struct ilist_traits; + friend struct ilist_sentinel_traits; void setParent(MachineBasicBlock *P) { Parent = P; } /// MachineInstr ctor - This constructor creates a copy of the given @@ -105,13 +109,13 @@ public: unsigned getNumExplicitOperands() const; /// Access to memory operands of the instruction - alist::iterator memoperands_begin() + std::list::iterator memoperands_begin() { return MemOperands.begin(); } - alist::iterator memoperands_end() + std::list::iterator memoperands_end() { return MemOperands.end(); } - alist::const_iterator memoperands_begin() const + std::list::const_iterator memoperands_begin() const { return MemOperands.begin(); } - alist::const_iterator memoperands_end() const + std::list::const_iterator memoperands_end() const { return MemOperands.end(); } bool memoperands_empty() const { return MemOperands.empty(); } diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index 692d9027c5..49dbd4347a 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -15,6 +15,7 @@ #ifndef LLVM_CODEGEN_SELECTIONDAG_H #define LLVM_CODEGEN_SELECTIONDAG_H +#include "llvm/ADT/ilist.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/StringMap.h" #include "llvm/CodeGen/SelectionDAGNodes.h" @@ -26,13 +27,38 @@ #include namespace llvm { - class AliasAnalysis; - class TargetLowering; - class TargetMachine; - class MachineModuleInfo; - class MachineFunction; - class MachineConstantPoolValue; - class FunctionLoweringInfo; + +class AliasAnalysis; +class TargetLowering; +class TargetMachine; +class MachineModuleInfo; +class MachineFunction; +class MachineConstantPoolValue; +class FunctionLoweringInfo; + +/// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use +/// pool allocation with recycling. +/// +typedef RecyclingAllocator::Alignment> + NodeAllocatorType; + +template<> class ilist_traits : public ilist_default_traits { + mutable SDNode Sentinel; +public: + ilist_traits() : Sentinel(ISD::DELETED_NODE, SDVTList()) {} + + SDNode *createSentinel() const { + return &Sentinel; + } + static void destroySentinel(SDNode *) {} + + static void deleteNode(SDNode *) { + assert(0 && "ilist_traits shouldn't see a deleteNode call!"); + } +private: + static void createNode(const SDNode &); +}; /// SelectionDAG class - This is used to represent a portion of an LLVM function /// in a low-level Data Dependence DAG representation suitable for instruction @@ -55,7 +81,12 @@ class SelectionDAG { SDValue Root, EntryNode; /// AllNodes - A linked list of nodes in the current DAG. - alist &AllNodes; + ilist AllNodes; + + /// NodeAllocator - Pool allocation for nodes. The allocator isn't + /// allocated inside this class because we want to reuse a single + /// recycler across multiple SelectionDAG runs. + NodeAllocatorType &NodeAllocator; /// CSEMap - This structure is used to memoize nodes, automatically performing /// CSE with existing nodes with a duplicate is requested. @@ -71,8 +102,8 @@ class SelectionDAG { public: SelectionDAG(TargetLowering &tli, MachineFunction &mf, FunctionLoweringInfo &fli, MachineModuleInfo *mmi, - alist &NodePool) - : TLI(tli), MF(mf), FLI(fli), MMI(mmi), AllNodes(NodePool) { + NodeAllocatorType &nodeallocator) + : TLI(tli), MF(mf), FLI(fli), MMI(mmi), NodeAllocator(nodeallocator) { EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); } ~SelectionDAG(); @@ -108,13 +139,13 @@ public: /// void setGraphColor(const SDNode *N, const char *Color); - typedef alist::const_iterator allnodes_const_iterator; + typedef ilist::const_iterator allnodes_const_iterator; allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } - typedef alist::iterator allnodes_iterator; + typedef ilist::iterator allnodes_iterator; allnodes_iterator allnodes_begin() { return AllNodes.begin(); } allnodes_iterator allnodes_end() { return AllNodes.end(); } - alist::size_type allnodes_size() const { + ilist::size_type allnodes_size() const { return AllNodes.size(); } @@ -682,7 +713,6 @@ public: SDValue getShuffleScalarElt(const SDNode *N, unsigned Idx); private: - inline alist_traits::AllocatorType &getAllocator(); void RemoveNodeFromCSEMaps(SDNode *N); SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h index c384fa512d..668e64eb87 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -182,7 +182,7 @@ private: FunctionLoweringInfo &FuncInfo); void SelectBasicBlock(BasicBlock *BB, MachineFunction &MF, FunctionLoweringInfo &FuncInfo, - alist &AllNodes); + NodeAllocatorType &NodeAllocator); void BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, std::vector > &PHINodesToUpdate, diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index d690732ec2..dbb12947f2 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -25,7 +25,8 @@ #include "llvm/ADT/iterator.h" #include "llvm/ADT/APFloat.h" #include "llvm/ADT/APInt.h" -#include "llvm/ADT/alist.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/Support/Allocator.h" @@ -43,6 +44,7 @@ class SDNode; class CompileUnitDesc; template struct DenseMapInfo; template struct simplify_type; +template class ilist_traits; /// SDVTList - This represents a list of ValueType's that has been intern'd by /// a SelectionDAG. Instances of this simple value class are returned by @@ -1028,7 +1030,7 @@ public: /// SDNode - Represents one node in the SelectionDAG. /// -class SDNode : public FoldingSetNode { +class SDNode : public FoldingSetNode, public ilist_node { private: /// NodeType - The operation that this node performs. /// @@ -1268,6 +1270,7 @@ public: protected: friend class SelectionDAG; + friend class ilist_traits; /// getValueTypeList - Return a pointer to the specified value type. /// @@ -2236,27 +2239,10 @@ template <> struct GraphTraits { /// typedef LoadSDNode LargestSDNode; -// alist_traits specialization for pool-allocating SDNodes. -template <> -class alist_traits { - typedef alist_iterator iterator; - -public: - // Pool-allocate and recycle SDNodes. - typedef RecyclingAllocator - AllocatorType; - - // Allocate the allocator immediately inside the traits class. - AllocatorType Allocator; - - void addNodeToList(SDNode*) {} - void removeNodeFromList(SDNode*) {} - void transferNodesFromList(alist_traits &, iterator, iterator) {} - void deleteNode(SDNode *N) { - N->~SDNode(); - Allocator.Deallocate(N); - } -}; +/// MostAlignedSDNode - The SDNode class with the greatest alignment +/// requirement. +/// +typedef ConstantSDNode MostAlignedSDNode; namespace ISD { /// isNormalLoad - Returns true if the specified node is a non-extending diff --git a/include/llvm/Function.h b/include/llvm/Function.h index 2ec38e1d00..9954418ab8 100644 --- a/include/llvm/Function.h +++ b/include/llvm/Function.h @@ -51,7 +51,8 @@ template<> struct ilist_traits static int getListOffset(); }; -class Function : public GlobalValue, public Annotable { +class Function : public GlobalValue, public Annotable, + public ilist_node { public: typedef iplist ArgumentListType; typedef iplist BasicBlockListType; @@ -76,18 +77,6 @@ private: friend class SymbolTableListTraits; void setParent(Module *parent); - Function *Prev, *Next; - void setNext(Function *N) { Next = N; } - void setPrev(Function *N) { Prev = N; } - - // getNext/Prev - Return the next or previous function in the list. These - // methods should never be used directly, and are only used to implement the - // function list as part of the module. - // - Function *getNext() { return Next; } - const Function *getNext() const { return Next; } - Function *getPrev() { return Prev; } - const Function *getPrev() const { return Prev; } /// hasLazyArguments/CheckLazyArguments - The argument list of a function is /// built on demand, so that the list isn't allocated until the first client diff --git a/include/llvm/GlobalAlias.h b/include/llvm/GlobalAlias.h index 7c147eb62a..124cf94fa9 100644 --- a/include/llvm/GlobalAlias.h +++ b/include/llvm/GlobalAlias.h @@ -17,6 +17,7 @@ #include "llvm/GlobalValue.h" #include "llvm/OperandTraits.h" +#include "llvm/ADT/ilist_node.h" namespace llvm { @@ -26,23 +27,13 @@ class PointerType; template class SymbolTableListTraits; -class GlobalAlias : public GlobalValue { +class GlobalAlias : public GlobalValue, public ilist_node { friend class SymbolTableListTraits; void operator=(const GlobalAlias &); // Do not implement GlobalAlias(const GlobalAlias &); // Do not implement void setParent(Module *parent); - GlobalAlias *Prev, *Next; - void setNext(GlobalAlias *N) { Next = N; } - void setPrev(GlobalAlias *N) { Prev = N; } - - // getNext/Prev - Return the next or previous alias in the list. - GlobalAlias *getNext() { return Next; } - const GlobalAlias *getNext() const { return Next; } - GlobalAlias *getPrev() { return Prev; } - const GlobalAlias *getPrev() const { return Prev; } - public: // allocate space for exactly one operand void *operator new(size_t s) { diff --git a/include/llvm/GlobalVariable.h b/include/llvm/GlobalVariable.h index a578cd1c09..b6910d54c9 100644 --- a/include/llvm/GlobalVariable.h +++ b/include/llvm/GlobalVariable.h @@ -22,6 +22,7 @@ #include "llvm/GlobalValue.h" #include "llvm/OperandTraits.h" +#include "llvm/ADT/ilist_node.h" namespace llvm { @@ -31,7 +32,7 @@ class PointerType; template class SymbolTableListTraits; -class GlobalVariable : public GlobalValue { +class GlobalVariable : public GlobalValue, public ilist_node { friend class SymbolTableListTraits; void *operator new(size_t, unsigned); // Do not implement void operator=(const GlobalVariable &); // Do not implement @@ -39,10 +40,6 @@ class GlobalVariable : public GlobalValue { void setParent(Module *parent); - GlobalVariable *Prev, *Next; - void setNext(GlobalVariable *N) { Next = N; } - void setPrev(GlobalVariable *N) { Prev = N; } - bool isConstantGlobal : 1; // Is this a global constant? bool isThreadLocalSymbol : 1; // Is this symbol "Thread Local"? @@ -144,12 +141,6 @@ public: static inline bool classof(const Value *V) { return V->getValueID() == Value::GlobalVariableVal; } -private: - // getNext/Prev - Return the next or previous global variable in the list. - GlobalVariable *getNext() { return Next; } - const GlobalVariable *getNext() const { return Next; } - GlobalVariable *getPrev() { return Prev; } - const GlobalVariable *getPrev() const { return Prev; } }; template <> diff --git a/include/llvm/Instruction.h b/include/llvm/Instruction.h index 89e3e23499..ac33a68bbf 100644 --- a/include/llvm/Instruction.h +++ b/include/llvm/Instruction.h @@ -16,6 +16,7 @@ #define LLVM_INSTRUCTION_H #include "llvm/User.h" +#include "llvm/ADT/ilist_node.h" namespace llvm { @@ -24,15 +25,11 @@ struct AssemblyAnnotationWriter; template class SymbolTableListTraits; -class Instruction : public User { +class Instruction : public User, public ilist_node { void operator=(const Instruction &); // Do not implement Instruction(const Instruction &); // Do not implement BasicBlock *Parent; - Instruction *Prev, *Next; // Next and Prev links for our intrusive linked list - - void setNext(Instruction *N) { Next = N; } - void setPrev(Instruction *N) { Prev = N; } friend class SymbolTableListTraits; void setParent(BasicBlock *P); @@ -230,14 +227,6 @@ public: #define LAST_OTHER_INST(N) OtherOpsEnd = N+1 #include "llvm/Instruction.def" }; - -private: - // getNext/Prev - Return the next or previous instruction in the list. The - // last node in the list is a terminator instruction. - Instruction *getNext() { return Next; } - const Instruction *getNext() const { return Next; } - Instruction *getPrev() { return Prev; } - const Instruction *getPrev() const { return Prev; } }; } // End llvm namespace diff --git a/include/llvm/Support/Recycler.h b/include/llvm/Support/Recycler.h index 4750a6d178..3f235b6e72 100644 --- a/include/llvm/Support/Recycler.h +++ b/include/llvm/Support/Recycler.h @@ -15,62 +15,81 @@ #ifndef LLVM_SUPPORT_RECYCLER_H #define LLVM_SUPPORT_RECYCLER_H -#include "llvm/ADT/alist_node.h" +#include "llvm/ADT/ilist.h" +#include "llvm/Support/AlignOf.h" +#include namespace llvm { /// PrintRecyclingAllocatorStats - Helper for RecyclingAllocator for /// printing statistics. /// -void PrintRecyclerStats(size_t LargestTypeSize, size_t FreeListSize); +void PrintRecyclerStats(size_t Size, size_t Align, size_t FreeListSize); + +/// RecyclerStruct - Implementation detail for Recycler. This is a +/// class that the recycler imposes on free'd memory to carve out +/// next/prev pointers. +struct RecyclerStruct { + RecyclerStruct *Prev, *Next; +}; + +template<> +struct ilist_traits : ilist_default_traits { + static RecyclerStruct *getPrev(const RecyclerStruct *t) { return t->Prev; } + static RecyclerStruct *getNext(const RecyclerStruct *t) { return t->Next; } + static void setPrev(RecyclerStruct *t, RecyclerStruct *p) { t->Prev = p; } + static void setNext(RecyclerStruct *t, RecyclerStruct *n) { t->Next = n; } + + mutable RecyclerStruct Sentinel; + RecyclerStruct *createSentinel() const { + return &Sentinel; + } + static void destroySentinel(RecyclerStruct *) {} + + static void deleteNode(RecyclerStruct *) { + assert(0 && "Recycler's ilist_traits shouldn't see a deleteNode call!"); + } +}; /// Recycler - This class manages a linked-list of deallocated nodes /// and facilitates reusing deallocated memory in place of allocating -/// new memory. The objects it allocates are stored in alist_node -/// containers, so they may be used in alists. +/// new memory. /// -template +template::Alignment> class Recycler { - typedef alist_node NodeTy; - - /// FreeListTraits - ilist traits for FreeList. - /// - struct FreeListTraits : ilist_traits > { - NodeTy &getSentinel() { return this->Sentinel; } - }; - /// FreeList - Doubly-linked list of nodes that have deleted contents and /// are not in active use. /// - iplist FreeList; - - /// CreateNewNode - Allocate a new node object and initialize its - /// prev and next pointers to 0. - /// - template - NodeTy *CreateNewNode(AllocatorType &Allocator) { - // Note that we're calling new on the *node*, to initialize its - // Next/Prev pointers, not new on the end-user object. - return new (Allocator.Allocate()) NodeTy(); - } + iplist FreeList; public: - ~Recycler() { assert(FreeList.empty()); } + ~Recycler() { + // If this fails, either the callee has lost track of some allocation, + // or the callee isn't tracking allocations and should just call + // clear() before deleting the Recycler. + assert(FreeList.empty() && "Non-empty recycler deleted!"); + } + /// clear - Release all the tracked allocations to the allocator. The + /// recycler must be free of any tracked allocations before being + /// deleted; calling clear is one way to ensure this. template void clear(AllocatorType &Allocator) { - while (!FreeList.empty()) - Allocator.Deallocate(FreeList.remove(FreeList.begin())); + while (!FreeList.empty()) { + T *t = reinterpret_cast(FreeList.remove(FreeList.begin())); + Allocator.Deallocate(t); + } } template SubClass *Allocate(AllocatorType &Allocator) { - NodeTy *N = !FreeList.empty() ? - FreeList.remove(FreeList.front()) : - CreateNewNode(Allocator); - assert(N->getPrev() == 0); - assert(N->getNext() == 0); - return N->getElement((SubClass*)0); + assert(sizeof(SubClass) <= Size && + "Recycler allocation size is less than object size!"); + assert(AlignOf::Alignment <= Align && + "Recycler allocation alignment is less than object alignment!"); + return !FreeList.empty() ? + reinterpret_cast(FreeList.remove(FreeList.begin())) : + static_cast(Allocator.Allocate(Size, Align)); } template @@ -80,14 +99,11 @@ public: template void Deallocate(AllocatorType & /*Allocator*/, SubClass* Element) { - NodeTy *N = NodeTy::getNode(Element); - assert(N->getPrev() == 0); - assert(N->getNext() == 0); - FreeList.push_front(N); + FreeList.push_front(reinterpret_cast(Element)); } void PrintStats() { - PrintRecyclerStats(sizeof(LargestT), FreeList.size()); + PrintRecyclerStats(Size, Align, FreeList.size()); } }; diff --git a/include/llvm/Support/RecyclingAllocator.h b/include/llvm/Support/RecyclingAllocator.h index 071a61d9dc..8e957f1b26 100644 --- a/include/llvm/Support/RecyclingAllocator.h +++ b/include/llvm/Support/RecyclingAllocator.h @@ -22,12 +22,13 @@ namespace llvm { /// RecyclingAllocator - This class wraps an Allocator, adding the /// functionality of recycling deleted objects. /// -template +template::Alignment> class RecyclingAllocator { private: /// Base - Implementation details. /// - Recycler Base; + Recycler Base; /// Allocator - The wrapped allocator. /// diff --git a/include/llvm/SymbolTableListTraits.h b/include/llvm/SymbolTableListTraits.h index 7d747d4c5e..911d1ce19d 100644 --- a/include/llvm/SymbolTableListTraits.h +++ b/include/llvm/SymbolTableListTraits.h @@ -25,6 +25,8 @@ #ifndef LLVM_SYMBOLTABLELISTTRAITS_H #define LLVM_SYMBOLTABLELISTTRAITS_H +#include "llvm/ADT/ilist.h" + namespace llvm { template class ilist_iterator; @@ -37,7 +39,7 @@ template struct ilist_traits; // inherit from ilist_traits // template -class SymbolTableListTraits { +class SymbolTableListTraits : public ilist_default_traits { typedef ilist_traits TraitsClass; public: SymbolTableListTraits() {} @@ -48,26 +50,14 @@ public: return reinterpret_cast(reinterpret_cast(this)- TraitsClass::getListOffset()); } - static ValueSubClass *getPrev(ValueSubClass *V) { return V->getPrev(); } - static ValueSubClass *getNext(ValueSubClass *V) { return V->getNext(); } - static const ValueSubClass *getPrev(const ValueSubClass *V) { - return V->getPrev(); - } - static const ValueSubClass *getNext(const ValueSubClass *V) { - return V->getNext(); - } void deleteNode(ValueSubClass *V) { delete V; } - static void setPrev(ValueSubClass *V, ValueSubClass *P) { V->setPrev(P); } - static void setNext(ValueSubClass *V, ValueSubClass *N) { V->setNext(N); } - void addNodeToList(ValueSubClass *V); void removeNodeFromList(ValueSubClass *V); - void transferNodesFromList(iplist > &L2, + void transferNodesFromList(ilist_traits &L2, ilist_iterator first, ilist_iterator last); //private: diff --git a/lib/Archive/Archive.cpp b/lib/Archive/Archive.cpp index a0e5eedc9c..776f4dd367 100644 --- a/lib/Archive/Archive.cpp +++ b/lib/Archive/Archive.cpp @@ -43,7 +43,7 @@ ArchiveMember::getMemberSize() const { // This default constructor is only use by the ilist when it creates its // sentry node. We give it specific static values to make it stand out a bit. ArchiveMember::ArchiveMember() - : next(0), prev(0), parent(0), path("--invalid--"), flags(0), data(0) + : parent(0), path("--invalid--"), flags(0), data(0) { info.user = sys::Process::GetCurrentUserId(); info.group = sys::Process::GetCurrentGroupId(); @@ -58,7 +58,7 @@ ArchiveMember::ArchiveMember() // This is required because correctly setting the data may depend on other // things in the Archive. ArchiveMember::ArchiveMember(Archive* PAR) - : next(0), prev(0), parent(PAR), path(), flags(0), data(0) + : parent(PAR), path(), flags(0), data(0) { } diff --git a/lib/Archive/ArchiveReader.cpp b/lib/Archive/ArchiveReader.cpp index 1ded9e5c4c..8d607f0df7 100644 --- a/lib/Archive/ArchiveReader.cpp +++ b/lib/Archive/ArchiveReader.cpp @@ -218,8 +218,6 @@ Archive::parseMemberHeader(const char*& At, const char* End, std::string* error) ArchiveMember* member = new ArchiveMember(this); // Fill in fields of the ArchiveMember - member->next = 0; - member->prev = 0; member->parent = this; member->path.set(pathname); member->info.fileSize = MemberSize; diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index baaed71d23..fde27b07a8 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -828,7 +828,7 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, // If the instruction accesses memory and the memory could be non-constant, // assume the instruction is not rematerializable. - for (alist::const_iterator I = MI->memoperands_begin(), + for (std::list::const_iterator I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I) { const MachineMemOperand &MMO = *I; if (MMO.isVolatile() || MMO.isStore()) diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 9a9f5b9271..5cfeeb63a7 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -24,7 +24,7 @@ using namespace llvm; MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb) : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false) { - Insts.getTraits().Parent = this; + Insts.Parent = this; } MachineBasicBlock::~MachineBasicBlock() { @@ -43,7 +43,7 @@ std::ostream& llvm::operator<<(std::ostream &OS, const MachineBasicBlock &MBB) { /// 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 alist_traits::addNodeToList(MachineBasicBlock* N) { +void ilist_traits::addNodeToList(MachineBasicBlock* N) { MachineFunction &MF = *N->getParent(); N->Number = MF.addToMBBNumbering(N); @@ -55,7 +55,7 @@ void alist_traits::addNodeToList(MachineBasicBlock* N) { LeakDetector::removeGarbageObject(N); } -void alist_traits::removeNodeFromList(MachineBasicBlock* N) { +void ilist_traits::removeNodeFromList(MachineBasicBlock* N) { N->getParent()->removeFromMBBNumbering(N->Number); N->Number = -1; LeakDetector::addGarbageObject(N); @@ -65,7 +65,7 @@ void alist_traits::removeNodeFromList(MachineBasicBlock* N) { /// addNodeToList (MI) - When we add an instruction to a basic block /// list, we update its parent pointer and add its operands from reg use/def /// lists if appropriate. -void alist_traits::addNodeToList(MachineInstr* N) { +void ilist_traits::addNodeToList(MachineInstr* N) { assert(N->getParent() == 0 && "machine instruction already in a basic block"); N->setParent(Parent); @@ -80,7 +80,7 @@ void alist_traits::addNodeToList(MachineInstr* N) { /// removeNodeFromList (MI) - When we remove an instruction from a basic block /// list, we update its parent pointer and remove its operands from reg use/def /// lists if appropriate. -void alist_traits::removeNodeFromList(MachineInstr* N) { +void ilist_traits::removeNodeFromList(MachineInstr* N) { assert(N->getParent() != 0 && "machine instruction not in a basic block"); // Remove from the use/def lists. @@ -94,35 +94,23 @@ void alist_traits::removeNodeFromList(MachineInstr* N) { /// transferNodesFromList (MI) - 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 alist_traits::transferNodesFromList( - alist_traits& fromList, +void ilist_traits::transferNodesFromList( + ilist_traits& fromList, MachineBasicBlock::iterator first, MachineBasicBlock::iterator last) { + assert(Parent->getParent() == fromList.Parent->getParent() && + "MachineInstr parent mismatch!"); + // Splice within the same MBB -> no change. if (Parent == fromList.Parent) return; // If splicing between two blocks within the same function, just update the // parent pointers. - if (Parent->getParent() == fromList.Parent->getParent()) { - for (; first != last; ++first) - first->setParent(Parent); - return; - } - - // Otherwise, we have to update the parent and the use/def lists. The common - // case when this occurs is if we're splicing from a block in a MF to a block - // that is not in an MF. - bool HasOldMF = fromList.Parent->getParent() != 0; - MachineFunction *NewMF = Parent->getParent(); - - for (; first != last; ++first) { - if (HasOldMF) first->RemoveRegOperandsFromUseLists(); + for (; first != last; ++first) first->setParent(Parent); - if (NewMF) first->AddRegOperandsToUseLists(NewMF->getRegInfo()); - } } -void alist_traits::deleteNode(MachineInstr* MI) { +void ilist_traits::deleteNode(MachineInstr* MI) { assert(!MI->getParent() && "MI is still in a block!"); Parent->getParent()->DeleteMachineInstr(MI); } diff --git a/lib/CodeGen/MachineFunction.cpp b/lib/CodeGen/MachineFunction.cpp index 2cac96a4a8..b243297253 100644 --- a/lib/CodeGen/MachineFunction.cpp +++ b/lib/CodeGen/MachineFunction.cpp @@ -102,7 +102,7 @@ FunctionPass *llvm::createMachineCodeDeleter() { // MachineFunction implementation //===---------------------------------------------------------------------===// -void alist_traits::deleteNode(MachineBasicBlock *MBB) { +void ilist_traits::deleteNode(MachineBasicBlock *MBB) { MBB->getParent()->DeleteMachineBasicBlock(MBB); } @@ -131,7 +131,6 @@ MachineFunction::~MachineFunction() { BasicBlocks.clear(); InstructionRecycler.clear(Allocator); BasicBlockRecycler.clear(Allocator); - MemOperandRecycler.clear(Allocator); RegInfo->~MachineRegisterInfo(); Allocator.Deallocate(RegInfo); if (MFInfo) { MFInfo->~MachineFunctionInfo(); Allocator.Deallocate(MFInfo); @@ -234,23 +233,6 @@ MachineFunction::DeleteMachineBasicBlock(MachineBasicBlock *MBB) { BasicBlockRecycler.Deallocate(Allocator, MBB); } -/// CreateMachineMemOperand - Allocate a new MachineMemOperand. Use this -/// instead of `new MachineMemOperand'. -/// -MachineMemOperand * -MachineFunction::CreateMachineMemOperand(const MachineMemOperand &MMO) { - return new (MemOperandRecycler.Allocate(Allocator)) - MachineMemOperand(MMO); -} - -/// DeleteMachineMemOperand - Delete the given MachineMemOperand. -/// -void -MachineFunction::DeleteMachineMemOperand(MachineMemOperand *MO) { - MO->~MachineMemOperand(); - MemOperandRecycler.Deallocate(Allocator, MO); -} - void MachineFunction::dump() const { print(*cerr.stream()); } diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp index d577582637..c952293976 100644 --- a/lib/CodeGen/MachineInstr.cpp +++ b/lib/CodeGen/MachineInstr.cpp @@ -322,7 +322,7 @@ MachineInstr::MachineInstr(MachineFunction &MF, const MachineInstr &MI) NumImplicitOps = MI.NumImplicitOps; // Add memory operands. - for (alist::const_iterator i = MI.memoperands_begin(), + for (std::list::const_iterator i = MI.memoperands_begin(), j = MI.memoperands_end(); i != j; ++i) addMemOperand(MF, *i); @@ -506,13 +506,12 @@ void MachineInstr::RemoveOperand(unsigned OpNo) { /// referencing arbitrary storage. void MachineInstr::addMemOperand(MachineFunction &MF, const MachineMemOperand &MO) { - MemOperands.push_back(MF.CreateMachineMemOperand(MO)); + MemOperands.push_back(MO); } /// clearMemOperands - Erase all of this MachineInstr's MachineMemOperands. void MachineInstr::clearMemOperands(MachineFunction &MF) { - while (!MemOperands.empty()) - MF.DeleteMachineMemOperand(MemOperands.remove(MemOperands.begin())); + MemOperands.clear(); } @@ -731,7 +730,7 @@ void MachineInstr::print(std::ostream &OS, const TargetMachine *TM) const { if (!memoperands_empty()) { OS << ", Mem:"; - for (alist::const_iterator i = memoperands_begin(), + for (std::list::const_iterator i = memoperands_begin(), e = memoperands_end(); i != e; ++i) { const MachineMemOperand &MRO = *i; const Value *V = MRO.getValue(); diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index c99d504f27..f8c11456d9 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -468,11 +468,6 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) { // SelectionDAG Class //===----------------------------------------------------------------------===// -inline alist_traits::AllocatorType & -SelectionDAG::getAllocator() { - return AllNodes.getTraits().Allocator; -} - /// RemoveDeadNodes - This method deletes all unreachable nodes in the /// SelectionDAG. void SelectionDAG::RemoveDeadNodes() { @@ -527,7 +522,7 @@ void SelectionDAG::RemoveDeadNodes(SmallVectorImpl &DeadNodes, N->NumOperands = 0; // Finally, remove N itself. - AllNodes.erase(N); + AllNodes.remove(N); } } @@ -558,7 +553,7 @@ void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { N->OperandList = 0; N->NumOperands = 0; - AllNodes.erase(N); + AllNodes.remove(N); } /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that @@ -772,14 +767,13 @@ unsigned SelectionDAG::getMVTAlignment(MVT VT) const { SelectionDAG::~SelectionDAG() { while (!AllNodes.empty()) { - SDNode *N = AllNodes.begin(); + SDNode *N = AllNodes.remove(AllNodes.begin()); N->SetNextInBucket(0); if (N->OperandsNeedDelete) { delete [] N->OperandList; } N->OperandList = 0; N->NumOperands = 0; - AllNodes.pop_front(); } } @@ -813,7 +807,7 @@ SDValue SelectionDAG::getConstant(const APInt &Val, MVT VT, bool isT) { if (!VT.isVector()) return SDValue(N, 0); if (!N) { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) ConstantSDNode(isT, Val, EltVT); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -852,7 +846,7 @@ SDValue SelectionDAG::getConstantFP(const APFloat& V, MVT VT, bool isTarget) { if (!VT.isVector()) return SDValue(N, 0); if (!N) { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) ConstantFPSDNode(isTarget, V, EltVT); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -900,7 +894,7 @@ SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) GlobalAddressSDNode(isTargetGA, GV, VT, Offset); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -915,7 +909,7 @@ SDValue SelectionDAG::getFrameIndex(int FI, MVT VT, bool isTarget) { void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) FrameIndexSDNode(FI, VT, isTarget); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -930,7 +924,7 @@ SDValue SelectionDAG::getJumpTable(int JTI, MVT VT, bool isTarget){ void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) JumpTableSDNode(JTI, VT, isTarget); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -949,7 +943,7 @@ SDValue SelectionDAG::getConstantPool(Constant *C, MVT VT, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -969,7 +963,7 @@ SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, MVT VT, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -984,7 +978,7 @@ SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) BasicBlockSDNode(MBB); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -998,7 +992,7 @@ SDValue SelectionDAG::getArgFlags(ISD::ArgFlagsTy Flags) { void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) ARG_FLAGSSDNode(Flags); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -1013,7 +1007,7 @@ SDValue SelectionDAG::getValueType(MVT VT) { ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT()]; if (N) return SDValue(N, 0); - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) VTSDNode(VT); AllNodes.push_back(N); return SDValue(N, 0); @@ -1022,7 +1016,7 @@ SDValue SelectionDAG::getValueType(MVT VT) { SDValue SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) { SDNode *&N = ExternalSymbols[Sym]; if (N) return SDValue(N, 0); - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) ExternalSymbolSDNode(false, Sym, VT); AllNodes.push_back(N); return SDValue(N, 0); @@ -1031,7 +1025,7 @@ SDValue SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) { SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, MVT VT) { SDNode *&N = TargetExternalSymbols[Sym]; if (N) return SDValue(N, 0); - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) ExternalSymbolSDNode(true, Sym, VT); AllNodes.push_back(N); return SDValue(N, 0); @@ -1042,7 +1036,7 @@ SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) { CondCodeNodes.resize(Cond+1); if (CondCodeNodes[Cond] == 0) { - CondCodeSDNode *N = getAllocator().Allocate(); + CondCodeSDNode *N = NodeAllocator.Allocate(); new (N) CondCodeSDNode(Cond); CondCodeNodes[Cond] = N; AllNodes.push_back(N); @@ -1057,7 +1051,7 @@ SDValue SelectionDAG::getRegister(unsigned RegNo, MVT VT) { void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) RegisterSDNode(RegNo, VT); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -1065,9 +1059,9 @@ SDValue SelectionDAG::getRegister(unsigned RegNo, MVT VT) { } SDValue SelectionDAG::getDbgStopPoint(SDValue Root, - unsigned Line, unsigned Col, - const CompileUnitDesc *CU) { - SDNode *N = getAllocator().Allocate(); + unsigned Line, unsigned Col, + const CompileUnitDesc *CU) { + SDNode *N = NodeAllocator.Allocate(); new (N) DbgStopPointSDNode(Root, Line, Col, CU); AllNodes.push_back(N); return SDValue(N, 0); @@ -1083,7 +1077,7 @@ SDValue SelectionDAG::getLabel(unsigned Opcode, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) LabelSDNode(Opcode, Root, LabelID); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -1102,7 +1096,7 @@ SDValue SelectionDAG::getSrcValue(const Value *V) { if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) SrcValueSDNode(V); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -1126,7 +1120,7 @@ SDValue SelectionDAG::getMemOperand(const MachineMemOperand &MO) { if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) MemOperandSDNode(MO); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -1979,7 +1973,7 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT) { void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) SDNode(Opcode, SDNode::getSDVTList(VT)); CSEMap.InsertNode(N, IP); @@ -2176,11 +2170,11 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, SDValue Operand) { void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) UnarySDNode(Opcode, VTs, Operand); CSEMap.InsertNode(N, IP); } else { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) UnarySDNode(Opcode, VTs, Operand); } @@ -2530,11 +2524,11 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) BinarySDNode(Opcode, VTs, N1, N2); CSEMap.InsertNode(N, IP); } else { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) BinarySDNode(Opcode, VTs, N1, N2); } @@ -2599,11 +2593,11 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) TernarySDNode(Opcode, VTs, N1, N2, N3); CSEMap.InsertNode(N, IP); } else { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) TernarySDNode(Opcode, VTs, N1, N2, N3); } AllNodes.push_back(N); @@ -3121,7 +3115,7 @@ SDValue SelectionDAG::getAtomic(unsigned Opcode, SDValue Chain, void* IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode* N = getAllocator().Allocate(); + SDNode* N = NodeAllocator.Allocate(); new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, PtrVal, Alignment); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -3152,7 +3146,7 @@ SDValue SelectionDAG::getAtomic(unsigned Opcode, SDValue Chain, void* IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode* N = getAllocator().Allocate(); + SDNode* N = NodeAllocator.Allocate(); new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, PtrVal, Alignment); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -3216,7 +3210,7 @@ SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset, Alignment, isVolatile); CSEMap.InsertNode(N, IP); @@ -3276,7 +3270,7 @@ SDValue SelectionDAG::getStore(SDValue Chain, SDValue Val, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, false, VT, SV, SVOffset, Alignment, isVolatile); CSEMap.InsertNode(N, IP); @@ -3313,7 +3307,7 @@ SDValue SelectionDAG::getTruncStore(SDValue Chain, SDValue Val, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, true, SVT, SV, SVOffset, Alignment, isVolatile); CSEMap.InsertNode(N, IP); @@ -3339,7 +3333,7 @@ SelectionDAG::getIndexedStore(SDValue OrigStore, SDValue Base, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - SDNode *N = getAllocator().Allocate(); + SDNode *N = NodeAllocator.Allocate(); new (N) StoreSDNode(Ops, VTs, AM, ST->isTruncatingStore(), ST->getMemoryVT(), ST->getSrcValue(), ST->getSrcValueOffset(), @@ -3411,11 +3405,11 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) SDNode(Opcode, VTs, Ops, NumOps); CSEMap.InsertNode(N, IP); } else { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) SDNode(Opcode, VTs, Ops, NumOps); } AllNodes.push_back(N); @@ -3477,31 +3471,31 @@ SDValue SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDValue(E, 0); if (NumOps == 1) { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) UnarySDNode(Opcode, VTList, Ops[0]); } else if (NumOps == 2) { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]); } else if (NumOps == 3) { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]); } else { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) SDNode(Opcode, VTList, Ops, NumOps); } CSEMap.InsertNode(N, IP); } else { if (NumOps == 1) { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) UnarySDNode(Opcode, VTList, Ops[0]); } else if (NumOps == 2) { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]); } else if (NumOps == 3) { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]); } else { - N = getAllocator().Allocate(); + N = NodeAllocator.Allocate(); new (N) SDNode(Opcode, VTList, Ops, NumOps); } } diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 7d34ca2744..c0652da35d 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -5425,24 +5425,23 @@ void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) { void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF, FunctionLoweringInfo &FuncInfo) { - // Define AllNodes here so that memory allocation is reused for + // Define NodeAllocator here so that memory allocation is reused for // each basic block. - alist AllNodes; + NodeAllocatorType NodeAllocator; - for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { - SelectBasicBlock(I, MF, FuncInfo, AllNodes); - AllNodes.clear(); - } + for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) + SelectBasicBlock(I, MF, FuncInfo, NodeAllocator); } -void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, - FunctionLoweringInfo &FuncInfo, - alist &AllNodes) { +void +SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, + FunctionLoweringInfo &FuncInfo, + NodeAllocatorType &NodeAllocator) { std::vector > PHINodesToUpdate; { SelectionDAG DAG(TLI, MF, FuncInfo, getAnalysisToUpdate(), - AllNodes); + NodeAllocator); CurDAG = &DAG; // First step, lower LLVM code to some DAG. This DAG may use operations and @@ -5478,7 +5477,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, if (!BitTestCases[i].Emitted) { SelectionDAG HSDAG(TLI, MF, FuncInfo, getAnalysisToUpdate(), - AllNodes); + NodeAllocator); CurDAG = &HSDAG; SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); // Set the current basic block to the mbb we wish to insert the code into @@ -5493,7 +5492,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) { SelectionDAG BSDAG(TLI, MF, FuncInfo, getAnalysisToUpdate(), - AllNodes); + NodeAllocator); CurDAG = &BSDAG; SelectionDAGLowering BSDL(BSDAG, TLI, *AA, FuncInfo, GCI); // Set the current basic block to the mbb we wish to insert the code into @@ -5552,7 +5551,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, if (!JTCases[i].first.Emitted) { SelectionDAG HSDAG(TLI, MF, FuncInfo, getAnalysisToUpdate(), - AllNodes); + NodeAllocator); CurDAG = &HSDAG; SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); // Set the current basic block to the mbb we wish to insert the code into @@ -5566,7 +5565,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, SelectionDAG JSDAG(TLI, MF, FuncInfo, getAnalysisToUpdate(), - AllNodes); + NodeAllocator); CurDAG = &JSDAG; SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo, GCI); // Set the current basic block to the mbb we wish to insert the code into @@ -5616,7 +5615,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) { SelectionDAG SDAG(TLI, MF, FuncInfo, getAnalysisToUpdate(), - AllNodes); + NodeAllocator); CurDAG = &SDAG; SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo, GCI); diff --git a/lib/Support/Allocator.cpp b/lib/Support/Allocator.cpp index 584ca125b7..db0d8f31e5 100644 --- a/lib/Support/Allocator.cpp +++ b/lib/Support/Allocator.cpp @@ -132,8 +132,10 @@ void BumpPtrAllocator::PrintStats() const { cerr << "Bytes allocated: " << BytesUsed << "\n"; } -void llvm::PrintRecyclerStats(size_t LargestTypeSize, +void llvm::PrintRecyclerStats(size_t Size, + size_t Align, size_t FreeListSize) { - cerr << "Recycler element size: " << LargestTypeSize << '\n'; + cerr << "Recycler element size: " << Size << '\n'; + cerr << "Recycler element alignment: " << Align << '\n'; cerr << "Number of elements free for recycling: " << FreeListSize << '\n'; } diff --git a/lib/VMCore/BasicBlock.cpp b/lib/VMCore/BasicBlock.cpp index 64711fea0c..514aa1de23 100644 --- a/lib/VMCore/BasicBlock.cpp +++ b/lib/VMCore/BasicBlock.cpp @@ -15,6 +15,7 @@ #include "llvm/Constants.h" #include "llvm/Instructions.h" #include "llvm/Type.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Support/CFG.h" #include "llvm/Support/LeakDetector.h" #include "llvm/Support/Compiler.h" @@ -260,7 +261,9 @@ BasicBlock *BasicBlock::splitBasicBlock(iterator I, const std::string &BBName) { assert(I != InstList.end() && "Trying to get me to create degenerate basic block!"); - BasicBlock *New = BasicBlock::Create(BBName, getParent(), getNext()); + BasicBlock *InsertBefore = next(Function::iterator(this)) + .getNodePtrUnchecked(); + BasicBlock *New = BasicBlock::Create(BBName, getParent(), InsertBefore); // Move all of the specified instructions from the original basic block into // the new basic block. diff --git a/lib/VMCore/SymbolTableListTraitsImpl.h b/lib/VMCore/SymbolTableListTraitsImpl.h index 2a3b3d835d..72687bb5e0 100644 --- a/lib/VMCore/SymbolTableListTraitsImpl.h +++ b/lib/VMCore/SymbolTableListTraitsImpl.h @@ -84,7 +84,7 @@ void SymbolTableListTraits template void SymbolTableListTraits -::transferNodesFromList(iplist > &L2, +::transferNodesFromList(ilist_traits &L2, ilist_iterator first, ilist_iterator last) { // We only have to do work here if transferring instructions between BBs -- cgit v1.2.3