Author: szepet Date: Sat Aug 19 03:24:52 2017 New Revision: 311234 URL: http://llvm.org/viewvc/llvm-project?rev=311234&view=rev Log: [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 Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp cfe/trunk/test/Analysis/loop-unrolling.cpp Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h?rev=311234&r1=311233&r2=311234&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h Sat Aug 19 03:24:52 2017 @@ -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 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 Modified: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp?rev=311234&r1=311233&r2=311234&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp Sat Aug 19 03:24:52 2017 @@ -1504,7 +1504,7 @@ void ExprEngine::processCFGBlockEntrance 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<FunctionDecl>(Pred->getStackFrame()->getDecl())); Modified: cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp?rev=311234&r1=311233&r2=311234&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp Sat Aug 19 03:24:52 2017 @@ -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<Stmt> simpleCon hasEitherOperand(ignoringParenImpCasts(integerLiteral()))); } -static internal::Matcher<Stmt> 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<Stmt> callByRef(StringRef NodeName) { - return hasDescendant(callExpr(forEachArgumentWithParam( - declRefExpr(to(varDecl(equalsBoundNode(NodeName)))), - parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))))); -} - -static internal::Matcher<Stmt> assignedToRef(StringRef NodeName) { - return hasDescendant(varDecl( +static internal::Matcher<Stmt> +changeIntBoundNode(internal::Matcher<Decl> 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<Stmt> +callByRef(internal::Matcher<Decl> VarNodeMatcher) { + return callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl(VarNodeMatcher))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); +} + +static internal::Matcher<Stmt> +assignedToRef(internal::Matcher<Decl> 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<Stmt> getAddrTo(StringRef NodeName) { - return hasDescendant(unaryOperator( +static internal::Matcher<Stmt> +getAddrTo(internal::Matcher<Decl> VarNodeMatcher) { + return unaryOperator( hasOperatorName("&"), - hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName)))))); + hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher)))); } static internal::Matcher<Stmt> 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<Stmt> forLoopMatcher() { @@ -115,16 +121,57 @@ static internal::Matcher<Stmt> forLoopMa 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<DeclStmt>(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<VarDecl>("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 // marked. while (BlockSet.find(SearchedBlock) == BlockSet.end() && StackFrame) { SearchedBlock = StackFrame->getCallSiteBlock(); - if(!SearchedBlock || StackFrame->inTopFrame()) + if (!SearchedBlock || StackFrame->inTopFrame()) break; StackFrame = StackFrame->getParent()->getCurrentStackFrame(); } Modified: cfe/trunk/test/Analysis/loop-unrolling.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/loop-unrolling.cpp?rev=311234&r1=311233&r2=311234&view=diff ============================================================================== --- cfe/trunk/test/Analysis/loop-unrolling.cpp (original) +++ cfe/trunk/test/Analysis/loop-unrolling.cpp Sat Aug 19 03:24:52 2017 @@ -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; } @@ -90,6 +96,45 @@ int simple_no_unroll5() { } int b = 22 / (k - 42); // no-warning 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() { _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits