Small optimizations for SourceManager::getFileID()

[djasper]

Summary

Specifically:

• Separate one-entry cache for loaded and local files
• Use bound that can be deduced from that cache for LessIndex
• Address FIXME to use a faster alternative to isOffsetInFileID()

No functional changes intended.

[djasper]

Ping?

[bruno]

Hi Daniel,

This seems pretty nice. Can you share how much performance improvements you got by this / how did you test it?

[alexander-shaposhnikov]

lib/Basic/SourceManager.cpp

843

not particularly important (and unrelated to your changes) - nit - s /C-style cast / static_cast / ?

include/clang/Basic/SourceManager.h

class SourceManager : public RefCountedBase<SourceManager> {
   ExternalSLocEntrySource *ExternalSLocEntries;
 
   /// \brief 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.
   mutable FileID LastFileIDLookup;
 
+  /// \brief Same as \c LastFileIDLookup, but for loaded file IDs.
+  mutable FileID LastLoadedFileIDLookup;
+
   /// \brief Holds information for \#line directives.
   ///
   /// This is referenced by indices from SLocEntryTable.
   LineTableInfo *LineTable;
 
   /// \brief These ivars serve as a cache used in the getLineNumber
   /// method which is used to speedup getLineNumber calls to nearby locations.
   mutable FileID LastLineNoFileIDQuery;
public:
   /// This is a very hot method that is used for all SourceManager queries
   /// that start with a SourceLocation object.  It is responsible for finding
   /// the entry in SLocEntryTable which contains the specified location.
   ///
   FileID getFileID(SourceLocation SpellingLoc) const {
     unsigned SLocOffset = SpellingLoc.getOffset();
 
     // If our one-entry cache covers this offset, just return it.
-    if (isOffsetInFileID(LastFileIDLookup, SLocOffset))
+    if (isLocalSourceLocation(SpellingLoc) &&
+        isOffsetInFileID(LastFileIDLookup, SLocOffset))
       return LastFileIDLookup;
+    if (isLoadedSourceLocation(SpellingLoc) &&
+        isOffsetInFileID(LastLoadedFileIDLookup, SLocOffset))
+      return LastLoadedFileIDLookup;
 
     return getFileIDSlow(SLocOffset);
   }
 
   /// \brief Return the filename of the file containing a SourceLocation.
   StringRef getFilename(SourceLocation SpellingLoc) const {
     if (const FileEntry *F = getFileEntryForID(getFileID(SpellingLoc)))
       return F->getName();

lib/Basic/SourceManager.cpp

 void SourceManager::clearIDTables() {
   MainFileID = FileID();
   LocalSLocEntryTable.clear();
   LoadedSLocEntryTable.clear();
   SLocEntryLoaded.clear();
   LastLineNoFileIDQuery = FileID();
   LastLineNoContentCache = nullptr;
   LastFileIDLookup = FileID();
+  LastLoadedFileIDLookup = FileID();
 
   if (LineTable)
     LineTable->clear();
 
   // Use up FileID #0 as an invalid expansion.
   NextLocalOffset = 0;
   CurrentLoadedOffset = MaxLoadedOffset;
   createExpansionLoc(SourceLocation(),SourceLocation(),SourceLocation(), 1);
assert(NextLocalOffset + FileSize + 1 > NextLocalOffset &&
          NextLocalOffset + FileSize + 1 <= CurrentLoadedOffset &&
          "Ran out of source locations!");
   // We do a +1 here because we want a SourceLocation that means "the end of the
   // file", e.g. for the "no newline at the end of the file" diagnostic.
   NextLocalOffset += FileSize + 1;
 
   // Set LastFileIDLookup to the newly created file.  The next getFileID call is
   // almost guaranteed to be from that file.
-  FileID FID = FileID::get(LocalSLocEntryTable.size()-1);
-  return LastFileIDLookup = FID;
+  LastFileIDLookup = FileID::get(LocalSLocEntryTable.size()-1);
+  return LastFileIDLookup;
 }
 
 SourceLocation
 SourceManager::createMacroArgExpansionLoc(SourceLocation SpellingLoc,
                                           SourceLocation ExpansionLoc,
                                           unsigned TokLength) {
   ExpansionInfo Info = ExpansionInfo::createForMacroArg(SpellingLoc,
                                                         ExpansionLoc);
FileID SourceManager::getFileIDLocal(unsigned SLocOffset) const {
   // To handle this, we do a linear search for up to 8 steps to catch #1 quickly
   // then we fall back to a less cache efficient, but more scalable, binary
   // search to find the location.
 
   // See if this is near the file point - worst case we start scanning from the
   // most newly created FileID.
   const SrcMgr::SLocEntry *I;
 
-  if (LastFileIDLookup.ID < 0 ||
-      LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) {
-    // Neither loc prunes our search.
+  int LastID = LastFileIDLookup.ID;
+  // LessIndex - This is the lower bound of the range that we're searching.
+  // We know that the offset corresponding to the FileID is less than
+  // SLocOffset.
+  unsigned LessIndex = 0;
+  if (LastID < 0) {
+    I = LocalSLocEntryTable.end();
+  } else if (LocalSLocEntryTable[LastID].getOffset() < SLocOffset) {
     I = LocalSLocEntryTable.end();
+    LessIndex = LastID;
   } else {
     // Perhaps it is near the file point.
     I = LocalSLocEntryTable.begin()+LastFileIDLookup.ID;
   }
 
   // Find the FileID that contains this.  "I" is an iterator that points to a
   // FileID whose offset is known to be larger than SLocOffset.
   unsigned NumProbes = 0;
while (1) {
     }
     if (++NumProbes == 8)
       break;
   }
 
   // Convert "I" back into an index.  We know that it is an entry whose index is
   // larger than the offset we are looking for.
   unsigned GreaterIndex = I - LocalSLocEntryTable.begin();
-  // LessIndex - This is the lower bound of the range that we're searching.
-  // We know that the offset corresponding to the FileID is is less than
-  // SLocOffset.
-  unsigned LessIndex = 0;
   NumProbes = 0;
   while (1) {
     bool Invalid = false;
     unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex;
     unsigned MidOffset = getLocalSLocEntry(MiddleIndex, &Invalid).getOffset();
     if (Invalid)
       return FileID::get(0);
-    
     ++NumProbes;
 
     // If the offset of the midpoint is too large, chop the high side of the
     // range to the midpoint.
     if (MidOffset > SLocOffset) {
       GreaterIndex = MiddleIndex;
       continue;
     }
 
     // If the middle index contains the value, succeed and return.
-    // FIXME: This could be made faster by using a function that's aware of
-    // being in the local area.
-    if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) {
+    if (SLocOffset < LocalSLocEntryTable[MiddleIndex + 1].getOffset()) {
       FileID Res = FileID::get(MiddleIndex);
 
       // If this isn't a macro expansion, remember it.  We have good locality
       // across FileID lookups.
       if (!LocalSLocEntryTable[MiddleIndex].isExpansion())
         LastFileIDLookup = Res;
       NumBinaryProbes += NumProbes;
       return Res;
if (SLocOffset < CurrentLoadedOffset) {
     return FileID();
   }
 
   // Essentially the same as the local case, but the loaded array is sorted
   // in the other direction.
 
   // First do a linear scan from the last lookup position, if possible.
   unsigned I;
-  int LastID = LastFileIDLookup.ID;
-  if (LastID >= 0 || getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset)
+  int LastID = LastLoadedFileIDLookup.ID;
+  unsigned LessIndex = LoadedSLocEntryTable.size();
+  if (LastID >= 0) {
     I = 0;
-  else
+  } else if (getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset) {
+    I = 0;
+    LessIndex = (-LastID - 2);
+  } else {
     I = (-LastID - 2) + 1;
+  }
 
   unsigned NumProbes;
   for (NumProbes = 0; NumProbes < 8; ++NumProbes, ++I) {
     // Make sure the entry is loaded!
     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(I);
     if (E.getOffset() <= SLocOffset) {
       FileID Res = FileID::get(-int(I) - 2);
 
       if (!E.isExpansion())
-        LastFileIDLookup = Res;
+        LastLoadedFileIDLookup = Res;
       NumLinearScans += NumProbes + 1;
       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();
   NumProbes = 0;
   while (1) {
     ++NumProbes;
     unsigned MiddleIndex = (LessIndex - GreaterIndex) / 2 + GreaterIndex;
     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(MiddleIndex);
     if (E.getOffset() == 0)
       return FileID(); // invalid entry.
 
     ++NumProbes;
 
     if (E.getOffset() > SLocOffset) {
       // Sanity checking, otherwise a bug may lead to hanging in release build.
       if (GreaterIndex == MiddleIndex) {
         assert(0 && "binary search missed the entry");
         return FileID();
       }
       GreaterIndex = MiddleIndex;
       continue;
     }
 
-    if (isOffsetInFileID(FileID::get(-int(MiddleIndex) - 2), SLocOffset)) {
+    if (getLoadedSLocEntry(MiddleIndex - 1).getOffset() > SLocOffset) {
       FileID Res = FileID::get(-int(MiddleIndex) - 2);
       if (!E.isExpansion())
-        LastFileIDLookup = Res;
+        LastLoadedFileIDLookup = Res;
       NumBinaryProbes += NumProbes;
       return Res;
     }
 
     // Sanity checking, otherwise a bug may lead to hanging in release build.
     if (LessIndex == MiddleIndex) {
       assert(0 && "binary search missed the entry");
       return FileID();