| 1 |
//===--- InefficientVectorOperationCheck.cpp - clang-tidy------------------===// |
| 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-exception |
| 6 |
// |
| 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 |
|
| 16 |
using namespace clang::ast_matchers; |
| 17 |
|
| 18 |
namespace clang::tidy::performance { |
| 19 |
|
| 20 |
namespace { |
| 21 |
|
| 22 |
// Matcher names. Given the code: |
| 23 |
// |
| 24 |
// \code |
| 25 |
// void f() { |
| 26 |
// vector<T> v; |
| 27 |
// for (int i = 0; i < 10 + 1; ++i) { |
| 28 |
// v.push_back(i); |
| 29 |
// } |
| 30 |
// |
| 31 |
// SomeProto p; |
| 32 |
// for (int i = 0; i < 10 + 1; ++i) { |
| 33 |
// p.add_xxx(i); |
| 34 |
// } |
| 35 |
// } |
| 36 |
// \endcode |
| 37 |
// |
| 38 |
// The matcher names are bound to following parts of the AST: |
| 39 |
// - LoopCounterName: The entire for loop (as ForStmt). |
| 40 |
// - LoopParentName: The body of function f (as CompoundStmt). |
| 41 |
// - VectorVarDeclName: 'v' (as VarDecl). |
| 42 |
// - VectorVarDeclStmatName: The entire 'std::vector<T> v;' statement (as |
| 43 |
// DeclStmt). |
| 44 |
// - PushBackOrEmplaceBackCallName: 'v.push_back(i)' (as cxxMemberCallExpr). |
| 45 |
// - LoopInitVarName: 'i' (as VarDecl). |
| 46 |
// - LoopEndExpr: '10+1' (as Expr). |
| 47 |
// If EnableProto, the proto related names are bound to the following parts: |
| 48 |
// - ProtoVarDeclName: 'p' (as VarDecl). |
| 49 |
// - ProtoVarDeclStmtName: The entire 'SomeProto p;' statement (as DeclStmt). |
| 50 |
// - ProtoAddFieldCallName: 'p.add_xxx(i)' (as cxxMemberCallExpr). |
| 51 |
static const char LoopCounterName[] = "for_loop_counter"; |
| 52 |
static const char LoopParentName[] = "loop_parent"; |
| 53 |
static const char VectorVarDeclName[] = "vector_var_decl"; |
| 54 |
static const char VectorVarDeclStmtName[] = "vector_var_decl_stmt"; |
| 55 |
static const char PushBackOrEmplaceBackCallName[] = "append_call"; |
| 56 |
static const char ProtoVarDeclName[] = "proto_var_decl"; |
| 57 |
static const char ProtoVarDeclStmtName[] = "proto_var_decl_stmt"; |
| 58 |
static const char ProtoAddFieldCallName[] = "proto_add_field"; |
| 59 |
static const char LoopInitVarName[] = "loop_init_var"; |
| 60 |
static const char LoopEndExprName[] = "loop_end_expr"; |
| 61 |
static const char RangeLoopName[] = "for_range_loop"; |
| 62 |
|
| 63 |
ast_matchers::internal::Matcher<Expr> supportedContainerTypesMatcher() { |
| 64 |
return hasType(cxxRecordDecl(hasAnyName( |
| 65 |
"::std::vector", "::std::set", "::std::unordered_set", "::std::map", |
| 66 |
"::std::unordered_map", "::std::array", "::std::deque"))); |
| 67 |
} |
| 68 |
|
| 69 |
AST_MATCHER(Expr, hasSideEffects) { |
| 70 |
return Node.HasSideEffects(Finder->getASTContext()); |
| 71 |
} |
| 72 |
|
| 73 |
} // namespace |
| 74 |
|
| 75 |
InefficientVectorOperationCheck::InefficientVectorOperationCheck( |
| 76 |
StringRef Name, ClangTidyContext *Context) |
| 77 |
: ClangTidyCheck(Name, Context), |
| 78 |
VectorLikeClasses(utils::options::parseStringList( |
| 79 |
Options.get("VectorLikeClasses", "::std::vector"))), |
| 80 |
EnableProto(Options.getLocalOrGlobal("EnableProto", false)) {} |
| 81 |
|
| 82 |
void InefficientVectorOperationCheck::storeOptions( |
| 83 |
ClangTidyOptions::OptionMap &Opts) { |
| 84 |
Options.store(Opts, "VectorLikeClasses", |
| 85 |
utils::options::serializeStringList(VectorLikeClasses)); |
| 86 |
Options.store(Opts, "EnableProto", EnableProto); |
| 87 |
} |
| 88 |
|
| 89 |
void 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 calling |
| 115 |
// 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( |
| 130 |
hasLoopInit(LoopVarInit), |
| 131 |
hasCondition(binaryOperator( |
| 132 |
hasOperatorName("<"), hasLHS(RefersToLoopVar), |
| 133 |
hasRHS(expr(unless(hasDescendant(expr(RefersToLoopVar)))) |
| 134 |
.bind(LoopEndExprName)))), |
| 135 |
hasIncrement(unaryOperator(hasOperatorName("++"), |
| 136 |
hasUnaryOperand(RefersToLoopVar))), |
| 137 |
HasInterestingLoopBody, InInterestingCompoundStmt) |
| 138 |
.bind(LoopCounterName), |
| 139 |
this); |
| 140 |
|
| 141 |
// Match for-range loops: |
| 142 |
// for (const auto& E : data) { |
| 143 |
// v.push_back(...); |
| 144 |
// // Or: proto.add_xxx(...); |
| 145 |
// } |
| 146 |
// |
| 147 |
// FIXME: Support more complex range-expressions. |
| 148 |
Finder->addMatcher( |
| 149 |
cxxForRangeStmt( |
| 150 |
hasRangeInit( |
| 151 |
anyOf(declRefExpr(supportedContainerTypesMatcher()), |
| 152 |
memberExpr(hasObjectExpression(unless(hasSideEffects())), |
| 153 |
supportedContainerTypesMatcher()))), |
| 154 |
HasInterestingLoopBody, InInterestingCompoundStmt) |
| 155 |
.bind(RangeLoopName), |
| 156 |
this); |
| 157 |
} |
| 158 |
|
| 159 |
void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) { |
| 160 |
const auto VectorDecl = cxxRecordDecl(hasAnyName(VectorLikeClasses)); |
| 161 |
const auto AppendMethodDecl = |
| 162 |
cxxMethodDecl(hasAnyName("push_back", "emplace_back")); |
| 163 |
addMatcher(VectorDecl, VectorVarDeclName, VectorVarDeclStmtName, |
| 164 |
AppendMethodDecl, PushBackOrEmplaceBackCallName, Finder); |
| 165 |
|
| 166 |
if (EnableProto) { |
| 167 |
const auto ProtoDecl = |
| 168 |
cxxRecordDecl(isDerivedFrom("::proto2::MessageLite")); |
| 169 |
|
| 170 |
// A method's name starts with "add_" might not mean it's an add field |
| 171 |
// call; it could be the getter for a proto field of which the name starts |
| 172 |
// with "add_". So we exclude const methods. |
| 173 |
const auto AddFieldMethodDecl = |
| 174 |
cxxMethodDecl(matchesName("::add_"), unless(isConst())); |
| 175 |
addMatcher(ProtoDecl, ProtoVarDeclName, ProtoVarDeclStmtName, |
| 176 |
AddFieldMethodDecl, ProtoAddFieldCallName, Finder); |
| 177 |
} |
| 178 |
} |
| 179 |
|
| 180 |
void InefficientVectorOperationCheck::check( |
| 181 |
const MatchFinder::MatchResult &Result) { |
| 182 |
auto* Context = Result.Context; |
| 183 |
if (Context->getDiagnostics().hasUncompilableErrorOccurred()) |
| 184 |
return; |
| 185 |
|
| 186 |
const SourceManager &SM = *Result.SourceManager; |
| 187 |
const auto *VectorVarDecl = |
| 188 |
Result.Nodes.getNodeAs<VarDecl>(VectorVarDeclName); |
| 189 |
const auto *ForLoop = Result.Nodes.getNodeAs<ForStmt>(LoopCounterName); |
| 190 |
const auto *RangeLoop = |
| 191 |
Result.Nodes.getNodeAs<CXXForRangeStmt>(RangeLoopName); |
| 192 |
const auto *VectorAppendCall = |
| 193 |
Result.Nodes.getNodeAs<CXXMemberCallExpr>(PushBackOrEmplaceBackCallName); |
| 194 |
const auto *ProtoVarDecl = Result.Nodes.getNodeAs<VarDecl>(ProtoVarDeclName); |
| 195 |
const auto *ProtoAddFieldCall = |
| 196 |
Result.Nodes.getNodeAs<CXXMemberCallExpr>(ProtoAddFieldCallName); |
| 197 |
const auto *LoopEndExpr = Result.Nodes.getNodeAs<Expr>(LoopEndExprName); |
| 198 |
const auto *LoopParent = Result.Nodes.getNodeAs<CompoundStmt>(LoopParentName); |
| 199 |
|
| 200 |
const CXXMemberCallExpr *AppendCall = |
| 201 |
VectorAppendCall ? VectorAppendCall : ProtoAddFieldCall; |
| 202 |
assert(AppendCall && "no append call expression"); |
| 203 |
|
| 204 |
const Stmt *LoopStmt = ForLoop; |
| 205 |
if (!LoopStmt) |
| 206 |
LoopStmt = RangeLoop; |
| 207 |
|
| 208 |
const auto *TargetVarDecl = VectorVarDecl; |
| 209 |
if (!TargetVarDecl) |
| 210 |
TargetVarDecl = ProtoVarDecl; |
| 211 |
|
| 212 |
llvm::SmallPtrSet<const DeclRefExpr *, 16> AllVarRefs = |
| 213 |
utils::decl_ref_expr::allDeclRefExprs(*TargetVarDecl, *LoopParent, |
| 214 |
*Context); |
| 215 |
for (const auto *Ref : AllVarRefs) { |
| 216 |
// Skip cases where there are usages (defined as DeclRefExpr that refers |
| 217 |
// to "v") of vector variable / proto variable `v` before the for loop. We |
| 218 |
// consider these usages are operations causing memory preallocation (e.g. |
| 219 |
// "v.resize(n)", "v.reserve(n)"). |
| 220 |
// |
| 221 |
// FIXME: make it more intelligent to identify the pre-allocating |
| 222 |
// operations before the for loop. |
| 223 |
if (SM.isBeforeInTranslationUnit(Ref->getLocation(), |
| 224 |
LoopStmt->getBeginLoc())) { |
| 225 |
return; |
| 226 |
} |
| 227 |
} |
| 228 |
|
| 229 |
std::string PartialReserveStmt; |
| 230 |
if (VectorAppendCall != nullptr) { |
| 231 |
PartialReserveStmt = ".reserve"; |
| 232 |
} else { |
| 233 |
llvm::StringRef FieldName = ProtoAddFieldCall->getMethodDecl()->getName(); |
| 234 |
FieldName.consume_front("add_"); |
| 235 |
std::string MutableFieldName = ("mutable_" + FieldName).str(); |
| 236 |
PartialReserveStmt = "." + MutableFieldName + |
| 237 |
"()->Reserve"; // e.g., ".mutable_xxx()->Reserve" |
| 238 |
} |
| 239 |
|
| 240 |
llvm::StringRef VarName = Lexer::getSourceText( |
| 241 |
CharSourceRange::getTokenRange( |
| 242 |
AppendCall->getImplicitObjectArgument()->getSourceRange()), |
| 243 |
SM, Context->getLangOpts()); |
| 244 |
|
| 245 |
std::string ReserveSize; |
| 246 |
// Handle for-range loop cases. |
| 247 |
if (RangeLoop) { |
| 248 |
// Get the range-expression in a for-range statement represented as |
| 249 |
// `for (range-declarator: range-expression)`. |
| 250 |
StringRef RangeInitExpName = |
| 251 |
Lexer::getSourceText(CharSourceRange::getTokenRange( |
| 252 |
RangeLoop->getRangeInit()->getSourceRange()), |
| 253 |
SM, Context->getLangOpts()); |
| 254 |
ReserveSize = (RangeInitExpName + ".size()").str(); |
| 255 |
} else if (ForLoop) { |
| 256 |
// Handle counter-based loop cases. |
| 257 |
StringRef LoopEndSource = Lexer::getSourceText( |
| 258 |
CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), SM, |
| 259 |
Context->getLangOpts()); |
| 260 |
ReserveSize = std::string(LoopEndSource); |
| 261 |
} |
| 262 |
|
| 263 |
auto Diag = diag(AppendCall->getBeginLoc(), |
| 264 |
"%0 is called inside a loop; consider pre-allocating the " |
| 265 |
"container capacity before the loop") |
| 266 |
<< AppendCall->getMethodDecl()->getDeclName(); |
| 267 |
if (!ReserveSize.empty()) { |
| 268 |
std::string ReserveStmt = |
| 269 |
(VarName + PartialReserveStmt + "(" + ReserveSize + ");\n").str(); |
| 270 |
Diag << FixItHint::CreateInsertion(LoopStmt->getBeginLoc(), ReserveStmt); |
| 271 |
} |
| 272 |
} |
| 273 |
|
| 274 |
} // namespace clang::tidy::performance |