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" 18 #include "clang/ASTMatchers/ASTMatchFinder.h" 19 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 20 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.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 45 ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, 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()}; 64 RegionAndSymbolInvalidationTraits ITraits; 65 for (auto *Region : Regions) { 66 ITraits.setTrait(Region, 67 RegionAndSymbolInvalidationTraits::TK_EntireMemSpace); 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, 78 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 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( 89 CXXMD->getThisType(STC->getAnalysisDeclContext()->getASTContext()), 90 STC); 91 ITraits.setTrait(ThisR, 92 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 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 102