From 2405a0addc2bc627392d9bfe2874bd9431d81d55 Mon Sep 17 00:00:00 2001
From: Ted Kremenek <kremenek@apple.com>
Date: Wed, 31 Mar 2010 18:16:59 +0000
Subject: [PATCH] Tweak DataFlowSolver's worklist data structure to have an
 ordered worklist and a DenseSet for caching instead of using a single
 SmallPtrSet. This makes the behavior of the DataFlowSolver more
 deterministic, and reduces the -fsyntax-only time on compare.c (403.gcc) by
 1%.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@100026 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../Analysis/FlowSensitive/DataflowSolver.h   | 24 ++++++++++++-------
 1 file changed, 16 insertions(+), 8 deletions(-)

diff --git a/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h
index cbf7010bfd..ebfa4e997b 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(); }
 };
 
 //===----------------------------------------------------------------------===//
-- 
2.40.0