Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h @@ -24,11 +24,10 @@ namespace ento { class AnalysisManager; -ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State, - const FunctionDecl *FD); -bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred, - AnalysisManager &AMgr); -bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx); +bool isUnrolledState(ProgramStateRef State); +ProgramStateRef updateUnrolledLoops(const Stmt *LoopStmt, ASTContext &ASTCtx, + ProgramStateRef State); +ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State); } // end namespace ento } // end namespace clang Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -519,10 +519,13 @@ ExplodedNodeSet Dst; Dst.Add(Pred); NodeBuilder Bldr(Pred, Dst, *currBldrCtx); + ProgramStateRef NewState = Pred->getState(); - LoopExit PP(S, Pred->getLocationContext()); - Bldr.generateNode(PP, Pred->getState(), Pred); + if(AMgr.options.shouldUnrollLoops()) + NewState = processLoopEnd(S, NewState); + LoopExit PP(S, Pred->getLocationContext()); + Bldr.generateNode(PP, NewState, Pred); // Enqueue the new nodes onto the work list. Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); } @@ -1519,22 +1522,15 @@ PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); // If we reach a loop which has a known bound (and meets // other constraints) then consider completely unrolling it. - if (AMgr.options.shouldUnrollLoops()) { - const CFGBlock *ActualBlock = nodeBuilder.getContext().getBlock(); - const Stmt *Term = ActualBlock->getTerminator(); - if (Term && shouldCompletelyUnroll(Term, AMgr.getASTContext())) { - ProgramStateRef UnrolledState = markLoopAsUnrolled( - Term, Pred->getState(), - cast(Pred->getStackFrame()->getDecl())); - if (UnrolledState != Pred->getState()) - nodeBuilder.generateNode(UnrolledState, Pred); - return; + if(AMgr.options.shouldUnrollLoops()) { + const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator(); + if (Term) { + ProgramStateRef NewState = updateUnrolledLoops(Term, AMgr.getASTContext(), Pred->getState()); + if (NewState != Pred->getState()){ + Pred = nodeBuilder.generateNode(NewState, Pred); + } } - - if (ActualBlock->empty()) - return; - - if (isUnrolledLoopBlock(ActualBlock, Pred, AMgr)) + if(isUnrolledState(Pred->getState())) return; } Index: lib/StaticAnalyzer/Core/LoopUnrolling.cpp =================================================================== --- lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -27,13 +27,8 @@ using namespace ento; using namespace clang::ast_matchers; -#define DEBUG_TYPE "LoopUnrolling" - -STATISTIC(NumTimesLoopUnrolled, - "The # of times a loop has got completely unrolled"); - -REGISTER_MAP_WITH_PROGRAMSTATE(UnrolledLoops, const Stmt *, - const FunctionDecl *) +REGISTER_LIST_WITH_PROGRAMSTATE(MaxBlockVisitStack, const llvm::APInt) +REGISTER_LIST_WITH_PROGRAMSTATE(UnrolledLoopStack, const Stmt *) namespace clang { namespace ento { @@ -42,6 +37,17 @@ return S && (isa(S) || isa(S) || isa(S)); } +ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { + auto ULS = State->get(); + auto MBVS = State->get(); + + assert(LoopStmt == ULS.getHead() && "Loop not added to the stack."); + + State = State->set(ULS.getTail()); + State = State->set(MBVS.getTail()); + return State; +} + static internal::Matcher simpleCondition(StringRef BindName) { return binaryOperator( anyOf(hasOperatorName("<"), hasOperatorName(">"), hasOperatorName("<="), @@ -127,83 +133,31 @@ return !Matches.empty(); } -namespace { -class LoopBlockVisitor : public ConstStmtVisitor { -public: - LoopBlockVisitor(llvm::SmallPtrSet &BS) : BlockSet(BS) {} - - void VisitChildren(const Stmt *S) { - for (const Stmt *Child : S->children()) - if (Child) - Visit(Child); - } +ProgramStateRef updateUnrolledLoops(const Stmt *LoopStmt, ASTContext &ASTCtx, + ProgramStateRef State){ + if (!isLoopStmt(LoopStmt)) + return State; - void VisitStmt(const Stmt *S) { - // In case of nested loops we only unroll the inner loop if it's marked too. - if (!S || (isLoopStmt(S) && S != LoopStmt)) - return; - BlockSet.insert(StmtToBlockMap->getBlock(S)); - VisitChildren(S); - } + auto ULS = State->get(); + if (!ULS.isEmpty() && LoopStmt == ULS.getHead()) + return State; - void setBlocksOfLoop(const Stmt *Loop, const CFGStmtMap *M) { - BlockSet.clear(); - StmtToBlockMap = M; - LoopStmt = Loop; - Visit(LoopStmt); + if(!shouldCompletelyUnroll(LoopStmt, ASTCtx)){ + State = State->add(llvm::APInt(1, 0)); + State = State->add(LoopStmt); + return State; } -private: - llvm::SmallPtrSet &BlockSet; - const CFGStmtMap *StmtToBlockMap; - const Stmt *LoopStmt; -}; -} -// TODO: refactor this function using LoopExit CFG element - once we have the -// information when the simulation reaches the end of the loop we can cleanup -// the state -bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred, - AnalysisManager &AMgr) { - const Stmt *Term = Block->getTerminator(); - auto State = Pred->getState(); - // In case of nested loops in an inlined function should not be unrolled only - // if the inner loop is marked. - if (Term && isLoopStmt(Term) && !State->contains(Term)) - return false; - - const CFGBlock *SearchedBlock; - llvm::SmallPtrSet BlockSet; - LoopBlockVisitor LBV(BlockSet); - // Check the CFGBlocks of every marked loop. - for (auto &E : State->get()) { - SearchedBlock = Block; - const StackFrameContext *StackFrame = Pred->getStackFrame(); - ParentMap PM(E.second->getBody()); - CFGStmtMap *M = CFGStmtMap::Build(AMgr.getCFG(E.second), &PM); - LBV.setBlocksOfLoop(E.first, M); - // In case of an inlined function call check if any of its callSiteBlock is - // marked. - while (BlockSet.find(SearchedBlock) == BlockSet.end() && StackFrame) { - SearchedBlock = StackFrame->getCallSiteBlock(); - if(!SearchedBlock || StackFrame->inTopFrame()) - break; - StackFrame = StackFrame->getParent()->getCurrentStackFrame(); - } - delete M; - if (SearchedBlock) - return true; - } - return false; + State = State->add(llvm::APInt(1, 1)); + State = State->add(LoopStmt); + return State; } -ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State, - const FunctionDecl *FD) { - if (State->contains(Term)) - return State; - - State = State->set(Term, FD); - ++NumTimesLoopUnrolled; - return State; +bool isUnrolledState(ProgramStateRef State) { + auto MBVS = State->get(); + if (MBVS.isEmpty() or MBVS.getHead() == 0 ) + return false; + return true; } } } Index: test/Analysis/loop-unrolling.cpp =================================================================== --- test/Analysis/loop-unrolling.cpp +++ test/Analysis/loop-unrolling.cpp @@ -1,4 +1,4 @@ -// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true -analyzer-stats -verify -std=c++11 %s +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -analyzer-stats -verify -std=c++11 %s void clang_analyzer_numTimesReached();