Author: george.karpenkov Date: Mon Feb 12 14:39:57 2018 New Revision: 324956
URL: http://llvm.org/viewvc/llvm-project?rev=324956&view=rev Log: [analyzer] Exploration strategy prioritizing unexplored coverage first See reviews.llvm.org/M1 for evaluation, and lists.llvm.org/pipermail/cfe-dev/2018-January/056718.html for discussion. Differential Revision: https://reviews.llvm.org/D42775 Added: cfe/trunk/test/Analysis/exploration_order/ cfe/trunk/test/Analysis/exploration_order/prefer_unexplored.cc Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.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=324956&r1=324955&r2=324956&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h Mon Feb 12 14:39:57 2018 @@ -191,6 +191,7 @@ public: enum class ExplorationStrategyKind { DFS, BFS, + UnexploredFirst, BFSBlockDFSContents, NotSet }; Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h?rev=324956&r1=324955&r2=324956&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h Mon Feb 12 14:39:57 2018 @@ -83,6 +83,7 @@ public: static std::unique_ptr<WorkList> makeDFS(); static std::unique_ptr<WorkList> makeBFS(); static std::unique_ptr<WorkList> makeBFSBlockDFSContents(); + static std::unique_ptr<WorkList> makeUnexploredFirst(); }; } // end GR namespace Modified: cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp?rev=324956&r1=324955&r2=324956&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp Mon Feb 12 14:39:57 2018 @@ -58,22 +58,25 @@ AnalyzerOptions::UserModeKind AnalyzerOp AnalyzerOptions::ExplorationStrategyKind AnalyzerOptions::getExplorationStrategy() { if (ExplorationStrategy == ExplorationStrategyKind::NotSet) { - StringRef StratStr = Config.insert( - std::make_pair("exploration_strategy", "dfs")).first->second; - ExplorationStrategy = llvm::StringSwitch<ExplorationStrategyKind>(StratStr) - .Case("dfs", ExplorationStrategyKind::DFS) - .Case("bfs", ExplorationStrategyKind::BFS) - .Case("bfs_block_dfs_contents", ExplorationStrategyKind::BFSBlockDFSContents) - .Default(ExplorationStrategyKind::NotSet); - assert(ExplorationStrategy != ExplorationStrategyKind::NotSet - && "User mode is invalid."); + StringRef StratStr = + Config + .insert(std::make_pair("exploration_strategy", "dfs")) + .first->second; + ExplorationStrategy = + llvm::StringSwitch<ExplorationStrategyKind>(StratStr) + .Case("dfs", ExplorationStrategyKind::DFS) + .Case("bfs", ExplorationStrategyKind::BFS) + .Case("unexplored_first", + ExplorationStrategyKind::UnexploredFirst) + .Case("bfs_block_dfs_contents", + ExplorationStrategyKind::BFSBlockDFSContents) + .Default(ExplorationStrategyKind::NotSet); + assert(ExplorationStrategy != ExplorationStrategyKind::NotSet && + "User mode is invalid."); } return ExplorationStrategy; - } - - IPAKind AnalyzerOptions::getIPAMode() { if (IPAMode == IPAK_NotSet) { Modified: cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp?rev=324956&r1=324955&r2=324956&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp Mon Feb 12 14:39:57 2018 @@ -19,6 +19,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/Support/Casting.h" using namespace clang; @@ -33,6 +34,9 @@ STATISTIC(NumReachedMaxSteps, STATISTIC(NumPathsExplored, "The # of paths explored by the analyzer."); +STATISTIC(MaxQueueSize, "Maximum size of the worklist"); +STATISTIC(MaxReachableSize, "Maximum size of auxiliary worklist set"); + //===----------------------------------------------------------------------===// // Worklist classes for exploration of reachable states. //===----------------------------------------------------------------------===// @@ -128,6 +132,64 @@ std::unique_ptr<WorkList> WorkList::make return llvm::make_unique<BFSBlockDFSContents>(); } +class UnexploredFirstStack : public WorkList { + + /// Stack of nodes known to have statements we have not traversed yet. + SmallVector<WorkListUnit, 20> StackUnexplored; + + /// Stack of all other nodes. + SmallVector<WorkListUnit, 20> StackOthers; + + typedef unsigned BlockID; + typedef std::pair<BlockID, const StackFrameContext *> LocIdentifier; + llvm::DenseSet<LocIdentifier> Reachable; + +public: + bool hasWork() const override { + return !(StackUnexplored.empty() && StackOthers.empty()); + } + + void enqueue(const WorkListUnit &U) override { + const ExplodedNode *N = U.getNode(); + auto BE = N->getLocation().getAs<BlockEntrance>(); + + if (!BE) { + + // Assume the choice of the order of the preceeding block entrance was + // correct. + StackUnexplored.push_back(U); + } else { + LocIdentifier LocId = std::make_pair( + BE->getBlock()->getBlockID(), N->getStackFrame()); + auto InsertInfo = Reachable.insert(LocId); + + if (InsertInfo.second) { + StackUnexplored.push_back(U); + } else { + StackOthers.push_back(U); + } + } + MaxReachableSize.updateMax(Reachable.size()); + MaxQueueSize.updateMax(StackUnexplored.size() + StackOthers.size()); + } + + WorkListUnit dequeue() override { + if (!StackUnexplored.empty()) { + WorkListUnit &U = StackUnexplored.back(); + StackUnexplored.pop_back(); + return U; + } else { + WorkListUnit &U = StackOthers.back(); + StackOthers.pop_back(); + return U; + } + } +}; + +std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() { + return llvm::make_unique<UnexploredFirstStack>(); +} + //===----------------------------------------------------------------------===// // Core analysis engine. //===----------------------------------------------------------------------===// @@ -140,6 +202,8 @@ static std::unique_ptr<WorkList> generat return WorkList::makeBFS(); case AnalyzerOptions::ExplorationStrategyKind::BFSBlockDFSContents: return WorkList::makeBFSBlockDFSContents(); + case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirst: + return WorkList::makeUnexploredFirst(); default: llvm_unreachable("Unexpected case"); } Added: cfe/trunk/test/Analysis/exploration_order/prefer_unexplored.cc URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/exploration_order/prefer_unexplored.cc?rev=324956&view=auto ============================================================================== --- cfe/trunk/test/Analysis/exploration_order/prefer_unexplored.cc (added) +++ cfe/trunk/test/Analysis/exploration_order/prefer_unexplored.cc Mon Feb 12 14:39:57 2018 @@ -0,0 +1,39 @@ +// RUN: %clang_analyze_cc1 -w -analyzer-checker=core -analyzer-config exploration_strategy=unexplored_first -analyzer-output=text -verify %s | FileCheck %s + +extern int coin(); + +int foo() { + int *x = 0; // expected-note {{'x' initialized to a null pointer value}} + while (coin()) { // expected-note{{Loop condition is true}} + if (coin()) // expected-note {{Taking true branch}} + return *x; // expected-warning{{Dereference of null pointer (loaded from variable 'x')}} + // expected-note@-1{{Dereference of null pointer (loaded from variable 'x')}} + } + return 0; +} + +void bar() { + while(coin()) // expected-note{{Loop condition is true}} + if (coin()) // expected-note {{Assuming the condition is true}} + foo(); // expected-note{{Calling 'foo'}} +} + +int foo2() { + int *x = 0; // expected-note {{'x' initialized to a null pointer value}} + while (coin()) { // expected-note{{Loop condition is true}} + if (coin()) // expected-note {{Taking false branch}} + return false; + else + return *x; // expected-warning{{Dereference of null pointer (loaded from variable 'x')}} + // expected-note@-1{{Dereference of null pointer (loaded from variable 'x')}} + } + return 0; +} + +void bar2() { + while(coin()) // expected-note{{Loop condition is true}} + if (coin()) // expected-note {{Assuming the condition is false}} + return false; + else + foo(); // expected-note{{Calling 'foo'}} +} _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
