[clang][AST] Use 64 bit integers for bit offsets inside AST file

[DmitryPolukhin]

Summary

This diff is for discussion how to address problem with large preamble file.

32 bit offsets can be used for PCH/preamble files below 512M. This diff fixes
crashes and asserts on clangd when preamble file exceeds 512M limit. The asserts
usually look like "LLVM ERROR: Invalid abbrev number". On about 700M preamble
files this patch increases file size on about 4%. I tested this diff on
Clang 8, 9 and master.

Test Plan:
Tested on clangd with 700M preamble file. 

[aganea]

Hello Dmitry! Could we use varints instead of uint64_t if size on disk is a concern?

[DmitryPolukhin]

In D76295#1927041, @aganea wrote:

Hello Dmitry! Could we use varints instead of uint64_t if size on disk is a concern?

Variants are very close to LLVM Bitcode Variable Width Integers that can be even smaller than byte. So I think the answer is yes but it will require replacing blobs with encoded values and I'm not sure why it was not implemented this way from the beginning taking into account that mechanism exists. Perhaps it happens because indices can be memory mapped and used as is without expansion in memory.

[DmitryPolukhin]

Relative 32-bit offsets in https://reviews.llvm.org/D76594

clang/include/clang/Serialization/ASTWriter.h

private:
   /// Offsets of sub-stmts already serialized. The offset points
   /// just after the stmt record.
   llvm::DenseMap<Stmt *, uint64_t> SubStmtEntries;
 
   /// @}
 
   /// Offsets of each of the identifier IDs into the identifier
   /// table.
-  std::vector<uint32_t> IdentifierOffsets;
+  std::vector<uint64_t> IdentifierOffsets;
 
   /// The first ID number we can use for our own submodules.
   serialization::SubmoduleID FirstSubmoduleID =
       serialization::NUM_PREDEF_SUBMODULE_IDS;
 
   /// The submodule ID that will be assigned to the next new submodule.
   serialization::SubmoduleID NextSubmoduleID = FirstSubmoduleID;
 
   /// The first ID number we can use for our own selectors.
   serialization::SelectorID FirstSelectorID =
       serialization::NUM_PREDEF_SELECTOR_IDS;
 
   /// The selector ID that will be assigned to the next new selector.
   serialization::SelectorID NextSelectorID = FirstSelectorID;
 
   /// Map that provides the ID numbers of each Selector.
   llvm::MapVector<Selector, serialization::SelectorID> SelectorIDs;
 
   /// Offset of each selector within the method pool/selector
   /// table, indexed by the Selector ID (-1).
-  std::vector<uint32_t> SelectorOffsets;
+  std::vector<uint64_t> SelectorOffsets;
 
   /// Mapping from macro definitions (as they occur in the preprocessing
   /// record) to the macro IDs.
   llvm::DenseMap<const MacroDefinitionRecord *,
                  serialization::PreprocessedEntityID> MacroDefinitions;
 
   /// Cache of indices of anonymous declarations within their lexical
   /// contexts.
public:
 
   /// Retrieve or create a submodule ID for this module, or return 0 if
   /// the submodule is neither local (a submodle of the currently-written module)
   /// nor from an imported module.
   unsigned getLocalOrImportedSubmoduleID(Module *Mod);
 
   /// Note that the identifier II occurs at the given offset
   /// within the identifier table.
-  void SetIdentifierOffset(const IdentifierInfo *II, uint32_t Offset);
+  void SetIdentifierOffset(const IdentifierInfo *II, uint64_t Offset);
 
   /// Note that the selector Sel occurs at the given offset
   /// within the method pool/selector table.
-  void SetSelectorOffset(Selector Sel, uint32_t Offset);
+  void SetSelectorOffset(Selector Sel, uint64_t Offset);
 
   /// Record an ID for the given switch-case statement.
   unsigned RecordSwitchCaseID(SwitchCase *S);
 
   /// Retrieve the ID for the given switch-case statement.
   unsigned getSwitchCaseID(SwitchCase *S);
 
   void ClearSwitchCaseIDs();

clang/include/clang/Serialization/ModuleFile.h

public:
   /// The base ID in the source manager's view of this module.
   int SLocEntryBaseID = 0;
 
   /// The base offset in the source manager's view of this module.
   unsigned SLocEntryBaseOffset = 0;
 
   /// Offsets for all of the source location entries in the
   /// AST file.
-  const uint32_t *SLocEntryOffsets = nullptr;
+  const uint64_t *SLocEntryOffsets = nullptr;
 
   /// SLocEntries that we're going to preload.
   SmallVector<uint64_t, 4> PreloadSLocEntries;
 
   /// Remapping table for source locations in this module.
   ContinuousRangeMap<uint32_t, int, 2> SLocRemap;
 
   // === Identifiers ===
 
   /// The number of identifiers in this AST file.
   unsigned LocalNumIdentifiers = 0;
 
   /// Offsets into the identifier table data.
   ///
   /// This array is indexed by the identifier ID (-1), and provides
   /// the offset into IdentifierTableData where the string data is
   /// stored.
-  const uint32_t *IdentifierOffsets = nullptr;
+  const uint64_t *IdentifierOffsets = nullptr;
 
   /// Base identifier ID for identifiers local to this module.
   serialization::IdentID BaseIdentifierID = 0;
 
   /// Remapping table for identifier IDs in this module.
   ContinuousRangeMap<uint32_t, int, 2> IdentifierRemap;
 
   /// Actual data for the on-disk hash table of identifiers.
public:
   /// The number of macros in this AST file.
   unsigned LocalNumMacros = 0;
 
   /// Offsets of macros in the preprocessor block.
   ///
   /// This array is indexed by the macro ID (-1), and provides
   /// the offset into the preprocessor block where macro definitions are
   /// stored.
-  const uint32_t *MacroOffsets = nullptr;
+  const uint64_t *MacroOffsets = nullptr;
 
   /// Base macro ID for macros local to this module.
   serialization::MacroID BaseMacroID = 0;
 
   /// Remapping table for macro IDs in this module.
   ContinuousRangeMap<uint32_t, int, 2> MacroRemap;
 
   /// The offset of the start of the set of defined macros.
public:
 
   /// The number of selectors new to this file.
   ///
   /// This is the number of entries in SelectorOffsets.
   unsigned LocalNumSelectors = 0;
 
   /// Offsets into the selector lookup table's data array
   /// where each selector resides.
-  const uint32_t *SelectorOffsets = nullptr;
+  const uint64_t *SelectorOffsets = nullptr;
 
   /// Base selector ID for selectors local to this module.
   serialization::SelectorID BaseSelectorID = 0;
 
   /// Remapping table for selector IDs in this module.
   ContinuousRangeMap<uint32_t, int, 2> SelectorRemap;
 
   /// A pointer to the character data that comprises the selector table

clang/lib/Serialization/ASTReader.cpp

if (Poisoned)
     II->setIsPoisoned(true);
   assert(II->isCPlusPlusOperatorKeyword() == CPlusPlusOperatorKeyword &&
          "Incorrect C++ operator keyword flag");
   (void)CPlusPlusOperatorKeyword;
 
   // If this identifier is a macro, deserialize the macro
   // definition.
   if (HadMacroDefinition) {
-    uint32_t MacroDirectivesOffset =
-        endian::readNext<uint32_t, little, unaligned>(d);
-    DataLen -= 4;
+    uint64_t MacroDirectivesOffset =
+        endian::readNext<uint64_t, little, unaligned>(d);
+    DataLen -= 8;
 
     Reader.addPendingMacro(II, &F, MacroDirectivesOffset);
   }
 
   Reader.SetIdentifierInfo(ID, II);
 
   // Read all of the declarations visible at global scope with this
   // name.
case IDENTIFIER_TABLE:
       }
       break;
 
     case IDENTIFIER_OFFSET: {
       if (F.LocalNumIdentifiers != 0) {
         Error("duplicate IDENTIFIER_OFFSET record in AST file");
         return Failure;
       }
-      F.IdentifierOffsets = (const uint32_t *)Blob.data();
+      F.IdentifierOffsets = (const uint64_t *)Blob.data();
       F.LocalNumIdentifiers = Record[0];
       unsigned LocalBaseIdentifierID = Record[1];
       F.BaseIdentifierID = getTotalNumIdentifiers();
 
       if (F.LocalNumIdentifiers > 0) {
         // Introduce the global -> local mapping for identifiers within this
         // module.
         GlobalIdentifierMap.insert(std::make_pair(getTotalNumIdentifiers() + 1,
case WEAK_UNDECLARED_IDENTIFIERS:
           getGlobalIdentifierID(F, Record[I++]));
         WeakUndeclaredIdentifiers.push_back(
           ReadSourceLocation(F, Record, I).getRawEncoding());
         WeakUndeclaredIdentifiers.push_back(Record[I++]);
       }
       break;
 
     case SELECTOR_OFFSETS: {
-      F.SelectorOffsets = (const uint32_t *)Blob.data();
+      F.SelectorOffsets = (const uint64_t *)Blob.data();
       F.LocalNumSelectors = Record[0];
       unsigned LocalBaseSelectorID = Record[1];
       F.BaseSelectorID = getTotalNumSelectors();
 
       if (F.LocalNumSelectors > 0) {
         // Introduce the global -> local mapping for selectors within this
         // module.
         GlobalSelectorMap.insert(std::make_pair(getTotalNumSelectors()+1, &F));
case PP_COUNTER_VALUE:
       break;
 
     case FILE_SORTED_DECLS:
       F.FileSortedDecls = (const DeclID *)Blob.data();
       F.NumFileSortedDecls = Record[0];
       break;
 
     case SOURCE_LOCATION_OFFSETS: {
-      F.SLocEntryOffsets = (const uint32_t *)Blob.data();
+      F.SLocEntryOffsets = (const uint64_t *)Blob.data();
       F.LocalNumSLocEntries = Record[0];
       unsigned SLocSpaceSize = Record[1];
       std::tie(F.SLocEntryBaseID, F.SLocEntryBaseOffset) =
           SourceMgr.AllocateLoadedSLocEntries(F.LocalNumSLocEntries,
                                               SLocSpaceSize);
       if (!F.SLocEntryBaseID) {
         Error("ran out of source locations");
         break;
case IMPORTED_MODULES:
       }
       break;
 
     case MACRO_OFFSET: {
       if (F.LocalNumMacros != 0) {
         Error("duplicate MACRO_OFFSET record in AST file");
         return Failure;
       }
-      F.MacroOffsets = (const uint32_t *)Blob.data();
+      F.MacroOffsets = (const uint64_t *)Blob.data();
       F.LocalNumMacros = Record[0];
       unsigned LocalBaseMacroID = Record[1];
       F.BaseMacroID = getTotalNumMacros();
 
       if (F.LocalNumMacros > 0) {
         // Introduce the global -> local mapping for macros within this module.
         GlobalMacroMap.insert(std::make_pair(getTotalNumMacros() + 1, &F));
 

clang/lib/Serialization/ASTWriter.cpp

void ASTWriter::WriteSourceManagerBlock(SourceManager &SourceMgr,
   unsigned SLocBufferAbbrv = CreateSLocBufferAbbrev(Stream);
   unsigned SLocBufferBlobAbbrv = CreateSLocBufferBlobAbbrev(Stream, false);
   unsigned SLocBufferBlobCompressedAbbrv =
       CreateSLocBufferBlobAbbrev(Stream, true);
   unsigned SLocExpansionAbbrv = CreateSLocExpansionAbbrev(Stream);
 
   // Write out the source location entry table. We skip the first
   // entry, which is always the same dummy entry.
-  std::vector<uint32_t> SLocEntryOffsets;
+  std::vector<uint64_t> SLocEntryOffsets;
   RecordData PreloadSLocs;
   SLocEntryOffsets.reserve(SourceMgr.local_sloc_entry_size() - 1);
   for (unsigned I = 1, N = SourceMgr.local_sloc_entry_size();
        I != N; ++I) {
     // Get this source location entry.
     const SrcMgr::SLocEntry *SLoc = &SourceMgr.getLocalSLocEntry(I);
     FileID FID = FileID::get(I);
     assert(&SourceMgr.getSLocEntry(FID) == SLoc);
void ASTWriter::WritePreprocessor(const Preprocessor &PP, bool IsModule) {
   }
 
   /// Offsets of each of the macros into the bitstream, indexed by
   /// the local macro ID
   ///
   /// For each identifier that is associated with a macro, this map
   /// provides the offset into the bitstream where that macro is
   /// defined.
-  std::vector<uint32_t> MacroOffsets;
+  std::vector<uint64_t> MacroOffsets;
 
   for (unsigned I = 0, N = MacroInfosToEmit.size(); I != N; ++I) {
     const IdentifierInfo *Name = MacroInfosToEmit[I].Name;
     MacroInfo *MI = MacroInfosToEmit[I].MI;
     MacroID ID = MacroInfosToEmit[I].ID;
 
     if (ID < FirstMacroID) {
       assert(0 && "Loaded MacroInfo entered MacroInfosToEmit ?");
public:
   EmitKeyDataLength(raw_ostream& Out, IdentifierInfo* II, IdentID ID) {
     unsigned KeyLen = II->getLength() + 1;
     unsigned DataLen = 4; // 4 bytes for the persistent ID << 1
     auto MacroOffset = Writer.getMacroDirectivesOffset(II);
     if (isInterestingIdentifier(II, MacroOffset)) {
       DataLen += 2; // 2 bytes for builtin ID
       DataLen += 2; // 2 bytes for flags
       if (MacroOffset)
-        DataLen += 4; // MacroDirectives offset.
+        DataLen += 8; // MacroDirectives offset.
 
       if (NeedDecls) {
         for (IdentifierResolver::iterator D = IdResolver.begin(II),
                                        DEnd = IdResolver.end();
              D != DEnd; ++D)
           DataLen += 4;
       }
     }
void EmitData(raw_ostream& Out, IdentifierInfo* II,
     Bits = (Bits << 1) | unsigned(II->isExtensionToken());
     Bits = (Bits << 1) | unsigned(II->isPoisoned());
     Bits = (Bits << 1) | unsigned(II->hasRevertedBuiltin());
     Bits = (Bits << 1) | unsigned(II->hasRevertedTokenIDToIdentifier());
     Bits = (Bits << 1) | unsigned(II->isCPlusPlusOperatorKeyword());
     LE.write<uint16_t>(Bits);
 
     if (HadMacroDefinition)
-      LE.write<uint32_t>(MacroOffset);
+      LE.write<uint64_t>(MacroOffset);
 
     if (NeedDecls) {
       // Emit the declaration IDs in reverse order, because the
       // IdentifierResolver provides the declarations as they would be
       // visible (e.g., the function "stat" would come before the struct
       // "stat"), but the ASTReader adds declarations to the end of the list
       // (so we need to see the struct "stat" before the function "stat").
       // Only emit declarations that aren't from a chained PCH, though.
void ASTWriter::AddVersionTuple(const VersionTuple &Version,
   if (Optional<unsigned> Subminor = Version.getSubminor())
     Record.push_back(*Subminor + 1);
   else
     Record.push_back(0);
 }
 
 /// Note that the identifier II occurs at the given offset
 /// within the identifier table.
-void ASTWriter::SetIdentifierOffset(const IdentifierInfo *II, uint32_t Offset) {
+void ASTWriter::SetIdentifierOffset(const IdentifierInfo *II, uint64_t Offset) {
   IdentID ID = IdentifierIDs[II];
   // Only store offsets new to this AST file. Other identifier names are looked
   // up earlier in the chain and thus don't need an offset.
   if (ID >= FirstIdentID)
     IdentifierOffsets[ID - FirstIdentID] = Offset;
 }
 
 /// Note that the selector Sel occurs at the given offset
 /// within the method pool/selector table.
-void ASTWriter::SetSelectorOffset(Selector Sel, uint32_t Offset) {
+void ASTWriter::SetSelectorOffset(Selector Sel, uint64_t Offset) {
   unsigned ID = SelectorIDs[Sel];
   assert(ID && "Unknown selector");
   // Don't record offsets for selectors that are also available in a different
   // file.
   if (ID < FirstSelectorID)
     return;
   SelectorOffsets[ID - FirstSelectorID] = Offset;
 }