Author: szepet Date: Mon Aug 28 03:50:28 2017 New Revision: 311883 URL: http://llvm.org/viewvc/llvm-project?rev=311883&view=rev Log: [StaticAnalyzer] LoopUnrolling: Keep track the maximum number of steps for each loop
This way the unrolling can be restricted for loops which will take at most a given number of steps. It is defined as 128 in this patch and it seems to have a good number for that purpose. Differential Revision: https://reviews.llvm.org/D37181 Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp cfe/trunk/test/Analysis/loop-unrolling.cpp Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h?rev=311883&r1=311882&r2=311883&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h Mon Aug 28 03:50:28 2017 @@ -38,7 +38,7 @@ bool isUnrolledState(ProgramStateRef Sta /// 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. Modified: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp?rev=311883&r1=311882&r2=311883&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp Mon Aug 28 03:50:28 2017 @@ -1523,10 +1523,11 @@ void ExprEngine::processCFGBlockEntrance // 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) Modified: cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp?rev=311883&r1=311882&r2=311883&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp Mon Aug 28 03:50:28 2017 @@ -23,22 +23,28 @@ using namespace clang; 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 @@ public: ID.AddInteger(K); ID.AddPointer(LoopStmt); ID.AddPointer(LCtx); + ID.AddInteger(maxStep); } }; @@ -74,12 +81,14 @@ ProgramStateRef processLoopEnd(const Stm } static internal::Matcher<Stmt> 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<Stmt> @@ -134,13 +143,13 @@ static internal::Matcher<Stmt> forLoopMa 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 @@ static bool isPossiblyEscaped(const VarD } bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, - ExplodedNode *Pred) { + ExplodedNode *Pred, unsigned &maxStep) { if (!isLoopStmt(LoopStmt)) return false; @@ -199,15 +208,21 @@ bool shouldCompletelyUnroll(const Stmt * return false; auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName"); + auto BoundNum = Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue(); + auto InitNum = Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue(); + auto CondOp = Matches[0].getNodeAs<BinaryOperator>("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 @@ bool madeNewBranch(ExplodedNode* N, cons // 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 @@ ProgramStateRef updateLoopStack(const St LCtx == LS.getHead().getLocationContext()) { if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) { State = State->set<LoopStack>(LS.getTail()); - State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx)); + State = State->add<LoopStack>( + LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); } return State; } - - if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred)) { - State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx)); + unsigned maxStep; + if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) { + State = State->add<LoopStack>( + LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); return State; } - State = State->add<LoopStack>(LoopState::getUnrolled(LoopStmt, LCtx)); + unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep()); + + unsigned innerMaxStep = maxStep * outerStep; + if (innerMaxStep > MAXIMUM_STEP_UNROLLED) + State = State->add<LoopStack>( + LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); + else + State = State->add<LoopStack>( + LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep)); return State; } Modified: cfe/trunk/test/Analysis/loop-unrolling.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/loop-unrolling.cpp?rev=311883&r1=311882&r2=311883&view=diff ============================================================================== --- cfe/trunk/test/Analysis/loop-unrolling.cpp (original) +++ cfe/trunk/test/Analysis/loop-unrolling.cpp Mon Aug 28 03:50:28 2017 @@ -5,7 +5,7 @@ void clang_analyzer_warnIfReached(); int getNum(); void foo(int &); -// Testing for loops. + int simple_unroll1() { int a[9]; int k = 42; @@ -259,7 +259,6 @@ int nested_inlined_no_unroll1() { return 0; } - int recursion_unroll1(bool b) { int k = 2; for (int i = 0; i < 5; i++) { @@ -289,7 +288,7 @@ 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) { + if (i == 4 && b) { recursion_unroll3(false); break; } @@ -320,3 +319,57 @@ int loop_exit_while_empty_loop_stack() { 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; +} + _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
