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" 17 #include "clang/ASTMatchers/ASTMatchFinder.h" 18 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 19 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.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 case Stmt::CXXForRangeStmtClass: 39 return cast<CXXForRangeStmt>(LoopStmt)->getCond(); 40 } 41 } 42 43 namespace clang { 44 namespace ento { 45 46 ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, 47 const LocationContext *LCtx, 48 unsigned BlockCount, const Stmt *LoopStmt) { 49 50 assert((isa<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(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( 72 findAll(stmt(hasDescendant( 73 varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))), 74 *LCtx->getDecl()->getBody(), ASTCtx); 75 for (BoundNodes Match : Matches) { 76 const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef); 77 assert(VD); 78 const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx); 79 ITraits.setTrait(VarMem, 80 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 81 } 82 83 84 // 'this' pointer is not an lvalue, we should not invalidate it. If the loop 85 // is located in a method, constructor or destructor, the value of 'this' 86 // pointer should remain unchanged. Ignore static methods, since they do not 87 // have 'this' pointers. 88 const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl()); 89 if (CXXMD && CXXMD->isImplicitObjectMemberFunction()) { 90 const CXXThisRegion *ThisR = 91 MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC); 92 ITraits.setTrait(ThisR, 93 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 94 } 95 96 return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt), 97 BlockCount, LCtx, true, nullptr, nullptr, 98 &ITraits); 99 } 100 101 } // end namespace ento 102 } // end namespace clang 103