diff --git a/clang/include/clang/Basic/SourceManager.h b/clang/include/clang/Basic/SourceManager.h --- a/clang/include/clang/Basic/SourceManager.h +++ b/clang/include/clang/Basic/SourceManager.h @@ -532,85 +532,6 @@ virtual std::pair 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> IncludedLocMap; - /// The key value into the IsBeforeInTUCache table. - using IsBeforeInTUCacheKey = std::pair; - - /// The IsBeforeInTranslationUnitCache is a mapping from FileID pairs - /// to cache results. - using InBeforeInTUCache = - llvm::DenseMap; + 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; + std::list LRU; + llvm::DenseMap> Lookup; + }; + mutable BeforeInTUCache IsBeforeInTUCache; // Cache for the "fake" buffer used for error-recovery purposes. mutable std::unique_ptr 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 - isInTheSameTranslationUnit(std::pair &LOffs, - std::pair &ROffs) const; + isInTheSameTranslationUnit(std::pair LOffs, + std::pair ROffs) const; /// Determines the order of 2 source locations in the "source location /// address space". diff --git a/clang/lib/Basic/SourceManager.cpp b/clang/lib/Basic/SourceManager.cpp --- a/clang/lib/Basic/SourceManager.cpp +++ b/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 &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 &Loc, const SourceManager &SM) { std::pair 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 SourceManager::isInTheSameTranslationUnit( - std::pair &LOffs, - std::pair &ROffs) const { + std::pair LOffs, + std::pair 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 {