Merge "DataflowIterator normalization"
diff --git a/compiler/dex/dataflow_iterator-inl.h b/compiler/dex/dataflow_iterator-inl.h
index 64e5fa6..0ca1a47 100644
--- a/compiler/dex/dataflow_iterator-inl.h
+++ b/compiler/dex/dataflow_iterator-inl.h
@@ -24,65 +24,100 @@
// Single forward pass over the nodes.
inline BasicBlock* DataflowIterator::ForwardSingleNext() {
BasicBlock* res = NULL;
+
+ // Are we not yet at the end?
if (idx_ < end_idx_) {
- BasicBlockId bb_id = block_id_list_->Get(idx_++);
+ // Get the next index.
+ BasicBlockId bb_id = block_id_list_->Get(idx_);
res = mir_graph_->GetBasicBlock(bb_id);
+ idx_++;
}
+
return res;
}
// Repeat full forward passes over all nodes until no change occurs during a complete pass.
-inline BasicBlock* DataflowIterator::ForwardRepeatNext(bool had_change) {
- changed_ |= had_change;
+inline BasicBlock* DataflowIterator::ForwardRepeatNext() {
BasicBlock* res = NULL;
- if ((idx_ >= end_idx_) && changed_) {
+
+ // Are we at the end and have we changed something?
+ if ((idx_ >= end_idx_) && changed_ == true) {
+ // Reset the index.
idx_ = start_idx_;
repeats_++;
changed_ = false;
}
+
+ // Are we not yet at the end?
if (idx_ < end_idx_) {
- BasicBlockId bb_id = block_id_list_->Get(idx_++);
+ // Get the BasicBlockId.
+ BasicBlockId bb_id = block_id_list_->Get(idx_);
res = mir_graph_->GetBasicBlock(bb_id);
+ idx_++;
}
+
return res;
}
// Single reverse pass over the nodes.
inline BasicBlock* DataflowIterator::ReverseSingleNext() {
BasicBlock* res = NULL;
+
+ // Are we not yet at the end?
if (idx_ >= 0) {
- BasicBlockId bb_id = block_id_list_->Get(idx_--);
+ // Get the BasicBlockId.
+ BasicBlockId bb_id = block_id_list_->Get(idx_);
res = mir_graph_->GetBasicBlock(bb_id);
+ idx_--;
}
+
return res;
}
// Repeat full backwards passes over all nodes until no change occurs during a complete pass.
-inline BasicBlock* DataflowIterator::ReverseRepeatNext(bool had_change) {
- changed_ |= had_change;
+inline BasicBlock* DataflowIterator::ReverseRepeatNext() {
BasicBlock* res = NULL;
+
+ // Are we done and we changed something during the last iteration?
if ((idx_ < 0) && changed_) {
+ // Reset the index.
idx_ = start_idx_;
repeats_++;
changed_ = false;
}
+
+ // Are we not yet done?
if (idx_ >= 0) {
- BasicBlockId bb_id = block_id_list_->Get(idx_--);
+ // Get the BasicBlockId.
+ BasicBlockId bb_id = block_id_list_->Get(idx_);
res = mir_graph_->GetBasicBlock(bb_id);
+ idx_--;
}
+
return res;
}
// AllNodes uses the existing GrowableArray iterator, and should be considered unordered.
-inline BasicBlock* AllNodesIterator::Next() {
+inline BasicBlock* AllNodesIterator::Next(bool had_change) {
BasicBlock* res = NULL;
+
+ // Suppose we want to keep looking.
bool keep_looking = true;
- while (keep_looking) {
+
+ // Find the next BasicBlock.
+ while (keep_looking == true) {
+ // Get next BasicBlock.
res = all_nodes_iterator_->Next();
- if ((res == NULL) || (!res->hidden)) {
+
+ // Are we done or is the BasicBlock not hidden?
+ if ((res == NULL) || (res->hidden == false)) {
keep_looking = false;
}
}
+
+ // Update changed: if had_changed is true, we remember it for the whole iteration.
+ changed_ |= had_change;
+
return res;
}
diff --git a/compiler/dex/dataflow_iterator.h b/compiler/dex/dataflow_iterator.h
index a0c1c12..12f924e 100644
--- a/compiler/dex/dataflow_iterator.h
+++ b/compiler/dex/dataflow_iterator.h
@@ -34,12 +34,40 @@
* 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
+ * @brief The main iterator class, all other iterators derive of this one to define an iteration order.
+ */
class DataflowIterator {
public:
virtual ~DataflowIterator() {}
+
+ /**
+ * @brief How many times have we repeated the iterator across the BasicBlocks?
+ * @return the number of iteration repetitions.
+ */
int32_t GetRepeatCount() { return repeats_; }
+ /**
+ * @brief Has the user of the iterator reported a change yet?
+ * @details Does not mean there was or not a change, it is only whether the user passed a true to the Next function call.
+ * @return whether the user of the iterator reported a change yet.
+ */
+ int32_t GetChanged() { return changed_; }
+
+ /**
+ * @brief Get the next BasicBlock depending on iteration order.
+ * @param had_change did the user of the iteration change the previous BasicBlock.
+ * @return the next BasicBlock following the iteration order, 0 if finished.
+ */
+ virtual BasicBlock* Next(bool had_change = false) = 0;
+
protected:
+ /**
+ * @param mir_graph the MIRGraph we are interested in.
+ * @param start_idx the first index we want to iterate across.
+ * @param end_idx the last index we want to iterate (not included).
+ */
DataflowIterator(MIRGraph* mir_graph, int32_t start_idx, int32_t end_idx)
: mir_graph_(mir_graph),
start_idx_(start_idx),
@@ -49,115 +77,254 @@
repeats_(0),
changed_(false) {}
+ /**
+ * @brief Get the next BasicBlock iterating forward.
+ * @return the next BasicBlock iterating forward.
+ */
virtual BasicBlock* ForwardSingleNext() ALWAYS_INLINE;
+
+ /**
+ * @brief Get the next BasicBlock iterating backward.
+ * @return the next BasicBlock iterating backward.
+ */
virtual BasicBlock* ReverseSingleNext() ALWAYS_INLINE;
- virtual BasicBlock* ForwardRepeatNext(bool had_change) ALWAYS_INLINE;
- virtual BasicBlock* ReverseRepeatNext(bool had_change) ALWAYS_INLINE;
+ /**
+ * @brief Get the next BasicBlock iterating forward, restart if a BasicBlock was reported changed during the last iteration.
+ * @return the next BasicBlock iterating forward, with chance of repeating the iteration.
+ */
+ virtual BasicBlock* ForwardRepeatNext() ALWAYS_INLINE;
- MIRGraph* const mir_graph_;
- const int32_t start_idx_;
- const int32_t end_idx_;
- GrowableArray<BasicBlockId>* block_id_list_;
- int32_t idx_;
- int32_t repeats_;
- bool changed_;
+ /**
+ * @brief Get the next BasicBlock iterating backward, restart if a BasicBlock was reported changed during the last iteration.
+ * @return the next BasicBlock iterating backward, with chance of repeating the iteration.
+ */
+ virtual BasicBlock* ReverseRepeatNext() ALWAYS_INLINE;
+
+ MIRGraph* const mir_graph_; /**< @brief the MIRGraph */
+ const int32_t start_idx_; /**< @brief the start index for the iteration */
+ const int32_t end_idx_; /**< @brief the last index for the iteration */
+ GrowableArray<BasicBlockId>* block_id_list_; /**< @brief the list of BasicBlocks we want to iterate on */
+ int32_t idx_; /**< @brief Current index for the iterator */
+ int32_t repeats_; /**< @brief Number of repeats over the iteration */
+ bool changed_; /**< @brief Has something changed during the current iteration? */
}; // DataflowIterator
+ /**
+ * @class PreOrderDfsIterator
+ * @brief Used to perform a Pre-order Depth-First-Search Iteration of a MIRGraph.
+ */
class PreOrderDfsIterator : public DataflowIterator {
public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
explicit PreOrderDfsIterator(MIRGraph* mir_graph)
: DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) {
+ // Extra setup for the PreOrderDfsIterator.
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDfsOrder();
}
- BasicBlock* Next() {
+ /**
+ * @brief Get the next BasicBlock depending on iteration order.
+ * @param had_change did the user of the iteration change the previous BasicBlock.
+ * @return the next BasicBlock following the iteration order, 0 if finished.
+ */
+ virtual BasicBlock* Next(bool had_change = false) {
+ // Update changed: if had_changed is true, we remember it for the whole iteration.
+ changed_ |= had_change;
+
return ForwardSingleNext();
}
};
+ /**
+ * @class RepeatingPreOrderDfsIterator
+ * @brief Used to perform a Repeating Pre-order Depth-First-Search Iteration of a MIRGraph.
+ * @details If there is a change during an iteration, the iteration starts over at the end of the iteration.
+ */
class RepeatingPreOrderDfsIterator : public DataflowIterator {
public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
explicit RepeatingPreOrderDfsIterator(MIRGraph* mir_graph)
: DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) {
+ // Extra setup for the RepeatingPreOrderDfsIterator.
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDfsOrder();
}
- BasicBlock* Next(bool had_change) {
- return ForwardRepeatNext(had_change);
+ /**
+ * @brief Get the next BasicBlock depending on iteration order.
+ * @param had_change did the user of the iteration change the previous BasicBlock.
+ * @return the next BasicBlock following the iteration order, 0 if finished.
+ */
+ virtual BasicBlock* Next(bool had_change = false) {
+ // Update changed: if had_changed is true, we remember it for the whole iteration.
+ changed_ |= had_change;
+
+ return ForwardRepeatNext();
}
};
+ /**
+ * @class RepeatingPostOrderDfsIterator
+ * @brief Used to perform a Repeating Post-order Depth-First-Search Iteration of a MIRGraph.
+ * @details If there is a change during an iteration, the iteration starts over at the end of the iteration.
+ */
class RepeatingPostOrderDfsIterator : public DataflowIterator {
public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
explicit RepeatingPostOrderDfsIterator(MIRGraph* mir_graph)
: DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) {
+ // Extra setup for the RepeatingPostOrderDfsIterator.
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDfsPostOrder();
}
- BasicBlock* Next(bool had_change) {
- return ForwardRepeatNext(had_change);
+ /**
+ * @brief Get the next BasicBlock depending on iteration order.
+ * @param had_change did the user of the iteration change the previous BasicBlock.
+ * @return the next BasicBlock following the iteration order, 0 if finished.
+ */
+ virtual BasicBlock* Next(bool had_change = false) {
+ // Update changed: if had_changed is true, we remember it for the whole iteration.
+ changed_ |= had_change;
+
+ return ForwardRepeatNext();
}
};
+ /**
+ * @class ReversePostOrderDfsIterator
+ * @brief Used to perform a Reverse Post-order Depth-First-Search Iteration of a MIRGraph.
+ */
class ReversePostOrderDfsIterator : public DataflowIterator {
public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
explicit ReversePostOrderDfsIterator(MIRGraph* mir_graph)
: DataflowIterator(mir_graph, mir_graph->GetNumReachableBlocks() -1, 0) {
+ // Extra setup for the ReversePostOrderDfsIterator.
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDfsPostOrder();
}
- BasicBlock* Next() {
+ /**
+ * @brief Get the next BasicBlock depending on iteration order.
+ * @param had_change did the user of the iteration change the previous BasicBlock.
+ * @return the next BasicBlock following the iteration order, 0 if finished.
+ */
+ virtual BasicBlock* Next(bool had_change = false) {
+ // Update changed: if had_changed is true, we remember it for the whole iteration.
+ changed_ |= had_change;
+
return ReverseSingleNext();
}
};
+ /**
+ * @class ReversePostOrderDfsIterator
+ * @brief Used to perform a Repeating Reverse Post-order Depth-First-Search Iteration of a MIRGraph.
+ * @details If there is a change during an iteration, the iteration starts over at the end of the iteration.
+ */
class RepeatingReversePostOrderDfsIterator : public DataflowIterator {
public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
explicit RepeatingReversePostOrderDfsIterator(MIRGraph* mir_graph)
: DataflowIterator(mir_graph, mir_graph->GetNumReachableBlocks() -1, 0) {
+ // Extra setup for the RepeatingReversePostOrderDfsIterator
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDfsPostOrder();
}
- BasicBlock* Next(bool had_change) {
- return ReverseRepeatNext(had_change);
+ /**
+ * @brief Get the next BasicBlock depending on iteration order.
+ * @param had_change did the user of the iteration change the previous BasicBlock.
+ * @return the next BasicBlock following the iteration order, 0 if finished.
+ */
+ virtual BasicBlock* Next(bool had_change = false) {
+ // Update changed: if had_changed is true, we remember it for the whole iteration.
+ changed_ |= had_change;
+
+ return ReverseRepeatNext();
}
};
+ /**
+ * @class PostOrderDOMIterator
+ * @brief Used to perform a Post-order Domination Iteration of a MIRGraph.
+ */
class PostOrderDOMIterator : public DataflowIterator {
public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
explicit PostOrderDOMIterator(MIRGraph* mir_graph)
: DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) {
+ // Extra setup for thePostOrderDOMIterator.
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDomPostOrder();
}
- BasicBlock* Next() {
+ /**
+ * @brief Get the next BasicBlock depending on iteration order.
+ * @param had_change did the user of the iteration change the previous BasicBlock.
+ * @return the next BasicBlock following the iteration order, 0 if finished.
+ */
+ virtual BasicBlock* Next(bool had_change = false) {
+ // Update changed: if had_changed is true, we remember it for the whole iteration.
+ changed_ |= had_change;
+
return ForwardSingleNext();
}
};
+ /**
+ * @class AllNodesIterator
+ * @brief Used to perform an iteration on all the BasicBlocks a MIRGraph.
+ */
class AllNodesIterator : public DataflowIterator {
public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
explicit AllNodesIterator(MIRGraph* mir_graph)
: DataflowIterator(mir_graph, 0, 0) {
all_nodes_iterator_ = new
(mir_graph->GetArena()) GrowableArray<BasicBlock*>::Iterator(mir_graph->GetBlockList());
}
+ /**
+ * @brief Resetting the iterator.
+ */
void Reset() {
all_nodes_iterator_->Reset();
}
- BasicBlock* Next() ALWAYS_INLINE;
+ /**
+ * @brief Get the next BasicBlock depending on iteration order.
+ * @param had_change did the user of the iteration change the previous BasicBlock.
+ * @return the next BasicBlock following the iteration order, 0 if finished.
+ */
+ virtual BasicBlock* Next(bool had_change = false) ALWAYS_INLINE;
private:
- GrowableArray<BasicBlock*>::Iterator* all_nodes_iterator_;
+ GrowableArray<BasicBlock*>::Iterator* all_nodes_iterator_; /**< @brief The list of all the nodes */
};
} // namespace art
