sammccall created this revision.
Herald added a project: All.
sammccall requested review of this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
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.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D134694
Files:
clang/include/clang/Basic/SourceManager.h
clang/lib/Basic/SourceManager.cpp
Index: clang/lib/Basic/SourceManager.cpp
===================================================================
--- clang/lib/Basic/SourceManager.cpp
+++ clang/lib/Basic/SourceManager.cpp
@@ -1973,44 +1973,123 @@
/// 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;
}
-/// 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);
+// 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;
- // 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;
+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;
+ }
- // Otherwise, do a lookup that will not construct a new value.
- InBeforeInTUCache::iterator I = IBTUCache.find(Key);
- if (I != IBTUCache.end())
- return I->second;
+ // 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;
+ }
+ }
- // 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.
@@ -2037,6 +2116,10 @@
// 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();
@@ -2071,22 +2154,19 @@
}
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);
-
- // 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));
+ return {true, 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
@@ -2108,35 +2188,24 @@
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 {
Index: clang/include/clang/Basic/SourceManager.h
===================================================================
--- clang/include/clang/Basic/SourceManager.h
+++ clang/include/clang/Basic/SourceManager.h
@@ -532,85 +532,6 @@
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.
@@ -754,21 +675,18 @@
/// function.
mutable llvm::DenseMap<FileID, std::pair<FileID, unsigned>> IncludedLocMap;
- /// The key value into the IsBeforeInTUCache table.
- using IsBeforeInTUCacheKey = std::pair<FileID, FileID>;
-
- /// The IsBeforeInTranslationUnitCache is a mapping from FileID pairs
- /// to cache results.
- using InBeforeInTUCache =
- llvm::DenseMap<IsBeforeInTUCacheKey, InBeforeInTUCacheEntry>;
+ class BeforeInTUCache {
+ public:
+ class Entry;
+ Entry &emplace(FileID L, FileID R);
- /// 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;
@@ -1646,8 +1564,8 @@
/// 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".
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
