X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FFoldingSet.cpp;h=145f12dc1e5d2e6d92586f59e1654d8a72097f6b;hb=5a1a1856a4dfa1335d937437fade5c0bbab06560;hp=2d2279cefe5c1f24c6a4f49c9e99b92bbaff48a2;hpb=1f801fa5ada9cb40fb97ae755c282e91af54a1bc;p=oota-llvm.git diff --git a/lib/Support/FoldingSet.cpp b/lib/Support/FoldingSet.cpp index 2d2279cefe5..145f12dc1e5 100644 --- a/lib/Support/FoldingSet.cpp +++ b/lib/Support/FoldingSet.cpp @@ -8,17 +8,42 @@ //===----------------------------------------------------------------------===// // // This file implements a hash set that can be used to remove duplication of -// nodes in a graph. This code was originally created by Chris Lattner for use -// with SelectionDAGCSEMap, but was isolated to provide use across the llvm code -// set. +// nodes in a graph. // //===----------------------------------------------------------------------===// #include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/Hashing.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/Host.h" #include "llvm/Support/MathExtras.h" #include +#include using namespace llvm; +//===----------------------------------------------------------------------===// +// FoldingSetNodeIDRef Implementation + +/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, +/// used to lookup the node in the FoldingSetImpl. +unsigned FoldingSetNodeIDRef::ComputeHash() const { + return static_cast(hash_combine_range(Data, Data+Size)); +} + +bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const { + if (Size != RHS.Size) return false; + return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0; +} + +/// Used to compare the "ordering" of two nodes as defined by the +/// profiled bits and their ordering defined by memcmp(). +bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const { + if (Size != RHS.Size) + return Size < RHS.Size; + return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0; +} + //===----------------------------------------------------------------------===// // FoldingSetNodeID Implementation @@ -29,10 +54,8 @@ void FoldingSetNodeID::AddPointer(const void *Ptr) { // depend on the host. It doesn't matter however, because hashing on // pointer values in inherently unstable. Nothing should depend on the // ordering of nodes in the folding set. - intptr_t PtrI = (intptr_t)Ptr; - Bits.push_back(unsigned(PtrI)); - if (sizeof(intptr_t) > sizeof(unsigned)) - Bits.push_back(unsigned(uint64_t(PtrI) >> 32)); + Bits.append(reinterpret_cast(&Ptr), + reinterpret_cast(&Ptr+1)); } void FoldingSetNodeID::AddInteger(signed I) { Bits.push_back(I); @@ -40,30 +63,35 @@ void FoldingSetNodeID::AddInteger(signed I) { void FoldingSetNodeID::AddInteger(unsigned I) { Bits.push_back(I); } -void FoldingSetNodeID::AddInteger(int64_t I) { - AddInteger((uint64_t)I); +void FoldingSetNodeID::AddInteger(long I) { + AddInteger((unsigned long)I); } -void FoldingSetNodeID::AddInteger(uint64_t I) { - Bits.push_back(unsigned(I)); - - // If the integer is small, encode it just as 32-bits. - if ((uint64_t)(int)I != I) - Bits.push_back(unsigned(I >> 32)); +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 FoldingSetNodeID::AddFloat(float F) { - Bits.push_back(FloatToBits(F)); +void FoldingSetNodeID::AddInteger(long long I) { + AddInteger((unsigned long long)I); } -void FoldingSetNodeID::AddDouble(double D) { - AddInteger(DoubleToBits(D)); +void FoldingSetNodeID::AddInteger(unsigned long long I) { + AddInteger(unsigned(I)); + if ((uint64_t)(unsigned)I != I) + Bits.push_back(unsigned(I >> 32)); } -void FoldingSetNodeID::AddString(const std::string &String) { - unsigned Size = String.size(); + +void FoldingSetNodeID::AddString(StringRef String) { + unsigned Size = String.size(); Bits.push_back(Size); if (!Size) return; unsigned Units = Size / 4; unsigned Pos = 0; - const unsigned *Base = (const unsigned *)String.data(); + const unsigned *Base = (const unsigned*) String.data(); // If the string is aligned do a bulk transfer. if (!((intptr_t)Base & 3)) { @@ -71,18 +99,32 @@ void FoldingSetNodeID::AddString(const std::string &String) { 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); + // To be compatible with above bulk transfer, we need to take endianness + // into account. + if (sys::IsBigEndianHost) { + 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); + } + } else { + assert(sys::IsLittleEndianHost && "Unexpected host endianness"); + for (Pos += 4; Pos <= Size; Pos += 4) { + unsigned V = ((unsigned char)String[Pos - 1] << 24) | + ((unsigned char)String[Pos - 2] << 16) | + ((unsigned char)String[Pos - 3] << 8) | + (unsigned char)String[Pos - 4]; + Bits.push_back(V); + } } } // With the leftover bits. unsigned V = 0; - // Pos will have overshot size by 4 - #bytes left over. + // Pos will have overshot size by 4 - #bytes left over. + // No need to take endianness into account here - this is always executed. 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. @@ -93,36 +135,48 @@ void FoldingSetNodeID::AddString(const std::string &String) { Bits.push_back(V); } +// AddNodeID - Adds the Bit data of another ID to *this. +void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) { + Bits.append(ID.Bits.begin(), ID.Bits.end()); +} + /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to /// lookup the node in the FoldingSetImpl. unsigned FoldingSetNodeID::ComputeHash() const { - // This is adapted from SuperFastHash by Paul Hsieh. - unsigned Hash = Bits.size(); - for (const unsigned *BP = &Bits[0], *E = BP+Bits.size(); BP != E; ++BP) { - unsigned Data = *BP; - Hash += Data & 0xFFFF; - unsigned Tmp = ((Data >> 16) << 11) ^ Hash; - Hash = (Hash << 16) ^ Tmp; - Hash += Hash >> 11; - } - - // Force "avalanching" of final 127 bits. - Hash ^= Hash << 3; - Hash += Hash >> 5; - Hash ^= Hash << 4; - Hash += Hash >> 17; - Hash ^= Hash << 25; - Hash += Hash >> 6; - return Hash; + return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash(); } /// operator== - Used to compare two nodes to each other. /// -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; +bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const { + return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); } +/// operator== - Used to compare two nodes to each other. +/// +bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const { + return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS; +} + +/// Used to compare the "ordering" of two nodes as defined by the +/// profiled bits and their ordering defined by memcmp(). +bool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const { + return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); +} + +bool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const { + return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS; +} + +/// Intern - Copy this node's data to a memory region allocated from the +/// given allocator and return a FoldingSetNodeIDRef describing the +/// interned data. +FoldingSetNodeIDRef +FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const { + unsigned *New = Allocator.Allocate(Bits.size()); + std::uninitialized_copy(Bits.begin(), Bits.end(), New); + return FoldingSetNodeIDRef(New, Bits.size()); +} //===----------------------------------------------------------------------===// /// Helper functions for FoldingSetImpl. @@ -151,28 +205,42 @@ static void **GetBucketPtr(void *NextInBucketPtr) { /// GetBucketFor - Hash the specified node ID and return the hash bucket for /// the specified ID. -static void **GetBucketFor(const FoldingSetNodeID &ID, - void **Buckets, unsigned NumBuckets) { +static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) { // NumBuckets is always a power of 2. - unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1); + unsigned BucketNum = Hash & (NumBuckets-1); return Buckets + BucketNum; } +/// AllocateBuckets - Allocated initialized bucket memory. +static void **AllocateBuckets(unsigned NumBuckets) { + void **Buckets = static_cast(calloc(NumBuckets+1, sizeof(void*))); + // Set the very last bucket to be a non-null "pointer". + Buckets[NumBuckets] = reinterpret_cast(-1); + return Buckets; +} + //===----------------------------------------------------------------------===// // FoldingSetImpl Implementation -FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) : NumNodes(0) { +FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { assert(5 < Log2InitSize && Log2InitSize < 32 && "Initial hash table size out of range"); NumBuckets = 1 << Log2InitSize; - Buckets = new void*[NumBuckets+1]; - memset(Buckets, 0, NumBuckets*sizeof(void*)); - - // Set the very last bucket to be a non-null "pointer". - Buckets[NumBuckets] = reinterpret_cast(-2); + Buckets = AllocateBuckets(NumBuckets); + NumNodes = 0; } FoldingSetImpl::~FoldingSetImpl() { - delete [] Buckets; + free(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. @@ -182,17 +250,12 @@ 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+1]; - memset(Buckets, 0, NumBuckets*sizeof(void*)); - - // Set the very last bucket to be a non-null "pointer". - Buckets[NumBuckets] = reinterpret_cast(-1); + Buckets = AllocateBuckets(NumBuckets); + NumNodes = 0; // Walk the old buckets, rehashing nodes into their new place. + FoldingSetNodeID TempID; for (unsigned i = 0; i != OldNumBuckets; ++i) { void *Probe = OldBuckets[i]; if (!Probe) continue; @@ -202,13 +265,14 @@ void FoldingSetImpl::GrowHashTable() { NodeInBucket->SetNextInBucket(0); // Insert the node into the new bucket, after recomputing the hash. - FoldingSetNodeID ID; - GetNodeProfile(ID, NodeInBucket); - InsertNode(NodeInBucket, GetBucketFor(ID, Buckets, NumBuckets)); + InsertNode(NodeInBucket, + GetBucketFor(ComputeNodeHash(NodeInBucket, TempID), + Buckets, NumBuckets)); + TempID.clear(); } } - delete[] OldBuckets; + free(OldBuckets); } /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, @@ -217,17 +281,17 @@ void FoldingSetImpl::GrowHashTable() { FoldingSetImpl::Node *FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { - - void **Bucket = GetBucketFor(ID, Buckets, NumBuckets); + unsigned IDHash = ID.ComputeHash(); + void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets); void *Probe = *Bucket; InsertPos = 0; + FoldingSetNodeID TempID; while (Node *NodeInBucket = GetNextPtr(Probe)) { - FoldingSetNodeID OtherID; - GetNodeProfile(OtherID, NodeInBucket); - if (OtherID == ID) + if (NodeEquals(NodeInBucket, ID, IDHash, TempID)) return NodeInBucket; + TempID.clear(); Probe = NodeInBucket->getNextInBucket(); } @@ -245,9 +309,8 @@ void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { // Do we need to grow the hashtable? if (NumNodes+1 > NumBuckets*2) { GrowHashTable(); - FoldingSetNodeID ID; - GetNodeProfile(ID, N); - InsertPos = GetBucketFor(ID, Buckets, NumBuckets); + FoldingSetNodeID TempID; + InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets); } ++NumNodes; @@ -313,7 +376,7 @@ bool FoldingSetImpl::RemoveNode(Node *N) { /// instead. FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { FoldingSetNodeID ID; - GetNodeProfile(ID, N); + GetNodeProfile(N, ID); void *IP; if (Node *E = FindNodeOrInsertPos(ID, IP)) return E; @@ -326,7 +389,8 @@ FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) { // Skip to the first non-null non-self-cycle bucket. - while (*Bucket == 0 || GetNextPtr(*Bucket) == 0) + while (*Bucket != reinterpret_cast(-1) && + (*Bucket == 0 || GetNextPtr(*Bucket) == 0)) ++Bucket; NodePtr = static_cast(*Bucket); @@ -345,7 +409,8 @@ void FoldingSetIteratorImpl::advance() { // Skip to the next non-null non-self-cycle bucket. do { ++Bucket; - } while (*Bucket == 0 || GetNextPtr(*Bucket) == 0); + } while (*Bucket != reinterpret_cast(-1) && + (*Bucket == 0 || GetNextPtr(*Bucket) == 0)); NodePtr = static_cast(*Bucket); }