Emit discriminator for inlined callsites.
[oota-llvm.git] / include / llvm / Support / OnDiskHashTable.h
1 //===--- OnDiskHashTable.h - On-Disk Hash Table Implementation --*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Defines facilities for reading and writing on-disk hash tables.
12 ///
13 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_SUPPORT_ONDISKHASHTABLE_H
15 #define LLVM_SUPPORT_ONDISKHASHTABLE_H
16
17 #include "llvm/Support/AlignOf.h"
18 #include "llvm/Support/Allocator.h"
19 #include "llvm/Support/DataTypes.h"
20 #include "llvm/Support/EndianStream.h"
21 #include "llvm/Support/Host.h"
22 #include "llvm/Support/MathExtras.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include <cassert>
25 #include <cstdlib>
26
27 namespace llvm {
28
29 /// \brief Generates an on disk hash table.
30 ///
31 /// This needs an \c Info that handles storing values into the hash table's
32 /// payload and computes the hash for a given key. This should provide the
33 /// following interface:
34 ///
35 /// \code
36 /// class ExampleInfo {
37 /// public:
38 ///   typedef ExampleKey key_type;   // Must be copy constructible
39 ///   typedef ExampleKey &key_type_ref;
40 ///   typedef ExampleData data_type; // Must be copy constructible
41 ///   typedef ExampleData &data_type_ref;
42 ///   typedef uint32_t hash_value_type; // The type the hash function returns.
43 ///   typedef uint32_t offset_type; // The type for offsets into the table.
44 ///
45 ///   /// Calculate the hash for Key
46 ///   static hash_value_type ComputeHash(key_type_ref Key);
47 ///   /// Return the lengths, in bytes, of the given Key/Data pair.
48 ///   static std::pair<offset_type, offset_type>
49 ///   EmitKeyDataLength(raw_ostream &Out, key_type_ref Key, data_type_ref Data);
50 ///   /// Write Key to Out.  KeyLen is the length from EmitKeyDataLength.
51 ///   static void EmitKey(raw_ostream &Out, key_type_ref Key,
52 ///                       offset_type KeyLen);
53 ///   /// Write Data to Out.  DataLen is the length from EmitKeyDataLength.
54 ///   static void EmitData(raw_ostream &Out, key_type_ref Key,
55 ///                        data_type_ref Data, offset_type DataLen);
56 ///   /// Determine if two keys are equal. Optional, only needed by contains.
57 ///   static bool EqualKey(key_type_ref Key1, key_type_ref Key2);
58 /// };
59 /// \endcode
60 template <typename Info> class OnDiskChainedHashTableGenerator {
61   /// \brief A single item in the hash table.
62   class Item {
63   public:
64     typename Info::key_type Key;
65     typename Info::data_type Data;
66     Item *Next;
67     const typename Info::hash_value_type Hash;
68
69     Item(typename Info::key_type_ref Key, typename Info::data_type_ref Data,
70          Info &InfoObj)
71         : Key(Key), Data(Data), Next(nullptr), Hash(InfoObj.ComputeHash(Key)) {}
72   };
73
74   typedef typename Info::offset_type offset_type;
75   offset_type NumBuckets;
76   offset_type NumEntries;
77   llvm::SpecificBumpPtrAllocator<Item> BA;
78
79   /// \brief A linked list of values in a particular hash bucket.
80   struct Bucket {
81     offset_type Off;
82     unsigned Length;
83     Item *Head;
84   };
85
86   Bucket *Buckets;
87
88 private:
89   /// \brief Insert an item into the appropriate hash bucket.
90   void insert(Bucket *Buckets, size_t Size, Item *E) {
91     Bucket &B = Buckets[E->Hash & (Size - 1)];
92     E->Next = B.Head;
93     ++B.Length;
94     B.Head = E;
95   }
96
97   /// \brief Resize the hash table, moving the old entries into the new buckets.
98   void resize(size_t NewSize) {
99     Bucket *NewBuckets = (Bucket *)std::calloc(NewSize, sizeof(Bucket));
100     // Populate NewBuckets with the old entries.
101     for (size_t I = 0; I < NumBuckets; ++I)
102       for (Item *E = Buckets[I].Head; E;) {
103         Item *N = E->Next;
104         E->Next = nullptr;
105         insert(NewBuckets, NewSize, E);
106         E = N;
107       }
108
109     free(Buckets);
110     NumBuckets = NewSize;
111     Buckets = NewBuckets;
112   }
113
114 public:
115   /// \brief Insert an entry into the table.
116   void insert(typename Info::key_type_ref Key,
117               typename Info::data_type_ref Data) {
118     Info InfoObj;
119     insert(Key, Data, InfoObj);
120   }
121
122   /// \brief Insert an entry into the table.
123   ///
124   /// Uses the provided Info instead of a stack allocated one.
125   void insert(typename Info::key_type_ref Key,
126               typename Info::data_type_ref Data, Info &InfoObj) {
127     ++NumEntries;
128     if (4 * NumEntries >= 3 * NumBuckets)
129       resize(NumBuckets * 2);
130     insert(Buckets, NumBuckets, new (BA.Allocate()) Item(Key, Data, InfoObj));
131   }
132
133   /// \brief Determine whether an entry has been inserted.
134   bool contains(typename Info::key_type_ref Key, Info &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))
138         return true;
139     return false;
140   }
141
142   /// \brief Emit the table to Out, which must not be at offset 0.
143   offset_type Emit(raw_ostream &Out) {
144     Info InfoObj;
145     return Emit(Out, InfoObj);
146   }
147
148   /// \brief Emit the table to Out, which must not be at offset 0.
149   ///
150   /// Uses the provided Info instead of a stack allocated one.
151   offset_type Emit(raw_ostream &Out, Info &InfoObj) {
152     using namespace llvm::support;
153     endian::Writer<little> LE(Out);
154
155     // Emit the payload of the table.
156     for (offset_type I = 0; I < NumBuckets; ++I) {
157       Bucket &B = Buckets[I];
158       if (!B.Head)
159         continue;
160
161       // Store the offset for the data of this bucket.
162       B.Off = Out.tell();
163       assert(B.Off && "Cannot write a bucket at offset 0. Please add padding.");
164
165       // Write out the number of items in the bucket.
166       LE.write<uint16_t>(B.Length);
167       assert(B.Length != 0 && "Bucket has a head but zero length?");
168
169       // Write out the entries in the bucket.
170       for (Item *I = B.Head; I; I = I->Next) {
171         LE.write<typename Info::hash_value_type>(I->Hash);
172         const std::pair<offset_type, offset_type> &Len =
173             InfoObj.EmitKeyDataLength(Out, I->Key, I->Data);
174 #ifdef NDEBUG
175         InfoObj.EmitKey(Out, I->Key, Len.first);
176         InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
177 #else
178         // In asserts mode, check that the users length matches the data they
179         // wrote.
180         uint64_t KeyStart = Out.tell();
181         InfoObj.EmitKey(Out, I->Key, Len.first);
182         uint64_t DataStart = Out.tell();
183         InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
184         uint64_t End = Out.tell();
185         assert(offset_type(DataStart - KeyStart) == Len.first &&
186                "key length does not match bytes written");
187         assert(offset_type(End - DataStart) == Len.second &&
188                "data length does not match bytes written");
189 #endif
190       }
191     }
192
193     // Pad with zeros so that we can start the hashtable at an aligned address.
194     offset_type TableOff = Out.tell();
195     uint64_t N = llvm::OffsetToAlignment(TableOff, alignOf<offset_type>());
196     TableOff += N;
197     while (N--)
198       LE.write<uint8_t>(0);
199
200     // Emit the hashtable itself.
201     LE.write<offset_type>(NumBuckets);
202     LE.write<offset_type>(NumEntries);
203     for (offset_type I = 0; I < NumBuckets; ++I)
204       LE.write<offset_type>(Buckets[I].Off);
205
206     return TableOff;
207   }
208
209   OnDiskChainedHashTableGenerator() {
210     NumEntries = 0;
211     NumBuckets = 64;
212     // Note that we do not need to run the constructors of the individual
213     // Bucket objects since 'calloc' returns bytes that are all 0.
214     Buckets = (Bucket *)std::calloc(NumBuckets, sizeof(Bucket));
215   }
216
217   ~OnDiskChainedHashTableGenerator() { std::free(Buckets); }
218 };
219
220 /// \brief Provides lookup on an on disk hash table.
221 ///
222 /// This needs an \c Info that handles reading values from the hash table's
223 /// payload and computes the hash for a given key. This should provide the
224 /// following interface:
225 ///
226 /// \code
227 /// class ExampleLookupInfo {
228 /// public:
229 ///   typedef ExampleData data_type;
230 ///   typedef ExampleInternalKey internal_key_type; // The stored key type.
231 ///   typedef ExampleKey external_key_type; // The type to pass to find().
232 ///   typedef uint32_t hash_value_type; // The type the hash function returns.
233 ///   typedef uint32_t offset_type; // The type for offsets into the table.
234 ///
235 ///   /// Compare two keys for equality.
236 ///   static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
237 ///   /// Calculate the hash for the given key.
238 ///   static hash_value_type ComputeHash(internal_key_type &IKey);
239 ///   /// Translate from the semantic type of a key in the hash table to the
240 ///   /// type that is actually stored and used for hashing and comparisons.
241 ///   /// The internal and external types are often the same, in which case this
242 ///   /// can simply return the passed in value.
243 ///   static const internal_key_type &GetInternalKey(external_key_type &EKey);
244 ///   /// Read the key and data length from Buffer, leaving it pointing at the
245 ///   /// following byte.
246 ///   static std::pair<offset_type, offset_type>
247 ///   ReadKeyDataLength(const unsigned char *&Buffer);
248 ///   /// Read the key from Buffer, given the KeyLen as reported from
249 ///   /// ReadKeyDataLength.
250 ///   const internal_key_type &ReadKey(const unsigned char *Buffer,
251 ///                                    offset_type KeyLen);
252 ///   /// Read the data for Key from Buffer, given the DataLen as reported from
253 ///   /// ReadKeyDataLength.
254 ///   data_type ReadData(StringRef Key, const unsigned char *Buffer,
255 ///                      offset_type DataLen);
256 /// };
257 /// \endcode
258 template <typename Info> class OnDiskChainedHashTable {
259   const typename Info::offset_type NumBuckets;
260   const typename Info::offset_type NumEntries;
261   const unsigned char *const Buckets;
262   const unsigned char *const Base;
263   Info InfoObj;
264
265 public:
266   typedef typename Info::internal_key_type internal_key_type;
267   typedef typename Info::external_key_type external_key_type;
268   typedef typename Info::data_type         data_type;
269   typedef typename Info::hash_value_type   hash_value_type;
270   typedef typename Info::offset_type       offset_type;
271
272   OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
273                          const unsigned char *Buckets,
274                          const unsigned char *Base,
275                          const Info &InfoObj = Info())
276       : NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),
277         Base(Base), InfoObj(InfoObj) {
278     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
279            "'buckets' must have a 4-byte alignment");
280   }
281
282   /// Read the number of buckets and the number of entries from a hash table
283   /// produced by OnDiskHashTableGenerator::Emit, and advance the Buckets
284   /// pointer past them.
285   static std::pair<offset_type, offset_type>
286   readNumBucketsAndEntries(const unsigned char *&Buckets) {
287     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
288            "buckets should be 4-byte aligned.");
289     using namespace llvm::support;
290     offset_type NumBuckets =
291         endian::readNext<offset_type, little, aligned>(Buckets);
292     offset_type NumEntries =
293         endian::readNext<offset_type, little, aligned>(Buckets);
294     return std::make_pair(NumBuckets, NumEntries);
295   }
296
297   offset_type getNumBuckets() const { return NumBuckets; }
298   offset_type getNumEntries() const { return NumEntries; }
299   const unsigned char *getBase() const { return Base; }
300   const unsigned char *getBuckets() const { return Buckets; }
301
302   bool isEmpty() const { return NumEntries == 0; }
303
304   class iterator {
305     internal_key_type Key;
306     const unsigned char *const Data;
307     const offset_type Len;
308     Info *InfoObj;
309
310   public:
311     iterator() : Data(nullptr), Len(0) {}
312     iterator(const internal_key_type K, const unsigned char *D, offset_type L,
313              Info *InfoObj)
314         : Key(K), Data(D), Len(L), InfoObj(InfoObj) {}
315
316     data_type operator*() const { return InfoObj->ReadData(Key, Data, Len); }
317
318     const unsigned char *getDataPtr() const { return Data; }
319     offset_type getDataLen() const { return Len; }
320
321     bool operator==(const iterator &X) const { return X.Data == Data; }
322     bool operator!=(const iterator &X) const { return X.Data != Data; }
323   };
324
325   /// \brief Look up the stored data for a particular key.
326   iterator find(const external_key_type &EKey, Info *InfoPtr = nullptr) {
327     const internal_key_type &IKey = InfoObj.GetInternalKey(EKey);
328     hash_value_type KeyHash = InfoObj.ComputeHash(IKey);
329     return find_hashed(IKey, KeyHash, InfoPtr);
330   }
331
332   /// \brief Look up the stored data for a particular key with a known hash.
333   iterator find_hashed(const internal_key_type &IKey, hash_value_type KeyHash,
334                        Info *InfoPtr = nullptr) {
335     using namespace llvm::support;
336
337     if (!InfoPtr)
338       InfoPtr = &InfoObj;
339
340     // Each bucket is just an offset into the hash table file.
341     offset_type Idx = KeyHash & (NumBuckets - 1);
342     const unsigned char *Bucket = Buckets + sizeof(offset_type) * Idx;
343
344     offset_type Offset = endian::readNext<offset_type, little, aligned>(Bucket);
345     if (Offset == 0)
346       return iterator(); // Empty bucket.
347     const unsigned char *Items = Base + Offset;
348
349     // 'Items' starts with a 16-bit unsigned integer representing the
350     // number of items in this bucket.
351     unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
352
353     for (unsigned i = 0; i < Len; ++i) {
354       // Read the hash.
355       hash_value_type ItemHash =
356           endian::readNext<hash_value_type, little, unaligned>(Items);
357
358       // Determine the length of the key and the data.
359       const std::pair<offset_type, offset_type> &L =
360           Info::ReadKeyDataLength(Items);
361       offset_type ItemLen = L.first + L.second;
362
363       // Compare the hashes.  If they are not the same, skip the entry entirely.
364       if (ItemHash != KeyHash) {
365         Items += ItemLen;
366         continue;
367       }
368
369       // Read the key.
370       const internal_key_type &X =
371           InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
372
373       // If the key doesn't match just skip reading the value.
374       if (!InfoPtr->EqualKey(X, IKey)) {
375         Items += ItemLen;
376         continue;
377       }
378
379       // The key matches!
380       return iterator(X, Items + L.first, L.second, InfoPtr);
381     }
382
383     return iterator();
384   }
385
386   iterator end() const { return iterator(); }
387
388   Info &getInfoObj() { return InfoObj; }
389
390   /// \brief Create the hash table.
391   ///
392   /// \param Buckets is the beginning of the hash table itself, which follows
393   /// the payload of entire structure. This is the value returned by
394   /// OnDiskHashTableGenerator::Emit.
395   ///
396   /// \param Base is the point from which all offsets into the structure are
397   /// based. This is offset 0 in the stream that was used when Emitting the
398   /// table.
399   static OnDiskChainedHashTable *Create(const unsigned char *Buckets,
400                                         const unsigned char *const Base,
401                                         const Info &InfoObj = Info()) {
402     assert(Buckets > Base);
403     auto NumBucketsAndEntries = readNumBucketsAndEntries(Buckets);
404     return new OnDiskChainedHashTable<Info>(NumBucketsAndEntries.first,
405                                             NumBucketsAndEntries.second,
406                                             Buckets, Base, InfoObj);
407   }
408 };
409
410 /// \brief Provides lookup and iteration over an on disk hash table.
411 ///
412 /// \copydetails llvm::OnDiskChainedHashTable
413 template <typename Info>
414 class OnDiskIterableChainedHashTable : public OnDiskChainedHashTable<Info> {
415   const unsigned char *Payload;
416
417 public:
418   typedef OnDiskChainedHashTable<Info>          base_type;
419   typedef typename base_type::internal_key_type internal_key_type;
420   typedef typename base_type::external_key_type external_key_type;
421   typedef typename base_type::data_type         data_type;
422   typedef typename base_type::hash_value_type   hash_value_type;
423   typedef typename base_type::offset_type       offset_type;
424
425 private:
426   /// \brief Iterates over all of the keys in the table.
427   class iterator_base {
428     const unsigned char *Ptr;
429     offset_type NumItemsInBucketLeft;
430     offset_type NumEntriesLeft;
431
432   public:
433     typedef external_key_type value_type;
434
435     iterator_base(const unsigned char *const Ptr, offset_type NumEntries)
436         : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries) {}
437     iterator_base()
438         : Ptr(nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}
439
440     friend bool operator==(const iterator_base &X, const iterator_base &Y) {
441       return X.NumEntriesLeft == Y.NumEntriesLeft;
442     }
443     friend bool operator!=(const iterator_base &X, const iterator_base &Y) {
444       return X.NumEntriesLeft != Y.NumEntriesLeft;
445     }
446
447     /// Move to the next item.
448     void advance() {
449       using namespace llvm::support;
450       if (!NumItemsInBucketLeft) {
451         // 'Items' starts with a 16-bit unsigned integer representing the
452         // number of items in this bucket.
453         NumItemsInBucketLeft =
454             endian::readNext<uint16_t, little, unaligned>(Ptr);
455       }
456       Ptr += sizeof(hash_value_type); // Skip the hash.
457       // Determine the length of the key and the data.
458       const std::pair<offset_type, offset_type> &L =
459           Info::ReadKeyDataLength(Ptr);
460       Ptr += L.first + L.second;
461       assert(NumItemsInBucketLeft);
462       --NumItemsInBucketLeft;
463       assert(NumEntriesLeft);
464       --NumEntriesLeft;
465     }
466
467     /// Get the start of the item as written by the trait (after the hash and
468     /// immediately before the key and value length).
469     const unsigned char *getItem() const {
470       return Ptr + (NumItemsInBucketLeft ? 0 : 2) + sizeof(hash_value_type);
471     }
472   };
473
474 public:
475   OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
476                                  const unsigned char *Buckets,
477                                  const unsigned char *Payload,
478                                  const unsigned char *Base,
479                                  const Info &InfoObj = Info())
480       : base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),
481         Payload(Payload) {}
482
483   /// \brief Iterates over all of the keys in the table.
484   class key_iterator : public iterator_base {
485     Info *InfoObj;
486
487   public:
488     typedef external_key_type value_type;
489
490     key_iterator(const unsigned char *const Ptr, offset_type NumEntries,
491                  Info *InfoObj)
492         : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
493     key_iterator() : iterator_base(), InfoObj() {}
494
495     key_iterator &operator++() {
496       this->advance();
497       return *this;
498     }
499     key_iterator operator++(int) { // Postincrement
500       key_iterator tmp = *this;
501       ++*this;
502       return tmp;
503     }
504
505     internal_key_type getInternalKey() const {
506       auto *LocalPtr = this->getItem();
507
508       // Determine the length of the key and the data.
509       auto L = Info::ReadKeyDataLength(LocalPtr);
510
511       // Read the key.
512       return InfoObj->ReadKey(LocalPtr, L.first);
513     }
514
515     value_type operator*() const {
516       return InfoObj->GetExternalKey(getInternalKey());
517     }
518   };
519
520   key_iterator key_begin() {
521     return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
522   }
523   key_iterator key_end() { return key_iterator(); }
524
525   iterator_range<key_iterator> keys() {
526     return make_range(key_begin(), key_end());
527   }
528
529   /// \brief Iterates over all the entries in the table, returning the data.
530   class data_iterator : public iterator_base {
531     Info *InfoObj;
532
533   public:
534     typedef data_type value_type;
535
536     data_iterator(const unsigned char *const Ptr, offset_type NumEntries,
537                   Info *InfoObj)
538         : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
539     data_iterator() : iterator_base(), InfoObj() {}
540
541     data_iterator &operator++() { // Preincrement
542       this->advance();
543       return *this;
544     }
545     data_iterator operator++(int) { // Postincrement
546       data_iterator tmp = *this;
547       ++*this;
548       return tmp;
549     }
550
551     value_type operator*() const {
552       auto *LocalPtr = this->getItem();
553
554       // Determine the length of the key and the data.
555       auto L = Info::ReadKeyDataLength(LocalPtr);
556
557       // Read the key.
558       const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
559       return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
560     }
561   };
562
563   data_iterator data_begin() {
564     return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
565   }
566   data_iterator data_end() { return data_iterator(); }
567
568   iterator_range<data_iterator> data() {
569     return make_range(data_begin(), data_end());
570   }
571
572   /// \brief Create the hash table.
573   ///
574   /// \param Buckets is the beginning of the hash table itself, which follows
575   /// the payload of entire structure. This is the value returned by
576   /// OnDiskHashTableGenerator::Emit.
577   ///
578   /// \param Payload is the beginning of the data contained in the table.  This
579   /// is Base plus any padding or header data that was stored, ie, the offset
580   /// that the stream was at when calling Emit.
581   ///
582   /// \param Base is the point from which all offsets into the structure are
583   /// based. This is offset 0 in the stream that was used when Emitting the
584   /// table.
585   static OnDiskIterableChainedHashTable *
586   Create(const unsigned char *Buckets, const unsigned char *const Payload,
587          const unsigned char *const Base, const Info &InfoObj = Info()) {
588     assert(Buckets > Base);
589     auto NumBucketsAndEntries =
590         OnDiskIterableChainedHashTable<Info>::readNumBucketsAndEntries(Buckets);
591     return new OnDiskIterableChainedHashTable<Info>(
592         NumBucketsAndEntries.first, NumBucketsAndEntries.second,
593         Buckets, Payload, Base, InfoObj);
594   }
595 };
596
597 } // end namespace llvm
598
599 #endif