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 | |
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(MR: Region, |
48 | IK: RegionAndSymbolInvalidationTraits::TK_EntireMemSpace); |
49 | } |
50 | |
51 | // References should not be invalidated. |
52 | auto Matches = match( |
53 | Matcher: findAll(Matcher: stmt(hasDescendant( |
54 | varDecl(hasType(InnerMatcher: hasCanonicalType(InnerMatcher: referenceType()))).bind(ID: MatchRef)))), |
55 | Node: *LCtx->getDecl()->getBody(), Context&: ASTCtx); |
56 | for (BoundNodes Match : Matches) { |
57 | const VarDecl *VD = Match.getNodeAs<VarDecl>(ID: MatchRef); |
58 | assert(VD); |
59 | const VarRegion *VarMem = MRMgr.getVarRegion(VD, LC: LCtx); |
60 | ITraits.setTrait(MR: VarMem, |
61 | IK: 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>(Val: STC->getDecl()); |
70 | if (CXXMD && CXXMD->isImplicitObjectMemberFunction()) { |
71 | const CXXThisRegion *ThisR = |
72 | MRMgr.getCXXThisRegion(thisPointerTy: CXXMD->getThisType(), LC: STC); |
73 | ITraits.setTrait(MR: ThisR, |
74 | IK: RegionAndSymbolInvalidationTraits::TK_PreserveContents); |
75 | } |
76 | |
77 | return PrevState->invalidateRegions(Regions, Elem, BlockCount, LCtx, CausesPointerEscape: true, |
78 | IS: nullptr, Call: nullptr, ITraits: &ITraits); |
79 | } |
80 | |
81 | } // end namespace ento |
82 | } // end namespace clang |
83 | |