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,8 +8,7 @@ //===----------------------------------------------------------------------===// /// /// This header contains the declarations of functions which are used to decide -/// which loops should be completely unrolled and mark their corresponding -/// CFGBlocks. +/// which loops should be completely unrolled and mark them. /// //===----------------------------------------------------------------------===// @@ -28,7 +27,8 @@ const FunctionDecl *FD); bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred, AnalysisManager &AMgr); -bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx); +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode *Pred); } // 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 @@ -1504,7 +1504,7 @@ if (AMgr.options.shouldUnrollLoops()) { const CFGBlock *ActualBlock = nodeBuilder.getContext().getBlock(); const Stmt *Term = ActualBlock->getTerminator(); - if (Term && shouldCompletelyUnroll(Term, AMgr.getASTContext())) { + if (Term && shouldCompletelyUnroll(Term, AMgr.getASTContext(), Pred)) { ProgramStateRef UnrolledState = markLoopAsUnrolled( Term, Pred->getState(), cast(Pred->getStackFrame()->getDecl())); Index: cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -8,8 +8,9 @@ //===----------------------------------------------------------------------===// /// /// This file contains functions which are used to decide if a loop worth to be -/// unrolled. Moreover contains function which mark the CFGBlocks which belongs -/// to the unrolled loop and store them in ProgramState. +/// 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. /// //===----------------------------------------------------------------------===// @@ -51,47 +52,52 @@ hasEitherOperand(ignoringParenImpCasts(integerLiteral()))); } -static internal::Matcher changeIntBoundNode(StringRef NodeName) { - return anyOf(hasDescendant(unaryOperator( - anyOf(hasOperatorName("--"), hasOperatorName("++")), - hasUnaryOperand(ignoringParenImpCasts( - declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))), - hasDescendant(binaryOperator( - anyOf(hasOperatorName("="), hasOperatorName("+="), - hasOperatorName("/="), hasOperatorName("*="), - hasOperatorName("-=")), - hasLHS(ignoringParenImpCasts( - declRefExpr(to(varDecl(equalsBoundNode(NodeName))))))))); -} - -static internal::Matcher callByRef(StringRef NodeName) { - return hasDescendant(callExpr(forEachArgumentWithParam( - declRefExpr(to(varDecl(equalsBoundNode(NodeName)))), - parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))))); -} - -static internal::Matcher assignedToRef(StringRef NodeName) { - return hasDescendant(varDecl( +static internal::Matcher +changeIntBoundNode(internal::Matcher VarNodeMatcher) { + return anyOf( + unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")), + hasUnaryOperand(ignoringParenImpCasts( + declRefExpr(to(varDecl(VarNodeMatcher)))))), + binaryOperator(anyOf(hasOperatorName("="), hasOperatorName("+="), + hasOperatorName("/="), hasOperatorName("*="), + hasOperatorName("-=")), + hasLHS(ignoringParenImpCasts( + declRefExpr(to(varDecl(VarNodeMatcher))))))); +} + +static internal::Matcher +callByRef(internal::Matcher VarNodeMatcher) { + return callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl(VarNodeMatcher))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); +} + +static internal::Matcher +assignedToRef(internal::Matcher VarNodeMatcher) { + return declStmt(hasDescendant(varDecl( allOf(hasType(referenceType()), - hasInitializer( - anyOf(initListExpr(has( - declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))), - declRefExpr(to(varDecl(equalsBoundNode(NodeName))))))))); + hasInitializer(anyOf( + initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))), + declRefExpr(to(varDecl(VarNodeMatcher))))))))); } -static internal::Matcher getAddrTo(StringRef NodeName) { - return hasDescendant(unaryOperator( +static internal::Matcher +getAddrTo(internal::Matcher VarNodeMatcher) { + return unaryOperator( hasOperatorName("&"), - hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName)))))); + hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher)))); } static internal::Matcher hasSuspiciousStmt(StringRef NodeName) { - return anyOf(hasDescendant(gotoStmt()), hasDescendant(switchStmt()), - // 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. - changeIntBoundNode(NodeName), callByRef(NodeName), - getAddrTo(NodeName), assignedToRef(NodeName)); + return hasDescendant(stmt( + anyOf(gotoStmt(), switchStmt(), + // 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. + changeIntBoundNode(equalsBoundNode(NodeName)), + callByRef(equalsBoundNode(NodeName)), + getAddrTo(equalsBoundNode(NodeName)), + assignedToRef(equalsBoundNode(NodeName))))); } static internal::Matcher forLoopMatcher() { @@ -115,16 +121,57 @@ unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop"); } -bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) { +static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) { + // Global variables assumed as escaped variables. + if (VD->hasGlobalStorage()) + return true; + + while (!N->pred_empty()) { + const Stmt *S = PathDiagnosticLocation::getStmt(N); + if (!S) { + N = N->getFirstPred(); + continue; + } + + if (const DeclStmt *DS = dyn_cast(S)) { + for (const Decl *D : DS->decls()) { + // Once we reach the declaration of the VD we can return. + if (D->getCanonicalDecl() == VD) + return false; + } + } + // Check the usage of the pass-by-ref function calls and adress-of operator + // on VD and reference initialized by VD. + ASTContext &ASTCtx = + N->getLocationContext()->getAnalysisDeclContext()->getASTContext(); + auto Match = + match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)), + assignedToRef(equalsNode(VD)))), + *S, ASTCtx); + if (!Match.empty()) + return true; + + N = N->getFirstPred(); + } + llvm_unreachable("Reached root without finding the declaration of VD"); +} + +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode *Pred) { if (!isLoopStmt(LoopStmt)) return false; // TODO: Match the cases where the bound is not a concrete literal but an // integer with known value - auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx); - return !Matches.empty(); + if (Matches.empty()) + return false; + + auto CounterVar = Matches[0].getNodeAs("initVarName"); + + // Check if the counter of the loop is not escaped before. + return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred); } namespace { @@ -185,7 +232,7 @@ // marked. while (BlockSet.find(SearchedBlock) == BlockSet.end() && StackFrame) { SearchedBlock = StackFrame->getCallSiteBlock(); - if(!SearchedBlock || StackFrame->inTopFrame()) + if (!SearchedBlock || StackFrame->inTopFrame()) break; StackFrame = StackFrame->getParent()->getCurrentStackFrame(); } 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-config unroll-loops=true -analyzer-stats -verify -std=c++11 %s +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config unroll-loops=true -verify -std=c++11 %s void clang_analyzer_numTimesReached(); @@ -24,6 +24,12 @@ clang_analyzer_numTimesReached(); // expected-warning {{9}} a[i] = 42; } + + for (int j = 0; j <= 9; ++j) { + clang_analyzer_numTimesReached(); // expected-warning {{10}} + a[j] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} return 0; } @@ -92,6 +98,45 @@ return 0; } +int escape_before_loop_no_unroll1() { + int a[9]; + int k = 42; + int i; + int &j = i; + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int escape_before_loop_no_unroll2() { + int a[9]; + int k = 42; + int i; + int *p = &i; + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int escape_before_loop_no_unroll3() { + int a[9]; + int k = 42; + int i; + foo(i); + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + int nested_outer_unrolled() { int a[9]; int k = 42;