ART: Topological Sort Traversal Implementation
- Added a topological sort implementation for traversal.
- Useful for traversals that require traversing the predecessors first.
- Added a function to BasicBlock to detect if it is an exception block.
Change-Id: I573da1768a635c6fd0259573dbb46b112132e129
Signed-off-by: Jean Christophe Beyler <jean.christophe.beyler@intel.com>
Signed-off-by: Razvan A Lupusoru <razvan.a.lupusoru@intel.com>
Signed-off-by: Yixin Shou <yixin.shou@intel.com>
Signed-off-by: Chao-ying Fu <chao-ying.fu@intel.com>
Signed-off-by: Udayan Banerji <udayan.banerji@intel.com>
diff --git a/compiler/dex/dataflow_iterator.h b/compiler/dex/dataflow_iterator.h
index b45d6a4..62973af 100644
--- a/compiler/dex/dataflow_iterator.h
+++ b/compiler/dex/dataflow_iterator.h
@@ -326,6 +326,81 @@
GrowableArray<BasicBlock*>::Iterator all_nodes_iterator_; /**< @brief The list of all the nodes */
};
+ /**
+ * @class TopologicalSortIterator
+ * @brief Used to perform a Topological Sort Iteration of a MIRGraph.
+ */
+ class TopologicalSortIterator : public DataflowIterator {
+ public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
+ explicit TopologicalSortIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, 0, mir_graph->GetTopologicalSortOrder() != nullptr ?
+ mir_graph->GetTopologicalSortOrder()->Size() : 0) {
+ // Extra setup for TopologicalSortIterator.
+ idx_ = start_idx_;
+ block_id_list_ = mir_graph->GetTopologicalSortOrder();
+
+ if (mir_graph->GetTopologicalSortOrder() == nullptr) {
+ /* Compute the topological order */
+ mir_graph->ComputeTopologicalSortOrder();
+ }
+ }
+
+ /**
+ * @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 RepeatingTopologicalSortIterator
+ * @brief Used to perform a Topological Sort Iteration of a MIRGraph.
+ * @details If there is a change during an iteration, the iteration starts over at the end of the
+ * iteration.
+ */
+ class RepeatingTopologicalSortIterator : public DataflowIterator {
+ public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
+ explicit RepeatingTopologicalSortIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, 0, mir_graph->GetTopologicalSortOrder() != nullptr ?
+ mir_graph->GetTopologicalSortOrder()->Size() : 0) {
+ // Extra setup for RepeatingTopologicalSortIterator.
+ idx_ = start_idx_;
+ block_id_list_ = mir_graph->GetTopologicalSortOrder();
+
+ if (mir_graph->GetTopologicalSortOrder() == nullptr) {
+ /* Compute the topological order */
+ mir_graph->ComputeTopologicalSortOrder();
+ }
+ }
+
+ /**
+ * @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();
+ }
+ };
+
+
} // namespace art
#endif // ART_COMPILER_DEX_DATAFLOW_ITERATOR_H_