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 | // This file defines a hash set that can be used to remove duplication of nodes |

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

11 | // SelectionDAGCSEMap, but was isolated to provide use across the llvm code set. |

12 | // |

13 | //===----------------------------------------------------------------------===// |

14 | |

15 | #ifndef LLVM_ADT_FOLDINGSET_H |

16 | #define LLVM_ADT_FOLDINGSET_H |

17 | |

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

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

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

21 | #include <cassert> |

22 | #include <cstddef> |

23 | #include <cstdint> |

24 | #include <utility> |

25 | |

26 | namespace llvm { |

27 | |

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

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

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

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

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

33 | /// |

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

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

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

37 | /// |

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

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

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

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

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

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

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

45 | /// |

46 | /// Eg. |

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

48 | /// private: |

49 | /// std::string Name; |

50 | /// unsigned Value; |

51 | /// public: |

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

53 | /// ... |

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

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

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

57 | /// } |

58 | /// ... |

59 | /// }; |

60 | /// |

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

62 | /// |

63 | /// Eg. |

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

65 | /// |

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

67 | /// |

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

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

70 | /// |

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

72 | /// |

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

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

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

76 | /// |

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

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

79 | /// check; |

80 | /// |

81 | /// FoldingSetNodeID ID; |

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

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

84 | /// void *InsertPoint; |

85 | /// |

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

87 | /// |

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

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

90 | /// |

91 | /// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new |

92 | /// node with FindNodeOrInsertPos; |

93 | /// |

94 | /// InsertNode(N, InsertPoint); |

95 | /// |

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

97 | /// |

98 | /// bool WasRemoved = RemoveNode(N); |

99 | /// |

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

101 | |

102 | class FoldingSetNodeID; |

103 | class StringRef; |

104 | |

105 | //===----------------------------------------------------------------------===// |

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

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

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

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

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

111 | /// |

112 | class FoldingSetBase { |

113 | virtual void anchor(); // Out of line virtual method. |

114 | |

115 | protected: |

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

117 | void **Buckets; |

118 | |

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

120 | unsigned NumBuckets; |

121 | |

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

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

124 | unsigned NumNodes; |

125 | |

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

127 | FoldingSetBase(FoldingSetBase &&Arg); |

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

129 | ~FoldingSetBase(); |

130 | |

131 | public: |

132 | //===--------------------------------------------------------------------===// |

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

134 | /// a folding set. |

135 | class Node { |

136 | private: |

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

138 | void *NextInFoldingSetBucket = nullptr; |

139 | |

140 | public: |

141 | Node() = default; |

142 | |

143 | // Accessors |

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

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

146 | }; |

147 | |

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

149 | void clear(); |

150 | |

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

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

153 | |

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

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

156 | |

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

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

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

160 | void reserve(unsigned EltCount); |

161 | |

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

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

164 | unsigned capacity() { |

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

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

167 | return NumBuckets * 2; |

168 | } |

169 | |

170 | private: |

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

172 | void GrowHashTable(); |

173 | |

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

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

176 | /// bucket count. |

177 | void GrowBucketCount(unsigned NewBucketCount); |

178 | |

179 | protected: |

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

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

182 | virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0; |

183 | |

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

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

186 | virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, |

187 | FoldingSetNodeID &TempID) const=0; |

188 | |

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

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

191 | virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0; |

192 | |

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

194 | // type-safe API. |

195 | |

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

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

198 | bool RemoveNode(Node *N); |

199 | |

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

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

202 | /// it instead. |

203 | Node *GetOrInsertNode(Node *N); |

204 | |

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

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

207 | /// faster. |

208 | Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos); |

209 | |

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

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

212 | /// FindNodeOrInsertPos. |

213 | void InsertNode(Node *N, void *InsertPos); |

214 | }; |

215 | |

216 | //===----------------------------------------------------------------------===// |

217 | |

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

219 | /// for FoldingSetTrait implementations. |

220 | template<typename T> struct DefaultFoldingSetTrait { |

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

222 | X.Profile(ID); |

223 | } |

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

225 | X.Profile(ID); |

226 | } |

227 | |

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

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

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

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

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

233 | FoldingSetNodeID &TempID); |

234 | |

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

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

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

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

239 | // implementations. |

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

241 | }; |

242 | |

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

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

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

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

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

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

249 | template<typename T> struct FoldingSetTrait |

250 | : public DefaultFoldingSetTrait<T> {}; |

251 | |

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

253 | /// for ContextualFoldingSets. |

254 | template<typename T, typename Ctx> |

255 | struct DefaultContextualFoldingSetTrait { |

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

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

258 | } |

259 | |

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

261 | FoldingSetNodeID &TempID, Ctx Context); |

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

263 | Ctx Context); |

264 | }; |

265 | |

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

267 | /// ContextualFoldingSets. |

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

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

270 | |

271 | //===--------------------------------------------------------------------===// |

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

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

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

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

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

277 | class FoldingSetNodeIDRef { |

278 | const unsigned *Data = nullptr; |

279 | size_t Size = 0; |

280 | |

281 | public: |

282 | FoldingSetNodeIDRef() = default; |

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

284 | |

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

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

287 | unsigned ComputeHash() const; |

288 | |

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

290 | |

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

292 | |

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

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

295 | bool operator<(FoldingSetNodeIDRef) const; |

296 | |

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

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

299 | }; |

300 | |

301 | //===--------------------------------------------------------------------===// |

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

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

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

305 | class FoldingSetNodeID { |

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

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

308 | SmallVector<unsigned, 32> Bits; |

309 | |

310 | public: |

311 | FoldingSetNodeID() = default; |

312 | |

313 | FoldingSetNodeID(FoldingSetNodeIDRef Ref) |

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

315 | |

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

317 | void AddPointer(const void *Ptr); |

318 | void AddInteger(signed I); |

319 | void AddInteger(unsigned I); |

320 | void AddInteger(long I); |

321 | void AddInteger(unsigned long I); |

322 | void AddInteger(long long I); |

323 | void AddInteger(unsigned long long I); |

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

325 | void AddString(StringRef String); |

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

327 | |

328 | template <typename T> |

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

330 | |

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

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

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

334 | |

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

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

337 | unsigned ComputeHash() const; |

338 | |

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

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

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

342 | |

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

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

345 | |

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

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

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

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

350 | |

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

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

353 | /// interned data. |

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

355 | }; |

356 | |

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

358 | using FoldingSetNode = FoldingSetBase::Node; |

359 | template<class T> class FoldingSetIterator; |

360 | template<class T> class FoldingSetBucketIterator; |

361 | |

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

363 | // require the definition of FoldingSetNodeID. |

364 | template<typename T> |

365 | inline bool |

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

367 | unsigned /*IDHash*/, |

368 | FoldingSetNodeID &TempID) { |

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

370 | return TempID == ID; |

371 | } |

372 | template<typename T> |

373 | inline unsigned |

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

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

376 | return TempID.ComputeHash(); |

377 | } |

378 | template<typename T, typename Ctx> |

379 | inline bool |

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

381 | const FoldingSetNodeID &ID, |

382 | unsigned /*IDHash*/, |

383 | FoldingSetNodeID &TempID, |

384 | Ctx Context) { |

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

386 | return TempID == ID; |

387 | } |

388 | template<typename T, typename Ctx> |

389 | inline unsigned |

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

391 | FoldingSetNodeID &TempID, |

392 | Ctx Context) { |

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

394 | return TempID.ComputeHash(); |

395 | } |

396 | |

397 | //===----------------------------------------------------------------------===// |

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

399 | /// FoldingSet and ContextualFoldingSet. |

400 | template <class T> class FoldingSetImpl : public FoldingSetBase { |

401 | protected: |

402 | explicit FoldingSetImpl(unsigned Log2InitSize) |

403 | : FoldingSetBase(Log2InitSize) {} |

404 | |

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

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

407 | ~FoldingSetImpl() = default; |

408 | |

409 | public: |

410 | using iterator = FoldingSetIterator<T>; |

411 | |

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

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

414 | |

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

416 | |

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

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

419 | |

420 | using bucket_iterator = FoldingSetBucketIterator<T>; |

421 | |

422 | bucket_iterator bucket_begin(unsigned hash) { |

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

424 | } |

425 | |

426 | bucket_iterator bucket_end(unsigned hash) { |

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

428 | } |

429 | |

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

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

432 | bool RemoveNode(T *N) { return FoldingSetBase::RemoveNode(N); } |

433 | |

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

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

436 | /// return it instead. |

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

438 | return static_cast<T *>(FoldingSetBase::GetOrInsertNode(N)); |

439 | } |

440 | |

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

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

443 | /// faster. |

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

445 | return static_cast<T *>(FoldingSetBase::FindNodeOrInsertPos(ID, InsertPos)); |

446 | } |

447 | |

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

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

450 | /// FindNodeOrInsertPos. |

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

452 | FoldingSetBase::InsertNode(N, InsertPos); |

453 | } |

454 | |

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

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

457 | void InsertNode(T *N) { |

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

459 | (void)Inserted; |

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

461 | } |

462 | }; |

463 | |

464 | //===----------------------------------------------------------------------===// |

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

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

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

468 | /// |

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

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

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

472 | /// that incorporate these objects. |

473 | template <class T> class FoldingSet final : public FoldingSetImpl<T> { |

474 | using Super = FoldingSetImpl<T>; |

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

476 | |

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

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

479 | void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override { |

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

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

482 | } |

483 | |

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

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

486 | bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, |

487 | FoldingSetNodeID &TempID) const override { |

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

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

490 | } |

491 | |

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

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

494 | unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override { |

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

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

497 | } |

498 | |

499 | public: |

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

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

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

503 | }; |

504 | |

505 | //===----------------------------------------------------------------------===// |

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

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

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

509 | /// initialization time. |

510 | /// |

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

512 | /// function with signature |

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

514 | template <class T, class Ctx> |

515 | class ContextualFoldingSet final : public FoldingSetImpl<T> { |

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

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

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

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

520 | |

521 | using Super = FoldingSetImpl<T>; |

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

523 | |

524 | Ctx Context; |

525 | |

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

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

528 | void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override { |

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

530 | ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context); |

531 | } |

532 | |

533 | bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, |

534 | FoldingSetNodeID &TempID) const override { |

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

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

537 | Context); |

538 | } |

539 | |

540 | unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override { |

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

542 | return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context); |

543 | } |

544 | |

545 | public: |

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

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

548 | |

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

550 | }; |

551 | |

552 | //===----------------------------------------------------------------------===// |

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

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

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

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

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

558 | class FoldingSetVector { |

559 | FoldingSet<T> Set; |

560 | VectorT Vector; |

561 | |

562 | public: |

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

564 | |

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

566 | |

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

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

569 | |

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

571 | |

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

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

574 | |

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

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

577 | |

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

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

580 | /// faster. |

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

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

583 | } |

584 | |

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

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

587 | /// return it instead. |

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

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

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

591 | return Result; |

592 | } |

593 | |

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

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

596 | /// FindNodeOrInsertPos. |

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

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

599 | Vector.push_back(N); |

600 | } |

601 | |

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

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

604 | void InsertNode(T *N) { |

605 | Set.InsertNode(N); |

606 | Vector.push_back(N); |

607 | } |

608 | |

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

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

611 | |

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

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

614 | }; |

615 | |

616 | //===----------------------------------------------------------------------===// |

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

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

619 | class FoldingSetIteratorImpl { |

620 | protected: |

621 | FoldingSetNode *NodePtr; |

622 | |

623 | FoldingSetIteratorImpl(void **Bucket); |

624 | |

625 | void advance(); |

626 | |

627 | public: |

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

629 | return NodePtr == RHS.NodePtr; |

630 | } |

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

632 | return NodePtr != RHS.NodePtr; |

633 | } |

634 | }; |

635 | |

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

637 | public: |

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

639 | |

640 | T &operator*() const { |

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

642 | } |

643 | |

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

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

646 | } |

647 | |

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

649 | advance(); |

650 | return *this; |

651 | } |

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

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

654 | } |

655 | }; |

656 | |

657 | //===----------------------------------------------------------------------===// |

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

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

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

661 | class FoldingSetBucketIteratorImpl { |

662 | protected: |

663 | void *Ptr; |

664 | |

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

666 | |

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

668 | |

669 | void advance() { |

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

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

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

673 | } |

674 | |

675 | public: |

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

677 | return Ptr == RHS.Ptr; |

678 | } |

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

680 | return Ptr != RHS.Ptr; |

681 | } |

682 | }; |

683 | |

684 | template <class T> |

685 | class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl { |

686 | public: |

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

688 | FoldingSetBucketIteratorImpl(Bucket) {} |

689 | |

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

691 | FoldingSetBucketIteratorImpl(Bucket, true) {} |

692 | |

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

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

695 | |

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

697 | advance(); |

698 | return *this; |

699 | } |

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

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

702 | } |

703 | }; |

704 | |

705 | //===----------------------------------------------------------------------===// |

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

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

708 | template <typename T> |

709 | class FoldingSetNodeWrapper : public FoldingSetNode { |

710 | T data; |

711 | |

712 | public: |

713 | template <typename... Ts> |

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

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

716 | |

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

718 | |

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

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

721 | |

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

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

724 | }; |

725 | |

726 | //===----------------------------------------------------------------------===// |

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

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

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

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

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

732 | class FastFoldingSetNode : public FoldingSetNode { |

733 | FoldingSetNodeID FastID; |

734 | |

735 | protected: |

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

737 | |

738 | public: |

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

740 | }; |

741 | |

742 | //===----------------------------------------------------------------------===// |

743 | // Partial specializations of FoldingSetTrait. |

744 | |

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

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

747 | ID.AddPointer(X); |

748 | } |

749 | }; |

750 | template <typename T1, typename T2> |

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

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

753 | FoldingSetNodeID &ID) { |

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

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

756 | } |

757 | }; |

758 | |

759 | } // end namespace llvm |

760 | |

761 | #endif // LLVM_ADT_FOLDINGSET_H |

762 |