X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=include%2Fllvm%2FADT%2FFoldingSet.h;h=c9205396591b89bd3cc8d3141c20218cc9356c62;hb=2b762697564ca1e12e0e974e93ceeb4c3420505c;hp=d2e0b8f91b2cc4e65a087780af17647a66dbae36;hpb=ed5edea96d72440679311d7d31d39804967f3220;p=oota-llvm.git diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index d2e0b8f91b2..c9205396591 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -16,15 +16,13 @@ #ifndef LLVM_ADT_FOLDINGSET_H #define LLVM_ADT_FOLDINGSET_H -#include "llvm/Support/DataTypes.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" +#include "llvm/ADT/iterator.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/DataTypes.h" namespace llvm { - class APFloat; - class APInt; - class BumpPtrAllocator; - /// This folding set used for two purposes: /// 1. Given information about a node we want to create, look up the unique /// instance of the node in the set. If the node already exists, return @@ -109,6 +107,8 @@ class FoldingSetNodeID; /// back to the bucket to facilitate node removal. /// class FoldingSetImpl { + virtual void anchor(); // Out of line virtual method. + protected: /// Buckets - Array of bucket chains. /// @@ -122,10 +122,12 @@ protected: /// is greater than twice the number of buckets. unsigned NumNodes; -public: explicit FoldingSetImpl(unsigned Log2InitSize = 6); - virtual ~FoldingSetImpl(); + FoldingSetImpl(FoldingSetImpl &&Arg); + FoldingSetImpl &operator=(FoldingSetImpl &&RHS); + ~FoldingSetImpl(); +public: //===--------------------------------------------------------------------===// /// Node - This class is used to maintain the singly linked bucket list in /// a folding set. @@ -136,8 +138,7 @@ public: void *NextInFoldingSetBucket; public: - - Node() : NextInFoldingSetBucket(0) {} + Node() : NextInFoldingSetBucket(nullptr) {} // Accessors void *getNextInBucket() const { return NextInFoldingSetBucket; } @@ -181,24 +182,21 @@ public: bool empty() const { return NumNodes == 0; } private: - /// GrowHashTable - Double the size of the hash table and rehash everything. /// void GrowHashTable(); protected: - /// GetNodeProfile - Instantiations of the FoldingSet template implement /// this function to gather data bits for the given node. virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0; /// NodeEquals - Instantiations of the FoldingSet template implement /// this function to compare the given node with the given ID. - virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, + virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID) const=0; - /// NodeEquals - Instantiations of the FoldingSet template implement + /// ComputeNodeHash - Instantiations of the FoldingSet template implement /// this function to compute a hash value for the given node. - virtual unsigned ComputeNodeHash(Node *N, - FoldingSetNodeID &TempID) const = 0; + virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0; }; //===----------------------------------------------------------------------===// @@ -220,7 +218,7 @@ template struct DefaultFoldingSetTrait { // to compute a temporary ID if necessary. The default implementation // just calls Profile and does a regular comparison. Implementations // can override this to provide more efficient implementations. - static inline bool Equals(T &X, const FoldingSetNodeID &ID, + static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID); // ComputeHash - Compute a hash value for X, using TempID to @@ -249,7 +247,7 @@ struct DefaultContextualFoldingSetTrait { static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) { X.Profile(ID, Context); } - static inline bool Equals(T &X, const FoldingSetNodeID &ID, + static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID, Ctx Context); static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, Ctx Context); @@ -269,8 +267,9 @@ template struct ContextualFoldingSetTrait class FoldingSetNodeIDRef { const unsigned *Data; size_t Size; + public: - FoldingSetNodeIDRef() : Data(0), Size(0) {} + FoldingSetNodeIDRef() : Data(nullptr), Size(0) {} FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {} /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, @@ -279,6 +278,12 @@ public: bool operator==(FoldingSetNodeIDRef) const; + bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); } + + /// Used to compare the "ordering" of two nodes as defined by the + /// profiled bits and their ordering defined by memcmp(). + bool operator<(FoldingSetNodeIDRef) const; + const unsigned *getData() const { return Data; } size_t getSize() const { return Size; } }; @@ -328,6 +333,14 @@ public: bool operator==(const FoldingSetNodeID &RHS) const; bool operator==(const FoldingSetNodeIDRef RHS) const; + bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); } + bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);} + + /// Used to compare the "ordering" of two nodes as defined by the + /// profiled bits and their ordering defined by memcmp(). + bool operator<(const FoldingSetNodeID &RHS) const; + bool operator<(const FoldingSetNodeIDRef RHS) const; + /// Intern - Copy this node's data to a memory region allocated from the /// given allocator and return a FoldingSetNodeIDRef describing the /// interned data. @@ -344,6 +357,7 @@ template class FoldingSetBucketIterator; template inline bool DefaultFoldingSetTrait::Equals(T &X, const FoldingSetNodeID &ID, + unsigned /*IDHash*/, FoldingSetNodeID &TempID) { FoldingSetTrait::Profile(X, TempID); return TempID == ID; @@ -358,6 +372,7 @@ template inline bool DefaultContextualFoldingSetTrait::Equals(T &X, const FoldingSetNodeID &ID, + unsigned /*IDHash*/, FoldingSetNodeID &TempID, Ctx Context) { ContextualFoldingSetTrait::Profile(X, TempID, Context); @@ -377,33 +392,41 @@ DefaultContextualFoldingSetTrait::ComputeHash(T &X, /// implementation of the folding set to the node class T. T must be a /// subclass of FoldingSetNode and implement a Profile function. /// -template class FoldingSet : public FoldingSetImpl { +/// Note that this set type is movable and move-assignable. However, its +/// moved-from state is not a valid state for anything other than +/// move-assigning and destroying. This is primarily to enable movable APIs +/// that incorporate these objects. +template class FoldingSet final : public FoldingSetImpl { private: /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a /// way to convert nodes into a unique specifier. - virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const { + void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override { T *TN = static_cast(N); FoldingSetTrait::Profile(*TN, ID); } /// NodeEquals - Instantiations may optionally provide a way to compare a /// node with a specified ID. - virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, - FoldingSetNodeID &TempID) const { + bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, + FoldingSetNodeID &TempID) const override { T *TN = static_cast(N); - return FoldingSetTrait::Equals(*TN, ID, TempID); + return FoldingSetTrait::Equals(*TN, ID, IDHash, TempID); } - /// NodeEquals - Instantiations may optionally provide a way to compute a + /// ComputeNodeHash - Instantiations may optionally provide a way to compute a /// hash value directly from a node. - virtual unsigned ComputeNodeHash(Node *N, - FoldingSetNodeID &TempID) const { + unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override { T *TN = static_cast(N); return FoldingSetTrait::ComputeHash(*TN, TempID); } public: explicit FoldingSet(unsigned Log2InitSize = 6) - : FoldingSetImpl(Log2InitSize) - {} + : FoldingSetImpl(Log2InitSize) {} + + FoldingSet(FoldingSet &&Arg) : FoldingSetImpl(std::move(Arg)) {} + FoldingSet &operator=(FoldingSet &&RHS) { + (void)FoldingSetImpl::operator=(std::move(RHS)); + return *this; + } typedef FoldingSetIterator iterator; iterator begin() { return iterator(Buckets); } @@ -448,7 +471,7 @@ public: /// function with signature /// void Profile(llvm::FoldingSetNodeID &, Ctx); template -class ContextualFoldingSet : public FoldingSetImpl { +class ContextualFoldingSet final : public FoldingSetImpl { // Unfortunately, this can't derive from FoldingSet because the // construction vtable for FoldingSet requires // FoldingSet::GetNodeProfile to be instantiated, which in turn @@ -459,19 +482,19 @@ private: /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a /// way to convert nodes into a unique specifier. - virtual void GetNodeProfile(FoldingSetImpl::Node *N, - FoldingSetNodeID &ID) const { + void GetNodeProfile(FoldingSetImpl::Node *N, + FoldingSetNodeID &ID) const override { T *TN = static_cast(N); ContextualFoldingSetTrait::Profile(*TN, ID, Context); } - virtual bool NodeEquals(FoldingSetImpl::Node *N, - const FoldingSetNodeID &ID, - FoldingSetNodeID &TempID) const { + bool NodeEquals(FoldingSetImpl::Node *N, const FoldingSetNodeID &ID, + unsigned IDHash, FoldingSetNodeID &TempID) const override { T *TN = static_cast(N); - return ContextualFoldingSetTrait::Equals(*TN, ID, TempID, Context); + return ContextualFoldingSetTrait::Equals(*TN, ID, IDHash, TempID, + Context); } - virtual unsigned ComputeNodeHash(FoldingSetImpl::Node *N, - FoldingSetNodeID &TempID) const { + unsigned ComputeNodeHash(FoldingSetImpl::Node *N, + FoldingSetNodeID &TempID) const override { T *TN = static_cast(N); return ContextualFoldingSetTrait::ComputeHash(*TN, TempID, Context); } @@ -483,7 +506,6 @@ public: Ctx getContext() const { return Context; } - typedef FoldingSetIterator iterator; iterator begin() { return iterator(Buckets); } iterator end() { return iterator(Buckets+NumBuckets); } @@ -517,6 +539,70 @@ public: } }; +//===----------------------------------------------------------------------===// +/// FoldingSetVector - This template class combines a FoldingSet and a vector +/// to provide the interface of FoldingSet but with deterministic iteration +/// order based on the insertion order. T must be a subclass of FoldingSetNode +/// and implement a Profile function. +template > +class FoldingSetVector { + FoldingSet Set; + VectorT Vector; + +public: + explicit FoldingSetVector(unsigned Log2InitSize = 6) + : Set(Log2InitSize) { + } + + typedef pointee_iterator iterator; + iterator begin() { return Vector.begin(); } + iterator end() { return Vector.end(); } + + typedef pointee_iterator const_iterator; + const_iterator begin() const { return Vector.begin(); } + const_iterator end() const { return Vector.end(); } + + /// clear - Remove all nodes from the folding set. + void clear() { Set.clear(); Vector.clear(); } + + /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, + /// return it. If not, return the insertion token that will make insertion + /// faster. + T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { + return Set.FindNodeOrInsertPos(ID, InsertPos); + } + + /// GetOrInsertNode - If there is an existing simple Node exactly + /// equal to the specified node, return it. Otherwise, insert 'N' and + /// return it instead. + T *GetOrInsertNode(T *N) { + T *Result = Set.GetOrInsertNode(N); + if (Result == N) Vector.push_back(N); + return Result; + } + + /// InsertNode - Insert the specified node into the folding set, knowing that + /// it is not already in the folding set. InsertPos must be obtained from + /// FindNodeOrInsertPos. + void InsertNode(T *N, void *InsertPos) { + Set.InsertNode(N, InsertPos); + Vector.push_back(N); + } + + /// InsertNode - Insert the specified node into the folding set, knowing that + /// it is not already in the folding set. + void InsertNode(T *N) { + Set.InsertNode(N); + Vector.push_back(N); + } + + /// size - Returns the number of nodes in the folding set. + unsigned size() const { return Set.size(); } + + /// empty - Returns true if there are no nodes in the folding set. + bool empty() const { return Set.empty(); } +}; + //===----------------------------------------------------------------------===// /// FoldingSetIteratorImpl - This is the common iterator support shared by all /// folding sets, which knows how to walk the folding set hash table. @@ -535,9 +621,7 @@ public: } }; - -template -class FoldingSetIterator : public FoldingSetIteratorImpl { +template class FoldingSetIterator : public FoldingSetIteratorImpl { public: explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {} @@ -587,8 +671,7 @@ public: } }; - -template +template class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl { public: explicit FoldingSetBucketIterator(void **Bucket) : @@ -615,32 +698,11 @@ public: template class FoldingSetNodeWrapper : public FoldingSetNode { T data; -public: - explicit FoldingSetNodeWrapper(const T &x) : data(x) {} - virtual ~FoldingSetNodeWrapper() {} - - template - explicit FoldingSetNodeWrapper(const A1 &a1) - : data(a1) {} - - template - explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2) - : data(a1,a2) {} - - template - explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3) - : data(a1,a2,a3) {} - - template - explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, - const A4 &a4) - : data(a1,a2,a3,a4) {} - - template - explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, - const A4 &a4, const A5 &a5) - : data(a1,a2,a3,a4,a5) {} +public: + template + explicit FoldingSetNodeWrapper(Ts &&... Args) + : data(std::forward(Args)...) {} void Profile(FoldingSetNodeID &ID) { FoldingSetTrait::Profile(data, ID); } @@ -659,12 +721,12 @@ public: /// information that would otherwise only be required for recomputing an ID. class FastFoldingSetNode : public FoldingSetNode { FoldingSetNodeID FastID; + protected: explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {} + public: - void Profile(FoldingSetNodeID &ID) const { - ID.AddNodeID(FastID); - } + void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(FastID); } }; //===----------------------------------------------------------------------===// @@ -675,6 +737,14 @@ template struct FoldingSetTrait { ID.AddPointer(X); } }; +template +struct FoldingSetTrait> { + static inline void Profile(const std::pair &P, + llvm::FoldingSetNodeID &ID) { + ID.Add(P.first); + ID.Add(P.second); + } +}; } // End of namespace llvm. #endif