Quick: Fix LoopRepeatingTopologicalSortIterator.
Always push the loop head on the loop head stack. This fixes
a bug where we failed to return to an unnatural loop head to
recalculate its GVN data.
Bug: 17410955
Change-Id: I3a2c3225e5d16268c3f56f7f90228759c7da37a9
diff --git a/compiler/dex/dataflow_iterator-inl.h b/compiler/dex/dataflow_iterator-inl.h
index 83dfc28..e9402e3 100644
--- a/compiler/dex/dataflow_iterator-inl.h
+++ b/compiler/dex/dataflow_iterator-inl.h
@@ -181,10 +181,16 @@
idx_ += 1;
BasicBlock* bb = mir_graph_->GetBasicBlock((*block_id_list_)[idx]);
DCHECK(bb != nullptr);
+ if ((*loop_ends_)[idx] != 0u) {
+ // If bb->visited is false, the loop needs to be processed from scratch.
+ // Otherwise we mark it as recalculating; for a natural loop we will not
+ // need to recalculate any block in the loop anyway, and for unnatural
+ // loops we will recalculate the loop head only if one of its predecessors
+ // actually changes.
+ bool recalculating = bb->visited;
+ loop_head_stack_->push_back(std::make_pair(idx, recalculating));
+ }
if (!bb->visited) {
- if ((*loop_ends_)[idx] != 0u) {
- loop_head_stack_->push_back(std::make_pair(idx, false)); // Not recalculating.
- }
return bb;
}
}
diff --git a/compiler/dex/mir_graph_test.cc b/compiler/dex/mir_graph_test.cc
index b3ad040..49b7511 100644
--- a/compiler/dex/mir_graph_test.cc
+++ b/compiler/dex/mir_graph_test.cc
@@ -15,6 +15,7 @@
*/
#include "compiler_ir.h"
+#include "dataflow_iterator-inl.h"
#include "mir_graph.h"
#include "gtest/gtest.h"
@@ -374,4 +375,72 @@
CheckLoopEnds(loop_ends);
}
+TEST_F(TopologicalSortOrderTest, UnnaturalLoops) {
+ const BBDef bbs[] = {
+ DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+ DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+ DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(10)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED1(1)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED2(11, 3)), // Unnatural loop head (top-level).
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED2(3, 4)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC2(9, 7), DEF_PRED1(5)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(8), DEF_PRED1(6)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(9), DEF_PRED2(10, 7)), // Unnatural loop head (nested).
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(10), DEF_PRED2(6, 8)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 11), DEF_PRED1(9)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 2), DEF_PRED1(10)),
+ };
+ const BasicBlockId expected_order[] = {
+ 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 2
+ };
+ const uint16_t loop_ends[] = {
+ 0, 0, 10, 0, 0, 0, 9, 0, 0, 0, 0,
+ };
+
+ PrepareBasicBlocks(bbs);
+ ComputeTopologicalSortOrder();
+ CheckOrder(expected_order);
+ CheckLoopEnds(loop_ends);
+
+ const std::pair<BasicBlockId, bool> expected_and_change[] = {
+ { 1, false },
+ { 3, false },
+ { 4, true }, // Initial run of the outer loop.
+ { 5, true },
+ { 6, true },
+ { 7, true },
+ { 8, true }, // Initial run of the inner loop.
+ { 9, true },
+ { 10, true },
+ { 8, true }, // Recalculation of the inner loop - changed.
+ { 9, true },
+ { 10, true },
+ { 8, false }, // Recalculation of the inner loop - unchanged.
+ { 11, true },
+ { 4, true }, // Recalculation of the outer loop - changed.
+ { 5, true },
+ { 6, true },
+ { 7, false }, // No change: skip inner loop head because inputs are unchanged.
+ { 9, true },
+ { 10, true },
+ { 8, true }, // Recalculation of the inner loop - changed.
+ { 9, true },
+ { 10, true },
+ { 8, false }, // Recalculation of the inner loop - unchanged.
+ { 11, true },
+ { 4, false }, // Recalculation of the outer loop - unchanged.
+ { 2, false },
+ };
+ size_t pos = 0;
+ LoopRepeatingTopologicalSortIterator iter(cu_.mir_graph.get());
+ bool change = false;
+ for (BasicBlock* bb = iter.Next(change); bb != nullptr; bb = iter.Next(change)) {
+ ASSERT_NE(arraysize(expected_and_change), pos);
+ ASSERT_EQ(expected_and_change[pos].first, bb->id) << pos;
+ change = expected_and_change[pos].second;
+ ++pos;
+ }
+ ASSERT_EQ(arraysize(expected_and_change), pos);
+}
+
} // namespace art
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index 7b1ec39..645511e 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -1790,7 +1790,8 @@
pred_mask_union |= pred_mask;
}
}
- DCHECK_EQ(((1u << (IsLoopHead(bb->id) ? bb->nesting_depth - 1u: bb->nesting_depth)) - 1u),
+ // DCHECK_EQ() may not hold for unnatural loop heads, so use DCHECK_GE().
+ DCHECK_GE(((1u << (IsLoopHead(bb->id) ? bb->nesting_depth - 1u: bb->nesting_depth)) - 1u),
pred_mask_union);
suspend_checks_in_loops &= pred_mask_union;
}
