Home | History | Annotate | Download | only in Support
      1 //===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements a hash set that can be used to remove duplication of
     11 // nodes in a graph.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "llvm/ADT/FoldingSet.h"
     16 #include "llvm/ADT/Hashing.h"
     17 #include "llvm/Support/Allocator.h"
     18 #include "llvm/Support/ErrorHandling.h"
     19 #include "llvm/Support/Host.h"
     20 #include "llvm/Support/MathExtras.h"
     21 #include <cassert>
     22 #include <cstring>
     23 using namespace llvm;
     24 
     25 //===----------------------------------------------------------------------===//
     26 // FoldingSetNodeIDRef Implementation
     27 
     28 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
     29 /// used to lookup the node in the FoldingSetImpl.
     30 unsigned FoldingSetNodeIDRef::ComputeHash() const {
     31   return static_cast<unsigned>(hash_combine_range(Data, Data+Size));
     32 }
     33 
     34 bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
     35   if (Size != RHS.Size) return false;
     36   return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0;
     37 }
     38 
     39 /// Used to compare the "ordering" of two nodes as defined by the
     40 /// profiled bits and their ordering defined by memcmp().
     41 bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const {
     42   if (Size != RHS.Size)
     43     return Size < RHS.Size;
     44   return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0;
     45 }
     46 
     47 //===----------------------------------------------------------------------===//
     48 // FoldingSetNodeID Implementation
     49 
     50 /// Add* - Add various data types to Bit data.
     51 ///
     52 void FoldingSetNodeID::AddPointer(const void *Ptr) {
     53   // Note: this adds pointers to the hash using sizes and endianness that
     54   // depend on the host.  It doesn't matter however, because hashing on
     55   // pointer values in inherently unstable.  Nothing  should depend on the
     56   // ordering of nodes in the folding set.
     57   Bits.append(reinterpret_cast<unsigned *>(&Ptr),
     58               reinterpret_cast<unsigned *>(&Ptr+1));
     59 }
     60 void FoldingSetNodeID::AddInteger(signed I) {
     61   Bits.push_back(I);
     62 }
     63 void FoldingSetNodeID::AddInteger(unsigned I) {
     64   Bits.push_back(I);
     65 }
     66 void FoldingSetNodeID::AddInteger(long I) {
     67   AddInteger((unsigned long)I);
     68 }
     69 void FoldingSetNodeID::AddInteger(unsigned long I) {
     70   if (sizeof(long) == sizeof(int))
     71     AddInteger(unsigned(I));
     72   else if (sizeof(long) == sizeof(long long)) {
     73     AddInteger((unsigned long long)I);
     74   } else {
     75     llvm_unreachable("unexpected sizeof(long)");
     76   }
     77 }
     78 void FoldingSetNodeID::AddInteger(long long I) {
     79   AddInteger((unsigned long long)I);
     80 }
     81 void FoldingSetNodeID::AddInteger(unsigned long long I) {
     82   AddInteger(unsigned(I));
     83   if ((uint64_t)(unsigned)I != I)
     84     Bits.push_back(unsigned(I >> 32));
     85 }
     86 
     87 void FoldingSetNodeID::AddString(StringRef String) {
     88   unsigned Size =  String.size();
     89   Bits.push_back(Size);
     90   if (!Size) return;
     91 
     92   unsigned Units = Size / 4;
     93   unsigned Pos = 0;
     94   const unsigned *Base = (const unsigned*) String.data();
     95 
     96   // If the string is aligned do a bulk transfer.
     97   if (!((intptr_t)Base & 3)) {
     98     Bits.append(Base, Base + Units);
     99     Pos = (Units + 1) * 4;
    100   } else {
    101     // Otherwise do it the hard way.
    102     // To be compatible with above bulk transfer, we need to take endianness
    103     // into account.
    104     if (sys::IsBigEndianHost) {
    105       for (Pos += 4; Pos <= Size; Pos += 4) {
    106         unsigned V = ((unsigned char)String[Pos - 4] << 24) |
    107                      ((unsigned char)String[Pos - 3] << 16) |
    108                      ((unsigned char)String[Pos - 2] << 8) |
    109                       (unsigned char)String[Pos - 1];
    110         Bits.push_back(V);
    111       }
    112     } else {
    113       assert(sys::IsLittleEndianHost && "Unexpected host endianness");
    114       for (Pos += 4; Pos <= Size; Pos += 4) {
    115         unsigned V = ((unsigned char)String[Pos - 1] << 24) |
    116                      ((unsigned char)String[Pos - 2] << 16) |
    117                      ((unsigned char)String[Pos - 3] << 8) |
    118                       (unsigned char)String[Pos - 4];
    119         Bits.push_back(V);
    120       }
    121     }
    122   }
    123 
    124   // With the leftover bits.
    125   unsigned V = 0;
    126   // Pos will have overshot size by 4 - #bytes left over.
    127   // No need to take endianness into account here - this is always executed.
    128   switch (Pos - Size) {
    129   case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru.
    130   case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru.
    131   case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break;
    132   default: return; // Nothing left.
    133   }
    134 
    135   Bits.push_back(V);
    136 }
    137 
    138 // AddNodeID - Adds the Bit data of another ID to *this.
    139 void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) {
    140   Bits.append(ID.Bits.begin(), ID.Bits.end());
    141 }
    142 
    143 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to
    144 /// lookup the node in the FoldingSetImpl.
    145 unsigned FoldingSetNodeID::ComputeHash() const {
    146   return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
    147 }
    148 
    149 /// operator== - Used to compare two nodes to each other.
    150 ///
    151 bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const {
    152   return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
    153 }
    154 
    155 /// operator== - Used to compare two nodes to each other.
    156 ///
    157 bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const {
    158   return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS;
    159 }
    160 
    161 /// Used to compare the "ordering" of two nodes as defined by the
    162 /// profiled bits and their ordering defined by memcmp().
    163 bool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const {
    164   return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
    165 }
    166 
    167 bool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const {
    168   return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS;
    169 }
    170 
    171 /// Intern - Copy this node's data to a memory region allocated from the
    172 /// given allocator and return a FoldingSetNodeIDRef describing the
    173 /// interned data.
    174 FoldingSetNodeIDRef
    175 FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const {
    176   unsigned *New = Allocator.Allocate<unsigned>(Bits.size());
    177   std::uninitialized_copy(Bits.begin(), Bits.end(), New);
    178   return FoldingSetNodeIDRef(New, Bits.size());
    179 }
    180 
    181 //===----------------------------------------------------------------------===//
    182 /// Helper functions for FoldingSetImpl.
    183 
    184 /// GetNextPtr - In order to save space, each bucket is a
    185 /// singly-linked-list. In order to make deletion more efficient, we make
    186 /// the list circular, so we can delete a node without computing its hash.
    187 /// The problem with this is that the start of the hash buckets are not
    188 /// Nodes.  If NextInBucketPtr is a bucket pointer, this method returns null:
    189 /// use GetBucketPtr when this happens.
    190 static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) {
    191   // The low bit is set if this is the pointer back to the bucket.
    192   if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1)
    193     return 0;
    194 
    195   return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr);
    196 }
    197 
    198 
    199 /// testing.
    200 static void **GetBucketPtr(void *NextInBucketPtr) {
    201   intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
    202   assert((Ptr & 1) && "Not a bucket pointer");
    203   return reinterpret_cast<void**>(Ptr & ~intptr_t(1));
    204 }
    205 
    206 /// GetBucketFor - Hash the specified node ID and return the hash bucket for
    207 /// the specified ID.
    208 static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) {
    209   // NumBuckets is always a power of 2.
    210   unsigned BucketNum = Hash & (NumBuckets-1);
    211   return Buckets + BucketNum;
    212 }
    213 
    214 /// AllocateBuckets - Allocated initialized bucket memory.
    215 static void **AllocateBuckets(unsigned NumBuckets) {
    216   void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*)));
    217   // Set the very last bucket to be a non-null "pointer".
    218   Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
    219   return Buckets;
    220 }
    221 
    222 //===----------------------------------------------------------------------===//
    223 // FoldingSetImpl Implementation
    224 
    225 FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) {
    226   assert(5 < Log2InitSize && Log2InitSize < 32 &&
    227          "Initial hash table size out of range");
    228   NumBuckets = 1 << Log2InitSize;
    229   Buckets = AllocateBuckets(NumBuckets);
    230   NumNodes = 0;
    231 }
    232 FoldingSetImpl::~FoldingSetImpl() {
    233   free(Buckets);
    234 }
    235 void FoldingSetImpl::clear() {
    236   // Set all but the last bucket to null pointers.
    237   memset(Buckets, 0, NumBuckets*sizeof(void*));
    238 
    239   // Set the very last bucket to be a non-null "pointer".
    240   Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
    241 
    242   // Reset the node count to zero.
    243   NumNodes = 0;
    244 }
    245 
    246 /// GrowHashTable - Double the size of the hash table and rehash everything.
    247 ///
    248 void FoldingSetImpl::GrowHashTable() {
    249   void **OldBuckets = Buckets;
    250   unsigned OldNumBuckets = NumBuckets;
    251   NumBuckets <<= 1;
    252 
    253   // Clear out new buckets.
    254   Buckets = AllocateBuckets(NumBuckets);
    255   NumNodes = 0;
    256 
    257   // Walk the old buckets, rehashing nodes into their new place.
    258   FoldingSetNodeID TempID;
    259   for (unsigned i = 0; i != OldNumBuckets; ++i) {
    260     void *Probe = OldBuckets[i];
    261     if (!Probe) continue;
    262     while (Node *NodeInBucket = GetNextPtr(Probe)) {
    263       // Figure out the next link, remove NodeInBucket from the old link.
    264       Probe = NodeInBucket->getNextInBucket();
    265       NodeInBucket->SetNextInBucket(0);
    266 
    267       // Insert the node into the new bucket, after recomputing the hash.
    268       InsertNode(NodeInBucket,
    269                  GetBucketFor(ComputeNodeHash(NodeInBucket, TempID),
    270                               Buckets, NumBuckets));
    271       TempID.clear();
    272     }
    273   }
    274 
    275   free(OldBuckets);
    276 }
    277 
    278 /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
    279 /// return it.  If not, return the insertion token that will make insertion
    280 /// faster.
    281 FoldingSetImpl::Node
    282 *FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
    283                                      void *&InsertPos) {
    284   unsigned IDHash = ID.ComputeHash();
    285   void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets);
    286   void *Probe = *Bucket;
    287 
    288   InsertPos = 0;
    289 
    290   FoldingSetNodeID TempID;
    291   while (Node *NodeInBucket = GetNextPtr(Probe)) {
    292     if (NodeEquals(NodeInBucket, ID, IDHash, TempID))
    293       return NodeInBucket;
    294     TempID.clear();
    295 
    296     Probe = NodeInBucket->getNextInBucket();
    297   }
    298 
    299   // Didn't find the node, return null with the bucket as the InsertPos.
    300   InsertPos = Bucket;
    301   return 0;
    302 }
    303 
    304 /// InsertNode - Insert the specified node into the folding set, knowing that it
    305 /// is not already in the map.  InsertPos must be obtained from
    306 /// FindNodeOrInsertPos.
    307 void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) {
    308   assert(N->getNextInBucket() == 0);
    309   // Do we need to grow the hashtable?
    310   if (NumNodes+1 > NumBuckets*2) {
    311     GrowHashTable();
    312     FoldingSetNodeID TempID;
    313     InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets);
    314   }
    315 
    316   ++NumNodes;
    317 
    318   /// The insert position is actually a bucket pointer.
    319   void **Bucket = static_cast<void**>(InsertPos);
    320 
    321   void *Next = *Bucket;
    322 
    323   // If this is the first insertion into this bucket, its next pointer will be
    324   // null.  Pretend as if it pointed to itself, setting the low bit to indicate
    325   // that it is a pointer to the bucket.
    326   if (Next == 0)
    327     Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1);
    328 
    329   // Set the node's next pointer, and make the bucket point to the node.
    330   N->SetNextInBucket(Next);
    331   *Bucket = N;
    332 }
    333 
    334 /// RemoveNode - Remove a node from the folding set, returning true if one was
    335 /// removed or false if the node was not in the folding set.
    336 bool FoldingSetImpl::RemoveNode(Node *N) {
    337   // Because each bucket is a circular list, we don't need to compute N's hash
    338   // to remove it.
    339   void *Ptr = N->getNextInBucket();
    340   if (Ptr == 0) return false;  // Not in folding set.
    341 
    342   --NumNodes;
    343   N->SetNextInBucket(0);
    344 
    345   // Remember what N originally pointed to, either a bucket or another node.
    346   void *NodeNextPtr = Ptr;
    347 
    348   // Chase around the list until we find the node (or bucket) which points to N.
    349   while (true) {
    350     if (Node *NodeInBucket = GetNextPtr(Ptr)) {
    351       // Advance pointer.
    352       Ptr = NodeInBucket->getNextInBucket();
    353 
    354       // We found a node that points to N, change it to point to N's next node,
    355       // removing N from the list.
    356       if (Ptr == N) {
    357         NodeInBucket->SetNextInBucket(NodeNextPtr);
    358         return true;
    359       }
    360     } else {
    361       void **Bucket = GetBucketPtr(Ptr);
    362       Ptr = *Bucket;
    363 
    364       // If we found that the bucket points to N, update the bucket to point to
    365       // whatever is next.
    366       if (Ptr == N) {
    367         *Bucket = NodeNextPtr;
    368         return true;
    369       }
    370     }
    371   }
    372 }
    373 
    374 /// GetOrInsertNode - If there is an existing simple Node exactly
    375 /// equal to the specified node, return it.  Otherwise, insert 'N' and it
    376 /// instead.
    377 FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) {
    378   FoldingSetNodeID ID;
    379   GetNodeProfile(N, ID);
    380   void *IP;
    381   if (Node *E = FindNodeOrInsertPos(ID, IP))
    382     return E;
    383   InsertNode(N, IP);
    384   return N;
    385 }
    386 
    387 //===----------------------------------------------------------------------===//
    388 // FoldingSetIteratorImpl Implementation
    389 
    390 FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) {
    391   // Skip to the first non-null non-self-cycle bucket.
    392   while (*Bucket != reinterpret_cast<void*>(-1) &&
    393          (*Bucket == 0 || GetNextPtr(*Bucket) == 0))
    394     ++Bucket;
    395 
    396   NodePtr = static_cast<FoldingSetNode*>(*Bucket);
    397 }
    398 
    399 void FoldingSetIteratorImpl::advance() {
    400   // If there is another link within this bucket, go to it.
    401   void *Probe = NodePtr->getNextInBucket();
    402 
    403   if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe))
    404     NodePtr = NextNodeInBucket;
    405   else {
    406     // Otherwise, this is the last link in this bucket.
    407     void **Bucket = GetBucketPtr(Probe);
    408 
    409     // Skip to the next non-null non-self-cycle bucket.
    410     do {
    411       ++Bucket;
    412     } while (*Bucket != reinterpret_cast<void*>(-1) &&
    413              (*Bucket == 0 || GetNextPtr(*Bucket) == 0));
    414 
    415     NodePtr = static_cast<FoldingSetNode*>(*Bucket);
    416   }
    417 }
    418 
    419 //===----------------------------------------------------------------------===//
    420 // FoldingSetBucketIteratorImpl Implementation
    421 
    422 FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) {
    423   Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket;
    424 }
    425