1 files changed, 33 insertions, 12 deletions
diff --git a/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h
index cbf7010bfdb53..3c762011a6575 100644
--- a/include/clang/Analysis/FlowSensitive/DataflowSolver.h
+++ b/include/clang/Analysis/FlowSensitive/DataflowSolver.h
@@ -17,7 +17,8 @@
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/ProgramPoint.h"
 #include "clang/Analysis/FlowSensitive/DataflowValues.h"
-#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
 #include "functional" // STL
 
 namespace clang {
@@ -28,23 +29,30 @@ namespace clang {
 //===----------------------------------------------------------------------===//
 
 class DataflowWorkListTy {
-  typedef llvm::SmallPtrSet<const CFGBlock*,20> BlockSet;
-  BlockSet wlist;
+  llvm::DenseMap<const CFGBlock*, unsigned char> BlockSet;
+  llvm::SmallVector<const CFGBlock *, 10> BlockQueue;
 public:
   /// enqueue - Add a block to the worklist.  Blocks already on the
   ///  worklist are not added a second time.
-  void enqueue(const CFGBlock* B) { wlist.insert(B); }
+  void enqueue(const CFGBlock* B) {
+    unsigned char &x = BlockSet[B];
+    if (x == 1)
+      return;
+    x = 1;
+    BlockQueue.push_back(B);
+  }
 
   /// dequeue - Remove a block from the worklist.
   const CFGBlock* dequeue() {
-    assert (!wlist.empty());
-    const CFGBlock* B = *wlist.begin();
-    wlist.erase(B);
+    assert(!BlockQueue.empty());
+    const CFGBlock *B = BlockQueue.back();
+    BlockQueue.pop_back();
+    BlockSet[B] = 0;
     return B;
   }
 
   /// isEmpty - Return true if the worklist is empty.
-  bool isEmpty() const { return wlist.empty(); }
+  bool isEmpty() const { return BlockQueue.empty(); }
 };
 
 //===----------------------------------------------------------------------===//
@@ -188,10 +196,7 @@ private:
   /// SolveDataflowEquations - Perform the actual worklist algorithm
   ///  to compute dataflow values.
   void SolveDataflowEquations(CFG& cfg, bool recordStmtValues) {
-    // Enqueue all blocks to ensure the dataflow values are computed
-    // for every block.  Not all blocks are guaranteed to reach the exit block.
-    for (CFG::iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I)
-      WorkList.enqueue(&**I);
+    EnqueueBlocksOnWorklist(cfg, AnalysisDirTag());
 
     while (!WorkList.isEmpty()) {
       const CFGBlock* B = WorkList.dequeue();
@@ -201,6 +206,22 @@ private:
     }
   }
 
+  void EnqueueBlocksOnWorklist(CFG &cfg, dataflow::forward_analysis_tag) {
+    // Enqueue all blocks to ensure the dataflow values are computed
+    // for every block.  Not all blocks are guaranteed to reach the exit block.
+    for (CFG::iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I)
+      WorkList.enqueue(&**I);
+  }
+
+  void EnqueueBlocksOnWorklist(CFG &cfg, dataflow::backward_analysis_tag) {
+    // Enqueue all blocks to ensure the dataflow values are computed
+    // for every block.  Not all blocks are guaranteed to reach the exit block.
+    // Enqueue in reverse order since that will more likely match with
+    // the order they should ideally processed by the dataflow algorithm.
+    for (CFG::reverse_iterator I=cfg.rbegin(), E=cfg.rend(); I!=E; ++I)
+      WorkList.enqueue(&**I);
+  }
+
   void ProcessMerge(CFG& cfg, const CFGBlock* B) {
     ValTy& V = TF.getVal();
     TF.SetTopValue(V);