Index: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h =================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h @@ -8,7 +8,17 @@ //===----------------------------------------------------------------------===// /// /// This header contains the declarations of functions which are used to decide -/// which loops should be completely unrolled and mark them. +/// which loops should be completely unrolled and mark their corresponding +/// CFGBlocks. It is done by tracking a stack of loops in the ProgramState. This +/// way specific loops can be marked as completely unrolled. For considering a +/// loop to be completely unrolled it has to fulfill the following requirements: +/// - Currently only forStmts can be considered. +/// - The bound has to be known. +/// - The counter variable has not escaped before/in the body of the loop and +/// changed only in the increment statement corresponding to the loop. It also +/// has to be initialized by a literal in the corresponding initStmt. +/// - Does not contain goto, switch and returnStmt. +/// /// //===----------------------------------------------------------------------===// @@ -18,17 +28,21 @@ #include "clang/Analysis/CFG.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" - namespace clang { 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, - ExplodedNode *Pred); +/// Returns if the given State indicates that is inside a completely unrolled +/// loop. +bool isUnrolledState(ProgramStateRef State); + +/// Updates the stack of loops contained by the ProgramState. +ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode* Pred); + +/// Updates the given ProgramState. In current implementation it removes the top +/// element of the stack of loops. +ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State); } // end namespace ento } // end namespace clang Index: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ cfe/trunk/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,17 @@ 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(), Pred)) { - 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 = updateLoopStack(Term, AMgr.getASTContext(), + Pred); + if (NewState != Pred->getState()){ + Pred = nodeBuilder.generateNode(NewState, Pred); + } } - - if (ActualBlock->empty()) - return; - - if (isUnrolledLoopBlock(ActualBlock, Pred, AMgr)) + // Is we are inside an unrolled loop then no need the check the counters. + if(isUnrolledState(Pred->getState())) return; } Index: cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -8,9 +8,8 @@ //===----------------------------------------------------------------------===// /// /// This file contains functions which are used to decide if a loop worth to be -/// unrolled. Moreover contains function which mark the loops which are unrolled -/// and store them in ProgramState. During the analysis we check the analyzed -/// blocks if they are part of an unrolled loop or reached from one. +/// unrolled. Moreover, these functions manages the stack of loop which is +/// tracked by the ProgramState. /// //===----------------------------------------------------------------------===// @@ -28,13 +27,41 @@ using namespace ento; using namespace clang::ast_matchers; -#define DEBUG_TYPE "LoopUnrolling" +struct LoopState { +private: + enum Kind { Normal, Unrolled } K; + const Stmt *LoopStmt; + const LocationContext *LCtx; + LoopState(Kind InK, const Stmt *S, const LocationContext *L) + : K(InK), LoopStmt(S), LCtx(L) {} -STATISTIC(NumTimesLoopUnrolled, - "The # of times a loop has got completely unrolled"); +public: + static LoopState getNormal(const Stmt *S, const LocationContext *L) { + return LoopState(Normal, S, L); + } + static LoopState getUnrolled(const Stmt *S, const LocationContext *L) { + return LoopState(Unrolled, S, L); + } + bool isUnrolled() const { return K == Unrolled; } + const Stmt *getLoopStmt() const { return LoopStmt; } + const LocationContext *getLocationContext() const { return LCtx; } + bool operator==(const LoopState &X) const { + return K == X.K && LoopStmt == X.LoopStmt; + } + void Profile(llvm::FoldingSetNodeID &ID) const { + ID.AddInteger(K); + ID.AddPointer(LoopStmt); + ID.AddPointer(LCtx); + } +}; -REGISTER_MAP_WITH_PROGRAMSTATE(UnrolledLoops, const Stmt *, - const FunctionDecl *) +// The tracked stack of loops. The stack indicates that which loops the +// simulated element contained by. The loops are marked depending if we decided +// to unroll them. +// TODO: The loop stack should not need to be in the program state since it is +// lexical in nature. Instead, the stack of loops should be tracked in the +// LocationContext. +REGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState) namespace clang { namespace ento { @@ -43,6 +70,16 @@ return S && (isa(S) || isa(S) || isa(S)); } +ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { + auto LS = State->get(); + assert(!LS.isEmpty() && "Loop not added to the stack."); + assert(LoopStmt == LS.getHead().getLoopStmt() && + "Loop is not on top of the stack."); + + State = State->set(LS.getTail()); + return State; +} + static internal::Matcher simpleCondition(StringRef BindName) { return binaryOperator( anyOf(hasOperatorName("<"), hasOperatorName(">"), hasOperatorName("<="), @@ -90,7 +127,7 @@ static internal::Matcher hasSuspiciousStmt(StringRef NodeName) { return hasDescendant(stmt( - anyOf(gotoStmt(), switchStmt(), + anyOf(gotoStmt(), switchStmt(), returnStmt(), // Escaping and not known mutation of the loop counter is handled // by exclusion of assigning and address-of operators and // pass-by-ref function calls on the loop counter from the body. @@ -174,83 +211,34 @@ return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred); } -namespace { -class LoopBlockVisitor : public ConstStmtVisitor { -public: - LoopBlockVisitor(llvm::SmallPtrSet &BS) : BlockSet(BS) {} +// updateLoopStack is called on every basic block, therefore it needs to be fast +ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode* Pred) { + auto State = Pred->getState(); + auto LCtx = Pred->getLocationContext(); - void VisitChildren(const Stmt *S) { - for (const Stmt *Child : S->children()) - if (Child) - Visit(Child); - } + 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 LS = State->get(); + if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() && + LCtx == LS.getHead().getLocationContext()) + return State; - void setBlocksOfLoop(const Stmt *Loop, const CFGStmtMap *M) { - BlockSet.clear(); - StmtToBlockMap = M; - LoopStmt = Loop; - Visit(LoopStmt); + if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred)) { + State = State->add(LoopState::getNormal(LoopStmt, LCtx)); + 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(LoopState::getUnrolled(LoopStmt, LCtx)); + 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 LS = State->get(); + if (LS.isEmpty() || !LS.getHead().isUnrolled()) + return false; + return true; } } } Index: cfe/trunk/test/Analysis/loop-unrolling.cpp =================================================================== --- cfe/trunk/test/Analysis/loop-unrolling.cpp +++ cfe/trunk/test/Analysis/loop-unrolling.cpp @@ -1,4 +1,4 @@ -// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config unroll-loops=true -verify -std=c++11 %s +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++11 %s void clang_analyzer_numTimesReached(); @@ -219,3 +219,56 @@ int a = 22 / k; // no-warning return 0; } + + +int recursion_unroll1(bool b) { + int k = 2; + for (int i = 0; i < 5; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{14}} + if(i == 0 && b) + recursion_unroll1(false); + clang_analyzer_numTimesReached(); // expected-warning {{15}} + } + int a = 22 / k; // no-warning + return 0; +} + +int recursion_unroll2(bool b) { + int k = 0; + for (int i = 0; i < 5; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{10}} + if(i == 0 && b) + recursion_unroll2(false); + clang_analyzer_numTimesReached(); // expected-warning {{10}} + } + int a = 22 / k; // expected-warning {{Division by zero}} + return 0; +} + +int recursion_unroll3(bool b) { + int k = 2; + for (int i = 0; i < 5; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{10}} + if(i == 4 && b) { + recursion_unroll3(false); + break; + } + clang_analyzer_numTimesReached(); // expected-warning {{10}} + } + int a = 22 / k; + return 0; +} + +int recursion_unroll4(bool b) { + int k = 2; + for (int i = 0; i < 5; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{14}} + if(i == 0 && b) { + recursion_unroll4(false); + continue; + } + clang_analyzer_numTimesReached(); // expected-warning {{14}} + } + int a = 22 / k; + return 0; +}