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   case Stmt::CXXForRangeStmtClass:
  39     return cast<CXXForRangeStmt>(LoopStmt)->getCond();
  40   }
  41 }
  42
  43 namespace clang {
  44 namespace ento {
  45
  46 ProgramStateRef 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(Region,
  67                      RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
  68   }
  69
  70   // References should not be invalidated.
  71   auto Matches = match(
  72       findAll(stmt(hasDescendant(
  73           varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))),
  74       *LCtx->getDecl()->getBody(), ASTCtx);
  75   for (BoundNodes Match : Matches) {
  76     const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef);
  77     assert(VD);
  78     const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
  79     ITraits.setTrait(VarMem,
  80                      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>(STC->getDecl());
  89   if (CXXMD && CXXMD->isImplicitObjectMemberFunction()) {
  90     const CXXThisRegion *ThisR =
  91         MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC);
  92     ITraits.setTrait(ThisR,
  93                      RegionAndSymbolInvalidationTraits::TK_PreserveContents);
  94   }
  95
  96   return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
  97                                       BlockCount, LCtx, true, nullptr, nullptr,
  98                                       &ITraits);
  99 }
 100
 101 } // end namespace ento
 102 } // end namespace clang