contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/LoopWidening.cpp

   1 //===--- LoopWidening.cpp - Widen loops -------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// This file contains functions which are used to widen loops. A loop may be
  11 /// widened to approximate the exit state(s), without analyzing every
  12 /// iteration. The widening is done by invalidating anything which might be
  13 /// modified by the body of the loop.
  14 ///
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
  18
  19 using namespace clang;
  20 using namespace ento;
  21
  22 /// Return the loops condition Stmt or NULL if LoopStmt is not a loop
  23 static const Expr *getLoopCondition(const Stmt *LoopStmt) {
  24   switch (LoopStmt->getStmtClass()) {
  25   default:
  26     return nullptr;
  27   case Stmt::ForStmtClass:
  28     return cast<ForStmt>(LoopStmt)->getCond();
  29   case Stmt::WhileStmtClass:
  30     return cast<WhileStmt>(LoopStmt)->getCond();
  31   case Stmt::DoStmtClass:
  32     return cast<DoStmt>(LoopStmt)->getCond();
  33   }
  34 }
  35
  36 namespace clang {
  37 namespace ento {
  38
  39 ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
  40                                     const LocationContext *LCtx,
  41                                     unsigned BlockCount, const Stmt *LoopStmt) {
  42
  43   assert(isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
  44          isa<DoStmt>(LoopStmt));
  45
  46   // Invalidate values in the current state.
  47   // TODO Make this more conservative by only invalidating values that might
  48   //      be modified by the body of the loop.
  49   // TODO Nested loops are currently widened as a result of the invalidation
  50   //      being so inprecise. When the invalidation is improved, the handling
  51   //      of nested loops will also need to be improved.
  52   const StackFrameContext *STC = LCtx->getCurrentStackFrame();
  53   MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
  54   const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
  55                                 MRMgr.getStackArgumentsRegion(STC),
  56                                 MRMgr.getGlobalsRegion()};
  57   RegionAndSymbolInvalidationTraits ITraits;
  58   for (auto *Region : Regions) {
  59     ITraits.setTrait(Region,
  60                      RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
  61   }
  62   return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
  63                                       BlockCount, LCtx, true, nullptr, nullptr,
  64                                       &ITraits);
  65 }
  66
  67 } // end namespace ento
  68 } // end namespace clang