X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FSupport%2FFoldingSet.cpp;h=0f61067d60df220ac992afa9be237210ab6304ba;hp=6c1b13f3b299b389f04a65bfb19d37ba34460d34;hb=c25e7581b9b8088910da31702d4ca21c4734c6d7;hpb=0e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7f diff --git a/lib/Support/FoldingSet.cpp b/lib/Support/FoldingSet.cpp index 6c1b13f3b29..0f61067d60d 100644 --- a/lib/Support/FoldingSet.cpp +++ b/lib/Support/FoldingSet.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by James M. Laskey and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -15,17 +15,18 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/FoldingSet.h" - -#include "llvm/ADT/MathExtras.h" - +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/MathExtras.h" +#include +#include using namespace llvm; //===----------------------------------------------------------------------===// -// FoldingSetImpl::NodeID Implementation +// FoldingSetNodeID Implementation /// Add* - Add various data types to Bit data. /// -void FoldingSetImpl::NodeID::AddPointer(const void *Ptr) { +void FoldingSetNodeID::AddPointer(const void *Ptr) { // Note: this adds pointers to the hash using sizes and endianness that // depend on the host. It doesn't matter however, because hashing on // pointer values in inherently unstable. Nothing should depend on the @@ -35,42 +36,83 @@ void FoldingSetImpl::NodeID::AddPointer(const void *Ptr) { if (sizeof(intptr_t) > sizeof(unsigned)) Bits.push_back(unsigned(uint64_t(PtrI) >> 32)); } -void FoldingSetImpl::NodeID::AddInteger(signed I) { +void FoldingSetNodeID::AddInteger(signed I) { Bits.push_back(I); } -void FoldingSetImpl::NodeID::AddInteger(unsigned I) { +void FoldingSetNodeID::AddInteger(unsigned I) { Bits.push_back(I); } -void FoldingSetImpl::NodeID::AddInteger(uint64_t I) { - Bits.push_back(unsigned(I)); - Bits.push_back(unsigned(I >> 32)); +void FoldingSetNodeID::AddInteger(long I) { + AddInteger((unsigned long)I); +} +void FoldingSetNodeID::AddInteger(unsigned long I) { + if (sizeof(long) == sizeof(int)) + AddInteger(unsigned(I)); + else if (sizeof(long) == sizeof(long long)) { + AddInteger((unsigned long long)I); + } else { + LLVM_UNREACHABLE("unexpected sizeof(long)"); + } } -void FoldingSetImpl::NodeID::AddFloat(float F) { - Bits.push_back(FloatToBits(F)); +void FoldingSetNodeID::AddInteger(long long I) { + AddInteger((unsigned long long)I); } -void FoldingSetImpl::NodeID::AddDouble(double D) { - Bits.push_back(DoubleToBits(D)); +void FoldingSetNodeID::AddInteger(unsigned long long I) { + AddInteger(unsigned(I)); + if ((uint64_t)(int)I != I) + Bits.push_back(unsigned(I >> 32)); } -void FoldingSetImpl::NodeID::AddString(const std::string &String) { - // Note: An assumption is made here that strings are composed of one byte - // chars. - unsigned Size = String.size(); - unsigned Units = Size / sizeof(unsigned); - const unsigned *Base = (const unsigned *)String.data(); - Bits.insert(Bits.end(), Base, Base + Units); - if (Size & 3) { - unsigned V = 0; - for (unsigned i = Units * sizeof(unsigned); i < Size; ++i) - V = (V << 8) | String[i]; - Bits.push_back(V); + +void FoldingSetNodeID::AddString(const char *String, const char *End) { + unsigned Size = static_cast(End - String); + Bits.push_back(Size); + if (!Size) return; + + unsigned Units = Size / 4; + unsigned Pos = 0; + const unsigned *Base = (const unsigned *)String; + + // If the string is aligned do a bulk transfer. + if (!((intptr_t)Base & 3)) { + Bits.append(Base, Base + Units); + Pos = (Units + 1) * 4; + } else { + // Otherwise do it the hard way. + for (Pos += 4; Pos <= Size; Pos += 4) { + unsigned V = ((unsigned char)String[Pos - 4] << 24) | + ((unsigned char)String[Pos - 3] << 16) | + ((unsigned char)String[Pos - 2] << 8) | + (unsigned char)String[Pos - 1]; + Bits.push_back(V); + } } + + // With the leftover bits. + unsigned V = 0; + // Pos will have overshot size by 4 - #bytes left over. + switch (Pos - Size) { + case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru. + case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru. + case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break; + default: return; // Nothing left. + } + + Bits.push_back(V); +} + +void FoldingSetNodeID::AddString(const char *String) { + AddString(String, String + strlen(String)); +} + +void FoldingSetNodeID::AddString(const std::string &String) { + AddString(&*String.begin(), &*String.end()); } -/// ComputeHash - Compute a strong hash value for this NodeID, used to +/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to /// lookup the node in the FoldingSetImpl. -unsigned FoldingSetImpl::NodeID::ComputeHash() const { +unsigned FoldingSetNodeID::ComputeHash() const { // This is adapted from SuperFastHash by Paul Hsieh. - unsigned Hash = Bits.size(); + unsigned Hash = static_cast(Bits.size()); for (const unsigned *BP = &Bits[0], *E = BP+Bits.size(); BP != E; ++BP) { unsigned Data = *BP; Hash += Data & 0xFFFF; @@ -91,58 +133,68 @@ unsigned FoldingSetImpl::NodeID::ComputeHash() const { /// operator== - Used to compare two nodes to each other. /// -bool FoldingSetImpl::NodeID::operator==(const FoldingSetImpl::NodeID &RHS)const{ +bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS)const{ if (Bits.size() != RHS.Bits.size()) return false; return memcmp(&Bits[0], &RHS.Bits[0], Bits.size()*sizeof(Bits[0])) == 0; } //===----------------------------------------------------------------------===// -// FoldingSetImpl Implementation - -FoldingSetImpl::FoldingSetImpl() : NumNodes(0) { - NumBuckets = 64; - Buckets = new void*[NumBuckets]; - memset(Buckets, 0, NumBuckets*sizeof(void*)); -} -FoldingSetImpl::~FoldingSetImpl() { - delete [] Buckets; -} +/// Helper functions for FoldingSetImpl. /// GetNextPtr - In order to save space, each bucket is a /// singly-linked-list. In order to make deletion more efficient, we make /// the list circular, so we can delete a node without computing its hash. /// The problem with this is that the start of the hash buckets are not -/// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null -/// : use GetBucketPtr when this happens. -FoldingSetImpl::Node *FoldingSetImpl::GetNextPtr(void *NextInBucketPtr) { - if (NextInBucketPtr >= Buckets && NextInBucketPtr < Buckets+NumBuckets) +/// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null: +/// use GetBucketPtr when this happens. +static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) { + // The low bit is set if this is the pointer back to the bucket. + if (reinterpret_cast(NextInBucketPtr) & 1) return 0; - return static_cast(NextInBucketPtr); + + return static_cast(NextInBucketPtr); } -/// GetNextPtr - This is just like the previous GetNextPtr implementation, -/// but allows a bucket array to be specified. -FoldingSetImpl::Node *FoldingSetImpl::GetNextPtr(void *NextInBucketPtr, - void **Bucks, - unsigned NumBuck) { - if (NextInBucketPtr >= Bucks && NextInBucketPtr < Bucks+NumBuck) - return 0; - return static_cast(NextInBucketPtr); -} -/// GetBucketPtr - Provides a casting of a bucket pointer for isNode /// testing. -void **FoldingSetImpl::GetBucketPtr(void *NextInBucketPtr) { - return static_cast(NextInBucketPtr); +static void **GetBucketPtr(void *NextInBucketPtr) { + intptr_t Ptr = reinterpret_cast(NextInBucketPtr); + assert((Ptr & 1) && "Not a bucket pointer"); + return reinterpret_cast(Ptr & ~intptr_t(1)); } /// GetBucketFor - Hash the specified node ID and return the hash bucket for /// the specified ID. -void **FoldingSetImpl::GetBucketFor(const NodeID &ID) const { +static void **GetBucketFor(const FoldingSetNodeID &ID, + void **Buckets, unsigned NumBuckets) { // NumBuckets is always a power of 2. unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1); - return Buckets+BucketNum; + return Buckets + BucketNum; +} + +//===----------------------------------------------------------------------===// +// FoldingSetImpl Implementation + +FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { + assert(5 < Log2InitSize && Log2InitSize < 32 && + "Initial hash table size out of range"); + NumBuckets = 1 << Log2InitSize; + Buckets = new void*[NumBuckets+1]; + clear(); +} +FoldingSetImpl::~FoldingSetImpl() { + delete [] Buckets; +} +void FoldingSetImpl::clear() { + // Set all but the last bucket to null pointers. + memset(Buckets, 0, NumBuckets*sizeof(void*)); + + // Set the very last bucket to be a non-null "pointer". + Buckets[NumBuckets] = reinterpret_cast(-1); + + // Reset the node count to zero. + NumNodes = 0; } /// GrowHashTable - Double the size of the hash table and rehash everything. @@ -152,26 +204,24 @@ void FoldingSetImpl::GrowHashTable() { unsigned OldNumBuckets = NumBuckets; NumBuckets <<= 1; - // Reset the node count to zero: we're going to reinsert everything. - NumNodes = 0; - // Clear out new buckets. - Buckets = new void*[NumBuckets]; - memset(Buckets, 0, NumBuckets*sizeof(void*)); + Buckets = new void*[NumBuckets+1]; + clear(); // Walk the old buckets, rehashing nodes into their new place. + FoldingSetNodeID ID; for (unsigned i = 0; i != OldNumBuckets; ++i) { void *Probe = OldBuckets[i]; if (!Probe) continue; - while (Node *NodeInBucket = GetNextPtr(Probe, OldBuckets, OldNumBuckets)){ + while (Node *NodeInBucket = GetNextPtr(Probe)) { // Figure out the next link, remove NodeInBucket from the old link. Probe = NodeInBucket->getNextInBucket(); NodeInBucket->SetNextInBucket(0); // Insert the node into the new bucket, after recomputing the hash. - NodeID ID; GetNodeProfile(ID, NodeInBucket); - InsertNode(NodeInBucket, GetBucketFor(ID)); + InsertNode(NodeInBucket, GetBucketFor(ID, Buckets, NumBuckets)); + ID.clear(); } } @@ -181,20 +231,23 @@ void FoldingSetImpl::GrowHashTable() { /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, /// return it. If not, return the insertion token that will make insertion /// faster. -FoldingSetImpl::Node *FoldingSetImpl::FindNodeOrInsertPos(const NodeID &ID, - void *&InsertPos) { - void **Bucket = GetBucketFor(ID); +FoldingSetImpl::Node +*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, + void *&InsertPos) { + + void **Bucket = GetBucketFor(ID, Buckets, NumBuckets); void *Probe = *Bucket; InsertPos = 0; + FoldingSetNodeID OtherID; while (Node *NodeInBucket = GetNextPtr(Probe)) { - NodeID OtherID; GetNodeProfile(OtherID, NodeInBucket); if (OtherID == ID) return NodeInBucket; Probe = NodeInBucket->getNextInBucket(); + OtherID.clear(); } // Didn't find the node, return null with the bucket as the InsertPos. @@ -206,14 +259,16 @@ FoldingSetImpl::Node *FoldingSetImpl::FindNodeOrInsertPos(const NodeID &ID, /// is not already in the map. InsertPos must be obtained from /// FindNodeOrInsertPos. void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { - ++NumNodes; + assert(N->getNextInBucket() == 0); // Do we need to grow the hashtable? - if (NumNodes > NumBuckets*2) { + if (NumNodes+1 > NumBuckets*2) { GrowHashTable(); - NodeID ID; + FoldingSetNodeID ID; GetNodeProfile(ID, N); - InsertPos = GetBucketFor(ID); + InsertPos = GetBucketFor(ID, Buckets, NumBuckets); } + + ++NumNodes; /// The insert position is actually a bucket pointer. void **Bucket = static_cast(InsertPos); @@ -221,11 +276,12 @@ void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { void *Next = *Bucket; // If this is the first insertion into this bucket, its next pointer will be - // null. Pretend as if it pointed to itself. + // null. Pretend as if it pointed to itself, setting the low bit to indicate + // that it is a pointer to the bucket. if (Next == 0) - Next = Bucket; + Next = reinterpret_cast(reinterpret_cast(Bucket)|1); - // Set the nodes next pointer, and make the bucket point to the node. + // Set the node's next pointer, and make the bucket point to the node. N->SetNextInBucket(Next); *Bucket = N; } @@ -234,15 +290,17 @@ void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { /// removed or false if the node was not in the folding set. bool FoldingSetImpl::RemoveNode(Node *N) { // Because each bucket is a circular list, we don't need to compute N's hash - // to remove it. Chase around the list until we find the node (or bucket) - // which points to N. + // to remove it. void *Ptr = N->getNextInBucket(); if (Ptr == 0) return false; // Not in folding set. --NumNodes; + N->SetNextInBucket(0); + // Remember what N originally pointed to, either a bucket or another node. void *NodeNextPtr = Ptr; - N->SetNextInBucket(0); + + // Chase around the list until we find the node (or bucket) which points to N. while (true) { if (Node *NodeInBucket = GetNextPtr(Ptr)) { // Advance pointer. @@ -272,7 +330,7 @@ bool FoldingSetImpl::RemoveNode(Node *N) { /// equal to the specified node, return it. Otherwise, insert 'N' and it /// instead. FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { - NodeID ID; + FoldingSetNodeID ID; GetNodeProfile(ID, N); void *IP; if (Node *E = FindNodeOrInsertPos(ID, IP)) @@ -280,3 +338,42 @@ FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { InsertNode(N, IP); return N; } + +//===----------------------------------------------------------------------===// +// FoldingSetIteratorImpl Implementation + +FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) { + // Skip to the first non-null non-self-cycle bucket. + while (*Bucket != reinterpret_cast(-1) && + (*Bucket == 0 || GetNextPtr(*Bucket) == 0)) + ++Bucket; + + NodePtr = static_cast(*Bucket); +} + +void FoldingSetIteratorImpl::advance() { + // If there is another link within this bucket, go to it. + void *Probe = NodePtr->getNextInBucket(); + + if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe)) + NodePtr = NextNodeInBucket; + else { + // Otherwise, this is the last link in this bucket. + void **Bucket = GetBucketPtr(Probe); + + // Skip to the next non-null non-self-cycle bucket. + do { + ++Bucket; + } while (*Bucket != reinterpret_cast(-1) && + (*Bucket == 0 || GetNextPtr(*Bucket) == 0)); + + NodePtr = static_cast(*Bucket); + } +} + +//===----------------------------------------------------------------------===// +// FoldingSetBucketIteratorImpl Implementation + +FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) { + Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket; +}