TrieRawHashMap.cpp Source File (original) (raw)

19#include

21using namespace llvm;

23namespace {

24struct TrieNode {

25 const bool IsSubtrie = false;

27 TrieNode(bool IsSubtrie) : IsSubtrie(IsSubtrie) {}

29 static void *operator new(size_t Size) { return ::operator new(Size); }

30 void operator delete(void *Ptr) { ::operator delete(Ptr); }

31};

33struct TrieContent final : public TrieNode {

34 const uint8_t ContentOffset;

35 const uint8_t HashSize;

36 const uint8_t HashOffset;

38 void *getValuePointer() const {

39 auto *Content = reinterpret_cast<const uint8_t *>(this) + ContentOffset;

40 return const_cast<uint8_t *>(Content);

41 }

43 ArrayRef<uint8_t> getHash() const {

44 auto *Begin = reinterpret_cast<const uint8_t *>(this) + HashOffset;

45 return ArrayRef(Begin, Begin + HashSize);

46 }

48 TrieContent(size_t ContentOffset, size_t HashSize, size_t HashOffset)

49 : TrieNode(false), ContentOffset(ContentOffset),

50 HashSize(HashSize), HashOffset(HashOffset) {}

52 static bool classof(const TrieNode *TN) { return !TN->IsSubtrie; }

53};

55static_assert(sizeof(TrieContent) ==

57 "Check header assumption!");

59class TrieSubtrie final

60 : public TrieNode,

61 private TrailingObjects<TrieSubtrie, LazyAtomicPointer> {

62public:

63 using Slot = LazyAtomicPointer;

65 Slot &get(size_t I) { return getTrailingObjects()[I]; }

66 TrieNode *load(size_t I) { return get(I).load(); }

68 unsigned size() const { return Size; }

70 TrieSubtrie *

71 sink(size_t I, TrieContent &Content, size_t NumSubtrieBits, size_t NewI,

72 function_ref<TrieSubtrie *(std::unique_ptr)> Saver);

74 static std::unique_ptr create(size_t StartBit, size_t NumBits);

76 explicit TrieSubtrie(size_t StartBit, size_t NumBits);

78 static bool classof(const TrieNode *TN) { return TN->IsSubtrie; }

80 static constexpr size_t sizeToAlloc(unsigned NumBits) {

81 assert(NumBits < 20 && "Tries should have fewer than ~1M slots");

82 unsigned Count = 1u << NumBits;

83 return totalSizeToAlloc<LazyAtomicPointer>(Count);

84 }

86private:

100

101

102

103

104

105

106

107 unsigned StartBit = 0;

108 unsigned NumBits = 0;

109 unsigned Size = 0;

110 friend class llvm::ThreadSafeTrieRawHashMapBase;

111 friend class TrailingObjects;

112

113public:

114

115 std::atomic<TrieSubtrie *> Next;

116};

117}

118

119std::unique_ptr TrieSubtrie::create(size_t StartBit,

120 size_t NumBits) {

121 void *Memory = ::operator new(sizeToAlloc(NumBits));

122 TrieSubtrie *S = ::new (Memory) TrieSubtrie(StartBit, NumBits);

123 return std::unique_ptr(S);

124}

125

126TrieSubtrie::TrieSubtrie(size_t StartBit, size_t NumBits)

127 : TrieNode(true), StartBit(StartBit), NumBits(NumBits), Size(1u << NumBits),

128 Next(nullptr) {

129 for (unsigned I = 0; I < Size; ++I)

131

132 static_assert(

133 std::is_trivially_destructible<LazyAtomicPointer>::value,

134 "Expected no work in destructor for TrieNode");

135}

136

137

138

139

140TrieSubtrie *TrieSubtrie::sink(

141 size_t I, TrieContent &Content, size_t NumSubtrieBits, size_t NewI,

142 function_ref<TrieSubtrie *(std::unique_ptr)> Saver) {

143

144

145 assert(NumSubtrieBits > 0);

146 std::unique_ptr S = create(StartBit + NumBits, NumSubtrieBits);

147

149 S->get(NewI).store(&Content);

150

151

152

153 TrieNode *ExistingNode = &Content;

155 if (get(I).compare_exchange_strong(ExistingNode, S.get()))

156 return Saver(std::move(S));

157

158

159

161}

162

164 : private TrailingObjects<ThreadSafeTrieRawHashMapBase::ImplType,

165 TrieSubtrie> {

166public:

167 static std::unique_ptr create(size_t StartBit, size_t NumBits) {

168 size_t Size = sizeof(ImplType) + TrieSubtrie::sizeToAlloc(NumBits);

170 ImplType *Impl = ::new (Memory) ImplType(StartBit, NumBits);

171 return std::unique_ptr(Impl);

172 }

173

174

175

176

177 TrieSubtrie *save(std::unique_ptr S) {

178 assert(!S->Next && "Expected S to a freshly-constructed leaf");

179

180 TrieSubtrie *CurrentHead = nullptr;

181

182

183

184

185 while ( getRoot ()->Next.compare_exchange_weak(CurrentHead, S.get()))

186 S->Next.exchange(CurrentHead);

187

188

189 return S.release();

190 }

191

192

194

195 static void *operator new(size_t Size) { return ::operator new(Size); }

196 void operator delete(void *Ptr) { ::operator delete(Ptr); }

197

198

199

200

202

203private:

205

206 ImplType(size_t StartBit, size_t NumBits) {

207 ::new (getRoot()) TrieSubtrie(StartBit, NumBits);

208 }

209};

210

213 if (ImplType *Impl = ImplPtr.load())

214 return *Impl;

215

216

217

218 std::unique_ptr Impl = ImplType::create(0, NumRootBits);

219 ImplType *ExistingImpl = nullptr;

220

221

222

223 if (ImplPtr.compare_exchange_strong(ExistingImpl, Impl.get()))

224 return *Impl.release();

225

226

227 return *ExistingImpl;

228}

229

232 assert(!Hash.empty() && "Uninitialized hash");

233

234 ImplType *Impl = ImplPtr.load();

235 if (!Impl)

237

238 TrieSubtrie *S = Impl->getRoot();

240 size_t Index = IndexGen.next();

241 while (Index != IndexGen.end()) {

242

243 TrieNode *Existing = S->get(Index);

244 if (!Existing)

246

247

249 return ExistingContent->getHash() == Hash

250 ? PointerBase(ExistingContent->getValuePointer())

252

253 Index = IndexGen.next();

255 }

256 llvm_unreachable("failed to locate the node after consuming all hash bytes");

257}

258

262 Constructor) {

263 assert(!Hash.empty() && "Uninitialized hash");

264

265 ImplType &Impl = getOrCreateImpl();

266 TrieSubtrie *S = Impl.getRoot();

268 size_t Index;

269 if (Hint.isHint()) {

270 S = static_cast<TrieSubtrie *>(Hint.P);

271 Index = IndexGen.hint(Hint.I, Hint.B);

272 } else {

273 Index = IndexGen.next();

274 }

275

276 while (Index != IndexGen.end()) {

277

278

279 bool Generated = false;

280 TrieNode &Existing = S->get(Index).loadOrGenerate([&]() {

281 Generated = true;

282

283

285 Impl.ContentAlloc.Allocate(ContentAllocSize, ContentAllocAlign));

286 const uint8_t *HashStorage = Constructor(Memory + ContentOffset, Hash);

287

288

289 TrieContent *Content = ::new (Memory)

290 TrieContent(ContentOffset, Hash.size(), HashStorage - Memory);

291 assert(Hash == Content->getHash() && "Hash not properly initialized");

292 return Content;

293 });

294

295 if (Generated)

297

299 S = ST;

300 Index = IndexGen.next();

301 continue;

302 }

303

304

306 if (ExistingContent.getHash() == Hash)

307 return PointerBase(ExistingContent.getValuePointer());

308

309

310 size_t NextIndex = IndexGen.next();

311 while (NextIndex != IndexGen.end()) {

312 size_t NewIndexForExistingContent =

314 S = S->sink(Index, ExistingContent, IndexGen.getNumBits(),

315 NewIndexForExistingContent,

316 [&Impl](std::unique_ptr S) {

317 return Impl.save(std::move(S));

318 });

319 Index = NextIndex;

320

321

322 if (NextIndex != NewIndexForExistingContent)

323 break;

324

325 NextIndex = IndexGen.next();

326 }

327 }

328 llvm_unreachable("failed to insert the node after consuming all hash bytes");

329}

330

332 size_t ContentAllocSize, size_t ContentAllocAlign, size_t ContentOffset,

333 std::optional<size_t> NumRootBits, std::optional<size_t> NumSubtrieBits)

334 : ContentAllocSize(ContentAllocSize), ContentAllocAlign(ContentAllocAlign),

335 ContentOffset(ContentOffset),

338 ImplPtr(nullptr) {

339

340

341

342 assert((!NumRootBits || *NumRootBits < 20) &&

343 "Root should have fewer than ~1M slots");

344 assert((!NumSubtrieBits || *NumSubtrieBits < 10) &&

345 "Subtries should have fewer than ~1K slots");

346}

347

350 : ContentAllocSize(RHS.ContentAllocSize),

351 ContentAllocAlign(RHS.ContentAllocAlign),

352 ContentOffset(RHS.ContentOffset), NumRootBits(RHS.NumRootBits),

353 NumSubtrieBits(RHS.NumSubtrieBits) {

354

355 ImplPtr = RHS.ImplPtr.exchange(nullptr);

356}

357

359 assert(!ImplPtr.load() && "Expected subclass to call destroyImpl()");

360}

361

364 std::unique_ptr Impl(ImplPtr.exchange(nullptr));

365 if (!Impl)

366 return;

367

368

369

370

371

372

373 if (Destructor)

374 for (TrieSubtrie *Trie = Impl->getRoot(); Trie; Trie = Trie->Next.load())

375 for (unsigned I = 0; I < Trie->size(); ++I)

377 Destructor(Content->getValuePointer());

378

379

380

381 TrieSubtrie *Trie = Impl->getRoot()->Next;

382 while (Trie) {

383 TrieSubtrie *Next = Trie->Next.exchange(nullptr);

384 delete Trie;

386 }

387}

388

391 ImplType *Impl = ImplPtr.load();

392 if (!Impl)

395}

396

399 assert(.isHint() && "Not a valid trie");

400 if (.P)

401 return 0;

403 return S->StartBit;

404 return 0;

405}

406

409 assert(.isHint() && "Not a valid trie");

410 if (.P)

411 return 0;

413 return S->NumBits;

414 return 0;

415}

416

419 assert(.isHint() && "Not a valid trie");

420 if (.P)

421 return 0;

423 if (!S)

424 return 0;

425 unsigned Num = 0;

426 for (unsigned I = 0, E = S->size(); I < E; ++I)

427 if (S->load(I))

428 ++Num;

429 return Num;

430}

431

434 assert(.isHint() && "Not a valid trie");

435 if (.P)

436 return "";

437

439 if (!S || !S->IsSubtrie)

440 return "";

441

442

443

444 TrieSubtrie *Current = S;

445 TrieContent *Node = nullptr;

446 while (Current) {

447 TrieSubtrie *Next = nullptr;

448

449 for (unsigned I = 0, E = Current->size(); I < E; ++I) {

450 auto *S = Current->load(I);

451 if (!S)

452 continue;

453

455 Node = Content;

458 break;

459 }

460

461

463 break;

464

465

466 Current = Next;

467 }

468

469 assert(Node && "malformed trie, cannot find TrieContent on leaf node");

470

471

472 std::string Str;

474

475 unsigned StartFullBytes = (S->StartBit + 1) / 8 - 1;

477 true);

478

479

480 std::string Bits;

481 for (unsigned I = StartFullBytes * 8, E = S->StartBit; I < E; ++I) {

482 unsigned Index = I / 8;

483 unsigned Offset = 7 - I % 8;

484 Bits.push_back('0' + ((Node->getHash()[Index] >> Offset) & 1));

485 }

486

487 if (!Bits.empty())

488 SS << "[" << Bits << "]";

489

490 return SS.str();

491}

492

494 ImplType *Impl = ImplPtr.load();

495 if (!Impl)

496 return 0;

497 unsigned Num = 0;

498 for (TrieSubtrie *Trie = Impl->getRoot(); Trie; Trie = Trie->Next.load())

499 ++Num;

500 return Num;

501}

502

506 assert(.isHint() && "Not a valid trie");

507 if (.P)

510 if (!S)

512 if (auto *E = S->Next.load())

515}

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

AMDGPU Mark last scratch load

Function Alias Analysis false

This file defines the BumpPtrAllocator interface.

static DeltaTreeNode * getRoot(void *Root)

static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU, OptimizationRemarkEmitter *ORE)

When an instruction is found to only be used outside of the loop, this function moves it to the exit ...

This header defines support for implementing classes that have some trailing object (or arrays of obj...

Definition TrieRawHashMap.cpp:165

TrieSubtrie * save(std::unique_ptr< TrieSubtrie > S)

Definition TrieRawHashMap.cpp:177

TrieSubtrie * getRoot()

Definition TrieRawHashMap.cpp:193

static std::unique_ptr< ImplType > create(size_t StartBit, size_t NumBits)

Definition TrieRawHashMap.cpp:167

friend class TrailingObjects

Definition TrieRawHashMap.cpp:204

ThreadSafeAllocator< BumpPtrAllocator > ContentAlloc

FIXME: This should take a function that allocates and constructs the content lazily (taking the hash ...

Definition TrieRawHashMap.cpp:201

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

size_t size() const

size - Get the array size.

bool empty() const

empty - Check if the array is empty.

StringRef take_front(size_t N=1) const

Return a StringRef equal to 'this' but with only the first N elements remaining.

Thread-safe allocator adaptor.

LLVM_ABI PointerBase getNextTrie(PointerBase P) const

Definition TrieRawHashMap.cpp:504

LLVM_ABI unsigned getNumTries() const

Definition TrieRawHashMap.cpp:493

LLVM_ABI unsigned getNumBits(PointerBase P) const

Definition TrieRawHashMap.cpp:407

LLVM_ABI unsigned getNumSlotUsed(PointerBase P) const

Definition TrieRawHashMap.cpp:417

LLVM_ABI ~ThreadSafeTrieRawHashMapBase()

Destructor, which asserts if there's anything to do.

Definition TrieRawHashMap.cpp:358

LLVM_ABI void destroyImpl(function_ref< void(void *ValueMem)> Destructor)

Definition TrieRawHashMap.cpp:362

static constexpr size_t DefaultNumSubtrieBits

ThreadSafeTrieRawHashMapBase()=delete

LLVM_ABI PointerBase find(ArrayRef< uint8_t > Hash) const

Find the stored content with hash.

Definition TrieRawHashMap.cpp:231

LLVM_ABI PointerBase getRoot() const

Definition TrieRawHashMap.cpp:390

LLVM_ABI PointerBase insert(PointerBase Hint, ArrayRef< uint8_t > Hash, function_ref< const uint8_t *(void *Mem, ArrayRef< uint8_t > Hash)> Constructor)

Insert and return the stored content.

Definition TrieRawHashMap.cpp:259

LLVM_ABI unsigned getStartBit(PointerBase P) const

Definition TrieRawHashMap.cpp:397

LLVM_ABI std::string getTriePrefixAsString(PointerBase P) const

Definition TrieRawHashMap.cpp:432

static constexpr size_t TrieContentBaseSize

static constexpr size_t DefaultNumRootBits

See the file comment for details on the usage of the TrailingObjects type.

const T * getTrailingObjects() const

An efficient, type-erasing, non-owning reference to a callable.

A raw_ostream that writes to an std::string.

This class provides various memory handling functions that manipulate MemoryBlock instances.

#define llvm_unreachable(msg)

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

This is an optimization pass for GlobalISel generic memory operations.

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

auto dyn_cast_or_null(const Y &Val)

decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)

FunctionAddr VTableAddr Count

@ Sub

Subtraction of integers.

FunctionAddr VTableAddr Next

ArrayRef(const T &OneElt) -> ArrayRef< T >

void toHex(ArrayRef< uint8_t > Input, bool LowerCase, SmallVectorImpl< char > &Output)

Convert buffer Input to its hexadecimal representation. The returned string is double the size of Inp...

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

StringRef toStringRef(bool B)

Construct a string ref from a boolean.

The utility class that helps computing the index of the object inside trie from its hash.

std::optional< size_t > StartBit

size_t getNumBits() const

size_t getCollidingBits(ArrayRef< uint8_t > CollidingBits) const

size_t hint(unsigned Index, unsigned Bit)