[Lex] Keep track of skipped preprocessor blocks and advance the lexer directly if they are revisited

[akyrtzi]

Summary

This speeds up preprocessing, specifically for preprocessing the clang sources time is reduced by about -36%,
using measurements on M1Pro with a release+thinLTO build.

[benlangmuir]

clang/lib/Lex/PPDirectives.cpp

530

Storing this pointer is only safe as long as SkipExcludedConditionalBlock can never be called recursively, since any modification to the DenseMap can invalidate this pointer. Is there some cheap way to assert that? If not, maybe we should do the lookup again in endLexPass, which would always be correct.

[akyrtzi]

clang/lib/Lex/PPDirectives.cpp

530

Good point! I can add a bool to assert that SkipExcludedConditionalBlock is not recursively called.

[akyrtzi]

Assert that SkipExcludedConditionalBlock() is not recursively called.

[akyrtzi]

clang/lib/Lex/PPDirectives.cpp

530

Done 👍

[benlangmuir]

Couple more minor things, but basically LGTM.

clang/include/clang/Lex/Preprocessor.h

2610

Would be good to mention *why* this is unsafe so we don't remove it by accident (or so we *can* remove it later if we ever change the code so it doesn't matter anymore).

Oh, and style nit: we should move these new fields to the top of the class where all the other fields are.

[akyrtzi]

Add more comments about the use of SkippingExcludedConditionalBlock and move the new Preprocessor fields towards the top of the class.

[tschuett]

Do you believe an entry in the ReleaseNotes would get this achievement more visibility?

[tambre]

In D127379#3581009, @tschuett wrote:

Do you believe an entry in the ReleaseNotes would get this achievement more visibility?

I second that this would be worthy of a release note. Seems like quite a big improvement.

I wonder how much is the total speedup for a full LLVM build or such?

clang/include/clang/Lex/Preprocessor.h

struct MacroInfoChain {
     MacroInfo MI;
     MacroInfoChain *Next;
   };
 
   /// MacroInfos are managed as a chain for easy disposal.  This is the head
   /// of that list.
   MacroInfoChain *MIChainHead = nullptr;
 
+  /// True if \p Preprocessor::SkipExcludedConditionalBlock() is running.
+  /// This is used to guard against calling this function recursively.
+  ///
+  /// See comments at the use-site for more context about why it is needed.
+  bool SkippingExcludedConditionalBlock = false;
+
+  /// Keeps track of skipped range mappings that were recorded while skipping
+  /// excluded conditional directives. It maps the source buffer pointer at
+  /// the beginning of a skipped block, to the number of bytes that should be
+  /// skipped.
+  llvm::DenseMap<const char *, unsigned> RecordedSkippedRanges;
+
   void updateOutOfDateIdentifier(IdentifierInfo &II) const;
 
 public:
   Preprocessor(std::shared_ptr<PreprocessorOptions> PPOpts,
                DiagnosticsEngine &diags, LangOptions &opts, SourceManager &SM,
                HeaderSearch &Headers, ModuleLoader &TheModuleLoader,
                IdentifierInfoLookup *IILookup = nullptr,
                bool OwnsHeaderSearch = false,

 
 private:
   void emitMacroDeprecationWarning(const Token &Identifier) const;
   void emitRestrictExpansionWarning(const Token &Identifier) const;
   void emitFinalMacroWarning(const Token &Identifier, bool IsUndef) const;
 };
 
 /// Abstract base class that describes a handler that will receive
 /// source ranges for each of the comments encountered in the source file.
 class CommentHandler {
 public:
   virtual ~CommentHandler();
 
   // The handler shall return true if it has pushed any tokens
   // to be read using e.g. EnterToken or EnterTokenStream.
   virtual bool HandleComment(Preprocessor &PP, SourceRange Comment) = 0;
 };

clang/lib/Lex/PPDirectives.cpp

 #include "clang/Lex/ModuleMap.h"
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Lex/Pragma.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Lex/PreprocessorOptions.h"
 #include "clang/Lex/Token.h"
 #include "clang/Lex/VariadicMacroSupport.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/StringSwitch.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/AlignOf.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/SaveAndRestore.h"
 #include <algorithm>
 #include <cassert>
 #include <cstring>
 #include <new>
 #include <string>
 #include <utility>
 
 using namespace clang;

 /// If ElseOk is true, then \#else directives are ok, if not, then we have
 /// already seen one so a \#else directive is a duplicate.  When this returns,
 /// the caller can lex the first valid token.
 void Preprocessor::SkipExcludedConditionalBlock(SourceLocation HashTokenLoc,
                                                 SourceLocation IfTokenLoc,
                                                 bool FoundNonSkipPortion,
                                                 bool FoundElse,
                                                 SourceLocation ElseLoc) {
+  // In SkippingRangeStateTy we are depending on SkipExcludedConditionalBlock()
+  // not getting called recursively by storing the RecordedSkippedRanges
+  // DenseMap lookup pointer (field SkipRangePtr). SkippingRangeStateTy expects
+  // that RecordedSkippedRanges won't get modified and SkipRangePtr won't be
+  // invalidated. If this changes and there is a need to call
+  // SkipExcludedConditionalBlock() recursively, SkippingRangeStateTy should
+  // change to do a second lookup in endLexPass function instead of reusing the
+  // lookup pointer.
+  assert(!SkippingExcludedConditionalBlock &&
+         "calling SkipExcludedConditionalBlock recursively");
+  llvm::SaveAndRestore<bool> SARSkipping(SkippingExcludedConditionalBlock,
+                                         true);
+
   ++NumSkipped;
   assert(!CurTokenLexer && CurPPLexer && "Lexing a macro, not a file?");
 
   if (PreambleConditionalStack.reachedEOFWhileSkipping())
     PreambleConditionalStack.clearSkipInfo();
   else
     CurPPLexer->pushConditionalLevel(IfTokenLoc, /*isSkipping*/ false,
                                      FoundNonSkipPortion, FoundElse);
 
   // Enter raw mode to disable identifier lookup (and thus macro expansion),
   // disabling warnings, etc.
   CurPPLexer->LexingRawMode = true;
   Token Tok;
   SourceLocation endLoc;
+
+  /// Keeps track and caches skipped ranges and also retrieves a prior skipped
+  /// range if the same block is re-visited.
+  struct SkippingRangeStateTy {
+    Preprocessor &PP;
+
+    const char *BeginPtr = nullptr;
+    unsigned *SkipRangePtr = nullptr;
+
+    SkippingRangeStateTy(Preprocessor &PP) : PP(PP) {}
+
+    void beginLexPass() {
+      if (BeginPtr)
+        return; // continue skipping a block.
+
+      // Initiate a skipping block and adjust the lexer if we already skipped it
+      // before.
+      BeginPtr = PP.CurLexer->getBufferLocation();
+      SkipRangePtr = &PP.RecordedSkippedRanges[BeginPtr];
+      if (*SkipRangePtr) {
+        PP.CurLexer->seek(PP.CurLexer->getCurrentBufferOffset() + *SkipRangePtr,
+                          /*IsAtStartOfLine*/ true);
+      }
+    }
+
+    void endLexPass(const char *Hashptr) {
+      if (!BeginPtr) {
+        // Not doing normal lexing.
+        assert(PP.CurLexer->isDependencyDirectivesLexer());
+        return;
+      }
+
+      // Finished skipping a block, record the range if it's first time visited.
+      if (!*SkipRangePtr) {
+        *SkipRangePtr = Hashptr - BeginPtr;
+      }
+      assert(*SkipRangePtr == Hashptr - BeginPtr);
+      BeginPtr = nullptr;
+      SkipRangePtr = nullptr;
+    }
+  } SkippingRangeState(*this);
+
   while (true) {
     if (CurLexer->isDependencyDirectivesLexer()) {
       CurLexer->LexDependencyDirectiveTokenWhileSkipping(Tok);
     } else {
+      SkippingRangeState.beginLexPass();
       while (true) {
         CurLexer->Lex(Tok);
 
         if (Tok.is(tok::code_completion)) {
           setCodeCompletionReached();
           if (CodeComplete)
             CodeComplete->CodeCompleteInConditionalExclusion();
           continue;
if (Tok.is(tok::eof))
       break;
 
     // We just parsed a # character at the start of a line, so we're in
     // directive mode.  Tell the lexer this so any newlines we see will be
     // converted into an EOD token (this terminates the macro).
     CurPPLexer->ParsingPreprocessorDirective = true;
     if (CurLexer) CurLexer->SetKeepWhitespaceMode(false);
 
+    assert(Tok.is(tok::hash));
+    const char *Hashptr = CurLexer->getBufferLocation() - Tok.getLength();
+    assert(CurLexer->getSourceLocation(Hashptr) == Tok.getLocation());
 
     // Read the next token, the directive flavor.
     LexUnexpandedToken(Tok);
 
     // If this isn't an identifier directive (e.g. is "# 1\n" or "#\n", or
     // something bogus), skip it.
     if (Tok.isNot(tok::raw_identifier)) {
       CurPPLexer->ParsingPreprocessorDirective = false;
if (Directive.startswith("if")) {
         PPConditionalInfo CondInfo;
         CondInfo.WasSkipping = true; // Silence bogus warning.
         bool InCond = CurPPLexer->popConditionalLevel(CondInfo);
         (void)InCond;  // Silence warning in no-asserts mode.
         assert(!InCond && "Can't be skipping if not in a conditional!");
 
         // If we popped the outermost skipping block, we're done skipping!
         if (!CondInfo.WasSkipping) {
+          SkippingRangeState.endLexPass(Hashptr);
           // Restore the value of LexingRawMode so that trailing comments
           // are handled correctly, if we've reached the outermost block.
           CurPPLexer->LexingRawMode = false;
           endLoc = CheckEndOfDirective("endif");
           CurPPLexer->LexingRawMode = true;
           if (Callbacks)
             Callbacks->Endif(Tok.getLocation(), CondInfo.IfLoc);
           break;
         } else {
           DiscardUntilEndOfDirective();
         }
       } else if (Sub == "lse") { // "else".
         // #else directive in a skipping conditional.  If not in some other
         // skipping conditional, and if #else hasn't already been seen, enter it
         // as a non-skipping conditional.
         PPConditionalInfo &CondInfo = CurPPLexer->peekConditionalLevel();
 
+        if (!CondInfo.WasSkipping)
+          SkippingRangeState.endLexPass(Hashptr);
+
         // If this is a #else with a #else before it, report the error.
         if (CondInfo.FoundElse)
           Diag(Tok, diag::pp_err_else_after_else);
 
         // Note that we've seen a #else in this conditional.
         CondInfo.FoundElse = true;
 
         // If the conditional is at the top level, and the #if block wasn't
if (Directive.startswith("if")) {
             Callbacks->Else(Tok.getLocation(), CondInfo.IfLoc);
           break;
         } else {
           DiscardUntilEndOfDirective();  // C99 6.10p4.
         }
       } else if (Sub == "lif") {  // "elif".
         PPConditionalInfo &CondInfo = CurPPLexer->peekConditionalLevel();
 
+        if (!CondInfo.WasSkipping)
+          SkippingRangeState.endLexPass(Hashptr);
+
         // If this is a #elif with a #else before it, report the error.
         if (CondInfo.FoundElse)
           Diag(Tok, diag::pp_err_elif_after_else) << PED_Elif;
 
         // If this is in a skipping block or if we're already handled this #if
         // block, don't bother parsing the condition.
         if (CondInfo.WasSkipping || CondInfo.FoundNonSkip) {
           // FIXME: We should probably do at least some minimal parsing of the
if (Directive.startswith("if")) {
           }
         }
       } else if (Sub == "lifdef" ||  // "elifdef"
                  Sub == "lifndef") { // "elifndef"
         bool IsElifDef = Sub == "lifdef";
         PPConditionalInfo &CondInfo = CurPPLexer->peekConditionalLevel();
         Token DirectiveToken = Tok;
 
+        if (!CondInfo.WasSkipping)
+          SkippingRangeState.endLexPass(Hashptr);
+
         // Warn if using `#elifdef` & `#elifndef` in not C2x & C++2b mode even
         // if this branch is in a skipping block.
         unsigned DiagID;
         if (LangOpts.CPlusPlus)
           DiagID = LangOpts.CPlusPlus2b ? diag::warn_cxx2b_compat_pp_directive
                                         : diag::ext_cxx2b_pp_directive;
         else
           DiagID = LangOpts.C2x ? diag::warn_c2x_compat_pp_directive