Improve running time of getAsmSrcLocInfo

[yunlian]

Summary

This tries to improve the compilation time of the test case in
https://llvm.org/bugs/show_bug.cgi?id=25416

The problem is that when trying to get the SrcLocInfo for asm, it tries to get the SrcLoc for each
line inside the asm string. For each line, it goes through the token table once. This is not optimal,
we can find the SrcLoc for all the lines of the asm with a single scan of the token table. To do this,
we need to store the information of the location of current token and the total size of token been
processed.

[yunlian]

Some format changes.

[• rafael]

Can you add a testcase? Anything that used to take 5s and is now much faster should get noticed if this regresses.

[yunlian]

Is there an example for the test case with timeout? Thanks

[rsmith]

include/clang/AST/Expr.h

1613–1617

Please run this through clang-format.

lib/AST/Expr.cpp

1009

Please update the doc comment to explain what the new parameters do and how they should be used.

1013

StartTokenByteOffset or ByteOffsetOfStartToken would be more obvious names here.

[yunlian]

The clang-format check is done. The doc comment is updated.

[yunlian]

ping?

[• rafael]

include/clang/AST/Expr.h

1615

Are you sure you used clang-format? The pointer style we use in llvm is "type *var".

One way to do it is to run "git clang-format master", assuming you have this patch in a git branch.

[yunlian]

I did not realize that git clang-format will modify the code directly. Updated.
Thanks

[• rafael]

lib/AST/Expr.cpp

1030

This part also needs git-clang-format..

[yunlian]

lib/AST/Expr.cpp

1030

Which part? Could you please give me some advice on how to modify it?
Thanks
I run git clang-format and it says clang-format did not modify any files.

[• rafael]

if (StartToken) TokNo = *StartToken;

It should have a newline.

[yunlian]

lib/AST/Expr.cpp

1030

For this line:
if (StartToken) TokNo = *StartToken;

I try to make it like
if (StartToken)

TokNo = *StartToken;

Bug git clang-format changes it back.

[• rafael]

There is something strange with your git-clang-format setup. This is
what I get locally.

Cheers,
Rafael

• t.diff415 KBDownload

[yunlian]

Applied Rafael's patch while still looking to see what is wrong of my git clang format.

[llvm-commits]

David, did you also have a clang-format issue where it wasn't breaking
short if's? In the end how did you fix it? Yunlian seems to be having a
similar problem.

• Sean Silva
  • msg-19522-253.txt162 BDownload

[yunlian]

ping?

[yunlian]

ping?

[rsmith]

LGTM

A testcase would be nice, but I guess the speedup here isn't dramatic enough to really be testable with an test case of a sane size (quadratic to linear in the size of the input)?

[yunlian]

A test case with 4K lines of code can show the difference. Reducing the compilation time from 3 seconds to instant on my desktop. Do you need that?
Could you please commit this for me? I still do not have the right to commit yet.

[rsmith]

Committed as r255198.

include/clang/AST/Expr.h

public:
 
   /// getLocationOfByte - Return a source location that points to the specified
   /// byte of this string literal.
   ///
   /// Strings are amazingly complex.  They can be formed from multiple tokens
   /// and can have escape sequences in them in addition to the usual trigraph
   /// and escaped newline business.  This routine handles this complexity.
   ///
-  SourceLocation getLocationOfByte(unsigned ByteNo, const SourceManager &SM,
-                                   const LangOptions &Features,
-                                   const TargetInfo &Target) const;
+  SourceLocation
+  getLocationOfByte(unsigned ByteNo, const SourceManager &SM,
+                    const LangOptions &Features, const TargetInfo &Target,
+                    unsigned *StartToken = nullptr,
+                    unsigned *StartTokenByteOffset = nullptr) const;
 
   typedef const SourceLocation *tokloc_iterator;
   tokloc_iterator tokloc_begin() const { return TokLocs; }
-  tokloc_iterator tokloc_end() const { return TokLocs+NumConcatenated; }
+  tokloc_iterator tokloc_end() const { return TokLocs + NumConcatenated; }
 
   SourceLocation getLocStart() const LLVM_READONLY { return TokLocs[0]; }
   SourceLocation getLocEnd() const LLVM_READONLY {
     return TokLocs[NumConcatenated - 1];
   }
 
   static bool classof(const Stmt *T) {
     return T->getStmtClass() == StringLiteralClass;

lib/AST/Expr.cpp

 }
 
 /// getLocationOfByte - Return a source location that points to the specified
 /// byte of this string literal.
 ///
 /// Strings are amazingly complex.  They can be formed from multiple tokens and
 /// can have escape sequences in them in addition to the usual trigraph and
 /// escaped newline business.  This routine handles this complexity.
 ///
-SourceLocation StringLiteral::
-getLocationOfByte(unsigned ByteNo, const SourceManager &SM,
-                  const LangOptions &Features, const TargetInfo &Target) const {
+/// The *StartToken sets the first token to be searched in this function and
+/// the *StartTokenByteOffset is the byte offset of the first token. Before
+/// returning, it updates the *StartToken to the TokNo of the token being found
+/// and sets *StartTokenByteOffset to the byte offset of the token in the
+/// string.
+/// Using these two parameters can reduce the time complexity from O(n^2) to
+/// O(n) if one wants to get the location of byte for all the tokens in a
+/// string.
+///
+SourceLocation
+StringLiteral::getLocationOfByte(unsigned ByteNo, const SourceManager &SM,
+                                 const LangOptions &Features,
+                                 const TargetInfo &Target, unsigned *StartToken,
+                                 unsigned *StartTokenByteOffset) const {
   assert((Kind == StringLiteral::Ascii || Kind == StringLiteral::UTF8) &&
          "Only narrow string literals are currently supported");
 
   // Loop over all of the tokens in this string until we find the one that
   // contains the byte we're looking for.
   unsigned TokNo = 0;
+  unsigned StringOffset = 0;
+  if (StartToken)
+    TokNo = *StartToken;
+  if (StartTokenByteOffset) {
+    StringOffset = *StartTokenByteOffset;
+    ByteNo -= StringOffset;
+  }
   while (1) {
     assert(TokNo < getNumConcatenated() && "Invalid byte number!");
     SourceLocation StrTokLoc = getStrTokenLoc(TokNo);
     
     // Get the spelling of the string so that we can get the data that makes up
     // the string literal, not the identifier for the macro it is potentially
     // expanded through.
     SourceLocation StrTokSpellingLoc = SM.getSpellingLoc(StrTokLoc);
-    
     // Re-lex the token to get its length and original spelling.
-    std::pair<FileID, unsigned> LocInfo =SM.getDecomposedLoc(StrTokSpellingLoc);
+    std::pair<FileID, unsigned> LocInfo =
+        SM.getDecomposedLoc(StrTokSpellingLoc);
     bool Invalid = false;
     StringRef Buffer = SM.getBufferData(LocInfo.first, &Invalid);
-    if (Invalid)
+    if (Invalid) {
+      if (StartTokenByteOffset != nullptr)
+        *StartTokenByteOffset = StringOffset;
+      if (StartToken != nullptr)
+        *StartToken = TokNo;
       return StrTokSpellingLoc;
-    
+    }
     const char *StrData = Buffer.data()+LocInfo.second;
     
     // Create a lexer starting at the beginning of this token.
     Lexer TheLexer(SM.getLocForStartOfFile(LocInfo.first), Features,
                    Buffer.begin(), StrData, Buffer.end());
     Token TheTok;
     TheLexer.LexFromRawLexer(TheTok);
     
     // Use the StringLiteralParser to compute the length of the string in bytes.
     StringLiteralParser SLP(TheTok, SM, Features, Target);
     unsigned TokNumBytes = SLP.GetStringLength();
     
     // If the byte is in this token, return the location of the byte.
     if (ByteNo < TokNumBytes ||
         (ByteNo == TokNumBytes && TokNo == getNumConcatenated() - 1)) {
-      unsigned Offset = SLP.getOffsetOfStringByte(TheTok, ByteNo); 
-      
+      unsigned Offset = SLP.getOffsetOfStringByte(TheTok, ByteNo);
       // Now that we know the offset of the token in the spelling, use the
       // preprocessor to get the offset in the original source.
+      if (StartTokenByteOffset != nullptr)
+        *StartTokenByteOffset = StringOffset;
+      if (StartToken != nullptr)
+        *StartToken = TokNo;
       return Lexer::AdvanceToTokenCharacter(StrTokLoc, Offset, SM, Features);
     }
-    
     // Move to the next string token.
+    StringOffset += TokNumBytes;
     ++TokNo;
     ByteNo -= TokNumBytes;
   }
 }
 
 
 
 /// getOpcodeStr - Turn an Opcode enum value into the punctuation char it

lib/CodeGen/CGStmt.cpp

static llvm::MDNode *getAsmSrcLocInfo(const StringLiteral *Str,
   SmallVector<llvm::Metadata *, 8> Locs;
   // Add the location of the first line to the MDNode.
   Locs.push_back(llvm::ConstantAsMetadata::get(llvm::ConstantInt::get(
       CGF.Int32Ty, Str->getLocStart().getRawEncoding())));
   StringRef StrVal = Str->getString();
   if (!StrVal.empty()) {
     const SourceManager &SM = CGF.CGM.getContext().getSourceManager();
     const LangOptions &LangOpts = CGF.CGM.getLangOpts();
+    unsigned StartToken = 0;
+    unsigned ByteOffset = 0;
 
     // Add the location of the start of each subsequent line of the asm to the
     // MDNode.
-    for (unsigned i = 0, e = StrVal.size()-1; i != e; ++i) {
+    for (unsigned i = 0, e = StrVal.size() - 1; i != e; ++i) {
       if (StrVal[i] != '\n') continue;
-      SourceLocation LineLoc = Str->getLocationOfByte(i+1, SM, LangOpts,
-                                                      CGF.getTarget());
+      SourceLocation LineLoc = Str->getLocationOfByte(
+          i + 1, SM, LangOpts, CGF.getTarget(), &StartToken, &ByteOffset);
       Locs.push_back(llvm::ConstantAsMetadata::get(
           llvm::ConstantInt::get(CGF.Int32Ty, LineLoc.getRawEncoding())));
     }
   }
 
   return llvm::MDNode::get(CGF.getLLVMContext(), Locs);
 }