FoldingSet.cpp Source File (original) (raw)

20#include

21#include

22using namespace llvm;

28 if (Size != RHS.Size) return false;

29 return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0;

30}

35 if (Size != RHS.Size)

36 return Size < RHS.Size;

37 return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0;

38}

52 if ( Size ) return;

54 unsigned Units = Size / 4;

55 unsigned Pos = 0;

56 const unsigned *Base = (const unsigned*) String.data();

59 if (!((intptr_t)Base & 3)) {

61 Pos = (Units + 1) * 4;

62 } else {

67 "Unexpected host endianness");

69 for (Pos += 4; Pos <= Size; Pos += 4) {

70 unsigned V = ((unsigned char)String[Pos - 4] << 24) |

71 ((unsigned char)String[Pos - 3] << 16) |

72 ((unsigned char)String[Pos - 2] << 8) |

75 }

76 } else {

77 for (Pos += 4; Pos <= Size; Pos += 4) {

78 unsigned V = ((unsigned char)String[Pos - 1] << 24) |

79 ((unsigned char)String[Pos - 2] << 16) |

80 ((unsigned char)String[Pos - 3] << 8) |

83 }

84 }

85 }

88 unsigned V = 0;

91 switch (Pos - Size) {

92 case 1: V = (V << 8) | (unsigned char)String[Size - 3]; [[fallthrough]];

93 case 2: V = (V << 8) | (unsigned char)String[Size - 2]; [[fallthrough]];

94 case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break;

95 default: return;

96 }

99}

100

101

103 Bits.append(ID.Bits.begin(), ID.Bits.end());

104}

105

106

107

110}

111

112

113

116}

117

118

119

122}

123

126}

127

128

129

130

133 unsigned *New = Allocator.Allocate<unsigned>(Bits.size());

134 std::uninitialized_copy(Bits.begin(), Bits.end(), New);

136}

137

138

139

140

141

142

143

144

145

146

148

149 if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1)

150 return nullptr;

151

153}

154

155

156

158 intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);

159 assert((Ptr & 1) && "Not a bucket pointer");

160 return reinterpret_cast<void**>(Ptr & ~intptr_t(1));

161}

162

163

164

165static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) {

166

167 unsigned BucketNum = Hash & (NumBuckets-1);

168 return Buckets + BucketNum;

169}

170

171

173 void **Buckets = static_cast<void**>(safe_calloc(NumBuckets + 1,

174 sizeof(void*)));

175

176 Buckets[NumBuckets] = reinterpret_cast<void*>(-1);

177 return Buckets;

178}

179

180

181

182

184 assert(5 < Log2InitSize && Log2InitSize < 32 &&

185 "Initial hash table size out of range");

189}

190

192 : Buckets(Arg.Buckets), NumBuckets(Arg.NumBuckets), NumNodes(Arg.NumNodes) {

193 Arg.Buckets = nullptr;

194 Arg.NumBuckets = 0;

195 Arg.NumNodes = 0;

196}

197

199 free(Buckets);

203 RHS.Buckets = nullptr;

204 RHS.NumBuckets = 0;

205 RHS.NumNodes = 0;

206 return *this;

207}

208

211}

212

214

216

217

219

220

222}

223

224void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount,

225 const FoldingSetInfo &Info) {

227 "Can't shrink a folding set with GrowBucketCount");

229 void **OldBuckets = Buckets;

231

232

234

237

238

240 for (unsigned i = 0; i != OldNumBuckets; ++i) {

241 void *Probe = OldBuckets[i];

242 if (!Probe) continue;

243 while (Node *NodeInBucket = GetNextPtr(Probe)) {

244

245 Probe = NodeInBucket->getNextInBucket();

246 NodeInBucket->SetNextInBucket(nullptr);

247

248

250 GetBucketFor(Info.ComputeNodeHash(this, NodeInBucket, TempID),

252 Info);

254 }

255 }

256

257 free(OldBuckets);

258}

259

260

261

262void FoldingSetBase::GrowHashTable(const FoldingSetInfo &Info) {

263 GrowBucketCount(NumBuckets * 2, Info);

264}

265

267

268

269

271 return;

273}

274

275

276

277

280 unsigned IDHash = ID.ComputeHash();

282 void *Probe = *Bucket;

283

284 InsertPos = nullptr;

285

288 if (Info.NodeEquals(this, NodeInBucket, ID, IDHash, TempID))

289 return NodeInBucket;

291

292 Probe = NodeInBucket->getNextInBucket();

293 }

294

295

296 InsertPos = Bucket;

297 return nullptr;

298}

299

300

301

302

305 assert(->getNextInBucket());

306

308 GrowHashTable(Info);

312 }

313

315

316

317 void **Bucket = static_cast<void**>(InsertPos);

318

319 void *Next = *Bucket;

320

321

322

323

324 if (!Next)

325 Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1);

326

327

328 N->SetNextInBucket(Next);

329 *Bucket = N;

330}

331

332

333

335

336

337 void *Ptr = N->getNextInBucket();

338 if ( Ptr ) return false;

339

341 N->SetNextInBucket(nullptr);

342

343

344 void *NodeNextPtr = Ptr;

345

346

347 while (true) {

349

350 Ptr = NodeInBucket->getNextInBucket();

351

352

353

354 if (Ptr == N) {

355 NodeInBucket->SetNextInBucket(NodeNextPtr);

356 return true;

357 }

358 } else {

360 Ptr = *Bucket;

361

362

363

364 if (Ptr == N) {

365 *Bucket = NodeNextPtr;

366 return true;

367 }

368 }

369 }

370}

371

372

373

374

379 Info.GetNodeProfile(this, N, ID);

380 void *IP;

382 return E;

384 return N;

385}

386

387

388

389

391

392 while (*Bucket != reinterpret_cast<void*>(-1) &&

394 ++Bucket;

395

397}

398

400

402

404 NodePtr = NextNodeInBucket;

405 else {

406

408

409

410 do {

411 ++Bucket;

412 } while (*Bucket != reinterpret_cast<void*>(-1) &&

414

416 }

417}

418

419

420

421

423 Ptr = (!*Bucket || GetNextPtr (*Bucket)) ? (void*) Bucket : *Bucket;

424}

This file defines the BumpPtrAllocator interface.

Analysis containing CSE Info

static void ** GetBucketPtr(void *NextInBucketPtr)

testing.

static void ** GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets)

GetBucketFor - Hash the specified node ID and return the hash bucket for the specified ID.

static void ** AllocateBuckets(unsigned NumBuckets)

AllocateBuckets - Allocated initialized bucket memory.

static FoldingSetBase::Node * GetNextPtr(void *NextInBucketPtr)

Helper functions for FoldingSetBase.

This file defines a hash set that can be used to remove duplication of nodes in a graph.

Merge contiguous icmps into a memcmp

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

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

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

void * getNextInBucket() const

FoldingSetBase - Implements the folding set functionality.

FoldingSetBase(unsigned Log2InitSize=6)

void ** Buckets

Buckets - Array of bucket chains.

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,...

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(void **Bucket)

FoldingSetIteratorImpl(void **Bucket)

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

bool operator==(FoldingSetNodeIDRef) const

bool operator<(FoldingSetNodeIDRef) const

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

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 clear()

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

bool operator==(const FoldingSetNodeID &RHS) const

operator== - Used to compare two nodes to each other.

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.

void reserve(size_type N)

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

pointer data()

Return a pointer to the vector's buffer, even if empty().

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

unsigned ID

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

static const bool IsLittleEndianHost

constexpr bool IsBigEndianHost

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)

constexpr bool isPowerOf2_32(uint32_t Value)

Return true if the argument is a power of two > 0.

constexpr T divideCeil(U Numerator, V Denominator)

Returns the integer ceil(Numerator / Denominator).

T bit_floor(T Value)

Returns the largest integral power of two no greater than Value if Value is nonzero.

Functions provided by the derived class to compute folding properties.