clang  12.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 
21 using namespace clang;
22 using namespace ento;
23 using namespace clang::ast_matchers;
24 
25 const auto MatchRef = "matchref";
26 
27 /// Return the loops condition Stmt or NULL if LoopStmt is not a loop
28 static 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  }
39 }
40 
41 namespace clang {
42 namespace ento {
43 
45  const LocationContext *LCtx,
46  unsigned BlockCount, const Stmt *LoopStmt) {
47 
48  assert(isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
49  isa<DoStmt>(LoopStmt));
50 
51  // Invalidate values in the current state.
52  // TODO Make this more conservative by only invalidating values that might
53  // be modified by the body of the loop.
54  // TODO Nested loops are currently widened as a result of the invalidation
55  // being so inprecise. When the invalidation is improved, the handling
56  // of nested loops will also need to be improved.
57  ASTContext &ASTCtx = LCtx->getAnalysisDeclContext()->getASTContext();
58  const StackFrameContext *STC = LCtx->getStackFrame();
59  MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
60  const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
61  MRMgr.getStackArgumentsRegion(STC),
62  MRMgr.getGlobalsRegion()};
64  for (auto *Region : Regions) {
65  ITraits.setTrait(Region,
67  }
68 
69  // References should not be invalidated.
70  auto Matches = match(
72  varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))),
73  *LCtx->getDecl()->getBody(), ASTCtx);
74  for (BoundNodes Match : Matches) {
75  const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef);
76  assert(VD);
77  const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
78  ITraits.setTrait(VarMem,
80  }
81 
82 
83  // 'this' pointer is not an lvalue, we should not invalidate it. If the loop
84  // is located in a method, constructor or destructor, the value of 'this'
85  // pointer should remain unchanged. Ignore static methods, since they do not
86  // have 'this' pointers.
87  const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl());
88  if (CXXMD && !CXXMD->isStatic()) {
89  const CXXThisRegion *ThisR =
90  MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC);
91  ITraits.setTrait(ThisR,
93  }
94 
95  return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
96  BlockCount, LCtx, true, nullptr, nullptr,
97  &ITraits);
98 }
99 
100 } // end namespace ento
101 } // end namespace clang
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
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:1010
Stmt - This represents one statement.
Definition: Stmt.h:68
Information about invalidation for a particular region/symbol.
Definition: MemRegion.h:1516
QualType getThisType() const
Return the type of the this pointer.
Definition: DeclCXX.cpp:2398
const GlobalsSpaceRegion * getGlobalsRegion(MemRegion::Kind K=MemRegion::GlobalInternalSpaceRegionKind, const CodeTextRegion *R=nullptr)
getGlobalsRegion - Retrieve the memory region associated with global variables.
Definition: MemRegion.cpp:847
const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant
Matches AST nodes that have descendant AST nodes that match the provided matcher. ...
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
const StackArgumentsSpaceRegion * getStackArgumentsRegion(const StackFrameContext *STC)
getStackArgumentsRegion - Retrieve the memory region associated with function/method arguments of the...
Definition: MemRegion.cpp:834
Represents a variable declaration or definition.
Definition: Decl.h:820
ASTContext & getASTContext() const
void setTrait(SymbolRef Sym, InvalidationKinds IK)
Definition: MemRegion.cpp:1699
const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl
Matches variable declarations.
bool isStatic() const
Definition: DeclCXX.cpp:2033
CXXThisRegion - Represents the region for the implicit &#39;this&#39; parameter in a call to a C++ method...
Definition: MemRegion.h:1022
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:174
const StackLocalsSpaceRegion * getStackLocalsRegion(const StackFrameContext *STC)
getStackLocalsRegion - Retrieve the memory region associated with the specified stack frame...
Definition: MemRegion.cpp:821
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
internal::Matcher< T > findAll(const internal::Matcher< T > &Matcher)
Matches if the node or any descendant matches.
Definition: ASTMatchers.h:3121
When applied to a MemSpaceRegion, indicates the entire memory space should be invalidated.
Definition: MemRegion.h:1541
This represents one expression.
Definition: Expr.h:110
static const Expr * getLoopCondition(const Stmt *LoopStmt)
Return the loops condition Stmt or NULL if LoopStmt is not a loop.
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:926
Maps string IDs to AST nodes matched by parts of a matcher.
Definition: ASTMatchers.h:107
ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, const LocationContext *LCtx, unsigned BlockCount, const Stmt *LoopStmt)
Get the states that result from widening the loop.
Represents a static or instance method of a struct/union/class.
Definition: DeclCXX.h:1960
Tells that a region&#39;s contents is not changed.
Definition: MemRegion.h:1531
const CXXThisRegion * getCXXThisRegion(QualType thisPointerTy, const LocationContext *LC)
getCXXThisRegion - Retrieve the [artificial] region associated with the parameter &#39;this&#39;...
Definition: MemRegion.cpp:1213
Dataflow Directional Tag Classes.
StmtClass getStmtClass() const
Definition: Stmt.h:1148
const Decl * getDecl() const
const StackFrameContext * getStackFrame() const
It represents a stack frame of the call stack (based on CallEvent).
const auto MatchRef
AnalysisDeclContext * getAnalysisDeclContext() const
const AstTypeMatcher< ReferenceType > referenceType
Matches both lvalue and rvalue reference types.