Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h @@ -28,7 +28,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: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ 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: lib/StaticAnalyzer/Core/LoopUnrolling.cpp =================================================================== --- lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -64,25 +64,27 @@ 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 +callByRef(internal::Matcher EqualityCheck) { + return callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl(EqualityCheck))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); } -static internal::Matcher assignedToRef(StringRef NodeName) { - return hasDescendant(varDecl( +static internal::Matcher +assignedToRef(internal::Matcher EqualityCheck) { + 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(EqualityCheck))))), + declRefExpr(to(varDecl(EqualityCheck))))))))); } -static internal::Matcher getAddrTo(StringRef NodeName) { - return hasDescendant(unaryOperator( +static internal::Matcher +getAddrTo(internal::Matcher EqualityCheck) { + return unaryOperator( hasOperatorName("&"), - hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName)))))); + hasUnaryOperand(declRefExpr(hasDeclaration(EqualityCheck)))); } static internal::Matcher hasSuspiciousStmt(StringRef NodeName) { @@ -90,8 +92,10 @@ // 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)); + changeIntBoundNode(NodeName), + hasDescendant(callByRef(equalsBoundNode(NodeName))), + hasDescendant(getAddrTo(equalsBoundNode(NodeName))), + hasDescendant(assignedToRef(equalsBoundNode(NodeName)))); } static internal::Matcher forLoopMatcher() { @@ -115,16 +119,51 @@ unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop"); } -bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) { +static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) { + 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 +224,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: test/Analysis/loop-unrolling.cpp =================================================================== --- test/Analysis/loop-unrolling.cpp +++ 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;