hokein created this revision.
Herald added a subscriber: mgorny.
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.
https://reviews.llvm.org/D31757
Files:
clang-tidy/performance/CMakeLists.txt
clang-tidy/performance/InefficientVectorOperationCheck.cpp
clang-tidy/performance/InefficientVectorOperationCheck.h
clang-tidy/performance/PerformanceTidyModule.cpp
docs/clang-tidy/checks/list.rst
docs/clang-tidy/checks/performance-inefficient-vector-operation.rst
test/clang-tidy/performance-inefficient-vector-operation.cpp
Index: test/clang-tidy/performance-inefficient-vector-operation.cpp
===================================================================
--- /dev/null
+++ test/clang-tidy/performance-inefficient-vector-operation.cpp
@@ -0,0 +1,102 @@
+// RUN: %check_clang_tidy %s performance-inefficient-vector-operation %t -- -format-style=llvm --
+
+typedef int size_t;
+
+namespace std {
+template <class T>
+class vector {
+ public:
+ typedef T* iterator;
+ typedef const T* const_iterator;
+ typedef T& reference;
+ typedef const T& const_reference;
+ typedef size_t size_type;
+
+ explicit vector();
+ explicit vector(size_type n);
+
+ void push_back(const T& val);
+ void reserve(size_t n);
+ size_t size();
+ const_reference operator[] (size_type) const;
+ reference operator[] (size_type);
+};
+} // namespace std
+
+void f(std::vector<int>& t) {
+ {
+ std::vector<int> v;
+ // CHECK-FIXES: v.reserve(10);
+ for (int i = 0; i < 10; ++i)
+ v.push_back(i);
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: push_back is called inside a loop; consider pre-allocating the vector capacity before the loop
+ }
+ {
+ std::vector<int> v;
+ // CHECK-FIXES: v.reserve(t.size());
+ for (size_t i = 0; i < t.size(); ++i) {
+ v.push_back(t[i]);
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: push_back is called
+ }
+ }
+ {
+ std::vector<int> v;
+ // CHECK-FIXES: v.reserve(t.size() - 1);
+ for (size_t i = 0; i < t.size() - 1; ++i) {
+ v.push_back(t[i]);
+ } // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: push_back is called
+ }
+
+ // ---- Non-fixed Cases ----
+ {
+ std::vector<int> v;
+ v.reserve(20);
+ // CHECK-FIXES-NOT: v.reserve(10);
+ // There is a "reserve" call already.
+ for (int i = 0; i < 10; ++i) {
+ v.push_back(i);
+ }
+ }
+ {
+ std::vector<int> v(20);
+ // CHECK-FIXES-NOT: v.reserve(10);
+ // v is not constructed with default constructor.
+ for (int i = 0; i < 10; ++i) {
+ v.push_back(i);
+ }
+ }
+ {
+ std::vector<int> v;
+ // CHECK-FIXES-NOT: v.reserve(10);
+ // For-loop is not started with 0.
+ for (int i = 1; i < 10; ++i) {
+ v.push_back(i);
+ }
+ }
+ {
+ std::vector<int> v;
+ // CHECK-FIXES-NOT: v.reserve(t.size());
+ // v isn't referenced in for-loop body.
+ for (size_t i = 0; i < t.size(); ++i) {
+ t.push_back(i);
+ }
+ }
+ {
+ std::vector<int> v;
+ int k;
+ // CHECK-FIXES-NOT: v.reserve(10);
+ // For-loop isn't a fixable loop.
+ for (size_t i = 0; k < 10; ++i) {
+ v.push_back(t[i]);
+ }
+ }
+ {
+ std::vector<int> v;
+ int k;
+ // CHECK-FIXES-NOT: v.reserve(10);
+ // For-loop isn't a fixable loop.
+ for (size_t i = 0; i < 10; ++k) {
+ v.push_back(t[i]);
+ }
+ }
+}
Index: docs/clang-tidy/checks/performance-inefficient-vector-operation.rst
===================================================================
--- /dev/null
+++ docs/clang-tidy/checks/performance-inefficient-vector-operation.rst
@@ -0,0 +1,17 @@
+.. title:: clang-tidy - performance-inefficient-vector-operation
+
+performance-inefficient-vector-operation
+========================================
+
+Finds possible inefficient vector push_back operation that causes unnecessary
+memory reallocation.
+
+.. code-block:: c++
+
+ std::vector<int> v;
+ for (int i = 0; i < n; ++i) {
+ v.push_back(n);
+ // This will trigger the warning since the push_back may cause multiple
+ // memory reallocations in v. This can be avoid by inserting a reserve(n)
+ // statment before the for statment.
+ }
Index: docs/clang-tidy/checks/list.rst
===================================================================
--- docs/clang-tidy/checks/list.rst
+++ docs/clang-tidy/checks/list.rst
@@ -141,6 +141,7 @@
performance-for-range-copy
performance-implicit-cast-in-loop
performance-inefficient-string-concatenation
+ performance-inefficient-vector-operation
performance-type-promotion-in-math-fn
performance-unnecessary-copy-initialization
performance-unnecessary-value-param
Index: clang-tidy/performance/PerformanceTidyModule.cpp
===================================================================
--- clang-tidy/performance/PerformanceTidyModule.cpp
+++ 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 @@
"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>(
Index: clang-tidy/performance/InefficientVectorOperationCheck.h
===================================================================
--- /dev/null
+++ 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 vector operations in for-loop that causes
+/// unnecessary memory reallocation.
+///
+/// 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
Index: clang-tidy/performance/InefficientVectorOperationCheck.cpp
===================================================================
--- /dev/null
+++ clang-tidy/performance/InefficientVectorOperationCheck.cpp
@@ -0,0 +1,99 @@
+//===--- 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"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {
+ const auto VectorDecl = cxxRecordDecl(hasName("std::vector"));
+ const auto VectorDefaultConstructorCall = cxxConstructExpr(
+ hasType(VectorDecl),
+ hasDeclaration(cxxConstructorDecl(isDefaultConstructor())));
+ const auto VectorVarDefStmt =
+ declStmt(
+ hasSingleDecl(varDecl(hasInitializer(VectorDefaultConstructorCall))
+ .bind("vector_var_def")))
+ .bind("vector_var_stmt");
+ const auto ReserveCall = cxxMemberCallExpr(
+ callee(cxxMethodDecl(hasName("reserve"))), on(hasType(VectorDecl)));
+ const auto PushBackCall =
+ cxxMemberCallExpr(callee(cxxMethodDecl(hasName("push_back"))),
+ on(hasType(VectorDecl)))
+ .bind("push_back_call");
+ const auto LoopVarInit =
+ declStmt(hasSingleDecl(varDecl(hasInitializer(integerLiteral(equals(0))))
+ .bind("init_loop_var")));
+ const auto RefersToLoopVar = ignoringParenImpCasts(
+ declRefExpr(to(varDecl(equalsBoundNode("init_loop_var")))));
+
+ Finder->addMatcher(
+ forStmt(
+ hasLoopInit(LoopVarInit),
+ hasCondition(binaryOperator(hasOperatorName("<"),
+ hasLHS(RefersToLoopVar),
+ hasRHS(expr().bind("loop_end_expr")))),
+ hasIncrement(unaryOperator(hasOperatorName("++"),
+ hasUnaryOperand(RefersToLoopVar))),
+ hasBody(anyOf(compoundStmt(statementCountIs(1), has(PushBackCall)),
+ PushBackCall)),
+ hasParent(compoundStmt(unless(has(ReserveCall)),
+ has(VectorVarDefStmt))))
+ .bind("for_loop"),
+ this);
+}
+
+void InefficientVectorOperationCheck::check(
+ const MatchFinder::MatchResult &Result) {
+ const auto *ForLoop = Result.Nodes.getNodeAs<ForStmt>("for_loop");
+ const auto* PushBackCall =
+ Result.Nodes.getNodeAs<CXXMemberCallExpr>("push_back_call");
+ const auto* LoopEndExpr =
+ Result.Nodes.getNodeAs<Expr>("loop_end_expr");
+ const auto* VectorVarDef =
+ Result.Nodes.getNodeAs<VarDecl>("vector_var_def");
+
+ assert(ForLoop);
+ assert(PushBackCall);
+ assert(LoopEndExpr);
+
+ const auto *PushBackCallerObject =
+ llvm::dyn_cast<DeclRefExpr>(PushBackCall->getImplicitObjectArgument());
+ // Ignore for-loops in which the push_back isn't referenced by the targeted
+ // vector var definition.
+ if (!PushBackCallerObject || PushBackCallerObject->getDecl() != VectorVarDef)
+ return;
+
+ const auto* SM= Result.SourceManager;
+ 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
Index: clang-tidy/performance/CMakeLists.txt
===================================================================
--- clang-tidy/performance/CMakeLists.txt
+++ clang-tidy/performance/CMakeLists.txt
@@ -5,6 +5,7 @@
ForRangeCopyCheck.cpp
ImplicitCastInLoopCheck.cpp
InefficientStringConcatenationCheck.cpp
+ InefficientVectorOperationCheck.cpp
PerformanceTidyModule.cpp
TypePromotionInMathFnCheck.cpp
UnnecessaryCopyInitialization.cpp
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
