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 static const Expr *getLoopCondition(const Stmt *LoopStmt) {
29   switch (LoopStmt->getStmtClass()) {
30   default:
31     return nullptr;
32   case Stmt::ForStmtClass:
33     return cast<ForStmt>(LoopStmt)->getCond();
34   case Stmt::WhileStmtClass:
35     return cast<WhileStmt>(LoopStmt)->getCond();
36   case Stmt::DoStmtClass:
37     return cast<DoStmt>(LoopStmt)->getCond();
38   }
39 }
40 
41 namespace clang {
42 namespace ento {
43 
44 ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
45                                     const LocationContext *LCtx,
46                                     unsigned BlockCount, const Stmt *LoopStmt) {
47 
48   assert((isa<ForStmt, WhileStmt, DoStmt>(LoopStmt)));
49 
50   // Invalidate values in the current state.
51   // TODO Make this more conservative by only invalidating values that might
52   //      be modified by the body of the loop.
53   // TODO Nested loops are currently widened as a result of the invalidation
54   //      being so inprecise. When the invalidation is improved, the handling
55   //      of nested loops will also need to be improved.
56   ASTContext &ASTCtx = LCtx->getAnalysisDeclContext()->getASTContext();
57   const StackFrameContext *STC = LCtx->getStackFrame();
58   MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
59   const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
60                                 MRMgr.getStackArgumentsRegion(STC),
61                                 MRMgr.getGlobalsRegion()};
62   RegionAndSymbolInvalidationTraits ITraits;
63   for (auto *Region : Regions) {
64     ITraits.setTrait(Region,
65                      RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
66   }
67 
68   // References should not be invalidated.
69   auto Matches = match(
70       findAll(stmt(hasDescendant(
71           varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))),
72       *LCtx->getDecl()->getBody(), ASTCtx);
73   for (BoundNodes Match : Matches) {
74     const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef);
75     assert(VD);
76     const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
77     ITraits.setTrait(VarMem,
78                      RegionAndSymbolInvalidationTraits::TK_PreserveContents);
79   }
80 
81 
82   // 'this' pointer is not an lvalue, we should not invalidate it. If the loop
83   // is located in a method, constructor or destructor, the value of 'this'
84   // pointer should remain unchanged.  Ignore static methods, since they do not
85   // have 'this' pointers.
86   const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl());
87   if (CXXMD && !CXXMD->isStatic()) {
88     const CXXThisRegion *ThisR =
89         MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC);
90     ITraits.setTrait(ThisR,
91                      RegionAndSymbolInvalidationTraits::TK_PreserveContents);
92   }
93 
94   return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
95                                       BlockCount, LCtx, true, nullptr, nullptr,
96                                       &ITraits);
97 }
98 
99 } // end namespace ento
100 } // end namespace clang
101