/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/LoopWidening.cpp
Line | Count | Source (jump to first uncovered line) |
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 | 52 | static const Expr *getLoopCondition(const Stmt *LoopStmt) { |
29 | 52 | switch (LoopStmt->getStmtClass()) { |
30 | 0 | default: |
31 | 0 | return nullptr; |
32 | 28 | case Stmt::ForStmtClass: |
33 | 28 | return cast<ForStmt>(LoopStmt)->getCond(); |
34 | 19 | case Stmt::WhileStmtClass: |
35 | 19 | return cast<WhileStmt>(LoopStmt)->getCond(); |
36 | 4 | case Stmt::DoStmtClass: |
37 | 4 | return cast<DoStmt>(LoopStmt)->getCond(); |
38 | 1 | case Stmt::CXXForRangeStmtClass: |
39 | 1 | return cast<CXXForRangeStmt>(LoopStmt)->getCond(); |
40 | 52 | } |
41 | 52 | } |
42 | | |
43 | | namespace clang { |
44 | | namespace ento { |
45 | | |
46 | | ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState, |
47 | | const LocationContext *LCtx, |
48 | 52 | unsigned BlockCount, const Stmt *LoopStmt) { |
49 | | |
50 | 52 | 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 | 52 | ASTContext &ASTCtx = LCtx->getAnalysisDeclContext()->getASTContext(); |
59 | 52 | const StackFrameContext *STC = LCtx->getStackFrame(); |
60 | 52 | MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager(); |
61 | 52 | const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC), |
62 | 52 | MRMgr.getStackArgumentsRegion(STC), |
63 | 52 | MRMgr.getGlobalsRegion()}; |
64 | 52 | RegionAndSymbolInvalidationTraits ITraits; |
65 | 156 | for (auto *Region : Regions) { |
66 | 156 | ITraits.setTrait(Region, |
67 | 156 | RegionAndSymbolInvalidationTraits::TK_EntireMemSpace); |
68 | 156 | } |
69 | | |
70 | | // References should not be invalidated. |
71 | 52 | auto Matches = match( |
72 | 52 | findAll(stmt(hasDescendant( |
73 | 52 | varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))), |
74 | 52 | *LCtx->getDecl()->getBody(), ASTCtx); |
75 | 52 | for (BoundNodes Match : Matches) { |
76 | 7 | const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef); |
77 | 7 | assert(VD); |
78 | 7 | const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx); |
79 | 7 | ITraits.setTrait(VarMem, |
80 | 7 | RegionAndSymbolInvalidationTraits::TK_PreserveContents); |
81 | 7 | } |
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 | 52 | const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl()); |
89 | 52 | if (CXXMD && CXXMD->isImplicitObjectMemberFunction()6 ) { |
90 | 5 | const CXXThisRegion *ThisR = |
91 | 5 | MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC); |
92 | 5 | ITraits.setTrait(ThisR, |
93 | 5 | RegionAndSymbolInvalidationTraits::TK_PreserveContents); |
94 | 5 | } |
95 | | |
96 | 52 | return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt), |
97 | 52 | BlockCount, LCtx, true, nullptr, nullptr, |
98 | 52 | &ITraits); |
99 | 52 | } |
100 | | |
101 | | } // end namespace ento |
102 | | } // end namespace clang |