Speed up preamble building by replacing the slow translateFile call by a new, faster isMainFile check

[arphaman]

Summary

[clang][Preprocessor] Replace the slow translateFile call by a new, faster isMainFile check

The commit 3c28a2dc6bdc331e5a0d8097a5fa59d06682b9d0 introduced the check that checks if we're
trying to re-enter a main file when building a preamble. Unfortunately this slowed down the preamble
compilation by 80-90% in some test cases, as translateFile is really slow. This change checks
to see if the FileEntry is the main file without calling translateFile, but by using the new
isMainFile check instead. This speeds up preamble building by 1.5-2x for certain test cases that we have.

rdar://59361291

[arphaman]

fix assertion in the unit test.

[jkorous]

IIUC the issue is that SourceManager::translateFile() basically consists of two blocks of code:

// First, check the main file ID, since it is common to look for a
// location in the main file.
if (MainFileID.isValid()) {
  bool Invalid = false;
  const SLocEntry &MainSLoc = getSLocEntry(MainFileID, &Invalid);
  if (Invalid)
    return FileID();

  if (MainSLoc.isFile()) {
    const ContentCache *MainContentCache =
        MainSLoc.getFile().getContentCache();
    if (MainContentCache && MainContentCache->OrigEntry == SourceFile)
      return MainFileID;
  }
}

and

  // The location we're looking for isn't in the main file; look
  // through all of the local source locations.
...

The comments suggest that the first block is a heuristic related to our case and the second block I would assume being the expensive part. SourceManager::getFileEntryRefForID implementation seems similar to the first block.

It makes sense to me to avoid the expensive search. I'm just wondering - how much speedup do we get with caching the value?

[arphaman]

In D79834#2034666, @jkorous wrote:

IIUC the issue is that SourceManager::translateFile() basically consists of two blocks of code:

// First, check the main file ID, since it is common to look for a
// location in the main file.
if (MainFileID.isValid()) {
  bool Invalid = false;
  const SLocEntry &MainSLoc = getSLocEntry(MainFileID, &Invalid);
  if (Invalid)
    return FileID();

  if (MainSLoc.isFile()) {
    const ContentCache *MainContentCache =
        MainSLoc.getFile().getContentCache();
    if (MainContentCache && MainContentCache->OrigEntry == SourceFile)
      return MainFileID;
  }
}

and

  // The location we're looking for isn't in the main file; look
  // through all of the local source locations.
...

The comments suggest that the first block is a heuristic related to our case and the second block I would assume being the expensive part. SourceManager::getFileEntryRefForID implementation seems similar to the first block.

It makes sense to me to avoid the expensive search. I'm just wondering - how much speedup do we get with caching the value?

Good question, let me check if caching can be avoided.

[arphaman]

Drop caching, it's not need for the speedup.

[arphaman]

@jkorous it looks like dropping caching works too, this achieves similar perf results.

[jkorous]

Could you please add a test for this method to clang/unittests/Basic/SourceManagerTest.cpp?

clang/include/clang/Basic/SourceManager.h

817

Please mention the assertion this method makes about the state of the instance it's called on.

clang/lib/Basic/SourceManager.cpp

398

I don't really understand all the details here but shouldn't we use this comparison?

bool operator==(const FileEntryRef &LHS, const FileEntryRef &RHS)

[arphaman]

Added test and a comment.

[arphaman]

clang/lib/Basic/SourceManager.cpp

398

The == comparison can return false for symlinks due to the different name, but we want to return true for symlinks to the main file as well.

[jkorous]

LGTM! Thanks Alex!

[dexonsmith]

clang/lib/Basic/SourceManager.cpp

398

I suggest adding a comment to the code explaining this when you land it, something like:

// Compare UIDs directly so that symlinks compare equal.

clang/include/clang/Basic/SourceManager.h

 /// the line is 17, or any other line.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_BASIC_SOURCEMANAGER_H
 #define LLVM_CLANG_BASIC_SOURCEMANAGER_H
 
 #include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <cassert>
 #include <cstddef>
 #include <map>
 #include <memory>
 #include <string>
 #include <utility>
 #include <vector>
 
 namespace clang {
 
 class ASTReader;
 class ASTWriter;
-class FileManager;
-class FileEntry;
-class FileEntryRef;
 class LineTableInfo;
 class SourceManager;
 
 /// Public enums and private classes that are part of the
 /// SourceManager implementation.
 namespace SrcMgr {
 
   /// Indicates whether a file or directory holds normal user code,
class SourceManager : public RefCountedBase<SourceManager> {
   mutable FileID LastLineNoFileIDQuery;
   mutable SrcMgr::ContentCache *LastLineNoContentCache;
   mutable unsigned LastLineNoFilePos;
   mutable unsigned LastLineNoResult;
 
   /// The file ID for the main source file of the translation unit.
   FileID MainFileID;
 
+  /// The file entry for the main source file.
+  Optional<FileEntryRef> CachedMainFileEntry;
+
   /// The file ID for the precompiled preamble there is one.
   FileID PreambleFileID;
 
   // Statistics for -print-stats.
   mutable unsigned NumLinearScans = 0;
   mutable unsigned NumBinaryProbes = 0;
 
   /// Associates a FileID with its "included/expanded in" decomposed
public:
   /// Returns the FileID of the main source file.
   FileID getMainFileID() const { return MainFileID; }
 
   /// Set the file ID for the main source file.
   void setMainFileID(FileID FID) {
     MainFileID = FID;
   }
 
+  /// Returns true when the given FileEntry corresponds to the main file.
+  bool isMainFile(FileEntryRef SourceFile);
+
   /// Set the file ID for the precompiled preamble.
   void setPreambleFileID(FileID Preamble) {
     assert(PreambleFileID.isInvalid() && "PreambleFileID already set!");
     PreambleFileID = Preamble;
   }
 
   /// Get the file ID for the precompiled preamble if there is one.
   FileID getPreambleFileID() const { return PreambleFileID; }

clang/lib/Basic/SourceManager.cpp

if (I->second) {
       I->second->~ContentCache();
       ContentCacheAlloc.Deallocate(I->second);
     }
   }
 }
 
 void SourceManager::clearIDTables() {
   MainFileID = FileID();
+  CachedMainFileEntry = None;
   LocalSLocEntryTable.clear();
   LoadedSLocEntryTable.clear();
   SLocEntryLoaded.clear();
   LastLineNoFileIDQuery = FileID();
   LastLineNoContentCache = nullptr;
   LastFileIDLookup = FileID();
 
   if (LineTable)
     LineTable->clear();
 
   // Use up FileID #0 as an invalid expansion.
   NextLocalOffset = 0;
   CurrentLoadedOffset = MaxLoadedOffset;
   createExpansionLoc(SourceLocation(), SourceLocation(), SourceLocation(), 1);
 }
 
+bool SourceManager::isMainFile(FileEntryRef SourceFile) {
+  assert(MainFileID.isValid() && "expected initialized SourceManager");
+  if (!CachedMainFileEntry) {
+    CachedMainFileEntry = getFileEntryRefForID(MainFileID);
+    assert(CachedMainFileEntry && "missing file entry for main file");
+  }
+  return CachedMainFileEntry->getUID() == SourceFile.getUID();
+}
+
 void SourceManager::initializeForReplay(const SourceManager &Old) {
   assert(MainFileID.isInvalid() && "expected uninitialized SourceManager");
 
   auto CloneContentCache = [&](const ContentCache *Cache) -> ContentCache * {
     auto *Clone = new (ContentCacheAlloc.Allocate<ContentCache>()) ContentCache;
     Clone->OrigEntry = Cache->OrigEntry;
     Clone->ContentsEntry = Cache->ContentsEntry;
     Clone->BufferOverridden = Cache->BufferOverridden;

clang/lib/Lex/PPDirectives.cpp

#endif
   }
 
   // Check for circular inclusion of the main file.
   // We can't generate a consistent preamble with regard to the conditional
   // stack if the main file is included again as due to the preamble bounds
   // some directives (e.g. #endif of a header guard) will never be seen.
   // Since this will lead to confusing errors, avoid the inclusion.
   if (Action == Enter && File && PreambleConditionalStack.isRecording() &&
-      SourceMgr.translateFile(&File->getFileEntry()) ==
-          SourceMgr.getMainFileID()) {
+      SourceMgr.isMainFile(*File)) {
     Diag(FilenameTok.getLocation(),
          diag::err_pp_including_mainfile_in_preamble);
     return {ImportAction::None};
   }
 
   if (Callbacks && !IsImportDecl) {
     // Notify the callback object that we've seen an inclusion directive.
     // FIXME: Use a different callback for a pp-import?