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
19using namespace clang;
20using namespace ento;
21
22/// Return the loops condition Stmt or NULL if LoopStmt is not a loop
23static 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
36namespace clang {
37namespace ento {
38
39ProgramStateRef 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