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/STLExtras.h"
16#include "llvm/ADT/StringRef.h"
17#include "llvm/Support/Allocator.h"
18#include "llvm/Support/MathExtras.h"
19#include "llvm/Support/SwapByteOrder.h"
20#include <cassert>
21#include <cstring>
22using namespace llvm;
23
24//===----------------------------------------------------------------------===//
25// FoldingSetNodeIDRef Implementation
26
27bool llvm::operator<(FoldingSetNodeIDRef LHS, FoldingSetNodeIDRef RHS) {
28 if (LHS.size() != RHS.size())
29 return LHS.size() < RHS.size();
30 return memcmp(s1: LHS.data(), s2: RHS.data(), n: LHS.size() * sizeof(unsigned)) < 0;
31}
32
33//===----------------------------------------------------------------------===//
34// FoldingSetNodeID Implementation
35
36void FoldingSetNodeID::AddString(StringRef String) {
37 unsigned Size = String.size();
38
39 unsigned NumInserts = 1 + divideCeil(Numerator: Size, Denominator: 4);
40 Bits.reserve(N: Bits.size() + NumInserts);
41
42 Bits.push_back(Elt: Size);
43 if (!Size)
44 return;
45
46 unsigned Units = Size / 4;
47 unsigned Pos = 0;
48 const unsigned *Base = (const unsigned *)String.data();
49
50 // If the string is aligned do a bulk transfer.
51 if (!((intptr_t)Base & 3)) {
52 Bits.append(in_start: Base, in_end: Base + Units);
53 Pos = (Units + 1) * 4;
54 } else {
55 // Otherwise do it the hard way.
56 // To be compatible with above bulk transfer, we need to take endianness
57 // into account.
58 static_assert(sys::IsBigEndianHost || sys::IsLittleEndianHost,
59 "Unexpected host endianness");
60 if (sys::IsBigEndianHost) {
61 for (Pos += 4; Pos <= Size; Pos += 4) {
62 unsigned V = ((unsigned char)String[Pos - 4] << 24) |
63 ((unsigned char)String[Pos - 3] << 16) |
64 ((unsigned char)String[Pos - 2] << 8) |
65 (unsigned char)String[Pos - 1];
66 Bits.push_back(Elt: V);
67 }
68 } else { // Little-endian host
69 for (Pos += 4; Pos <= Size; Pos += 4) {
70 unsigned V = ((unsigned char)String[Pos - 1] << 24) |
71 ((unsigned char)String[Pos - 2] << 16) |
72 ((unsigned char)String[Pos - 3] << 8) |
73 (unsigned char)String[Pos - 4];
74 Bits.push_back(Elt: V);
75 }
76 }
77 }
78
79 // With the leftover bits.
80 unsigned V = 0;
81 // Pos will have overshot size by 4 - #bytes left over.
82 // No need to take endianness into account here - this is always executed.
83 switch (Pos - Size) {
84 case 1:
85 V = (V << 8) | (unsigned char)String[Size - 3];
86 [[fallthrough]];
87 case 2:
88 V = (V << 8) | (unsigned char)String[Size - 2];
89 [[fallthrough]];
90 case 3:
91 V = (V << 8) | (unsigned char)String[Size - 1];
92 break;
93 default:
94 return; // Nothing left.
95 }
96
97 Bits.push_back(Elt: V);
98}
99
100void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) {
101 Bits.append(in_start: ID.Bits.begin(), in_end: ID.Bits.end());
102}
103
104FoldingSetNodeIDRef
105FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const {
106 unsigned *New = Allocator.Allocate<unsigned>(Num: Bits.size());
107 llvm::uninitialized_copy(Src: Bits, Dst: New);
108 return FoldingSetNodeIDRef(New, Bits.size());
109}
110
111//===----------------------------------------------------------------------===//
112// FoldingSetBase Implementation
113
114FoldingSetBase::FoldingSetBase(unsigned Log2InitSize) {
115 assert(5 < Log2InitSize && Log2InitSize < 32 &&
116 "Initial hash table size out of range");
117 NumBuckets = 1 << Log2InitSize;
118 Buckets = static_cast<FoldingSetNode **>(
119 safe_calloc(Count: NumBuckets, Sz: sizeof(FoldingSetNode *)));
120}
121
122FoldingSetBase::FoldingSetBase(FoldingSetBase &&Arg)
123 : Buckets(std::exchange(obj&: Arg.Buckets, new_val: nullptr)),
124 NumBuckets(std::exchange(obj&: Arg.NumBuckets, new_val: 0)),
125 NumNodes(std::exchange(obj&: Arg.NumNodes, new_val: 0)) {
126 Arg.incrementEpoch();
127}
128
129FoldingSetBase &FoldingSetBase::operator=(FoldingSetBase &&RHS) {
130 if (this == &RHS)
131 return *this;
132
133 incrementEpoch();
134 RHS.incrementEpoch();
135 free(ptr: Buckets); // This may be null if the set is in a moved-from state.
136 Buckets = std::exchange(obj&: RHS.Buckets, new_val: nullptr);
137 NumBuckets = std::exchange(obj&: RHS.NumBuckets, new_val: 0);
138 NumNodes = std::exchange(obj&: RHS.NumNodes, new_val: 0);
139 return *this;
140}
141
142FoldingSetBase::~FoldingSetBase() { free(ptr: Buckets); }
143
144void FoldingSetBase::clear() {
145 incrementEpoch();
146 // Stale hashes are unreachable, so only the occupancy needs resetting.
147 if (NumBuckets)
148 memset(s: Buckets, c: 0, n: NumBuckets * sizeof(FoldingSetNode *));
149 NumNodes = 0;
150}
151
152void FoldingSetBase::placeNode(FoldingSetNode *N, uint32_t Hash) {
153 unsigned Mask = NumBuckets - 1;
154 unsigned I = Hash & Mask;
155 while (Buckets[I]) {
156 assert(Buckets[I] != N && "Node already in the folding set");
157 I = (I + 1) & Mask;
158 }
159 Buckets[I] = N;
160 ++NumNodes;
161}
162
163void FoldingSetBase::grow(unsigned MinNumBuckets) {
164 // The floor is the smallest size the constructor accepts.
165 unsigned NewBucketCount = std::max(a: 64u, b: llvm::bit_ceil(Value: MinNumBuckets));
166 assert(NewBucketCount > NumBuckets && "Can't shrink a folding set");
167
168 FoldingSetBase Tmp(llvm::Log2_32(Value: NewBucketCount));
169 for (unsigned I = 0; I != NumBuckets; ++I)
170 if (FoldingSetNode *N = Buckets[I])
171 Tmp.placeNode(N, Hash: N->getFoldingSetHash());
172
173 *this = std::move(Tmp);
174}
175
176void FoldingSetBase::reserve(unsigned N) {
177 if (N * 4 <= NumBuckets * 3)
178 return;
179 // N + (N + 2) / 3 is ceil(4N/3).
180 grow(MinNumBuckets: N + (N + 2) / 3);
181}
182
183void FoldingSetBase::insert(FoldingSetNode *N, FoldingSetInsertToken Token) {
184 assert(N && "Cannot insert a null node");
185 assert(Token && "Invalid token!");
186 incrementEpoch();
187 if (LLVM_UNLIKELY((NumNodes + 1) * 4 > NumBuckets * 3))
188 grow(MinNumBuckets: NumBuckets * 2);
189 uint32_t Hash = Token.Hash;
190 placeNode(N, Hash);
191 N->setFoldingSetHash(Hash);
192}
193
194bool FoldingSetBase::erase(FoldingSetNode *N) {
195 uint32_t Hash = N->getFoldingSetHash();
196 if (Hash == FoldingSetNodeIDRef::NotAHash)
197 return false; // Never inserted.
198
199 unsigned Mask = NumBuckets - 1;
200 unsigned I = Hash & Mask;
201 while (Buckets[I] != N) {
202 if (LLVM_UNLIKELY(!Buckets[I]))
203 return false; // Not in folding set.
204 I = (I + 1) & Mask;
205 }
206
207 incrementEpoch();
208
209 // Knuth TAOCP 6.4 Algorithm R: walk forward sliding each following entry
210 // whose probe path crosses the hole.
211 for (unsigned J = (I + 1) & Mask; Buckets[J]; J = (J + 1) & Mask) {
212 unsigned Ideal = Buckets[J]->getFoldingSetHash();
213 if (((I - Ideal) & Mask) < ((J - Ideal) & Mask)) {
214 Buckets[I] = Buckets[J];
215 I = J;
216 }
217 }
218 Buckets[I] = nullptr;
219 N->setFoldingSetHash(FoldingSetNodeIDRef::NotAHash);
220 --NumNodes;
221 return true;
222}
223