From e017f9615d3a4ff53f47984e8293ef68361cf3cf Mon Sep 17 00:00:00 2001 From: Peter Szecsi Date: Sat, 19 Aug 2017 10:24:52 +0000 Subject: [PATCH] [StaticAnalyzer] LoopUnrolling: Exclude cases where the counter is escaped before the loop Adding escape check for the counter variable of the loop. It is achieved by jumping back on the ExplodedGraph to its declStmt. Differential Revision: https://reviews.llvm.org/D35657 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@311234 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Core/PathSensitive/LoopUnrolling.h | 6 +- lib/StaticAnalyzer/Core/ExprEngine.cpp | 2 +- lib/StaticAnalyzer/Core/LoopUnrolling.cpp | 119 ++++++++++++------ test/Analysis/loop-unrolling.cpp | 47 ++++++- 4 files changed, 133 insertions(+), 41 deletions(-) diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h b/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h index 54c943e531..b76f251882 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h +++ b/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 @@ ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State, 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 diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp index 2970a6c879..835b353686 100644 --- a/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1504,7 +1504,7 @@ void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, 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())); diff --git a/lib/StaticAnalyzer/Core/LoopUnrolling.cpp b/lib/StaticAnalyzer/Core/LoopUnrolling.cpp index dd37cbd218..df5d792542 100644 --- a/lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ b/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 @@ static internal::Matcher simpleCondition(StringRef BindName) { 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 +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(StringRef NodeName) { - return hasDescendant(callExpr(forEachArgumentWithParam( - declRefExpr(to(varDecl(equalsBoundNode(NodeName)))), - parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))))); +static internal::Matcher +callByRef(internal::Matcher VarNodeMatcher) { + return callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl(VarNodeMatcher))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); } -static internal::Matcher assignedToRef(StringRef NodeName) { - return hasDescendant(varDecl( +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 @@ static internal::Matcher forLoopMatcher() { 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 @@ bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred, // marked. while (BlockSet.find(SearchedBlock) == BlockSet.end() && StackFrame) { SearchedBlock = StackFrame->getCallSiteBlock(); - if(!SearchedBlock || StackFrame->inTopFrame()) + if (!SearchedBlock || StackFrame->inTopFrame()) break; StackFrame = StackFrame->getParent()->getCurrentStackFrame(); } diff --git a/test/Analysis/loop-unrolling.cpp b/test/Analysis/loop-unrolling.cpp index 9381c4c7d9..51261e3ee1 100644 --- a/test/Analysis/loop-unrolling.cpp +++ b/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 @@ int simple_unroll2() { 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 @@ int simple_no_unroll5() { 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; -- 2.40.0