Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h @@ -24,8 +24,9 @@ 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); +bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred); +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(), Pred->getLocationContext() Index: lib/StaticAnalyzer/Core/LoopUnrolling.cpp =================================================================== --- lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -69,13 +69,19 @@ parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))))); } +static internal::Matcher callByRef(const Decl *D) { + return callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl(equalsNode(D)))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); +} + static internal::Matcher assignedToRef(StringRef NodeName) { return 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(equalsBoundNode(NodeName)))))), + declRefExpr(to(varDecl(equalsBoundNode(NodeName))))))))); } static internal::Matcher getAddrTo(StringRef NodeName) { @@ -114,8 +120,52 @@ unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop"); } -bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) { +static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) { + if (N->pred_empty()) + assert("Reached root without finding the declaration of VD"); + const Stmt *S = PathDiagnosticLocation::getStmt(N); + if (!S) + return isPossiblyEscaped(VD, N->getFirstPred()); + + 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 if a reference is initialized by the variable. + if (auto V = dyn_cast(D)) { + if (!V->getInit()) + continue; + auto DRE = dyn_cast(V->getInit()->IgnoreParenImpCasts()); + if (DRE && isa(V->getType()) && + DRE->getDecl()->getCanonicalDecl() == VD) + return true; + } + } + } + // Check the usage of the adress-of operator on VD. + do { + auto UO = dyn_cast(S); + if (!UO || UO->getOpcode() != UO_AddrOf) + break; + auto DRE = dyn_cast(UO->getSubExpr()->IgnoreParenImpCasts()); + if (DRE && DRE->getDecl()->getCanonicalDecl() == VD) + return true; + } while (false); + + // Check for pass-by-ref function calls. + auto Match = + match(callByRef(VD), *S, + N->getLocationContext()->getAnalysisDeclContext()->getASTContext()); + if (!Match.empty()) + return true; + + return isPossiblyEscaped(VD, N->getFirstPred()); +} +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode *Pred) { if (!isLoopStmt(LoopStmt)) return false; @@ -123,7 +173,13 @@ // 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 { @@ -158,12 +214,10 @@ const Stmt *LoopStmt; }; } -// TODO: refactor this function using ScopeContext - once we have the -// information when the simulation reaches the end of the loop we can cleanup -// the state -bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev) { + +bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred) { const Stmt *Term = Block->getTerminator(); - auto State = Prev->getState(); + auto State = Pred->getState(); // In case of nested loops in an inlined function should not be unrolled only // if the inner loop is marked. if (Term && isLoopStmt(Term) && !State->contains(Term)) @@ -175,7 +229,7 @@ // Check the CFGBlocks of every marked loop. for (auto &E : State->get()) { SearchedBlock = Block; - const StackFrameContext *StackFrame = Prev->getStackFrame(); + const StackFrameContext *StackFrame = Pred->getStackFrame(); LBV.setBlocksOfLoop(E.first, E.second); // In case of an inlined function call check if any of its callSiteBlock is // marked. Index: test/Analysis/loop-unrolling.cpp =================================================================== --- test/Analysis/loop-unrolling.cpp +++ test/Analysis/loop-unrolling.cpp @@ -93,6 +93,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; @@ -160,7 +199,7 @@ int k; for (int i = 0; i < 9; i++) { clang_analyzer_numTimesReached(); // expected-warning {{9}} - k = simple_known_bound_loop(); // no reevaluation without inlining + k = simple_known_bound_loop(); // no reevaluation without inlining } int a = 22 / k; // expected-warning {{Division by zero}} return 0; @@ -170,7 +209,7 @@ int k; for (int i = 0; i < 9; i++) { clang_analyzer_numTimesReached(); // expected-warning {{26}} - k = simple_unknown_bound_loop(); // reevaluation without inlining + k = simple_unknown_bound_loop(); // reevaluation without inlining } int a = 22 / k; // no-warning return 0;