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 @@ -38,7 +38,7 @@ /// Updates the stack of loops contained by the ProgramState. ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, - ExplodedNode* Pred); + ExplodedNode* Pred, unsigned maxVisitOnPath); /// Updates the given ProgramState. In current implementation it removes the top /// element of the stack of loops. Index: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1523,10 +1523,11 @@ // If we reach a loop which has a known bound (and meets // other constraints) then consider completely unrolling it. if(AMgr.options.shouldUnrollLoops()) { + unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath; const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator(); if (Term) { ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(), - Pred); + Pred, maxBlockVisitOnPath); if (NewState != Pred->getState()) { ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred); if (!UpdatedNode) Index: cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -23,22 +23,28 @@ using namespace ento; using namespace clang::ast_matchers; +static const int MAXIMUM_STEP_UNROLLED = 128; + 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) {} + unsigned maxStep; + LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N) + : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {} public: - static LoopState getNormal(const Stmt *S, const LocationContext *L) { - return LoopState(Normal, S, L); + static LoopState getNormal(const Stmt *S, const LocationContext *L, + unsigned N) { + return LoopState(Normal, S, L, N); } - static LoopState getUnrolled(const Stmt *S, const LocationContext *L) { - return LoopState(Unrolled, S, L); + static LoopState getUnrolled(const Stmt *S, const LocationContext *L, + unsigned N) { + return LoopState(Unrolled, S, L, N); } bool isUnrolled() const { return K == Unrolled; } + unsigned getMaxStep() const { return maxStep; } const Stmt *getLoopStmt() const { return LoopStmt; } const LocationContext *getLocationContext() const { return LCtx; } bool operator==(const LoopState &X) const { @@ -48,6 +54,7 @@ ID.AddInteger(K); ID.AddPointer(LoopStmt); ID.AddPointer(LCtx); + ID.AddInteger(maxStep); } }; @@ -74,12 +81,14 @@ } static internal::Matcher simpleCondition(StringRef BindName) { - return binaryOperator( - anyOf(hasOperatorName("<"), hasOperatorName(">"), hasOperatorName("<="), - hasOperatorName(">="), hasOperatorName("!=")), - hasEitherOperand(ignoringParenImpCasts( - declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))))), - hasEitherOperand(ignoringParenImpCasts(integerLiteral()))); + return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"), + hasOperatorName("<="), hasOperatorName(">="), + hasOperatorName("!=")), + hasEitherOperand(ignoringParenImpCasts(declRefExpr( + to(varDecl(hasType(isInteger())).bind(BindName))))), + hasEitherOperand(ignoringParenImpCasts( + integerLiteral().bind("boundNum")))) + .bind("conditionOperator"); } static internal::Matcher @@ -134,13 +143,13 @@ return forStmt( hasCondition(simpleCondition("initVarName")), // Initialization should match the form: 'int i = 6' or 'i = 42'. - hasLoopInit( - anyOf(declStmt(hasSingleDecl( - varDecl(allOf(hasInitializer(integerLiteral()), - equalsBoundNode("initVarName"))))), - binaryOperator(hasLHS(declRefExpr(to(varDecl( - equalsBoundNode("initVarName"))))), - hasRHS(integerLiteral())))), + hasLoopInit(anyOf( + declStmt(hasSingleDecl(varDecl( + allOf(hasInitializer(integerLiteral().bind("initNum")), + equalsBoundNode("initVarName"))))), + binaryOperator(hasLHS(declRefExpr(to( + varDecl(equalsBoundNode("initVarName"))))), + hasRHS(integerLiteral().bind("initNum"))))), // Incrementation should be a simple increment or decrement // operator call. hasIncrement(unaryOperator( @@ -187,7 +196,7 @@ } bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, - ExplodedNode *Pred) { + ExplodedNode *Pred, unsigned &maxStep) { if (!isLoopStmt(LoopStmt)) return false; @@ -199,15 +208,21 @@ return false; auto CounterVar = Matches[0].getNodeAs("initVarName"); + auto BoundNum = Matches[0].getNodeAs("boundNum")->getValue(); + auto InitNum = Matches[0].getNodeAs("initNum")->getValue(); + auto CondOp = Matches[0].getNodeAs("conditionOperator"); + if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE) + maxStep = (BoundNum - InitNum + 1).abs().getZExtValue(); + else + maxStep = (BoundNum - InitNum).abs().getZExtValue(); // Check if the counter of the loop is not escaped before. return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred); } -bool madeNewBranch(ExplodedNode* N, const Stmt* LoopStmt) { - const Stmt* S = nullptr; - while (!N->pred_empty()) - { +bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) { + const Stmt *S = nullptr; + while (!N->pred_empty()) { if (N->succ_size() > 1) return true; @@ -226,7 +241,7 @@ // updateLoopStack is called on every basic block, therefore it needs to be fast ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, - ExplodedNode* Pred) { + ExplodedNode *Pred, unsigned maxVisitOnPath) { auto State = Pred->getState(); auto LCtx = Pred->getLocationContext(); @@ -238,17 +253,27 @@ LCtx == LS.getHead().getLocationContext()) { if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) { State = State->set(LS.getTail()); - State = State->add(LoopState::getNormal(LoopStmt, LCtx)); + State = State->add( + LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); } return State; } - - if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred)) { - State = State->add(LoopState::getNormal(LoopStmt, LCtx)); + unsigned maxStep; + if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) { + State = State->add( + LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); return State; } - State = State->add(LoopState::getUnrolled(LoopStmt, LCtx)); + unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep()); + + unsigned innerMaxStep = maxStep * outerStep; + if (innerMaxStep > MAXIMUM_STEP_UNROLLED) + State = State->add( + LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); + else + State = State->add( + LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep)); return State; } Index: cfe/trunk/test/Analysis/loop-unrolling.cpp =================================================================== --- cfe/trunk/test/Analysis/loop-unrolling.cpp +++ cfe/trunk/test/Analysis/loop-unrolling.cpp @@ -5,7 +5,7 @@ int getNum(); void foo(int &); -// Testing for loops. + int simple_unroll1() { int a[9]; int k = 42; @@ -259,7 +259,6 @@ return 0; } - int recursion_unroll1(bool b) { int k = 2; for (int i = 0; i < 5; i++) { @@ -289,7 +288,7 @@ int k = 2; for (int i = 0; i < 5; i++) { clang_analyzer_numTimesReached(); // expected-warning {{10}} - if(i == 4 && b) { + if (i == 4 && b) { recursion_unroll3(false); break; } @@ -320,3 +319,57 @@ return 0; } +int num_steps_on_limit() { + for (int i = 0; i < 128; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{128}} + } + clang_analyzer_numTimesReached(); // expected-warning {{1}} + return 0; +} + +int num_steps_over_limit1() { + for (int i = 0; i < 129; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + } + return 0; +} + +int num_steps_on_limit2() { + for (int i = 0; i < 2; i++) { + for (int j = 0; j < 64; j++) { + clang_analyzer_numTimesReached(); // expected-warning {{128}} + } + } + return 0; +} + +int num_steps_over_limit2() { + for (int i = 0; i < 2; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{1}} + for (int j = 0; j <= 64; j++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + } + } + return 0; +} + +int num_steps_on_limit3() { + for (int i = 0; i < getNum(); i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + for (int j = 0; j < 32; j++) { + clang_analyzer_numTimesReached(); // expected-warning {{128}} + } + } + return 0; +} + +int num_steps_over_limit3() { + for (int i = 0; i < getNum(); i++) { + clang_analyzer_numTimesReached(); // expected-warning {{1}} + for (int j = 0; j < 33; j++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + } + } + return 0; +} +