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.h b/compiler/dex/mir_graph.h
index 0bb8265..3a00a43 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -354,11 +354,12 @@
*/
MIR* GetNextUnconditionalMir(MIRGraph* mir_graph, MIR* current);
bool RemoveMIR(MIR* mir);
+ bool IsExceptionBlock() const;
};
/*
* The "blocks" field in "successor_block_list" points to an array of elements with the type
- * "SuccessorBlockInfo". For catch blocks, key is type index for the exception. For swtich
+ * "SuccessorBlockInfo". For catch blocks, key is type index for the exception. For switch
* blocks, key is the case value.
*/
struct SuccessorBlockInfo {
@@ -598,6 +599,10 @@
void BasicBlockOptimization();
+ GrowableArray<BasicBlockId>* GetTopologicalSortOrder() {
+ return topological_order_;
+ }
+
bool IsConst(int32_t s_reg) const {
return is_constant_v_->IsBitSet(s_reg);
}
@@ -865,6 +870,7 @@
MIR* AdvanceMIR(BasicBlock** p_bb, MIR* mir);
BasicBlock* NextDominatedBlock(BasicBlock* bb);
bool LayoutBlocks(BasicBlock* bb);
+ void ComputeTopologicalSortOrder();
bool InlineCallsGate();
void InlineCallsStart();
@@ -1003,6 +1009,7 @@
GrowableArray<BasicBlockId>* dfs_order_;
GrowableArray<BasicBlockId>* dfs_post_order_;
GrowableArray<BasicBlockId>* dom_post_order_traversal_;
+ GrowableArray<BasicBlockId>* topological_order_;
int* i_dom_list_;
ArenaBitVector** def_block_matrix_; // num_dalvik_register x num_blocks.
ArenaBitVector* temp_dalvik_register_v_;