clang  8.0.0svn
LoopWidening.cpp
Go to the documentation of this file.
1 //===--- LoopWidening.cpp - Widen loops -------------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// This file contains functions which are used to widen loops. A loop may be
11 /// widened to approximate the exit state(s), without analyzing every
12 /// iteration. The widening is done by invalidating anything which might be
13 /// modified by the body of the loop.
14 ///
15 //===----------------------------------------------------------------------===//
16 
17 #include "clang/AST/AST.h"
21 
22 using namespace clang;
23 using namespace ento;
24 using namespace clang::ast_matchers;
25 
26 const auto MatchRef = "matchref";
27 
28 /// Return the loops condition Stmt or NULL if LoopStmt is not a loop
29 static const Expr *getLoopCondition(const Stmt *LoopStmt) {
30  switch (LoopStmt->getStmtClass()) {
31  default:
32  return nullptr;
33  case Stmt::ForStmtClass:
34  return cast<ForStmt>(LoopStmt)->getCond();
35  case Stmt::WhileStmtClass:
36  return cast<WhileStmt>(LoopStmt)->getCond();
37  case Stmt::DoStmtClass:
38  return cast<DoStmt>(LoopStmt)->getCond();
39  }
40 }
41 
42 namespace clang {
43 namespace ento {
44 
46  const LocationContext *LCtx,
47  unsigned BlockCount, const Stmt *LoopStmt) {
48 
49  assert(isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
50  isa<DoStmt>(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.
58  ASTContext &ASTCtx = LCtx->getAnalysisDeclContext()->getASTContext();
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(findAll(stmt(hasDescendant(varDecl(hasType(referenceType())).bind(MatchRef)))),
72  *LCtx->getDecl()->getBody(), ASTCtx);
73  for (BoundNodes Match : Matches) {
74  const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef);
75  assert(VD);
76  const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
77  ITraits.setTrait(VarMem,
79  }
80 
81 
82  // 'this' pointer is not an lvalue, we should not invalidate it. If the loop
83  // is located in a method, constructor or destructor, the value of 'this'
84  // pointer should remain unchanged. Ignore static methods, since they do not
85  // have 'this' pointers.
86  const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl());
87  if (CXXMD && !CXXMD->isStatic()) {
88  const CXXThisRegion *ThisR = MRMgr.getCXXThisRegion(
90  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:992
Stmt - This represents one statement.
Definition: Stmt.h:66
Information about invalidation for a particular region/symbol.
Definition: MemRegion.h:1384
const GlobalsSpaceRegion * getGlobalsRegion(MemRegion::Kind K=MemRegion::GlobalInternalSpaceRegionKind, const CodeTextRegion *R=nullptr)
getGlobalsRegion - Retrieve the memory region associated with global variables.
Definition: MemRegion.cpp:741
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:728
Represents a variable declaration or definition.
Definition: Decl.h:820
ASTContext & getASTContext() const
void setTrait(SymbolRef Sym, InvalidationKinds IK)
Definition: MemRegion.cpp:1533
const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl
Matches variable declarations.
bool isStatic() const
Definition: DeclCXX.cpp:1849
CXXThisRegion - Represents the region for the implicit &#39;this&#39; parameter in a call to a C++ method...
Definition: MemRegion.h:966
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:153
const StackLocalsSpaceRegion * getStackLocalsRegion(const StackFrameContext *STC)
getStackLocalsRegion - Retrieve the memory region associated with the specified stack frame...
Definition: MemRegion.cpp:715
QualType getThisType(ASTContext &C) const
Returns the type of the this pointer.
Definition: DeclCXX.cpp:2149
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:2648
When applied to a MemSpaceRegion, indicates the entire memory space should be invalidated.
Definition: MemRegion.h:1409
Expr - This represents one expression.
Definition: Expr.h:106
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:102
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:2051
Tells that a region&#39;s contents is not changed.
Definition: MemRegion.h:1399
const CXXThisRegion * getCXXThisRegion(QualType thisPointerTy, const LocationContext *LC)
getCXXThisRegion - Retrieve the [artificial] region associated with the parameter &#39;this&#39;...
Definition: MemRegion.cpp:1065
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:819
StmtClass getStmtClass() const
Definition: Stmt.h:391
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.