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/compiler_enums.h b/src/compiler/dex/compiler_enums.h
index 3eb862f..71d7d65 100644
--- a/src/compiler/dex/compiler_enums.h
+++ b/src/compiler/dex/compiler_enums.h
@@ -327,18 +327,6 @@
std::ostream& operator<<(std::ostream& os, const DividePattern& pattern);
-/* Customized node traversal orders for different needs */
-enum DataFlowAnalysisMode {
- kAllNodes = 0, // All nodes.
- kReachableNodes, // All reachable nodes.
- kPreOrderDFSTraversal, // Depth-First-Search / Pre-Order.
- kPostOrderDFSTraversal, // Depth-First-Search / Post-Order.
- kPostOrderDOMTraversal, // Dominator tree / Post-Order.
- kReversePostOrderTraversal, // Depth-First-Search / reverse Post-Order.
-};
-
-std::ostream& operator<<(std::ostream& os, const DataFlowAnalysisMode& mode);
-
// Memory barrier types (see "The JSR-133 Cookbook for Compiler Writers").
enum MemBarrierKind {
kLoadStore,
diff --git a/src/compiler/dex/dataflow_iterator.cc b/src/compiler/dex/dataflow_iterator.cc
index 6a3975e..514eeba 100644
--- a/src/compiler/dex/dataflow_iterator.cc
+++ b/src/compiler/dex/dataflow_iterator.cc
@@ -18,69 +18,10 @@
namespace art {
- DataflowIterator::DataflowIterator(MIRGraph* mir_graph, DataFlowAnalysisMode dfa_mode, bool is_iterative)
- : mir_graph_(mir_graph),
- mode_(dfa_mode),
- is_iterative_(is_iterative),
- changed_(false) {
- switch(mode_) {
- case kAllNodes:
- GrowableListIteratorInit(mir_graph_->GetBlockList(), &all_nodes_iterator_);
- break;
-
- case kReachableNodes:
- case kPreOrderDFSTraversal:
- start_idx_ = 0;
- end_idx_ = mir_graph_->GetNumReachableBlocks();
- idx_ = start_idx_;
- block_id_list_ = mir_graph_->GetDfsOrder();
- reverse_ = false;
- break;
-
- case kPostOrderDFSTraversal:
- start_idx_ = mir_graph_->GetNumReachableBlocks() - 1;
- end_idx_ = 0;
- idx_ = start_idx_;
- block_id_list_ = mir_graph_->GetDfsOrder();
- reverse_ = true;
- break;
-
- case kPostOrderDOMTraversal:
- start_idx_ = 0;
- end_idx_ = mir_graph_->GetNumReachableBlocks();
- idx_ = start_idx_;
- block_id_list_ = mir_graph_->GetDomPostOrder();
- reverse_ = false;
- break;
-
- case kReversePostOrderTraversal:
- start_idx_ = mir_graph_->GetNumReachableBlocks() - 1;
- end_idx_ = 0;
- idx_ = start_idx_;
- block_id_list_ = mir_graph_->GetDfsPostOrder();
- reverse_ = true;
- break;
- default:
- LOG(FATAL) << "Unknown traversal mode: " << dfa_mode;
- }
- }
-
- BasicBlock* DataflowIterator::NextBody(bool had_change)
- {
+ BasicBlock* DataflowIterator::NextBody(bool had_change) {
changed_ |= had_change;
BasicBlock* res = NULL;
- if (mode_ == kAllNodes) {
- bool keep_looking = true;
- while (keep_looking) {
- res = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&all_nodes_iterator_));
- if (is_iterative_ && changed_ && (res == NULL)) {
- GrowableListIteratorInit(mir_graph_->GetBlockList(), &all_nodes_iterator_);
- changed_ = false;
- } else if ((res == NULL) || (!res->hidden)) {
- keep_looking = false;
- }
- }
- } else if (reverse_) {
+ if (reverse_) {
if (is_iterative_ && changed_ && (idx_ < 0)) {
idx_ = start_idx_;
changed_ = false;
@@ -102,16 +43,21 @@
return res;
}
- BasicBlock* DataflowIterator::Next(bool had_change)
- {
- DCHECK(is_iterative_);
- return NextBody(had_change);
- }
-
- BasicBlock* DataflowIterator::Next()
- {
- DCHECK(!is_iterative_);
- return NextBody(false);
+ // AllNodes uses the existing GrowableList iterator, so use different NextBody().
+ BasicBlock* AllNodesIterator::NextBody(bool had_change) {
+ changed_ |= had_change;
+ BasicBlock* res = NULL;
+ bool keep_looking = true;
+ while (keep_looking) {
+ res = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&all_nodes_iterator_));
+ if (is_iterative_ && changed_ && (res == NULL)) {
+ GrowableListIteratorInit(mir_graph_->GetBlockList(), &all_nodes_iterator_);
+ changed_ = false;
+ } else if ((res == NULL) || (!res->hidden)) {
+ keep_looking = false;
+ }
+ }
+ return res;
}
} // namespace art
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_
diff --git a/src/compiler/dex/mir_dataflow.cc b/src/compiler/dex/mir_dataflow.cc
index add5ca0..0c767aa 100644
--- a/src/compiler/dex/mir_dataflow.cc
+++ b/src/compiler/dex/mir_dataflow.cc
@@ -1320,7 +1320,7 @@
if (cu_->disable_opt & (1 << kPromoteRegs)) {
return;
}
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
CountUses(bb);
}
@@ -1370,7 +1370,7 @@
void MIRGraph::VerifyDataflow()
{
/* Verify if all blocks are connected as claimed */
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
VerifyPredInfo(bb);
}
diff --git a/src/compiler/dex/mir_optimization.cc b/src/compiler/dex/mir_optimization.cc
index bb3938b..759dc32 100644
--- a/src/compiler/dex/mir_optimization.cc
+++ b/src/compiler/dex/mir_optimization.cc
@@ -103,7 +103,7 @@
is_constant_v_ = AllocBitVector(cu_, GetNumSSARegs(), false);
constant_values_ = static_cast<int*>(NewMem(cu_, sizeof(int) * GetNumSSARegs(), true,
kAllocDFInfo));
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
DoConstantPropogation(bb);
}
@@ -754,11 +754,11 @@
{
if (!(cu_->disable_opt & (1 << kNullCheckElimination))) {
DCHECK(temp_ssa_register_v_ != NULL);
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
NullCheckEliminationInit(bb);
}
- DataflowIterator iter2(this, kPreOrderDFSTraversal, true /* iterative */);
+ PreOrderDfsIterator iter2(this, true /* iterative */);
bool change = false;
for (BasicBlock* bb = iter2.Next(change); bb != NULL; bb = iter2.Next(change)) {
change = EliminateNullChecks(bb);
@@ -771,7 +771,7 @@
void MIRGraph::BasicBlockCombine()
{
- DataflowIterator iter(this, kPreOrderDFSTraversal, false /* not iterative */);
+ PreOrderDfsIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
CombineBlocks(bb);
}
@@ -782,7 +782,7 @@
void MIRGraph::CodeLayout()
{
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
LayoutBlocks(bb);
}
@@ -796,7 +796,7 @@
Checkstats* stats =
static_cast<Checkstats*>(NewMem(cu_, sizeof(Checkstats), true, kAllocDFInfo));
cu_->checkstats = stats;
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
CountChecks(bb);
}
@@ -853,11 +853,11 @@
CompilerInitGrowableList(cu_, &cu_->compiler_temps, 6, kListMisc);
DCHECK_EQ(cu_->num_compiler_temps, 0);
// Mark all blocks as not visited
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
ClearVisitedFlag(bb);
}
- DataflowIterator iter2(this, kPreOrderDFSTraversal, false /* not iterative */);
+ PreOrderDfsIterator iter2(this, false /* not iterative */);
for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) {
BuildExtendedBBList(bb);
}
diff --git a/src/compiler/dex/portable/mir_to_gbc.cc b/src/compiler/dex/portable/mir_to_gbc.cc
index 3de593c..afef7bf 100644
--- a/src/compiler/dex/portable/mir_to_gbc.cc
+++ b/src/compiler/dex/portable/mir_to_gbc.cc
@@ -1962,7 +1962,7 @@
CreateFunction(cu);
// Create an LLVM basic block for each MIR block in dfs preorder
- DataflowIterator iter(cu->mir_graph.get(), kPreOrderDFSTraversal, false /* not iterative */);
+ PreOrderDfsIterator iter(cu->mir_graph.get(), false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
CreateLLVMBasicBlock(cu, bb);
}
@@ -1994,7 +1994,7 @@
}
}
- DataflowIterator iter2(cu->mir_graph.get(), kPreOrderDFSTraversal, false /* not iterative */);
+ PreOrderDfsIterator iter2(cu->mir_graph.get(), false /* not iterative */);
for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) {
BlockBitcodeConversion(cu, bb);
}
diff --git a/src/compiler/dex/quick/mir_to_lir.cc b/src/compiler/dex/quick/mir_to_lir.cc
index 0b85e92..7aec54e 100644
--- a/src/compiler/dex/quick/mir_to_lir.cc
+++ b/src/compiler/dex/quick/mir_to_lir.cc
@@ -834,7 +834,7 @@
cu->block_label_list =
static_cast<LIR*>(NewMem(cu, sizeof(LIR) * cu->mir_graph->GetNumBlocks(), true, kAllocLIR));
- DataflowIterator iter(cu->mir_graph.get(), kPreOrderDFSTraversal, false /* not iterative */);
+ PreOrderDfsIterator iter(cu->mir_graph.get(), false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
MethodBlockCodeGen(cu, bb);
}
diff --git a/src/compiler/dex/ssa_transformation.cc b/src/compiler/dex/ssa_transformation.cc
index 52674aa..b13cf05 100644
--- a/src/compiler/dex/ssa_transformation.cc
+++ b/src/compiler/dex/ssa_transformation.cc
@@ -97,7 +97,7 @@
}
// Reset visited flags from all nodes
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
ClearVisitedFlag(bb);
}
@@ -139,11 +139,11 @@
for (i = 0; i < num_registers; i++) {
def_block_matrix_[i] = AllocBitVector(cu_, GetNumBlocks(), false, kBitMapBMatrix);
}
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
FindLocalLiveIn(bb);
}
- DataflowIterator iter2(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter2(this, false /* not iterative */);
for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) {
FillDefBlockMatrix(bb);
}
@@ -369,7 +369,7 @@
int num_total_blocks = GetBasicBlockListCount();
/* Initialize domination-related data structures */
- DataflowIterator iter(this, kReachableNodes, false /* not iterative */);
+ ReachableNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
InitializeDominationInfo(bb);
}
@@ -388,7 +388,7 @@
i_dom_list_[GetEntryBlock()->dfs_id] = GetEntryBlock()->dfs_id;
/* Compute the immediate dominators */
- DataflowIterator iter2(this, kReversePostOrderTraversal, true /* iterative */);
+ ReversePostOrderDfsIterator iter2(this, true /* iterative */);
bool change = false;
for (BasicBlock* bb = iter2.Next(false); bb != NULL; bb = iter2.Next(change)) {
change = ComputeblockIDom(bb);
@@ -405,12 +405,12 @@
}
GetEntryBlock()->i_dom = NULL;
- DataflowIterator iter3(this, kReachableNodes, false /* not iterative */);
+ ReachableNodesIterator iter3(this, false /* not iterative */);
for (BasicBlock* bb = iter3.Next(); bb != NULL; bb = iter3.Next()) {
SetDominators(bb);
}
- DataflowIterator iter4(this, kReversePostOrderTraversal, false /* not iterative */);
+ ReversePostOrderDfsIterator iter4(this, false /* not iterative */);
for (BasicBlock* bb = iter4.Next(); bb != NULL; bb = iter4.Next()) {
ComputeBlockDominators(bb);
}
@@ -430,7 +430,7 @@
DCHECK_EQ(dom_post_order_traversal_.num_used, static_cast<unsigned>(num_reachable_blocks_));
/* Now compute the dominance frontier for each block */
- DataflowIterator iter5(this, kPostOrderDOMTraversal, false /* not iterative */);
+ PostOrderDOMIterator iter5(this, false /* not iterative */);
for (BasicBlock* bb = iter5.Next(); bb != NULL; bb = iter5.Next()) {
ComputeDominanceFrontier(bb);
}
@@ -506,7 +506,7 @@
temp_dalvik_register_v_ =
AllocBitVector(cu_, cu_->num_dalvik_registers, false, kBitMapRegisterV);
- DataflowIterator iter(this, kPostOrderDFSTraversal, true /* iterative */);
+ PostOrderDfsIterator iter(this, true /* iterative */);
bool change = false;
for (BasicBlock* bb = iter.Next(false); bb != NULL; bb = iter.Next(change)) {
change = ComputeBlockLiveIns(bb);
@@ -691,7 +691,7 @@
}
/* Rename register names by local defs and phi nodes */
- DataflowIterator iter(this, kAllNodes, false /* not iterative */);
+ AllNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
ClearVisitedFlag(bb);
}
@@ -705,7 +705,7 @@
temp_ssa_register_v_ = AllocBitVector(cu_, GetNumSSARegs(), false, kBitMapTempSSARegisterV);
/* Insert phi-operands with latest SSA names from predecessor blocks */
- DataflowIterator iter(this, kReachableNodes, false /* not iterative */);
+ ReachableNodesIterator iter(this, false /* not iterative */);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
InsertPhiNodeOperands(bb);
}
diff --git a/src/compiler/dex/vreg_analysis.cc b/src/compiler/dex/vreg_analysis.cc
index 4f516fe..08f1f35 100644
--- a/src/compiler/dex/vreg_analysis.cc
+++ b/src/compiler/dex/vreg_analysis.cc
@@ -473,7 +473,7 @@
}
/* Do type & size inference pass */
- DataflowIterator iter(this, kPreOrderDFSTraversal, true /* iterative */);
+ PreOrderDfsIterator iter(this, true /* iterative */);
bool change = false;
for (BasicBlock* bb = iter.Next(false); bb != NULL; bb = iter.Next(change)) {
change = InferTypeAndSize(bb);
