Index: clang-tools-extra/trunk/clang-tidy/performance/CMakeLists.txt =================================================================== --- clang-tools-extra/trunk/clang-tidy/performance/CMakeLists.txt +++ clang-tools-extra/trunk/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-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.h =================================================================== --- clang-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.h +++ clang-tools-extra/trunk/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-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.cpp =================================================================== --- clang-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.cpp +++ clang-tools-extra/trunk/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 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 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(LoopCounterName); + const auto *PushBackCall = + Result.Nodes.getNodeAs(PushBackCallName); + const auto *LoopEndExpr = Result.Nodes.getNodeAs(LoopEndExprName); + const auto *LoopParent = Result.Nodes.getNodeAs(LoopParentName); + const auto *VectorVarDecl = + Result.Nodes.getNodeAs(VectorVarDeclName); + + llvm::SmallPtrSet 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 Index: clang-tools-extra/trunk/clang-tidy/performance/PerformanceTidyModule.cpp =================================================================== --- clang-tools-extra/trunk/clang-tidy/performance/PerformanceTidyModule.cpp +++ clang-tools-extra/trunk/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: clang-tools-extra/trunk/docs/ReleaseNotes.rst =================================================================== --- clang-tools-extra/trunk/docs/ReleaseNotes.rst +++ clang-tools-extra/trunk/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. @@ -95,6 +95,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: clang-tools-extra/trunk/docs/clang-tidy/checks/list.rst =================================================================== --- clang-tools-extra/trunk/docs/clang-tidy/checks/list.rst +++ clang-tools-extra/trunk/docs/clang-tidy/checks/list.rst @@ -142,6 +142,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-tools-extra/trunk/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst =================================================================== --- clang-tools-extra/trunk/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst +++ clang-tools-extra/trunk/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst @@ -0,0 +1,20 @@ +.. 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. + +Currently, the check only detects a typical counter-based for loop with a single +statement in it, see below: + +.. 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: clang-tools-extra/trunk/test/clang-tidy/performance-inefficient-vector-operation.cpp =================================================================== --- clang-tools-extra/trunk/test/clang-tidy/performance-inefficient-vector-operation.cpp +++ clang-tools-extra/trunk/test/clang-tidy/performance-inefficient-vector-operation.cpp @@ -0,0 +1,183 @@ +// 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); + void resize(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(10); + for (int i = 0; i < 10; i++) + v.push_back(i); + // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called + } + { + std::vector v; + // CHECK-FIXES: v.reserve(10); + for (int i = 0; i < 10; ++i) + v.push_back(0); + // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called + } + { + std::vector v; + // CHECK-FIXES: v.reserve(5); + for (int i = 0; i < 5; ++i) { + v.push_back(i); + // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called + } + // CHECK-FIXES-NOT: v.reserve(10); + for (int i = 0; i < 10; ++i) { + // No fix for this loop as we encounter the prior loops. + v.push_back(i); + } + } + { + std::vector v; + std::vector v2; + v2.reserve(3); + // 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 + } + { + 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; + v.reserve(5); + // 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; + v.resize(5); + // CHECK-FIXES-NOT: v.reserve(10); + // There is a ref usage of v before the loop. + for (int i = 0; i < 10; ++i) { + v.push_back(i); + } + } + { + std::vector v; + v.push_back(0); + // CHECK-FIXES-NOT: v.reserve(10); + // There is a ref usage of v before the loop. + for (int i = 0; i < 10; ++i) { + v.push_back(i); + } + } + { + std::vector v; + f(v); + // CHECK-FIXES-NOT: v.reserve(10); + // There is a ref usage of v before the loop. + 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; + // CHECK-FIXES-NOT: v.reserve(i + 1); + // The loop end expression refers to the loop variable i. + for (int i = 0; i < i + 1; i++) + v.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; i < 10; ++k) { + v.push_back(t[i]); + } + } +}