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}

49 Bits.reserve(Bits.size() + NumInserts);

51 Bits.push_back(Size);

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)) {

60 Bits.append(Base, Base + Units);

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

73 (unsigned char)String[Pos - 1];

74 Bits.push_back(V);

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

81 (unsigned char)String[Pos - 4];

82 Bits.push_back(V);

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 }

98 Bits.push_back(V);

99}

100

101

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

104}

105

106

107

111

112

113

117

118

119

123

127

128

129

130

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

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

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

212

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;

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) {

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

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

401 void *Probe = NodePtr->getNextInBucket();

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}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file defines the BumpPtrAllocator interface.

Analysis containing CSE Info

static void ** GetBucketPtr(void *NextInBucketPtr)

testing.

Definition FoldingSet.cpp:157

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

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

Definition FoldingSet.cpp:165

static void ** AllocateBuckets(unsigned NumBuckets)

AllocateBuckets - Allocated initialized bucket memory.

Definition FoldingSet.cpp:172

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

Helper functions for FoldingSetBase.

Definition FoldingSet.cpp:147

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

Merge contiguous icmps into a memcmp

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

LLVM_ABI FoldingSetBase(unsigned Log2InitSize=6)

Definition FoldingSet.cpp:183

void ** Buckets

Buckets - Array of bucket chains.

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

Definition FoldingSet.cpp:266

LLVM_ABI bool RemoveNode(Node *N)

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

Definition FoldingSet.cpp:334

LLVM_ABI FoldingSetBase & operator=(FoldingSetBase &&RHS)

Definition FoldingSet.cpp:198

LLVM_ABI ~FoldingSetBase()

Definition FoldingSet.cpp:209

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

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

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

Definition FoldingSet.cpp:376

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

Definition FoldingSet.cpp:303

LLVM_ABI void clear()

clear - Remove all nodes from the folding set.

Definition FoldingSet.cpp:213

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

FindNodeOrInsertPos - Look up the node specified by ID.

Definition FoldingSet.cpp:278

LLVM_ABI FoldingSetBucketIteratorImpl(void **Bucket)

Definition FoldingSet.cpp:422

LLVM_ABI FoldingSetIteratorImpl(void **Bucket)

Definition FoldingSet.cpp:390

LLVM_ABI void advance()

Definition FoldingSet.cpp:399

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

LLVM_ABI bool operator==(FoldingSetNodeIDRef) const

Definition FoldingSet.cpp:27

LLVM_ABI bool operator<(FoldingSetNodeIDRef) const

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

Definition FoldingSet.cpp:34

FoldingSetNodeIDRef()=default

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

LLVM_ABI FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const

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

Definition FoldingSet.cpp:132

void clear()

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

FoldingSetNodeID()=default

LLVM_ABI bool operator==(const FoldingSetNodeID &RHS) const

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

Definition FoldingSet.cpp:108

LLVM_ABI bool operator<(const FoldingSetNodeID &RHS) const

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

Definition FoldingSet.cpp:120

LLVM_ABI void AddNodeID(const FoldingSetNodeID &ID)

Definition FoldingSet.cpp:102

LLVM_ABI void AddString(StringRef String)

Add* - Add various data types to Bit data.

Definition FoldingSet.cpp:45

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

unsigned ID

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

constexpr bool IsLittleEndianHost

constexpr bool IsBigEndianHost

This is an optimization pass for GlobalISel generic memory operations.

FoldingSetBase::Node FoldingSetNode

auto uninitialized_copy(R &&Src, IterTy Dst)

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

FunctionAddr VTableAddr Next

BumpPtrAllocatorImpl<> BumpPtrAllocator

The standard BumpPtrAllocator which just uses the default template parameters.

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.