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/mir_graph.cc b/compiler/dex/mir_graph.cc
index 4ba6677..c34a9f5 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -17,6 +17,7 @@
#include "mir_graph.h"
#include <inttypes.h>
+#include <queue>
#include "base/stl_util.h"
#include "compiler_internals.h"
@@ -76,6 +77,7 @@
dfs_order_(NULL),
dfs_post_order_(NULL),
dom_post_order_traversal_(NULL),
+ topological_order_(nullptr),
i_dom_list_(NULL),
def_block_matrix_(NULL),
temp_dalvik_register_v_(NULL),
@@ -1337,6 +1339,104 @@
DoDFSPreOrderSSARename(GetEntryBlock());
}
+void MIRGraph::ComputeTopologicalSortOrder() {
+ std::queue<BasicBlock *> q;
+ std::map<int, int> visited_cnt_values;
+
+ // Clear the nodes.
+ ClearAllVisitedFlags();
+
+ // Create the topological order if need be.
+ if (topological_order_ != nullptr) {
+ topological_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, 0);
+ }
+ topological_order_->Reset();
+
+ // Set up visitedCntValues map for all BB. The default value for this counters in the map is zero.
+ // also fill initial queue.
+ GrowableArray<BasicBlock*>::Iterator iterator(&block_list_);
+
+ while (true) {
+ BasicBlock* bb = iterator.Next();
+
+ if (bb == nullptr) {
+ break;
+ }
+
+ if (bb->hidden == true) {
+ continue;
+ }
+
+ visited_cnt_values[bb->id] = bb->predecessors->Size();
+
+ GrowableArray<BasicBlockId>::Iterator pred_iterator(bb->predecessors);
+ // To process loops we should not wait for dominators.
+ while (true) {
+ BasicBlock* pred_bb = GetBasicBlock(pred_iterator.Next());
+
+ if (pred_bb == nullptr) {
+ break;
+ }
+
+ if (pred_bb->dominators == nullptr || pred_bb->hidden == true) {
+ continue;
+ }
+
+ // Skip the backward branch.
+ if (pred_bb->dominators->IsBitSet(bb->id) != 0) {
+ visited_cnt_values[bb->id]--;
+ }
+ }
+
+ // Add entry block to queue.
+ if (visited_cnt_values[bb->id] == 0) {
+ q.push(bb);
+ }
+ }
+
+ while (q.size() > 0) {
+ // Get top.
+ BasicBlock *bb = q.front();
+ q.pop();
+
+ DCHECK_EQ(bb->hidden, false);
+
+ if (bb->IsExceptionBlock() == true) {
+ continue;
+ }
+
+ // We've visited all the predecessors. So, we can visit bb.
+ if (bb->visited == false) {
+ bb->visited = true;
+
+ // Now add the basic block.
+ topological_order_->Insert(bb->id);
+
+ // Reduce visitedCnt for all the successors and add into the queue ones with visitedCnt equals to zero.
+ ChildBlockIterator succIter(bb, this);
+ BasicBlock *successor = succIter.Next();
+ while (successor != nullptr) {
+ // one more predecessor was visited.
+ visited_cnt_values[successor->id]--;
+
+ if (visited_cnt_values[successor->id] <= 0 && successor->visited == false && successor->hidden == false) {
+ q.push(successor);
+ }
+
+ // Take next successor.
+ successor = succIter.Next();
+ }
+ }
+ }
+}
+
+bool BasicBlock::IsExceptionBlock() const {
+ if (block_type == kExceptionHandling) {
+ return true;
+ }
+ return false;
+}
+
ChildBlockIterator::ChildBlockIterator(BasicBlock* bb, MIRGraph* mir_graph)
: basic_block_(bb), mir_graph_(mir_graph), visited_fallthrough_(false),
visited_taken_(false), have_successors_(false) {