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 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 `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 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("for_loop"); + const auto* PushBackCall = + Result.Nodes.getNodeAs("push_back_call"); + const auto* LoopEndExpr = + Result.Nodes.getNodeAs("loop_end_expr"); + const auto* VectorVarDef = + Result.Nodes.getNodeAs("vector_var_def"); + + assert(ForLoop); + assert(PushBackCall); + assert(LoopEndExpr); + + const auto *PushBackCallerObject = + llvm::dyn_cast(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/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( "performance-inefficient-string-concatenation"); + CheckFactories.registerCheck( + "performance-inefficient-vector-operation"); CheckFactories.registerCheck( "performance-type-promotion-in-math-fn"); CheckFactories.registerCheck( Index: docs/ReleaseNotes.rst =================================================================== --- docs/ReleaseNotes.rst +++ docs/ReleaseNotes.rst @@ -62,7 +62,7 @@ Finds modification of the ``std`` or ``posix`` namespace. -- Improved `cppcoreguidelines-no-malloc +- Improved `cppcoreguidelines-no-malloc `_ check Allow custom memory management functions to be considered as well. @@ -90,6 +90,12 @@ - Support clang-formatting of the code around applied fixes (``-format-style`` command-line option). +- New `performance-inefficient-vector-operation + `_ check + + Finds possible inefficient vector operations in for-loops that may cause + unnecessary memory reallocations. + Improvements to include-fixer ----------------------------- 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: 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 `std::vector` operations (e.g. `push_back`) that may +cause unnecessary memory reallocations. + +.. code-block:: c++ + + std::vector 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: 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 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& t) { + { + std::vector 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 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 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 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 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 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 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 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 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]); + } + } +}