106f32e7eSjoerg //===--- LoopWidening.cpp - Widen loops -------------------------*- C++ -*-===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg ///
906f32e7eSjoerg /// This file contains functions which are used to widen loops. A loop may be
1006f32e7eSjoerg /// widened to approximate the exit state(s), without analyzing every
1106f32e7eSjoerg /// iteration. The widening is done by invalidating anything which might be
1206f32e7eSjoerg /// modified by the body of the loop.
1306f32e7eSjoerg ///
1406f32e7eSjoerg //===----------------------------------------------------------------------===//
1506f32e7eSjoerg
1606f32e7eSjoerg #include "clang/AST/AST.h"
1706f32e7eSjoerg #include "clang/ASTMatchers/ASTMatchFinder.h"
1806f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
1906f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
2006f32e7eSjoerg
2106f32e7eSjoerg using namespace clang;
2206f32e7eSjoerg using namespace ento;
2306f32e7eSjoerg using namespace clang::ast_matchers;
2406f32e7eSjoerg
2506f32e7eSjoerg const auto MatchRef = "matchref";
2606f32e7eSjoerg
2706f32e7eSjoerg /// Return the loops condition Stmt or NULL if LoopStmt is not a loop
getLoopCondition(const Stmt * LoopStmt)2806f32e7eSjoerg static const Expr *getLoopCondition(const Stmt *LoopStmt) {
2906f32e7eSjoerg switch (LoopStmt->getStmtClass()) {
3006f32e7eSjoerg default:
3106f32e7eSjoerg return nullptr;
3206f32e7eSjoerg case Stmt::ForStmtClass:
3306f32e7eSjoerg return cast<ForStmt>(LoopStmt)->getCond();
3406f32e7eSjoerg case Stmt::WhileStmtClass:
3506f32e7eSjoerg return cast<WhileStmt>(LoopStmt)->getCond();
3606f32e7eSjoerg case Stmt::DoStmtClass:
3706f32e7eSjoerg return cast<DoStmt>(LoopStmt)->getCond();
3806f32e7eSjoerg }
3906f32e7eSjoerg }
4006f32e7eSjoerg
4106f32e7eSjoerg namespace clang {
4206f32e7eSjoerg namespace ento {
4306f32e7eSjoerg
getWidenedLoopState(ProgramStateRef PrevState,const LocationContext * LCtx,unsigned BlockCount,const Stmt * LoopStmt)4406f32e7eSjoerg ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
4506f32e7eSjoerg const LocationContext *LCtx,
4606f32e7eSjoerg unsigned BlockCount, const Stmt *LoopStmt) {
4706f32e7eSjoerg
4806f32e7eSjoerg assert(isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
4906f32e7eSjoerg isa<DoStmt>(LoopStmt));
5006f32e7eSjoerg
5106f32e7eSjoerg // Invalidate values in the current state.
5206f32e7eSjoerg // TODO Make this more conservative by only invalidating values that might
5306f32e7eSjoerg // be modified by the body of the loop.
5406f32e7eSjoerg // TODO Nested loops are currently widened as a result of the invalidation
5506f32e7eSjoerg // being so inprecise. When the invalidation is improved, the handling
5606f32e7eSjoerg // of nested loops will also need to be improved.
5706f32e7eSjoerg ASTContext &ASTCtx = LCtx->getAnalysisDeclContext()->getASTContext();
5806f32e7eSjoerg const StackFrameContext *STC = LCtx->getStackFrame();
5906f32e7eSjoerg MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
6006f32e7eSjoerg const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
6106f32e7eSjoerg MRMgr.getStackArgumentsRegion(STC),
6206f32e7eSjoerg MRMgr.getGlobalsRegion()};
6306f32e7eSjoerg RegionAndSymbolInvalidationTraits ITraits;
6406f32e7eSjoerg for (auto *Region : Regions) {
6506f32e7eSjoerg ITraits.setTrait(Region,
6606f32e7eSjoerg RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
6706f32e7eSjoerg }
6806f32e7eSjoerg
6906f32e7eSjoerg // References should not be invalidated.
70*13fbcb42Sjoerg auto Matches = match(
71*13fbcb42Sjoerg findAll(stmt(hasDescendant(
72*13fbcb42Sjoerg varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))),
7306f32e7eSjoerg *LCtx->getDecl()->getBody(), ASTCtx);
7406f32e7eSjoerg for (BoundNodes Match : Matches) {
7506f32e7eSjoerg const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef);
7606f32e7eSjoerg assert(VD);
7706f32e7eSjoerg const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
7806f32e7eSjoerg ITraits.setTrait(VarMem,
7906f32e7eSjoerg RegionAndSymbolInvalidationTraits::TK_PreserveContents);
8006f32e7eSjoerg }
8106f32e7eSjoerg
8206f32e7eSjoerg
8306f32e7eSjoerg // 'this' pointer is not an lvalue, we should not invalidate it. If the loop
8406f32e7eSjoerg // is located in a method, constructor or destructor, the value of 'this'
8506f32e7eSjoerg // pointer should remain unchanged. Ignore static methods, since they do not
8606f32e7eSjoerg // have 'this' pointers.
8706f32e7eSjoerg const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl());
8806f32e7eSjoerg if (CXXMD && !CXXMD->isStatic()) {
8906f32e7eSjoerg const CXXThisRegion *ThisR =
9006f32e7eSjoerg MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC);
9106f32e7eSjoerg ITraits.setTrait(ThisR,
9206f32e7eSjoerg RegionAndSymbolInvalidationTraits::TK_PreserveContents);
9306f32e7eSjoerg }
9406f32e7eSjoerg
9506f32e7eSjoerg return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
9606f32e7eSjoerg BlockCount, LCtx, true, nullptr, nullptr,
9706f32e7eSjoerg &ITraits);
9806f32e7eSjoerg }
9906f32e7eSjoerg
10006f32e7eSjoerg } // end namespace ento
10106f32e7eSjoerg } // end namespace clang
102