[clang-rename] improve performance for rename-all

[omtcyfz]

Summary

As Miklos Vajna noticed clang-rename rename-all has significant performance problems, which exposed the fact that clang-rename parses translation unit N times where N stands for the number of {offset | old-name} -> new-name pairs.

This patch prevents clang-rename from parsing translation unit multiple times.

[omtcyfz]

Prevent unnecessary std::vector copying. Explicitly write type.

[vmiklos]

I can confirm that with this, the test script from the mail thread shows that clang-rename is almost as fast as clang++ as expected. Thanks!

[alexander-shaposhnikov]

clang-rename/USRFindingAction.h

38–41

in the constructor SymbolOffsets, OldNames are passed by non-constant reference
but then you make a copy.

[omtcyfz]

Prevent std::vector from redundant copying.

[omtcyfz]

clang-rename/USRFindingAction.h

38–41

Aw, you're right. Good catch, thanks!

[alexfh]

clang-rename/USRFindingAction.cpp

69

Should USRs be a local variable now?

147

Use ArrayRef here as well. BTW, if the code relies on SymbolOffsets and OldNames being of the same length, maybe a single collection of pairs would work better? Or define a structure for keeping offset and old name together?

clang-rename/USRFindingAction.h

29

Use ArrayRef instead of const vector<>&. ArrayRef<> is less restrictive.

30

Use ArrayRef<std::string>.

38

Reference members always seem suspicious to me. One has to be really really careful not to mess up lifetimes. Are we actually saving much but not copying these vectors?

[omtcyfz]

Partly address comments.

[omtcyfz]

clang-rename/USRFindingAction.cpp

69

Can you elaborate please?

clang-rename/USRFindingAction.h

38

Not really, they aren't meant to be quite huge. At this point I have ensured the lifetimes, but if the code would be reused, I agree, it might cause some trouble if one is not careful enough.

Do you propose to perform copying to gain more safety?

[omtcyfz]

Address one more comment.

[omtcyfz]

clang-rename/USRFindingAction.cpp

69–70

Ah, sure. Sorry, didn't understand it at first.

[alexander-shaposhnikov]

clang-rename/USRFindingAction.cpp

207

not particularly important, probably it can be simply

return llvm::make_unique<NamedDeclFindingConsumer>(
    SymbolOffsets, OldNames, SpellingNames, USRList);

[alexander-shaposhnikov]

clang-rename/USRFindingAction.cpp

192

USRList.push_back(std::move(NextUSRBunch))

or (IMO even better)

USRList.push_back(Finder.Find());

[omtcyfz]

clang-rename/USRFindingAction.cpp

193–194

Yep. Makes sense. Thanks!

207–208

Yes, it's way better.

[alexfh]

clang-rename/USRFindingAction.cpp

147

What about the second part?

BTW, if the code relies on SymbolOffsets and OldNames being of the same length, maybe a single collection of pairs would work better? Or define a structure for keeping offset and old name together?

clang-rename/USRFindingAction.h

38–42

Yes, I think, copying here makes sense to uncouple lifetime of the creator of the class with the lifetime of this class.

[vmiklos]

It is expected that either SymbolOffsets or OldNames is empty, and the size of the non-empty container is the same as the size of the NewNames container. So no, the code does not rely on the offsets and the old names having the same length.

[omtcyfz]

In D23651#521031, @vmiklos wrote:

It is expected that either SymbolOffsets or OldNames is empty, and the size of the non-empty container is the same as the size of the NewNames container. So no, the code does not rely on the offsets and the old names having the same length.

If I understood correctly, you and Alex are talking about different things.

As far as I understand Alex what he meant is the code inside USRFindingAction.cpp relies on SymbolOffsetsVector and OldNamesVector (or whatever I actually called them) having same size. And that's right. See clang-rename/USRFindingAction.cpp line 153 in current diff. And I actually construct them to have the same size (see line 212 in clang-rename/ClangRename.cpp). I do not claim this to be the best solution, open to any other ideas, but it isn't too ugly to do so IMO.

If I understand you correctly code doesn't rely on SymbolOffsets and OldNames having equal size. And that's also correct.

Thus said, what Alex proposes (bind offset and old-name together while passing to USRFindingAction) makes sense to me.

[omtcyfz]

Address couple of comments.

[omtcyfz]

Actually, it might make sense to merge rename-at and rename-all after all. Passing a list of old-name/offset -> new-name is just easier.

But that's for another patch.

[vmiklos]

If I understood correctly, you and Alex are talking about different things.

Yes, sorry, the context of my above comment was the cl::opt instances in the tool itself, not the various parameters to the different actions called from the tool.

[vmiklos]

Kirill, are you waiting for me on this one? AFAICS the patch in its current form applies on top of current trunk, but no longer builds.

[omtcyfz]

In D23651#531884, @vmiklos wrote:

Kirill, are you waiting for me on this one? AFAICS the patch in its current form applies on top of current trunk, but no longer builds.

Miklos, it is a bit more complicated :)

Bascially, I have another patch kind of complete, which is built on top of this patch, which kind of makes this one outdated. Pushing this will make things a bit more complicated. I'll write about it soon enough.

[vmiklos]

Ah, if you mean you squashed this into D24192, then I see what you mean, ignore me. :-)

[omtcyfz]

Revert diff, as the last one "deletes and creates" files instead of "moving and changing them" in the filesystem.

[omtcyfz]

Oops, wrong patch... Abandoning this one anyway.

clang-rename/USRFindingAction.h

 /// \brief Provides an action to find all relevant USRs at a point.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_RENAME_USR_FINDING_ACTION_H_
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_RENAME_USR_FINDING_ACTION_H_
 
 #include "clang/Frontend/FrontendAction.h"
+#include <vector>
 
 namespace clang {
 class ASTConsumer;
 class CompilerInstance;
 class NamedDecl;
 
 namespace rename {
 
 struct USRFindingAction {
-  USRFindingAction(unsigned Offset, const std::string &Name)
-      : SymbolOffset(Offset), OldName(Name) {}
+  USRFindingAction(const std::vector<unsigned> &SymbolOffsets,
+                   const std::vector<std::string> &OldNames)
+      : SymbolOffsets(SymbolOffsets), OldNames(OldNames) {}
   std::unique_ptr<ASTConsumer> newASTConsumer();
 
-  // \brief get the spelling of the USR(s) as it would appear in source files.
-  const std::string &getUSRSpelling() { return SpellingName; }
-
-  const std::vector<std::string> &getUSRs() { return USRs; }
+  const std::vector<std::string> &getUSRSpellings() { return SpellingNames; }
+  const std::vector<std::vector<std::string>> &getUSRList() { return USRList; }
 
 private:
-  unsigned SymbolOffset;
-  std::string OldName;
-  std::string SpellingName;
-  std::vector<std::string> USRs;
+  const std::vector<unsigned> &SymbolOffsets;
+  const std::vector<std::string> &OldNames;
+  std::vector<std::string> SpellingNames;
+  std::vector<std::vector<std::string>> USRList;
 };
 
 } // namespace rename
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_RENAME_USR_FINDING_ACTION_H_

clang-rename/USRFindingAction.cpp

 
 namespace {
 // \brief NamedDeclFindingConsumer should delegate finding USRs of given Decl to
 // AdditionalUSRFinder. AdditionalUSRFinder adds USRs of ctor and dtor if given
 // Decl refers to class and adds USRs of all overridden methods if Decl refers
 // to virtual method.
 class AdditionalUSRFinder : public RecursiveASTVisitor<AdditionalUSRFinder> {
 public:
-  explicit AdditionalUSRFinder(const Decl *FoundDecl, ASTContext &Context,
-                               std::vector<std::string> *USRs)
-      : FoundDecl(FoundDecl), Context(Context), USRs(USRs) {}
+  explicit AdditionalUSRFinder(const Decl *FoundDecl, ASTContext &Context)
+      : FoundDecl(FoundDecl), Context(Context) {}
 
-  void Find() {
+  std::vector<std::string> Find() {
     // Fill OverriddenMethods and PartialSpecs storages.
     TraverseDecl(Context.getTranslationUnitDecl());
     if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(FoundDecl)) {
       addUSRsOfOverridenFunctions(MethodDecl);
       for (const auto &OverriddenMethod : OverriddenMethods) {
         if (checkIfOverriddenFunctionAscends(OverriddenMethod)) {
           USRSet.insert(getUSRForDecl(OverriddenMethod));
         }
       }
     } else if (const auto *RecordDecl = dyn_cast<CXXRecordDecl>(FoundDecl)) {
       handleCXXRecordDecl(RecordDecl);
     } else if (const auto *TemplateDecl =
                    dyn_cast<ClassTemplateDecl>(FoundDecl)) {
       handleClassTemplateDecl(TemplateDecl);
     } else {
       USRSet.insert(getUSRForDecl(FoundDecl));
     }
-    USRs->insert(USRs->end(), USRSet.begin(), USRSet.end());
+    USRs.insert(USRs.end(), USRSet.begin(), USRSet.end());
+    return USRs;
   }
 
   bool VisitCXXMethodDecl(const CXXMethodDecl *MethodDecl) {
     if (MethodDecl->isVirtual()) {
       OverriddenMethods.push_back(MethodDecl);
     }
     return true;
   }
for (const auto &OverriddenMethod : MethodDecl->overridden_methods()) {
       }
       return checkIfOverriddenFunctionAscends(OverriddenMethod);
     }
     return false;
   }
 
   const Decl *FoundDecl;
   ASTContext &Context;
-  std::vector<std::string> *USRs;
+  std::vector<std::string> USRs;
   std::set<std::string> USRSet;
   std::vector<const CXXMethodDecl *> OverriddenMethods;
   std::vector<const ClassTemplatePartialSpecializationDecl *> PartialSpecs;
 };
 } // namespace
 
-struct NamedDeclFindingConsumer : public ASTConsumer {
+class NamedDeclFindingConsumer : public ASTConsumer {
+public:
+  explicit NamedDeclFindingConsumer(
+      const std::vector<unsigned> &SymbolOffsets,
+      const std::vector<std::string> &OldNames,
+      std::vector<std::string> &SpellingNames,
+      std::vector<std::vector<std::string>> &USRList)
+      : SymbolOffsets(SymbolOffsets), OldNames(OldNames),
+        SpellingNames(SpellingNames), USRList(USRList) {}
+
   void HandleTranslationUnit(ASTContext &Context) override {
+    for (unsigned I = 0; I < OldNames.size(); ++I) {
+      unsigned SymbolOffset = SymbolOffsets[I];
+      const std::string &OldName = OldNames[I];
       const SourceManager &SourceMgr = Context.getSourceManager();
       // The file we look for the USR in will always be the main source file.
       const SourceLocation Point =
           SourceMgr.getLocForStartOfFile(SourceMgr.getMainFileID())
               .getLocWithOffset(SymbolOffset);
       if (!Point.isValid())
         return;
       const NamedDecl *FoundDecl = nullptr;
       if (OldName.empty()) {
         FoundDecl = getNamedDeclAt(Context, Point);
       } else {
         FoundDecl = getNamedDeclFor(Context, OldName);
       }
       if (FoundDecl == nullptr) {
         FullSourceLoc FullLoc(Point, SourceMgr);
         errs() << "clang-rename: could not find symbol at "
                << SourceMgr.getFilename(Point) << ":"
                << FullLoc.getSpellingLineNumber() << ":"
-             << FullLoc.getSpellingColumnNumber() << " (offset " << SymbolOffset
-             << ").\n";
+               << FullLoc.getSpellingColumnNumber() << " (offset "
+               << SymbolOffset << ").\n";
         return;
       }
 
-    // If FoundDecl is a constructor or destructor, we want to instead take the
-    // Decl of the corresponding class.
+      // If FoundDecl is a constructor or destructor, we want to instead take
+      // the Decl of the corresponding class.
       if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FoundDecl)) {
         FoundDecl = CtorDecl->getParent();
-    } else if (const auto *DtorDecl = dyn_cast<CXXDestructorDecl>(FoundDecl)) {
+      } else if (const auto *DtorDecl =
+                     dyn_cast<CXXDestructorDecl>(FoundDecl)) {
         FoundDecl = DtorDecl->getParent();
       }
-    *SpellingName = FoundDecl->getNameAsString();
-
-    AdditionalUSRFinder Finder(FoundDecl, Context, USRs);
-    Finder.Find();
+      SpellingNames.push_back(FoundDecl->getNameAsString());
+      AdditionalUSRFinder Finder(FoundDecl, Context);
+      std::vector<std::string> NextUSRBunch = Finder.Find();
+      USRList.push_back(NextUSRBunch);
+    }
   }
 
-  unsigned SymbolOffset;
-  std::string OldName;
-  std::string *SpellingName;
-  std::vector<std::string> *USRs;
+private:
+  const std::vector<unsigned> &SymbolOffsets;
+  const std::vector<std::string> &OldNames;
+  std::vector<std::string> &SpellingNames;
+  std::vector<std::vector<std::string>> &USRList;
 };
 
 std::unique_ptr<ASTConsumer> USRFindingAction::newASTConsumer() {
   std::unique_ptr<NamedDeclFindingConsumer> Consumer(
-      new NamedDeclFindingConsumer);
-  SpellingName = "";
-  Consumer->SymbolOffset = SymbolOffset;
-  Consumer->OldName = OldName;
-  Consumer->USRs = &USRs;
-  Consumer->SpellingName = &SpellingName;
+      new NamedDeclFindingConsumer(SymbolOffsets, OldNames, SpellingNames,
+                                   USRList));
   return std::move(Consumer);
 }
 
 } // namespace rename
 } // namespace clang

clang-rename/tool/ClangRename.cpp

int subcommandMain(bool isRenameAll, int argc, const char **argv) {
   // Check the arguments for correctness.
 
   if (NewNames.empty()) {
     errs() << "clang-rename: either -new-name or -input is required.\n\n";
     exit(1);
   }
 
   // Check if NewNames is a valid identifier in C++17.
-  for (const auto &NewName : NewNames) {
-    LangOptions Options;
-    Options.CPlusPlus = true;
-    Options.CPlusPlus1z = true;
-    IdentifierTable Table(Options);
+  for (const auto &NewName : NewNames) {
     auto NewNameTokKind = Table.get(NewName).getTokenID();
     if (!tok::isAnyIdentifier(NewNameTokKind)) {
       errs() << "ERROR: new name is not a valid identifier in C++17.\n\n";
       exit(1);
     }
   }
 
   if (!OldNames.empty() && OldNames.size() != NewNames.size()) {
     errs() << "clang-rename: number of old names (" << OldNames.size()
            << ") do not equal to number of new names (" << NewNames.size()
            << ").\n\n";
     cl::PrintHelpMessage();
     exit(1);
   }
 
   if (!SymbolOffsets.empty() && SymbolOffsets.size() != NewNames.size()) {
     errs() << "clang-rename: number of symbol offsets (" << SymbolOffsets.size()
            << ") do not equal to number of new names (" << NewNames.size()
            << ").\n\n";
     cl::PrintHelpMessage();
     exit(1);
   }
 
-  std::vector<std::vector<std::string>> USRList;
-  std::vector<std::string> PrevNames;
   auto Files = OP.getSourcePathList();
   tooling::RefactoringTool Tool(OP.getCompilations(), Files);
+
   unsigned Count = OldNames.size() ? OldNames.size() : SymbolOffsets.size();
+  std::vector<unsigned> SymbolOffsetsVector(Count, 0);
+  std::vector<std::string> OldNamesVector(Count, "");
   for (unsigned I = 0; I < Count; ++I) {
-    unsigned SymbolOffset = SymbolOffsets.empty() ? 0 : SymbolOffsets[I];
-    const std::string &OldName = OldNames.empty() ? std::string() : OldNames[I];
-
-    // Get the USRs.
-    rename::USRFindingAction USRAction(SymbolOffset, OldName);
-
-    // Find the USRs.
-    Tool.run(tooling::newFrontendActionFactory(&USRAction).get());
-    const auto &USRs = USRAction.getUSRs();
-    USRList.push_back(USRs);
-    const auto &PrevName = USRAction.getUSRSpelling();
-    PrevNames.push_back(PrevName);
-
-    if (PrevName.empty()) {
-      // An error should have already been printed.
-      exit(1);
-    }
+    if (!SymbolOffsets.empty()) {
+      SymbolOffsetsVector[I] = SymbolOffsets[I];
+    }
+    if (!OldNames.empty()) {
+      OldNamesVector[I] = OldNames[I];
+    }
 
-    if (PrintName) {
-      errs() << "clang-rename: found name: " << PrevName << '\n';
+  rename::USRFindingAction USRAction(SymbolOffsetsVector, OldNamesVector);
+  Tool.run(tooling::newFrontendActionFactory(&USRAction).get());
+  const std::vector<std::vector<std::string>> &USRList = USRAction.getUSRList();
+  const std::vector<std::string> &PrevNames = USRAction.getUSRSpellings();
+    for (const auto &PrevName : PrevNames) {
+      outs() << "clang-rename found name: " << PrevName << '\n';
     }
   }
 
   // Perform the renaming.
   rename::RenamingAction RenameAction(NewNames, PrevNames, USRList,
                                       Tool.getReplacements(), PrintLocations);
-  auto Factory = tooling::newFrontendActionFactory(&RenameAction);
+  std::unique_ptr<tooling::FrontendActionFactory> Factory =
+      tooling::newFrontendActionFactory(&RenameAction);
   int ExitCode;
 
   if (Inplace) {
     ExitCode = Tool.runAndSave(Factory.get());
   } else {
     ExitCode = Tool.run(Factory.get());
 
     if (!ExportFixes.empty()) {