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.h b/compiler/dex/dataflow_iterator.h
index 66c524f..06d6832 100644
--- a/compiler/dex/dataflow_iterator.h
+++ b/compiler/dex/dataflow_iterator.h
@@ -388,6 +388,52 @@
}
};
+ /**
+ * @class LoopRepeatingTopologicalSortIterator
+ * @brief Used to perform a Topological Sort Iteration of a MIRGraph, repeating loops as needed.
+ * @details The iterator uses the visited flags to keep track of the blocks that need
+ * recalculation and keeps a stack of loop heads in the MIRGraph. At the end of the loop
+ * it returns back to the loop head if it needs to be recalculated. Due to the use of
+ * the visited flags and the loop head stack in the MIRGraph, it's not possible to use
+ * two iterators at the same time or modify this data during iteration (though inspection
+ * of this data is allowed and sometimes even expected).
+ *
+ * NOTE: This iterator is not suitable for passes that need to propagate changes to
+ * predecessors, such as type inferrence.
+ */
+ class LoopRepeatingTopologicalSortIterator : public DataflowIterator {
+ public:
+ /**
+ * @brief The constructor, using all of the reachable blocks of the MIRGraph.
+ * @param mir_graph The MIRGraph considered.
+ */
+ explicit LoopRepeatingTopologicalSortIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, 0, mir_graph->GetTopologicalSortOrder()->Size()),
+ loop_ends_(mir_graph->GetTopologicalSortOrderLoopEnds()),
+ loop_head_stack_(mir_graph_->GetTopologicalSortOrderLoopHeadStack()) {
+ // Extra setup for RepeatingTopologicalSortIterator.
+ idx_ = start_idx_;
+ block_id_list_ = mir_graph->GetTopologicalSortOrder();
+ // Clear visited flags and check that the loop head stack is empty.
+ mir_graph->ClearAllVisitedFlags();
+ DCHECK_EQ(loop_head_stack_->Size(), 0u);
+ }
+
+ ~LoopRepeatingTopologicalSortIterator() {
+ DCHECK_EQ(loop_head_stack_->Size(), 0u);
+ }
+
+ /**
+ * @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) OVERRIDE;
+
+ private:
+ const GrowableArray<BasicBlockId>* const loop_ends_;
+ GrowableArray<std::pair<uint16_t, bool>>* const loop_head_stack_;
+ };
} // namespace art