clang 20.0.0git
LoopWidening.cpp
Go to the documentation of this file.
1//===--- LoopWidening.cpp - Widen loops -------------------------*- C++ -*-===//
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/// This file contains functions which are used to widen loops. A loop may be
10/// widened to approximate the exit state(s), without analyzing every
11/// iteration. The widening is done by invalidating anything which might be
12/// modified by the body of the loop.
13///
14//===----------------------------------------------------------------------===//
15
16#include "clang/AST/AST.h"
20
21using namespace clang;
22using namespace ento;
23using namespace clang::ast_matchers;
24
25const auto MatchRef = "matchref";
26
27/// Return the loops condition Stmt or NULL if LoopStmt is not a loop
28static const Expr *getLoopCondition(const Stmt *LoopStmt) {
29 switch (LoopStmt->getStmtClass()) {
30 default:
31 return nullptr;
32 case Stmt::ForStmtClass:
33 return cast<ForStmt>(LoopStmt)->getCond();
34 case Stmt::WhileStmtClass:
35 return cast<WhileStmt>(LoopStmt)->getCond();
36 case Stmt::DoStmtClass:
37 return cast<DoStmt>(LoopStmt)->getCond();
38 case Stmt::CXXForRangeStmtClass:
39 return cast<CXXForRangeStmt>(LoopStmt)->getCond();
40 }
41}
42
43namespace clang {
44namespace ento {
45
47 const LocationContext *LCtx,
48 unsigned BlockCount, const Stmt *LoopStmt) {
49
50 assert((isa<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(LoopStmt)));
51
52 // Invalidate values in the current state.
53 // TODO Make this more conservative by only invalidating values that might
54 // be modified by the body of the loop.
55 // TODO Nested loops are currently widened as a result of the invalidation
56 // being so inprecise. When the invalidation is improved, the handling
57 // of nested loops will also need to be improved.
59 const StackFrameContext *STC = LCtx->getStackFrame();
60 MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
61 const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
62 MRMgr.getStackArgumentsRegion(STC),
63 MRMgr.getGlobalsRegion()};
65 for (auto *Region : Regions) {
66 ITraits.setTrait(Region,
68 }
69
70 // References should not be invalidated.
71 auto Matches = match(
73 varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))),
74 *LCtx->getDecl()->getBody(), ASTCtx);
75 for (BoundNodes Match : Matches) {
76 const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef);
77 assert(VD);
78 const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
79 ITraits.setTrait(VarMem,
81 }
82
83
84 // 'this' pointer is not an lvalue, we should not invalidate it. If the loop
85 // is located in a method, constructor or destructor, the value of 'this'
86 // pointer should remain unchanged. Ignore static methods, since they do not
87 // have 'this' pointers.
88 const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl());
89 if (CXXMD && CXXMD->isImplicitObjectMemberFunction()) {
90 const CXXThisRegion *ThisR =
91 MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC);
92 ITraits.setTrait(ThisR,
94 }
95
96 return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
97 BlockCount, LCtx, true, nullptr, nullptr,
98 &ITraits);
99}
100
101} // end namespace ento
102} // end namespace clang
const auto MatchRef
static const Expr * getLoopCondition(const Stmt *LoopStmt)
Return the loops condition Stmt or NULL if LoopStmt is not a loop.
This header contains the declarations of functions which are used to widen loops which do not otherwi...
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:187
ASTContext & getASTContext() const
Represents a static or instance method of a struct/union/class.
Definition: DeclCXX.h:2064
bool isImplicitObjectMemberFunction() const
[C++2b][dcl.fct]/p7 An implicit object member function is a non-static member function without an exp...
Definition: DeclCXX.cpp:2500
QualType getThisType() const
Return the type of the this pointer.
Definition: DeclCXX.cpp:2603
virtual Stmt * getBody() const
getBody - If this Decl represents a declaration for a body of code, such as a function or method defi...
Definition: DeclBase.h:1077
This represents one expression.
Definition: Expr.h:110
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
const StackFrameContext * getStackFrame() const
It represents a stack frame of the call stack (based on CallEvent).
Stmt - This represents one statement.
Definition: Stmt.h:84
StmtClass getStmtClass() const
Definition: Stmt.h:1358
Represents a variable declaration or definition.
Definition: Decl.h:879
Maps string IDs to AST nodes matched by parts of a matcher.
Definition: ASTMatchers.h:109
CXXThisRegion - Represents the region for the implicit 'this' parameter in a call to a C++ method.
Definition: MemRegion.h:1074
const StackArgumentsSpaceRegion * getStackArgumentsRegion(const StackFrameContext *STC)
getStackArgumentsRegion - Retrieve the memory region associated with function/method arguments of the...
Definition: MemRegion.cpp:914
const CXXThisRegion * getCXXThisRegion(QualType thisPointerTy, const LocationContext *LC)
getCXXThisRegion - Retrieve the [artificial] region associated with the parameter 'this'.
Definition: MemRegion.cpp:1300
const VarRegion * getVarRegion(const VarDecl *VD, const LocationContext *LC)
getVarRegion - Retrieve or create the memory region associated with a specified VarDecl and LocationC...
Definition: MemRegion.cpp:1002
const StackLocalsSpaceRegion * getStackLocalsRegion(const StackFrameContext *STC)
getStackLocalsRegion - Retrieve the memory region associated with the specified stack frame.
Definition: MemRegion.cpp:902
const GlobalsSpaceRegion * getGlobalsRegion(MemRegion::Kind K=MemRegion::GlobalInternalSpaceRegionKind, const CodeTextRegion *R=nullptr)
getGlobalsRegion - Retrieve the memory region associated with global variables.
Definition: MemRegion.cpp:926
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:97
Information about invalidation for a particular region/symbol.
Definition: MemRegion.h:1629
@ TK_PreserveContents
Tells that a region's contents is not changed.
Definition: MemRegion.h:1644
@ TK_EntireMemSpace
When applied to a MemSpaceRegion, indicates the entire memory space should be invalidated.
Definition: MemRegion.h:1654
void setTrait(SymbolRef Sym, InvalidationKinds IK)
Definition: MemRegion.cpp:1781
const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl
Matches variable declarations.
const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant
Matches AST nodes that have descendant AST nodes that match the provided matcher.
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
const AstTypeMatcher< ReferenceType > referenceType
Matches both lvalue and rvalue reference types.
internal::Matcher< T > findAll(const internal::Matcher< T > &Matcher)
Matches if the node or any descendant matches.
Definition: ASTMatchers.h:3568
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, const LocationContext *LCtx, unsigned BlockCount, const Stmt *LoopStmt)
Get the states that result from widening the loop.
The JSON file list parser is used to communicate input to InstallAPI.