LCOV - code coverage report
Current view: top level - lib/Support - FoldingSet.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 162 178 91.0 %
Date: 2018-09-23 13:06:45 Functions: 30 34 88.2 %
Legend: Lines: hit not hit

          Line data    Source code
       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 FoldingSetBase.
      30  1344756626 : unsigned FoldingSetNodeIDRef::ComputeHash() const {
      31  1344756626 :   return static_cast<unsigned>(hash_combine_range(Data, Data+Size));
      32             : }
      33             : 
      34  1301705522 : bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
      35  1301705522 :   if (Size != RHS.Size) return false;
      36  1110410529 :   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         274 : bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const {
      42         274 :   if (Size != RHS.Size)
      43         149 :     return Size < RHS.Size;
      44         125 :   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  4956998663 : 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 is inherently unstable. Nothing should depend on the
      56             :   // ordering of nodes in the folding set.
      57             :   static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),
      58             :                 "unexpected pointer size");
      59  4956998663 :   AddInteger(reinterpret_cast<uintptr_t>(Ptr));
      60  4956998656 : }
      61  1065711164 : void FoldingSetNodeID::AddInteger(signed I) {
      62  1065711164 :   Bits.push_back(I);
      63  1065711164 : }
      64 13075760820 : void FoldingSetNodeID::AddInteger(unsigned I) {
      65 13075760820 :   Bits.push_back(I);
      66 13075761804 : }
      67    67490916 : void FoldingSetNodeID::AddInteger(long I) {
      68    67490916 :   AddInteger((unsigned long)I);
      69    67490917 : }
      70  5249163894 : void FoldingSetNodeID::AddInteger(unsigned long I) {
      71             :   if (sizeof(long) == sizeof(int))
      72             :     AddInteger(unsigned(I));
      73             :   else if (sizeof(long) == sizeof(long long)) {
      74  5249163894 :     AddInteger((unsigned long long)I);
      75             :   } else {
      76             :     llvm_unreachable("unexpected sizeof(long)");
      77             :   }
      78  5249164617 : }
      79           0 : void FoldingSetNodeID::AddInteger(long long I) {
      80           0 :   AddInteger((unsigned long long)I);
      81           0 : }
      82  5249168492 : void FoldingSetNodeID::AddInteger(unsigned long long I) {
      83  5249168492 :   AddInteger(unsigned(I));
      84  5249168823 :   AddInteger(unsigned(I >> 32));
      85  5249168954 : }
      86             : 
      87   304859085 : void FoldingSetNodeID::AddString(StringRef String) {
      88   304859085 :   unsigned Size =  String.size();
      89   304859085 :   Bits.push_back(Size);
      90   325888222 :   if (!Size) return;
      91             : 
      92   304846346 :   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   304846346 :   if (!((intptr_t)Base & 3)) {
      98   303974027 :     Bits.append(Base, Base + Units);
      99   303974027 :     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             :     static_assert(sys::IsBigEndianHost || sys::IsLittleEndianHost,
     105             :                   "Unexpected host endianness");
     106             :     if (sys::IsBigEndianHost) {
     107             :       for (Pos += 4; Pos <= Size; Pos += 4) {
     108             :         unsigned V = ((unsigned char)String[Pos - 4] << 24) |
     109             :                      ((unsigned char)String[Pos - 3] << 16) |
     110             :                      ((unsigned char)String[Pos - 2] << 8) |
     111             :                       (unsigned char)String[Pos - 1];
     112             :         Bits.push_back(V);
     113             :       }
     114             :     } else {  // Little-endian host
     115     3529897 :       for (Pos += 4; Pos <= Size; Pos += 4) {
     116     2657578 :         unsigned V = ((unsigned char)String[Pos - 1] << 24) |
     117     2657578 :                      ((unsigned char)String[Pos - 2] << 16) |
     118     2657578 :                      ((unsigned char)String[Pos - 3] << 8) |
     119     2657578 :                       (unsigned char)String[Pos - 4];
     120     2657578 :         Bits.push_back(V);
     121             :       }
     122             :     }
     123             :   }
     124             : 
     125             :   // With the leftover bits.
     126   304846346 :   unsigned V = 0;
     127             :   // Pos will have overshot size by 4 - #bytes left over.
     128             :   // No need to take endianness into account here - this is always executed.
     129   304846346 :   switch (Pos - Size) {
     130   107683390 :   case 1: V = (V << 8) | (unsigned char)String[Size - 3]; LLVM_FALLTHROUGH;
     131   279039550 :   case 2: V = (V << 8) | (unsigned char)String[Size - 2]; LLVM_FALLTHROUGH;
     132   283817209 :   case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break;
     133             :   default: return; // Nothing left.
     134             :   }
     135             : 
     136   283817209 :   Bits.push_back(V);
     137             : }
     138             : 
     139             : // AddNodeID - Adds the Bit data of another ID to *this.
     140    10190963 : void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) {
     141    20381926 :   Bits.append(ID.Bits.begin(), ID.Bits.end());
     142    10190963 : }
     143             : 
     144             : /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to
     145             : /// lookup the node in the FoldingSetBase.
     146  1344142052 : unsigned FoldingSetNodeID::ComputeHash() const {
     147  4032426156 :   return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
     148             : }
     149             : 
     150             : /// operator== - Used to compare two nodes to each other.
     151             : ///
     152  1267985064 : bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const {
     153  3803955192 :   return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
     154             : }
     155             : 
     156             : /// operator== - Used to compare two nodes to each other.
     157             : ///
     158  1301705523 : bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const {
     159  3905116569 :   return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS;
     160             : }
     161             : 
     162             : /// Used to compare the "ordering" of two nodes as defined by the
     163             : /// profiled bits and their ordering defined by memcmp().
     164         274 : bool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const {
     165         822 :   return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
     166             : }
     167             : 
     168         274 : bool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const {
     169         822 :   return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS;
     170             : }
     171             : 
     172             : /// Intern - Copy this node's data to a memory region allocated from the
     173             : /// given allocator and return a FoldingSetNodeIDRef describing the
     174             : /// interned data.
     175             : FoldingSetNodeIDRef
     176     1496237 : FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const {
     177     1496237 :   unsigned *New = Allocator.Allocate<unsigned>(Bits.size());
     178             :   std::uninitialized_copy(Bits.begin(), Bits.end(), New);
     179     1496237 :   return FoldingSetNodeIDRef(New, Bits.size());
     180             : }
     181             : 
     182             : //===----------------------------------------------------------------------===//
     183             : /// Helper functions for FoldingSetBase.
     184             : 
     185             : /// GetNextPtr - In order to save space, each bucket is a
     186             : /// singly-linked-list. In order to make deletion more efficient, we make
     187             : /// the list circular, so we can delete a node without computing its hash.
     188             : /// The problem with this is that the start of the hash buckets are not
     189             : /// Nodes.  If NextInBucketPtr is a bucket pointer, this method returns null:
     190             : /// use GetBucketPtr when this happens.
     191             : static FoldingSetBase::Node *GetNextPtr(void *NextInBucketPtr) {
     192             :   // The low bit is set if this is the pointer back to the bucket.
     193  2188763190 :   if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1)
     194             :     return nullptr;
     195             : 
     196             :   return static_cast<FoldingSetBase::Node*>(NextInBucketPtr);
     197             : }
     198             : 
     199             : 
     200             : /// testing.
     201             : static void **GetBucketPtr(void *NextInBucketPtr) {
     202             :   intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
     203             :   assert((Ptr & 1) && "Not a bucket pointer");
     204     1098489 :   return reinterpret_cast<void**>(Ptr & ~intptr_t(1));
     205             : }
     206             : 
     207             : /// GetBucketFor - Hash the specified node ID and return the hash bucket for
     208             : /// the specified ID.
     209             : static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) {
     210             :   // NumBuckets is always a power of 2.
     211  1324861428 :   unsigned BucketNum = Hash & (NumBuckets-1);
     212      343104 :   return Buckets + BucketNum;
     213             : }
     214             : 
     215             : /// AllocateBuckets - Allocated initialized bucket memory.
     216             : static void **AllocateBuckets(unsigned NumBuckets) {
     217    11820093 :   void **Buckets = static_cast<void**>(safe_calloc(NumBuckets + 1,
     218             :                                                    sizeof(void*)));
     219             :   // Set the very last bucket to be a non-null "pointer".
     220    11820086 :   Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
     221             :   return Buckets;
     222             : }
     223             : 
     224             : //===----------------------------------------------------------------------===//
     225             : // FoldingSetBase Implementation
     226             : 
     227           0 : void FoldingSetBase::anchor() {}
     228             : 
     229    11467233 : FoldingSetBase::FoldingSetBase(unsigned Log2InitSize) {
     230             :   assert(5 < Log2InitSize && Log2InitSize < 32 &&
     231             :          "Initial hash table size out of range");
     232    11467233 :   NumBuckets = 1 << Log2InitSize;
     233    11467226 :   Buckets = AllocateBuckets(NumBuckets);
     234    11467226 :   NumNodes = 0;
     235    11467226 : }
     236             : 
     237        3588 : FoldingSetBase::FoldingSetBase(FoldingSetBase &&Arg)
     238        3588 :     : Buckets(Arg.Buckets), NumBuckets(Arg.NumBuckets), NumNodes(Arg.NumNodes) {
     239        3588 :   Arg.Buckets = nullptr;
     240        3588 :   Arg.NumBuckets = 0;
     241        3588 :   Arg.NumNodes = 0;
     242        3588 : }
     243             : 
     244           0 : FoldingSetBase &FoldingSetBase::operator=(FoldingSetBase &&RHS) {
     245           0 :   free(Buckets); // This may be null if the set is in a moved-from state.
     246           0 :   Buckets = RHS.Buckets;
     247           0 :   NumBuckets = RHS.NumBuckets;
     248           0 :   NumNodes = RHS.NumNodes;
     249           0 :   RHS.Buckets = nullptr;
     250           0 :   RHS.NumBuckets = 0;
     251           0 :   RHS.NumNodes = 0;
     252           0 :   return *this;
     253             : }
     254             : 
     255     6765888 : FoldingSetBase::~FoldingSetBase() {
     256     3382944 :   free(Buckets);
     257     3382944 : }
     258             : 
     259     1285082 : void FoldingSetBase::clear() {
     260             :   // Set all but the last bucket to null pointers.
     261     1285082 :   memset(Buckets, 0, NumBuckets*sizeof(void*));
     262             : 
     263             :   // Set the very last bucket to be a non-null "pointer".
     264     1285082 :   Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
     265             : 
     266             :   // Reset the node count to zero.
     267     1285082 :   NumNodes = 0;
     268     1285082 : }
     269             : 
     270      352860 : void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount) {
     271             :   assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount");
     272             :   assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!");
     273      352860 :   void **OldBuckets = Buckets;
     274      352860 :   unsigned OldNumBuckets = NumBuckets;
     275             : 
     276             :   // Clear out new buckets.
     277      352860 :   Buckets = AllocateBuckets(NewBucketCount);
     278             :   // Set NumBuckets only if allocation of new buckets was successful.
     279      352860 :   NumBuckets = NewBucketCount;
     280      352860 :   NumNodes = 0;
     281             : 
     282             :   // Walk the old buckets, rehashing nodes into their new place.
     283             :   FoldingSetNodeID TempID;
     284   152110812 :   for (unsigned i = 0; i != OldNumBuckets; ++i) {
     285   151757952 :     void *Probe = OldBuckets[i];
     286   151757952 :     if (!Probe) continue;
     287   302276993 :     while (Node *NodeInBucket = GetNextPtr(Probe)) {
     288             :       // Figure out the next link, remove NodeInBucket from the old link.
     289   302276993 :       Probe = NodeInBucket->getNextInBucket();
     290             :       NodeInBucket->SetNextInBucket(nullptr);
     291             : 
     292             :       // Insert the node into the new bucket, after recomputing the hash.
     293   302276993 :       InsertNode(NodeInBucket,
     294   302276993 :                  GetBucketFor(ComputeNodeHash(NodeInBucket, TempID),
     295             :                               Buckets, NumBuckets));
     296             :       TempID.clear();
     297             :     }
     298             :   }
     299             : 
     300      352860 :   free(OldBuckets);
     301      352860 : }
     302             : 
     303             : /// GrowHashTable - Double the size of the hash table and rehash everything.
     304             : ///
     305      343104 : void FoldingSetBase::GrowHashTable() {
     306      343104 :   GrowBucketCount(NumBuckets * 2);
     307      343104 : }
     308             : 
     309        9764 : void FoldingSetBase::reserve(unsigned EltCount) {
     310             :   // This will give us somewhere between EltCount / 2 and
     311             :   // EltCount buckets.  This puts us in the load factor
     312             :   // range of 1.0 - 2.0.
     313       19528 :   if(EltCount < capacity())
     314             :     return;
     315       19512 :   GrowBucketCount(PowerOf2Floor(EltCount));
     316             : }
     317             : 
     318             : /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
     319             : /// return it.  If not, return the insertion token that will make insertion
     320             : /// faster.
     321             : FoldingSetBase::Node *
     322  1022241336 : FoldingSetBase::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
     323             :                                     void *&InsertPos) {
     324  1022241336 :   unsigned IDHash = ID.ComputeHash();
     325  1022241331 :   void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets);
     326  1022241331 :   void *Probe = *Bucket;
     327             : 
     328  1022241331 :   InsertPos = nullptr;
     329             : 
     330             :   FoldingSetNodeID TempID;
     331  1443241337 :   while (Node *NodeInBucket = GetNextPtr(Probe)) {
     332  1302531931 :     if (NodeEquals(NodeInBucket, ID, IDHash, TempID))
     333   629482664 :       return NodeInBucket;
     334             :     TempID.clear();
     335             : 
     336   673049275 :     Probe = NodeInBucket->getNextInBucket();
     337   673049275 :   }
     338             : 
     339             :   // Didn't find the node, return null with the bucket as the InsertPos.
     340   392758675 :   InsertPos = Bucket;
     341   392758675 :   return nullptr;
     342             : }
     343             : 
     344             : /// InsertNode - Insert the specified node into the folding set, knowing that it
     345             : /// is not already in the map.  InsertPos must be obtained from
     346             : /// FindNodeOrInsertPos.
     347   612404808 : void FoldingSetBase::InsertNode(Node *N, void *InsertPos) {
     348             :   assert(!N->getNextInBucket());
     349             :   // Do we need to grow the hashtable?
     350  1224809616 :   if (NumNodes+1 > capacity()) {
     351      343104 :     GrowHashTable();
     352             :     FoldingSetNodeID TempID;
     353      343104 :     InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets);
     354             :   }
     355             : 
     356   612404808 :   ++NumNodes;
     357             : 
     358             :   /// The insert position is actually a bucket pointer.
     359             :   void **Bucket = static_cast<void**>(InsertPos);
     360             : 
     361   612404808 :   void *Next = *Bucket;
     362             : 
     363             :   // If this is the first insertion into this bucket, its next pointer will be
     364             :   // null.  Pretend as if it pointed to itself, setting the low bit to indicate
     365             :   // that it is a pointer to the bucket.
     366   612404808 :   if (!Next)
     367   308553751 :     Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1);
     368             : 
     369             :   // Set the node's next pointer, and make the bucket point to the node.
     370             :   N->SetNextInBucket(Next);
     371   612404808 :   *Bucket = N;
     372   612404808 : }
     373             : 
     374             : /// RemoveNode - Remove a node from the folding set, returning true if one was
     375             : /// removed or false if the node was not in the folding set.
     376    44813678 : bool FoldingSetBase::RemoveNode(Node *N) {
     377             :   // Because each bucket is a circular list, we don't need to compute N's hash
     378             :   // to remove it.
     379    44813678 :   void *Ptr = N->getNextInBucket();
     380    44813678 :   if (!Ptr) return false;  // Not in folding set.
     381             : 
     382    39149002 :   --NumNodes;
     383             :   N->SetNextInBucket(nullptr);
     384             : 
     385             :   // Remember what N originally pointed to, either a bucket or another node.
     386             :   void *NodeNextPtr = Ptr;
     387             : 
     388             :   // Chase around the list until we find the node (or bucket) which points to N.
     389             :   while (true) {
     390    20196338 :     if (Node *NodeInBucket = GetNextPtr(Ptr)) {
     391             :       // Advance pointer.
     392    20196338 :       Ptr = NodeInBucket->getNextInBucket();
     393             : 
     394             :       // We found a node that points to N, change it to point to N's next node,
     395             :       // removing N from the list.
     396    20196338 :       if (Ptr == N) {
     397             :         NodeInBucket->SetNextInBucket(NodeNextPtr);
     398     7356661 :         return true;
     399             :       }
     400             :     } else {
     401             :       void **Bucket = GetBucketPtr(Ptr);
     402    39149001 :       Ptr = *Bucket;
     403             : 
     404             :       // If we found that the bucket points to N, update the bucket to point to
     405             :       // whatever is next.
     406    39149001 :       if (Ptr == N) {
     407    31792341 :         *Bucket = NodeNextPtr;
     408    31792341 :         return true;
     409             :       }
     410             :     }
     411             :   }
     412             : }
     413             : 
     414             : /// GetOrInsertNode - If there is an existing simple Node exactly
     415             : /// equal to the specified node, return it.  Otherwise, insert 'N' and it
     416             : /// instead.
     417    11088072 : FoldingSetBase::Node *FoldingSetBase::GetOrInsertNode(FoldingSetBase::Node *N) {
     418             :   FoldingSetNodeID ID;
     419    11088072 :   GetNodeProfile(N, ID);
     420             :   void *IP;
     421    11088072 :   if (Node *E = FindNodeOrInsertPos(ID, IP))
     422             :     return E;
     423    11010631 :   InsertNode(N, IP);
     424    11010631 :   return N;
     425             : }
     426             : 
     427             : //===----------------------------------------------------------------------===//
     428             : // FoldingSetIteratorImpl Implementation
     429             : 
     430      553952 : FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) {
     431             :   // Skip to the first non-null non-self-cycle bucket.
     432    13488199 :   while (*Bucket != reinterpret_cast<void*>(-1) &&
     433             :          (!*Bucket || !GetNextPtr(*Bucket)))
     434    12934247 :     ++Bucket;
     435             : 
     436      553952 :   NodePtr = static_cast<FoldingSetNode*>(*Bucket);
     437      553952 : }
     438             : 
     439     1453263 : void FoldingSetIteratorImpl::advance() {
     440             :   // If there is another link within this bucket, go to it.
     441     1453263 :   void *Probe = NodePtr->getNextInBucket();
     442             : 
     443      354777 :   if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe))
     444      354774 :     NodePtr = NextNodeInBucket;
     445             :   else {
     446             :     // Otherwise, this is the last link in this bucket.
     447             :     void **Bucket = GetBucketPtr(Probe);
     448             : 
     449             :     // Skip to the next non-null non-self-cycle bucket.
     450             :     do {
     451    48155851 :       ++Bucket;
     452    48155851 :     } while (*Bucket != reinterpret_cast<void*>(-1) &&
     453             :              (!*Bucket || !GetNextPtr(*Bucket)));
     454             : 
     455     1098489 :     NodePtr = static_cast<FoldingSetNode*>(*Bucket);
     456             :   }
     457     1453263 : }
     458             : 
     459             : //===----------------------------------------------------------------------===//
     460             : // FoldingSetBucketIteratorImpl Implementation
     461             : 
     462           0 : FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) {
     463           0 :   Ptr = (!*Bucket || !GetNextPtr(*Bucket)) ? (void*) Bucket : *Bucket;
     464           0 : }

Generated by: LCOV version 1.13