Go to the documentation of this file.
13 #ifndef LLVM_SUPPORT_ONDISKHASHTABLE_H
14 #define LLVM_SUPPORT_ONDISKHASHTABLE_H
63 typename Info::key_type
Key;
66 const typename Info::hash_value_type Hash;
68 Item(
typename Info::key_type_ref
Key,
typename Info::data_type_ref
Data,
74 offset_type NumBuckets;
75 offset_type NumEntries;
89 void insert(Bucket *Buckets,
size_t Size, Item *
E) {
90 Bucket &
B = Buckets[
E->Hash & (Size - 1)];
97 void resize(
size_t NewSize) {
98 Bucket *NewBuckets =
static_cast<Bucket *
>(
101 for (
size_t I = 0;
I < NumBuckets; ++
I)
102 for (Item *
E = Buckets[
I].Head;
E;) {
105 insert(NewBuckets, NewSize,
E);
110 NumBuckets = NewSize;
111 Buckets = NewBuckets;
117 typename Info::data_type_ref
Data) {
126 typename Info::data_type_ref
Data,
Info &InfoObj) {
128 if (4 * NumEntries >= 3 * NumBuckets)
129 resize(NumBuckets * 2);
130 insert(Buckets, NumBuckets,
new (BA.
Allocate()) Item(
Key,
Data, InfoObj));
135 unsigned Hash = InfoObj.ComputeHash(
Key);
136 for (Item *
I = Buckets[Hash & (NumBuckets - 1)].Head;
I;
I =
I->Next)
137 if (
I->Hash == Hash && InfoObj.EqualKey(
I->Key,
Key))
145 return Emit(Out, InfoObj);
166 unsigned TargetNumBuckets =
168 if (TargetNumBuckets != NumBuckets)
169 resize(TargetNumBuckets);
172 for (offset_type
I = 0;
I < NumBuckets; ++
I) {
173 Bucket &
B = Buckets[
I];
179 assert(
B.Off &&
"Cannot write a bucket at offset 0. Please add padding.");
183 assert(
B.Length != 0 &&
"Bucket has a head but zero length?");
186 for (Item *
I =
B.Head;
I;
I =
I->Next) {
187 LE.write<
typename Info::hash_value_type>(
I->Hash);
188 const std::pair<offset_type, offset_type> &Len =
189 InfoObj.EmitKeyDataLength(Out,
I->Key,
I->Data);
191 InfoObj.EmitKey(Out,
I->Key, Len.first);
192 InfoObj.EmitData(Out,
I->Key,
I->Data, Len.second);
197 InfoObj.EmitKey(Out,
I->Key, Len.first);
199 InfoObj.EmitData(Out,
I->Key,
I->Data, Len.second);
201 assert(offset_type(DataStart - KeyStart) == Len.first &&
202 "key length does not match bytes written");
203 assert(offset_type(End - DataStart) == Len.second &&
204 "data length does not match bytes written");
210 offset_type TableOff = Out.
tell();
214 LE.write<uint8_t>(0);
217 LE.write<offset_type>(NumBuckets);
218 LE.write<offset_type>(NumEntries);
219 for (offset_type
I = 0;
I < NumBuckets; ++
I)
220 LE.write<offset_type>(Buckets[
I].Off);
230 Buckets =
static_cast<Bucket *
>(
safe_calloc(NumBuckets,
sizeof(Bucket)));
277 const unsigned char *
const Buckets;
278 const unsigned char *
const Base;
290 const unsigned char *Buckets,
291 const unsigned char *
Base,
293 : NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),
295 assert((
reinterpret_cast<uintptr_t
>(Buckets) & 0
x3) == 0 &&
296 "'buckets' must have a 4-byte alignment");
302 static std::pair<offset_type, offset_type>
304 assert((
reinterpret_cast<uintptr_t
>(Buckets) & 0
x3) == 0 &&
305 "buckets should be 4-byte aligned.");
308 endian::readNext<offset_type, little, aligned>(Buckets);
310 endian::readNext<offset_type, little, aligned>(Buckets);
311 return std::make_pair(NumBuckets, NumEntries);
319 bool isEmpty()
const {
return NumEntries == 0; }
323 const unsigned char *
const Data;
331 :
Key(K),
Data(
D), Len(L), InfoObj(InfoObj) {}
346 return find_hashed(IKey, KeyHash, InfoPtr);
351 Info *InfoPtr =
nullptr) {
359 const unsigned char *Bucket = Buckets +
sizeof(
offset_type) * Idx;
361 offset_type Offset = endian::readNext<offset_type, little, aligned>(Bucket);
364 const unsigned char *Items =
Base + Offset;
368 unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
370 for (
unsigned i = 0;
i < Len; ++
i) {
373 endian::readNext<hash_value_type, little, unaligned>(Items);
376 const std::pair<offset_type, offset_type> &L =
377 Info::ReadKeyDataLength(Items);
381 if (ItemHash != KeyHash) {
388 InfoPtr->ReadKey((
const unsigned char *
const)Items, L.first);
391 if (!InfoPtr->EqualKey(
X, IKey)) {
397 return iterator(
X, Items + L.first, L.second, InfoPtr);
417 const unsigned char *
const Base,
420 auto NumBucketsAndEntries = readNumBucketsAndEntries(Buckets);
422 NumBucketsAndEntries.second,
423 Buckets,
Base, InfoObj);
430 template <
typename Info>
432 const unsigned char *Payload;
444 class iterator_base {
445 const unsigned char *Ptr;
452 iterator_base(
const unsigned char *
const Ptr,
offset_type NumEntries)
453 : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries) {}
455 : Ptr(
nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}
457 friend bool operator==(
const iterator_base &
X,
const iterator_base &
Y) {
458 return X.NumEntriesLeft ==
Y.NumEntriesLeft;
460 friend bool operator!=(
const iterator_base &
X,
const iterator_base &
Y) {
461 return X.NumEntriesLeft !=
Y.NumEntriesLeft;
467 if (!NumItemsInBucketLeft) {
470 NumItemsInBucketLeft =
471 endian::readNext<uint16_t, little, unaligned>(Ptr);
475 const std::pair<offset_type, offset_type> &L =
476 Info::ReadKeyDataLength(Ptr);
477 Ptr += L.first + L.second;
478 assert(NumItemsInBucketLeft);
479 --NumItemsInBucketLeft;
486 const unsigned char *getItem()
const {
493 const unsigned char *Buckets,
494 const unsigned char *Payload,
495 const unsigned char *
Base,
509 : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
523 auto *LocalPtr = this->getItem();
526 auto L = Info::ReadKeyDataLength(LocalPtr);
529 return InfoObj->ReadKey(LocalPtr, L.first);
533 return InfoObj->GetExternalKey(getInternalKey());
538 return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
555 : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
569 auto *LocalPtr = this->getItem();
572 auto L = Info::ReadKeyDataLength(LocalPtr);
576 return InfoObj->ReadData(
Key, LocalPtr + L.first, L.second);
581 return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
603 Create(
const unsigned char *Buckets,
const unsigned char *
const Payload,
604 const unsigned char *
const Base,
const Info &InfoObj =
Info()) {
606 auto NumBucketsAndEntries =
609 NumBucketsAndEntries.first, NumBucketsAndEntries.second,
610 Buckets, Payload,
Base, InfoObj);
uint64_t tell() const
tell - Return the current offset with the file.
base_type::external_key_type external_key_type
This is an optimization pass for GlobalISel generic memory operations.
data_iterator data_begin()
InstrProfLookupTrait::offset_type offset_type
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Info::hash_value_type hash_value_type
offset_type getNumEntries() const
Generates an on disk hash table.
iterator_range< data_iterator > data()
iterator_range< key_iterator > keys()
bool operator!=(const iterator &X) const
Info::external_key_type external_key_type
base_type::offset_type offset_type
void insert(typename Info::key_type_ref Key, typename Info::data_type_ref Data, Info &InfoObj)
Insert an entry into the table.
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)
external_key_type value_type
base_type::internal_key_type internal_key_type
bool operator!=(uint64_t V1, const APInt &V2)
Iterates over all of the keys in the table.
void insert(typename Info::key_type_ref Key, typename Info::data_type_ref Data)
Insert an entry into the table.
Provides lookup on an on disk hash table.
static std::pair< offset_type, offset_type > readNumBucketsAndEntries(const unsigned char *&Buckets)
Read the number of buckets and the number of entries from a hash table produced by OnDiskHashTableGen...
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Adapter to write values to a stream in a particular byte order.
key_iterator operator++(int)
In x86 we generate this spiffy xmm0 xmm0 ret in x86 we generate this which could be xmm1 movss xmm1 xmm0 ret In sse4 we could use insertps to make both better Here s another testcase that could use x3
Info::data_type data_type
offset_type getDataLen() const
data_iterator & operator++()
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
offset_type Emit(raw_ostream &Out)
Emit the table to Out, which must not be at offset 0.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
data_iterator operator++(int)
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
iterator find_hashed(const internal_key_type &IKey, hash_value_type KeyHash, Info *InfoPtr=nullptr)
Look up the stored data for a particular key with a known hash.
data_iterator(const unsigned char *const Ptr, offset_type NumEntries, Info *InfoObj)
This class implements an extremely fast bulk output stream that can only output to a stream.
bool operator==(const iterator &X) const
base_type::hash_value_type hash_value_type
Analysis containing CSE Info
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
value_type operator*() const
Info::offset_type offset_type
bool contains(typename Info::key_type_ref Key, Info &InfoObj)
Determine whether an entry has been inserted.
OnDiskChainedHashTable< Info > base_type
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
iterator find(const external_key_type &EKey, Info *InfoPtr=nullptr)
Look up the stored data for a particular key.
const unsigned char * getBuckets() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Iterates over all the entries in the table, returning the data.
offset_type Emit(raw_ostream &Out, Info &InfoObj)
Emit the table to Out, which must not be at offset 0.
const unsigned char * getDataPtr() const
bool operator==(uint64_t V1, const APInt &V2)
static OnDiskChainedHashTable * Create(const unsigned char *Buckets, const unsigned char *const Base, const Info &InfoObj=Info())
Create the hash table.
Provides lookup and iteration over an on disk hash table.
data_type operator*() const
~OnDiskChainedHashTableGenerator()
key_iterator & operator++()
internal_key_type getInternalKey() const
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries, const unsigned char *Buckets, const unsigned char *Payload, const unsigned char *Base, const Info &InfoObj=Info())
OnDiskChainedHashTableGenerator()
Info::internal_key_type internal_key_type
base_type::data_type data_type
key_iterator(const unsigned char *const Ptr, offset_type NumEntries, Info *InfoObj)
offset_type getNumBuckets() const
static OnDiskIterableChainedHashTable * Create(const unsigned char *Buckets, const unsigned char *const Payload, const unsigned char *const Base, const Info &InfoObj=Info())
Create the hash table.
InstrProfLookupTrait::data_type data_type
A range adaptor for a pair of iterators.
OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries, const unsigned char *Buckets, const unsigned char *Base, const Info &InfoObj=Info())
value_type operator*() const
uint64_t offsetToAlignment(uint64_t Value, Align Alignment)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
const unsigned char * getBase() const
iterator(const internal_key_type K, const unsigned char *D, offset_type L, Info *InfoObj)