[Lex] Simplify and cleanup the updateConsecutiveMacroArgTokens implementation.

[hokein]

Summary

The code falls back to the pre-2011 partition-file-id solution (see for
details).

This patch simplifies/rewrites the code based on the partition-based-on-file-id
idea. The new implementation is optimized by reducing the number of
calling getFileID (~40% drop).

Despite the huge drop of getFileID, this is a marignal improvment on
speed (becase the number of calling non-cached getFileID is roughly
the same). It removes the evaluation-order performance gap between gcc-built-clang
and clang-built-clang.

SemaExpr.cpp:

• before: 315063 SLocEntries, FileID scans: 388230 linear, 1393437 binary. 458893 cache hits, 672299 getFileID calls
• after: 313494 SLocEntries, FileID scans: 397525 linear, 1451890 binary, 176714 cache hits, 397144 getFileID calls

FindTarget.cpp:

• before: 279984 SLocEntries, FileID scans: 361926 linear, 1275930 binary, 436072 cache hits, 632150 getFileID calls
• after: 278426 SLocEntries, FileID scans: 371279 linear, 1333963 binary, 153705 cache hits, 356814 getFileID calls

[hokein]

Some more perf data on building linux kernel (x86_64)

before: getFileID 2.4% (1.10% on getFileIDSlow)
after: getFileID 2.35% (1.05% on getFileIDSlow)

[nickdesaulniers]

In D134942#3827216, @hokein wrote:

Some more perf data on building linux kernel (x86_64)

before: getFileID 2.4% (1.10% on getFileIDSlow)
after: getFileID 2.35% (1.05% on getFileIDSlow)

What compiler was used as the bootstrap?

For me bootstrapping w/ clang, I observed:

Before:
+    2.11%  clang-15                           [.] clang::SourceManager::getFileIDLocal
After:
+    2.01%  clang-15                           [.] clang::SourceManager::getFileIDLocal

I can test again bootstrapping with gcc.

This is such a small improvement that I'm tempted to say "look elsewhere." But it is an improvement in the hottest method, and gets rid of that awful magic constant 50. It might take a few refactorings to get this method out of the top spot of profiles.

[nickdesaulniers]

clang/lib/Lex/TokenLexer.cpp

1006–1011

Could you just check that all of the tokens in the partition have the same fileID as the first token?

FileID FirstFID = SM.getFileID(Partition[0]->getLocation());
llvm::all_of(Partition, [&SM, &FirstID](const Token &T) { return SM.getFileID(T.getLocation() == FID; });

or move the assertion into the take_while above so we iterate less?

[hokein]

update

[hokein]

In D134942#3828449, @nickdesaulniers wrote:

In D134942#3827216, @hokein wrote:

Some more perf data on building linux kernel (x86_64)

before: getFileID 2.4% (1.10% on getFileIDSlow)
after: getFileID 2.35% (1.05% on getFileIDSlow)

What compiler was used as the bootstrap?

For me bootstrapping w/ clang, I observed:

Before:
+    2.11%  clang-15                           [.] clang::SourceManager::getFileIDLocal
After:
+    2.01%  clang-15                           [.] clang::SourceManager::getFileIDLocal

That's interesting. I also used clang (v14) for bootstrapping.

What's your base revision? I'm using d32b8fdbdb4b99a5cc21604db6211fc506eb1f9b, looking at your profile (clang-15), I think your base revision is older than mine (my profile shows clang-16).

clang/lib/Lex/TokenLexer.cpp

1006–1011

The optimization for this case is that we don't call any getFileID, the getFileID is only needed in the assert sanity check, so moving the assertion to take_while doesn't really work.

I adjust the code to save some unnecessary getFileID call in assert.

[sammccall]

Thanks, I think this is worthwhile for the simpler code, better (non-lying) comments, avoiding arg-evaluation-order stuff.

-0.05% time and -0.5% SLocEntries is interesting too! Clearly not earth-shattering but the the offset table idea gives us a lead to follow.
I do have one idea to skip a getFileID() that might not be cached...

clang/lib/Lex/TokenLexer.cpp

999

I think this comment can be shorter while still getting its point across.

// Consecutive tokens not written in macros must be from the same file.
// (Neither #include nor eof can occur inside a macro argument.)

1006

this assertion seems to belong outside the if() - it applies to both the file/macro case?
I'd suggest asserting nonempty first and then the rest as another assertion.
also missing an assertion that if there are any more tokens, the next token has a different FileID

that said with these assertions we should probably check we're not regressing debug performance too much!

1017

this getFileID() call is unneccesary when All.empty() || All.front().getLocation().isFileID().

Worth checking whether bailing out in that case is profitable?

You could do it right at the top:

if (All.size() == 1 || All[0].getLocation().isFileID() != All[1].getLocation().isFileID())
  return All.take_front(1);

1021

nit: s/begin/front/ if you're using back()

1037

hmm, actually maybe just before this line would be the best place to assert that T and BeginLoc are in the same FileID, as it justifies the subtraction

[nickdesaulniers]

clang/lib/Lex/TokenLexer.cpp

1006

Right, I do all development and profiles with Release builds with assertions enabled. So avoiding getFileID in release+no_asserts builds is a win, but am somewhat bummed to not get as much a win for my rel+assert builds.

1017

Good point; I'd say "avoid getFileID" at all costs, even to readability/style.

[hokein]

address comments

[hokein]

clang/lib/Lex/TokenLexer.cpp

1006

this assertion seems to belong outside the if() - it applies to both the file/macro case?

yeah, it should apply the else case. Moved it outside -- it seems unnecessary to check the else case, since we actually do the partition based on the file id (that being said, it is somehow like int s = 1+1; assert(s == 2);), but it might be good for code readability.

I do all development and profiles with Release builds with assertions enabled

hmm, I think when doing profiles we probably should use a release build without assertions enabled to give a more correct result, since assertion will slow everything down.

1017

We have handled the 1-element special case in the caller, so All.size() > 1 in this function. Added an assertion.

All[0].getLocation().isFileID() != All[1].getLocation().isFileID()

I tried it when writing this patch, I don't find the result now, but IIRC performance difference is negligible. I'm happy to add this special case since it won't hurt the readability too much.

1037

I agree that this is the best place to put the check-file-id assertion.

Simply adding assert(getFileID(BeginLoc) == getFileID(T.getLocation())) can work, but it creates N-1 unnecessary getFileID calls on BeginLoc for assert build, it is better to avoid it. The only way I can think of is

#ifndef NDEBUG
FileID BeginFID = SM.getFileID(BeginLoc);
assert(BeginFID == getFileID(T.getLocation()));
#endif

[sammccall]

clang/lib/Lex/TokenLexer.cpp

1037

I assume you mean with the #if once above, but the assert outside the #if and inside the loop?
That LGTM

There's also #ifdef EXPENSIVE_CHECKS, maybe not needed here though.

[nickdesaulniers]

clang/lib/Lex/TokenLexer.cpp

1019

Please consider moving this to

#ifdef EXPENSIVE_CHECKS rather than asserts.

clang/lib/Lex/TokenLexer.cpp

 #include "clang/Lex/LexDiagnostic.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Lex/MacroArgs.h"
 #include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Lex/Token.h"
 #include "clang/Lex/VariadicMacroSupport.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include <cassert>
 #include <cstring>
 
 using namespace clang;
 

 /// for the 'foo', '==', 'bar' tokens will point inside that chunk.
 ///
 /// \arg begin_tokens will be updated to a position past all the found
 /// consecutive tokens.
 static void updateConsecutiveMacroArgTokens(SourceManager &SM,
                                             SourceLocation InstLoc,
                                             Token *&begin_tokens,
                                             Token * end_tokens) {
-  assert(begin_tokens < end_tokens);
-
-  SourceLocation FirstLoc = begin_tokens->getLocation();
-  SourceLocation CurLoc = FirstLoc;
-
-  // Compare the source location offset of tokens and group together tokens that
-  // are close, even if their locations point to different FileIDs. e.g.
-  //
-  //  |bar    |  foo | cake   |  (3 tokens from 3 consecutive FileIDs)
-  //  ^                    ^
-  //  |bar       foo   cake|     (one SLocEntry chunk for all tokens)
-  //
-  // we can perform this "merge" since the token's spelling location depends
-  // on the relative offset.
-
-  Token *NextTok = begin_tokens + 1;
-  for (; NextTok < end_tokens; ++NextTok) {
-    SourceLocation NextLoc = NextTok->getLocation();
-    if (CurLoc.isFileID() != NextLoc.isFileID())
-      break; // Token from different kind of FileID.
-
-    SourceLocation::IntTy RelOffs;
-    if (!SM.isInSameSLocAddrSpace(CurLoc, NextLoc, &RelOffs))
-      break; // Token from different local/loaded location.
-    // Check that token is not before the previous token or more than 50
-    // "characters" away.
-    if (RelOffs < 0 || RelOffs > 50)
-      break;
-
-    if (CurLoc.isMacroID() && !SM.isWrittenInSameFile(CurLoc, NextLoc))
-      break; // Token from a different macro.
-
-    CurLoc = NextLoc;
+  assert(begin_tokens + 1 < end_tokens);
+  SourceLocation BeginLoc = begin_tokens->getLocation();
+  llvm::MutableArrayRef<Token> All(begin_tokens, end_tokens);
+  llvm::MutableArrayRef<Token> Partition;
+
+  // Partition the tokens by their FileID.
+  // This is a hot function, and calling getFileID can be expensive, the
+  // implementation is optimized by reducing the number of getFileID.
+  if (BeginLoc.isFileID()) {
+    // Consecutive tokens not written in macros must be from the same file.
+    // (Neither #include nor eof can occur inside a macro argument.)
+    Partition = All.take_while([&](const Token &T) {
+      return T.getLocation().isFileID();
+    });
+  } else {
+    // Call getFileID once to calculate the bounds, and use the cheaper
+    // sourcelocation-against-bounds comparison.
+    FileID BeginFID = SM.getFileID(BeginLoc);
+    SourceLocation Limit =
+        SM.getComposedLoc(BeginFID, SM.getFileIDSize(BeginFID));
+    Partition = All.take_while([&](const Token &T) {
+      return T.getLocation() >= BeginLoc && T.getLocation() < Limit;
+    });
   }
+  assert(!Partition.empty());
 
   // For the consecutive tokens, find the length of the SLocEntry to contain
   // all of them.
-  Token &LastConsecutiveTok = *(NextTok-1);
-  SourceLocation::IntTy LastRelOffs = 0;
-  SM.isInSameSLocAddrSpace(FirstLoc, LastConsecutiveTok.getLocation(),
-                           &LastRelOffs);
   SourceLocation::UIntTy FullLength =
-      LastRelOffs + LastConsecutiveTok.getLength();
-
+      Partition.back().getEndLoc().getRawEncoding() -
+      Partition.front().getLocation().getRawEncoding();
   // Create a macro expansion SLocEntry that will "contain" all of the tokens.
   SourceLocation Expansion =
-      SM.createMacroArgExpansionLoc(FirstLoc, InstLoc,FullLength);
+      SM.createMacroArgExpansionLoc(BeginLoc, InstLoc, FullLength);
 
+#ifdef EXPENSIVE_CHECKS
+  assert(llvm::all_of(Partition.drop_front(),
+                      [&SM, ID = SM.getFileID(Partition.front().getLocation())](
+                          const Token &T) {
+                        return ID == SM.getFileID(T.getLocation());
+                      }) &&
+         "Must have the same FIleID!");
+#endif
   // Change the location of the tokens from the spelling location to the new
   // expanded location.
-  for (; begin_tokens < NextTok; ++begin_tokens) {
-    Token &Tok = *begin_tokens;
-    SourceLocation::IntTy RelOffs = 0;
-    SM.isInSameSLocAddrSpace(FirstLoc, Tok.getLocation(), &RelOffs);
-    Tok.setLocation(Expansion.getLocWithOffset(RelOffs));
+  for (Token& T : Partition) {
+    SourceLocation::IntTy RelativeOffset =
+        T.getLocation().getRawEncoding() - BeginLoc.getRawEncoding();
+    T.setLocation(Expansion.getLocWithOffset(RelativeOffset));
   }
+  begin_tokens = &Partition.back() + 1;
 }
 
 /// Creates SLocEntries and updates the locations of macro argument
 /// tokens to their new expanded locations.
 ///
 /// \param ArgIdSpellLoc the location of the macro argument id inside the macro
 /// definition.
 void TokenLexer::updateLocForMacroArgTokens(SourceLocation ArgIdSpellLoc,