[clang] Optimize SourceManager::getFileIDLocal [WIP]

[melver]

Summary

• Avoid bit operations to compute Offset by removing bitfields. On 64-bit architectures, SLocEntry's size is unchanged!

• Move fast-path assignment of LessIndex up, to avoid potential spill.

• Provide branch-prediction hints to compiler to generate better code.

Tested:

• Default compiler: clang-9

TDB

[melver]

Extra unlikely hint.

[melver]

Improve code-gen further -- another ~5%.

[melver]

More background: https://github.com/ClangBuiltLinux/linux/issues/1032

This approach likely doesn't yield too much benefit. Too much variability is observed when compiling Clang with either Clang or GCC.

Since Nick has a better proposal at the above link, let's abandon this.

clang/include/clang/Basic/SourceManager.h

public:
     }
   };
 
   /// This is a discriminated union of FileInfo and ExpansionInfo.
   ///
   /// SourceManager keeps an array of these objects, and they are uniquely
   /// identified by the FileID datatype.
   class SLocEntry {
-    unsigned Offset : 31;
-    unsigned IsExpansion : 1;
+    unsigned Offset;
+    bool IsExpansion;
     union {
       FileInfo File;
       ExpansionInfo Expansion;
     };
 
   public:
     SLocEntry() : Offset(), IsExpansion(), File() {}
 
     unsigned getOffset() const { return Offset; }
 
     bool isExpansion() const { return IsExpansion; }
     bool isFile() const { return !isExpansion(); }
 
     const FileInfo &getFile() const {
       assert(isFile() && "Not a file SLocEntry!");
       return File;
     }
 
     const ExpansionInfo &getExpansion() const {
       assert(isExpansion() && "Not a macro expansion SLocEntry!");
       return Expansion;
     }
 
     static SLocEntry get(unsigned Offset, const FileInfo &FI) {
-      assert(!(Offset & (1u << 31)) && "Offset is too large");
       SLocEntry E;
       E.Offset = Offset;
       E.IsExpansion = false;
       E.File = FI;
       return E;
     }
 
     static SLocEntry get(unsigned Offset, const ExpansionInfo &Expansion) {
-      assert(!(Offset & (1u << 31)) && "Offset is too large");
       SLocEntry E;
       E.Offset = Offset;
       E.IsExpansion = true;
       E.Expansion = Expansion;
       return E;
     }
   };
 

clang/lib/Basic/SourceManager.cpp

FileID SourceManager::getFileIDLocal(unsigned SLocOffset) const {
   // We know that the offset corresponding to the FileID is is less than
   // SLocOffset.
   unsigned LessIndex = 0;
   NumProbes = 0;
   while (true) {
     bool Invalid = false;
     unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex;
     unsigned MidOffset = getLocalSLocEntry(MiddleIndex, &Invalid).getOffset();
-    if (Invalid)
+    if (LLVM_UNLIKELY(Invalid))
       return FileID::get(0);
 
     ++NumProbes;
 
     // If the offset of the midpoint is too large, chop the high side of the
     // range to the midpoint.
-    if (MidOffset > SLocOffset) {
+    if (LLVM_LIKELY(MidOffset > SLocOffset)) {
       GreaterIndex = MiddleIndex;
       continue;
     }
 
     // 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 (LLVM_UNLIKELY(isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset))) {
       FileID Res = FileID::get(MiddleIndex);
 
       // If this isn't a macro expansion, remember it.  We have good locality
       // across FileID lookups.
       if (!LocalSLocEntryTable[MiddleIndex].isExpansion())
         LastFileIDLookup = Res;
       NumBinaryProbes += NumProbes;
       return Res;