Index: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h =================================================================== --- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h +++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h @@ -278,6 +278,9 @@ /// \sa shouldWidenLoops Optional WidenLoops; + /// \sa shouldUnrollLoops + Optional UnrollLoops; + /// \sa shouldDisplayNotesAsEvents Optional DisplayNotesAsEvents; @@ -570,7 +573,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,32 @@ +//===--- 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" + +namespace clang { +namespace ento { +unsigned getMaxBlockVisitOnPath(ProgramStateRef State); +ProgramStateRef setMaxBlockVisitOnPath(const Stmt *LoopStmt, ASTContext &ASTCtx, + ProgramStateRef State, unsigned DefaultVal); +ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State); +} // end namespace ento +} // end namespace clang + +#endif Index: lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp +++ lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp @@ -272,6 +272,7 @@ reportBug(llvm::to_string(NumTimesReached), BR, N); } + ReachedStats.clear(); } void ExprInspectionChecker::analyzerCrash(const CallExpr *CE, Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp =================================================================== --- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -380,6 +380,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,7 @@ LINK_LIBS clangAST + clangASTMatchers clangAnalysis clangBasic clangLex Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -17,6 +17,7 @@ #include "PrettyStackTraceLocationContext.h" #include "clang/AST/CharUnits.h" #include "clang/AST/ParentMap.h" +#include "clang/Analysis/CFGStmtMap.h" #include "clang/AST/StmtCXX.h" #include "clang/AST/StmtObjC.h" #include "clang/Basic/Builtins.h" @@ -27,6 +28,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" @@ -517,12 +519,16 @@ ExplodedNodeSet Dst; Dst.Add(Pred); NodeBuilder Bldr(Pred, Dst, *currBldrCtx); + ProgramStateRef NewState = Pred->getState(); + if(AMgr.options.shouldUnrollLoops()){ + NewState = processLoopEnd(S, NewState); + } LoopExit PP(S, Pred->getLocationContext()); - Bldr.generateNode(PP, Pred->getState(), Pred); + Bldr.generateNode(PP, NewState, Pred); + // Enqueue the new nodes onto the work list. - llvm::errs() << Pred->getLocation().getKind() << "\n"; Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); } @@ -1516,11 +1522,26 @@ NodeBuilderWithSinks &nodeBuilder, ExplodedNode *Pred) { PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); + // If we reach a loop which has a known bound (and meets + // other constraints) then consider completely unrolling it. + unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath; + if (AMgr.options.shouldUnrollLoops()) { + const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator(); + if (Term) { + ProgramStateRef NewState = setMaxBlockVisitOnPath(Term, AMgr.getASTContext(),Pred->getState(), maxBlockVisitOnPath); + if (NewState != Pred->getState()) + nodeBuilder.generateNode(NewState, Pred); + return; + } + auto UnrollingBlockVisitNum = getMaxBlockVisitOnPath(Pred->getState()); + if(UnrollingBlockVisitNum > 0) + maxBlockVisitOnPath = UnrollingBlockVisitNum; + } // 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(); - if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 && + if (BlockCount == maxBlockVisitOnPath - 1 && AMgr.options.shouldWidenLoops()) { const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator(); if (!(Term && @@ -1535,7 +1556,7 @@ } // FIXME: Refactor this into a checker. - if (BlockCount >= AMgr.options.maxBlockVisitOnPath) { + if (BlockCount >= maxBlockVisitOnPath) { static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded"); const ExplodedNode *Sink = nodeBuilder.generateSink(Pred->getState(), Pred, &tag); @@ -1683,7 +1704,6 @@ const LocationContext *LCtx = Pred->getLocationContext(); PrettyStackTraceLocationContext StackCrashInfo(LCtx); currBldrCtx = &BldCtx; - // Check for NULL conditions; e.g. "for(;;)" if (!Condition) { BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); Index: lib/StaticAnalyzer/Core/LoopUnrolling.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -0,0 +1,179 @@ +//===--- 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/CheckerContext.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_LIST_WITH_PROGRAMSTATE(MaxBlockVisitStack, const llvm::APInt) +REGISTER_LIST_WITH_PROGRAMSTATE(UnrolledLoopStack, const Stmt *) + +namespace clang { +namespace ento { + +static bool isLoopStmt(const Stmt *S) { + return S && (isa(S) || isa(S) || isa(S)); +} + +ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { + auto ULS = State->get(); + assert(LoopStmt == ULS.getHead()); + auto MBVS = State->get(); + State = State->set(ULS.getTail()); + State = State->set(MBVS.getTail()); + return State; +} + +static internal::Matcher simpleCondition(StringRef BindName) { + return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"), + hasOperatorName("<="), hasOperatorName(">="), + hasOperatorName("!=")), + hasEitherOperand(ignoringParenImpCasts(declRefExpr( + to(varDecl(hasType(isInteger())).bind(BindName))))), + hasEitherOperand(ignoringParenImpCasts( + integerLiteral().bind("counterEndVal")))) + .bind("condition"); +} + +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 callByRef(StringRef NodeName) { + return hasDescendant(callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl(equalsBoundNode(NodeName)))), + 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))))))))); +} + +static internal::Matcher getAddrTo(StringRef NodeName) { + return hasDescendant(unaryOperator( + hasOperatorName("&"), + hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName)))))); +} + +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)); +} + +static internal::Matcher forLoopMatcher() { + return forStmt( + hasCondition(simpleCondition("initVarName")), + // Initialization should match the form: 'int i = 6' or 'i = 42'. + hasLoopInit(anyOf( + declStmt(hasSingleDecl(varDecl(allOf( + hasInitializer(integerLiteral().bind("counterStartVal")), + equalsBoundNode("initVarName"))))), + binaryOperator( + hasLHS(declRefExpr( + to(varDecl(equalsBoundNode("initVarName"))))), + hasRHS(integerLiteral().bind("counterStartVal"))))), + // Incrementation should be a simple increment or decrement + // operator call. + hasIncrement( + unaryOperator( + anyOf(hasOperatorName("++"), hasOperatorName("--")), + hasUnaryOperand(declRefExpr(to(varDecl( + allOf(equalsBoundNode("initVarName"), + hasType(isInteger()))))))).bind("stepOperator")), + unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop"); +} + +ProgramStateRef setMaxBlockVisitOnPath(const Stmt *LoopStmt, ASTContext &ASTCtx, + ProgramStateRef State, + unsigned DefaultVal) { + if (!isLoopStmt(LoopStmt)) + return State; + + // TODO: Match the cases where the bound is not a concrete literal but an + // integer with known value + + auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx); + + auto ULS = State->get(); + if (!ULS.isEmpty() && LoopStmt == ULS.getHead()) + return State; + + if (Matches.empty()) { + State = State->add(llvm::APInt(8, DefaultVal)); + State = State->add(LoopStmt); + return State; + } + + llvm::APInt Start = + Matches[0].getNodeAs("counterStartVal")->getValue(); + llvm::APInt End = + Matches[0].getNodeAs("counterEndVal")->getValue(); + llvm::APInt Diff = (End - Start).abs(); + auto Cond = Matches[0].getNodeAs("condition"); + if (Cond->getOpcode() == BO_GE || Cond->getOpcode() == BO_LE) + Diff++; + auto MBVS = State->get(); + llvm::APInt OuterVisitNum = llvm::APInt(Diff.getBitWidth(), 1); + if (!MBVS.isEmpty() && MBVS.getHead().getLimitedValue() != DefaultVal) + OuterVisitNum = + llvm::APInt(Diff.getBitWidth(), MBVS.getHead().getLimitedValue()); + + Diff *= OuterVisitNum; + State = State->add(Diff.abs()); + State = State->add(LoopStmt); + return State; +} + +unsigned getMaxBlockVisitOnPath(ProgramStateRef State) { + auto MBVS = State->get(); + if (MBVS.isEmpty()) + return 0; + return MBVS.getHead().getLimitedValue(UINT_MAX); +} +} +} Index: test/Analysis/analyzer-config.c =================================================================== --- test/Analysis/analyzer-config.c +++ test/Analysis/analyzer-config.c @@ -28,6 +28,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 = 18 +// CHECK-NEXT: num-entries = 19 Index: test/Analysis/analyzer-config.cpp =================================================================== --- test/Analysis/analyzer-config.cpp +++ test/Analysis/analyzer-config.cpp @@ -39,6 +39,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 = 23 +// CHECK-NEXT: num-entries = 24 Index: test/Analysis/loop-unrolling.cpp =================================================================== --- /dev/null +++ test/Analysis/loop-unrolling.cpp @@ -0,0 +1,181 @@ +// REQUIRES: asserts +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true -analyzer-stats -verify -std=c++11 %s 2>&1 | FileCheck %s + +void clang_analyzer_numTimesReached(); + +int getNum(); +void foo(int &); +// Testing for loops. +int simple_unroll1() { + int a[9]; + int k = 42; + for (int i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{9}} + 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++) { + clang_analyzer_numTimesReached(); // expected-warning {{9}} + 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++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + 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++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + 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++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + (void)&i; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int simple_no_unroll4() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + int &j = i; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int simple_no_unroll5() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + int &j{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++) { + clang_analyzer_numTimesReached(); // expected-warning {{16}} + for (j = 0; j < getNum(); ++j) { + clang_analyzer_numTimesReached(); // expected-warning {{15}} + 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++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + for (j = 0; j < 8; ++j) { + clang_analyzer_numTimesReached(); // expected-warning {{32}} + 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++) { + clang_analyzer_numTimesReached(); // expected-warning {{7}} + for (j = 0; j < 6; ++j) { + clang_analyzer_numTimesReached(); // expected-warning {{42}} + a[j] = 22; + } + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_known_bound_loop() { + for (int i = 2; i < 12; i++) { + // This function is inlined in nested_inlined_unroll1() + clang_analyzer_numTimesReached(); // expected-warning {{90}} + } + return 0; +} + +int simple_unknown_bound_loop() { + for (int i = 2; i < getNum(); i++) { + clang_analyzer_numTimesReached(); // expected-warning {{10}} + } + return 0; +} + +int nested_inlined_unroll1() { + int k; + for (int i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{9}} + k = simple_known_bound_loop(); // no reevaluation without inlining + } + int a = 22 / k; // expected-warning {{Division by zero}} + return 0; +} + +int nested_inlined_no_unroll1() { + int k; + for (int i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{26}} + k = simple_unknown_bound_loop(); // reevaluation without inlining + } + int a = 22 / k; // no-warning + return 0; +} + +// CHECK: ... Statistics Collected ... +// CHECK: 5 ExprEngine - The # of times we re-evaluated a call without inlining +// CHECK: 9 LoopUnrolling - The # of times a loop has got completely unrolled