Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Support/FoldingSet.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements a hash set that can be used to remove duplication of
10
// nodes in a graph.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/ADT/FoldingSet.h"
15
#include "llvm/ADT/Hashing.h"
16
#include "llvm/Support/Allocator.h"
17
#include "llvm/Support/ErrorHandling.h"
18
#include "llvm/Support/Host.h"
19
#include "llvm/Support/MathExtras.h"
20
#include <cassert>
21
#include <cstring>
22
using namespace llvm;
23
24
//===----------------------------------------------------------------------===//
25
// FoldingSetNodeIDRef Implementation
26
27
/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
28
/// used to lookup the node in the FoldingSetBase.
29
612M
unsigned FoldingSetNodeIDRef::ComputeHash() const {
30
612M
  return static_cast<unsigned>(hash_combine_range(Data, Data+Size));
31
612M
}
32
33
652M
bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
34
652M
  if (Size != RHS.Size) 
return false147M
;
35
504M
  return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0;
36
504M
}
37
38
/// Used to compare the "ordering" of two nodes as defined by the
39
/// profiled bits and their ordering defined by memcmp().
40
216
bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const {
41
216
  if (Size != RHS.Size)
42
111
    return Size < RHS.Size;
43
105
  return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0;
44
105
}
45
46
//===----------------------------------------------------------------------===//
47
// FoldingSetNodeID Implementation
48
49
/// Add* - Add various data types to Bit data.
50
///
51
2.59G
void FoldingSetNodeID::AddPointer(const void *Ptr) {
52
2.59G
  // Note: this adds pointers to the hash using sizes and endianness that
53
2.59G
  // depend on the host. It doesn't matter, however, because hashing on
54
2.59G
  // pointer values is inherently unstable. Nothing should depend on the
55
2.59G
  // ordering of nodes in the folding set.
56
2.59G
  static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),
57
2.59G
                "unexpected pointer size");
58
2.59G
  AddInteger(reinterpret_cast<uintptr_t>(Ptr));
59
2.59G
}
60
369M
void FoldingSetNodeID::AddInteger(signed I) {
61
369M
  Bits.push_back(I);
62
369M
}
63
6.57G
void FoldingSetNodeID::AddInteger(unsigned I) {
64
6.57G
  Bits.push_back(I);
65
6.57G
}
66
33.2M
void FoldingSetNodeID::AddInteger(long I) {
67
33.2M
  AddInteger((unsigned long)I);
68
33.2M
}
69
2.78G
void FoldingSetNodeID::AddInteger(unsigned long I) {
70
2.78G
  if (sizeof(long) == sizeof(int))
71
0
    AddInteger(unsigned(I));
72
2.78G
  else 
if (2.78G
sizeof(long) == sizeof(long long)2.78G
) {
73
2.78G
    AddInteger((unsigned long long)I);
74
18.4E
  } else {
75
18.4E
    llvm_unreachable("unexpected sizeof(long)");
76
18.4E
  }
77
2.78G
}
78
2.99M
void FoldingSetNodeID::AddInteger(long long I) {
79
2.99M
  AddInteger((unsigned long long)I);
80
2.99M
}
81
2.83G
void FoldingSetNodeID::AddInteger(unsigned long long I) {
82
2.83G
  AddInteger(unsigned(I));
83
2.83G
  AddInteger(unsigned(I >> 32));
84
2.83G
}
85
86
168M
void FoldingSetNodeID::AddString(StringRef String) {
87
168M
  unsigned Size =  String.size();
88
168M
  Bits.push_back(Size);
89
168M
  if (!Size) 
return12.7k
;
90
168M
91
168M
  unsigned Units = Size / 4;
92
168M
  unsigned Pos = 0;
93
168M
  const unsigned *Base = (const unsigned*) String.data();
94
168M
95
168M
  // If the string is aligned do a bulk transfer.
96
168M
  if (!((intptr_t)Base & 3)) {
97
23.9M
    Bits.append(Base, Base + Units);
98
23.9M
    Pos = (Units + 1) * 4;
99
145M
  } else {
100
145M
    // Otherwise do it the hard way.
101
145M
    // To be compatible with above bulk transfer, we need to take endianness
102
145M
    // into account.
103
145M
    static_assert(sys::IsBigEndianHost || sys::IsLittleEndianHost,
104
145M
                  "Unexpected host endianness");
105
145M
    if (sys::IsBigEndianHost) {
106
0
      for (Pos += 4; Pos <= Size; Pos += 4) {
107
0
        unsigned V = ((unsigned char)String[Pos - 4] << 24) |
108
0
                     ((unsigned char)String[Pos - 3] << 16) |
109
0
                     ((unsigned char)String[Pos - 2] << 8) |
110
0
                      (unsigned char)String[Pos - 1];
111
0
        Bits.push_back(V);
112
0
      }
113
145M
    } else {  // Little-endian host
114
431M
      for (Pos += 4; Pos <= Size; 
Pos += 4286M
) {
115
286M
        unsigned V = ((unsigned char)String[Pos - 1] << 24) |
116
286M
                     ((unsigned char)String[Pos - 2] << 16) |
117
286M
                     ((unsigned char)String[Pos - 3] << 8) |
118
286M
                      (unsigned char)String[Pos - 4];
119
286M
        Bits.push_back(V);
120
286M
      }
121
145M
    }
122
145M
  }
123
168M
124
168M
  // With the leftover bits.
125
168M
  unsigned V = 0;
126
168M
  // Pos will have overshot size by 4 - #bytes left over.
127
168M
  // No need to take endianness into account here - this is always executed.
128
168M
  switch (Pos - Size) {
129
168M
  
case 1: V = (V << 8) | (unsigned char)String[Size - 3]; 36.2M
LLVM_FALLTHROUGH36.2M
;
130
75.0M
  case 2: V = (V << 8) | (unsigned char)String[Size - 2]; LLVM_FALLTHROUGH;
131
157M
  case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break;
132
75.0M
  
default: return11.5M
; // Nothing left.
133
157M
  }
134
157M
135
157M
  Bits.push_back(V);
136
157M
}
137
138
// AddNodeID - Adds the Bit data of another ID to *this.
139
2.09M
void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) {
140
2.09M
  Bits.append(ID.Bits.begin(), ID.Bits.end());
141
2.09M
}
142
143
/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to
144
/// lookup the node in the FoldingSetBase.
145
596M
unsigned FoldingSetNodeID::ComputeHash() const {
146
596M
  return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
147
596M
}
148
149
/// operator== - Used to compare two nodes to each other.
150
///
151
405M
bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const {
152
405M
  return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
153
405M
}
154
155
/// operator== - Used to compare two nodes to each other.
156
///
157
652M
bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const {
158
652M
  return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS;
159
652M
}
160
161
/// Used to compare the "ordering" of two nodes as defined by the
162
/// profiled bits and their ordering defined by memcmp().
163
216
bool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const {
164
216
  return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
165
216
}
166
167
216
bool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const {
168
216
  return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS;
169
216
}
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
23.7M
FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const {
176
23.7M
  unsigned *New = Allocator.Allocate<unsigned>(Bits.size());
177
23.7M
  std::uninitialized_copy(Bits.begin(), Bits.end(), New);
178
23.7M
  return FoldingSetNodeIDRef(New, Bits.size());
179
23.7M
}
180
181
//===----------------------------------------------------------------------===//
182
/// Helper functions for FoldingSetBase.
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
981M
static FoldingSetBase::Node *GetNextPtr(void *NextInBucketPtr) {
191
981M
  // The low bit is set if this is the pointer back to the bucket.
192
981M
  if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1)
193
154M
    return nullptr;
194
827M
195
827M
  return static_cast<FoldingSetBase::Node*>(NextInBucketPtr);
196
827M
}
197
198
199
/// testing.
200
37.5M
static void **GetBucketPtr(void *NextInBucketPtr) {
201
37.5M
  intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
202
37.5M
  assert((Ptr & 1) && "Not a bucket pointer");
203
37.5M
  return reinterpret_cast<void**>(Ptr & ~intptr_t(1));
204
37.5M
}
205
206
/// GetBucketFor - Hash the specified node ID and return the hash bucket for
207
/// the specified ID.
208
605M
static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) {
209
605M
  // NumBuckets is always a power of 2.
210
605M
  unsigned BucketNum = Hash & (NumBuckets-1);
211
605M
  return Buckets + BucketNum;
212
605M
}
213
214
/// AllocateBuckets - Allocated initialized bucket memory.
215
12.1M
static void **AllocateBuckets(unsigned NumBuckets) {
216
12.1M
  void **Buckets = static_cast<void**>(safe_calloc(NumBuckets + 1,
217
12.1M
                                                   sizeof(void*)));
218
12.1M
  // Set the very last bucket to be a non-null "pointer".
219
12.1M
  Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
220
12.1M
  return Buckets;
221
12.1M
}
222
223
//===----------------------------------------------------------------------===//
224
// FoldingSetBase Implementation
225
226
0
void FoldingSetBase::anchor() {}
227
228
11.9M
FoldingSetBase::FoldingSetBase(unsigned Log2InitSize) {
229
11.9M
  assert(5 < Log2InitSize && Log2InitSize < 32 &&
230
11.9M
         "Initial hash table size out of range");
231
11.9M
  NumBuckets = 1 << Log2InitSize;
232
11.9M
  Buckets = AllocateBuckets(NumBuckets);
233
11.9M
  NumNodes = 0;
234
11.9M
}
235
236
FoldingSetBase::FoldingSetBase(FoldingSetBase &&Arg)
237
10.0k
    : Buckets(Arg.Buckets), NumBuckets(Arg.NumBuckets), NumNodes(Arg.NumNodes) {
238
10.0k
  Arg.Buckets = nullptr;
239
10.0k
  Arg.NumBuckets = 0;
240
10.0k
  Arg.NumNodes = 0;
241
10.0k
}
242
243
0
FoldingSetBase &FoldingSetBase::operator=(FoldingSetBase &&RHS) {
244
0
  free(Buckets); // This may be null if the set is in a moved-from state.
245
0
  Buckets = RHS.Buckets;
246
0
  NumBuckets = RHS.NumBuckets;
247
0
  NumNodes = RHS.NumNodes;
248
0
  RHS.Buckets = nullptr;
249
0
  RHS.NumBuckets = 0;
250
0
  RHS.NumNodes = 0;
251
0
  return *this;
252
0
}
253
254
10.6M
FoldingSetBase::~FoldingSetBase() {
255
10.6M
  free(Buckets);
256
10.6M
}
257
258
2.20M
void FoldingSetBase::clear() {
259
2.20M
  // Set all but the last bucket to null pointers.
260
2.20M
  memset(Buckets, 0, NumBuckets*sizeof(void*));
261
2.20M
262
2.20M
  // Set the very last bucket to be a non-null "pointer".
263
2.20M
  Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
264
2.20M
265
2.20M
  // Reset the node count to zero.
266
2.20M
  NumNodes = 0;
267
2.20M
}
268
269
158k
void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount) {
270
158k
  assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount");
271
158k
  assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!");
272
158k
  void **OldBuckets = Buckets;
273
158k
  unsigned OldNumBuckets = NumBuckets;
274
158k
275
158k
  // Clear out new buckets.
276
158k
  Buckets = AllocateBuckets(NewBucketCount);
277
158k
  // Set NumBuckets only if allocation of new buckets was successful.
278
158k
  NumBuckets = NewBucketCount;
279
158k
  NumNodes = 0;
280
158k
281
158k
  // Walk the old buckets, rehashing nodes into their new place.
282
158k
  FoldingSetNodeID TempID;
283
38.2M
  for (unsigned i = 0; i != OldNumBuckets; 
++i38.0M
) {
284
38.0M
    void *Probe = OldBuckets[i];
285
38.0M
    if (!Probe) 
continue5.65M
;
286
107M
    
while (Node *32.4M
NodeInBucket = GetNextPtr(Probe)) {
287
74.7M
      // Figure out the next link, remove NodeInBucket from the old link.
288
74.7M
      Probe = NodeInBucket->getNextInBucket();
289
74.7M
      NodeInBucket->SetNextInBucket(nullptr);
290
74.7M
291
74.7M
      // Insert the node into the new bucket, after recomputing the hash.
292
74.7M
      InsertNode(NodeInBucket,
293
74.7M
                 GetBucketFor(ComputeNodeHash(NodeInBucket, TempID),
294
74.7M
                              Buckets, NumBuckets));
295
74.7M
      TempID.clear();
296
74.7M
    }
297
32.4M
  }
298
158k
299
158k
  free(OldBuckets);
300
158k
}
301
302
/// GrowHashTable - Double the size of the hash table and rehash everything.
303
///
304
147k
void FoldingSetBase::GrowHashTable() {
305
147k
  GrowBucketCount(NumBuckets * 2);
306
147k
}
307
308
10.8k
void FoldingSetBase::reserve(unsigned EltCount) {
309
10.8k
  // This will give us somewhere between EltCount / 2 and
310
10.8k
  // EltCount buckets.  This puts us in the load factor
311
10.8k
  // range of 1.0 - 2.0.
312
10.8k
  if(EltCount < capacity())
313
8
    return;
314
10.8k
  GrowBucketCount(PowerOf2Floor(EltCount));
315
10.8k
}
316
317
/// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
318
/// return it.  If not, return the insertion token that will make insertion
319
/// faster.
320
FoldingSetBase::Node *
321
FoldingSetBase::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
322
530M
                                    void *&InsertPos) {
323
530M
  unsigned IDHash = ID.ComputeHash();
324
530M
  void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets);
325
530M
  void *Probe = *Bucket;
326
530M
327
530M
  InsertPos = nullptr;
328
530M
329
530M
  FoldingSetNodeID TempID;
330
817M
  while (Node *NodeInBucket = GetNextPtr(Probe)) {
331
653M
    if (NodeEquals(NodeInBucket, ID, IDHash, TempID))
332
366M
      return NodeInBucket;
333
286M
    TempID.clear();
334
286M
335
286M
    Probe = NodeInBucket->getNextInBucket();
336
286M
  }
337
530M
338
530M
  // Didn't find the node, return null with the bucket as the InsertPos.
339
530M
  InsertPos = Bucket;
340
163M
  return nullptr;
341
530M
}
342
343
/// InsertNode - Insert the specified node into the folding set, knowing that it
344
/// is not already in the map.  InsertPos must be obtained from
345
/// FindNodeOrInsertPos.
346
220M
void FoldingSetBase::InsertNode(Node *N, void *InsertPos) {
347
220M
  assert(!N->getNextInBucket());
348
220M
  // Do we need to grow the hashtable?
349
220M
  if (NumNodes+1 > capacity()) {
350
147k
    GrowHashTable();
351
147k
    FoldingSetNodeID TempID;
352
147k
    InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets);
353
147k
  }
354
220M
355
220M
  ++NumNodes;
356
220M
357
220M
  /// The insert position is actually a bucket pointer.
358
220M
  void **Bucket = static_cast<void**>(InsertPos);
359
220M
360
220M
  void *Next = *Bucket;
361
220M
362
220M
  // If this is the first insertion into this bucket, its next pointer will be
363
220M
  // null.  Pretend as if it pointed to itself, setting the low bit to indicate
364
220M
  // that it is a pointer to the bucket.
365
220M
  if (!Next)
366
120M
    Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1);
367
220M
368
220M
  // Set the node's next pointer, and make the bucket point to the node.
369
220M
  N->SetNextInBucket(Next);
370
220M
  *Bucket = N;
371
220M
}
372
373
/// RemoveNode - Remove a node from the folding set, returning true if one was
374
/// removed or false if the node was not in the folding set.
375
39.9M
bool FoldingSetBase::RemoveNode(Node *N) {
376
39.9M
  // Because each bucket is a circular list, we don't need to compute N's hash
377
39.9M
  // to remove it.
378
39.9M
  void *Ptr = N->getNextInBucket();
379
39.9M
  if (!Ptr) 
return false3.46M
; // Not in folding set.
380
36.5M
381
36.5M
  --NumNodes;
382
36.5M
  N->SetNextInBucket(nullptr);
383
36.5M
384
36.5M
  // Remember what N originally pointed to, either a bucket or another node.
385
36.5M
  void *NodeNextPtr = Ptr;
386
36.5M
387
36.5M
  // Chase around the list until we find the node (or bucket) which points to N.
388
54.8M
  while (
true54.8M
) {
389
54.8M
    if (Node *NodeInBucket = GetNextPtr(Ptr)) {
390
18.3M
      // Advance pointer.
391
18.3M
      Ptr = NodeInBucket->getNextInBucket();
392
18.3M
393
18.3M
      // We found a node that points to N, change it to point to N's next node,
394
18.3M
      // removing N from the list.
395
18.3M
      if (Ptr == N) {
396
5.40M
        NodeInBucket->SetNextInBucket(NodeNextPtr);
397
5.40M
        return true;
398
5.40M
      }
399
36.5M
    } else {
400
36.5M
      void **Bucket = GetBucketPtr(Ptr);
401
36.5M
      Ptr = *Bucket;
402
36.5M
403
36.5M
      // If we found that the bucket points to N, update the bucket to point to
404
36.5M
      // whatever is next.
405
36.5M
      if (Ptr == N) {
406
31.1M
        *Bucket = NodeNextPtr;
407
31.1M
        return true;
408
31.1M
      }
409
36.5M
    }
410
54.8M
  }
411
36.5M
}
412
413
/// GetOrInsertNode - If there is an existing simple Node exactly
414
/// equal to the specified node, return it.  Otherwise, insert 'N' and it
415
/// instead.
416
12.3M
FoldingSetBase::Node *FoldingSetBase::GetOrInsertNode(FoldingSetBase::Node *N) {
417
12.3M
  FoldingSetNodeID ID;
418
12.3M
  GetNodeProfile(N, ID);
419
12.3M
  void *IP;
420
12.3M
  if (Node *E = FindNodeOrInsertPos(ID, IP))
421
40.1k
    return E;
422
12.3M
  InsertNode(N, IP);
423
12.3M
  return N;
424
12.3M
}
425
426
//===----------------------------------------------------------------------===//
427
// FoldingSetIteratorImpl Implementation
428
429
635k
FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) {
430
635k
  // Skip to the first non-null non-self-cycle bucket.
431
15.4M
  while (*Bucket != reinterpret_cast<void*>(-1) &&
432
15.4M
         
(14.9M
!*Bucket14.9M
||
!GetNextPtr(*Bucket)143k
))
433
14.8M
    ++Bucket;
434
635k
435
635k
  NodePtr = static_cast<FoldingSetNode*>(*Bucket);
436
635k
}
437
438
1.24M
void FoldingSetIteratorImpl::advance() {
439
1.24M
  // If there is another link within this bucket, go to it.
440
1.24M
  void *Probe = NodePtr->getNextInBucket();
441
1.24M
442
1.24M
  if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe))
443
204k
    NodePtr = NextNodeInBucket;
444
1.04M
  else {
445
1.04M
    // Otherwise, this is the last link in this bucket.
446
1.04M
    void **Bucket = GetBucketPtr(Probe);
447
1.04M
448
1.04M
    // Skip to the next non-null non-self-cycle bucket.
449
50.0M
    do {
450
50.0M
      ++Bucket;
451
50.0M
    } while (*Bucket != reinterpret_cast<void*>(-1) &&
452
50.0M
             
(49.8M
!*Bucket49.8M
||
!GetNextPtr(*Bucket)900k
));
453
1.04M
454
1.04M
    NodePtr = static_cast<FoldingSetNode*>(*Bucket);
455
1.04M
  }
456
1.24M
}
457
458
//===----------------------------------------------------------------------===//
459
// FoldingSetBucketIteratorImpl Implementation
460
461
0
FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) {
462
0
  Ptr = (!*Bucket || !GetNextPtr(*Bucket)) ? (void*) Bucket : *Bucket;
463
0
}