commit f7a82b422fa0428fb5678d91804610d56398b478
author Jean Christophe Beyler <jean.christophe.beyler@intel.com> Mon Feb 10 22:12:58 2014 -0800
committer buzbee <buzbee@google.com> Tue Feb 25 12:20:24 2014 -0800
tree 55582fcfd2d4e734e4709e96afcc14be690c494a
parent 3fcf18e25241253f23efbeebe77b2a4c4a7c54d3

Implements a BasicBlock iterator using the ArenaBitVector.

Added the implementation of a BasicBlock iterator using the ArenaBitVector.
This patch only adds the implementation of the iterator and does not yet use
 it everywhere it could be.

Added one example in ssa_transformation.cc of its use.

Change-Id: Ia85d58320c80c48a43609265ea5318a416c71f18
Signed-off-by: Jean Christophe Beyler <jean.christophe.beyler@intel.com>

compiler/dex/arena_bit_vector.cc

diff --git a/compiler/dex/arena_bit_vector.cc b/compiler/dex/arena_bit_vector.cc
index b567ae8..1b37b71 100644
--- a/compiler/dex/arena_bit_vector.cc
+++ b/compiler/dex/arena_bit_vector.cc
@@ -44,4 +44,14 @@
                                bool expandable, OatBitMapKind kind)
   :  BitVector(start_bits, expandable, new (arena) ArenaBitVectorAllocator(arena)), kind_(kind) {}
 
+BasicBlock* ArenaBitVector::BasicBlockIterator::Next() {
+    int idx = internal_iterator_.Next();
+
+    if (idx == -1) {
+      return nullptr;
+    }
+
+    return mir_graph_->GetBasicBlock(idx);
+}
+
 }  // namespace art

compiler/dex/arena_bit_vector.h

diff --git a/compiler/dex/arena_bit_vector.h b/compiler/dex/arena_bit_vector.h
index e904406..cdd5c68 100644
--- a/compiler/dex/arena_bit_vector.h
+++ b/compiler/dex/arena_bit_vector.h
@@ -20,14 +20,45 @@
 #include "base/bit_vector.h"
 #include "compiler_enums.h"
 #include "utils/arena_allocator.h"
+#include "compiler_ir.h"
 
 namespace art {
 
+// Forward declaration
+class MIRGraph;
+
 /*
  * A BitVector implementation that uses Arena allocation.
  */
 class ArenaBitVector : public BitVector {
   public:
+    /**
+     * @class BasicBlockIterator
+     * @brief Helper class to get the BasicBlocks when iterating through the ArenaBitVector.
+     */
+    class BasicBlockIterator {
+      public:
+        explicit BasicBlockIterator(ArenaBitVector* bv, MIRGraph* mir_graph)
+          : mir_graph_(mir_graph),
+            internal_iterator_(bv) {}
+
+        explicit BasicBlockIterator(ArenaBitVector* bv, CompilationUnit* c_unit)
+          : mir_graph_(c_unit->mir_graph.get()),
+            internal_iterator_(bv) {}
+
+        BasicBlock* Next();
+
+        static void* operator new(size_t size, ArenaAllocator* arena) {
+          return arena->Alloc(sizeof(ArenaBitVector::BasicBlockIterator),
+                              ArenaAllocator::kAllocGrowableArray);
+        };
+        static void operator delete(void* p) {}  // Nop.
+
+      private:
+        MIRGraph* const mir_graph_;
+        Iterator internal_iterator_;
+    };
+
     ArenaBitVector(ArenaAllocator* arena, uint32_t start_bits, bool expandable,
                    OatBitMapKind kind = kBitMapMisc);
     ~ArenaBitVector() {}

compiler/dex/ssa_transformation.cc

diff --git a/compiler/dex/ssa_transformation.cc b/compiler/dex/ssa_transformation.cc
index 502df1e..0f79f41 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -248,22 +248,11 @@
   }
 
   /* Calculate DF_up */
-  ArenaBitVector::Iterator bv_iterator(bb->i_dominated);
-  while (true) {
-    // TUNING: hot call to BitVectorIteratorNext
-    int dominated_idx = bv_iterator.Next();
-    if (dominated_idx == -1) {
-      break;
-    }
-    BasicBlock* dominated_bb = GetBasicBlock(dominated_idx);
-    ArenaBitVector::Iterator df_iterator(dominated_bb->dom_frontier);
-    while (true) {
-      // TUNING: hot call to BitVectorIteratorNext
-      int df_up_idx = df_iterator.Next();
-      if (df_up_idx == -1) {
-        break;
-      }
-      BasicBlock* df_up_block = GetBasicBlock(df_up_idx);
+  ArenaBitVector::BasicBlockIterator it(bb->i_dominated, cu_);
+  for (BasicBlock *dominated_bb = it.Next(); dominated_bb != nullptr; dominated_bb = it.Next()) {
+    ArenaBitVector::BasicBlockIterator inner_it(dominated_bb->dom_frontier, cu_);
+    for (BasicBlock *df_up_block = inner_it.Next(); df_up_block != nullptr;
+         df_up_block = inner_it.Next()) {
       CheckForDominanceFrontier(bb, df_up_block);
     }
   }