Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- LazyRandomTypeCollection.h -------------------------------*- C++ -*-===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8.  
  9. #ifndef LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
  10. #define LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
  11.  
  12. #include "llvm/ADT/ArrayRef.h"
  13. #include "llvm/ADT/StringRef.h"
  14. #include "llvm/DebugInfo/CodeView/TypeCollection.h"
  15. #include "llvm/DebugInfo/CodeView/TypeIndex.h"
  16. #include "llvm/Support/Allocator.h"
  17. #include "llvm/Support/BinaryStreamArray.h"
  18. #include "llvm/Support/Error.h"
  19. #include "llvm/Support/StringSaver.h"
  20. #include <cstdint>
  21. #include <vector>
  22.  
  23. namespace llvm {
  24. namespace codeview {
  25.  
  26. /// Provides amortized O(1) random access to a CodeView type stream.
  27. /// Normally to access a type from a type stream, you must know its byte
  28. /// offset into the type stream, because type records are variable-lengthed.
  29. /// However, this is not the way we prefer to access them.  For example, given
  30. /// a symbol record one of the fields may be the TypeIndex of the symbol's
  31. /// type record.  Or given a type record such as an array type, there might
  32. /// be a TypeIndex for the element type.  Sequential access is perfect when
  33. /// we're just dumping every entry, but it's very poor for real world usage.
  34. ///
  35. /// Type streams in PDBs contain an additional field which is a list of pairs
  36. /// containing indices and their corresponding offsets, roughly every ~8KB of
  37. /// record data.  This general idea need not be confined to PDBs though.  By
  38. /// supplying such an array, the producer of a type stream can allow the
  39. /// consumer much better access time, because the consumer can find the nearest
  40. /// index in this array, and do a linear scan forward only from there.
  41. ///
  42. /// LazyRandomTypeCollection implements this algorithm, but additionally goes
  43. /// one step further by caching offsets of every record that has been visited at
  44. /// least once.  This way, even repeated visits of the same record will never
  45. /// require more than one linear scan.  For a type stream of N elements divided
  46. /// into M chunks of roughly equal size, this yields a worst case lookup time
  47. /// of O(N/M) and an amortized time of O(1).
  48. class LazyRandomTypeCollection : public TypeCollection {
  49.   using PartialOffsetArray = FixedStreamArray<TypeIndexOffset>;
  50.  
  51.   struct CacheEntry {
  52.     CVType Type;
  53.     uint32_t Offset;
  54.     StringRef Name;
  55.   };
  56.  
  57. public:
  58.   explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
  59.   LazyRandomTypeCollection(StringRef Data, uint32_t RecordCountHint);
  60.   LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
  61.   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
  62.                            PartialOffsetArray PartialOffsets);
  63.   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
  64.  
  65.   void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
  66.   void reset(StringRef Data, uint32_t RecordCountHint);
  67.   void reset(BinaryStreamReader &Reader, uint32_t RecordCountHint);
  68.  
  69.   uint32_t getOffsetOfType(TypeIndex Index);
  70.  
  71.   std::optional<CVType> tryGetType(TypeIndex Index);
  72.  
  73.   CVType getType(TypeIndex Index) override;
  74.   StringRef getTypeName(TypeIndex Index) override;
  75.   bool contains(TypeIndex Index) override;
  76.   uint32_t size() override;
  77.   uint32_t capacity() override;
  78.   std::optional<TypeIndex> getFirst() override;
  79.   std::optional<TypeIndex> getNext(TypeIndex Prev) override;
  80.   bool replaceType(TypeIndex &Index, CVType Data, bool Stabilize) override;
  81.  
  82. private:
  83.   Error ensureTypeExists(TypeIndex Index);
  84.   void ensureCapacityFor(TypeIndex Index);
  85.  
  86.   Error visitRangeForType(TypeIndex TI);
  87.   Error fullScanForType(TypeIndex TI);
  88.   void visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
  89.  
  90.   /// Number of actual records.
  91.   uint32_t Count = 0;
  92.  
  93.   /// The largest type index which we've visited.
  94.   TypeIndex LargestTypeIndex = TypeIndex::None();
  95.  
  96.   BumpPtrAllocator Allocator;
  97.   StringSaver NameStorage;
  98.  
  99.   /// The type array to allow random access visitation of.
  100.   CVTypeArray Types;
  101.  
  102.   std::vector<CacheEntry> Records;
  103.  
  104.   /// An array of index offsets for the given type stream, allowing log(N)
  105.   /// lookups of a type record by index.  Similar to KnownOffsets but only
  106.   /// contains offsets for some type indices, some of which may not have
  107.   /// ever been visited.
  108.   PartialOffsetArray PartialOffsets;
  109. };
  110.  
  111. } // end namespace codeview
  112. } // end namespace llvm
  113.  
  114. #endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
  115.