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 } 39 } 40 41 namespace clang { 42 namespace ento { 43 44 ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, 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()}; 63 RegionAndSymbolInvalidationTraits ITraits; 64 for (auto *Region : Regions) { 65 ITraits.setTrait(Region, 66 RegionAndSymbolInvalidationTraits::TK_EntireMemSpace); 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, 77 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 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, 90 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 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 100