[clang-tidy] Add a clang-tidy check for possible inefficient vector operations

Summary:
The "performance-inefficient-vector-operation" check finds vector oprations in
for-loop statements which may cause multiple memory reallocations.

This is the first version, only detects typical for-loop:

```
std::vector<int> v;
for (int i = 0; i < n; ++i) {
  v.push_back(i);
}

// or

for (int i = 0; i < v2.size(); ++i) {
  v.push_back(v2[i]);
}
```

We can extend it to handle more cases like for-range loop in the future.

Reviewers: alexfh, aaron.ballman

Reviewed By: aaron.ballman

Subscribers: zaks.anna, Eugene.Zelenko, mgorny, cfe-commits, djasper

Differential Revision: https://reviews.llvm.org/D31757

git-svn-id: https://llvm.org/svn/llvm-project/clang-tools-extra/trunk@300534 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 189 insertions, 0 deletions

diff --git a/clang-tidy/performance/CMakeLists.txt b/clang-tidy/performance/CMakeLists.txt
index 8473f2c1..102e76ec 100644
--- a/clang-tidy/performance/CMakeLists.txt
+++ b/clang-tidy/performance/CMakeLists.txt
@@ -5,6 +5,7 @@ add_clang_library(clangTidyPerformanceModule
   ForRangeCopyCheck.cpp
   ImplicitCastInLoopCheck.cpp
   InefficientStringConcatenationCheck.cpp
+  InefficientVectorOperationCheck.cpp
   PerformanceTidyModule.cpp
   TypePromotionInMathFnCheck.cpp
   UnnecessaryCopyInitialization.cpp
diff --git a/clang-tidy/performance/InefficientVectorOperationCheck.cpp b/clang-tidy/performance/InefficientVectorOperationCheck.cpp
new file mode 100644
index 00000000..be9b1e31
--- /dev/null
+++ b/clang-tidy/performance/InefficientVectorOperationCheck.cpp
@@ -0,0 +1,149 @@
+//===--- InefficientVectorOperationCheck.cpp - clang-tidy------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "InefficientVectorOperationCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Lex/Lexer.h"
+#include "../utils/DeclRefExprUtils.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+namespace {
+
+// Matcher names. Given the code:
+//
+// \code
+// void f() {
+//   vector<T> v;
+//   for (int i = 0; i < 10 + 1; ++i) {
+//     v.push_back(i);
+//   }
+// }
+// \endcode
+//
+// The matcher names are bound to following parts of the AST:
+//   - LoopName: The entire for loop (as ForStmt).
+//   - LoopParentName: The body of function f (as CompoundStmt).
+//   - VectorVarDeclName: 'v' in  (as VarDecl).
+//   - VectorVarDeclStmatName: The entire 'std::vector<T> v;' statement (as
+//     DeclStmt).
+//   - PushBackCallName: 'v.push_back(i)' (as cxxMemberCallExpr).
+//   - LoopInitVarName: 'i' (as VarDecl).
+//   - LoopEndExpr: '10+1' (as Expr).
+static const char LoopCounterName[] = "for_loop_counter";
+static const char LoopParentName[] = "loop_parent";
+static const char VectorVarDeclName[] = "vector_var_decl";
+static const char VectorVarDeclStmtName[] = "vector_var_decl_stmt";
+static const char PushBackCallName[] = "push_back_call";
+
+static const char LoopInitVarName[] = "loop_init_var";
+static const char LoopEndExprName[] = "loop_end_expr";
+
+} // namespace
+
+void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {
+  const auto VectorDecl = cxxRecordDecl(hasName("::std::vector"));
+  const auto VectorDefaultConstructorCall = cxxConstructExpr(
+      hasType(VectorDecl),
+      hasDeclaration(cxxConstructorDecl(isDefaultConstructor())));
+  const auto VectorVarDecl =
+      varDecl(hasInitializer(VectorDefaultConstructorCall))
+          .bind(VectorVarDeclName);
+  const auto PushBackCallExpr =
+      cxxMemberCallExpr(
+          callee(cxxMethodDecl(hasName("push_back"))), on(hasType(VectorDecl)),
+          onImplicitObjectArgument(declRefExpr(to(VectorVarDecl))))
+          .bind(PushBackCallName);
+  const auto PushBackCall =
+      expr(anyOf(PushBackCallExpr, exprWithCleanups(has(PushBackCallExpr))));
+  const auto VectorVarDefStmt =
+      declStmt(hasSingleDecl(equalsBoundNode(VectorVarDeclName)))
+          .bind(VectorVarDeclStmtName);
+
+  const auto LoopVarInit =
+      declStmt(hasSingleDecl(varDecl(hasInitializer(integerLiteral(equals(0))))
+                                 .bind(LoopInitVarName)));
+  const auto RefersToLoopVar = ignoringParenImpCasts(
+      declRefExpr(to(varDecl(equalsBoundNode(LoopInitVarName)))));
+
+  // Match counter-based for loops:
+  //  for (int i = 0; i < n; ++i) { v.push_back(...); }
+  //
+  // FIXME: Support more types of counter-based loops like decrement loops.
+  Finder->addMatcher(
+      forStmt(
+          hasLoopInit(LoopVarInit),
+          hasCondition(binaryOperator(
+              hasOperatorName("<"), hasLHS(RefersToLoopVar),
+              hasRHS(expr(unless(hasDescendant(expr(RefersToLoopVar))))
+                         .bind(LoopEndExprName)))),
+          hasIncrement(unaryOperator(hasOperatorName("++"),
+                                     hasUnaryOperand(RefersToLoopVar))),
+          hasBody(anyOf(compoundStmt(statementCountIs(1), has(PushBackCall)),
+                        PushBackCall)),
+          hasParent(compoundStmt(has(VectorVarDefStmt)).bind(LoopParentName)))
+          .bind(LoopCounterName),
+      this);
+}
+
+void InefficientVectorOperationCheck::check(
+    const MatchFinder::MatchResult &Result) {
+  if (Result.Context->getDiagnostics().hasUncompilableErrorOccurred())
+    return;
+
+  const SourceManager &SM = *Result.SourceManager;
+  const auto *ForLoop = Result.Nodes.getNodeAs<ForStmt>(LoopCounterName);
+  const auto *PushBackCall =
+      Result.Nodes.getNodeAs<CXXMemberCallExpr>(PushBackCallName);
+  const auto *LoopEndExpr = Result.Nodes.getNodeAs<Expr>(LoopEndExprName);
+  const auto *LoopParent = Result.Nodes.getNodeAs<CompoundStmt>(LoopParentName);
+  const auto *VectorVarDecl =
+      Result.Nodes.getNodeAs<VarDecl>(VectorVarDeclName);
+
+  llvm::SmallPtrSet<const DeclRefExpr *, 16> AllVectorVarRefs =
+      utils::decl_ref_expr::allDeclRefExprs(*VectorVarDecl, *LoopParent,
+                                            *Result.Context);
+  for (const auto *Ref : AllVectorVarRefs) {
+    // Skip cases where there are usages (defined as DeclRefExpr that refers to
+    // "v") of vector variable `v` before the for loop. We consider these usages
+    // are operations causing memory preallocation (e.g. "v.resize(n)",
+    // "v.reserve(n)").
+    //
+    // FIXME: make it more intelligent to identify the pre-allocating operations
+    // before the for loop.
+    if (SM.isBeforeInTranslationUnit(Ref->getLocation(),
+                                     ForLoop->getLocStart())) {
+      return;
+    }
+  }
+
+  llvm::StringRef LoopEndSource = clang::Lexer::getSourceText(
+      CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), SM,
+      clang::LangOptions());
+  llvm::StringRef VectorVarName = clang::Lexer::getSourceText(
+      CharSourceRange::getTokenRange(
+          PushBackCall->getImplicitObjectArgument()->getSourceRange()),
+      SM, clang::LangOptions());
+  std::string ReserveStmt =
+      (VectorVarName + ".reserve(" + LoopEndSource + ");\n").str();
+
+  diag(PushBackCall->getLocStart(),
+       "'push_back' is called inside a loop; "
+       "consider pre-allocating the vector capacity before the loop.")
+      << FixItHint::CreateInsertion(ForLoop->getLocStart(), ReserveStmt);
+}
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
diff --git a/clang-tidy/performance/InefficientVectorOperationCheck.h b/clang-tidy/performance/InefficientVectorOperationCheck.h
new file mode 100644
index 00000000..246f8c0b
--- /dev/null
+++ b/clang-tidy/performance/InefficientVectorOperationCheck.h
@@ -0,0 +1,36 @@
+//===--- InefficientVectorOperationCheck.h - clang-tidy----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENT_VECTOR_OPERATION_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENT_VECTOR_OPERATION_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+/// Finds possible inefficient `std::vector` operations (e.g. `push_back`) in
+/// for loops that may cause unnecessary memory reallocations.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-vector-operation.html
+class InefficientVectorOperationCheck : public ClangTidyCheck {
+public:
+  InefficientVectorOperationCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENT_VECTOR_OPERATION_H
diff --git a/clang-tidy/performance/PerformanceTidyModule.cpp b/clang-tidy/performance/PerformanceTidyModule.cpp
index 90255c5e..072f817e 100644
--- a/clang-tidy/performance/PerformanceTidyModule.cpp
+++ b/clang-tidy/performance/PerformanceTidyModule.cpp
@@ -14,6 +14,7 @@
 #include "ForRangeCopyCheck.h"
 #include "ImplicitCastInLoopCheck.h"
 #include "InefficientStringConcatenationCheck.h"
+#include "InefficientVectorOperationCheck.h"
 #include "TypePromotionInMathFnCheck.h"
 #include "UnnecessaryCopyInitialization.h"
 #include "UnnecessaryValueParamCheck.h"
@@ -33,6 +34,8 @@ public:
         "performance-implicit-cast-in-loop");
     CheckFactories.registerCheck<InefficientStringConcatenationCheck>(
         "performance-inefficient-string-concatenation");
+    CheckFactories.registerCheck<InefficientVectorOperationCheck>(
+        "performance-inefficient-vector-operation");
     CheckFactories.registerCheck<TypePromotionInMathFnCheck>(
         "performance-type-promotion-in-math-fn");
     CheckFactories.registerCheck<UnnecessaryCopyInitialization>(