clang: lib/StaticAnalyzer/Core/LoopUnrolling.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
20#include
21
22using namespace clang;
23using namespace ento;
25
27
28namespace {
29struct LoopState {
30private:
31 enum Kind { Normal, Unrolled } K;
32 const Stmt *LoopStmt;
34 unsigned maxStep;
36 : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {}
37
38public:
40 unsigned N) {
41 return LoopState(Normal, S, L, N);
42 }
44 unsigned N) {
45 return LoopState(Unrolled, S, L, N);
46 }
47 bool isUnrolled() const { return K == Unrolled; }
48 unsigned getMaxStep() const { return maxStep; }
49 const Stmt *getLoopStmt() const { return LoopStmt; }
50 const LocationContext *getLocationContext() const { return LCtx; }
51 bool operator==(const LoopState &X) const {
52 return K == X.K && LoopStmt == X.LoopStmt;
53 }
54 void Profile(llvm::FoldingSetNodeID &ID) const {
55 ID.AddInteger(K);
56 ID.AddPointer(LoopStmt);
57 ID.AddPointer(LCtx);
58 ID.AddInteger(maxStep);
59 }
60};
61}
62
63
64
65
66
67
68
70
72namespace ento {
73
75 return isa_and_nonnull<ForStmt, WhileStmt, DoStmt>(S);
76}
77
79 auto LS = State->get();
80 if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)
81 State = State->set(LS.getTail());
82 return State;
83}
84
86 StringRef RefName) {
88 anyOf(hasOperatorName("<"), hasOperatorName(">"),
89 hasOperatorName("<="), hasOperatorName(">="),
90 hasOperatorName("!=")),
91 hasEitherOperand(ignoringParenImpCasts(
93 .bind(RefName))),
94 hasEitherOperand(
95 ignoringParenImpCasts(integerLiteral().bind("boundNum"))))
96 .bind("conditionOperator");
97}
98
99static internal::Matcher
103 hasUnaryOperand(ignoringParenImpCasts(
106 hasLHS(ignoringParenImpCasts(
108}
109
110static internal::Matcher
111callByRef(internal::Matcher VarNodeMatcher) {
112 return callExpr(forEachArgumentWithParam(
115}
116
117static internal::Matcher
121 hasInitializer(anyOf(
124}
125
126static internal::Matcher
127getAddrTo(internal::Matcher VarNodeMatcher) {
129 hasOperatorName("&"),
131}
132
136
137
138
140 callByRef(equalsBoundNode(std::string(NodeName))),
141 getAddrTo(equalsBoundNode(std::string(NodeName))),
142 assignedToRef(equalsBoundNode(std::string(NodeName))))));
143}
144
147 hasCondition(simpleCondition("initVarName", "initVarRef")),
148
149 hasLoopInit(
151 varDecl(allOf(hasInitializer(ignoringParenImpCasts(
153 equalsBoundNode("initVarName"))))),
155 equalsBoundNode("initVarName"))))),
156 hasRHS(ignoringParenImpCasts(
158
159
161 anyOf(hasOperatorName("++"), hasOperatorName("--")),
163 to(varDecl(allOf(equalsBoundNode("initVarName"),
164 hasType(isInteger())))))))),
166 .bind("forLoop");
167}
168
170
171
175 const auto *MD = cast(D);
176 assert(MD && MD->getParent()->isLambda() &&
177 "Captured variable should only be seen while evaluating a lambda");
179
180
181 llvm::DenseMap<const ValueDecl *, FieldDecl *> LambdaCaptureFields;
182 FieldDecl *LambdaThisCaptureField;
183 LambdaCXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
184
185
187 assert(VD);
188 const FieldDecl *FD = LambdaCaptureFields[VD];
189 assert(FD && "Captured variable without a corresponding field");
191}
192
194 if (const DeclStmt *DS = dyn_cast(S)) {
195 for (const Decl *D : DS->decls()) {
196
198 return true;
199 }
200 }
201 return false;
202}
203
204
205
206
207
208
211 assert(VD);
212
214 return true;
215
216 const bool IsRefParamOrCapture =
218
222 return true;
223
225
226
228 if (!S) {
230 continue;
231 }
232
234 return false;
235 }
236
237 if (const auto *SS = dyn_cast(S)) {
238 if (const auto *CST = dyn_cast(SS->getBody())) {
239 for (const Stmt *CB : CST->body()) {
241 return false;
242 }
243 }
244 }
245
246
247
250
251 auto Match =
254 *S, ASTCtx);
255 if (!Match.empty())
256 return true;
257
259 }
260
261
262 if (IsRefParamOrCapture)
263 return false;
264
265 llvm_unreachable("Reached root without finding the declaration of VD");
266}
267
270
272 return false;
273
274
275
277 if (Matches.empty())
278 return false;
279
280 const auto *CounterVarRef = Matches[0].getNodeAs<DeclRefExpr>("initVarRef");
281 llvm::APInt BoundNum =
282 Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();
283 llvm::APInt InitNum =
284 Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();
285 auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");
286 unsigned MaxWidth = std::max(InitNum.getBitWidth(), BoundNum.getBitWidth());
287
288 InitNum = InitNum.zext(MaxWidth);
289 BoundNum = BoundNum.zext(MaxWidth);
290
291 if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
292 maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
293 else
294 maxStep = (BoundNum - InitNum).abs().getZExtValue();
295
296
298}
299
301 const Stmt *S = nullptr;
304 return true;
305
307 if (std::optional BE = P.getAs<BlockEntrance>())
308 S = BE->getBlock()->getTerminatorStmt();
309
310 if (S == LoopStmt)
311 return false;
312
314 }
315
316 llvm_unreachable("Reached root without encountering the previous step");
317}
318
319
321 ExplodedNode *Pred, unsigned maxVisitOnPath) {
322 auto State = Pred->getState();
324
326 return State;
327
328 auto LS = State->get();
329 if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&
330 LCtx == LS.getHead().getLocationContext()) {
331 if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) {
332 State = State->set(LS.getTail());
333 State = State->add(
334 LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
335 }
336 return State;
337 }
338 unsigned maxStep;
340 State = State->add(
341 LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
342 return State;
343 }
344
345 unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep());
346
347 unsigned innerMaxStep = maxStep * outerStep;
349 State = State->add(
350 LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
351 else
352 State = State->add(
353 LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep));
354 return State;
355}
356
358 auto LS = State->get();
359 if (LS.isEmpty() || !LS.getHead().isUnrolled())
360 return false;
361 return true;
362}
363}
364}
static const int MAXIMUM_STEP_UNROLLED
This header contains the declarations of functions which are used to decide which loops should be com...
#define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable list type NameTy, suitable for placement into the ProgramState.
__DEVICE__ long long abs(long long __n)
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
ASTContext & getASTContext() const
A builtin binary operation expression such as "x + y" or "x <= y".
Represents a C++ struct/union/class.
void getCaptureFields(llvm::DenseMap< const ValueDecl *, FieldDecl * > &Captures, FieldDecl *&ThisCapture) const
For a closure type, retrieve the mapping from captured variables and this to the non-static data memb...
DeclContext * getParent()
getParent - Returns the containing DeclContext.
A reference to a declared variable, function, enum, etc.
bool refersToEnclosingVariableOrCapture() const
Does this DeclRefExpr refer to an enclosing local or a captured variable?
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Decl - This represents one declaration (or definition), e.g.
virtual Decl * getCanonicalDecl()
Retrieves the "canonical" declaration of the given declaration.
Represents a member of a struct/union/class.
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
const Decl * getDecl() const
LLVM_ATTRIBUTE_RETURNS_NONNULL AnalysisDeclContext * getAnalysisDeclContext() const
Stmt - This represents one statement.
bool isReferenceType() const
Represents a variable declaration or definition.
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
const ProgramStateRef & getState() const
const Stmt * getStmtForDiagnostics() const
If the node's program point corresponds to a statement, retrieve that statement.
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
const LocationContext * getLocationContext() const
ExplodedNode * getFirstPred()
unsigned succ_size() const
const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl
Matches variable declarations.
const internal::VariadicDynCastAllOfMatcher< Stmt, DeclRefExpr > declRefExpr
Matches expressions that refer to declarations.
const internal::VariadicOperatorMatcherFunc< 1, 1 > unless
Matches if the provided matcher does not match.
const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant
Matches AST nodes that have descendant AST nodes that match the provided matcher.
const internal::VariadicDynCastAllOfMatcher< Decl, ParmVarDecl > parmVarDecl
Matches parameter variable declarations.
const internal::VariadicDynCastAllOfMatcher< Stmt, ReturnStmt > returnStmt
Matches return statements.
const internal::VariadicDynCastAllOfMatcher< Stmt, CallExpr > callExpr
Matches call expressions.
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
const internal::VariadicDynCastAllOfMatcher< Stmt, UnaryOperator > unaryOperator
Matches unary operator expressions.
const internal::VariadicDynCastAllOfMatcher< Stmt, InitListExpr > initListExpr
Matches init list expressions.
const internal::VariadicDynCastAllOfMatcher< Stmt, ForStmt > forStmt
Matches for statements.
const internal::VariadicDynCastAllOfMatcher< Stmt, GotoStmt > gotoStmt
Matches goto statements.
const internal::VariadicDynCastAllOfMatcher< Stmt, BinaryOperator > binaryOperator
Matches binary operator expressions.
const internal::ArgumentAdaptingMatcherFunc< internal::HasMatcher > has
Matches AST nodes that have child AST nodes that match the provided matcher.
const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> allOf
Matches if all given matchers match.
const internal::VariadicDynCastAllOfMatcher< Stmt, SwitchStmt > switchStmt
Matches switch statements.
const AstTypeMatcher< ReferenceType > referenceType
Matches both lvalue and rvalue reference types.
const internal::VariadicDynCastAllOfMatcher< Stmt, IntegerLiteral > integerLiteral
Matches integer literals of all sizes / encodings, e.g.
internal::PolymorphicMatcher< internal::HasDeclarationMatcher, void(internal::HasDeclarationSupportedTypes), internal::Matcher< Decl > > hasDeclaration(const internal::Matcher< Decl > &InnerMatcher)
Matches a node if the declaration associated with that node matches the given matcher.
const internal::VariadicDynCastAllOfMatcher< Stmt, DeclStmt > declStmt
Matches declaration statements.
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> anyOf
Matches if any of the given matchers matches.
const internal::VariadicAllOfMatcher< QualType > qualType
Matches QualTypes in the clang AST.
static bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt)
static internal::Matcher< Stmt > simpleCondition(StringRef BindName, StringRef RefName)
static internal::Matcher< Stmt > hasSuspiciousStmt(StringRef NodeName)
static internal::Matcher< Stmt > callByRef(internal::Matcher< Decl > VarNodeMatcher)
static internal::Matcher< Stmt > forLoopMatcher()
static bool isPossiblyEscaped(ExplodedNode *N, const DeclRefExpr *DR)
static internal::Matcher< Stmt > getAddrTo(internal::Matcher< Decl > VarNodeMatcher)
static bool isLoopStmt(const Stmt *S)
ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State)
Updates the given ProgramState.
static bool isFoundInStmt(const Stmt *S, const VarDecl *VD)
static internal::Matcher< Stmt > assignedToRef(internal::Matcher< Decl > VarNodeMatcher)
static bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, ExplodedNode *Pred, unsigned &maxStep)
bool isUnrolledState(ProgramStateRef State)
Returns if the given State indicates that is inside a completely unrolled loop.
static bool isCapturedByReference(ExplodedNode *N, const DeclRefExpr *DR)
ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, ExplodedNode *Pred, unsigned maxVisitOnPath)
Updates the stack of loops contained by the ProgramState.
static internal::Matcher< Stmt > changeIntBoundNode(internal::Matcher< Decl > VarNodeMatcher)
The JSON file list parser is used to communicate input to InstallAPI.
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)