Rewrite topological sort order and improve GVN.
Rewrite the topological sort order to include a full loop
before the blocks that go after the loop. Add a new iterator
class LoopRepeatingTopologicalSortIterator that differs from
the RepeatingTopologicalSortIterator by repeating only loops
and repeating them early. It returns to the loop head if the
head needs recalculation when we reach the end of the loop.
In GVN, use the new loop-repeating topological sort iterator
and for a loop head merge only the preceding blocks' LVNs
if we're not currently recalculating this loop.
Also fix LocalValueNumbering::InPlaceIntersectMaps() which
was keeping only the last element of the intersection, avoid
some unnecessary processing during LVN merge and add some
missing braces to MIRGraph::InferTypeAndSize().
Bug: 16398693
Change-Id: I4e10d4acb626a5b8a28ec0de106a7b37f9cbca32
diff --git a/compiler/dex/dataflow_iterator-inl.h b/compiler/dex/dataflow_iterator-inl.h
index f8b9c1a..d1abf7f 100644
--- a/compiler/dex/dataflow_iterator-inl.h
+++ b/compiler/dex/dataflow_iterator-inl.h
@@ -121,6 +121,56 @@
return res;
}
+inline BasicBlock* LoopRepeatingTopologicalSortIterator::Next(bool had_change) {
+ if (idx_ != 0) {
+ // Mark last processed block visited.
+ BasicBlock* bb = mir_graph_->GetBasicBlock(block_id_list_->Get(idx_ - 1));
+ bb->visited = true;
+ if (had_change) {
+ // If we had a change we need to revisit the children.
+ ChildBlockIterator iter(bb, mir_graph_);
+ for (BasicBlock* child_bb = iter.Next(); child_bb != nullptr; child_bb = iter.Next()) {
+ child_bb->visited = false;
+ }
+ }
+ }
+
+ while (true) {
+ // Pop loops we have left and check if we need to recalculate one of them.
+ // NOTE: We need to do this even if idx_ == end_idx_.
+ while (loop_head_stack_->Size() != 0u &&
+ loop_ends_->Get(loop_head_stack_->Peek().first) == idx_) {
+ auto top = loop_head_stack_->Peek();
+ uint16_t loop_head_idx = top.first;
+ bool recalculated = top.second;
+ loop_head_stack_->Pop();
+ BasicBlock* loop_head = mir_graph_->GetBasicBlock(block_id_list_->Get(loop_head_idx));
+ DCHECK(loop_head != nullptr);
+ if (!recalculated || !loop_head->visited) {
+ loop_head_stack_->Insert(std::make_pair(loop_head_idx, true)); // Recalculating this loop.
+ idx_ = loop_head_idx + 1;
+ return loop_head;
+ }
+ }
+
+ if (idx_ == end_idx_) {
+ return nullptr;
+ }
+
+ // Get next block and return it if unvisited.
+ BasicBlockId idx = idx_;
+ idx_ += 1;
+ BasicBlock* bb = mir_graph_->GetBasicBlock(block_id_list_->Get(idx));
+ DCHECK(bb != nullptr);
+ if (!bb->visited) {
+ if (loop_ends_->Get(idx) != 0u) {
+ loop_head_stack_->Insert(std::make_pair(idx, false)); // Not recalculating.
+ }
+ return bb;
+ }
+ }
+}
+
} // namespace art
#endif // ART_COMPILER_DEX_DATAFLOW_ITERATOR_INL_H_