Index: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h =================================================================== --- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h +++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h @@ -188,7 +188,17 @@ /// \brief The mode of function selection used during inlining. AnalysisInliningMode InliningMode; + enum class ExplorationStrategyKind { + DFS, + BFS, + BFSBlockDFSContents, + NotSet + }; + private: + + ExplorationStrategyKind ExplorationStrategy; + /// \brief Describes the kinds for high-level analyzer mode. enum UserModeKind { UMK_NotSet = 0, @@ -390,6 +400,8 @@ /// outside of AnalyzerOptions. UserModeKind getUserMode(); + ExplorationStrategyKind getExplorationStrategy(); + /// \brief Returns the inter-procedural analysis mode. IPAKind getIPAMode(); @@ -611,6 +623,7 @@ // Cap the stack depth at 4 calls (5 stack frames, base + 4 calls). InlineMaxStackDepth(5), InliningMode(NoRedundancy), + ExplorationStrategy(ExplorationStrategyKind::NotSet), UserMode(UMK_NotSet), IPAMode(IPAK_NotSet), CXXMemberInliningMode() {} Index: include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -21,6 +21,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h" #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" +#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" #include namespace clang { @@ -114,9 +115,9 @@ public: /// Construct a CoreEngine object to analyze the provided CFG. - CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS) - : SubEng(subengine), WList(WorkList::makeDFS()), - BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {} + CoreEngine(SubEngine &subengine, + FunctionSummariesTy *FS, + AnalyzerOptions &Opts); /// getGraph - Returns the exploded graph. ExplodedGraph &getGraph() { return G; } Index: include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h @@ -80,9 +80,9 @@ void setBlockCounter(BlockCounter C) { CurrentCounter = C; } BlockCounter getBlockCounter() const { return CurrentCounter; } - static WorkList *makeDFS(); - static WorkList *makeBFS(); - static WorkList *makeBFSBlockDFSContents(); + static std::unique_ptr makeDFS(); + static std::unique_ptr makeBFS(); + static std::unique_ptr makeBFSBlockDFSContents(); }; } // end GR namespace Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp =================================================================== --- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -55,6 +55,26 @@ return UserMode; } +AnalyzerOptions::ExplorationStrategyKind +AnalyzerOptions::getExplorationStrategy() { + if (ExplorationStrategy == ExplorationStrategyKind::NotSet) { + StringRef StratStr = Config.insert( + std::make_pair("exploration_strategy", "dfs")).first->second; + ExplorationStrategy = llvm::StringSwitch(StratStr) + .Case("dfs", ExplorationStrategyKind::DFS) + .Case("bfs", ExplorationStrategyKind::BFS) + .Case("loopstack_priority", ExplorationStrategyKind::LoopstackPriority) + .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) { Index: lib/StaticAnalyzer/Core/CoreEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/CoreEngine.cpp +++ lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -82,8 +82,13 @@ // functions, and we the code for the dstor generated in one compilation unit. WorkList::~WorkList() {} -WorkList *WorkList::makeDFS() { return new DFS(); } -WorkList *WorkList::makeBFS() { return new BFS(); } +std::unique_ptr WorkList::makeDFS() { + return llvm::make_unique(); +} + +std::unique_ptr WorkList::makeBFS() { + return llvm::make_unique(); +} namespace { class BFSBlockDFSContents : public WorkList { @@ -119,14 +124,34 @@ }; } // end anonymous namespace -WorkList* WorkList::makeBFSBlockDFSContents() { - return new BFSBlockDFSContents(); +std::unique_ptr WorkList::makeBFSBlockDFSContents() { + return llvm::make_unique(); } //===----------------------------------------------------------------------===// // Core analysis engine. //===----------------------------------------------------------------------===// +static std::unique_ptr generateWorkList(AnalyzerOptions &Opts) { + switch (Opts.getExplorationStrategy()) { + case AnalyzerOptions::ExplorationStrategyKind::DFS: + return WorkList::makeDFS(); + case AnalyzerOptions::ExplorationStrategyKind::BFS: + return WorkList::makeBFS(); + case AnalyzerOptions::ExplorationStrategyKind::BFSBlockDFSContents: + return WorkList::makeBFSBlockDFSContents(); + default: + llvm_unreachable("Unexpected case"); + } +} + +CoreEngine::CoreEngine(SubEngine &subengine, + FunctionSummariesTy *FS, + AnalyzerOptions &Opts) : SubEng(subengine), + WList(generateWorkList(Opts)), + BCounterFactory(G.getAllocator()), + FunctionSummaries(FS) {} + /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState) { Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -90,7 +90,7 @@ InliningModes HowToInlineIn) : AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), - Engine(*this, FS), + Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()), StateMgr(getContext(), mgr.getStoreManagerCreator(), mgr.getConstraintManagerCreator(), G.getAllocator(), Index: test/Analysis/analyzer-config.c =================================================================== --- test/Analysis/analyzer-config.c +++ test/Analysis/analyzer-config.c @@ -16,6 +16,7 @@ // CHECK-NEXT: cfg-lifetime = false // CHECK-NEXT: cfg-loopexit = false // CHECK-NEXT: cfg-temporary-dtors = false +// CHECK-NEXT: exploration_strategy = dfs // CHECK-NEXT: faux-bodies = true // CHECK-NEXT: graph-trim-interval = 1000 // CHECK-NEXT: inline-lambdas = true @@ -31,4 +32,4 @@ // CHECK-NEXT: unroll-loops = false // CHECK-NEXT: widen-loops = false // CHECK-NEXT: [stats] -// CHECK-NEXT: num-entries = 19 +// CHECK-NEXT: num-entries = 20 Index: test/Analysis/analyzer-config.cpp =================================================================== --- test/Analysis/analyzer-config.cpp +++ test/Analysis/analyzer-config.cpp @@ -27,6 +27,7 @@ // CHECK-NEXT: cfg-lifetime = false // CHECK-NEXT: cfg-loopexit = false // CHECK-NEXT: cfg-temporary-dtors = false +// CHECK-NEXT: exploration_strategy = dfs // CHECK-NEXT: faux-bodies = true // CHECK-NEXT: graph-trim-interval = 1000 // CHECK-NEXT: inline-lambdas = true @@ -42,4 +43,4 @@ // CHECK-NEXT: unroll-loops = false // CHECK-NEXT: widen-loops = false // CHECK-NEXT: [stats] -// CHECK-NEXT: num-entries = 24 +// CHECK-NEXT: num-entries = 25