This revision was automatically updated to reflect the committed changes.
Closed by commit rG10c0eca25523: [clang][Lexer] Speed up HeaderSearch when
there are many HeaderMaps (authored by troyj).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D135801/new/
https://reviews.llvm.org/D135801
Files:
clang/include/clang/Lex/HeaderMap.h
clang/include/clang/Lex/HeaderSearch.h
clang/lib/Lex/HeaderSearch.cpp
Index: clang/lib/Lex/HeaderSearch.cpp
===================================================================
--- clang/lib/Lex/HeaderSearch.cpp
+++ clang/lib/Lex/HeaderSearch.cpp
@@ -116,6 +116,7 @@
NoCurDirSearch = noCurDirSearch;
SearchDirToHSEntry = std::move(searchDirToHSEntry);
//LookupFileCache.clear();
+ indexInitialHeaderMaps();
}
void HeaderSearch::AddSearchPath(const DirectoryLookup &dir, bool isAngled) {
@@ -372,6 +373,29 @@
return Module;
}
+void HeaderSearch::indexInitialHeaderMaps() {
+ llvm::StringMap<unsigned, llvm::BumpPtrAllocator> Index(SearchDirs.size());
+
+ // Iterate over all filename keys and associate them with the index i.
+ unsigned i = 0;
+ for (; i != SearchDirs.size(); ++i) {
+ auto &Dir = SearchDirs[i];
+
+ // We're concerned with only the initial contiguous run of header
+ // maps within SearchDirs, which can be 99% of SearchDirs when
+ // SearchDirs.size() is ~10000.
+ if (!Dir.isHeaderMap())
+ break;
+
+ // Give earlier keys precedence over identical later keys.
+ auto Callback = [&](StringRef Filename) { Index.try_emplace(Filename, i); };
+ Dir.getHeaderMap()->forEachKey(Callback);
+ }
+
+ SearchDirHeaderMapIndex = std::move(Index);
+ FirstNonHeaderMapSearchDirIdx = i;
+}
+
//===----------------------------------------------------------------------===//
// File lookup within a DirectoryLookup scope
//===----------------------------------------------------------------------===//
@@ -977,24 +1001,37 @@
ConstSearchDirIterator NextIt = std::next(It);
- // If the entry has been previously looked up, the first value will be
- // non-zero. If the value is equal to i (the start point of our search), then
- // this is a matching hit.
- if (!SkipCache && CacheLookup.StartIt == NextIt) {
- // Skip querying potentially lots of directories for this lookup.
- if (CacheLookup.HitIt)
- It = CacheLookup.HitIt;
- if (CacheLookup.MappedName) {
- Filename = CacheLookup.MappedName;
- if (IsMapped)
- *IsMapped = true;
+ if (!SkipCache) {
+ if (CacheLookup.StartIt == NextIt) {
+ // HIT: Skip querying potentially lots of directories for this lookup.
+ if (CacheLookup.HitIt)
+ It = CacheLookup.HitIt;
+ if (CacheLookup.MappedName) {
+ Filename = CacheLookup.MappedName;
+ if (IsMapped)
+ *IsMapped = true;
+ }
+ } else {
+ // MISS: This is the first query, or the previous query didn't match
+ // our search start. We will fill in our found location below, so prime
+ // the start point value.
+ CacheLookup.reset(/*NewStartIt=*/NextIt);
+
+ if (It == search_dir_begin() && FirstNonHeaderMapSearchDirIdx > 0) {
+ // Handle cold misses of user includes in the presence of many header
+ // maps. We avoid searching perhaps thousands of header maps by
+ // jumping directly to the correct one or jumping beyond all of them.
+ auto Iter = SearchDirHeaderMapIndex.find(Filename);
+ if (Iter == SearchDirHeaderMapIndex.end())
+ // Not in index => Skip to first SearchDir after initial header maps
+ It = search_dir_nth(FirstNonHeaderMapSearchDirIdx);
+ else
+ // In index => Start with a specific header map
+ It = search_dir_nth(Iter->second);
+ }
}
- } else {
- // Otherwise, this is the first query, or the previous query didn't match
- // our search start. We will fill in our found location below, so prime the
- // start point value.
+ } else
CacheLookup.reset(/*NewStartIt=*/NextIt);
- }
SmallString<64> MappedName;
Index: clang/include/clang/Lex/HeaderSearch.h
===================================================================
--- clang/include/clang/Lex/HeaderSearch.h
+++ clang/include/clang/Lex/HeaderSearch.h
@@ -249,6 +249,14 @@
unsigned SystemDirIdx = 0;
bool NoCurDirSearch = false;
+ /// Maps HeaderMap keys to SearchDir indices. When HeaderMaps are used
+ /// heavily, SearchDirs can start with thousands of HeaderMaps, so this Index
+ /// lets us avoid scanning them all to find a match.
+ llvm::StringMap<unsigned, llvm::BumpPtrAllocator> SearchDirHeaderMapIndex;
+
+ /// The index of the first SearchDir that isn't a header map.
+ unsigned FirstNonHeaderMapSearchDirIdx = 0;
+
/// \#include prefixes for which the 'system header' property is
/// overridden.
///
@@ -330,6 +338,10 @@
/// Entity used to look up stored header file information.
ExternalHeaderFileInfoSource *ExternalSource = nullptr;
+ /// Scan all of the header maps at the beginning of SearchDirs and
+ /// map their keys to the SearchDir index of their header map.
+ void indexInitialHeaderMaps();
+
public:
HeaderSearch(std::shared_ptr<HeaderSearchOptions> HSOpts,
SourceManager &SourceMgr, DiagnosticsEngine &Diags,
@@ -801,6 +813,10 @@
}
ConstSearchDirIterator search_dir_begin() const { return quoted_dir_begin(); }
+ ConstSearchDirIterator search_dir_nth(size_t n) const {
+ assert(n < SearchDirs.size());
+ return {*this, n};
+ }
ConstSearchDirIterator search_dir_end() const { return system_dir_end(); }
ConstSearchDirRange search_dir_range() const {
return {search_dir_begin(), search_dir_end()};
Index: clang/include/clang/Lex/HeaderMap.h
===================================================================
--- clang/include/clang/Lex/HeaderMap.h
+++ clang/include/clang/Lex/HeaderMap.h
@@ -15,6 +15,7 @@
#include "clang/Basic/FileManager.h"
#include "clang/Basic/LLVM.h"
+#include "clang/Lex/HeaderMapTypes.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/Support/Compiler.h"
@@ -39,6 +40,21 @@
// Check for a valid header and extract the byte swap.
static bool checkHeader(const llvm::MemoryBuffer &File, bool &NeedsByteSwap);
+ // Make a call for every Key in the map.
+ template <typename Func> void forEachKey(Func Callback) const {
+ const HMapHeader &Hdr = getHeader();
+ unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
+
+ for (unsigned Bucket = 0; Bucket < NumBuckets; ++Bucket) {
+ HMapBucket B = getBucket(Bucket);
+ if (B.Key != HMAP_EmptyBucketKey) {
+ Optional<StringRef> Key = getString(B.Key);
+ if (Key)
+ Callback(Key.value());
+ }
+ }
+ }
+
/// If the specified relative filename is located in this HeaderMap return
/// the filename it is mapped to, otherwise return an empty StringRef.
StringRef lookupFilename(StringRef Filename,
@@ -78,6 +94,7 @@
FileManager &FM);
using HeaderMapImpl::dump;
+ using HeaderMapImpl::forEachKey;
using HeaderMapImpl::getFileName;
using HeaderMapImpl::lookupFilename;
using HeaderMapImpl::reverseLookupFilename;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
