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