Add a new BFS GRWorkList and make it the default worklist model for
GRCoreEngine. This tends to result in shorter paths for pathological cases.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@70585 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/include/clang/Analysis/PathSensitive/GRCoreEngine.h
index fe8634e..93c2884 100644
--- a/include/clang/Analysis/PathSensitive/GRCoreEngine.h
+++ b/include/clang/Analysis/PathSensitive/GRCoreEngine.h
@@ -631,7 +631,7 @@
/// a DFS exploration of the exploded graph.
GRCoreEngine(CFG& cfg, Decl& cd, ASTContext& ctx, SubEngineTy& subengine)
: GRCoreEngineImpl(new GraphTy(cfg, cd, ctx),
- GRWorkList::MakeBFSBlockDFSContents()),
+ GRWorkList::MakeBFS()),
SubEngine(subengine) {}
/// Construct a GRCoreEngine object to analyze the provided CFG and to
diff --git a/include/clang/Analysis/PathSensitive/GRWorkList.h b/include/clang/Analysis/PathSensitive/GRWorkList.h
index de7ea5e..c765322 100644
--- a/include/clang/Analysis/PathSensitive/GRWorkList.h
+++ b/include/clang/Analysis/PathSensitive/GRWorkList.h
@@ -68,8 +68,9 @@
void setBlockCounter(GRBlockCounter C) { CurrentCounter = C; }
GRBlockCounter getBlockCounter() const { return CurrentCounter; }
- static GRWorkList* MakeDFS();
- static GRWorkList* MakeBFSBlockDFSContents();
+ static GRWorkList *MakeDFS();
+ static GRWorkList *MakeBFS();
+ static GRWorkList *MakeBFSBlockDFSContents();
};
} // end clang namespace
#endif
diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp
index e4f27b6..46a2173 100644
--- a/lib/Analysis/GRCoreEngine.cpp
+++ b/lib/Analysis/GRCoreEngine.cpp
@@ -47,13 +47,35 @@
return U;
}
};
+
+class VISIBILITY_HIDDEN BFS : public GRWorkList {
+ std::queue<GRWorkListUnit> Queue;
+public:
+ virtual bool hasWork() const {
+ return !Queue.empty();
+ }
+
+ virtual void Enqueue(const GRWorkListUnit& U) {
+ Queue.push(U);
+ }
+
+ virtual GRWorkListUnit Dequeue() {
+ // Don't use const reference. The subsequent pop_back() might make it
+ // unsafe.
+ GRWorkListUnit U = Queue.front();
+ Queue.pop();
+ return U;
+ }
+};
+
} // end anonymous namespace
// Place the dstor for GRWorkList here because it contains virtual member
// functions, and we the code for the dstor generated in one compilation unit.
GRWorkList::~GRWorkList() {}
-GRWorkList* GRWorkList::MakeDFS() { return new DFS(); }
+GRWorkList *GRWorkList::MakeDFS() { return new DFS(); }
+GRWorkList *GRWorkList::MakeBFS() { return new BFS(); }
namespace {
class VISIBILITY_HIDDEN BFSBlockDFSContents : public GRWorkList {