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 21using namespace clang; 22using namespace ento; 23using namespace clang::ast_matchers; 24 25const auto MatchRef = "matchref"; 26 27/// Return the loops condition Stmt or NULL if LoopStmt is not a loop 28static 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 41namespace clang { 42namespace ento { 43 44ProgramStateRef 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