1 | //===- llvm/ADT/FoldingSet.h - 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 | /// \file |

10 | /// This file defines a hash set that can be used to remove duplication of nodes |

11 | /// in a graph. This code was originally created by Chris Lattner for use with |

12 | /// SelectionDAGCSEMap, but was isolated to provide use across the llvm code |

13 | /// set. |

14 | //===----------------------------------------------------------------------===// |

15 | |

16 | #ifndef LLVM_ADT_FOLDINGSET_H |

17 | #define LLVM_ADT_FOLDINGSET_H |

18 | |

19 | #include "llvm/ADT/APInt.h" |

20 | #include "llvm/ADT/Hashing.h" |

21 | #include "llvm/ADT/STLForwardCompat.h" |

22 | #include "llvm/ADT/SmallVector.h" |

23 | #include "llvm/ADT/iterator.h" |

24 | #include "llvm/Support/Allocator.h" |

25 | #include <cassert> |

26 | #include <cstddef> |

27 | #include <cstdint> |

28 | #include <type_traits> |

29 | #include <utility> |

30 | |

31 | namespace llvm { |

32 | |

33 | /// This folding set used for two purposes: |

34 | /// 1. Given information about a node we want to create, look up the unique |

35 | /// instance of the node in the set. If the node already exists, return |

36 | /// it, otherwise return the bucket it should be inserted into. |

37 | /// 2. Given a node that has already been created, remove it from the set. |

38 | /// |

39 | /// This class is implemented as a single-link chained hash table, where the |

40 | /// "buckets" are actually the nodes themselves (the next pointer is in the |

41 | /// node). The last node points back to the bucket to simplify node removal. |

42 | /// |

43 | /// Any node that is to be included in the folding set must be a subclass of |

44 | /// FoldingSetNode. The node class must also define a Profile method used to |

45 | /// establish the unique bits of data for the node. The Profile method is |

46 | /// passed a FoldingSetNodeID object which is used to gather the bits. Just |

47 | /// call one of the Add* functions defined in the FoldingSetBase::NodeID class. |

48 | /// NOTE: That the folding set does not own the nodes and it is the |

49 | /// responsibility of the user to dispose of the nodes. |

50 | /// |

51 | /// Eg. |

52 | /// class MyNode : public FoldingSetNode { |

53 | /// private: |

54 | /// std::string Name; |

55 | /// unsigned Value; |

56 | /// public: |

57 | /// MyNode(const char *N, unsigned V) : Name(N), Value(V) {} |

58 | /// ... |

59 | /// void Profile(FoldingSetNodeID &ID) const { |

60 | /// ID.AddString(Name); |

61 | /// ID.AddInteger(Value); |

62 | /// } |

63 | /// ... |

64 | /// }; |

65 | /// |

66 | /// To define the folding set itself use the FoldingSet template; |

67 | /// |

68 | /// Eg. |

69 | /// FoldingSet<MyNode> MyFoldingSet; |

70 | /// |

71 | /// Four public methods are available to manipulate the folding set; |

72 | /// |

73 | /// 1) If you have an existing node that you want add to the set but unsure |

74 | /// that the node might already exist then call; |

75 | /// |

76 | /// MyNode *M = MyFoldingSet.GetOrInsertNode(N); |

77 | /// |

78 | /// If The result is equal to the input then the node has been inserted. |

79 | /// Otherwise, the result is the node existing in the folding set, and the |

80 | /// input can be discarded (use the result instead.) |

81 | /// |

82 | /// 2) If you are ready to construct a node but want to check if it already |

83 | /// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to |

84 | /// check; |

85 | /// |

86 | /// FoldingSetNodeID ID; |

87 | /// ID.AddString(Name); |

88 | /// ID.AddInteger(Value); |

89 | /// void *InsertPoint; |

90 | /// |

91 | /// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint); |

92 | /// |

93 | /// If found then M will be non-NULL, else InsertPoint will point to where it |

94 | /// should be inserted using InsertNode. |

95 | /// |

96 | /// 3) If you get a NULL result from FindNodeOrInsertPos then you can insert a |

97 | /// new node with InsertNode; |

98 | /// |

99 | /// MyFoldingSet.InsertNode(M, InsertPoint); |

100 | /// |

101 | /// 4) Finally, if you want to remove a node from the folding set call; |

102 | /// |

103 | /// bool WasRemoved = MyFoldingSet.RemoveNode(M); |

104 | /// |

105 | /// The result indicates whether the node existed in the folding set. |

106 | |

107 | class FoldingSetNodeID; |

108 | class StringRef; |

109 | |

110 | //===----------------------------------------------------------------------===// |

111 | /// FoldingSetBase - Implements the folding set functionality. The main |

112 | /// structure is an array of buckets. Each bucket is indexed by the hash of |

113 | /// the nodes it contains. The bucket itself points to the nodes contained |

114 | /// in the bucket via a singly linked list. The last node in the list points |

115 | /// back to the bucket to facilitate node removal. |

116 | /// |

117 | class FoldingSetBase { |

118 | protected: |

119 | /// Buckets - Array of bucket chains. |

120 | void **Buckets; |

121 | |

122 | /// NumBuckets - Length of the Buckets array. Always a power of 2. |

123 | unsigned NumBuckets; |

124 | |

125 | /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes |

126 | /// is greater than twice the number of buckets. |

127 | unsigned NumNodes; |

128 | |

129 | explicit FoldingSetBase(unsigned Log2InitSize = 6); |

130 | FoldingSetBase(FoldingSetBase &&Arg); |

131 | FoldingSetBase &operator=(FoldingSetBase &&RHS); |

132 | ~FoldingSetBase(); |

133 | |

134 | public: |

135 | //===--------------------------------------------------------------------===// |

136 | /// Node - This class is used to maintain the singly linked bucket list in |

137 | /// a folding set. |

138 | class Node { |

139 | private: |

140 | // NextInFoldingSetBucket - next link in the bucket list. |

141 | void *NextInFoldingSetBucket = nullptr; |

142 | |

143 | public: |

144 | Node() = default; |

145 | |

146 | // Accessors |

147 | void *getNextInBucket() const { return NextInFoldingSetBucket; } |

148 | void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; } |

149 | }; |

150 | |

151 | /// clear - Remove all nodes from the folding set. |

152 | void clear(); |

153 | |

154 | /// size - Returns the number of nodes in the folding set. |

155 | unsigned size() const { return NumNodes; } |

156 | |

157 | /// empty - Returns true if there are no nodes in the folding set. |

158 | bool empty() const { return NumNodes == 0; } |

159 | |

160 | /// capacity - Returns the number of nodes permitted in the folding set |

161 | /// before a rebucket operation is performed. |

162 | unsigned capacity() { |

163 | // We allow a load factor of up to 2.0, |

164 | // so that means our capacity is NumBuckets * 2 |

165 | return NumBuckets * 2; |

166 | } |

167 | |

168 | protected: |

169 | /// Functions provided by the derived class to compute folding properties. |

170 | /// This is effectively a vtable for FoldingSetBase, except that we don't |

171 | /// actually store a pointer to it in the object. |

172 | struct FoldingSetInfo { |

173 | /// GetNodeProfile - Instantiations of the FoldingSet template implement |

174 | /// this function to gather data bits for the given node. |

175 | void (*GetNodeProfile)(const FoldingSetBase *Self, Node *N, |

176 | FoldingSetNodeID &ID); |

177 | |

178 | /// NodeEquals - Instantiations of the FoldingSet template implement |

179 | /// this function to compare the given node with the given ID. |

180 | bool (*NodeEquals)(const FoldingSetBase *Self, Node *N, |

181 | const FoldingSetNodeID &ID, unsigned IDHash, |

182 | FoldingSetNodeID &TempID); |

183 | |

184 | /// ComputeNodeHash - Instantiations of the FoldingSet template implement |

185 | /// this function to compute a hash value for the given node. |

186 | unsigned (*ComputeNodeHash)(const FoldingSetBase *Self, Node *N, |

187 | FoldingSetNodeID &TempID); |

188 | }; |

189 | |

190 | private: |

191 | /// GrowHashTable - Double the size of the hash table and rehash everything. |

192 | void GrowHashTable(const FoldingSetInfo &Info); |

193 | |

194 | /// GrowBucketCount - resize the hash table and rehash everything. |

195 | /// NewBucketCount must be a power of two, and must be greater than the old |

196 | /// bucket count. |

197 | void GrowBucketCount(unsigned NewBucketCount, const FoldingSetInfo &Info); |

198 | |

199 | protected: |

200 | // The below methods are protected to encourage subclasses to provide a more |

201 | // type-safe API. |

202 | |

203 | /// reserve - Increase the number of buckets such that adding the |

204 | /// EltCount-th node won't cause a rebucket operation. reserve is permitted |

205 | /// to allocate more space than requested by EltCount. |

206 | void reserve(unsigned EltCount, const FoldingSetInfo &Info); |

207 | |

208 | /// RemoveNode - Remove a node from the folding set, returning true if one |

209 | /// was removed or false if the node was not in the folding set. |

210 | bool RemoveNode(Node *N); |

211 | |

212 | /// GetOrInsertNode - If there is an existing simple Node exactly |

213 | /// equal to the specified node, return it. Otherwise, insert 'N' and return |

214 | /// it instead. |

215 | Node *GetOrInsertNode(Node *N, const FoldingSetInfo &Info); |

216 | |

217 | /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, |

218 | /// return it. If not, return the insertion token that will make insertion |

219 | /// faster. |

220 | Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos, |

221 | const FoldingSetInfo &Info); |

222 | |

223 | /// InsertNode - Insert the specified node into the folding set, knowing that |

224 | /// it is not already in the folding set. InsertPos must be obtained from |

225 | /// FindNodeOrInsertPos. |

226 | void InsertNode(Node *N, void *InsertPos, const FoldingSetInfo &Info); |

227 | }; |

228 | |

229 | //===----------------------------------------------------------------------===// |

230 | |

231 | /// DefaultFoldingSetTrait - This class provides default implementations |

232 | /// for FoldingSetTrait implementations. |

233 | template<typename T> struct DefaultFoldingSetTrait { |

234 | static void Profile(const T &X, FoldingSetNodeID &ID) { |

235 | X.Profile(ID); |

236 | } |

237 | static void Profile(T &X, FoldingSetNodeID &ID) { |

238 | X.Profile(ID); |

239 | } |

240 | |

241 | // Equals - Test if the profile for X would match ID, using TempID |

242 | // to compute a temporary ID if necessary. The default implementation |

243 | // just calls Profile and does a regular comparison. Implementations |

244 | // can override this to provide more efficient implementations. |

245 | static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, |

246 | FoldingSetNodeID &TempID); |

247 | |

248 | // ComputeHash - Compute a hash value for X, using TempID to |

249 | // compute a temporary ID if necessary. The default implementation |

250 | // just calls Profile and does a regular hash computation. |

251 | // Implementations can override this to provide more efficient |

252 | // implementations. |

253 | static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID); |

254 | }; |

255 | |

256 | /// FoldingSetTrait - This trait class is used to define behavior of how |

257 | /// to "profile" (in the FoldingSet parlance) an object of a given type. |

258 | /// The default behavior is to invoke a 'Profile' method on an object, but |

259 | /// through template specialization the behavior can be tailored for specific |

260 | /// types. Combined with the FoldingSetNodeWrapper class, one can add objects |

261 | /// to FoldingSets that were not originally designed to have that behavior. |

262 | template <typename T, typename Enable = void> |

263 | struct FoldingSetTrait : public DefaultFoldingSetTrait<T> {}; |

264 | |

265 | /// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but |

266 | /// for ContextualFoldingSets. |

267 | template<typename T, typename Ctx> |

268 | struct DefaultContextualFoldingSetTrait { |

269 | static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) { |

270 | X.Profile(ID, Context); |

271 | } |

272 | |

273 | static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, |

274 | FoldingSetNodeID &TempID, Ctx Context); |

275 | static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, |

276 | Ctx Context); |

277 | }; |

278 | |

279 | /// ContextualFoldingSetTrait - Like FoldingSetTrait, but for |

280 | /// ContextualFoldingSets. |

281 | template<typename T, typename Ctx> struct ContextualFoldingSetTrait |

282 | : public DefaultContextualFoldingSetTrait<T, Ctx> {}; |

283 | |

284 | //===--------------------------------------------------------------------===// |

285 | /// FoldingSetNodeIDRef - This class describes a reference to an interned |

286 | /// FoldingSetNodeID, which can be a useful to store node id data rather |

287 | /// than using plain FoldingSetNodeIDs, since the 32-element SmallVector |

288 | /// is often much larger than necessary, and the possibility of heap |

289 | /// allocation means it requires a non-trivial destructor call. |

290 | class FoldingSetNodeIDRef { |

291 | const unsigned *Data = nullptr; |

292 | size_t Size = 0; |

293 | |

294 | public: |

295 | FoldingSetNodeIDRef() = default; |

296 | FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {} |

297 | |

298 | /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, |

299 | /// used to lookup the node in the FoldingSetBase. |

300 | unsigned ComputeHash() const { |

301 | return static_cast<unsigned>(hash_combine_range(first: Data, last: Data + Size)); |

302 | } |

303 | |

304 | bool operator==(FoldingSetNodeIDRef) const; |

305 | |

306 | bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); } |

307 | |

308 | /// Used to compare the "ordering" of two nodes as defined by the |

309 | /// profiled bits and their ordering defined by memcmp(). |

310 | bool operator<(FoldingSetNodeIDRef) const; |

311 | |

312 | const unsigned *getData() const { return Data; } |

313 | size_t getSize() const { return Size; } |

314 | }; |

315 | |

316 | //===--------------------------------------------------------------------===// |

317 | /// FoldingSetNodeID - This class is used to gather all the unique data bits of |

318 | /// a node. When all the bits are gathered this class is used to produce a |

319 | /// hash value for the node. |

320 | class FoldingSetNodeID { |

321 | /// Bits - Vector of all the data bits that make the node unique. |

322 | /// Use a SmallVector to avoid a heap allocation in the common case. |

323 | SmallVector<unsigned, 32> Bits; |

324 | |

325 | public: |

326 | FoldingSetNodeID() = default; |

327 | |

328 | FoldingSetNodeID(FoldingSetNodeIDRef Ref) |

329 | : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {} |

330 | |

331 | /// Add* - Add various data types to Bit data. |

332 | void AddPointer(const void *Ptr) { |

333 | // Note: this adds pointers to the hash using sizes and endianness that |

334 | // depend on the host. It doesn't matter, however, because hashing on |

335 | // pointer values is inherently unstable. Nothing should depend on the |

336 | // ordering of nodes in the folding set. |

337 | static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long), |

338 | "unexpected pointer size"); |

339 | AddInteger(I: reinterpret_cast<uintptr_t>(Ptr)); |

340 | } |

341 | void AddInteger(signed I) { Bits.push_back(Elt: I); } |

342 | void AddInteger(unsigned I) { Bits.push_back(Elt: I); } |

343 | void AddInteger(long I) { AddInteger(I: (unsigned long)I); } |

344 | void AddInteger(unsigned long I) { |

345 | if (sizeof(long) == sizeof(int)) |

346 | AddInteger(I: unsigned(I)); |

347 | else if (sizeof(long) == sizeof(long long)) { |

348 | AddInteger(I: (unsigned long long)I); |

349 | } else { |

350 | llvm_unreachable("unexpected sizeof(long)"); |

351 | } |

352 | } |

353 | void AddInteger(long long I) { AddInteger(I: (unsigned long long)I); } |

354 | void AddInteger(unsigned long long I) { |

355 | AddInteger(I: unsigned(I)); |

356 | AddInteger(I: unsigned(I >> 32)); |

357 | } |

358 | void AddInteger(const APInt &Int) { |

359 | AddInteger(I: Int.getBitWidth()); |

360 | const auto *Parts = Int.getRawData(); |

361 | for (int i = 0, N = Int.getNumWords(); i < N; ++i) { |

362 | AddInteger(I: Parts[i]); |

363 | } |

364 | } |

365 | |

366 | void AddBoolean(bool B) { AddInteger(I: B ? 1U : 0U); } |

367 | void AddString(StringRef String); |

368 | void AddNodeID(const FoldingSetNodeID &ID); |

369 | |

370 | template <typename T> |

371 | inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); } |

372 | |

373 | /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID |

374 | /// object to be used to compute a new profile. |

375 | inline void clear() { Bits.clear(); } |

376 | |

377 | /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used |

378 | /// to lookup the node in the FoldingSetBase. |

379 | unsigned ComputeHash() const { |

380 | return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash(); |

381 | } |

382 | |

383 | /// operator== - Used to compare two nodes to each other. |

384 | bool operator==(const FoldingSetNodeID &RHS) const; |

385 | bool operator==(const FoldingSetNodeIDRef RHS) const; |

386 | |

387 | bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); } |

388 | bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);} |

389 | |

390 | /// Used to compare the "ordering" of two nodes as defined by the |

391 | /// profiled bits and their ordering defined by memcmp(). |

392 | bool operator<(const FoldingSetNodeID &RHS) const; |

393 | bool operator<(const FoldingSetNodeIDRef RHS) const; |

394 | |

395 | /// Intern - Copy this node's data to a memory region allocated from the |

396 | /// given allocator and return a FoldingSetNodeIDRef describing the |

397 | /// interned data. |

398 | FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const; |

399 | }; |

400 | |

401 | // Convenience type to hide the implementation of the folding set. |

402 | using FoldingSetNode = FoldingSetBase::Node; |

403 | template<class T> class FoldingSetIterator; |

404 | template<class T> class FoldingSetBucketIterator; |

405 | |

406 | // Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which |

407 | // require the definition of FoldingSetNodeID. |

408 | template<typename T> |

409 | inline bool |

410 | DefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID, |

411 | unsigned /*IDHash*/, |

412 | FoldingSetNodeID &TempID) { |

413 | FoldingSetTrait<T>::Profile(X, TempID); |

414 | return TempID == ID; |

415 | } |

416 | template<typename T> |

417 | inline unsigned |

418 | DefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) { |

419 | FoldingSetTrait<T>::Profile(X, TempID); |

420 | return TempID.ComputeHash(); |

421 | } |

422 | template<typename T, typename Ctx> |

423 | inline bool |

424 | DefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X, |

425 | const FoldingSetNodeID &ID, |

426 | unsigned /*IDHash*/, |

427 | FoldingSetNodeID &TempID, |

428 | Ctx Context) { |

429 | ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); |

430 | return TempID == ID; |

431 | } |

432 | template<typename T, typename Ctx> |

433 | inline unsigned |

434 | DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X, |

435 | FoldingSetNodeID &TempID, |

436 | Ctx Context) { |

437 | ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); |

438 | return TempID.ComputeHash(); |

439 | } |

440 | |

441 | //===----------------------------------------------------------------------===// |

442 | /// FoldingSetImpl - An implementation detail that lets us share code between |

443 | /// FoldingSet and ContextualFoldingSet. |

444 | template <class Derived, class T> class FoldingSetImpl : public FoldingSetBase { |

445 | protected: |

446 | explicit FoldingSetImpl(unsigned Log2InitSize) |

447 | : FoldingSetBase(Log2InitSize) {} |

448 | |

449 | FoldingSetImpl(FoldingSetImpl &&Arg) = default; |

450 | FoldingSetImpl &operator=(FoldingSetImpl &&RHS) = default; |

451 | ~FoldingSetImpl() = default; |

452 | |

453 | public: |

454 | using iterator = FoldingSetIterator<T>; |

455 | |

456 | iterator begin() { return iterator(Buckets); } |

457 | iterator end() { return iterator(Buckets+NumBuckets); } |

458 | |

459 | using const_iterator = FoldingSetIterator<const T>; |

460 | |

461 | const_iterator begin() const { return const_iterator(Buckets); } |

462 | const_iterator end() const { return const_iterator(Buckets+NumBuckets); } |

463 | |

464 | using bucket_iterator = FoldingSetBucketIterator<T>; |

465 | |

466 | bucket_iterator bucket_begin(unsigned hash) { |

467 | return bucket_iterator(Buckets + (hash & (NumBuckets-1))); |

468 | } |

469 | |

470 | bucket_iterator bucket_end(unsigned hash) { |

471 | return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); |

472 | } |

473 | |

474 | /// reserve - Increase the number of buckets such that adding the |

475 | /// EltCount-th node won't cause a rebucket operation. reserve is permitted |

476 | /// to allocate more space than requested by EltCount. |

477 | void reserve(unsigned EltCount) { |

478 | return FoldingSetBase::reserve(EltCount, Info: Derived::getFoldingSetInfo()); |

479 | } |

480 | |

481 | /// RemoveNode - Remove a node from the folding set, returning true if one |

482 | /// was removed or false if the node was not in the folding set. |

483 | bool RemoveNode(T *N) { |

484 | return FoldingSetBase::RemoveNode(N); |

485 | } |

486 | |

487 | /// GetOrInsertNode - If there is an existing simple Node exactly |

488 | /// equal to the specified node, return it. Otherwise, insert 'N' and |

489 | /// return it instead. |

490 | T *GetOrInsertNode(T *N) { |

491 | return static_cast<T *>( |

492 | FoldingSetBase::GetOrInsertNode(N, Info: Derived::getFoldingSetInfo())); |

493 | } |

494 | |

495 | /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, |

496 | /// return it. If not, return the insertion token that will make insertion |

497 | /// faster. |

498 | T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { |

499 | return static_cast<T *>(FoldingSetBase::FindNodeOrInsertPos( |

500 | ID, InsertPos, Info: Derived::getFoldingSetInfo())); |

501 | } |

502 | |

503 | /// InsertNode - Insert the specified node into the folding set, knowing that |

504 | /// it is not already in the folding set. InsertPos must be obtained from |

505 | /// FindNodeOrInsertPos. |

506 | void InsertNode(T *N, void *InsertPos) { |

507 | FoldingSetBase::InsertNode(N, InsertPos, Info: Derived::getFoldingSetInfo()); |

508 | } |

509 | |

510 | /// InsertNode - Insert the specified node into the folding set, knowing that |

511 | /// it is not already in the folding set. |

512 | void InsertNode(T *N) { |

513 | T *Inserted = GetOrInsertNode(N); |

514 | (void)Inserted; |

515 | assert(Inserted == N && "Node already inserted!"); |

516 | } |

517 | }; |

518 | |

519 | //===----------------------------------------------------------------------===// |

520 | /// FoldingSet - This template class is used to instantiate a specialized |

521 | /// implementation of the folding set to the node class T. T must be a |

522 | /// subclass of FoldingSetNode and implement a Profile function. |

523 | /// |

524 | /// Note that this set type is movable and move-assignable. However, its |

525 | /// moved-from state is not a valid state for anything other than |

526 | /// move-assigning and destroying. This is primarily to enable movable APIs |

527 | /// that incorporate these objects. |

528 | template <class T> |

529 | class FoldingSet : public FoldingSetImpl<FoldingSet<T>, T> { |

530 | using Super = FoldingSetImpl<FoldingSet, T>; |

531 | using Node = typename Super::Node; |

532 | |

533 | /// GetNodeProfile - Each instantiation of the FoldingSet needs to provide a |

534 | /// way to convert nodes into a unique specifier. |

535 | static void GetNodeProfile(const FoldingSetBase *, Node *N, |

536 | FoldingSetNodeID &ID) { |

537 | T *TN = static_cast<T *>(N); |

538 | FoldingSetTrait<T>::Profile(*TN, ID); |

539 | } |

540 | |

541 | /// NodeEquals - Instantiations may optionally provide a way to compare a |

542 | /// node with a specified ID. |

543 | static bool NodeEquals(const FoldingSetBase *, Node *N, |

544 | const FoldingSetNodeID &ID, unsigned IDHash, |

545 | FoldingSetNodeID &TempID) { |

546 | T *TN = static_cast<T *>(N); |

547 | return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID); |

548 | } |

549 | |

550 | /// ComputeNodeHash - Instantiations may optionally provide a way to compute a |

551 | /// hash value directly from a node. |

552 | static unsigned ComputeNodeHash(const FoldingSetBase *, Node *N, |

553 | FoldingSetNodeID &TempID) { |

554 | T *TN = static_cast<T *>(N); |

555 | return FoldingSetTrait<T>::ComputeHash(*TN, TempID); |

556 | } |

557 | |

558 | static const FoldingSetBase::FoldingSetInfo &getFoldingSetInfo() { |

559 | static constexpr FoldingSetBase::FoldingSetInfo Info = { |

560 | GetNodeProfile, NodeEquals, ComputeNodeHash}; |

561 | return Info; |

562 | } |

563 | friend Super; |

564 | |

565 | public: |

566 | explicit FoldingSet(unsigned Log2InitSize = 6) : Super(Log2InitSize) {} |

567 | FoldingSet(FoldingSet &&Arg) = default; |

568 | FoldingSet &operator=(FoldingSet &&RHS) = default; |

569 | }; |

570 | |

571 | //===----------------------------------------------------------------------===// |

572 | /// ContextualFoldingSet - This template class is a further refinement |

573 | /// of FoldingSet which provides a context argument when calling |

574 | /// Profile on its nodes. Currently, that argument is fixed at |

575 | /// initialization time. |

576 | /// |

577 | /// T must be a subclass of FoldingSetNode and implement a Profile |

578 | /// function with signature |

579 | /// void Profile(FoldingSetNodeID &, Ctx); |

580 | template <class T, class Ctx> |

581 | class ContextualFoldingSet |

582 | : public FoldingSetImpl<ContextualFoldingSet<T, Ctx>, T> { |

583 | // Unfortunately, this can't derive from FoldingSet<T> because the |

584 | // construction of the vtable for FoldingSet<T> requires |

585 | // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn |

586 | // requires a single-argument T::Profile(). |

587 | |

588 | using Super = FoldingSetImpl<ContextualFoldingSet, T>; |

589 | using Node = typename Super::Node; |

590 | |

591 | Ctx Context; |

592 | |

593 | static const Ctx &getContext(const FoldingSetBase *Base) { |

594 | return static_cast<const ContextualFoldingSet*>(Base)->Context; |

595 | } |

596 | |

597 | /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a |

598 | /// way to convert nodes into a unique specifier. |

599 | static void GetNodeProfile(const FoldingSetBase *Base, Node *N, |

600 | FoldingSetNodeID &ID) { |

601 | T *TN = static_cast<T *>(N); |

602 | ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, getContext(Base)); |

603 | } |

604 | |

605 | static bool NodeEquals(const FoldingSetBase *Base, Node *N, |

606 | const FoldingSetNodeID &ID, unsigned IDHash, |

607 | FoldingSetNodeID &TempID) { |

608 | T *TN = static_cast<T *>(N); |

609 | return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID, |

610 | getContext(Base)); |

611 | } |

612 | |

613 | static unsigned ComputeNodeHash(const FoldingSetBase *Base, Node *N, |

614 | FoldingSetNodeID &TempID) { |

615 | T *TN = static_cast<T *>(N); |

616 | return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, |

617 | getContext(Base)); |

618 | } |

619 | |

620 | static const FoldingSetBase::FoldingSetInfo &getFoldingSetInfo() { |

621 | static constexpr FoldingSetBase::FoldingSetInfo Info = { |

622 | GetNodeProfile, NodeEquals, ComputeNodeHash}; |

623 | return Info; |

624 | } |

625 | friend Super; |

626 | |

627 | public: |

628 | explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6) |

629 | : Super(Log2InitSize), Context(Context) {} |

630 | |

631 | Ctx getContext() const { return Context; } |

632 | }; |

633 | |

634 | //===----------------------------------------------------------------------===// |

635 | /// FoldingSetVector - This template class combines a FoldingSet and a vector |

636 | /// to provide the interface of FoldingSet but with deterministic iteration |

637 | /// order based on the insertion order. T must be a subclass of FoldingSetNode |

638 | /// and implement a Profile function. |

639 | template <class T, class VectorT = SmallVector<T*, 8>> |

640 | class FoldingSetVector { |

641 | FoldingSet<T> Set; |

642 | VectorT Vector; |

643 | |

644 | public: |

645 | explicit FoldingSetVector(unsigned Log2InitSize = 6) : Set(Log2InitSize) {} |

646 | |

647 | using iterator = pointee_iterator<typename VectorT::iterator>; |

648 | |

649 | iterator begin() { return Vector.begin(); } |

650 | iterator end() { return Vector.end(); } |

651 | |

652 | using const_iterator = pointee_iterator<typename VectorT::const_iterator>; |

653 | |

654 | const_iterator begin() const { return Vector.begin(); } |

655 | const_iterator end() const { return Vector.end(); } |

656 | |

657 | /// clear - Remove all nodes from the folding set. |

658 | void clear() { Set.clear(); Vector.clear(); } |

659 | |

660 | /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, |

661 | /// return it. If not, return the insertion token that will make insertion |

662 | /// faster. |

663 | T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { |

664 | return Set.FindNodeOrInsertPos(ID, InsertPos); |

665 | } |

666 | |

667 | /// GetOrInsertNode - If there is an existing simple Node exactly |

668 | /// equal to the specified node, return it. Otherwise, insert 'N' and |

669 | /// return it instead. |

670 | T *GetOrInsertNode(T *N) { |

671 | T *Result = Set.GetOrInsertNode(N); |

672 | if (Result == N) Vector.push_back(N); |

673 | return Result; |

674 | } |

675 | |

676 | /// InsertNode - Insert the specified node into the folding set, knowing that |

677 | /// it is not already in the folding set. InsertPos must be obtained from |

678 | /// FindNodeOrInsertPos. |

679 | void InsertNode(T *N, void *InsertPos) { |

680 | Set.InsertNode(N, InsertPos); |

681 | Vector.push_back(N); |

682 | } |

683 | |

684 | /// InsertNode - Insert the specified node into the folding set, knowing that |

685 | /// it is not already in the folding set. |

686 | void InsertNode(T *N) { |

687 | Set.InsertNode(N); |

688 | Vector.push_back(N); |

689 | } |

690 | |

691 | /// size - Returns the number of nodes in the folding set. |

692 | unsigned size() const { return Set.size(); } |

693 | |

694 | /// empty - Returns true if there are no nodes in the folding set. |

695 | bool empty() const { return Set.empty(); } |

696 | }; |

697 | |

698 | //===----------------------------------------------------------------------===// |

699 | /// FoldingSetIteratorImpl - This is the common iterator support shared by all |

700 | /// folding sets, which knows how to walk the folding set hash table. |

701 | class FoldingSetIteratorImpl { |

702 | protected: |

703 | FoldingSetNode *NodePtr; |

704 | |

705 | FoldingSetIteratorImpl(void **Bucket); |

706 | |

707 | void advance(); |

708 | |

709 | public: |

710 | bool operator==(const FoldingSetIteratorImpl &RHS) const { |

711 | return NodePtr == RHS.NodePtr; |

712 | } |

713 | bool operator!=(const FoldingSetIteratorImpl &RHS) const { |

714 | return NodePtr != RHS.NodePtr; |

715 | } |

716 | }; |

717 | |

718 | template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl { |

719 | public: |

720 | explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {} |

721 | |

722 | T &operator*() const { |

723 | return *static_cast<T*>(NodePtr); |

724 | } |

725 | |

726 | T *operator->() const { |

727 | return static_cast<T*>(NodePtr); |

728 | } |

729 | |

730 | inline FoldingSetIterator &operator++() { // Preincrement |

731 | advance(); |

732 | return *this; |

733 | } |

734 | FoldingSetIterator operator++(int) { // Postincrement |

735 | FoldingSetIterator tmp = *this; ++*this; return tmp; |

736 | } |

737 | }; |

738 | |

739 | //===----------------------------------------------------------------------===// |

740 | /// FoldingSetBucketIteratorImpl - This is the common bucket iterator support |

741 | /// shared by all folding sets, which knows how to walk a particular bucket |

742 | /// of a folding set hash table. |

743 | class FoldingSetBucketIteratorImpl { |

744 | protected: |

745 | void *Ptr; |

746 | |

747 | explicit FoldingSetBucketIteratorImpl(void **Bucket); |

748 | |

749 | FoldingSetBucketIteratorImpl(void **Bucket, bool) : Ptr(Bucket) {} |

750 | |

751 | void advance() { |

752 | void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket(); |

753 | uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1; |

754 | Ptr = reinterpret_cast<void*>(x); |

755 | } |

756 | |

757 | public: |

758 | bool operator==(const FoldingSetBucketIteratorImpl &RHS) const { |

759 | return Ptr == RHS.Ptr; |

760 | } |

761 | bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const { |

762 | return Ptr != RHS.Ptr; |

763 | } |

764 | }; |

765 | |

766 | template <class T> |

767 | class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl { |

768 | public: |

769 | explicit FoldingSetBucketIterator(void **Bucket) : |

770 | FoldingSetBucketIteratorImpl(Bucket) {} |

771 | |

772 | FoldingSetBucketIterator(void **Bucket, bool) : |

773 | FoldingSetBucketIteratorImpl(Bucket, true) {} |

774 | |

775 | T &operator*() const { return *static_cast<T*>(Ptr); } |

776 | T *operator->() const { return static_cast<T*>(Ptr); } |

777 | |

778 | inline FoldingSetBucketIterator &operator++() { // Preincrement |

779 | advance(); |

780 | return *this; |

781 | } |

782 | FoldingSetBucketIterator operator++(int) { // Postincrement |

783 | FoldingSetBucketIterator tmp = *this; ++*this; return tmp; |

784 | } |

785 | }; |

786 | |

787 | //===----------------------------------------------------------------------===// |

788 | /// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary |

789 | /// types in an enclosing object so that they can be inserted into FoldingSets. |

790 | template <typename T> |

791 | class FoldingSetNodeWrapper : public FoldingSetNode { |

792 | T data; |

793 | |

794 | public: |

795 | template <typename... Ts> |

796 | explicit FoldingSetNodeWrapper(Ts &&... Args) |

797 | : data(std::forward<Ts>(Args)...) {} |

798 | |

799 | void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); } |

800 | |

801 | T &getValue() { return data; } |

802 | const T &getValue() const { return data; } |

803 | |

804 | operator T&() { return data; } |

805 | operator const T&() const { return data; } |

806 | }; |

807 | |

808 | //===----------------------------------------------------------------------===// |

809 | /// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores |

810 | /// a FoldingSetNodeID value rather than requiring the node to recompute it |

811 | /// each time it is needed. This trades space for speed (which can be |

812 | /// significant if the ID is long), and it also permits nodes to drop |

813 | /// information that would otherwise only be required for recomputing an ID. |

814 | class FastFoldingSetNode : public FoldingSetNode { |

815 | FoldingSetNodeID FastID; |

816 | |

817 | protected: |

818 | explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {} |

819 | |

820 | public: |

821 | void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(ID: FastID); } |

822 | }; |

823 | |

824 | //===----------------------------------------------------------------------===// |

825 | // Partial specializations of FoldingSetTrait. |

826 | |

827 | template<typename T> struct FoldingSetTrait<T*> { |

828 | static inline void Profile(T *X, FoldingSetNodeID &ID) { |

829 | ID.AddPointer(Ptr: X); |

830 | } |

831 | }; |

832 | template <typename T1, typename T2> |

833 | struct FoldingSetTrait<std::pair<T1, T2>> { |

834 | static inline void Profile(const std::pair<T1, T2> &P, |

835 | FoldingSetNodeID &ID) { |

836 | ID.Add(P.first); |

837 | ID.Add(P.second); |

838 | } |

839 | }; |

840 | |

841 | template <typename T> |

842 | struct FoldingSetTrait<T, std::enable_if_t<std::is_enum<T>::value>> { |

843 | static void Profile(const T &X, FoldingSetNodeID &ID) { |

844 | ID.AddInteger(llvm::to_underlying(X)); |

845 | } |

846 | }; |

847 | |

848 | } // end namespace llvm |

849 | |

850 | #endif // LLVM_ADT_FOLDINGSET_H |

851 |