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