LCOV - code coverage report
Current view: top level - lib/Support - FoldingSet.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 175 200 87.5 %
Date: 2017-09-14 15:23:50 Functions: 28 35 80.0 %
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   147346239 : unsigned FoldingSetNodeIDRef::ComputeHash() const {
      31   294692476 :   return static_cast<unsigned>(hash_combine_range(Data, Data+Size));
      32             : }
      33             : 
      34   140793499 : bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
      35   140793499 :   if (Size != RHS.Size) return false;
      36   112319238 :   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           0 : bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const {
      42           0 :   if (Size != RHS.Size)
      43           0 :     return Size < RHS.Size;
      44           0 :   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  1074168963 : 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  1074168963 :   AddInteger(reinterpret_cast<uintptr_t>(Ptr));
      60  1074168944 : }
      61    57008372 : void FoldingSetNodeID::AddInteger(signed I) {
      62    57008372 :   Bits.push_back(I);
      63    57008372 : }
      64  2662550189 : void FoldingSetNodeID::AddInteger(unsigned I) {
      65  2662550189 :   Bits.push_back(I);
      66  2662550416 : }
      67    17920246 : void FoldingSetNodeID::AddInteger(long I) {
      68    17920246 :   AddInteger((unsigned long)I);
      69    17920246 : }
      70  1153441142 : 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  1153441142 :     AddInteger((unsigned long long)I);
      75             :   } else {
      76             :     llvm_unreachable("unexpected sizeof(long)");
      77             :   }
      78  1153441544 : }
      79           0 : void FoldingSetNodeID::AddInteger(long long I) {
      80           0 :   AddInteger((unsigned long long)I);
      81           0 : }
      82  1153441139 : void FoldingSetNodeID::AddInteger(unsigned long long I) {
      83  1153441139 :   AddInteger(unsigned(I));
      84  1153441237 :   AddInteger(unsigned(I >> 32));
      85  1153441298 : }
      86             : 
      87    22977219 : void FoldingSetNodeID::AddString(StringRef String) {
      88    22977219 :   unsigned Size =  String.size();
      89    22977219 :   Bits.push_back(Size);
      90    24351623 :   if (!Size) return;
      91             : 
      92    22964729 :   unsigned Units = Size / 4;
      93    22964729 :   unsigned Pos = 0;
      94    22964729 :   const unsigned *Base = (const unsigned*) String.data();
      95             :   
      96             :   // If the string is aligned do a bulk transfer.
      97    22964729 :   if (!((intptr_t)Base & 3)) {
      98    22756087 :     Bits.append(Base, Base + Units);
      99    22756087 :     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     1049720 :       for (Pos += 4; Pos <= Size; Pos += 4) {
     116     1261617 :         unsigned V = ((unsigned char)String[Pos - 1] << 24) |
     117     1261617 :                      ((unsigned char)String[Pos - 2] << 16) |
     118     1261617 :                      ((unsigned char)String[Pos - 3] << 8) |
     119     1261617 :                       (unsigned char)String[Pos - 4];
     120      420539 :         Bits.push_back(V);
     121             :       }
     122             :     }
     123             :   }
     124             :   
     125             :   // With the leftover bits.
     126    22964729 :   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    22964729 :   switch (Pos - Size) {
     130     9022922 :   case 1: V = (V << 8) | (unsigned char)String[Size - 3]; LLVM_FALLTHROUGH;
     131    19431194 :   case 2: V = (V << 8) | (unsigned char)String[Size - 2]; LLVM_FALLTHROUGH;
     132    43205630 :   case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break;
     133             :   default: return; // Nothing left.
     134             :   }
     135             : 
     136    21602815 :   Bits.push_back(V);
     137             : }
     138             : 
     139             : // AddNodeID - Adds the Bit data of another ID to *this.
     140      370947 : void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) {
     141     1112841 :   Bits.append(ID.Bits.begin(), ID.Bits.end());
     142      370947 : }
     143             : 
     144             : /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to 
     145             : /// lookup the node in the FoldingSetBase.
     146   147019322 : unsigned FoldingSetNodeID::ComputeHash() const {
     147   588077288 :   return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
     148             : }
     149             : 
     150             : /// operator== - Used to compare two nodes to each other.
     151             : ///
     152   129209616 : bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const {
     153   516838464 :   return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
     154             : }
     155             : 
     156             : /// operator== - Used to compare two nodes to each other.
     157             : ///
     158   140793500 : bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const {
     159   563174000 :   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           0 : bool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const {
     165           0 :   return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
     166             : }
     167             : 
     168           0 : bool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const {
     169           0 :   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      919710 : FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const {
     177     2759130 :   unsigned *New = Allocator.Allocate<unsigned>(Bits.size());
     178     3678840 :   std::uninitialized_copy(Bits.begin(), Bits.end(), New);
     179     1839420 :   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   243098873 :   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    18380038 :   intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
     203             :   assert((Ptr & 1) && "Not a bucket pointer");
     204    18380038 :   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   142497425 :   unsigned BucketNum = Hash & (NumBuckets-1);
     212   142497425 :   return Buckets + BucketNum;
     213             : }
     214             : 
     215             : /// AllocateBuckets - Allocated initialized bucket memory.
     216     2434223 : static void **AllocateBuckets(unsigned NumBuckets) {
     217     2434223 :   void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*)));
     218             : 
     219     2434223 :   if (Buckets == nullptr)
     220           0 :     report_bad_alloc_error("Allocation of Buckets failed.");
     221             :   
     222             :   // Set the very last bucket to be a non-null "pointer".
     223     2434223 :   Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
     224     2434223 :   return Buckets;
     225             : }
     226             : 
     227             : //===----------------------------------------------------------------------===//
     228             : // FoldingSetBase Implementation
     229             : 
     230           0 : void FoldingSetBase::anchor() {}
     231             : 
     232     2411673 : FoldingSetBase::FoldingSetBase(unsigned Log2InitSize) {
     233             :   assert(5 < Log2InitSize && Log2InitSize < 32 &&
     234             :          "Initial hash table size out of range");
     235     2411673 :   NumBuckets = 1 << Log2InitSize;
     236     2411673 :   Buckets = AllocateBuckets(NumBuckets);
     237     2411676 :   NumNodes = 0;
     238     2411676 : }
     239             : 
     240        2260 : FoldingSetBase::FoldingSetBase(FoldingSetBase &&Arg)
     241        2260 :     : Buckets(Arg.Buckets), NumBuckets(Arg.NumBuckets), NumNodes(Arg.NumNodes) {
     242        2260 :   Arg.Buckets = nullptr;
     243        2260 :   Arg.NumBuckets = 0;
     244        2260 :   Arg.NumNodes = 0;
     245        2260 : }
     246             : 
     247           0 : FoldingSetBase &FoldingSetBase::operator=(FoldingSetBase &&RHS) {
     248           0 :   free(Buckets); // This may be null if the set is in a moved-from state.
     249           0 :   Buckets = RHS.Buckets;
     250           0 :   NumBuckets = RHS.NumBuckets;
     251           0 :   NumNodes = RHS.NumNodes;
     252           0 :   RHS.Buckets = nullptr;
     253           0 :   RHS.NumBuckets = 0;
     254           0 :   RHS.NumNodes = 0;
     255           0 :   return *this;
     256             : }
     257             : 
     258     4458486 : FoldingSetBase::~FoldingSetBase() {
     259     2229243 :   free(Buckets);
     260     2229243 : }
     261             : 
     262      281212 : void FoldingSetBase::clear() {
     263             :   // Set all but the last bucket to null pointers.
     264      281212 :   memset(Buckets, 0, NumBuckets*sizeof(void*));
     265             : 
     266             :   // Set the very last bucket to be a non-null "pointer".
     267      281212 :   Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
     268             : 
     269             :   // Reset the node count to zero.
     270      281212 :   NumNodes = 0;
     271      281212 : }
     272             : 
     273       22549 : void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount) {
     274             :   assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount");
     275             :   assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!");
     276       22549 :   void **OldBuckets = Buckets;
     277       22549 :   unsigned OldNumBuckets = NumBuckets;
     278             :   
     279             :   // Clear out new buckets.
     280       22549 :   Buckets = AllocateBuckets(NewBucketCount);
     281             :   // Set NumBuckets only if allocation of new buckets was succesful
     282       22549 :   NumBuckets = NewBucketCount; 
     283       22549 :   NumNodes = 0;
     284             : 
     285             :   // Walk the old buckets, rehashing nodes into their new place.
     286       45098 :   FoldingSetNodeID TempID;
     287    10147989 :   for (unsigned i = 0; i != OldNumBuckets; ++i) {
     288    10125440 :     void *Probe = OldBuckets[i];
     289    10125440 :     if (!Probe) continue;
     290    19382042 :     while (Node *NodeInBucket = GetNextPtr(Probe)) {
     291             :       // Figure out the next link, remove NodeInBucket from the old link.
     292    19382042 :       Probe = NodeInBucket->getNextInBucket();
     293    19382042 :       NodeInBucket->SetNextInBucket(nullptr);
     294             : 
     295             :       // Insert the node into the new bucket, after recomputing the hash.
     296    19382042 :       InsertNode(NodeInBucket,
     297    38764084 :                  GetBucketFor(ComputeNodeHash(NodeInBucket, TempID),
     298             :                               Buckets, NumBuckets));
     299             :       TempID.clear();
     300             :     }
     301             :   }
     302             :   
     303       22549 :   free(OldBuckets);
     304       22549 : }
     305             : 
     306             : /// GrowHashTable - Double the size of the hash table and rehash everything.
     307             : ///
     308       15707 : void FoldingSetBase::GrowHashTable() {
     309       15707 :   GrowBucketCount(NumBuckets * 2);
     310       15707 : }
     311             : 
     312        6850 : void FoldingSetBase::reserve(unsigned EltCount) {
     313             :   // This will give us somewhere between EltCount / 2 and
     314             :   // EltCount buckets.  This puts us in the load factor
     315             :   // range of 1.0 - 2.0.
     316       13700 :   if(EltCount < capacity())
     317             :     return;
     318       13684 :   GrowBucketCount(PowerOf2Floor(EltCount));
     319             : }
     320             : 
     321             : /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
     322             : /// return it.  If not, return the insertion token that will make insertion
     323             : /// faster.
     324             : FoldingSetBase::Node *
     325   123099679 : FoldingSetBase::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
     326             :                                     void *&InsertPos) {
     327   123099679 :   unsigned IDHash = ID.ComputeHash();
     328   246199352 :   void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets);
     329   123099676 :   void *Probe = *Bucket;
     330             :   
     331   123099676 :   InsertPos = nullptr;
     332             :   
     333   123099678 :   FoldingSetNodeID TempID;
     334   162935522 :   while (Node *NodeInBucket = GetNextPtr(Probe)) {
     335   141316647 :     if (NodeEquals(NodeInBucket, ID, IDHash, TempID))
     336             :       return NodeInBucket;
     337    64499545 :     TempID.clear();
     338             : 
     339    64499545 :     Probe = NodeInBucket->getNextInBucket();
     340    64499545 :   }
     341             :   
     342             :   // Didn't find the node, return null with the bucket as the InsertPos.
     343    46282574 :   InsertPos = Bucket;
     344    46282574 :   return nullptr;
     345             : }
     346             : 
     347             : /// InsertNode - Insert the specified node into the folding set, knowing that it
     348             : /// is not already in the map.  InsertPos must be obtained from 
     349             : /// FindNodeOrInsertPos.
     350    61980330 : void FoldingSetBase::InsertNode(Node *N, void *InsertPos) {
     351             :   assert(!N->getNextInBucket());
     352             :   // Do we need to grow the hashtable?
     353   123960660 :   if (NumNodes+1 > capacity()) {
     354       15707 :     GrowHashTable();
     355       31414 :     FoldingSetNodeID TempID;
     356       31414 :     InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets);
     357             :   }
     358             : 
     359    61980330 :   ++NumNodes;
     360             :   
     361             :   /// The insert position is actually a bucket pointer.
     362    61980330 :   void **Bucket = static_cast<void**>(InsertPos);
     363             :   
     364    61980330 :   void *Next = *Bucket;
     365             :   
     366             :   // If this is the first insertion into this bucket, its next pointer will be
     367             :   // null.  Pretend as if it pointed to itself, setting the low bit to indicate
     368             :   // that it is a pointer to the bucket.
     369    61980330 :   if (!Next)
     370    32618680 :     Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1);
     371             : 
     372             :   // Set the node's next pointer, and make the bucket point to the node.
     373    61980330 :   N->SetNextInBucket(Next);
     374    61980330 :   *Bucket = N;
     375    61980330 : }
     376             : 
     377             : /// RemoveNode - Remove a node from the folding set, returning true if one was
     378             : /// removed or false if the node was not in the folding set.
     379    19254575 : bool FoldingSetBase::RemoveNode(Node *N) {
     380             :   // Because each bucket is a circular list, we don't need to compute N's hash
     381             :   // to remove it.
     382    19254575 :   void *Ptr = N->getNextInBucket();
     383    19254575 :   if (!Ptr) return false;  // Not in folding set.
     384             : 
     385    17918163 :   --NumNodes;
     386    17918163 :   N->SetNextInBucket(nullptr);
     387             : 
     388             :   // Remember what N originally pointed to, either a bucket or another node.
     389    17918163 :   void *NodeNextPtr = Ptr;
     390             :   
     391             :   // Chase around the list until we find the node (or bucket) which points to N.
     392             :   while (true) {
     393     8791319 :     if (Node *NodeInBucket = GetNextPtr(Ptr)) {
     394             :       // Advance pointer.
     395     8791319 :       Ptr = NodeInBucket->getNextInBucket();
     396             :       
     397             :       // We found a node that points to N, change it to point to N's next node,
     398             :       // removing N from the list.
     399     8791319 :       if (Ptr == N) {
     400     2626853 :         NodeInBucket->SetNextInBucket(NodeNextPtr);
     401     2626853 :         return true;
     402             :       }
     403             :     } else {
     404    17918163 :       void **Bucket = GetBucketPtr(Ptr);
     405    17918163 :       Ptr = *Bucket;
     406             :       
     407             :       // If we found that the bucket points to N, update the bucket to point to
     408             :       // whatever is next.
     409    17918163 :       if (Ptr == N) {
     410    15291310 :         *Bucket = NodeNextPtr;
     411    15291310 :         return true;
     412             :       }
     413             :     }
     414             :   }
     415             : }
     416             : 
     417             : /// GetOrInsertNode - If there is an existing simple Node exactly
     418             : /// equal to the specified node, return it.  Otherwise, insert 'N' and it
     419             : /// instead.
     420     5385822 : FoldingSetBase::Node *FoldingSetBase::GetOrInsertNode(FoldingSetBase::Node *N) {
     421    10771644 :   FoldingSetNodeID ID;
     422     5385822 :   GetNodeProfile(N, ID);
     423             :   void *IP;
     424     5385822 :   if (Node *E = FindNodeOrInsertPos(ID, IP))
     425             :     return E;
     426     5368361 :   InsertNode(N, IP);
     427     5368361 :   return N;
     428             : }
     429             : 
     430             : //===----------------------------------------------------------------------===//
     431             : // FoldingSetIteratorImpl Implementation
     432             : 
     433      252579 : FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) {
     434             :   // Skip to the first non-null non-self-cycle bucket.
     435    10751867 :   while (*Bucket != reinterpret_cast<void*>(-1) &&
     436       89301 :          (!*Bucket || !GetNextPtr(*Bucket)))
     437     5249644 :     ++Bucket;
     438             :   
     439      252579 :   NodePtr = static_cast<FoldingSetNode*>(*Bucket);
     440      252579 : }
     441             : 
     442      510421 : void FoldingSetIteratorImpl::advance() {
     443             :   // If there is another link within this bucket, go to it.
     444     1020842 :   void *Probe = NodePtr->getNextInBucket();
     445             : 
     446       48546 :   if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe))
     447       48546 :     NodePtr = NextNodeInBucket;
     448             :   else {
     449             :     // Otherwise, this is the last link in this bucket.  
     450      461875 :     void **Bucket = GetBucketPtr(Probe);
     451             : 
     452             :     // Skip to the next non-null non-self-cycle bucket.
     453             :     do {
     454    42671577 :       ++Bucket;
     455    42671577 :     } while (*Bucket != reinterpret_cast<void*>(-1) &&
     456      372572 :              (!*Bucket || !GetNextPtr(*Bucket)));
     457             :     
     458      461875 :     NodePtr = static_cast<FoldingSetNode*>(*Bucket);
     459             :   }
     460      510421 : }
     461             : 
     462             : //===----------------------------------------------------------------------===//
     463             : // FoldingSetBucketIteratorImpl Implementation
     464             : 
     465           0 : FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) {
     466           0 :   Ptr = (!*Bucket || !GetNextPtr(*Bucket)) ? (void*) Bucket : *Bucket;
     467           0 : }

Generated by: LCOV version 1.13