Clean up isBeforeInTranslationUnit cache and add eviction.

[sammccall]

Summary

Previously the first 300 entries would stay around forever, and any new queries
would thrash on entry 301.
The cache code/data structures were more complicated than necessary.

Cleaned up the interface to isInSameTranslationUnit, which had unspecified
side-effects that other code was relying on.

clang/include/clang/Basic/SourceManager.h

public:
   virtual bool ReadSLocEntry(int ID) = 0;
 
   /// Retrieve the module import location and name for the given ID, if
   /// in fact it was loaded from a module (rather than, say, a precompiled
   /// header).
   virtual std::pair<SourceLocation, StringRef> getModuleImportLoc(int ID) = 0;
 };
 
-/// Holds the cache used by isBeforeInTranslationUnit.
-///
-/// The cache structure is complex enough to be worth breaking out of
-/// SourceManager.
-class InBeforeInTUCacheEntry {
-  /// The FileID's of the cached query.
-  ///
-  /// If these match up with a subsequent query, the result can be reused.
-  FileID LQueryFID, RQueryFID;
-
-  /// The relative order of FileIDs that the CommonFID *immediately* includes.
-  ///
-  /// This is used to compare macro expansion locations.
-  bool LChildBeforeRChild;
-
-  /// The file found in common between the two \#include traces, i.e.,
-  /// the nearest common ancestor of the \#include tree.
-  FileID CommonFID;
-
-  /// The offset of the previous query in CommonFID.
-  ///
-  /// Usually, this represents the location of the \#include for QueryFID, but
-  /// if LQueryFID is a parent of RQueryFID (or vice versa) then these can be a
-  /// random token in the parent.
-  unsigned LCommonOffset, RCommonOffset;
-
-public:
-  InBeforeInTUCacheEntry() = default;
-  InBeforeInTUCacheEntry(FileID L, FileID R) : LQueryFID(L), RQueryFID(R) {
-    assert(L != R);
-  }
-
-  /// Return true if the currently cached values match up with
-  /// the specified LHS/RHS query.
-  ///
-  /// If not, we can't use the cache.
-  bool isCacheValid() const {
-    return CommonFID.isValid();
-  }
-
-  /// If the cache is valid, compute the result given the
-  /// specified offsets in the LHS/RHS FileID's.
-  bool getCachedResult(unsigned LOffset, unsigned ROffset) const {
-    // If one of the query files is the common file, use the offset.  Otherwise,
-    // use the #include loc in the common file.
-    if (LQueryFID != CommonFID) LOffset = LCommonOffset;
-    if (RQueryFID != CommonFID) ROffset = RCommonOffset;
-
-    // It is common for multiple macro expansions to be "included" from the same
-    // location (expansion location), in which case use the order of the FileIDs
-    // to determine which came first. This will also take care the case where
-    // one of the locations points at the inclusion/expansion point of the other
-    // in which case its FileID will come before the other.
-    if (LOffset == ROffset)
-      return LChildBeforeRChild;
-
-    return LOffset < ROffset;
-  }
-
-  /// Set up a new query.
-  /// If it matches the old query, we can keep the cached answer.
-  void setQueryFIDs(FileID LHS, FileID RHS) {
-    assert(LHS != RHS);
-    if (LQueryFID != LHS || RQueryFID != RHS) {
-      LQueryFID = LHS;
-      RQueryFID = RHS;
-      CommonFID = FileID();
-    }
-  }
-
-  void setCommonLoc(FileID commonFID, unsigned lCommonOffset,
-                    unsigned rCommonOffset, bool LParentBeforeRParent) {
-    CommonFID = commonFID;
-    LCommonOffset = lCommonOffset;
-    RCommonOffset = rCommonOffset;
-    LChildBeforeRChild = LParentBeforeRParent;
-  }
-};
-
 /// The stack used when building modules on demand, which is used
 /// to provide a link between the source managers of the different compiler
 /// instances.
 using ModuleBuildStack = ArrayRef<std::pair<std::string, FullSourceLoc>>;
 
 /// This class handles loading and caching of source files into memory.
 ///
 /// This object owns the MemoryBuffer objects for all of the loaded
class SourceManager : public RefCountedBase<SourceManager> {
 
   /// Associates a FileID with its "included/expanded in" decomposed
   /// location.
   ///
   /// Used to cache results from and speed-up \c getDecomposedIncludedLoc
   /// function.
   mutable llvm::DenseMap<FileID, std::pair<FileID, unsigned>> IncludedLocMap;
 
-  /// The key value into the IsBeforeInTUCache table.
-  using IsBeforeInTUCacheKey = std::pair<FileID, FileID>;
+  class BeforeInTUCache {
+  public:
+    class Entry;
+    Entry &emplace(FileID L, FileID R);
 
-  /// The IsBeforeInTranslationUnitCache is a mapping from FileID pairs
-  /// to cache results.
-  using InBeforeInTUCache =
-      llvm::DenseMap<IsBeforeInTUCacheKey, InBeforeInTUCacheEntry>;
-
-  /// Cache results for the isBeforeInTranslationUnit method.
-  mutable InBeforeInTUCache IBTUCache;
-  mutable InBeforeInTUCacheEntry IBTUCacheOverflow;
-
-  /// Return the cache entry for comparing the given file IDs
-  /// for isBeforeInTranslationUnit.
-  InBeforeInTUCacheEntry &getInBeforeInTUCache(FileID LFID, FileID RFID) const;
+  private:
+    constexpr static unsigned MaxSize = 500;
+    using Key = std::pair<FileID, FileID>;
+    std::list<Key> LRU;
+    llvm::DenseMap<Key, std::pair<Entry, decltype(LRU)::iterator>> Lookup;
+  };
+  mutable BeforeInTUCache IsBeforeInTUCache;
 
   // Cache for the "fake" buffer used for error-recovery purposes.
   mutable std::unique_ptr<llvm::MemoryBuffer> FakeBufferForRecovery;
 
   mutable std::unique_ptr<SrcMgr::ContentCache> FakeContentCacheForRecovery;
 
   mutable std::unique_ptr<SrcMgr::SLocEntry> FakeSLocEntryForRecovery;
 
public:
   /// Determines whether the two decomposed source location is in the
   ///        same translation unit. As a byproduct, it also calculates the order
   ///        of the source locations in case they are in the same TU.
   ///
   /// \returns Pair of bools the first component is true if the two locations
   ///          are in the same TU. The second bool is true if the first is true
   ///          and \p LOffs is before \p ROffs.
   std::pair<bool, bool>
-  isInTheSameTranslationUnit(std::pair<FileID, unsigned> &LOffs,
-                             std::pair<FileID, unsigned> &ROffs) const;
+  isInTheSameTranslationUnit(std::pair<FileID, unsigned> LOffs,
+                             std::pair<FileID, unsigned> ROffs) const;
 
   /// Determines the order of 2 source locations in the "source location
   /// address space".
   bool isBeforeInSLocAddrSpace(SourceLocation LHS, SourceLocation RHS) const {
     return isBeforeInSLocAddrSpace(LHS, RHS.getOffset());
   }
 
   /// Determines the order of a source location and a source location

clang/lib/Basic/SourceManager.cpp

SourceManager::getDecomposedIncludedLoc(FileID FID) const {
   if (UpperLoc.isValid())
     DecompLoc = getDecomposedLoc(UpperLoc);
 
   return DecompLoc;
 }
 
 /// Given a decomposed source location, move it up the include/expansion stack
 /// to the parent source location.  If this is possible, return the decomposed
-/// version of the parent in Loc and return false.  If Loc is the top-level
-/// entry, return true and don't modify it.
-static bool MoveUpIncludeHierarchy(std::pair<FileID, unsigned> &Loc,
+/// version of the parent in Loc and return true.  If Loc is the top-level
+/// entry, return false and don't modify it.
+static bool moveUpIncludeHierarchy(std::pair<FileID, unsigned> &Loc,
                                    const SourceManager &SM) {
   std::pair<FileID, unsigned> UpperLoc = SM.getDecomposedIncludedLoc(Loc.first);
   if (UpperLoc.first.isInvalid())
-    return true; // We reached the top.
+    return false; // We reached the top.
 
   Loc = UpperLoc;
-  return false;
+  return true;
+}
+
+// An entry in the BeforeInTUCache describes the computed relationship between
+// a pair of FileIDs. This can be used to efficiently compare locations in
+// those FileIDs.
+class SourceManager::BeforeInTUCache::Entry {
+  enum Kind : unsigned {
+    // The relationship between the FileIDs hasn't been computed yet.
+    NotComputed,
+    // The FileIDs are not in the same translation unit.
+    Unrelated,
+    // The common file is distinct from both FileIDs.
+    // Therefore the comparison result is constant and stored in Payload.
+    Distinct,
+    // The common file is the left FileID.
+    // The offset of the right fileID in the common one is stored in Payload.
+    LeftIncludesRight,
+    // The common file is the right FileID.
+    // The offset of the left fileID in the common one is stored in Payload.
+    RightIncludesLeft,
+  };
+  Kind State;
+  unsigned Payload;
+
+public:
+  // Initially we do not know the relationship between the files.
+  Entry() : State(NotComputed) {}
+  bool isComputed() const { return State != NotComputed; }
+
+  bool isRelated() const {
+    assert(isComputed());
+    return State != Unrelated;
+  }
+
+  // Save the computed state: these files are not in the same TU.
+  void fillUnrelated() {
+    assert(!isComputed());
+    State = Unrelated;
+  }
+  // Save the computed relationship between these files.
+  // LeftFile and RightFile are the files this cache entry is for.
+  // Common is their common ancestor.
+  // LeftChild is the immediate child of Common on the way to LeftFile.
+  // LeftOffsetInCommon is the position of LeftChild within Common.
+  void fill(FileID Common, FileID LeftFile, unsigned LeftOffsetInCommon,
+            FileID LeftChild, FileID RightFile, unsigned RightOffsetInCommon,
+            FileID RightChild) {
+    assert(!isComputed());
+    assert(LeftFile != RightFile);
+    if (Common == LeftFile) {
+      State = LeftIncludesRight;
+      Payload = RightOffsetInCommon;
+    } else if (Common == RightFile) {
+      State = RightIncludesLeft;
+      Payload = LeftOffsetInCommon;
+    } else {
+      State = Distinct;
+      if (LeftOffsetInCommon != RightOffsetInCommon)
+        Payload = LeftOffsetInCommon < RightOffsetInCommon;
+      else
+        // The relative order of LParent and RParent is a tiebreaker when
+        // - locs expand to the same location (occurs in macro arg expansion)
+        // - one loc is a parent of the other (the parent is "first")
+        // For the parent to be first, the invalid file ID must compare smaller.
+        // However loaded FileIDs are <0, so we perform *unsigned* comparison!
+        // This changes the relative order of local vs loaded FileIDs, but it
+        // doesn't matter: these are never mixed in macro expansion.
+        Payload = (unsigned)LeftChild.ID < (unsigned)RightChild.ID;
+    }
   }
 
-/// Return the cache entry for comparing the given file IDs
-/// for isBeforeInTranslationUnit.
-InBeforeInTUCacheEntry &SourceManager::getInBeforeInTUCache(FileID LFID,
-                                                            FileID RFID) const {
-  // This is a magic number for limiting the cache size.  It was experimentally
-  // derived from a small Objective-C project (where the cache filled
-  // out to ~250 items).  We can make it larger if necessary.
-  // FIXME: this is almost certainly full these days. Use an LRU cache?
-  enum { MagicCacheSize = 300 };
-  IsBeforeInTUCacheKey Key(LFID, RFID);
-
-  // If the cache size isn't too large, do a lookup and if necessary default
-  // construct an entry.  We can then return it to the caller for direct
-  // use.  When they update the value, the cache will get automatically
-  // updated as well.
-  if (IBTUCache.size() < MagicCacheSize)
-    return IBTUCache.try_emplace(Key, LFID, RFID).first->second;
-
-  // Otherwise, do a lookup that will not construct a new value.
-  InBeforeInTUCache::iterator I = IBTUCache.find(Key);
-  if (I != IBTUCache.end())
-    return I->second;
-
-  // Fall back to the overflow value.
-  IBTUCacheOverflow.setQueryFIDs(LFID, RFID);
-  return IBTUCacheOverflow;
+  // Compare locations in the two files.
+  // LOffset is an offset into the left file.
+  bool isBefore(unsigned LOffset, unsigned ROffset) const {
+    assert(isComputed() && isRelated());
+    if (State == Distinct)
+      return Payload;
+    // In case of equality, we want the parent to be considered first.
+    if (State == LeftIncludesRight)
+      return LOffset <= Payload;
+    assert(State == RightIncludesLeft);
+    return Payload < ROffset;
+  }
+};
+
+// Look up the cache entry for a pair of files, creating it if it doesn't exist.
+// The returned entry may or may not have been computed.
+SourceManager::BeforeInTUCache::Entry &
+SourceManager::BeforeInTUCache::emplace(FileID L, FileID R) {
+  Key K{L, R};
+  auto E = Lookup.try_emplace(K);
+  auto &Iterator = E.first->second.second;
+  if (E.second) {
+    // This is a new entry.
+    LRU.push_front(K);
+    Iterator = LRU.begin();
+    // We grew the cache, evict if needed.
+    if (Lookup.size() > MaxSize) {
+      Lookup.erase(LRU.back());
+      LRU.pop_back();
+    }
+  } else {
+    // We looked up an existing entry, move it to the front of LRU.
+    if (Iterator != LRU.begin())
+      LRU.splice(LRU.begin(), LRU, Iterator, std::next(Iterator));
+  }
+  return E.first->second.first;
 }
 
 /// Determines the order of 2 source locations in the translation unit.
 ///
 /// \returns true if LHS source location comes before RHS, false otherwise.
 bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS,
                                               SourceLocation RHS) const {
   assert(LHS.isValid() && RHS.isValid() && "Passed invalid source location!");
if (LOffs.first.isInvalid() || ROffs.first.isInvalid())
     return LOffs.first.isInvalid() && !ROffs.first.isInvalid();
 
   std::pair<bool, bool> InSameTU = isInTheSameTranslationUnit(LOffs, ROffs);
   if (InSameTU.first)
     return InSameTU.second;
 
   // If we arrived here, the location is either in a built-ins buffer or
   // associated with global inline asm. PR5662 and PR22576 are examples.
+  while (moveUpIncludeHierarchy(LOffs, *this)) {
+  }
+  while (moveUpIncludeHierarchy(ROffs, *this)) {
+  }
 
   StringRef LB = getBufferOrFake(LOffs.first).getBufferIdentifier();
   StringRef RB = getBufferOrFake(ROffs.first).getBufferIdentifier();
   bool LIsBuiltins = LB == "<built-in>";
   bool RIsBuiltins = RB == "<built-in>";
   // Sort built-in before non-built-in.
   if (LIsBuiltins || RIsBuiltins) {
     if (LIsBuiltins != RIsBuiltins)
if (LIsScratch || RIsScratch) {
     if (LIsScratch != RIsScratch)
       return LIsScratch;
     return LOffs.second < ROffs.second;
   }
   llvm_unreachable("Unsortable locations found");
 }
 
 std::pair<bool, bool> SourceManager::isInTheSameTranslationUnit(
-    std::pair<FileID, unsigned> &LOffs,
-    std::pair<FileID, unsigned> &ROffs) const {
+    std::pair<FileID, unsigned> LOffs,
+    std::pair<FileID, unsigned> ROffs) const {
   // If the source locations are in the same file, just compare offsets.
   if (LOffs.first == ROffs.first)
-    return std::make_pair(true, LOffs.second < ROffs.second);
+    return {true, LOffs.second < ROffs.second};
 
-  // If we are comparing a source location with multiple locations in the same
-  // file, we get a big win by caching the result.
-  InBeforeInTUCacheEntry &IsBeforeInTUCache =
-    getInBeforeInTUCache(LOffs.first, ROffs.first);
-
-  // If we are comparing a source location with multiple locations in the same
-  // file, we get a big win by caching the result.
-  if (IsBeforeInTUCache.isCacheValid())
-    return std::make_pair(
-        true, IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second));
+  FileID LeftFile = LOffs.first, RightFile = ROffs.first;
+  auto &Cache = IsBeforeInTUCache.emplace(LeftFile, RightFile);
+  if (Cache.isComputed()) {
+    if (!Cache.isRelated())
+      return {false, false};
+    return {true, Cache.isBefore(LOffs.second, ROffs.second)};
+  }
 
   // Okay, we missed in the cache, we'll compute the answer and populate it.
   // We need to find the common ancestor. The only way of doing this is to
   // build the complete include chain for one and then walking up the chain
   // of the other looking for a match.
 
   // A location within a FileID on the path up from LOffs to the main file.
   struct Entry {
     unsigned Offset;
     FileID ParentFID; // Used for breaking ties.
   };
   llvm::SmallDenseMap<FileID, Entry, 16> LChain;
 
   FileID Parent;
   do {
     LChain.try_emplace(LOffs.first, Entry{LOffs.second, Parent});
     // We catch the case where LOffs is in a file included by ROffs and
     // quit early. The other way round unfortunately remains suboptimal.
     if (LOffs.first == ROffs.first)
       break;
     Parent = LOffs.first;
-  } while (!MoveUpIncludeHierarchy(LOffs, *this));
+  } while (moveUpIncludeHierarchy(LOffs, *this));
 
   Parent = FileID();
   do {
     auto I = LChain.find(ROffs.first);
     if (I != LChain.end()) {
       // Compare the locations within the common file and cache them.
-      LOffs.first = I->first;
-      LOffs.second = I->second.Offset;
-      // The relative order of LParent and RParent is a tiebreaker when
-      // - locs expand to the same location (occurs in macro arg expansion)
-      // - one loc is a parent of the other (we consider the parent as "first")
-      // For the parent to be first, the invalid file ID must compare smaller.
-      // However loaded FileIDs are <0, so we perform *unsigned* comparison!
-      // This changes the relative order of local vs loaded FileIDs, but it
-      // doesn't matter as these are never mixed in macro expansion.
-      unsigned LParent = I->second.ParentFID.ID;
-      unsigned RParent = Parent.ID;
-      IsBeforeInTUCache.setCommonLoc(LOffs.first, LOffs.second, ROffs.second,
-                                     LParent < RParent);
-      return std::make_pair(
-          true, IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second));
+      Cache.fill(I->first, LeftFile, I->second.Offset,
+                 /*LeftChild=*/I->second.ParentFID, RightFile, ROffs.second,
+                 /*RightChild=*/Parent);
+      return {true, Cache.isBefore(I->second.Offset, ROffs.second)};
     }
     Parent = ROffs.first;
-  } while (!MoveUpIncludeHierarchy(ROffs, *this));
+  } while (moveUpIncludeHierarchy(ROffs, *this));
 
   // If we found no match, we're not in the same TU.
-  // We don't cache this, but it is rare.
-  return std::make_pair(false, false);
+  Cache.fillUnrelated();
+  return {false, false};
 }
 
 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)