Author: szepet Date: Wed Jul 19 16:50:00 2017 New Revision: 308558 URL: http://llvm.org/viewvc/llvm-project?rev=308558&view=rev Log: This feature allows the analyzer to consider loops to completely unroll. New requirements/rules (for unrolling) can be added easily via ASTMatchers.
The current implementation is hidden behind a flag. Right now the blocks which belong to an unrolled loop are marked by the LoopVisitor which adds them to the ProgramState. Then whenever we encounter a CFGBlock in the processCFGBlockEntrance which is marked then we skip its investigating. That means, it won't be considered to be visited more than the maximal bound for visiting since it won't be checked. Differential Revision: https://reviews.llvm.org/D34260 Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h cfe/trunk/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp cfe/trunk/test/Analysis/analyzer-config.c cfe/trunk/test/Analysis/analyzer-config.cpp Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h?rev=308558&r1=308557&r2=308558&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h Wed Jul 19 16:50:00 2017 @@ -275,6 +275,9 @@ private: /// \sa shouldWidenLoops Optional<bool> WidenLoops; + /// \sa shouldUnrollLoops + Optional<bool> UnrollLoops; + /// \sa shouldDisplayNotesAsEvents Optional<bool> DisplayNotesAsEvents; @@ -560,7 +563,11 @@ public: /// 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. /// Modified: cfe/trunk/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp?rev=308558&r1=308557&r2=308558&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp Wed Jul 19 16:50:00 2017 @@ -272,6 +272,7 @@ void ExprInspectionChecker::checkEndAnal reportBug(llvm::to_string(NumTimesReached), BR, N); } + ReachedStats.clear(); } void ExprInspectionChecker::analyzerCrash(const CallExpr *CE, Modified: cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp?rev=308558&r1=308557&r2=308558&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp Wed Jul 19 16:50:00 2017 @@ -375,6 +375,12 @@ bool AnalyzerOptions::shouldWidenLoops() 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 = Modified: cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt?rev=308558&r1=308557&r2=308558&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt Wed Jul 19 16:50:00 2017 @@ -35,6 +35,7 @@ add_clang_library(clangStaticAnalyzerCor ExprEngineObjC.cpp FunctionSummary.cpp HTMLDiagnostics.cpp + LoopUnrolling.cpp LoopWidening.cpp MemRegion.cpp PathDiagnostic.cpp @@ -54,6 +55,7 @@ add_clang_library(clangStaticAnalyzerCor LINK_LIBS clangAST + clangASTMatchers clangAnalysis clangBasic clangLex Modified: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp?rev=308558&r1=308557&r2=308558&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp Wed Jul 19 16:50:00 2017 @@ -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" @@ -1497,6 +1499,27 @@ void ExprEngine::processCFGBlockEntrance 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. + 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(), + Pred->getLocationContext() + ->getAnalysisDeclContext() + ->getCFGStmtMap()); + if (UnrolledState != Pred->getState()) + nodeBuilder.generateNode(UnrolledState, Pred); + return; + } + + if (isUnrolledLoopBlock(ActualBlock, Pred)) + 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. @@ -1664,7 +1687,6 @@ void ExprEngine::processBranch(const Stm 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); Modified: cfe/trunk/test/Analysis/analyzer-config.c URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/analyzer-config.c?rev=308558&r1=308557&r2=308558&view=diff ============================================================================== --- cfe/trunk/test/Analysis/analyzer-config.c (original) +++ cfe/trunk/test/Analysis/analyzer-config.c Wed Jul 19 16:50:00 2017 @@ -27,6 +27,7 @@ void foo() { // 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 = 17 +// CHECK-NEXT: num-entries = 18 Modified: cfe/trunk/test/Analysis/analyzer-config.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/analyzer-config.cpp?rev=308558&r1=308557&r2=308558&view=diff ============================================================================== --- cfe/trunk/test/Analysis/analyzer-config.cpp (original) +++ cfe/trunk/test/Analysis/analyzer-config.cpp Wed Jul 19 16:50:00 2017 @@ -38,6 +38,7 @@ public: // 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 = 22 +// CHECK-NEXT: num-entries = 23 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits