Index: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h =================================================================== --- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h +++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h @@ -191,6 +191,7 @@ enum class ExplorationStrategyKind { DFS, BFS, + UnexploredFirst, BFSBlockDFSContents, NotSet }; Index: include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h @@ -83,6 +83,7 @@ static std::unique_ptr makeDFS(); static std::unique_ptr makeBFS(); static std::unique_ptr makeBFSBlockDFSContents(); + static std::unique_ptr makeUnexploredFirst(); }; } // end GR namespace Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp =================================================================== --- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -58,23 +58,25 @@ 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."); + 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("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) { Index: lib/StaticAnalyzer/Core/CoreEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/CoreEngine.cpp +++ lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -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; @@ -128,6 +129,61 @@ return llvm::make_unique(); } +class UnexploredFirstStack : public WorkList { + + /// Stack of nodes known to have statements we have not traversed yet. + SmallVector StackUnexplored; + + /// Stack of all other nodes. + SmallVector StackOthers; + + typedef unsigned BlockID; + typedef std::pair LocIdentifier; + llvm::DenseSet 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(); + + if (!BE) { + // Assume unexplored. + StackUnexplored.push_back(U); + return; + } + + LocIdentifier LocId = + std::make_pair(BE->getDst()->getBlockID(), N->getStackFrame()); + + if (!reachable.count(LocId)) { + StackUnexplored.push_back(U); + } else { + StackOthers.push_back(U); + } + reachable.insert(LocId); + } + + 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::makeUnexploredFirst() { + return llvm::make_unique(); +} + //===----------------------------------------------------------------------===// // Core analysis engine. //===----------------------------------------------------------------------===// @@ -140,6 +196,8 @@ return WorkList::makeBFS(); case AnalyzerOptions::ExplorationStrategyKind::BFSBlockDFSContents: return WorkList::makeBFSBlockDFSContents(); + case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirst: + return WorkList::makeUnexploredFirst(); default: llvm_unreachable("Unexpected case"); } Index: test/Analysis/exploration_order/prefer_unexplored.cc =================================================================== --- /dev/null +++ test/Analysis/exploration_order/prefer_unexplored.cc @@ -0,0 +1,19 @@ +// 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'}} +}