Index: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h =================================================================== --- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h +++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h @@ -269,6 +269,9 @@ /// \sa shouldWidenLoops Optional WidenLoops; + /// \sa shouldUnrollLoops + Optional UnrollLoops; + /// \sa shouldDisplayNotesAsEvents Optional DisplayNotesAsEvents; @@ -540,7 +543,11 @@ /// This is controlled by the 'widen-loops' config option. bool shouldWidenLoops(); - /// Returns true if the bug reporter should transparently treat extra note + /// Returns true if the analysis should try to unroll loops with known bounds. + /// This is controlled by the 'unroll-loops' config option. + bool shouldUnrollLoops(); + + /// Returns true if the bug reporter should transparently treat extra note /// diagnostic pieces as event diagnostic pieces. Useful when the diagnostic /// consumer doesn't support the extra note pieces. /// Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h =================================================================== --- /dev/null +++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h @@ -0,0 +1,36 @@ +//===--- LoopUnrolling.h - Unroll loops -------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// This header contains the declarations of functions which are used to decide +/// which loops should be completely unrolled and mark their corresponding +/// CFGBlocks. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPUNROLLING_H +#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPUNROLLING_H + +#include "clang/Analysis/CFG.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" + +namespace clang { +namespace ento { +ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State); +bool isUnrolledLoopBlock(const CFGBlock *Block, ProgramStateRef State, + AnalysisManager &AMgr, CFGStmtMap *StmtToBlockMap); +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx); + +} // end namespace ento +} // end namespace clang + +#endif Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp =================================================================== --- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -364,6 +364,12 @@ return WidenLoops.getValue(); } +bool AnalyzerOptions::shouldUnrollLoops() { + if (!UnrollLoops.hasValue()) + UnrollLoops = getBooleanOption("unroll-loops", /*Default=*/false); + return UnrollLoops.getValue(); +} + bool AnalyzerOptions::shouldDisplayNotesAsEvents() { if (!DisplayNotesAsEvents.hasValue()) DisplayNotesAsEvents = Index: lib/StaticAnalyzer/Core/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Core/CMakeLists.txt +++ lib/StaticAnalyzer/Core/CMakeLists.txt @@ -35,6 +35,7 @@ ExprEngineObjC.cpp FunctionSummary.cpp HTMLDiagnostics.cpp + LoopUnrolling.cpp LoopWidening.cpp MemRegion.cpp PathDiagnostic.cpp @@ -54,6 +55,8 @@ LINK_LIBS clangAST + clangASTMatchers + clangDynamicASTMatchers clangAnalysis clangBasic clangLex Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -15,9 +15,14 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "PrettyStackTraceLocationContext.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/AST/StmtVisitor.h" #include "clang/AST/CharUnits.h" #include "clang/AST/ParentMap.h" +#include "clang/Analysis/CFGStmtMap.h" #include "clang/AST/StmtCXX.h" +#include "clang/AST/RecursiveASTVisitor.h" #include "clang/AST/StmtObjC.h" #include "clang/Basic/Builtins.h" #include "clang/Basic/PrettyStackTrace.h" @@ -27,6 +32,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/SaveAndRestore.h" #include "llvm/Support/raw_ostream.h" @@ -1496,6 +1502,28 @@ ExplodedNode *Pred) { PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); + // If this block is terminated by a loop which has a known bound (and meets + // other constraints) then consider completely unrolling it. + if (AMgr.options.shouldUnrollLoops()) { + const CFGBlock *ActualBlock = nodeBuilder.getContext().getBlock(); + const Stmt *Term = ActualBlock->getTerminator(); + if (Term && shouldCompletelyUnroll(Term, AMgr.getASTContext())) { + ProgramStateRef UnrolledState = + markLoopAsUnrolled(Term, Pred->getState()); + if (UnrolledState != Pred->getState()) + nodeBuilder.generateNode(UnrolledState, Pred); + return; + } + + if (isUnrolledLoopBlock(ActualBlock, Pred->getState(), AMgr, + Pred->getLocationContext() + ->getAnalysisDeclContext() + ->getCFGStmtMap())) + return; + if (ActualBlock->empty()) + return; + } + // If this block is terminated by a loop and it has already been visited the // maximum number of times, widen the loop. unsigned int BlockCount = nodeBuilder.getContext().blockCount(); Index: lib/StaticAnalyzer/Core/LoopUnrolling.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -0,0 +1,216 @@ +//===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// 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. +/// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/CFGStmtMap.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/AST/ParentMap.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" +#include "llvm/ADT/Statistic.h" + +using namespace clang; +using namespace ento; +using namespace clang::ast_matchers; + +#define DEBUG_TYPE "LoopUnrolling" + +STATISTIC(NumTimesLoopUnrolled, + "The # of times a loop has got completely unrolled"); + +REGISTER_SET_WITH_PROGRAMSTATE(UnrolledLoops, const Stmt *) +REGISTER_SET_WITH_PROGRAMSTATE(UnrolledLoopBlocks, const CFGBlock *) + +namespace clang { +namespace ento { + +static bool isLoopStmt(const Stmt *S) { + return S && (isa(S) || isa(S) || isa(S)); +} + +static internal::Matcher simpleCondition(std::string BindName) { + return binaryOperator( + anyOf(hasOperatorName("<"), hasOperatorName(">"), hasOperatorName("<="), + hasOperatorName(">="), hasOperatorName("!=")), + hasEitherOperand(ignoringParenImpCasts( + declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))))), + hasEitherOperand(ignoringParenImpCasts(integerLiteral()))); +} + +static internal::Matcher changeIntBoundNode(const std::string &NodeName) { + return hasDescendant(binaryOperator( + anyOf(hasOperatorName("="), hasOperatorName("+="), hasOperatorName("/="), + hasOperatorName("*="), hasOperatorName("-=")), + hasLHS(ignoringParenImpCasts( + declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))); +} + +static internal::Matcher callByRef(std::string NodeName) { + return hasDescendant(callExpr(forEachArgumentWithParam( + declRefExpr(hasDeclaration(equalsBoundNode(NodeName))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))))); +} + +static internal::Matcher getAddrTo(std::string NodeName) { + return hasDescendant(unaryOperator( + hasOperatorName("&"), + hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName)))))); +} + +static internal::Matcher forLoopMatcher() { + return forStmt( + hasCondition(simpleCondition("initVarName")), + // Initialization should match the form: 'int i = 6' or 'i = 7'. + hasLoopInit( + anyOf(declStmt(hasSingleDecl( + varDecl(allOf(hasInitializer(integerLiteral()), + equalsBoundNode("initVarName"))))), + binaryOperator(hasLHS(declRefExpr(to(varDecl( + equalsBoundNode("initVarName"))))), + hasRHS(integerLiteral())))), + // Incrementation should be a simple increment or decrement + // operator call. + hasIncrement(unaryOperator( + anyOf(hasOperatorName("++"), hasOperatorName("--")), + hasUnaryOperand(declRefExpr( + to(varDecl(allOf(equalsBoundNode("initVarName"), + hasType(isInteger())))))))), + // 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. + unless(hasBody(anyOf(changeIntBoundNode("initVarName"), + callByRef("initVarName"), + getAddrTo("initVarName"))))).bind("forLoop"); +} + +static internal::Matcher whileLoopMatcher() { + return whileStmt(hasCondition(simpleCondition("initVarName")), + hasBody(hasDescendant(unaryOperator( + anyOf(hasOperatorName("++"), hasOperatorName("--")), + hasUnaryOperand(declRefExpr( + to(varDecl(allOf(equalsBoundNode("initVarName"), + hasType(isInteger()))))))))), + unless(hasBody(anyOf(changeIntBoundNode("initVarName"), + callByRef("initVarName"), + getAddrTo("initVarName"))))) + .bind("whileLoop"); +} + +static internal::Matcher doWhileLoopMatcher() { + return doStmt(hasCondition(simpleCondition("initVarName")), + hasBody(hasDescendant(unaryOperator( + anyOf(hasOperatorName("++"), hasOperatorName("--")), + hasUnaryOperand(declRefExpr( + to(varDecl(allOf(equalsBoundNode("initVarName"), + hasType(isInteger()))))))))), + unless(hasBody(anyOf( + changeIntBoundNode("initVarName"), callByRef("initVarName"), + getAddrTo("initVarName"))))).bind("whileLoop"); +} + +static internal::Matcher loopMatcher() { + return anyOf(doWhileLoopMatcher(), whileLoopMatcher(), forLoopMatcher()); +} + +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) { + + if (!isLoopStmt(LoopStmt)) + return false; + + // TODO: In cases of while and do..while statements the value of initVarName + // should be checked to be known + // TODO: Match the cases where the bound is not a concrete literal but an + // integer with known value + + auto Matches = match(loopMatcher(), *LoopStmt, ASTCtx); + return !Matches.empty(); +} + +namespace { +class LoopVisitor : public ConstStmtVisitor { +public: + LoopVisitor(ProgramStateRef St, AnalysisManager &AMgr, CFGStmtMap *M) + : State(St), AMgr(AMgr), StmtToBlockMap(M), Found(false) {} + + void VisitChildren(const Stmt *S) { + for (const Stmt *Child : S->children()) + if (Child) + Visit(Child); + } + + void VisitStmt(const Stmt *S) { + if (!S || (isLoopStmt(S) && S != LoopStmt) || Found) + return; + assert(StmtToBlockMap->getBlock(S)); + if(StmtToBlockMap->getBlock(S) == SearchedBlock){ + Found = true; + return; + } + + // In case of function calls investigate their CFGBlocks as well. + auto CallExp = dyn_cast(S); + if (CallExp && CallExp->getCalleeDecl() && + CallExp->getCalleeDecl()->getBody()) { + auto CalleeCFG = AMgr.getCFG(CallExp->getCalleeDecl()); + for (auto &Block : *CalleeCFG) { + if(Block == SearchedBlock){ + Found = true; + return; + } + } + } + VisitChildren(S); + } + + bool isBlockOfLoop(const CFGBlock* B, const Stmt* Loop){ + LoopStmt = Loop; + SearchedBlock = B; + Visit(LoopStmt); + return Found; + } + +private: + ProgramStateRef State; + AnalysisManager &AMgr; + CFGStmtMap *StmtToBlockMap; + const Stmt *LoopStmt; + bool Found; + const CFGBlock* SearchedBlock; +}; +} + +bool isUnrolledLoopBlock(const CFGBlock *Block, ProgramStateRef State, AnalysisManager &AMgr, + CFGStmtMap *StmtToBlockMap) { + + for (auto Term : State->get()) { + LoopVisitor LV(State, AMgr, StmtToBlockMap); + if(LV.isBlockOfLoop(Block,Term)) + return true; + } + return false; + +} + +ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State) { + if (State->contains(Term)) + return State; + + State = State->add(Term); + ++NumTimesLoopUnrolled; + return State; +} +} +} Index: test/Analysis/analyzer-config.c =================================================================== --- test/Analysis/analyzer-config.c +++ test/Analysis/analyzer-config.c @@ -25,7 +25,7 @@ // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14 // CHECK-NEXT: mode = deep // CHECK-NEXT: region-store-small-struct-limit = 2 +// CHECK-NEXT: unroll-loops = false // CHECK-NEXT: widen-loops = false // CHECK-NEXT: [stats] -// CHECK-NEXT: num-entries = 15 - +// CHECK-NEXT: num-entries = 16 Index: test/Analysis/analyzer-config.cpp =================================================================== --- test/Analysis/analyzer-config.cpp +++ test/Analysis/analyzer-config.cpp @@ -36,6 +36,7 @@ // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14 // CHECK-NEXT: mode = deep // CHECK-NEXT: region-store-small-struct-limit = 2 +// CHECK-NEXT: unroll-loops = false // CHECK-NEXT: widen-loops = false // CHECK-NEXT: [stats] -// CHECK-NEXT: num-entries = 20 +// CHECK-NEXT: num-entries = 21 Index: test/Analysis/loop-unrolling.cpp =================================================================== --- /dev/null +++ test/Analysis/loop-unrolling.cpp @@ -0,0 +1,179 @@ +// REQUIRES: asserts +// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-config unroll-loops=true -analyzer-stats -verify %s 2>&1 | FileCheck %s + +int getNum(); +void foo(int &); +// Testing for loops. +int simple_unroll1() { + int a[9]; + int k = 42; + for (int i = 0; i < 9; i++) { + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_unroll2() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_no_unroll1() { + int a[9]; + int k = 42; + for (int i = 0; i < 9; i++) { + a[i] = 42; + foo(i); + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_no_unroll2() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + a[i] = 42; + i += getNum(); + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_no_unroll3() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + a[i] = 42; + (void)&i; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int nested_outer_unrolled() { + int a[9]; + int k = 42; + int j = 0; + for (int i = 0; i < 9; i++) { + for (j = 0; j < getNum(); ++j) { + a[j] = 22; + } + a[i] = 42; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int nested_inner_unrolled() { + int a[9]; + int k = 42; + int j = 0; + for (int i = 0; i < getNum(); i++) { + for (j = 0; j < 8; ++j) { + a[j] = 22; + } + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int nested_both_unrolled() { + int a[9]; + int k = 42; + int j = 0; + for (int i = 0; i < 7; i++) { + for (j = 0; j < 6; ++j) { + a[j] = 22; + } + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +// Testing while loops. +int simple_unroll3() { + int a[9]; + int k = 42; + int i = 0; + while (i < 9) { + a[i] = 42 * i; + ++i; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_unroll4() { + int a[22]; + int k = 42; + int i = 21; + while (i > 7) { + a[i] = 42 * i; + --i; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_no_unroll4() { + int a[9]; + int k = 42; + int i = 0; + while (i < 9) { + a[i] = 42 * i; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +// Testing do-while loops. +int simple_unroll5() { + int a[9]; + int k = 42; + int i = 0; + do { + a[i] = 42 * i; + ++i; + } while (i < 9); + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_unroll6() { + int a[22]; + int k = 42; + int i = 21; + do { + a[i] = 42 * i; + --i; + } while (i > 7); + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_no_unroll5() { + int a[9]; + int k = 42; + int i = 0; + do { + a[i] = 42 * i; + i += getNum(); + } while (i < 9); + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +// CHECK: ... Statistics Collected ... +// CHECK: 10 LoopUnrolling - The # of times a loop has got completely unrolled