10b57cec5SDimitry Andric //===--- LoopWidening.cpp - Widen loops -------------------------*- C++ -*-===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric ///
90b57cec5SDimitry Andric /// This file contains functions which are used to widen loops. A loop may be
100b57cec5SDimitry Andric /// widened to approximate the exit state(s), without analyzing every
110b57cec5SDimitry Andric /// iteration. The widening is done by invalidating anything which might be
120b57cec5SDimitry Andric /// modified by the body of the loop.
130b57cec5SDimitry Andric ///
140b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
150b57cec5SDimitry Andric
160b57cec5SDimitry Andric #include "clang/AST/AST.h"
170b57cec5SDimitry Andric #include "clang/ASTMatchers/ASTMatchFinder.h"
180b57cec5SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
190b57cec5SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
200b57cec5SDimitry Andric
210b57cec5SDimitry Andric using namespace clang;
220b57cec5SDimitry Andric using namespace ento;
230b57cec5SDimitry Andric using namespace clang::ast_matchers;
240b57cec5SDimitry Andric
250b57cec5SDimitry Andric const auto MatchRef = "matchref";
260b57cec5SDimitry Andric
270b57cec5SDimitry Andric /// Return the loops condition Stmt or NULL if LoopStmt is not a loop
getLoopCondition(const Stmt * LoopStmt)280b57cec5SDimitry Andric static const Expr *getLoopCondition(const Stmt *LoopStmt) {
290b57cec5SDimitry Andric switch (LoopStmt->getStmtClass()) {
300b57cec5SDimitry Andric default:
310b57cec5SDimitry Andric return nullptr;
320b57cec5SDimitry Andric case Stmt::ForStmtClass:
330b57cec5SDimitry Andric return cast<ForStmt>(LoopStmt)->getCond();
340b57cec5SDimitry Andric case Stmt::WhileStmtClass:
350b57cec5SDimitry Andric return cast<WhileStmt>(LoopStmt)->getCond();
360b57cec5SDimitry Andric case Stmt::DoStmtClass:
370b57cec5SDimitry Andric return cast<DoStmt>(LoopStmt)->getCond();
38*5f757f3fSDimitry Andric case Stmt::CXXForRangeStmtClass:
39*5f757f3fSDimitry Andric return cast<CXXForRangeStmt>(LoopStmt)->getCond();
400b57cec5SDimitry Andric }
410b57cec5SDimitry Andric }
420b57cec5SDimitry Andric
430b57cec5SDimitry Andric namespace clang {
440b57cec5SDimitry Andric namespace ento {
450b57cec5SDimitry Andric
getWidenedLoopState(ProgramStateRef PrevState,const LocationContext * LCtx,unsigned BlockCount,const Stmt * LoopStmt)460b57cec5SDimitry Andric ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
470b57cec5SDimitry Andric const LocationContext *LCtx,
480b57cec5SDimitry Andric unsigned BlockCount, const Stmt *LoopStmt) {
490b57cec5SDimitry Andric
50*5f757f3fSDimitry Andric assert((isa<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(LoopStmt)));
510b57cec5SDimitry Andric
520b57cec5SDimitry Andric // Invalidate values in the current state.
530b57cec5SDimitry Andric // TODO Make this more conservative by only invalidating values that might
540b57cec5SDimitry Andric // be modified by the body of the loop.
550b57cec5SDimitry Andric // TODO Nested loops are currently widened as a result of the invalidation
560b57cec5SDimitry Andric // being so inprecise. When the invalidation is improved, the handling
570b57cec5SDimitry Andric // of nested loops will also need to be improved.
580b57cec5SDimitry Andric ASTContext &ASTCtx = LCtx->getAnalysisDeclContext()->getASTContext();
590b57cec5SDimitry Andric const StackFrameContext *STC = LCtx->getStackFrame();
600b57cec5SDimitry Andric MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
610b57cec5SDimitry Andric const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
620b57cec5SDimitry Andric MRMgr.getStackArgumentsRegion(STC),
630b57cec5SDimitry Andric MRMgr.getGlobalsRegion()};
640b57cec5SDimitry Andric RegionAndSymbolInvalidationTraits ITraits;
650b57cec5SDimitry Andric for (auto *Region : Regions) {
660b57cec5SDimitry Andric ITraits.setTrait(Region,
670b57cec5SDimitry Andric RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
680b57cec5SDimitry Andric }
690b57cec5SDimitry Andric
700b57cec5SDimitry Andric // References should not be invalidated.
715ffd83dbSDimitry Andric auto Matches = match(
725ffd83dbSDimitry Andric findAll(stmt(hasDescendant(
735ffd83dbSDimitry Andric varDecl(hasType(hasCanonicalType(referenceType()))).bind(MatchRef)))),
740b57cec5SDimitry Andric *LCtx->getDecl()->getBody(), ASTCtx);
750b57cec5SDimitry Andric for (BoundNodes Match : Matches) {
760b57cec5SDimitry Andric const VarDecl *VD = Match.getNodeAs<VarDecl>(MatchRef);
770b57cec5SDimitry Andric assert(VD);
780b57cec5SDimitry Andric const VarRegion *VarMem = MRMgr.getVarRegion(VD, LCtx);
790b57cec5SDimitry Andric ITraits.setTrait(VarMem,
800b57cec5SDimitry Andric RegionAndSymbolInvalidationTraits::TK_PreserveContents);
810b57cec5SDimitry Andric }
820b57cec5SDimitry Andric
830b57cec5SDimitry Andric
840b57cec5SDimitry Andric // 'this' pointer is not an lvalue, we should not invalidate it. If the loop
850b57cec5SDimitry Andric // is located in a method, constructor or destructor, the value of 'this'
860b57cec5SDimitry Andric // pointer should remain unchanged. Ignore static methods, since they do not
870b57cec5SDimitry Andric // have 'this' pointers.
880b57cec5SDimitry Andric const CXXMethodDecl *CXXMD = dyn_cast<CXXMethodDecl>(STC->getDecl());
89*5f757f3fSDimitry Andric if (CXXMD && CXXMD->isImplicitObjectMemberFunction()) {
900b57cec5SDimitry Andric const CXXThisRegion *ThisR =
910b57cec5SDimitry Andric MRMgr.getCXXThisRegion(CXXMD->getThisType(), STC);
920b57cec5SDimitry Andric ITraits.setTrait(ThisR,
930b57cec5SDimitry Andric RegionAndSymbolInvalidationTraits::TK_PreserveContents);
940b57cec5SDimitry Andric }
950b57cec5SDimitry Andric
960b57cec5SDimitry Andric return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
970b57cec5SDimitry Andric BlockCount, LCtx, true, nullptr, nullptr,
980b57cec5SDimitry Andric &ITraits);
990b57cec5SDimitry Andric }
1000b57cec5SDimitry Andric
1010b57cec5SDimitry Andric } // end namespace ento
1020b57cec5SDimitry Andric } // end namespace clang
103