Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h @@ -25,11 +25,11 @@ namespace clang { namespace ento { - ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State, - CFGStmtMap *StmtToBlockMap); - bool isUnrolledLoopBlock(const CFGBlock *Block, - ExplodedNode *Prev); -bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx); +ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State, + CFGStmtMap *StmtToBlockMap); +bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev); +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode* Pred, SValBuilder &SVB); } // end namespace ento } // end namespace clang Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1504,16 +1504,7 @@ // If this block is terminated by 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(), Pred->getLocationContext()->getAnalysisDeclContext()->getCFGStmtMap()); - if (UnrolledState != Pred->getState()) - nodeBuilder.generateNode(UnrolledState, Pred); - return; - } - + const CFGBlock* ActualBlock = nodeBuilder.getContext().getBlock(); if (isUnrolledLoopBlock(ActualBlock, Pred)) return; if (ActualBlock->empty()) @@ -1695,6 +1686,23 @@ return; } + if (AMgr.options.shouldUnrollLoops()) { + if (shouldCompletelyUnroll(Term, AMgr.getASTContext(), Pred, svalBuilder)) { + ProgramStateRef UnrolledState = + markLoopAsUnrolled(Term, Pred->getState(), + Pred->getLocationContext()-> + getAnalysisDeclContext()->getCFGStmtMap()); + if(UnrolledState != Pred->getState()) { + NodeBuilder UnrolledStateBldr(Pred, Dst, BldCtx); + UnrolledStateBldr.generateNode(Pred->getLocation(), UnrolledState, + Pred); + assert(Dst.size() == 1); + Pred = *Dst.begin(); + Dst.clear(); + } + } + } + if (const Expr *Ex = dyn_cast(Condition)) Condition = Ex->IgnoreParens(); Index: lib/StaticAnalyzer/Core/LoopUnrolling.cpp =================================================================== --- lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -44,9 +44,11 @@ return binaryOperator( anyOf(hasOperatorName("<"), hasOperatorName(">"), hasOperatorName("<="), hasOperatorName(">="), hasOperatorName("!=")), - hasEitherOperand(ignoringParenImpCasts( - declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))))), - hasEitherOperand(ignoringParenImpCasts(integerLiteral()))); + hasEitherOperand(expr(ignoringParenImpCasts(declRefExpr( + to(varDecl(hasType(isInteger())).bind(BindName))))) + .bind("CounterExp")), + hasEitherOperand( + expr(unless(equalsBoundNode("CounterExp"))).bind("BoundExp"))); } static internal::Matcher changeIntBoundNode(StringRef NodeName) { @@ -124,18 +126,30 @@ return anyOf(doWhileLoopMatcher(), whileLoopMatcher(), forLoopMatcher()); } -bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) { +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode *Pred, SValBuilder &SVB) { if (!isLoopStmt(LoopStmt)) return false; - // TODO: In cases of while and do..while statements the value of initVarName - // should be checked to be known - // TODO: Match the cases where the bound is not a concrete literal but an - // integer with known value + // TODO: Check for possibilities of changing the bound expression. auto Matches = match(loopMatcher(), *LoopStmt, ASTCtx); - return !Matches.empty(); + if (Matches.empty()) + return false; + + const Expr *BoundExp = Matches[0].getNodeAs("BoundExp"); + const Expr *CounterExp = Matches[0].getNodeAs("CounterExp"); + auto State = Pred->getState(); + auto LCtx = Pred->getLocationContext(); + SVal BoundVal = State->getSVal(BoundExp, LCtx); + SVal CounterVal = State->getSVal(CounterExp, LCtx); + + if (!SVB.getKnownValue(State, BoundVal) || + !SVB.getKnownValue(State, CounterVal)) + return false; + + return true; } namespace { @@ -175,7 +189,7 @@ } bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev) { - const Stmt* Term = Block->getTerminator(); + const Stmt *Term = Block->getTerminator(); auto State = Prev->getState(); // In case of nested loops in an inlined function should not be unrolled only // if the inner loop is marked. @@ -186,7 +200,7 @@ llvm::SmallPtrSet BlockSet; LoopBlockVisitor LBV(BlockSet); // Check the CFGBlocks of every marked loop. - for (auto& E : State->get()) { + for (auto &E : State->get()) { SearchedBlock = Block; const StackFrameContext *StackFrame = Prev->getStackFrame(); LBV.setBlocksOfLoop(E.first, E.second); Index: test/Analysis/loop-unrolling.cpp =================================================================== --- test/Analysis/loop-unrolling.cpp +++ test/Analysis/loop-unrolling.cpp @@ -132,6 +132,26 @@ return 0; } +int known_variable_unroll() { + int a[9]; + int k = 42; + for (int i = 0; i < k; i++) { + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int known_variable_unroll2() { + int a[9]; + int k = 42; + for (int i = 0; i < k / 2 + 12; i++) { + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + // Testing while loops. int simple_unroll3() { int a[9]; @@ -193,6 +213,18 @@ return 0; } +int known_variable_unroll3() { + int a[9]; + int k = 42; + int i = 2; + do { + a[i] = 42 * i; + ++i; + } while (i < 9); + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + int simple_no_unroll5() { int a[9]; int k = 42; @@ -205,6 +237,18 @@ return 0; } +int unknown_var_no_unroll1() { + int a[9]; + int k = 42; + int i = getNum(); + do { + a[i] = 42 * i; + ++i; + } while (i < 9); + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + // CHECK: ... Statistics Collected ... // CHECK: 5 ExprEngine - The # of times we re-evaluated a call without inlining -// CHECK: 13 LoopUnrolling - The # of times a loop has got completely unrolled +// CHECK: 16 LoopUnrolling - The # of times a loop has got completely unrolled