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>(Val: LoopStmt)->getCond();
34 case Stmt::WhileStmtClass:
35 return cast<WhileStmt>(Val: LoopStmt)->getCond();
36 case Stmt::DoStmtClass:
37 return cast<DoStmt>(Val: LoopStmt)->getCond();
38 case Stmt::CXXForRangeStmtClass:
39 return cast<CXXForRangeStmt>(Val: LoopStmt)->getCond();
40 }
41}
42
43namespace clang {
44namespace ento {
45
46ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
47 const LocationContext *LCtx,
48 unsigned BlockCount, const Stmt *LoopStmt) {
49
50 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 ASTContext &ASTCtx = LCtx->getAnalysisDeclContext()->getASTContext();
59 const StackFrameContext *STC = LCtx->getStackFrame();
60 MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
61 const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
62 MRMgr.getStackArgumentsRegion(STC),
63 MRMgr.getGlobalsRegion()};
64 RegionAndSymbolInvalidationTraits ITraits;
65 for (auto *Region : Regions) {
66 ITraits.setTrait(MR: Region,
67 IK: RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
68 }
69
70 // References should not be invalidated.
71 auto Matches = match(
72 Matcher: findAll(Matcher: stmt(hasDescendant(
73 varDecl(hasType(InnerMatcher: hasCanonicalType(InnerMatcher: referenceType()))).bind(ID: MatchRef)))),
74 Node: *LCtx->getDecl()->getBody(), Context&: ASTCtx);
75 for (BoundNodes Match : Matches) {
76 const VarDecl *VD = Match.getNodeAs<VarDecl>(ID: MatchRef);
77 assert(VD);
78 const VarRegion *VarMem = MRMgr.getVarRegion(VD, LC: LCtx);
79 ITraits.setTrait(MR: VarMem,
80 IK: RegionAndSymbolInvalidationTraits::TK_PreserveContents);
81 }
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 const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(Val: STC->getDecl());
89 if (CXXMD && CXXMD->isImplicitObjectMemberFunction()) {
90 const CXXThisRegion *ThisR =
91 MRMgr.getCXXThisRegion(thisPointerTy: CXXMD->getThisType(), LC: STC);
92 ITraits.setTrait(MR: ThisR,
93 IK: RegionAndSymbolInvalidationTraits::TK_PreserveContents);
94 }
95
96 return PrevState->invalidateRegions(Regions, E: getLoopCondition(LoopStmt),
97 BlockCount, LCtx, CausesPointerEscape: true, IS: nullptr, Call: nullptr,
98 ITraits: &ITraits);
99}
100
101} // end namespace ento
102} // end namespace clang
103