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 will 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 insert a |

92 | /// new node with InsertNode; |

93 | /// |

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

95 | /// |

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

97 | /// |

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

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 | protected: |

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

115 | void **Buckets; |

116 | |

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

118 | unsigned NumBuckets; |

119 | |

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

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

122 | unsigned NumNodes; |

123 | |

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

125 | FoldingSetBase(FoldingSetBase &&Arg); |

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

127 | ~FoldingSetBase(); |

128 | |

129 | public: |

130 | //===--------------------------------------------------------------------===// |

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

132 | /// a folding set. |

133 | class Node { |

134 | private: |

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

136 | void *NextInFoldingSetBucket = nullptr; |

137 | |

138 | public: |

139 | Node() = default; |

140 | |

141 | // Accessors |

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

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

144 | }; |

145 | |

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

147 | void clear(); |

148 | |

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

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

151 | |

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

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

154 | |

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

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

157 | unsigned capacity() { |

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

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

160 | return NumBuckets * 2; |

161 | } |

162 | |

163 | protected: |

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

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

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

167 | struct FoldingSetInfo { |

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

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

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

171 | FoldingSetNodeID &ID); |

172 | |

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

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

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

176 | const FoldingSetNodeID &ID, unsigned IDHash, |

177 | FoldingSetNodeID &TempID); |

178 | |

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

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

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

182 | FoldingSetNodeID &TempID); |

183 | }; |

184 | |

185 | private: |

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

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

188 | |

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

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

191 | /// bucket count. |

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

193 | |

194 | protected: |

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

196 | // type-safe API. |

197 | |

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

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

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

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

202 | |

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

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

205 | bool RemoveNode(Node *N); |

206 | |

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

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

209 | /// it instead. |

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

211 | |

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

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

214 | /// faster. |

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

216 | const FoldingSetInfo &Info); |

217 | |

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

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

220 | /// FindNodeOrInsertPos. |

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

222 | }; |

223 | |

224 | //===----------------------------------------------------------------------===// |

225 | |

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

227 | /// for FoldingSetTrait implementations. |

228 | template<typename T> struct DefaultFoldingSetTrait { |

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

230 | X.Profile(ID); |

231 | } |

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

233 | X.Profile(ID); |

234 | } |

235 | |

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

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

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

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

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

241 | FoldingSetNodeID &TempID); |

242 | |

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

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

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

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

247 | // implementations. |

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

249 | }; |

250 | |

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

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

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

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

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

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

257 | template<typename T> struct FoldingSetTrait |

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

259 | |

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

261 | /// for ContextualFoldingSets. |

262 | template<typename T, typename Ctx> |

263 | struct DefaultContextualFoldingSetTrait { |

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

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

266 | } |

267 | |

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

269 | FoldingSetNodeID &TempID, Ctx Context); |

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

271 | Ctx Context); |

272 | }; |

273 | |

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

275 | /// ContextualFoldingSets. |

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

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

278 | |

279 | //===--------------------------------------------------------------------===// |

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

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

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

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

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

285 | class FoldingSetNodeIDRef { |

286 | const unsigned *Data = nullptr; |

287 | size_t Size = 0; |

288 | |

289 | public: |

290 | FoldingSetNodeIDRef() = default; |

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

292 | |

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

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

295 | unsigned ComputeHash() const; |

296 | |

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

298 | |

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

300 | |

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

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

303 | bool operator<(FoldingSetNodeIDRef) const; |

304 | |

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

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

307 | }; |

308 | |

309 | //===--------------------------------------------------------------------===// |

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

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

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

313 | class FoldingSetNodeID { |

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

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

316 | SmallVector<unsigned, 32> Bits; |

317 | |

318 | public: |

319 | FoldingSetNodeID() = default; |

320 | |

321 | FoldingSetNodeID(FoldingSetNodeIDRef Ref) |

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

323 | |

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

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

326 | void AddInteger(signed I); |

327 | void AddInteger(unsigned I); |

328 | void AddInteger(long I); |

329 | void AddInteger(unsigned long I); |

330 | void AddInteger(long long I); |

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

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

333 | void AddString(StringRef String); |

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

335 | |

336 | template <typename T> |

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

338 | |

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

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

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

342 | |

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

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

345 | unsigned ComputeHash() const; |

346 | |

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

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

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

350 | |

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

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

353 | |

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

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

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

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

358 | |

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

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

361 | /// interned data. |

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

363 | }; |

364 | |

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

366 | using FoldingSetNode = FoldingSetBase::Node; |

367 | template<class T> class FoldingSetIterator; |

368 | template<class T> class FoldingSetBucketIterator; |

369 | |

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

371 | // require the definition of FoldingSetNodeID. |

372 | template<typename T> |

373 | inline bool |

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

375 | unsigned /*IDHash*/, |

376 | FoldingSetNodeID &TempID) { |

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

378 | return TempID == ID; |

379 | } |

380 | template<typename T> |

381 | inline unsigned |

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

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

384 | return TempID.ComputeHash(); |

385 | } |

386 | template<typename T, typename Ctx> |

387 | inline bool |

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

389 | const FoldingSetNodeID &ID, |

390 | unsigned /*IDHash*/, |

391 | FoldingSetNodeID &TempID, |

392 | Ctx Context) { |

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

394 | return TempID == ID; |

395 | } |

396 | template<typename T, typename Ctx> |

397 | inline unsigned |

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

399 | FoldingSetNodeID &TempID, |

400 | Ctx Context) { |

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

402 | return TempID.ComputeHash(); |

403 | } |

404 | |

405 | //===----------------------------------------------------------------------===// |

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

407 | /// FoldingSet and ContextualFoldingSet. |

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

409 | protected: |

410 | explicit FoldingSetImpl(unsigned Log2InitSize) |

411 | : FoldingSetBase(Log2InitSize) {} |

412 | |

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

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

415 | ~FoldingSetImpl() = default; |

416 | |

417 | public: |

418 | using iterator = FoldingSetIterator<T>; |

419 | |

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

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

422 | |

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

424 | |

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

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

427 | |

428 | using bucket_iterator = FoldingSetBucketIterator<T>; |

429 | |

430 | bucket_iterator bucket_begin(unsigned hash) { |

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

432 | } |

433 | |

434 | bucket_iterator bucket_end(unsigned hash) { |

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

436 | } |

437 | |

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

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

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

441 | void reserve(unsigned EltCount) { |

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

443 | } |

444 | |

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

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

447 | bool RemoveNode(T *N) { |

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

449 | } |

450 | |

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

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

453 | /// return it instead. |

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

455 | return static_cast<T *>( |

456 | FoldingSetBase::GetOrInsertNode(N, Derived::getFoldingSetInfo())); |

457 | } |

458 | |

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

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

461 | /// faster. |

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

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

464 | ID, InsertPos, Derived::getFoldingSetInfo())); |

465 | } |

466 | |

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

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

469 | /// FindNodeOrInsertPos. |

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

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

472 | } |

473 | |

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

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

476 | void InsertNode(T *N) { |

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

478 | (void)Inserted; |

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

480 | } |

481 | }; |

482 | |

483 | //===----------------------------------------------------------------------===// |

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

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

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

487 | /// |

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

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

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

491 | /// that incorporate these objects. |

492 | template <class T> |

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

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

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

496 | |

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

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

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

500 | FoldingSetNodeID &ID) { |

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

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

503 | } |

504 | |

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

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

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

508 | const FoldingSetNodeID &ID, unsigned IDHash, |

509 | FoldingSetNodeID &TempID) { |

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

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

512 | } |

513 | |

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

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

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

517 | FoldingSetNodeID &TempID) { |

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

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

520 | } |

521 | |

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

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

524 | GetNodeProfile, NodeEquals, ComputeNodeHash}; |

525 | return Info; |

526 | } |

527 | friend Super; |

528 | |

529 | public: |

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

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

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

533 | }; |

534 | |

535 | //===----------------------------------------------------------------------===// |

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

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

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

539 | /// initialization time. |

540 | /// |

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

542 | /// function with signature |

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

544 | template <class T, class Ctx> |

545 | class ContextualFoldingSet |

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

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

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

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

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

551 | |

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

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

554 | |

555 | Ctx Context; |

556 | |

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

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

559 | } |

560 | |

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

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

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

564 | FoldingSetNodeID &ID) { |

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

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

567 | } |

568 | |

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

570 | const FoldingSetNodeID &ID, unsigned IDHash, |

571 | FoldingSetNodeID &TempID) { |

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

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

574 | getContext(Base)); |

575 | } |

576 | |

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

578 | FoldingSetNodeID &TempID) { |

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

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

581 | getContext(Base)); |

582 | } |

583 | |

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

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

586 | GetNodeProfile, NodeEquals, ComputeNodeHash}; |

587 | return Info; |

588 | } |

589 | friend Super; |

590 | |

591 | public: |

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

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

594 | |

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

596 | }; |

597 | |

598 | //===----------------------------------------------------------------------===// |

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

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

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

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

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

604 | class FoldingSetVector { |

605 | FoldingSet<T> Set; |

606 | VectorT Vector; |

607 | |

608 | public: |

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

610 | |

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

612 | |

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

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

615 | |

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

617 | |

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

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

620 | |

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

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

623 | |

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

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

626 | /// faster. |

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

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

629 | } |

630 | |

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

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

633 | /// return it instead. |

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

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

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

637 | return Result; |

638 | } |

639 | |

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

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

642 | /// FindNodeOrInsertPos. |

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

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

645 | Vector.push_back(N); |

646 | } |

647 | |

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

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

650 | void InsertNode(T *N) { |

651 | Set.InsertNode(N); |

652 | Vector.push_back(N); |

653 | } |

654 | |

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

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

657 | |

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

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

660 | }; |

661 | |

662 | //===----------------------------------------------------------------------===// |

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

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

665 | class FoldingSetIteratorImpl { |

666 | protected: |

667 | FoldingSetNode *NodePtr; |

668 | |

669 | FoldingSetIteratorImpl(void **Bucket); |

670 | |

671 | void advance(); |

672 | |

673 | public: |

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

675 | return NodePtr == RHS.NodePtr; |

676 | } |

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

678 | return NodePtr != RHS.NodePtr; |

679 | } |

680 | }; |

681 | |

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

683 | public: |

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

685 | |

686 | T &operator*() const { |

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

688 | } |

689 | |

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

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

692 | } |

693 | |

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

695 | advance(); |

696 | return *this; |

697 | } |

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

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

700 | } |

701 | }; |

702 | |

703 | //===----------------------------------------------------------------------===// |

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

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

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

707 | class FoldingSetBucketIteratorImpl { |

708 | protected: |

709 | void *Ptr; |

710 | |

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

712 | |

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

714 | |

715 | void advance() { |

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

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

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

719 | } |

720 | |

721 | public: |

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

723 | return Ptr == RHS.Ptr; |

724 | } |

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

726 | return Ptr != RHS.Ptr; |

727 | } |

728 | }; |

729 | |

730 | template <class T> |

731 | class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl { |

732 | public: |

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

734 | FoldingSetBucketIteratorImpl(Bucket) {} |

735 | |

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

737 | FoldingSetBucketIteratorImpl(Bucket, true) {} |

738 | |

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

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

741 | |

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

743 | advance(); |

744 | return *this; |

745 | } |

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

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

748 | } |

749 | }; |

750 | |

751 | //===----------------------------------------------------------------------===// |

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

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

754 | template <typename T> |

755 | class FoldingSetNodeWrapper : public FoldingSetNode { |

756 | T data; |

757 | |

758 | public: |

759 | template <typename... Ts> |

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

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

762 | |

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

764 | |

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

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

767 | |

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

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

770 | }; |

771 | |

772 | //===----------------------------------------------------------------------===// |

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

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

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

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

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

778 | class FastFoldingSetNode : public FoldingSetNode { |

779 | FoldingSetNodeID FastID; |

780 | |

781 | protected: |

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

783 | |

784 | public: |

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

786 | }; |

787 | |

788 | //===----------------------------------------------------------------------===// |

789 | // Partial specializations of FoldingSetTrait. |

790 | |

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

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

793 | ID.AddPointer(X); |

794 | } |

795 | }; |

796 | template <typename T1, typename T2> |

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

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

799 | FoldingSetNodeID &ID) { |

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

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

802 | } |

803 | }; |

804 | |

805 | } // end namespace llvm |

806 | |

807 | #endif // LLVM_ADT_FOLDINGSET_H |

808 |