djasper created this revision.
djasper added a reviewer: rsmith.
djasper added a subscriber: cfe-commits.
Specifically:
- Separate one-entry cache for loaded and local files
- Use bound that can be deduced from that cache for LessIndex
- Address FIXME to use a faster alternative to isOffsetInFileID()
No functional changes intended.
https://reviews.llvm.org/D28218
Files:
include/clang/Basic/SourceManager.h
lib/Basic/SourceManager.cpp
Index: lib/Basic/SourceManager.cpp
===
--- lib/Basic/SourceManager.cpp
+++ lib/Basic/SourceManager.cpp
@@ -396,6 +396,7 @@
LastLineNoFileIDQuery = FileID();
LastLineNoContentCache = nullptr;
LastFileIDLookup = FileID();
+ LastLoadedFileIDLookup = FileID();
if (LineTable)
LineTable->clear();
@@ -580,8 +581,8 @@
// Set LastFileIDLookup to the newly created file. The next getFileID call is
// almost guaranteed to be from that file.
- FileID FID = FileID::get(LocalSLocEntryTable.size()-1);
- return LastFileIDLookup = FID;
+ LastFileIDLookup = FileID::get(LocalSLocEntryTable.size()-1);
+ return LastFileIDLookup;
}
SourceLocation
@@ -736,10 +737,16 @@
// most newly created FileID.
const SrcMgr::SLocEntry *I;
- if (LastFileIDLookup.ID < 0 ||
- LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) {
-// Neither loc prunes our search.
+ int LastID = LastFileIDLookup.ID;
+ // LessIndex - This is the lower bound of the range that we're searching.
+ // We know that the offset corresponding to the FileID is less than
+ // SLocOffset.
+ unsigned LessIndex = 0;
+ if (LastID < 0) {
+I = LocalSLocEntryTable.end();
+ } else if (LocalSLocEntryTable[LastID].getOffset() < SLocOffset) {
I = LocalSLocEntryTable.end();
+LessIndex = LastID;
} else {
// Perhaps it is near the file point.
I = LocalSLocEntryTable.begin()+LastFileIDLookup.ID;
@@ -767,18 +774,14 @@
// Convert "I" back into an index. We know that it is an entry whose index is
// larger than the offset we are looking for.
unsigned GreaterIndex = I - LocalSLocEntryTable.begin();
- // LessIndex - This is the lower bound of the range that we're searching.
- // We know that the offset corresponding to the FileID is is less than
- // SLocOffset.
- unsigned LessIndex = 0;
NumProbes = 0;
while (1) {
bool Invalid = false;
unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex;
unsigned MidOffset = getLocalSLocEntry(MiddleIndex, ).getOffset();
if (Invalid)
return FileID::get(0);
-
+
++NumProbes;
// If the offset of the midpoint is too large, chop the high side of the
@@ -789,9 +792,7 @@
}
// If the middle index contains the value, succeed and return.
-// FIXME: This could be made faster by using a function that's aware of
-// being in the local area.
-if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) {
+if (SLocOffset < LocalSLocEntryTable[MiddleIndex + 1].getOffset()) {
FileID Res = FileID::get(MiddleIndex);
// If this isn't a macro expansion, remember it. We have good locality
@@ -823,11 +824,16 @@
// First do a linear scan from the last lookup position, if possible.
unsigned I;
- int LastID = LastFileIDLookup.ID;
- if (LastID >= 0 || getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset)
+ int LastID = LastLoadedFileIDLookup.ID;
+ unsigned LessIndex = LoadedSLocEntryTable.size();
+ if (LastID >= 0) {
I = 0;
- else
+ } else if (getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset) {
+I = 0;
+LessIndex = (-LastID - 2);
+ } else {
I = (-LastID - 2) + 1;
+ }
unsigned NumProbes;
for (NumProbes = 0; NumProbes < 8; ++NumProbes, ++I) {
@@ -837,7 +843,7 @@
FileID Res = FileID::get(-int(I) - 2);
if (!E.isExpansion())
-LastFileIDLookup = Res;
+LastLoadedFileIDLookup = Res;
NumLinearScans += NumProbes + 1;
return Res;
}
@@ -847,7 +853,6 @@
// table: GreaterIndex is the one where the offset is greater, which is
// actually a lower index!
unsigned GreaterIndex = I;
- unsigned LessIndex = LoadedSLocEntryTable.size();
NumProbes = 0;
while (1) {
++NumProbes;
@@ -868,10 +873,10 @@
continue;
}
-if (isOffsetInFileID(FileID::get(-int(MiddleIndex) - 2), SLocOffset)) {
+if (getLoadedSLocEntry(MiddleIndex - 1).getOffset() > SLocOffset) {
FileID Res = FileID::get(-int(MiddleIndex) - 2);
if (!E.isExpansion())
-LastFileIDLookup = Res;
+LastLoadedFileIDLookup = Res;
NumBinaryProbes += NumProbes;
return Res;
}
Index: include/clang/Basic/SourceManager.h
===
--- include/clang/Basic/SourceManager.h
+++ include/clang/Basic/SourceManager.h
@@ -648,6 +648,9 @@
/// is very common to look up many tokens from the same file.
mutable
