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

   ///
   SourceLocation getLocationOfByte(unsigned ByteNo, const SourceManager &SM,
                                    const LangOptions &Features,
-                                   const TargetInfo &Target) const;
+                                   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 {

lib/AST/Expr.cpp

 /// can have escape sequences in them in addition to the usual trigraph and
 /// escaped newline business.  This routine handles this complexity.
 ///
+/// 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) const {
+                  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);

     // 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;
     

     // 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;
   }

lib/CodeGen/CGStmt.cpp

   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) {
-      if (StrVal[i] != '\n') continue;
+    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());
+                                                      CGF.getTarget(),
+                                                      &StartToken,
+                                                      &ByteOffset);
       Locs.push_back(llvm::ConstantAsMetadata::get(
           llvm::ConstantInt::get(CGF.Int32Ty, LineLoc.getRawEncoding())));
     }