FoldingSet.h Source File (original) (raw)

16#ifndef LLVM_ADT_FOLDINGSET_H

17#define LLVM_ADT_FOLDINGSET_H

25#include

26#include

27#include

28#include <type_traits>

29#include

31namespace llvm {

100

101

102

103

104

105

106

107class FoldingSetNodeID;

108class StringRef;

109

110

111

112

113

114

115

116

118protected:

119

121

122

124

125

126

128

133

134public:

135

136

137

139 private:

140

141 void *NextInFoldingSetBucket = nullptr;

142

143 public:

145

146

149 };

150

151

153

154

156

157

159

160

161

163

164

166 }

167

168protected:

169

170

171

173

174

177

178

179

183

184

185

188 };

189

190private:

191

193

194

195

196

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

198

199protected:

200

201

202

203

204

205

207

208

209

211

212

213

214

216

217

218

219

222

223

224

225

227};

228

229

230

231

232

235 X.Profile(ID);

236 }

238 X.Profile(ID);

239 }

240

241

242

243

244

247

248

249

250

251

252

254};

255

256

257

258

259

260

261

262template <typename T, typename Enable = void>

264

265

266

267template<typename T, typename Ctx>

270 X.Profile(ID, Context);

271 }

272

276 Ctx Context);

277};

278

279

280

283

284

285

286

287

288

289

291 const unsigned *Data = nullptr;

292 size_t Size = 0;

293

294public:

297

298

299

302 }

303

304

305

308 reinterpret_cast<const uint8_t *>(Data), sizeof(unsigned) * Size)));

309 }

310

312

314

315

316

318

319 const unsigned *getData() const { return Data; }

320 size_t getSize() const { return Size; }

321};

322

323

324

325

326

328

329

331

332public:

334

337

338

340

341

342

343

344 static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),

345 "unexpected pointer size");

347 }

352 if (sizeof(long) == sizeof(int))

354 else if (sizeof(long) == sizeof(long long)) {

356 } else {

358 }

359 }

364 }

365

369

370 template

372

373

374

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

376

377

378

379

382 }

383

384

385

388 }

389

390

393

396

397

398

401

402

403

404

406};

407

408

412

413

414

415template

416inline bool

418 unsigned ,

421 return TempID == ID;

422}

423template

424inline unsigned

428}

429template<typename T, typename Ctx>

430inline bool

433 unsigned ,

435 Ctx Context) {

437 return TempID == ID;

438}

439template<typename T, typename Ctx>

440inline unsigned

443 Ctx Context) {

446}

447

448

449

450

452protected:

455

459

460public:

462

465

467

470

472

475 }

476

479 }

480

481

482

483

486 }

487

488

489

492 }

493

494

495

496

498 return static_cast<T *>(

500 }

501

502

503

504

507 ID, InsertPos, Derived::getFoldingSetInfo()));

508 }

509

510

511

512

515 }

516

517

518

521 (void)Inserted;

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

523 }

524};

525

526

527

528

529

530

531

532

533

534

535template

539

540

541

544 T *TN = static_cast<T *>(N);

546 }

547

548

549

553 T *TN = static_cast<T *>(N);

555 }

556

557

558

561 T *TN = static_cast<T *>(N);

563 }

564

567 GetNodeProfile, NodeEquals, ComputeNodeHash};

569 }

571

572public:

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

576};

577

578

579

580

581

582

583

584

585

586

587template <class T, class Ctx>

589 : public FoldingSetImpl<ContextualFoldingSet<T, Ctx>, T> {

590

591

592

593

594

597

598 Ctx Context;

599

602 }

603

604

605

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

610 }

611

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

618 }

619

622 T *TN = static_cast<T *>(N);

625 }

626

629 GetNodeProfile, NodeEquals, ComputeNodeHash};

631 }

633

634public:

636 : Super(Log2InitSize), Context(Context) {}

637

639};

640

641

642

643

644

645

646template <class T, class VectorT = SmallVector<T*, 8>>

649 VectorT Vector;

650

651public:

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

653

655

658

660

663

664

666

667

668

669

671 return Set.FindNodeOrInsertPos(ID, InsertPos);

672 }

673

674

675

676

678 T *Result = Set.GetOrInsertNode(N);

679 if (Result == N) Vector.push_back(N);

680 return Result;

681 }

682

683

684

685

687 Set.InsertNode(N, InsertPos);

689 }

690

691

692

694 Set.InsertNode(N);

696 }

697

698

699 unsigned size() const { return Set.size(); }

700

701

702 bool empty() const { return Set.empty(); }

703};

704

705

706

707

709protected:

711

713

715

716public:

719 }

722 }

723};

724

726public:

728

730 return *static_cast<T*>(NodePtr);

731 }

732

734 return static_cast<T*>(NodePtr);

735 }

736

739 return *this;

740 }

743 }

744};

745

746

747

748

749

751protected:

753

755

757

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

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

761 Ptr = reinterpret_cast<void*>(x);

762 }

763

764public:

766 return Ptr == RHS.Ptr;

767 }

769 return Ptr != RHS.Ptr;

770 }

771};

772

773template

775public:

778

781

784

787 return *this;

788 }

791 }

792};

793

794

795

796

797template

799 T data;

800

801public:

802 template <typename... Ts>

804 : data(std::forward(Args)...) {}

805

807

810

811 operator T&() { return data; }

812 operator const T&() const { return data; }

813};

814

815

816

817

818

819

820

823

824protected:

826

827public:

829};

830

831

832

833

836 ID.AddPointer(X);

837 }

838};

839template <typename T1, typename T2>

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

843 ID.Add(P.first);

844 ID.Add(P.second);

845 }

846};

847

848template

852 }

853};

854

855}

856

857#endif

This file defines the BumpPtrAllocator interface.

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

Analysis containing CSE Info

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file contains library features backported from future STL versions.

This file defines the SmallVector class.

static unsigned getSize(unsigned Kind)

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Allocate memory in an ever growing pool, as if by bump-pointer.

ContextualFoldingSet - This template class is a further refinement of FoldingSet which provides a con...

ContextualFoldingSet(Ctx Context, unsigned Log2InitSize=6)

FastFoldingSetNode - This is a subclass of FoldingSetNode which stores a FoldingSetNodeID value rathe...

FastFoldingSetNode(const FoldingSetNodeID &ID)

void Profile(FoldingSetNodeID &ID) const

Node - This class is used to maintain the singly linked bucket list in a folding set.

void * getNextInBucket() const

void SetNextInBucket(void *N)

FoldingSetBase - Implements the folding set functionality.

void ** Buckets

Buckets - Array of bucket chains.

unsigned size() const

size - Returns the number of nodes in the folding set.

void reserve(unsigned EltCount, const FoldingSetInfo &Info)

reserve - Increase the number of buckets such that adding the EltCount-th node won't cause a rebucket...

bool RemoveNode(Node *N)

RemoveNode - Remove a node from the folding set, returning true if one was removed or false if the no...

FoldingSetBase & operator=(FoldingSetBase &&RHS)

unsigned NumBuckets

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

unsigned NumNodes

NumNodes - Number of nodes in the folding set.

unsigned capacity()

capacity - Returns the number of nodes permitted in the folding set before a rebucket operation is pe...

Node * GetOrInsertNode(Node *N, const FoldingSetInfo &Info)

GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...

bool empty() const

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

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

InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...

void clear()

clear - Remove all nodes from the folding set.

Node * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos, const FoldingSetInfo &Info)

FindNodeOrInsertPos - Look up the node specified by ID.

FoldingSetBucketIteratorImpl - This is the common bucket iterator support shared by all folding sets,...

FoldingSetBucketIteratorImpl(void **Bucket, bool)

bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const

bool operator==(const FoldingSetBucketIteratorImpl &RHS) const

FoldingSetBucketIterator(void **Bucket, bool)

FoldingSetBucketIterator(void **Bucket)

FoldingSetBucketIterator operator++(int)

FoldingSetBucketIterator & operator++()

FoldingSetImpl - An implementation detail that lets us share code between FoldingSet and ContextualFo...

void reserve(unsigned EltCount)

reserve - Increase the number of buckets such that adding the EltCount-th node won't cause a rebucket...

FoldingSetIterator< T > iterator

const_iterator end() const

bucket_iterator bucket_begin(unsigned hash)

bool RemoveNode(T *N)

RemoveNode - Remove a node from the folding set, returning true if one was removed or false if the no...

~FoldingSetImpl()=default

FoldingSetImpl(FoldingSetImpl &&Arg)=default

FoldingSetBucketIterator< T > bucket_iterator

void InsertNode(T *N)

InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...

void InsertNode(T *N, void *InsertPos)

InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...

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

FindNodeOrInsertPos - Look up the node specified by ID.

const_iterator begin() const

FoldingSetIterator< const T > const_iterator

FoldingSetImpl & operator=(FoldingSetImpl &&RHS)=default

T * GetOrInsertNode(T *N)

GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...

FoldingSetImpl(unsigned Log2InitSize)

bucket_iterator bucket_end(unsigned hash)

FoldingSetIteratorImpl - This is the common iterator support shared by all folding sets,...

bool operator==(const FoldingSetIteratorImpl &RHS) const

bool operator!=(const FoldingSetIteratorImpl &RHS) const

FoldingSetIterator(void **Bucket)

FoldingSetIterator operator++(int)

FoldingSetIterator & operator++()

FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...

unsigned computeStableHash() const

FoldingSetNodeIDRef(const unsigned *D, size_t S)

bool operator<(FoldingSetNodeIDRef) const

Used to compare the "ordering" of two nodes as defined by the profiled bits and their ordering define...

bool operator!=(FoldingSetNodeIDRef RHS) const

unsigned ComputeHash() const

FoldingSetNodeIDRef()=default

const unsigned * getData() const

FoldingSetNodeID - This class is used to gather all the unique data bits of a node.

FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const

Intern - Copy this node's data to a memory region allocated from the given allocator and return a Fol...

void AddInteger(signed I)

void AddInteger(unsigned long I)

FoldingSetNodeID(FoldingSetNodeIDRef Ref)

unsigned computeStableHash() const

void AddPointer(const void *Ptr)

Add* - Add various data types to Bit data.

bool operator!=(const FoldingSetNodeIDRef RHS) const

void clear()

clear - Clear the accumulated profile, allowing this FoldingSetNodeID object to be used to compute a ...

void AddInteger(unsigned I)

FoldingSetNodeID()=default

bool operator!=(const FoldingSetNodeID &RHS) const

void AddInteger(unsigned long long I)

void AddInteger(long long I)

unsigned ComputeHash() const

bool operator<(const FoldingSetNodeID &RHS) const

Used to compare the "ordering" of two nodes as defined by the profiled bits and their ordering define...

void AddNodeID(const FoldingSetNodeID &ID)

void AddString(StringRef String)

Add* - Add various data types to Bit data.

FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary types in an enclosing object ...

FoldingSetNodeWrapper(Ts &&... Args)

const T & getValue() const

void Profile(FoldingSetNodeID &ID)

FoldingSetVector - This template class combines a FoldingSet and a vector to provide the interface of...

T * GetOrInsertNode(T *N)

GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...

const_iterator end() const

void InsertNode(T *N)

InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...

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

FindNodeOrInsertPos - Look up the node specified by ID.

unsigned size() const

size - Returns the number of nodes in the folding set.

void clear()

clear - Remove all nodes from the folding set.

bool empty() const

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

FoldingSetVector(unsigned Log2InitSize=6)

void InsertNode(T *N, void *InsertPos)

InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...

const_iterator begin() const

FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...

FoldingSet(FoldingSet &&Arg)=default

FoldingSet(unsigned Log2InitSize=6)

FoldingSet & operator=(FoldingSet &&RHS)=default

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

This is an optimization pass for GlobalISel generic memory operations.

uint64_t xxh3_64bits(ArrayRef< uint8_t > data)

constexpr std::underlying_type_t< Enum > to_underlying(Enum E)

Returns underlying integer value of an enum.

@ Ref

The access may reference the value stored in memory.

hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)

Compute a hash_code for a sequence of values.

Implement std::hash so that hash_code can be used in STL containers.

ContextualFoldingSetTrait - Like FoldingSetTrait, but for ContextualFoldingSets.

DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but for ContextualFoldingSets.

static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID, Ctx Context)

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

static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, Ctx Context)

DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...

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

static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID)

static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)

static void Profile(T &X, FoldingSetNodeID &ID)

Functions provided by the derived class to compute folding properties.

unsigned(* ComputeNodeHash)(const FoldingSetBase *Self, Node *N, FoldingSetNodeID &TempID)

ComputeNodeHash - Instantiations of the FoldingSet template implement this function to compute a hash...

bool(* NodeEquals)(const FoldingSetBase *Self, Node *N, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)

NodeEquals - Instantiations of the FoldingSet template implement this function to compare the given n...

void(* GetNodeProfile)(const FoldingSetBase *Self, Node *N, FoldingSetNodeID &ID)

GetNodeProfile - Instantiations of the FoldingSet template implement this function to gather data bit...

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

static void Profile(T *X, FoldingSetNodeID &ID)

static void Profile(const std::pair< T1, T2 > &P, FoldingSetNodeID &ID)

FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...

An iterator type that allows iterating over the pointees via some other iterator.