From 44e5bdec17d0528b90cc0773be2beb76dcafdc5b Mon Sep 17 00:00:00 2001 From: Jean Christophe Beyler Date: Tue, 29 Apr 2014 14:40:41 -0700 Subject: [PATCH] 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 Signed-off-by: Razvan A Lupusoru Signed-off-by: Yixin Shou Signed-off-by: Chao-ying Fu Signed-off-by: Udayan Banerji --- compiler/dex/dataflow_iterator.h | 75 +++++++++++++++++++++++++++++ compiler/dex/mir_graph.cc | 100 +++++++++++++++++++++++++++++++++++++++ compiler/dex/mir_graph.h | 9 +++- compiler/dex/pass.h | 5 ++ compiler/dex/pass_driver.cc | 6 +++ compiler/dex/pass_me.h | 2 + 6 files changed, 196 insertions(+), 1 deletion(-) diff --git a/compiler/dex/dataflow_iterator.h b/compiler/dex/dataflow_iterator.h index b45d6a45a..62973afc3 100644 --- a/compiler/dex/dataflow_iterator.h +++ b/compiler/dex/dataflow_iterator.h @@ -326,6 +326,81 @@ namespace art { GrowableArray::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_ diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc index 4ba66771b..c34a9f563 100644 --- a/compiler/dex/mir_graph.cc +++ b/compiler/dex/mir_graph.cc @@ -17,6 +17,7 @@ #include "mir_graph.h" #include +#include #include "base/stl_util.h" #include "compiler_internals.h" @@ -76,6 +77,7 @@ MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) 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 @@ void MIRGraph::InitializeSSATransformation() { DoDFSPreOrderSSARename(GetEntryBlock()); } +void MIRGraph::ComputeTopologicalSortOrder() { + std::queue q; + std::map visited_cnt_values; + + // Clear the nodes. + ClearAllVisitedFlags(); + + // Create the topological order if need be. + if (topological_order_ != nullptr) { + topological_order_ = new (arena_) GrowableArray(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::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::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) { diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h index 0bb82659a..3a00a434b 100644 --- a/compiler/dex/mir_graph.h +++ b/compiler/dex/mir_graph.h @@ -354,11 +354,12 @@ struct BasicBlock { */ 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 @@ class MIRGraph { void BasicBlockOptimization(); + GrowableArray* GetTopologicalSortOrder() { + return topological_order_; + } + bool IsConst(int32_t s_reg) const { return is_constant_v_->IsBitSet(s_reg); } @@ -865,6 +870,7 @@ class MIRGraph { 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 @@ class MIRGraph { GrowableArray* dfs_order_; GrowableArray* dfs_post_order_; GrowableArray* dom_post_order_traversal_; + GrowableArray* topological_order_; int* i_dom_list_; ArenaBitVector** def_block_matrix_; // num_dalvik_register x num_blocks. ArenaBitVector* temp_dalvik_register_v_; diff --git a/compiler/dex/pass.h b/compiler/dex/pass.h index ac2229481..4ce040e9a 100644 --- a/compiler/dex/pass.h +++ b/compiler/dex/pass.h @@ -22,6 +22,11 @@ #include "base/macros.h" namespace art { +// Forward declarations. +struct BasicBlock; +struct CompilationUnit; +class Pass; + // Empty Pass Data Class, can be extended by any pass extending the base Pass class. class PassDataHolder { }; diff --git a/compiler/dex/pass_driver.cc b/compiler/dex/pass_driver.cc index 999ed2af5..ca936cd41 100644 --- a/compiler/dex/pass_driver.cc +++ b/compiler/dex/pass_driver.cc @@ -162,6 +162,12 @@ void PassDriver::DispatchPass(CompilationUnit* c_unit, const Pass* curPass) { case kAllNodes: DoWalkBasicBlocks(c_unit, curPass); break; + case kTopologicalSortTraversal: + DoWalkBasicBlocks(c_unit, curPass); + break; + case kRepeatingTopologicalSortTraversal: + DoWalkBasicBlocks(c_unit, curPass); + break; case kNoNodes: break; default: diff --git a/compiler/dex/pass_me.h b/compiler/dex/pass_me.h index 1132166a3..069fb45dc 100644 --- a/compiler/dex/pass_me.h +++ b/compiler/dex/pass_me.h @@ -49,6 +49,8 @@ enum DataFlowAnalysisMode { kRepeatingPostOrderDFSTraversal, /**< @brief Depth-First-Search / Repeating Post-Order. */ kRepeatingReversePostOrderDFSTraversal, /**< @brief Depth-First-Search / Repeating Reverse Post-Order. */ kPostOrderDOMTraversal, /**< @brief Dominator tree / Post-Order. */ + kTopologicalSortTraversal, /**< @brief Topological Order traversal. */ + kRepeatingTopologicalSortTraversal, /**< @brief Repeating Topological Order traversal. */ kNoNodes, /**< @brief Skip BasicBlock traversal. */ }; -- 2.11.0