274 lines · cpp
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "InefficientVectorOperationCheck.h"10#include "../utils/DeclRefExprUtils.h"11#include "../utils/OptionsUtils.h"12#include "clang/AST/ASTContext.h"13#include "clang/ASTMatchers/ASTMatchFinder.h"14#include "clang/Lex/Lexer.h"15 16using namespace clang::ast_matchers;17 18namespace clang::tidy::performance {19 20// Matcher names. Given the code:21//22// \code23// void f() {24// vector<T> v;25// for (int i = 0; i < 10 + 1; ++i) {26// v.push_back(i);27// }28//29// SomeProto p;30// for (int i = 0; i < 10 + 1; ++i) {31// p.add_xxx(i);32// }33// }34// \endcode35//36// The matcher names are bound to following parts of the AST:37// - LoopCounterName: The entire for loop (as ForStmt).38// - LoopParentName: The body of function f (as CompoundStmt).39// - VectorVarDeclName: 'v' (as VarDecl).40// - VectorVarDeclStmtName: The entire 'std::vector<T> v;' statement (as41// DeclStmt).42// - PushBackOrEmplaceBackCallName: 'v.push_back(i)' (as cxxMemberCallExpr).43// - LoopInitVarName: 'i' (as VarDecl).44// - LoopEndExpr: '10+1' (as Expr).45// If EnableProto, the proto related names are bound to the following parts:46// - ProtoVarDeclName: 'p' (as VarDecl).47// - ProtoVarDeclStmtName: The entire 'SomeProto p;' statement (as DeclStmt).48// - ProtoAddFieldCallName: 'p.add_xxx(i)' (as cxxMemberCallExpr).49static const char LoopCounterName[] = "for_loop_counter";50static const char LoopParentName[] = "loop_parent";51static const char VectorVarDeclName[] = "vector_var_decl";52static const char VectorVarDeclStmtName[] = "vector_var_decl_stmt";53static const char PushBackOrEmplaceBackCallName[] = "append_call";54static const char ProtoVarDeclName[] = "proto_var_decl";55static const char ProtoVarDeclStmtName[] = "proto_var_decl_stmt";56static const char ProtoAddFieldCallName[] = "proto_add_field";57static const char LoopInitVarName[] = "loop_init_var";58static const char LoopEndExprName[] = "loop_end_expr";59static const char RangeLoopName[] = "for_range_loop";60 61static ast_matchers::internal::Matcher<Expr> supportedContainerTypesMatcher() {62 return hasType(cxxRecordDecl(hasAnyName(63 "::std::vector", "::std::set", "::std::unordered_set", "::std::map",64 "::std::unordered_map", "::std::array", "::std::deque")));65}66 67namespace {68 69AST_MATCHER(Expr, hasSideEffects) {70 return Node.HasSideEffects(Finder->getASTContext());71}72 73} // namespace74 75InefficientVectorOperationCheck::InefficientVectorOperationCheck(76 StringRef Name, ClangTidyContext *Context)77 : ClangTidyCheck(Name, Context),78 VectorLikeClasses(utils::options::parseStringList(79 Options.get("VectorLikeClasses", "::std::vector"))),80 EnableProto(Options.get("EnableProto", false)) {}81 82void InefficientVectorOperationCheck::storeOptions(83 ClangTidyOptions::OptionMap &Opts) {84 Options.store(Opts, "VectorLikeClasses",85 utils::options::serializeStringList(VectorLikeClasses));86 Options.store(Opts, "EnableProto", EnableProto);87}88 89void InefficientVectorOperationCheck::addMatcher(90 const DeclarationMatcher &TargetRecordDecl, StringRef VarDeclName,91 StringRef VarDeclStmtName, const DeclarationMatcher &AppendMethodDecl,92 StringRef AppendCallName, MatchFinder *Finder) {93 const auto DefaultConstructorCall = cxxConstructExpr(94 hasType(TargetRecordDecl),95 hasDeclaration(cxxConstructorDecl(isDefaultConstructor())));96 const auto TargetVarDecl =97 varDecl(hasInitializer(DefaultConstructorCall)).bind(VarDeclName);98 const auto TargetVarDefStmt =99 declStmt(hasSingleDecl(equalsBoundNode(std::string(VarDeclName))))100 .bind(VarDeclStmtName);101 102 const auto AppendCallExpr =103 cxxMemberCallExpr(104 callee(AppendMethodDecl), on(hasType(TargetRecordDecl)),105 onImplicitObjectArgument(declRefExpr(to(TargetVarDecl))))106 .bind(AppendCallName);107 const auto AppendCall = expr(ignoringImplicit(AppendCallExpr));108 const auto LoopVarInit = declStmt(hasSingleDecl(109 varDecl(hasInitializer(ignoringParenImpCasts(integerLiteral(equals(0)))))110 .bind(LoopInitVarName)));111 const auto RefersToLoopVar = ignoringParenImpCasts(112 declRefExpr(to(varDecl(equalsBoundNode(LoopInitVarName)))));113 114 // Matchers for the loop whose body has only 1 push_back/emplace_back calling115 // statement.116 const auto HasInterestingLoopBody = hasBody(117 anyOf(compoundStmt(statementCountIs(1), has(AppendCall)), AppendCall));118 const auto InInterestingCompoundStmt =119 hasParent(compoundStmt(has(TargetVarDefStmt)).bind(LoopParentName));120 121 // Match counter-based for loops:122 // for (int i = 0; i < n; ++i) {123 // v.push_back(...);124 // // Or: proto.add_xxx(...);125 // }126 //127 // FIXME: Support more types of counter-based loops like decrement loops.128 Finder->addMatcher(129 forStmt(hasLoopInit(LoopVarInit),130 hasCondition(binaryOperator(131 hasOperatorName("<"), hasLHS(RefersToLoopVar),132 hasRHS(expr(unless(hasDescendant(expr(RefersToLoopVar))))133 .bind(LoopEndExprName)))),134 hasIncrement(unaryOperator(hasOperatorName("++"),135 hasUnaryOperand(RefersToLoopVar))),136 HasInterestingLoopBody, InInterestingCompoundStmt)137 .bind(LoopCounterName),138 this);139 140 // Match for-range loops:141 // for (const auto& E : data) {142 // v.push_back(...);143 // // Or: proto.add_xxx(...);144 // }145 //146 // FIXME: Support more complex range-expressions.147 Finder->addMatcher(148 cxxForRangeStmt(149 hasRangeInit(150 anyOf(declRefExpr(supportedContainerTypesMatcher()),151 memberExpr(hasObjectExpression(unless(hasSideEffects())),152 supportedContainerTypesMatcher()))),153 HasInterestingLoopBody, InInterestingCompoundStmt)154 .bind(RangeLoopName),155 this);156}157 158void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {159 const auto VectorDecl = cxxRecordDecl(hasAnyName(VectorLikeClasses));160 const auto AppendMethodDecl =161 cxxMethodDecl(hasAnyName("push_back", "emplace_back"));162 addMatcher(VectorDecl, VectorVarDeclName, VectorVarDeclStmtName,163 AppendMethodDecl, PushBackOrEmplaceBackCallName, Finder);164 165 if (EnableProto) {166 const auto ProtoDecl =167 cxxRecordDecl(isDerivedFrom("::proto2::MessageLite"));168 169 // A method's name starts with "add_" might not mean it's an add field170 // call; it could be the getter for a proto field of which the name starts171 // with "add_". So we exclude const methods.172 const auto AddFieldMethodDecl =173 cxxMethodDecl(matchesName("::add_"), unless(isConst()));174 addMatcher(ProtoDecl, ProtoVarDeclName, ProtoVarDeclStmtName,175 AddFieldMethodDecl, ProtoAddFieldCallName, Finder);176 }177}178 179void InefficientVectorOperationCheck::check(180 const MatchFinder::MatchResult &Result) {181 auto *Context = Result.Context;182 if (Context->getDiagnostics().hasUncompilableErrorOccurred())183 return;184 185 const SourceManager &SM = *Result.SourceManager;186 const auto *VectorVarDecl =187 Result.Nodes.getNodeAs<VarDecl>(VectorVarDeclName);188 const auto *ForLoop = Result.Nodes.getNodeAs<ForStmt>(LoopCounterName);189 const auto *RangeLoop =190 Result.Nodes.getNodeAs<CXXForRangeStmt>(RangeLoopName);191 const auto *VectorAppendCall =192 Result.Nodes.getNodeAs<CXXMemberCallExpr>(PushBackOrEmplaceBackCallName);193 const auto *ProtoVarDecl = Result.Nodes.getNodeAs<VarDecl>(ProtoVarDeclName);194 const auto *ProtoAddFieldCall =195 Result.Nodes.getNodeAs<CXXMemberCallExpr>(ProtoAddFieldCallName);196 const auto *LoopEndExpr = Result.Nodes.getNodeAs<Expr>(LoopEndExprName);197 const auto *LoopParent = Result.Nodes.getNodeAs<CompoundStmt>(LoopParentName);198 199 const CXXMemberCallExpr *AppendCall =200 VectorAppendCall ? VectorAppendCall : ProtoAddFieldCall;201 assert(AppendCall && "no append call expression");202 203 const Stmt *LoopStmt = ForLoop;204 if (!LoopStmt)205 LoopStmt = RangeLoop;206 207 const auto *TargetVarDecl = VectorVarDecl;208 if (!TargetVarDecl)209 TargetVarDecl = ProtoVarDecl;210 211 const llvm::SmallPtrSet<const DeclRefExpr *, 16> AllVarRefs =212 utils::decl_ref_expr::allDeclRefExprs(*TargetVarDecl, *LoopParent,213 *Context);214 for (const auto *Ref : AllVarRefs) {215 // Skip cases where there are usages (defined as DeclRefExpr that refers216 // to "v") of vector variable / proto variable `v` before the for loop. We217 // consider these usages are operations causing memory preallocation (e.g.218 // "v.resize(n)", "v.reserve(n)").219 //220 // FIXME: make it more intelligent to identify the pre-allocating221 // operations before the for loop.222 if (SM.isBeforeInTranslationUnit(Ref->getLocation(),223 LoopStmt->getBeginLoc())) {224 return;225 }226 }227 228 std::string PartialReserveStmt;229 if (VectorAppendCall != nullptr) {230 PartialReserveStmt = ".reserve";231 } else {232 llvm::StringRef FieldName = ProtoAddFieldCall->getMethodDecl()->getName();233 FieldName.consume_front("add_");234 const std::string MutableFieldName = ("mutable_" + FieldName).str();235 PartialReserveStmt = "." + MutableFieldName +236 "()->Reserve"; // e.g., ".mutable_xxx()->Reserve"237 }238 239 const llvm::StringRef VarName = Lexer::getSourceText(240 CharSourceRange::getTokenRange(241 AppendCall->getImplicitObjectArgument()->getSourceRange()),242 SM, Context->getLangOpts());243 244 std::string ReserveSize;245 // Handle for-range loop cases.246 if (RangeLoop) {247 // Get the range-expression in a for-range statement represented as248 // `for (range-declarator: range-expression)`.249 const StringRef RangeInitExpName =250 Lexer::getSourceText(CharSourceRange::getTokenRange(251 RangeLoop->getRangeInit()->getSourceRange()),252 SM, Context->getLangOpts());253 ReserveSize = (RangeInitExpName + ".size()").str();254 } else if (ForLoop) {255 // Handle counter-based loop cases.256 const StringRef LoopEndSource = Lexer::getSourceText(257 CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), SM,258 Context->getLangOpts());259 ReserveSize = std::string(LoopEndSource);260 }261 262 auto Diag = diag(AppendCall->getBeginLoc(),263 "%0 is called inside a loop; consider pre-allocating the "264 "container capacity before the loop")265 << AppendCall->getMethodDecl()->getDeclName();266 if (!ReserveSize.empty()) {267 const std::string ReserveStmt =268 (VarName + PartialReserveStmt + "(" + ReserveSize + ");\n").str();269 Diag << FixItHint::CreateInsertion(LoopStmt->getBeginLoc(), ReserveStmt);270 }271}272 273} // namespace clang::tidy::performance274