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
getLoopCondition(const Stmt * LoopStmt)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
getWidenedLoopState(ProgramStateRef PrevState,const LocationContext * LCtx,unsigned BlockCount,const Stmt * LoopStmt)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
69