Refine SourceManager's isBeforeInTranslationUnit() cache to have more entries.

isBeforeInTranslationUnit() uses a cache to reduce the expensive work
to compute a common ancestor for two FileIDs.  This work is very
expensive, so even caching the latest used FileIDs was a big win.
A closer analysis of the cache before, however, shows that the cache
access pattern would oscillate between a working set of FileIDs, and
thus caching more pairs would be profitable.

This patch adds a side table for extending caching.  This side table
is bounded in size (experimentally determined in this case from
a simple Objective-C project), and when the table gets too large
we fall back to the single entry caching before as before.

On Sketch (a small example Objective-C project), this optimization
reduces -fsyntax-only time on SKTGraphicView.m by 5%.  This is
for a project that is already using PCH.

Fixes <rdar://problem/13299847>

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@176142 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 16 insertions, 4 deletions

diff --git a/include/clang/Basic/SourceManager.h b/include/clang/Basic/SourceManager.h
index d7c71a7632..00c96c3da0 100644
--- a/include/clang/Basic/SourceManager.h
+++ b/include/clang/Basic/SourceManager.h
@@ -447,7 +447,7 @@ public:
 ///
 /// The cache structure is complex enough to be worth breaking out of
 /// SourceManager.
-class IsBeforeInTranslationUnitCache {
+class InBeforeInTUCacheEntry {
   /// \brief The FileID's of the cached query.
   ///
   /// If these match up with a subsequent query, the result can be reused.
@@ -469,7 +469,6 @@ class IsBeforeInTranslationUnitCache {
   /// random token in the parent.
   unsigned LCommonOffset, RCommonOffset;
 public:
-
   /// \brief Return true if the currently cached values match up with
   /// the specified LHS/RHS query.
   ///
@@ -647,8 +646,21 @@ class SourceManager : public RefCountedBase<SourceManager> {
   // Statistics for -print-stats.
   mutable unsigned NumLinearScans, NumBinaryProbes;
 
-  // Cache results for the isBeforeInTranslationUnit method.
-  mutable IsBeforeInTranslationUnitCache IsBeforeInTUCache;
+  /// The key value into the IsBeforeInTUCache table.
+  typedef std::pair<FileID, FileID> IsBeforeInTUCacheKey;
+
+  /// The IsBeforeInTranslationUnitCache is a mapping from FileID pairs
+  /// to cache results.
+  typedef llvm::DenseMap<IsBeforeInTUCacheKey, InBeforeInTUCacheEntry>
+          InBeforeInTUCache;
+
+  /// 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;
 
   // Cache for the "fake" buffer used for error-recovery purposes.
   mutable llvm::MemoryBuffer *FakeBufferForRecovery;