[Lex] Bring back the magic number 50 in updateConsecutiveMacroArgTokens.

[hokein]

Summary

The magic number 50 was removed in D134942, as a behavior change for
performance reason.

While it reduces the number of SLocEntry, it increases the usage of
SourceLocation address space usage, which is critical for compiling
large TU.

This fixes a regression caused in D134942 -- clang failed to compile one of
our internal files, complaining the file is too large to process because clang
runs out of source location space (we spend 40% more address space!)

[alexfh]

LG, thanks!

[sammccall]

This is a subtle change that needs careful review, and honestly should have a test.

I realize there's a breakage that needs to be fixed with some urgency and you believe you're just restoring the old behavior, however in that case the right course of action is to revert the patch.
As it turns out I think this introduces a bug when offset space is nearly full.

clang/lib/Lex/TokenLexer.cpp

991

distance -> Distance

991

having worked quite hard to make this code readable, copy/pasting the same (buggy) algorithm in both places seems like an unfortunate choice.

I'd suggest:

auto NearLast = [&, Last{BeginLoc}](SourceLocation Loc) mutable {
  constexpr int Limit = 50;
  SourceLocation IntTy  RelOffs;
  if (!SM.isInSameSLocAddrSpace(Last, Loc, &RelOffs) || RelOffs < 0 || RelOffs > Limit)
    return false;
  Last = Loc;
  return true;
};

...
Partition = All.take_while([&]{
  return T.getLocation() >= BeginLoc && T.getLocation() < Limit && NearLast(T.getLocation());
});

Here NearLast can be shared between both branches.

992

This seems to be missing the same-sloc-address-space check: it can create a single file ID spanning a local and loaded sloc entry, which will be corrupted by saving+loading

992

(getOffset() would be much clearly correct than getRawEncoding())

[sammccall]

This is a subtle change that needs careful review, and honestly should have a test.

Um, sorry for the grumpy tone. I thought this had already been quickly landed! Apologies...

[alexfh]

In D136539#3877872, @sammccall wrote:

This is a subtle change that needs careful review, and honestly should have a test.

I realize there's a breakage that needs to be fixed with some urgency and you believe you're just restoring the old behavior, however in that case the right course of action is to revert the patch.

You're right. Let's first revert the change that caused the problem and then figure out what amount of testing is necessary here.

[alexfh]

FYI, I've reverted f83347b0bedb22ea676861c8e4e2ed9c31371ade and 74e4f778cf16cbf7163b5c6de6027a43f5e9169f.

[alexfh]

Undo LGTM, since we decided to go with a revert.

[hokein]

address comments and add a stress test.

[hokein]

This is a subtle change that needs careful review, and honestly should have a test.

I agree, and thanks for the nice review comments!

I'd like to add a unittest, but I don't see a straight way (I manually test it by comparing the number of allocated SLocEntries and the used SourceLocation address space in clang --print-stats with/out this patch), some options:

1. construct a large TU that will make clang fails to compile without the 50 trick patch;
2. create a small test, and verify the the source location is split when the two consecutive tokens distance > 50, and verify the number of in clang print-stats;

1 feels better to reflect the real behavior, the only concern is that this is a stress test, running it is expensive (we also have a similar SourceLocationsOverlow.c, I guess it is ok to add it).

clang/lib/Lex/TokenLexer.cpp

992

missing the same-sloc-address-space check

oops, good spot. Indeed this is another behavior change in the previous-rewriting patch :( -- the original behavior was that if two consecutive tokens are not in the same address space, it split to two expansion SLocEntries.

Fixed.

[sammccall]

In D136539#3882316, @hokein wrote:

This is a subtle change that needs careful review, and honestly should have a test.

I agree, and thanks for the nice review comments!

I'd like to add a unittest, but I don't see a straight way (I manually test it by comparing the number of allocated SLocEntries and the used SourceLocation address space in clang --print-stats with/out this patch), some options:

1. construct a large TU that will make clang fails to compile without the 50 trick patch;
2. create a small test, and verify the the source location is split when the two consecutive tokens distance > 50, and verify the number of in clang print-stats;

1 feels better to reflect the real behavior, the only concern is that this is a stress test, running it is expensive (we also have a similar SourceLocationsOverlow.c, I guess it is ok to add it).

I was all ready to say that option 2 is the only practical one, and was surprised that you had an actual testcase.
I'm a bit nervous (it must be slow and eat tons of ram) but if we already have a similar test...

clang/lib/Lex/TokenLexer.cpp

992

oops, good spot. Indeed this is another behavior change in the previous-rewriting patch :(

Argh, I'm so sorry, this prompted me to take another look and there is no bug/need for the check at all.

Before we do the NearLast check we've already established that the FileID is the same, which means the locations are necessarily in the same address space.

We can replace the isInSameSLocAddrSpace with a raw offset comparison again...

[hokein]

refine the test.

[hokein]

In D136539#3882922, @sammccall wrote:

In D136539#3882316, @hokein wrote:

This is a subtle change that needs careful review, and honestly should have a test.

I agree, and thanks for the nice review comments!

I'd like to add a unittest, but I don't see a straight way (I manually test it by comparing the number of allocated SLocEntries and the used SourceLocation address space in clang --print-stats with/out this patch), some options:

1. construct a large TU that will make clang fails to compile without the 50 trick patch;
2. create a small test, and verify the the source location is split when the two consecutive tokens distance > 50, and verify the number of in clang print-stats;

1 feels better to reflect the real behavior, the only concern is that this is a stress test, running it is expensive (we also have a similar SourceLocationsOverlow.c, I guess it is ok to add it).

I was all ready to say that option 2 is the only practical one, and was surprised that you had an actual testcase.
I'm a bit nervous (it must be slow and eat tons of ram) but if we already have a similar test...

now I change my mind -- this test is very expensive, taking ~8s to run (which is 4x slower than the SourceLocationsOverlow.c), adding it is not a good idea. Switched to 2.

clang/lib/Lex/TokenLexer.cpp

992

hmm, I think there was some misunderstanding here -- I thought you meant a corner case where Last and T are in the same file, but Last.offset < CurrentLoadedOffset, and T.offset > CurrentLoadedOffset. For this case, there is a behavior change between both versions.

I'm not sure whether this case is possible or it is reasonable to handle it, since it is a running-out-of-sourcelocation-space case (clang's behavior is somewhat inconsistent, in CreateFileID, we emit a too-large diagnostic, in createExpansionLocImpl, it is just an assertion), maybe we should not worry about this case, treat it as UB.

[sammccall]

LG other than removing the redundant same-sloc-address check again (sorry!)

clang/lib/Lex/TokenLexer.cpp

992

hmm, I think there was some misunderstanding here -- I thought you meant a corner case where Last and T are in the same file, but Last.offset < CurrentLoadedOffset and T.offset > CurrentLoadedOffset

That's not possible, loaded vs local is a property of the FileID. I was missing that we'd established they're in the same FileID before checking deltas.

clang/test/Lexer/update_consecutive_macro_address_space.c

3

it's a shame there's no -cc1 flag for SourceManager::dump() or this could be much more direct...

[hokein]

upload the full reland version.

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;
 

 /// point to that SLocEntry. e.g for
 ///   assert(foo == bar);
 /// There will be a single SLocEntry for the "foo == bar" chunk and locations
 /// 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,
+                                            SourceLocation ExpandLoc,
                                             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.
+  assert(begin_tokens + 1 < end_tokens);
+  SourceLocation BeginLoc = begin_tokens->getLocation();
+  llvm::MutableArrayRef<Token> All(begin_tokens, end_tokens);
+  llvm::MutableArrayRef<Token> Partition;
+
+  auto NearLast = [&, Last = BeginLoc](SourceLocation Loc) mutable {
+    // The maximum distance between two consecutive tokens in a partition.
+    // This is an important trick to avoid using too much SourceLocation address
+    // space!
+    static constexpr SourceLocation::IntTy MaxDistance = 50;
+    auto Distance = Loc.getRawEncoding() - Last.getRawEncoding();
+    Last = Loc;
+    return Distance <= MaxDistance;
+  };
 
-    CurLoc = NextLoc;
+  // 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() && NearLast(T.getLocation());
+    });
+  } 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 &&
+             NearLast(T.getLocation());
+    });
   }
+  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, ExpandLoc, 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,
                                             Token *begin_tokens,
                                             Token *end_tokens) {
   SourceManager &SM = PP.getSourceManager();
 
-  SourceLocation InstLoc =
+  SourceLocation ExpandLoc =
       getExpansionLocForMacroDefLoc(ArgIdSpellLoc);
 
   while (begin_tokens < end_tokens) {
     // If there's only one token just create a SLocEntry for it.
     if (end_tokens - begin_tokens == 1) {
       Token &Tok = *begin_tokens;
       Tok.setLocation(SM.createMacroArgExpansionLoc(Tok.getLocation(),
-                                                    InstLoc,
+                                                    ExpandLoc,
                                                     Tok.getLength()));
       return;
     }
 
-    updateConsecutiveMacroArgTokens(SM, InstLoc, begin_tokens, end_tokens);
+    updateConsecutiveMacroArgTokens(SM, ExpandLoc, begin_tokens, end_tokens);
   }
 }
 
 void TokenLexer::PropagateLineStartLeadingSpaceInfo(Token &Result) {
   AtStartOfLine = Result.isAtStartOfLine();
   HasLeadingSpace = Result.hasLeadingSpace();
 }

clang/test/Lexer/update_consecutive_macro_address_space.c

+// RUN: %clang -cc1 -print-stats %s 2>&1 | FileCheck %s
+// CHECK: 6 local SLocEntry's allocated
+//
+// Verify that the macro arg expansion is split to two file ids, we have 6 file
+// ids rather than 5:
+//   0: invalid file id
+//   1: main file
+//   2: builtin file
+//   3: macro expansion for X
+//   4: macro arg expansions for 1
+//   5: macro arg expansions for == 2
+#define X(x) (int)(x);
+void func() {
+  X(1
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+/*************************************************************************************************/
+== 2);
+}