FoldingSet.cpp revision ed5edea96d72440679311d7d31d39804967f3220
1282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski//===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===// 2282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 3282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// The LLVM Compiler Infrastructure 4282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 5282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// This file is distributed under the University of Illinois Open Source 6fab50875b98e8274ac8ee44b38ba42521bbbf1f9Adam Lesinski// License. See LICENSE.TXT for details. 7282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 82c72b6822debb08fe997926eedc110f62d287d34Adam Lesinski//===----------------------------------------------------------------------===// 92c72b6822debb08fe997926eedc110f62d287d34Adam Lesinski// 10282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// This file implements a hash set that can be used to remove duplication of 11282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// nodes in a graph. This code was originally created by Chris Lattner for use 12282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// with SelectionDAGCSEMap, but was isolated to provide use across the llvm code 13282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// set. 142c72b6822debb08fe997926eedc110f62d287d34Adam Lesinski// 152c72b6822debb08fe997926eedc110f62d287d34Adam Lesinski//===----------------------------------------------------------------------===// 162c72b6822debb08fe997926eedc110f62d287d34Adam Lesinski 17282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "llvm/ADT/FoldingSet.h" 182c72b6822debb08fe997926eedc110f62d287d34Adam Lesinski#include "llvm/ADT/Hashing.h" 19282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "llvm/Support/Allocator.h" 202c72b6822debb08fe997926eedc110f62d287d34Adam Lesinski#include "llvm/Support/ErrorHandling.h" 21282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "llvm/Support/MathExtras.h" 22282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "llvm/Support/Host.h" 232c72b6822debb08fe997926eedc110f62d287d34Adam Lesinski#include <cassert> 24282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include <cstring> 25282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiusing namespace llvm; 26282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 27ad751224401564dcc8338df3d5c4c5de7722be8fAdam Lesinski//===----------------------------------------------------------------------===// 28ad751224401564dcc8338df3d5c4c5de7722be8fAdam Lesinski// FoldingSetNodeIDRef Implementation 29ad751224401564dcc8338df3d5c4c5de7722be8fAdam Lesinski 30ad751224401564dcc8338df3d5c4c5de7722be8fAdam Lesinski/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, 31282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// used to lookup the node in the FoldingSetImpl. 32282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiunsigned FoldingSetNodeIDRef::ComputeHash() const { 33282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return static_cast<unsigned>(hash_combine_range(Data, Data+Size)); 34282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 35282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 36282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskibool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const { 37282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (Size != RHS.Size) return false; 38282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0; 39ad751224401564dcc8338df3d5c4c5de7722be8fAdam Lesinski} 40282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 41282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski//===----------------------------------------------------------------------===// 42282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// FoldingSetNodeID Implementation 43282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 44282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// Add* - Add various data types to Bit data. 45282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// 46282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetNodeID::AddPointer(const void *Ptr) { 47282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Note: this adds pointers to the hash using sizes and endianness that 48282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // depend on the host. It doesn't matter however, because hashing on 49282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // pointer values in inherently unstable. Nothing should depend on the 50282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // ordering of nodes in the folding set. 51282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.append(reinterpret_cast<unsigned *>(&Ptr), 52282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski reinterpret_cast<unsigned *>(&Ptr+1)); 53282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 54282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetNodeID::AddInteger(signed I) { 55282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.push_back(I); 56282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 57282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetNodeID::AddInteger(unsigned I) { 58282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.push_back(I); 59282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 60282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetNodeID::AddInteger(long I) { 61282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski AddInteger((unsigned long)I); 62282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 63282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetNodeID::AddInteger(unsigned long I) { 64282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (sizeof(long) == sizeof(int)) 65282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski AddInteger(unsigned(I)); 66282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski else if (sizeof(long) == sizeof(long long)) { 67282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski AddInteger((unsigned long long)I); 68282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } else { 69282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski llvm_unreachable("unexpected sizeof(long)"); 70282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 71282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 72282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetNodeID::AddInteger(long long I) { 73282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski AddInteger((unsigned long long)I); 74282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 75282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetNodeID::AddInteger(unsigned long long I) { 76282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski AddInteger(unsigned(I)); 77282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if ((uint64_t)(unsigned)I != I) 78282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.push_back(unsigned(I >> 32)); 79282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 80282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 81282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetNodeID::AddString(StringRef String) { 82282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski unsigned Size = String.size(); 83282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.push_back(Size); 84282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (!Size) return; 85282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 86282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski unsigned Units = Size / 4; 87282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski unsigned Pos = 0; 88282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const unsigned *Base = (const unsigned*) String.data(); 89282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 90282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // If the string is aligned do a bulk transfer. 91282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (!((intptr_t)Base & 3)) { 92282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.append(Base, Base + Units); 93282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Pos = (Units + 1) * 4; 94282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } else { 95282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Otherwise do it the hard way. 96282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // To be compatible with above bulk transfer, we need to take endianness 97282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // into account. 98282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (sys::isBigEndianHost()) { 99282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski for (Pos += 4; Pos <= Size; Pos += 4) { 100282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski unsigned V = ((unsigned char)String[Pos - 4] << 24) | 101282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski ((unsigned char)String[Pos - 3] << 16) | 102282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski ((unsigned char)String[Pos - 2] << 8) | 103282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski (unsigned char)String[Pos - 1]; 104282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.push_back(V); 105282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 106282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } else { 107282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski assert(sys::isLittleEndianHost() && "Unexpected host endianness"); 108282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski for (Pos += 4; Pos <= Size; Pos += 4) { 109282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski unsigned V = ((unsigned char)String[Pos - 1] << 24) | 110282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski ((unsigned char)String[Pos - 2] << 16) | 111282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski ((unsigned char)String[Pos - 3] << 8) | 112282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski (unsigned char)String[Pos - 4]; 113282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.push_back(V); 114282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 115282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 116282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 117282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 118282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // With the leftover bits. 119282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski unsigned V = 0; 120282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Pos will have overshot size by 4 - #bytes left over. 121282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // No need to take endianness into account here - this is always executed. 122282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski switch (Pos - Size) { 123282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru. 124282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru. 125282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break; 126282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski default: return; // Nothing left. 127282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 128282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 129282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.push_back(V); 130282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 131282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 132282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// AddNodeID - Adds the Bit data of another ID to *this. 133282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) { 134282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Bits.append(ID.Bits.begin(), ID.Bits.end()); 135282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 136282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 137282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to 138282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// lookup the node in the FoldingSetImpl. 139282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiunsigned FoldingSetNodeID::ComputeHash() const { 140282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash(); 141282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 142282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 143282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// operator== - Used to compare two nodes to each other. 144282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// 145282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskibool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS)const{ 146282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); 147282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 148282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 149282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// operator== - Used to compare two nodes to each other. 150282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// 151282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskibool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const { 152282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS; 153282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 154282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 155282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// Intern - Copy this node's data to a memory region allocated from the 156282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// given allocator and return a FoldingSetNodeIDRef describing the 157282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// interned data. 158282e181b58cf72b6ca770dc7ca5f91f135444502Adam LesinskiFoldingSetNodeIDRef 159282e181b58cf72b6ca770dc7ca5f91f135444502Adam LesinskiFoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const { 160282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski unsigned *New = Allocator.Allocate<unsigned>(Bits.size()); 161282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski std::uninitialized_copy(Bits.begin(), Bits.end(), New); 162282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return FoldingSetNodeIDRef(New, Bits.size()); 163282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 164282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 165282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski//===----------------------------------------------------------------------===// 166282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// Helper functions for FoldingSetImpl. 167282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 168282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// GetNextPtr - In order to save space, each bucket is a 169282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// singly-linked-list. In order to make deletion more efficient, we make 170282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// the list circular, so we can delete a node without computing its hash. 171282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// The problem with this is that the start of the hash buckets are not 172282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null: 173282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// use GetBucketPtr when this happens. 174282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) { 175282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // The low bit is set if this is the pointer back to the bucket. 176282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1) 177282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return 0; 178282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 179282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr); 180282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 181282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 182282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 183282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// testing. 184282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic void **GetBucketPtr(void *NextInBucketPtr) { 185282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr); 186282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski assert((Ptr & 1) && "Not a bucket pointer"); 187282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return reinterpret_cast<void**>(Ptr & ~intptr_t(1)); 188282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 189282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 190282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// GetBucketFor - Hash the specified node ID and return the hash bucket for 191282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// the specified ID. 192282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) { 193282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // NumBuckets is always a power of 2. 194282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski unsigned BucketNum = Hash & (NumBuckets-1); 195282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return Buckets + BucketNum; 196282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 197282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 198282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// AllocateBuckets - Allocated initialized bucket memory. 199282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic void **AllocateBuckets(unsigned NumBuckets) { 200282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*))); 201282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Set the very last bucket to be a non-null "pointer". 202282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 203282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return Buckets; 204282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 205282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 206282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski//===----------------------------------------------------------------------===// 207282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// FoldingSetImpl Implementation 208282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 209282e181b58cf72b6ca770dc7ca5f91f135444502Adam LesinskiFoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { 210282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski assert(5 < Log2InitSize && Log2InitSize < 32 && 211282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski "Initial hash table size out of range"); 212282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NumBuckets = 1 << Log2InitSize; 213282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Buckets = AllocateBuckets(NumBuckets); 214282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NumNodes = 0; 215282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 216282e181b58cf72b6ca770dc7ca5f91f135444502Adam LesinskiFoldingSetImpl::~FoldingSetImpl() { 217282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski free(Buckets); 218282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 219282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetImpl::clear() { 220282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Set all but the last bucket to null pointers. 221282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski memset(Buckets, 0, NumBuckets*sizeof(void*)); 222282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 223282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Set the very last bucket to be a non-null "pointer". 224282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 225282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 226282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Reset the node count to zero. 227282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NumNodes = 0; 228282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 229282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 230282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// GrowHashTable - Double the size of the hash table and rehash everything. 231282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// 232282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetImpl::GrowHashTable() { 233282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void **OldBuckets = Buckets; 234282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski unsigned OldNumBuckets = NumBuckets; 235282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NumBuckets <<= 1; 236282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 237282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Clear out new buckets. 238282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Buckets = AllocateBuckets(NumBuckets); 239282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NumNodes = 0; 240282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 241282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Walk the old buckets, rehashing nodes into their new place. 242282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski FoldingSetNodeID TempID; 243282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski for (unsigned i = 0; i != OldNumBuckets; ++i) { 244282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void *Probe = OldBuckets[i]; 245282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (!Probe) continue; 246282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski while (Node *NodeInBucket = GetNextPtr(Probe)) { 247282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Figure out the next link, remove NodeInBucket from the old link. 248282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Probe = NodeInBucket->getNextInBucket(); 249282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NodeInBucket->SetNextInBucket(0); 250282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 251282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Insert the node into the new bucket, after recomputing the hash. 252282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski InsertNode(NodeInBucket, 253282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski GetBucketFor(ComputeNodeHash(NodeInBucket, TempID), 254282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Buckets, NumBuckets)); 255282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski TempID.clear(); 256282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 257282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 258282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 259282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski free(OldBuckets); 260282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 261282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 262282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 263282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// return it. If not, return the insertion token that will make insertion 264282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// faster. 265282e181b58cf72b6ca770dc7ca5f91f135444502Adam LesinskiFoldingSetImpl::Node 266282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, 267282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void *&InsertPos) { 268282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 269282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void **Bucket = GetBucketFor(ID.ComputeHash(), Buckets, NumBuckets); 270282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void *Probe = *Bucket; 271282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 272282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski InsertPos = 0; 273282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 274282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski FoldingSetNodeID TempID; 275282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski while (Node *NodeInBucket = GetNextPtr(Probe)) { 276282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (NodeEquals(NodeInBucket, ID, TempID)) 277282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return NodeInBucket; 278282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski TempID.clear(); 279282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 280282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Probe = NodeInBucket->getNextInBucket(); 281282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 282282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 283282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Didn't find the node, return null with the bucket as the InsertPos. 284282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski InsertPos = Bucket; 285282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return 0; 286282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 287282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 288282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// InsertNode - Insert the specified node into the folding set, knowing that it 289282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// is not already in the map. InsertPos must be obtained from 290282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// FindNodeOrInsertPos. 291282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { 292282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski assert(N->getNextInBucket() == 0); 293282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Do we need to grow the hashtable? 294282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (NumNodes+1 > NumBuckets*2) { 295282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski GrowHashTable(); 296282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski FoldingSetNodeID TempID; 297282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets); 298282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 299282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 300282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski ++NumNodes; 301282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 302282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// The insert position is actually a bucket pointer. 303282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void **Bucket = static_cast<void**>(InsertPos); 304282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 305282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void *Next = *Bucket; 306282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 307282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // If this is the first insertion into this bucket, its next pointer will be 308282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // null. Pretend as if it pointed to itself, setting the low bit to indicate 309282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // that it is a pointer to the bucket. 310282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (Next == 0) 311282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1); 312282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 313282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Set the node's next pointer, and make the bucket point to the node. 314282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski N->SetNextInBucket(Next); 315282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski *Bucket = N; 316282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 317282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 318282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// RemoveNode - Remove a node from the folding set, returning true if one was 319282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// removed or false if the node was not in the folding set. 320282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskibool FoldingSetImpl::RemoveNode(Node *N) { 321282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Because each bucket is a circular list, we don't need to compute N's hash 322282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // to remove it. 323282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void *Ptr = N->getNextInBucket(); 324282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (Ptr == 0) return false; // Not in folding set. 325282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 326282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski --NumNodes; 327282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski N->SetNextInBucket(0); 328282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 329282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Remember what N originally pointed to, either a bucket or another node. 330282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void *NodeNextPtr = Ptr; 331282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 332282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Chase around the list until we find the node (or bucket) which points to N. 333282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski while (true) { 334282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (Node *NodeInBucket = GetNextPtr(Ptr)) { 335282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Advance pointer. 336282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Ptr = NodeInBucket->getNextInBucket(); 337282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 338282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // We found a node that points to N, change it to point to N's next node, 339282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // removing N from the list. 340282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (Ptr == N) { 341282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NodeInBucket->SetNextInBucket(NodeNextPtr); 342282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return true; 343282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 344282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } else { 345282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void **Bucket = GetBucketPtr(Ptr); 346282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Ptr = *Bucket; 347282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 348282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // If we found that the bucket points to N, update the bucket to point to 349282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // whatever is next. 350282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (Ptr == N) { 351282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski *Bucket = NodeNextPtr; 352282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return true; 353282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 354282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 355282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 356282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 357282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 358282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// GetOrInsertNode - If there is an existing simple Node exactly 359282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// equal to the specified node, return it. Otherwise, insert 'N' and it 360282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/// instead. 361282e181b58cf72b6ca770dc7ca5f91f135444502Adam LesinskiFoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { 362282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski FoldingSetNodeID ID; 363282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski GetNodeProfile(N, ID); 364282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void *IP; 365282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (Node *E = FindNodeOrInsertPos(ID, IP)) 366282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return E; 367282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski InsertNode(N, IP); 368282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return N; 369282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 370282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 371282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski//===----------------------------------------------------------------------===// 372282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// FoldingSetIteratorImpl Implementation 373282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 374282e181b58cf72b6ca770dc7ca5f91f135444502Adam LesinskiFoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) { 375282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Skip to the first non-null non-self-cycle bucket. 376282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski while (*Bucket != reinterpret_cast<void*>(-1) && 377282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski (*Bucket == 0 || GetNextPtr(*Bucket) == 0)) 378282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski ++Bucket; 379282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 380282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NodePtr = static_cast<FoldingSetNode*>(*Bucket); 381282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 382282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 383282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid FoldingSetIteratorImpl::advance() { 384282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // If there is another link within this bucket, go to it. 385282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void *Probe = NodePtr->getNextInBucket(); 386282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 387282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe)) 388282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NodePtr = NextNodeInBucket; 38976327314d2238e105f8b94909f9c0cf85caca318Maurice Chu else { 39076327314d2238e105f8b94909f9c0cf85caca318Maurice Chu // Otherwise, this is the last link in this bucket. 39176327314d2238e105f8b94909f9c0cf85caca318Maurice Chu void **Bucket = GetBucketPtr(Probe); 39276327314d2238e105f8b94909f9c0cf85caca318Maurice Chu 39376327314d2238e105f8b94909f9c0cf85caca318Maurice Chu // Skip to the next non-null non-self-cycle bucket. 39476327314d2238e105f8b94909f9c0cf85caca318Maurice Chu do { 39576327314d2238e105f8b94909f9c0cf85caca318Maurice Chu ++Bucket; 39676327314d2238e105f8b94909f9c0cf85caca318Maurice Chu } while (*Bucket != reinterpret_cast<void*>(-1) && 39776327314d2238e105f8b94909f9c0cf85caca318Maurice Chu (*Bucket == 0 || GetNextPtr(*Bucket) == 0)); 39876327314d2238e105f8b94909f9c0cf85caca318Maurice Chu 39976327314d2238e105f8b94909f9c0cf85caca318Maurice Chu NodePtr = static_cast<FoldingSetNode*>(*Bucket); 4002675f769673f69b0661ddee346292f25cb30a296Maurice Chu } 4012675f769673f69b0661ddee346292f25cb30a296Maurice Chu} 40276327314d2238e105f8b94909f9c0cf85caca318Maurice Chu 40376327314d2238e105f8b94909f9c0cf85caca318Maurice Chu//===----------------------------------------------------------------------===// 40476327314d2238e105f8b94909f9c0cf85caca318Maurice Chu// FoldingSetBucketIteratorImpl Implementation 40576327314d2238e105f8b94909f9c0cf85caca318Maurice Chu 40676327314d2238e105f8b94909f9c0cf85caca318Maurice ChuFoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) { 40776327314d2238e105f8b94909f9c0cf85caca318Maurice Chu Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket; 40876327314d2238e105f8b94909f9c0cf85caca318Maurice Chu} 40976327314d2238e105f8b94909f9c0cf85caca318Maurice Chu