xref: /freebsd-src/contrib/llvm-project/clang/lib/StaticAnalyzer/Core/LoopWidening.cpp (revision 5f757f3ff9144b609b3c433dfd370cc6bdc191ad)
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