SourceManager: Don't allocate an SLocEntry until it's loaded

[dexonsmith]

Summary

Replace SLocEntryLoaded (a bitmap) with a vector of optional indices
into LoadedSLocEntryTable called LoadedSLocEntryIndices, and
allocate an SLocEntry in LoadedSLocEntryTable only once it has been
loaded. The optional index is stored using the new class
LoadedSLocEntryIndex, which has similar semantics to an
Optional<unsigned> without storage overhead. It uses 0 as a sentinel
to allow zero-initialization when loading a new module and stores the
index (if present) off-by-one.

This makes the allocation for an unloaded SLocEntry 6x smaller (24B =>
4B), dramatically improving memory usage with large / many modules. It
increases memory usage for a *loaded* SLocEntry by 4B (24B => 28B).

[dexonsmith]

This should be complementary to https://reviews.llvm.org/D89580, but I think it's independent.

[teemperor]

Maybe arc didn't correctly apply the patch, but this causes a few LLDB tests to fail on my machine:

lldb-api :: commands/expression/import-std-module/queue/TestQueueFromStdModule.py
lldb-api :: commands/expression/import-std-module/list/TestListFromStdModule.py
lldb-api :: commands/expression/import-std-module/forward_list-dbg-info-content/TestDbgInfoContentForwardListFromStdModule.py

From the backtrace this seems like the ASTImporter needs to be updated:

* frame #0: 0x00007ffff25f1bb6 _lldb.so`clang::ASTImporter::Import(clang::FileID, bool) + 566
  frame #1: 0x00007ffff25ecc56 _lldb.so`clang::ASTImporter::Import(clang::SourceLocation) + 182
  frame #2: 0x00007ffff25bbaed _lldb.so`clang::SourceLocation clang::ASTNodeImporter::importChecked<clang::SourceLocation>(llvm::Error&, clang::SourceLocation const&) + 61
  frame #3: 0x00007ffff25c34e8 _lldb.so`clang::ASTNodeImporter::VisitFunctionDecl(clang::FunctionDecl*) + 2968
  frame #4: 0x00007ffff25ebb31 _lldb.so`clang::declvisitor::Base<std::add_pointer, clang::ASTNodeImporter, llvm::Expected<clang::Decl*> >::Visit(clang::Decl*) + 81
  frame #5: 0x00007ffff25ebac2 _lldb.so`clang::ASTImporter::ImportImpl(clang::Decl*) + 34
  frame #6: 0x00007ffff0df9cb1 _lldb.so`lldb_private::ClangASTImporter::ASTImporterDelegate::ImportImpl(clang::Decl*) + 1345
  frame #7: 0x00007ffff25ed3f4 _lldb.so`clang::ASTImporter::Import(clang::Decl*) + 532
  frame #8: 0x00007ffff25aeb93 _lldb.so`llvm::Expected<clang::ValueDecl*> clang::ASTNodeImport

The tests are just loading a Clang module and then trying to import some Decls into another ASTContext, so I don't think the error here is specific to LLDB. We just don't have any ASTImporter tests that exercise modules.

FWIW, if you quickly want to see if your SourceManager changes break LLDB, then you can just set the LIT_FILTER to "Modules" and run check-lldb as LLDB's use of Clang modules are the only place where we have any valid SourceLocations within LLDB.

Regarding the patch itself:

1. The I - 1 everywhere when translating SLocEntryLoaded values to a LoadedSLocEntryTable index is a bit cryptic. We already do similar magic in other places, but here it's really just about expressing an optional integer. Could we maybe have a wrapper function that turns this into a llvm::Optional<unsigned> (that is llvm::None when it's not loaded). Something like this maybe (which hopefully optimizes to something similar to the original code):

llvm::Optional<unsigned> getLoadedSLocEntryTableIndex(size_t Index) const {
  unsigned result = SLocEntryLoaded[Index];
  if (result == /*sentinel value*/0)
    return llvm::None;
  return result - 1U;
}

2. If we have this as an Optional, we might as well make the sentinel value std::numeric_limits<unsigned>::max() instead of 0 in SLocEntryLoaded. Then we can just all values as-is without translating them to an index.

3. Now that the primary purpose of SLocEntryLoaded is storing indices and not the loaded status, maybe something like SLocEntryIndices would be a better name?

4. Do you still have your benchmarking values (or some estimates) for this? I'm just curious how much memory this actually saves.

Otherwise I think this looks good.

[v.g.vassilev]

Thanks for the patch!! This is a super hot place for us (mostly due to boost). I will try it on our end and let you know!

[dexonsmith]

In D89749#2353651, @v.g.vassilev wrote:

Thanks for the patch!! This is a super hot place for us (mostly due to boost). I will try it on our end and let you know!

Great!

In D89749#2353602, @teemperor wrote:

Maybe arc didn't correctly apply the patch, but this causes a few LLDB tests to fail on my machine:

lldb-api :: commands/expression/import-std-module/queue/TestQueueFromStdModule.py
lldb-api :: commands/expression/import-std-module/list/TestListFromStdModule.py
lldb-api :: commands/expression/import-std-module/forward_list-dbg-info-content/TestDbgInfoContentForwardListFromStdModule.py

From the backtrace this seems like the ASTImporter needs to be updated:

Thanks for doing that legwork, I'll take a look.

The tests are just loading a Clang module and then trying to import some Decls into another ASTContext, so I don't think the error here is specific to LLDB. We just don't have any ASTImporter tests that exercise modules.

I'll add one.

FWIW, if you quickly want to see if your SourceManager changes break LLDB, then you can just set the LIT_FILTER to "Modules" and run check-lldb as LLDB's use of Clang modules are the only place where we have any valid SourceLocations within LLDB.

This is helpful, thanks. I also need to deal with whatever entitlements check-lldb needs (new machine since the last time and I remember it being non-trivial) but I'll figure that out.

1. The I - 1 everywhere when translating SLocEntryLoaded values to a LoadedSLocEntryTable index is a bit cryptic. [...]

Great comment; I think the way I'll do this is to create a simple wrapper type that degrades to Optional<unsigned>.

2. If we have this as an Optional, we might as well make the sentinel value std::numeric_limits<unsigned>::max() instead of 0 in SLocEntryLoaded. Then we can just all values as-is without translating them to an index.

Could do, but there's a tradeoff since then a resize operation can't/doesn't use zero-initialization. As a result I have a (weak) preference for a 0-sentinel (probably my next patch will keep that semantic), but I'm open to changing it.

3. Now that the primary purpose of SLocEntryLoaded is storing indices and not the loaded status, maybe something like SLocEntryIndices would be a better name?

Good idea.

4. Do you still have your benchmarking values (or some estimates) for this? I'm just curious how much memory this actually saves.

I'll find some numbers if Vassil hasn't shared his by the time I've fixed the patch.

[teemperor]

The tests are just loading a Clang module and then trying to import some Decls into another ASTContext, so I don't think the error here is specific to LLDB. We just don't have any ASTImporter tests that exercise modules.

I'll add one.

I'm actually not even sure if we have a nice framework where we could test modules + ASTImporter, so don't feel obligated to solve this as part of this patch.

FWIW, if you quickly want to see if your SourceManager changes break LLDB, then you can just set the LIT_FILTER to "Modules" and run check-lldb as LLDB's use of Clang modules are the only place where we have any valid SourceLocations within LLDB.

This is helpful, thanks. I also need to deal with whatever entitlements check-lldb needs (new machine since the last time and I remember it being non-trivial) but I'll figure that out.

1. The I - 1 everywhere when translating SLocEntryLoaded values to a LoadedSLocEntryTable index is a bit cryptic. [...]

Great comment; I think the way I'll do this is to create a simple wrapper type that degrades to Optional<unsigned>.

Thanks!

2. If we have this as an Optional, we might as well make the sentinel value std::numeric_limits<unsigned>::max() instead of 0 in SLocEntryLoaded. Then we can just all values as-is without translating them to an index.

Could do, but there's a tradeoff since then a resize operation can't/doesn't use zero-initialization. As a result I have a (weak) preference for a 0-sentinel (probably my next patch will keep that semantic), but I'm open to changing it.

True. Let's keep the 0 sentinel value for now then, I don't think the small advantage of using 2^32 is worth that trouble.

3. Now that the primary purpose of SLocEntryLoaded is storing indices and not the loaded status, maybe something like SLocEntryIndices would be a better name?

Good idea.

4. Do you still have your benchmarking values (or some estimates) for this? I'm just curious how much memory this actually saves.

I'll find some numbers if Vassil hasn't shared his by the time I've fixed the patch.

[dexonsmith]

Made the planned changes to SourceManager, wrapping the index in LoadedSLocEntryIndex which acts like an Optional<unsigned> (but still using 0 for a sentinel to allow zero-initialization).

[dexonsmith]

I still need to investigate the LLDB test failures related to ASTImporter.

[dexonsmith]

Added a unit test for LoadedSLocEntryIndex.

[dexonsmith]

In D89749#2354072, @dexonsmith wrote:

I still need to investigate the LLDB test failures related to ASTImporter.

(still to-do)

[dexonsmith]

Fix name of LoadedSLocEntryIndices (I documented it with this name, but was using SLocEntryIndices previously).

[dexonsmith]

(still need to investigate ASTImporter)

[dexonsmith]

In D89749#2353602, @teemperor wrote:

The tests are just loading a Clang module and then trying to import some Decls into another ASTContext, so I don't think the error here is specific to LLDB. We just don't have any ASTImporter tests that exercise modules.

FWIW, if you quickly want to see if your SourceManager changes break LLDB, then you can just set the LIT_FILTER to "Modules" and run check-lldb as LLDB's use of Clang modules are the only place where we have any valid SourceLocations within LLDB.

I haven't reproduced yet (still building), but I think I found the problem by inspection:

Expected<FileID> ASTImporter::Import(FileID FromID, bool IsBuiltin) {
  llvm::DenseMap<FileID, FileID>::iterator Pos = ImportedFileIDs.find(FromID);
  if (Pos != ImportedFileIDs.end())
    return Pos->second;

  SourceManager &FromSM = FromContext.getSourceManager();
  SourceManager &ToSM = ToContext.getSourceManager();
  const SrcMgr::SLocEntry &FromSLoc = FromSM.getSLocEntry(FromID);

  // Various recursive calls to Import.

After this patch, the address of SLocEntry is potentially invalidated by subsequent calls to getSLocEntry, since a load can increase the capacity of LoadedSLocEntryTable and move its allocation.

That means it's not safe to store an address from getSLocEntry when there will be another call. I can update ASTImporter to use a copy, but I think this is too much of a gotcha... I'll think more about what to do, but here are the ideas I have:

1. Return an SLocEntry by-value. After https://reviews.llvm.org/D89580 that's just 24B (down from 40B), so maybe this is reasonable.
2. Return an SLocEntryRef by-value, a new type that is (say) a pointer to the correct SLocEntryTable and an index into it. This would be 16B.

Let me know if you have thoughts.

[dexonsmith]

@teemperor, I don't get test failures:

% (cd build && env LIT_FILTER=Modules ninja -k20 check-lldb)
ld: warning: spew

Testing Time: 10.54s
  Excluded   : 2105
  Unsupported:   17
  Passed     :   13

Could this be because I used -DLLDB_USE_SYSTEM_DEBUGSERVER=ON?

If you're still seeing them, can you try the speculative fix in https://reviews.llvm.org/D90192 to confirm I understand the issue?

[dexonsmith]

In D89749#2354386, @dexonsmith wrote:

That means it's not safe to store an address from getSLocEntry when there will be another call. I can update ASTImporter to use a copy, but I think this is too much of a gotcha... I'll think more about what to do, but here are the ideas I have:

1. Return an SLocEntry by-value. After https://reviews.llvm.org/D89580 that's just 24B (down from 40B), so maybe this is reasonable.
2. Return an SLocEntryRef by-value, a new type that is (say) a pointer to the correct SLocEntryTable and an index into it. This would be 16B.

Let me know if you have thoughts.

3. Use indirection (like https://github.com/Teemperor/llvm/commit/a06b21cbc55c6d2f1d2bf6f39771411ccc17342b, but doesn't have to be lazy) to allocate SLocEntrys in non-contiguous chunks, with stable addresses.

[v.g.vassilev]

Unfortunately, the patch does not apply against llvm9 (which is what we have as experimental setup) not to speak against llvm5 which is our production setup.

Is the performance overhead for loaded module a % of the overall size of the source files?

Sorry for the naive question but what is a unloaded module?

clang/include/clang/Basic/SourceManager.h

703

We can probably remove the bitvector header include.

[dexonsmith]

In D89749#2356846, @v.g.vassilev wrote:

Is the performance overhead for loaded module a % of the overall size of the source files?

SourceManager::PrintStats almost has the information you need. One of the lines is:

llvm::errs() << LoadedSLocEntryTable.size()
               << " loaded SLocEntries allocated, "

This is how many SLocEntries have been allocated for imported ASTs (modules / PCH). But unless the corresponding bit in SLocEntryLoaded is set, it hasn't actually been "loaded", a spot has just been reserved. The first call to getSLocEntry for that location will trigger a load from the serialized AST.

Here's how you can estimate the memory usage change:

uint64_t OldMem = 0, NewMem = 0;

// Add each allocated SLocEntry. NextPowerOf2 is an estimate of the SmallVector
// load factor.
OldMem += llvm::capacity_in_bytes(LoadedSLocEntryTable);
NewMem += NextPowerOf2(SLocEntryTableLoaded.count()) * sizeof(SLocEntry);

// Add the side table overhead. We know precisely what the load factor of
// is in this case, since we have one that's the same size.
OldMem += llvm::capacity_in_bytes(SLocEntryTableLoaded);
NewMem += LoadedSLocEntryTable.capacity() * sizeof(unsigned);

If you do that calculation at the end of the compilation, you can see the memory savings.

Sorry for the naive question but what is a unloaded module?

It's an unloaded SLocEntry. After the module has been imported, the SLocEntrys are allocated, but lazily read from disk on first access. If it hasn't been read from disk yet, I'm calling it "unloaded".

clang/include/clang/Basic/SourceManager.h

703

Nice catch, I'll fix that.

clang/include/clang/Basic/SourceManager.h

 class FileEntryRef;
 class LineTableInfo;
 class SourceManager;
 
 /// Public enums and private classes that are part of the
 /// SourceManager implementation.
 namespace SrcMgr {
 
+  /// Optional index for loadable SLoc entries. Semantics of Optional<unsigned>
+  /// but without storage overhead.
+  class LoadedSLocEntryIndex {
+  public:
+    explicit operator bool() const { return Data; }
+    unsigned operator*() const {
+      assert(*this && "Dereferencing None?");
+      return Data - 1;
+    }
+
+    LoadedSLocEntryIndex &operator=(llvm::NoneType) {
+      return *this = LoadedSLocEntryIndex(None);
+    }
+    LoadedSLocEntryIndex &operator=(unsigned I) {
+      return *this = LoadedSLocEntryIndex(I);
+    }
+    LoadedSLocEntryIndex(llvm::NoneType = None) : Data(0) {}
+    LoadedSLocEntryIndex(unsigned I) : Data(I + 1) {
+      assert(*this && "Index too big");
+    }
+
+  private:
+    /// Index stored off-by-one with 0 as a sentinel to enable
+    /// zero-initialization.
+    unsigned Data;
+  };
+
   /// Indicates whether a file or directory holds normal user code,
   /// system code, or system code which is implicitly 'extern "C"' in C++ mode.
   ///
   /// Entire directories can be tagged with this (this is maintained by
   /// DirectoryLookup and friends) as can specific FileInfos when a \#pragma
   /// system_header is seen or in various other cases.
   ///
   enum CharacteristicKind {
class SourceManager : public RefCountedBase<SourceManager> {
   /// The table of SLocEntries that are local to this module.
   ///
   /// Positive FileIDs are indexes into this table. Entry 0 indicates an invalid
   /// expansion.
   SmallVector<SrcMgr::SLocEntry, 0> LocalSLocEntryTable;
 
   /// The table of SLocEntries that are loaded from other modules.
   ///
-  /// Negative FileIDs are indexes into this table. To get from ID to an index,
-  /// use (-ID - 2).
+  /// Negative FileIDs are indexes into LoadedSLocEntryIndices, which contains the
+  /// index into this table.
   SmallVector<SrcMgr::SLocEntry, 0> LoadedSLocEntryTable;
 
   /// The starting offset of the next local SLocEntry.
   ///
   /// This is LocalSLocEntryTable.back().Offset + the size of that entry.
   unsigned NextLocalOffset;
 
   /// The starting offset of the latest batch of loaded SLocEntries.
   ///
-  /// This is LoadedSLocEntryTable.back().Offset, except that that entry might
-  /// not have been loaded, so that value would be unknown.
+  /// This is LoadedSLocEntryTable[LoadedSLocEntryIndices.back()].Offset,
+  /// except that that entry might not have been loaded, so that value would be
+  /// unknown.
   unsigned CurrentLoadedOffset;
 
   /// The highest possible offset is 2^31-1, so CurrentLoadedOffset
   /// starts at 2^31.
   static const unsigned MaxLoadedOffset = 1U << 31U;
 
-  /// A bitmap that indicates whether the entries of LoadedSLocEntryTable
-  /// have already been loaded from the external source.
+  /// An optional index into LoadedSLocEntryTable, where None indicates that an
+  /// SLocEntry has not yet been allocated.
   ///
-  /// Same indexing as LoadedSLocEntryTable.
-  llvm::BitVector SLocEntryLoaded;
+  /// Negative FileIDs are indexes into this table. To get from ID to an index,
+  /// use (-ID - 2).
+  SmallVector<SrcMgr::LoadedSLocEntryIndex, 0> LoadedSLocEntryIndices;
 
   /// An external source for source location entries.
   ExternalSLocEntrySource *ExternalSLocEntries = nullptr;
 
   /// A one-entry cache to speed up getFileID.
   ///
   /// LastFileIDLookup records the last FileID looked up or created, because it
   /// is very common to look up many tokens from the same file.
public:
 
   /// Get a local SLocEntry. This is exposed for indexing.
   const SrcMgr::SLocEntry &getLocalSLocEntry(unsigned Index) const {
     assert(Index < LocalSLocEntryTable.size() && "Invalid index");
     return LocalSLocEntryTable[Index];
   }
 
   /// Get the number of loaded SLocEntries we have.
-  unsigned loaded_sloc_entry_size() const { return LoadedSLocEntryTable.size();}
+  unsigned loaded_sloc_entry_size() const { return LoadedSLocEntryIndices.size(); }
 
   /// Get a loaded SLocEntry. This is exposed for indexing.
   const SrcMgr::SLocEntry &getLoadedSLocEntry(unsigned Index,
                                               bool *Invalid = nullptr) const {
-    assert(Index < LoadedSLocEntryTable.size() && "Invalid index");
-    if (SLocEntryLoaded[Index])
-      return LoadedSLocEntryTable[Index];
+    assert(Index < LoadedSLocEntryIndices.size() && "Invalid index");
+    if (auto I = LoadedSLocEntryIndices[Index])
+      return LoadedSLocEntryTable[*I];
     return loadSLocEntry(Index, Invalid);
   }
 
   const SrcMgr::SLocEntry &getSLocEntry(FileID FID,
                                         bool *Invalid = nullptr) const {
     if (FID.ID == 0 || FID.ID == -1) {
       if (Invalid) *Invalid = true;
       return LocalSLocEntryTable[0];
     }
     return getSLocEntryByID(FID.ID, Invalid);
   }
 
   unsigned getNextLocalOffset() const { return NextLocalOffset; }
 
   void setExternalSLocEntrySource(ExternalSLocEntrySource *Source) {
-    assert(LoadedSLocEntryTable.empty() &&
+    assert(LoadedSLocEntryIndices.empty() &&
            "Invalidating existing loaded entries");
     ExternalSLocEntries = Source;
   }
 
   /// Allocate a number of loaded SLocEntries, which will be actually
   /// loaded on demand from the external source.
   ///
   /// NumSLocEntries will be allocated, which occupy a total of TotalSize space

clang/lib/Basic/SourceManager.cpp

for (llvm::DenseMap<const FileEntry*, SrcMgr::ContentCache*>::iterator
     }
   }
 }
 
 void SourceManager::clearIDTables() {
   MainFileID = FileID();
   LocalSLocEntryTable.clear();
   LoadedSLocEntryTable.clear();
-  SLocEntryLoaded.clear();
+  LoadedSLocEntryIndices.clear();
   LastLineNoFileIDQuery = FileID();
   LastLineNoContentCache = nullptr;
   LastFileIDLookup = FileID();
 
   if (LineTable)
     LineTable->clear();
 
   // Use up FileID #0 as an invalid expansion.
auto CloneContentCache = [&](const ContentCache *Cache) -> ContentCache * {
     Clone->BufferOverridden = Cache->BufferOverridden;
     Clone->IsFileVolatile = Cache->IsFileVolatile;
     Clone->IsTransient = Cache->IsTransient;
     Clone->setUnownedBuffer(Cache->getBufferIfLoaded());
     return Clone;
   };
 
   // Ensure all SLocEntries are loaded from the external source.
-  for (unsigned I = 0, N = Old.LoadedSLocEntryTable.size(); I != N; ++I)
-    if (!Old.SLocEntryLoaded[I])
+  for (unsigned I = 0, N = Old.LoadedSLocEntryIndices.size(); I != N; ++I)
+    if (!Old.LoadedSLocEntryIndices[I])
       Old.loadSLocEntry(I, nullptr);
 
   // Inherit any content cache data from the old source manager.
   for (auto &FileInfo : Old.FileInfos) {
     SrcMgr::ContentCache *&Slot = FileInfos[FileInfo.first];
     if (Slot)
       continue;
     Slot = CloneContentCache(FileInfo.second);
const ContentCache *SourceManager::createMemBufferContentCache(
   new (Entry) ContentCache();
   MemBufferInfos.push_back(Entry);
   Entry->setBuffer(std::move(Buffer));
   return Entry;
 }
 
 const SrcMgr::SLocEntry &SourceManager::loadSLocEntry(unsigned Index,
                                                       bool *Invalid) const {
-  assert(!SLocEntryLoaded[Index]);
+  assert(!LoadedSLocEntryIndices[Index]);
   if (ExternalSLocEntries->ReadSLocEntry(-(static_cast<int>(Index) + 2))) {
     if (Invalid)
       *Invalid = true;
     // If the file of the SLocEntry changed we could still have loaded it.
-    if (!SLocEntryLoaded[Index]) {
+    if (!LoadedSLocEntryIndices[Index]) {
       // Try to recover; create a SLocEntry so the rest of clang can handle it.
       if (!FakeSLocEntryForRecovery)
         FakeSLocEntryForRecovery = std::make_unique<SLocEntry>(
             SLocEntry::get(0, FileInfo::get(SourceLocation(),
                                             *getFakeContentCacheForRecovery(),
                                             SrcMgr::C_User, "")));
       return *FakeSLocEntryForRecovery;
     }
   }
 
-  return LoadedSLocEntryTable[Index];
+  assert(LoadedSLocEntryIndices[Index] && "Failed to load but returned success");
+  return LoadedSLocEntryTable[*LoadedSLocEntryIndices[Index]];
 }
 
 std::pair<int, unsigned>
 SourceManager::AllocateLoadedSLocEntries(unsigned NumSLocEntries,
                                          unsigned TotalSize) {
   assert(ExternalSLocEntries && "Don't have an external sloc source");
   // Make sure we're not about to run out of source locations.
   if (CurrentLoadedOffset - TotalSize < NextLocalOffset)
     return std::make_pair(0, 0);
-  LoadedSLocEntryTable.resize(LoadedSLocEntryTable.size() + NumSLocEntries);
-  SLocEntryLoaded.resize(LoadedSLocEntryTable.size());
+  LoadedSLocEntryIndices.resize(LoadedSLocEntryIndices.size() + NumSLocEntries);
   CurrentLoadedOffset -= TotalSize;
-  int ID = LoadedSLocEntryTable.size();
+  int ID = LoadedSLocEntryIndices.size();
   return std::make_pair(-ID - 1, CurrentLoadedOffset);
 }
 
 /// As part of recovering from missing or changed content, produce a
 /// fake, non-empty buffer.
 llvm::MemoryBuffer *SourceManager::getFakeBufferForRecovery() const {
   if (!FakeBufferForRecovery)
     FakeBufferForRecovery =
FileID SourceManager::getPreviousFileID(FileID FID) const {
 
   int ID = FID.ID;
   if (ID == -1)
     return FileID();
 
   if (ID > 0) {
     if (ID-1 == 0)
       return FileID();
-  } else if (unsigned(-(ID-1) - 2) >= LoadedSLocEntryTable.size()) {
+  } else if (unsigned(-(ID - 1) - 2) >= LoadedSLocEntryIndices.size()) {
     return FileID();
   }
 
   return FileID::get(ID-1);
 }
 
 /// Returns the next in-order FileID or an invalid FileID if there is
 /// no next one.

 FileID SourceManager::createFileIDImpl(const ContentCache &File,
                                        StringRef Filename,
                                        SourceLocation IncludePos,
                                        SrcMgr::CharacteristicKind FileCharacter,
                                        int LoadedID, unsigned LoadedOffset) {
   if (LoadedID < 0) {
     assert(LoadedID != -1 && "Loading sentinel FileID");
     unsigned Index = unsigned(-LoadedID) - 2;
-    assert(Index < LoadedSLocEntryTable.size() && "FileID out of range");
-    assert(!SLocEntryLoaded[Index] && "FileID already loaded");
-    LoadedSLocEntryTable[Index] = SLocEntry::get(
-        LoadedOffset, FileInfo::get(IncludePos, File, FileCharacter, Filename));
-    SLocEntryLoaded[Index] = true;
+    assert(Index < LoadedSLocEntryIndices.size() && "FileID out of range");
+    assert(!LoadedSLocEntryIndices[Index] && "FileID already loaded");
+    LoadedSLocEntryIndices[Index] = LoadedSLocEntryTable.size();
+    LoadedSLocEntryTable.push_back(
+        SLocEntry::get(LoadedOffset, FileInfo::get(IncludePos, File,
+                                                   FileCharacter, Filename)));
     return FileID::get(LoadedID);
   }
   unsigned FileSize = File.getSize();
   if (!(NextLocalOffset + FileSize + 1 > NextLocalOffset &&
         NextLocalOffset + FileSize + 1 <= CurrentLoadedOffset)) {
     Diag.Report(IncludePos, diag::err_include_too_large);
     return FileID();
   }

 SourceLocation
 SourceManager::createExpansionLocImpl(const ExpansionInfo &Info,
                                       unsigned TokLength,
                                       int LoadedID,
                                       unsigned LoadedOffset) {
   if (LoadedID < 0) {
     assert(LoadedID != -1 && "Loading sentinel FileID");
     unsigned Index = unsigned(-LoadedID) - 2;
-    assert(Index < LoadedSLocEntryTable.size() && "FileID out of range");
-    assert(!SLocEntryLoaded[Index] && "FileID already loaded");
-    LoadedSLocEntryTable[Index] = SLocEntry::get(LoadedOffset, Info);
-    SLocEntryLoaded[Index] = true;
+    assert(Index < LoadedSLocEntryIndices.size() && "FileID out of range");
+    assert(!LoadedSLocEntryIndices[Index] && "FileID already loaded");
+    LoadedSLocEntryIndices[Index] = LoadedSLocEntryTable.size();
+    LoadedSLocEntryTable.push_back(SLocEntry::get(LoadedOffset, Info));
     return SourceLocation::getMacroLoc(LoadedOffset);
   }
   LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset, Info));
   assert(NextLocalOffset + TokLength + 1 > NextLocalOffset &&
          NextLocalOffset + TokLength + 1 <= CurrentLoadedOffset &&
          "Ran out of source locations!");
   // See createFileID for that +1.
   NextLocalOffset += TokLength + 1;
if (E.getOffset() <= SLocOffset) {
       return Res;
     }
   }
 
   // Linear scan failed. Do the binary search. Note the reverse sorting of the
   // table: GreaterIndex is the one where the offset is greater, which is
   // actually a lower index!
   unsigned GreaterIndex = I;
-  unsigned LessIndex = LoadedSLocEntryTable.size();
+  unsigned LessIndex = LoadedSLocEntryIndices.size();
   NumProbes = 0;
   while (true) {
     ++NumProbes;
     unsigned MiddleIndex = (LessIndex - GreaterIndex) / 2 + GreaterIndex;
     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(MiddleIndex);
     if (E.getOffset() == 0)
       return FileID(); // invalid entry.
 

 void SourceManager::PrintStats() const {
   llvm::errs() << "\n*** Source Manager Stats:\n";
   llvm::errs() << FileInfos.size() << " files mapped, " << MemBufferInfos.size()
                << " mem buffers mapped.\n";
   llvm::errs() << LocalSLocEntryTable.size() << " local SLocEntry's allocated ("
                << llvm::capacity_in_bytes(LocalSLocEntryTable)
                << " bytes of capacity), "
                << NextLocalOffset << "B of Sloc address space used.\n";
-  llvm::errs() << LoadedSLocEntryTable.size()
-               << " loaded SLocEntries allocated, "
+  llvm::errs() << LoadedSLocEntryIndices.size() << " loaded SLocEntries ("
+               << LoadedSLocEntryTable.size() << " allocated), "
                << MaxLoadedOffset - CurrentLoadedOffset
                << "B of Sloc address space used.\n";
 
   unsigned NumLineNumsComputed = 0;
   unsigned NumFileBytesMapped = 0;
   for (fileinfo_iterator I = fileinfo_begin(), E = fileinfo_end(); I != E; ++I){
     NumLineNumsComputed += bool(I->second->SourceLineCache);
     NumFileBytesMapped  += I->second->getSizeBytesMapped();
LLVM_DUMP_METHOD void SourceManager::dump() const {
   // Dump local SLocEntries.
   for (unsigned ID = 0, NumIDs = LocalSLocEntryTable.size(); ID != NumIDs; ++ID) {
     DumpSLocEntry(ID, LocalSLocEntryTable[ID],
                   ID == NumIDs - 1 ? NextLocalOffset
                                    : LocalSLocEntryTable[ID + 1].getOffset());
   }
   // Dump loaded SLocEntries.
   llvm::Optional<unsigned> NextStart;
-  for (unsigned Index = 0; Index != LoadedSLocEntryTable.size(); ++Index) {
+  for (unsigned Index = 0; Index != LoadedSLocEntryIndices.size(); ++Index) {
     int ID = -(int)Index - 2;
-    if (SLocEntryLoaded[Index]) {
-      DumpSLocEntry(ID, LoadedSLocEntryTable[Index], NextStart);
-      NextStart = LoadedSLocEntryTable[Index].getOffset();
+    if (auto I = LoadedSLocEntryIndices[Index]) {
+      DumpSLocEntry(ID, LoadedSLocEntryTable[*I], NextStart);
+      NextStart = LoadedSLocEntryTable[*I].getOffset();
     } else {
       NextStart = None;
     }
   }
 }
 
 ExternalSLocEntrySource::~ExternalSLocEntrySource() = default;
 
SourceManager::MemoryBufferSizes SourceManager::getMemoryBufferSizes() const {
 
   return MemoryBufferSizes(malloc_bytes, mmap_bytes);
 }
 
 size_t SourceManager::getDataStructureSizes() const {
   size_t size = llvm::capacity_in_bytes(MemBufferInfos)
     + llvm::capacity_in_bytes(LocalSLocEntryTable)
     + llvm::capacity_in_bytes(LoadedSLocEntryTable)
-    + llvm::capacity_in_bytes(SLocEntryLoaded)
+    + llvm::capacity_in_bytes(LoadedSLocEntryIndices)
     + llvm::capacity_in_bytes(FileInfos);
 
   if (OverriddenFilesInfo)
     size += llvm::capacity_in_bytes(OverriddenFilesInfo->OverriddenFiles);
 
   return size;
 }
 

clang/unittests/Basic/SourceManagerTest.cpp

TEST_F(SourceManagerTest, isMainFile) {
   FileID MainFileID = SourceMgr.getOrCreateFileID(SourceFile, SrcMgr::C_User);
   SourceMgr.setMainFileID(MainFileID);
 
   EXPECT_TRUE(SourceMgr.isMainFile(*SourceFile));
   EXPECT_TRUE(SourceMgr.isMainFile(*SourceFile));
   EXPECT_FALSE(SourceMgr.isMainFile(*SecondFile));
 }
 
+TEST_F(SourceManagerTest, LoadedSLocEntryIndex) {
+  using SrcMgr::LoadedSLocEntryIndex;
+
+  // Check operator bool.
+  EXPECT_FALSE(LoadedSLocEntryIndex());
+  EXPECT_TRUE(LoadedSLocEntryIndex(0U));
+  EXPECT_TRUE(LoadedSLocEntryIndex(1U));
+  EXPECT_TRUE(LoadedSLocEntryIndex(-2U));
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH(LoadedSLocEntryIndex(-1U), "Index too big");
+#endif
+  EXPECT_FALSE(LoadedSLocEntryIndex(None));
+
+  // Check operator*.
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH(*LoadedSLocEntryIndex(), "Dereferencing None?");
+#endif
+  EXPECT_EQ(0U, *LoadedSLocEntryIndex(0U));
+  EXPECT_EQ(1U, *LoadedSLocEntryIndex(1U));
+  EXPECT_EQ(-2U, *LoadedSLocEntryIndex(-2U));
+
+  // Check operator=.
+  LoadedSLocEntryIndex I;
+  EXPECT_EQ(0U, *(I = 0U));
+  EXPECT_EQ(1U, *(I = 1U));
+  EXPECT_EQ(-2U, *(I = -2U));
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH((I = -1U), "Index too big");
+#endif
+  EXPECT_FALSE((I = None));
+}
+
 #endif
 
 } // anonymous namespace