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

1 files changed, 23 insertions, 1 deletions

diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp
index e4f27b60cf..46a2173c96 100644
--- a/lib/Analysis/GRCoreEngine.cpp
+++ b/lib/Analysis/GRCoreEngine.cpp
@@ -47,13 +47,35 @@ public:
     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 {