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/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
17 #include "clang/ASTMatchers/ASTMatchFinder.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
19
20 using namespace clang;
21 using namespace ento;
22 using namespace clang::ast_matchers;
23
24 const auto MatchRef = "matchref";
25
26 namespace clang {
27 namespace ento {
28
getWidenedLoopState(ProgramStateRef PrevState,const LocationContext * LCtx,unsigned BlockCount,ConstCFGElementRef Elem)29 ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
30 const LocationContext *LCtx,
31 unsigned BlockCount,
32 ConstCFGElementRef Elem) {
33 // Invalidate values in the current state.
34 // TODO Make this more conservative by only invalidating values that might
35 // be modified by the body of the loop.
36 // TODO Nested loops are currently widened as a result of the invalidation
37 // being so inprecise. When the invalidation is improved, the handling
38 // of nested loops will also need to be improved.
39 ASTContext &ASTCtx = LCtx->getAnalysisDeclContext()->getASTContext();
40 const StackFrameContext *STC = LCtx->getStackFrame();
41 MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
42 const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
43 MRMgr.getStackArgumentsRegion(STC),
44 MRMgr.getGlobalsRegion()};
45 RegionAndSymbolInvalidationTraits ITraits;
46 for (auto *Region : Regions) {
47 ITraits.setTrait(Region,
48 RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
49 }
50
51 // References should not be invalidated.
52 auto Matches = match(
53 findAll(stmt(hasDescendant(
54 varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))),
55 *LCtx->getDecl()->getBody(), ASTCtx);
56 for (BoundNodes Match : Matches) {
57 const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef);
58 assert(VD);
59 const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
60 ITraits.setTrait(VarMem,
61 RegionAndSymbolInvalidationTraits::TK_PreserveContents);
62 }
63
64
65 // 'this' pointer is not an lvalue, we should not invalidate it. If the loop
66 // is located in a method, constructor or destructor, the value of 'this'
67 // pointer should remain unchanged. Ignore static methods, since they do not
68 // have 'this' pointers.
69 const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl());
70 if (CXXMD && CXXMD->isImplicitObjectMemberFunction()) {
71 const CXXThisRegion *ThisR =
72 MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC);
73 ITraits.setTrait(ThisR,
74 RegionAndSymbolInvalidationTraits::TK_PreserveContents);
75 }
76
77 return PrevState->invalidateRegions(Regions, Elem, BlockCount, LCtx, true,
78 nullptr, nullptr, &ITraits);
79 }
80
81 } // end namespace ento
82 } // end namespace clang
83