[SourceManager] Improve getFileIDLoaded.

[hokein]

Summary

Similar to getFileIDLocal patch, but for the version for load module.

Test with clangd (building AST with preamble), FileID scans in binary
search is reduced:

SemaExpr.cpp: 142K -> 137K (-3%)
FindTarget.cpp: 368K -> 343K (-6%)

[sammccall]

Nice!

Just a couple of comments where we could take the opportunity to clarify the existing code. Optional.

clang/lib/Basic/SourceManager.cpp

880

This is confusing: if SLocEntry.getOffset() > SLocOffset then it means SLocOffset is *not* part the entry (entry can be pruned), but if they're equal it means it *is* part of the entry (entry should not be pruned).
Then we're pruning the entry regardless.

I think we're getting away with this because we never get here in the == case as we would have hit the cache.
But > seems clearer than >=, assuming my analysis is right.

881

I believe the +1 here is in order to exclude LastFileIDLookup.ID, and again the justification is that we would otherwise have hit the cache.

I think a short comment // Exclude LastID, else we would have hit the cache would help here

clang/lib/Basic/SourceManager.cpp

 /// local one.
 FileID SourceManager::getFileIDLoaded(SourceLocation::UIntTy SLocOffset) const {
   if (SLocOffset < CurrentLoadedOffset) {
     assert(0 && "Invalid SLocOffset or bad function choice");
     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;
+  // in the other direction (decreasing order).
+  // GreaterIndex is the one where the offset is greater, which is actually a
+  // lower index!
+  unsigned GreaterIndex = 0;
+  unsigned LessIndex = LoadedSLocEntryTable.size();
+  if (LastFileIDLookup.ID < 0) {
+    // Prune the search space.
     int LastID = LastFileIDLookup.ID;
-  if (LastID >= 0 || getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset)
-    I = 0;
+    if (getLoadedSLocEntryByID(LastID).getOffset() > SLocOffset)
+      GreaterIndex =
+          (-LastID - 2) + 1; // Exclude LastID, else we would have hit the cache
     else
-    I = (-LastID - 2) + 1;
+      LessIndex = -LastID - 2;
+  }
 
+  // First do a linear scan from the last lookup position, if possible.
   unsigned NumProbes;
   bool Invalid = false;
-  for (NumProbes = 0; NumProbes < 8; ++NumProbes, ++I) {
+  for (NumProbes = 0; NumProbes < 8; ++NumProbes, ++GreaterIndex) {
     // Make sure the entry is loaded!
-    const SrcMgr::SLocEntry &E = getLoadedSLocEntry(I, &Invalid);
+    const SrcMgr::SLocEntry &E = getLoadedSLocEntry(GreaterIndex, &Invalid);
     if (Invalid)
       return FileID(); // invalid entry.
     if (E.getOffset() <= SLocOffset) {
-      FileID Res = FileID::get(-int(I) - 2);
+      FileID Res = FileID::get(-int(GreaterIndex) - 2);
       LastFileIDLookup = 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();
+  // Linear scan failed. Do the binary search.
   NumProbes = 0;
   while (true) {
     ++NumProbes;
     unsigned MiddleIndex = (LessIndex - GreaterIndex) / 2 + GreaterIndex;
     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(MiddleIndex, &Invalid);
     if (Invalid)
       return FileID(); // invalid entry.