clang  10.0.0svn
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(findAll(stmt(hasDescendant(varDecl(hasType(referenceType())).bind(MatchRef)))),
71  *LCtx->getDecl()->getBody(), ASTCtx);
72  for (BoundNodes Match : Matches) {
73  const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef);
74  assert(VD);
75  const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
76  ITraits.setTrait(VarMem,
78  }
79 
80 
81  // 'this' pointer is not an lvalue, we should not invalidate it. If the loop
82  // is located in a method, constructor or destructor, the value of 'this'
83  // pointer should remain unchanged. Ignore static methods, since they do not
84  // have 'this' pointers.
85  const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl());
86  if (CXXMD && !CXXMD->isStatic()) {
87  const CXXThisRegion *ThisR =
88  MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC);
89  ITraits.setTrait(ThisR,
91  }
92 
93  return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
94  BlockCount, LCtx, true, nullptr, nullptr,
95  &ITraits);
96 }
97 
98 } // end namespace ento
99 } // 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:986
Stmt - This represents one statement.
Definition: Stmt.h:66
Information about invalidation for a particular region/symbol.
Definition: MemRegion.h:1445
QualType getThisType() const
Return the type of the this pointer.
Definition: DeclCXX.cpp:2310
const GlobalsSpaceRegion * getGlobalsRegion(MemRegion::Kind K=MemRegion::GlobalInternalSpaceRegionKind, const CodeTextRegion *R=nullptr)
getGlobalsRegion - Retrieve the memory region associated with global variables.
Definition: MemRegion.cpp:767
const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant
Matches AST nodes that have descendant AST nodes that match the provided matcher. ...
const StackArgumentsSpaceRegion * getStackArgumentsRegion(const StackFrameContext *STC)
getStackArgumentsRegion - Retrieve the memory region associated with function/method arguments of the...
Definition: MemRegion.cpp:754
Represents a variable declaration or definition.
Definition: Decl.h:827
ASTContext & getASTContext() const
void setTrait(SymbolRef Sym, InvalidationKinds IK)
Definition: MemRegion.cpp:1585
const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl
Matches variable declarations.
bool isStatic() const
Definition: DeclCXX.cpp:1968
CXXThisRegion - Represents the region for the implicit &#39;this&#39; parameter in a call to a C++ method...
Definition: MemRegion.h:973
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:160
const StackLocalsSpaceRegion * getStackLocalsRegion(const StackFrameContext *STC)
getStackLocalsRegion - Retrieve the memory region associated with the specified stack frame...
Definition: MemRegion.cpp:741
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:2886
When applied to a MemSpaceRegion, indicates the entire memory space should be invalidated.
Definition: MemRegion.h:1470
This represents one expression.
Definition: Expr.h:108
static const Expr * getLoopCondition(const Stmt *LoopStmt)
Return the loops condition Stmt or NULL if LoopStmt is not a loop.
Maps string IDs to AST nodes matched by parts of a matcher.
Definition: ASTMatchers.h:103
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:1905
Tells that a region&#39;s contents is not changed.
Definition: MemRegion.h:1460
const CXXThisRegion * getCXXThisRegion(QualType thisPointerTy, const LocationContext *LC)
getCXXThisRegion - Retrieve the [artificial] region associated with the parameter &#39;this&#39;...
Definition: MemRegion.cpp:1100
Dataflow Directional Tag Classes.
const VarRegion * getVarRegion(const VarDecl *D, const LocationContext *LC)
getVarRegion - Retrieve or create the memory region associated with a specified VarDecl and LocationC...
Definition: MemRegion.cpp:845
StmtClass getStmtClass() const
Definition: Stmt.h:1097
const Decl * getDecl() const
const StackFrameContext * getStackFrame() const
const auto MatchRef
AnalysisDeclContext * getAnalysisDeclContext() const
const AstTypeMatcher< ReferenceType > referenceType
Matches both lvalue and rvalue reference types.