Owen Anderson 2009-06-15: Use a SmallPtrSet here, for speed and to match df_iterator.

Owen Anderson 2009-06-15: Remember to clear out our maps to prevent crashing.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73438 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 18 insertions, 8 deletions

diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h
index bf7ce9d0bb..b477d0a8f0 100644
--- a/include/llvm/ADT/PostOrderIterator.h
+++ b/include/llvm/ADT/PostOrderIterator.h
@@ -18,6 +18,7 @@
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include <set>
 #include <stack>
 #include <vector>
@@ -39,9 +40,9 @@ public:
 };
 
 template<class GraphT,
-         class SetType = std::set<typename GraphTraits<GraphT>::NodeType*>,
-         bool ExtStorage = false,
-         class GT = GraphTraits<GraphT> >
+  class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>,
+  bool ExtStorage = false,
+  class GT = GraphTraits<GraphT> >
 class po_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>,
                     public po_iterator_storage<SetType, ExtStorage> {
   typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super;
diff --git a/lib/CodeGen/LazyLiveness.cpp b/lib/CodeGen/LazyLiveness.cpp
index 6fb35d235a..a951c99ddb 100644
--- a/lib/CodeGen/LazyLiveness.cpp
+++ b/lib/CodeGen/LazyLiveness.cpp
@@ -32,10 +32,12 @@ void LazyLiveness::computeBackedgeChain(MachineFunction& mf,
   calculated.set(preorder[MBB]);
   
   for (SparseBitVector<128>::iterator I = tmp.begin(); I != tmp.end(); ++I) {
+    assert(rev_preorder.size() > *I && "Unknown block!");
+    
     MachineBasicBlock* SrcMBB = rev_preorder[*I];
     
-    for (MachineBasicBlock::succ_iterator SI = SrcMBB->succ_begin();
-         SI != SrcMBB->succ_end(); ++SI) {
+    for (MachineBasicBlock::succ_iterator SI = SrcMBB->succ_begin(),
+         SE = SrcMBB->succ_end(); SI != SE; ++SI) {
       MachineBasicBlock* TgtMBB = *SI;
       
       if (backedges.count(std::make_pair(SrcMBB, TgtMBB)) &&
@@ -44,7 +46,8 @@ void LazyLiveness::computeBackedgeChain(MachineFunction& mf,
           computeBackedgeChain(mf, TgtMBB);
         
         tv[MBB].set(preorder[TgtMBB]);
-        tv[MBB] |= tv[TgtMBB];
+        SparseBitVector<128> right = tv[TgtMBB];
+        tv[MBB] |= right;
       }
     }
     
@@ -60,6 +63,12 @@ bool LazyLiveness::runOnMachineFunction(MachineFunction &mf) {
   backedge_target.clear();
   calculated.clear();
   preorder.clear();
+  rev_preorder.clear();
+  
+  rv.resize(mf.size());
+  tv.resize(mf.size());
+  preorder.resize(mf.size());
+  rev_preorder.reserve(mf.size());
   
   MRI = &mf.getRegInfo();
   MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
@@ -106,8 +115,8 @@ bool LazyLiveness::runOnMachineFunction(MachineFunction &mf) {
       for (MachineBasicBlock::succ_iterator SI = (*POI)->succ_begin(),
            SE = (*POI)->succ_end(); SI != SE; ++SI)
         if (!backedges.count(std::make_pair(*POI, *SI)) && tv.count(*SI)) {
-          SparseBitVector<128>& PBV = tv[*POI];
-          PBV = tv[*SI];
+          SparseBitVector<128> right = tv[*SI];
+          tv[*POI] |= right;
         }
   
   for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()),