1 files changed, 158 insertions, 0 deletions
diff --git a/compiler/dex/dataflow_iterator.h b/compiler/dex/dataflow_iterator.h
new file mode 100644
index 0000000000..12cbf9cadf
--- /dev/null
+++ b/compiler/dex/dataflow_iterator.h
@@ -0,0 +1,158 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_SRC_COMPILER_DEX_DATAFLOW_ITERATOR_H_
+#define ART_SRC_COMPILER_DEX_DATAFLOW_ITERATOR_H_
+
+#include "compiler_ir.h"
+#include "mir_graph.h"
+
+namespace art {
+
+  /*
+   * This class supports iterating over lists of basic blocks in various
+   * interesting orders.  Note that for efficiency, the visit orders have been pre-computed.
+   * The order itself will not change during the iteration.  However, for some uses,
+   * auxiliary data associated with the basic blocks may be changed during the iteration,
+   * necessitating another pass over the list.
+   *
+   * To support this usage, we have is_iterative_.  If false, the iteration is a one-shot
+   * pass through the pre-computed list using Next().  If true, the caller must tell the
+   * iterator whether a change has been made that necessitates another pass.  Use
+   * Next(had_change) for this.  The general idea is that the iterative_ use case means
+   * that the iterator will keep repeating the full basic block list until a complete pass
+   * is made through it with no changes.  Note that calling Next(true) does not affect
+   * the iteration order or short-curcuit the current pass - it simply tells the iterator
+   * that once it has finished walking through the block list it should reset and do another
+   * full pass through the list.
+   */
+  class DataflowIterator {
+    public:
+
+      virtual ~DataflowIterator(){}
+
+      // Return the next BasicBlock* to visit.
+      BasicBlock* Next() {
+        DCHECK(!is_iterative_);
+        return NextBody(false);
+      }
+
+      /*
+       * Return the next BasicBlock* to visit, and tell the iterator whether any change
+       * has occurred that requires another full pass over the block list.
+       */
+      BasicBlock* Next(bool had_change) {
+        DCHECK(is_iterative_);
+        return NextBody(had_change);
+      }
+
+    protected:
+      DataflowIterator(MIRGraph* mir_graph, bool is_iterative, int start_idx, int end_idx,
+                       bool reverse)
+          : mir_graph_(mir_graph),
+            is_iterative_(is_iterative),
+            start_idx_(start_idx),
+            end_idx_(end_idx),
+            reverse_(reverse),
+            block_id_list_(NULL),
+            idx_(0),
+            changed_(false) {}
+
+      virtual BasicBlock* NextBody(bool had_change) ALWAYS_INLINE;
+
+      MIRGraph* const mir_graph_;
+      const bool is_iterative_;
+      const int start_idx_;
+      const int end_idx_;
+      const bool reverse_;
+      GrowableArray<int>* block_id_list_;
+      int idx_;
+      bool changed_;
+
+  }; // DataflowIterator
+
+  class ReachableNodesIterator : public DataflowIterator {
+    public:
+      ReachableNodesIterator(MIRGraph* mir_graph, bool is_iterative)
+          : DataflowIterator(mir_graph, is_iterative, 0,
+                             mir_graph->GetNumReachableBlocks(), false) {
+        idx_ = start_idx_;
+        block_id_list_ = mir_graph->GetDfsOrder();
+      }
+  };
+
+  class PreOrderDfsIterator : public DataflowIterator {
+    public:
+      PreOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
+          : DataflowIterator(mir_graph, is_iterative, 0,
+                             mir_graph->GetNumReachableBlocks(), false) {
+        idx_ = start_idx_;
+        block_id_list_ = mir_graph->GetDfsOrder();
+      }
+  };
+
+  class PostOrderDfsIterator : public DataflowIterator {
+    public:
+
+      PostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
+          : DataflowIterator(mir_graph, is_iterative, 0,
+                             mir_graph->GetNumReachableBlocks(), false) {
+        idx_ = start_idx_;
+        block_id_list_ = mir_graph->GetDfsPostOrder();
+      }
+  };
+
+  class ReversePostOrderDfsIterator : public DataflowIterator {
+    public:
+      ReversePostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
+          : DataflowIterator(mir_graph, is_iterative,
+                             mir_graph->GetNumReachableBlocks() -1, 0, true) {
+        idx_ = start_idx_;
+        block_id_list_ = mir_graph->GetDfsPostOrder();
+      }
+  };
+
+  class PostOrderDOMIterator : public DataflowIterator {
+    public:
+      PostOrderDOMIterator(MIRGraph* mir_graph, bool is_iterative)
+          : DataflowIterator(mir_graph, is_iterative, 0,
+                             mir_graph->GetNumReachableBlocks(), false) {
+        idx_ = start_idx_;
+        block_id_list_ = mir_graph->GetDomPostOrder();
+      }
+  };
+
+  class AllNodesIterator : public DataflowIterator {
+    public:
+      AllNodesIterator(MIRGraph* mir_graph, bool is_iterative)
+          : DataflowIterator(mir_graph, is_iterative, 0, 0, false) {
+        all_nodes_iterator_ =
+            new (mir_graph->GetArena()) GrowableArray<BasicBlock*>::Iterator (mir_graph->GetBlockList());
+      }
+
+      void Reset() {
+        all_nodes_iterator_->Reset();
+      }
+
+      BasicBlock* NextBody(bool had_change) ALWAYS_INLINE;
+
+    private:
+      GrowableArray<BasicBlock*>::Iterator* all_nodes_iterator_;
+  };
+
+}  // namespace art
+
+#endif // ART_SRC_COMPILER_DEX_DATAFLOW_ITERATOR_H_