contrib/llvm-project/clang/lib/StaticAnalyzer/Core/LoopWidening.cpp

   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>(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