| 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, WhileStmt, DoStmt>(LoopStmt))); |
| 49 |
|
| 50 |
// Invalidate values in the current state. |
| 51 |
// TODO Make this more conservative by only invalidating values that might |
| 52 |
// be modified by the body of the loop. |
| 53 |
// TODO Nested loops are currently widened as a result of the invalidation |
| 54 |
// being so inprecise. When the invalidation is improved, the handling |
| 55 |
// of nested loops will also need to be improved. |
| 56 |
ASTContext &ASTCtx = LCtx->getAnalysisDeclContext()->getASTContext(); |
| 57 |
const StackFrameContext *STC = LCtx->getStackFrame(); |
| 58 |
MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager(); |
| 59 |
const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC), |
| 60 |
MRMgr.getStackArgumentsRegion(STC), |
| 61 |
MRMgr.getGlobalsRegion()}; |
| 62 |
RegionAndSymbolInvalidationTraits ITraits; |
| 63 |
for (auto *Region : Regions) { |
| 64 |
ITraits.setTrait(Region, |
| 65 |
RegionAndSymbolInvalidationTraits::TK_EntireMemSpace); |
| 66 |
} |
| 67 |
|
| 68 |
// References should not be invalidated. |
| 69 |
auto Matches = match( |
| 70 |
findAll(stmt(hasDescendant( |
| 71 |
varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))), |
| 72 |
*LCtx->getDecl()->getBody(), ASTCtx); |
| 73 |
for (BoundNodes Match : Matches) { |
| 74 |
const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef); |
| 75 |
assert(VD); |
| 76 |
const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx); |
| 77 |
ITraits.setTrait(VarMem, |
| 78 |
RegionAndSymbolInvalidationTraits::TK_PreserveContents); |
| 79 |
} |
| 80 |
|
| 81 |
|
| 82 |
// 'this' pointer is not an lvalue, we should not invalidate it. If the loop |
| 83 |
// is located in a method, constructor or destructor, the value of 'this' |
| 84 |
// pointer should remain unchanged. Ignore static methods, since they do not |
| 85 |
// have 'this' pointers. |
| 86 |
const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl()); |
| 87 |
if (CXXMD && !CXXMD->isStatic()) { |
| 88 |
const CXXThisRegion *ThisR = |
| 89 |
MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC); |
| 90 |
ITraits.setTrait(ThisR, |
| 91 |
RegionAndSymbolInvalidationTraits::TK_PreserveContents); |
| 92 |
} |
| 93 |
|
| 94 |
return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt), |
| 95 |
BlockCount, LCtx, true, nullptr, nullptr, |
| 96 |
&ITraits); |
| 97 |
} |
| 98 |
|
| 99 |
} // end namespace ento |
| 100 |
} // end namespace clang |