1 //===--- LoopWidening.cpp - Widen loops -------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
17 #include "clang/AST/AST.h"
18 #include "clang/ASTMatchers/ASTMatchFinder.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
20 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
22 using namespace clang;
24 using namespace clang::ast_matchers;
26 const auto MatchRef = "matchref";
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()) {
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();
45 ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
46 const LocationContext *LCtx,
47 unsigned BlockCount, const Stmt *LoopStmt) {
49 assert(isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
50 isa<DoStmt>(LoopStmt));
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()};
64 RegionAndSymbolInvalidationTraits ITraits;
65 for (auto *Region : Regions) {
66 ITraits.setTrait(Region,
67 RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
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);
76 const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
77 ITraits.setTrait(VarMem,
78 RegionAndSymbolInvalidationTraits::TK_PreserveContents);
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 shoule remain unchanged.
85 if (const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl())) {
86 const CXXThisRegion *ThisR = MRMgr.getCXXThisRegion(
87 CXXMD->getThisType(STC->getAnalysisDeclContext()->getASTContext()),
89 ITraits.setTrait(ThisR,
90 RegionAndSymbolInvalidationTraits::TK_PreserveContents);
93 return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
94 BlockCount, LCtx, true, nullptr, nullptr,
98 } // end namespace ento
99 } // end namespace clang