X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FFoldingSet.cpp;h=463511408759ccc8cb5829ecf19ce8103ce1028c;hb=5dac5bd2256178b7dafb30ea6fc7612eb65cf4e7;hp=d2e35b8eb676d264cbf8b17d59d754ca73127c8e;hpb=e27c3ea2bcdabf1b8be87675c66a38c3ad0ac1f9;p=oota-llvm.git diff --git a/lib/Support/FoldingSet.cpp b/lib/Support/FoldingSet.cpp index d2e35b8eb67..46351140875 100644 --- a/lib/Support/FoldingSet.cpp +++ b/lib/Support/FoldingSet.cpp @@ -8,17 +8,16 @@ //===----------------------------------------------------------------------===// // // 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/MathExtras.h" #include "llvm/Support/Host.h" +#include "llvm/Support/MathExtras.h" #include #include using namespace llvm; @@ -29,24 +28,7 @@ using namespace llvm; /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, /// used to lookup the node in the FoldingSetImpl. unsigned FoldingSetNodeIDRef::ComputeHash() const { - // This is adapted from SuperFastHash by Paul Hsieh. - unsigned Hash = static_cast(Size); - for (const unsigned *BP = Data, *E = BP+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 static_cast(hash_combine_range(Data, Data+Size)); } bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const { @@ -54,6 +36,14 @@ bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const { 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 @@ -64,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); @@ -92,7 +80,7 @@ void FoldingSetNodeID::AddInteger(long long I) { } void FoldingSetNodeID::AddInteger(unsigned long long I) { AddInteger(unsigned(I)); - if ((uint64_t)(int)I != I) + if ((uint64_t)(unsigned)I != I) Bits.push_back(unsigned(I >> 32)); } @@ -113,7 +101,7 @@ void FoldingSetNodeID::AddString(StringRef String) { // Otherwise do it the hard way. // To be compatible with above bulk transfer, we need to take endianness // into account. - if (sys::isBigEndianHost()) { + if (sys::IsBigEndianHost) { for (Pos += 4; Pos <= Size; Pos += 4) { unsigned V = ((unsigned char)String[Pos - 4] << 24) | ((unsigned char)String[Pos - 3] << 16) | @@ -122,7 +110,7 @@ void FoldingSetNodeID::AddString(StringRef String) { Bits.push_back(V); } } else { - assert(sys::isLittleEndianHost() && "Unexpected host endianness"); + 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) | @@ -160,7 +148,7 @@ unsigned FoldingSetNodeID::ComputeHash() const { /// operator== - Used to compare two nodes to each other. /// -bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS)const{ +bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const { return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); } @@ -170,6 +158,16 @@ 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. @@ -192,7 +190,7 @@ FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const { 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 nullptr; return static_cast(NextInBucketPtr); } @@ -264,7 +262,7 @@ void FoldingSetImpl::GrowHashTable() { while (Node *NodeInBucket = GetNextPtr(Probe)) { // Figure out the next link, remove NodeInBucket from the old link. Probe = NodeInBucket->getNextInBucket(); - NodeInBucket->SetNextInBucket(0); + NodeInBucket->SetNextInBucket(nullptr); // Insert the node into the new bucket, after recomputing the hash. InsertNode(NodeInBucket, @@ -283,15 +281,15 @@ void FoldingSetImpl::GrowHashTable() { FoldingSetImpl::Node *FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { - - void **Bucket = GetBucketFor(ID.ComputeHash(), Buckets, NumBuckets); + unsigned IDHash = ID.ComputeHash(); + void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets); void *Probe = *Bucket; - InsertPos = 0; + InsertPos = nullptr; FoldingSetNodeID TempID; while (Node *NodeInBucket = GetNextPtr(Probe)) { - if (NodeEquals(NodeInBucket, ID, TempID)) + if (NodeEquals(NodeInBucket, ID, IDHash, TempID)) return NodeInBucket; TempID.clear(); @@ -300,14 +298,14 @@ FoldingSetImpl::Node // Didn't find the node, return null with the bucket as the InsertPos. InsertPos = Bucket; - return 0; + return nullptr; } /// InsertNode - Insert the specified node into the folding set, knowing that it /// is not already in the map. InsertPos must be obtained from /// FindNodeOrInsertPos. void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { - assert(N->getNextInBucket() == 0); + assert(!N->getNextInBucket()); // Do we need to grow the hashtable? if (NumNodes+1 > NumBuckets*2) { GrowHashTable(); @@ -325,7 +323,7 @@ void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { // If this is the first insertion into this bucket, its next pointer will be // 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) + if (!Next) Next = reinterpret_cast(reinterpret_cast(Bucket)|1); // Set the node's next pointer, and make the bucket point to the node. @@ -339,10 +337,10 @@ bool FoldingSetImpl::RemoveNode(Node *N) { // Because each bucket is a circular list, we don't need to compute N's hash // to remove it. void *Ptr = N->getNextInBucket(); - if (Ptr == 0) return false; // Not in folding set. + if (!Ptr) return false; // Not in folding set. --NumNodes; - N->SetNextInBucket(0); + N->SetNextInBucket(nullptr); // Remember what N originally pointed to, either a bucket or another node. void *NodeNextPtr = Ptr; @@ -392,7 +390,7 @@ FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { 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 || !GetNextPtr(*Bucket))) ++Bucket; NodePtr = static_cast(*Bucket); @@ -412,7 +410,7 @@ void FoldingSetIteratorImpl::advance() { do { ++Bucket; } while (*Bucket != reinterpret_cast(-1) && - (*Bucket == 0 || GetNextPtr(*Bucket) == 0)); + (!*Bucket || !GetNextPtr(*Bucket))); NodePtr = static_cast(*Bucket); } @@ -422,5 +420,5 @@ void FoldingSetIteratorImpl::advance() { // FoldingSetBucketIteratorImpl Implementation FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) { - Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket; + Ptr = (!*Bucket || !GetNextPtr(*Bucket)) ? (void*) Bucket : *Bucket; }