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 FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
28 if (Size != RHS.Size)
29 return false;
30 return memcmp(s1: Data, s2: RHS.Data, n: Size * sizeof(*Data)) == 0;
31}
32
33bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const {
34 if (Size != RHS.Size)
35 return Size < RHS.Size;
36 return memcmp(s1: Data, s2: RHS.Data, n: Size * sizeof(*Data)) < 0;
37}
38
39//===----------------------------------------------------------------------===//
40// FoldingSetNodeID Implementation
41
42void FoldingSetNodeID::AddString(StringRef String) {
43 unsigned Size = String.size();
44
45 unsigned NumInserts = 1 + divideCeil(Numerator: Size, Denominator: 4);
46 Bits.reserve(N: Bits.size() + NumInserts);
47
48 Bits.push_back(Elt: Size);
49 if (!Size)
50 return;
51
52 unsigned Units = Size / 4;
53 unsigned Pos = 0;
54 const unsigned *Base = (const unsigned *)String.data();
55
56 // If the string is aligned do a bulk transfer.
57 if (!((intptr_t)Base & 3)) {
58 Bits.append(in_start: Base, in_end: Base + Units);
59 Pos = (Units + 1) * 4;
60 } else {
61 // Otherwise do it the hard way.
62 // To be compatible with above bulk transfer, we need to take endianness
63 // into account.
64 static_assert(sys::IsBigEndianHost || sys::IsLittleEndianHost,
65 "Unexpected host endianness");
66 if (sys::IsBigEndianHost) {
67 for (Pos += 4; Pos <= Size; Pos += 4) {
68 unsigned V = ((unsigned char)String[Pos - 4] << 24) |
69 ((unsigned char)String[Pos - 3] << 16) |
70 ((unsigned char)String[Pos - 2] << 8) |
71 (unsigned char)String[Pos - 1];
72 Bits.push_back(Elt: V);
73 }
74 } else { // Little-endian host
75 for (Pos += 4; Pos <= Size; Pos += 4) {
76 unsigned V = ((unsigned char)String[Pos - 1] << 24) |
77 ((unsigned char)String[Pos - 2] << 16) |
78 ((unsigned char)String[Pos - 3] << 8) |
79 (unsigned char)String[Pos - 4];
80 Bits.push_back(Elt: V);
81 }
82 }
83 }
84
85 // With the leftover bits.
86 unsigned V = 0;
87 // Pos will have overshot size by 4 - #bytes left over.
88 // No need to take endianness into account here - this is always executed.
89 switch (Pos - Size) {
90 case 1:
91 V = (V << 8) | (unsigned char)String[Size - 3];
92 [[fallthrough]];
93 case 2:
94 V = (V << 8) | (unsigned char)String[Size - 2];
95 [[fallthrough]];
96 case 3:
97 V = (V << 8) | (unsigned char)String[Size - 1];
98 break;
99 default:
100 return; // Nothing left.
101 }
102
103 Bits.push_back(Elt: V);
104}
105
106void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) {
107 Bits.append(in_start: ID.Bits.begin(), in_end: ID.Bits.end());
108}
109
110bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const {
111 return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
112}
113
114bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const {
115 return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS;
116}
117
118bool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const {
119 return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
120}
121
122bool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const {
123 return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS;
124}
125
126FoldingSetNodeIDRef
127FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const {
128 unsigned *New = Allocator.Allocate<unsigned>(Num: Bits.size());
129 llvm::uninitialized_copy(Src: Bits, Dst: New);
130 return FoldingSetNodeIDRef(New, Bits.size());
131}
132
133//===----------------------------------------------------------------------===//
134// FoldingSetBase Implementation
135
136/// Encode a 32-bit hash as an opaque non-null token for InsertPos.
137static void *encodeHash(uint32_t Hash) {
138 return reinterpret_cast<void *>(static_cast<uintptr_t>(Hash));
139}
140
141static uint32_t decodeHash(void *InsertPos) {
142 return static_cast<uint32_t>(reinterpret_cast<uintptr_t>(InsertPos));
143}
144
145FoldingSetBase::FoldingSetBase(unsigned Log2InitSize) {
146 assert(5 < Log2InitSize && Log2InitSize < 32 &&
147 "Initial hash table size out of range");
148 NumBuckets = 1 << Log2InitSize;
149 Buckets = static_cast<void **>(safe_calloc(Count: NumBuckets, Sz: sizeof(void *)));
150}
151
152FoldingSetBase::FoldingSetBase(FoldingSetBase &&Arg)
153 : Buckets(std::exchange(obj&: Arg.Buckets, new_val: nullptr)),
154 NumBuckets(std::exchange(obj&: Arg.NumBuckets, new_val: 0)),
155 NumNodes(std::exchange(obj&: Arg.NumNodes, new_val: 0)) {
156 Arg.incrementEpoch();
157}
158
159FoldingSetBase &FoldingSetBase::operator=(FoldingSetBase &&RHS) {
160 if (this == &RHS)
161 return *this;
162
163 incrementEpoch();
164 RHS.incrementEpoch();
165 free(ptr: Buckets); // This may be null if the set is in a moved-from state.
166 Buckets = std::exchange(obj&: RHS.Buckets, new_val: nullptr);
167 NumBuckets = std::exchange(obj&: RHS.NumBuckets, new_val: 0);
168 NumNodes = std::exchange(obj&: RHS.NumNodes, new_val: 0);
169 return *this;
170}
171
172FoldingSetBase::~FoldingSetBase() { free(ptr: Buckets); }
173
174void FoldingSetBase::clear() {
175 incrementEpoch();
176 // Stale hashes are unreachable, so only the occupancy needs resetting.
177 if (NumBuckets)
178 memset(s: Buckets, c: 0, n: NumBuckets * sizeof(void *));
179 NumNodes = 0;
180}
181
182void FoldingSetBase::placeNode(Node *N, uint32_t Hash) {
183 unsigned Mask = NumBuckets - 1;
184 unsigned I = Hash & Mask;
185 while (Buckets[I]) {
186 assert(Buckets[I] != N && "Node already in the folding set");
187 I = (I + 1) & Mask;
188 }
189 Buckets[I] = N;
190 ++NumNodes;
191}
192
193void FoldingSetBase::grow(unsigned MinNumBuckets) {
194 // The floor is the smallest size the constructor accepts.
195 unsigned NewBucketCount = std::max(a: 64u, b: llvm::bit_ceil(Value: MinNumBuckets));
196 assert(NewBucketCount > NumBuckets && "Can't shrink a folding set");
197
198 FoldingSetBase Tmp(llvm::Log2_32(Value: NewBucketCount));
199 for (unsigned I = 0; I != NumBuckets; ++I)
200 if (void *N = Buckets[I])
201 Tmp.placeNode(N: static_cast<Node *>(N),
202 Hash: static_cast<Node *>(N)->getFoldingSetHash());
203
204 *this = std::move(Tmp);
205}
206
207void FoldingSetBase::reserve(unsigned N) {
208 if (N * 4 <= NumBuckets * 3)
209 return;
210 // N + (N + 2) / 3 is ceil(4N/3).
211 grow(MinNumBuckets: N + (N + 2) / 3);
212}
213
214LLVM_ATTRIBUTE_NOINLINE bool
215FoldingSetBase::nodeEquals(const FoldingSetInfo &Info,
216 const FoldingSetBase *Self, Node *N,
217 const FoldingSetNodeID &ID) {
218 FoldingSetNodeID TempID;
219 return Info.NodeEquals(Self, N, ID, TempID);
220}
221
222FoldingSetBase::Node *FoldingSetBase::lookup(const FoldingSetNodeID &ID,
223 FoldingSetInsertToken &Token,
224 const FoldingSetInfo &Info) {
225 unsigned IDHash = ID.ComputeHash();
226 unsigned Mask = NumBuckets - 1;
227 for (unsigned I = IDHash & Mask; Buckets[I]; I = (I + 1) & Mask) {
228 Node *N = static_cast<Node *>(Buckets[I]);
229 if (N->getFoldingSetHash() == IDHash && nodeEquals(Info, Self: this, N, ID)) {
230 Token = {};
231 return N;
232 }
233 }
234
235 Token = FoldingSetInsertToken(IDHash);
236 return nullptr;
237}
238
239FoldingSetBase::Node *FoldingSetBase::FindNodeOrInsertPos(
240 const FoldingSetNodeID &ID, void *&InsertPos, const FoldingSetInfo &Info) {
241 FoldingSetInsertToken Token;
242 Node *N = lookup(ID, Token, Info);
243 InsertPos = Token ? encodeHash(Hash: Token.Hash) : nullptr;
244 return N;
245}
246
247void FoldingSetBase::insert(Node *N, FoldingSetInsertToken Token) {
248 assert(N && "Cannot insert a null node");
249 assert(Token && "Invalid token!");
250 incrementEpoch();
251 if (LLVM_UNLIKELY((NumNodes + 1) * 4 > NumBuckets * 3))
252 grow(MinNumBuckets: NumBuckets * 2);
253 uint32_t Hash = Token.Hash;
254 placeNode(N, Hash);
255 N->setFoldingSetHash(Hash);
256}
257
258void FoldingSetBase::InsertNode(Node *N, void *InsertPos) {
259 insert(N, Token: FoldingSetInsertToken(decodeHash(InsertPos)));
260}
261
262bool FoldingSetBase::RemoveNode(Node *N) {
263 uint32_t Hash = N->getFoldingSetHash();
264 if (Hash == FoldingSetNodeIDRef::NotAHash)
265 return false; // Never inserted.
266
267 unsigned Mask = NumBuckets - 1;
268 unsigned I = Hash & Mask;
269 while (Buckets[I] != N) {
270 if (LLVM_UNLIKELY(!Buckets[I]))
271 return false; // Not in folding set.
272 I = (I + 1) & Mask;
273 }
274
275 incrementEpoch();
276
277 // Knuth TAOCP 6.4 Algorithm R: walk forward sliding each following entry
278 // whose probe path crosses the hole.
279 for (unsigned J = (I + 1) & Mask; Buckets[J]; J = (J + 1) & Mask) {
280 unsigned Ideal = static_cast<Node *>(Buckets[J])->getFoldingSetHash();
281 if (((I - Ideal) & Mask) < ((J - Ideal) & Mask)) {
282 Buckets[I] = Buckets[J];
283 I = J;
284 }
285 }
286 Buckets[I] = nullptr;
287 N->setFoldingSetHash(FoldingSetNodeIDRef::NotAHash);
288 --NumNodes;
289 return true;
290}
291
292FoldingSetBase::Node *
293FoldingSetBase::GetOrInsertNode(Node *N, const FoldingSetInfo &Info) {
294 FoldingSetNodeID ID;
295 Info.GetNodeProfile(this, N, ID);
296 FoldingSetInsertToken Token;
297 if (Node *E = lookup(ID, Token, Info))
298 return E;
299 insert(N, Token);
300 return N;
301}
302