DataflowIterator normalization
The patch normalizes the data flow iterators. The reasoning behind it is
to allow passing the base class around without knowing what underlying iterator
is used. This will thus allow called functions to call the
specified Next function. This feature will be required for future patches.
- Made DataflowIterator a base class with an abstract Next function
- Updated each derived class to use the same Next function signature
- Added comments and doxygen comments
Change-Id: I3b9bce6326675575172f0ebd3681369d40d55661
Signed-off-by: Jean Christophe Beyler <jean.christophe.beyler@intel.com>
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
