Compiler: rework dataflow iterator.
This cl addresses comments from 278630 - rework DatflowIterator
to be a parent class for the various iteration modes.
Change-Id: Ic16c093597e2d754761b4fdfa47f665d8b315542
diff --git a/src/compiler/dex/dataflow_iterator.h b/src/compiler/dex/dataflow_iterator.h
index 7acaf43..f3a2fca 100644
--- a/src/compiler/dex/dataflow_iterator.h
+++ b/src/compiler/dex/dataflow_iterator.h
@@ -22,30 +22,132 @@
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:
- DataflowIterator(MIRGraph* mir_graph, DataFlowAnalysisMode dfa_mode, bool is_iterative);
- ~DataflowIterator(){}
- BasicBlock* Next(bool had_change);
- BasicBlock* Next();
+ virtual ~DataflowIterator(){}
- private:
- // TODO: rework this class.
- MIRGraph* mir_graph_;
- DataFlowAnalysisMode mode_;
- bool is_iterative_;
- bool changed_;
- int start_idx_;
- int end_idx_;
- int idx_;
- bool reverse_;
+ // 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) {}
+
+ virtual BasicBlock* NextBody(bool had_change);
+
+ MIRGraph* const mir_graph_;
+ const bool is_iterative_;
+ const int start_idx_;
+ const int end_idx_;
+ const bool reverse_;
GrowableList* block_id_list_;
GrowableListIterator all_nodes_iterator_;
-
- BasicBlock* NextBody(bool had_change);
+ 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) {
+ GrowableListIteratorInit(mir_graph->GetBlockList(), &all_nodes_iterator_);
+ }
+
+ virtual BasicBlock* NextBody(bool had_change);
+ };
+
} // namespace art
#endif // ART_SRC_COMPILER_DEX_DATAFLOW_ITERATOR_H_