ART: Fix Quick's DCE+GVN
DCE_GVN does not take into account the following case:
mov a, b
...
mov c, b
when optimization tries to replace a with c it must ensure that
for all uses of a there is no new definition of c before use.
Otherwise that use will incorrectly substituted with new c instead
of original b.
Bug: 23102860
Signed-off-by: Serguei Katkov <serguei.i.katkov@intel.com>
(cherry picked from commit 2f2f17399f6bdfc5ec94a875152c31ef79620520)
Change-Id: I1f08c99cedbe4fd1b96cad11f17d60ab551c7cf7
diff --git a/compiler/dex/gvn_dead_code_elimination.cc b/compiler/dex/gvn_dead_code_elimination.cc
index d29b865..4de3410 100644
--- a/compiler/dex/gvn_dead_code_elimination.cc
+++ b/compiler/dex/gvn_dead_code_elimination.cc
@@ -715,6 +715,7 @@
// Try to find a MOVE to a vreg that wasn't changed since check_change.
uint16_t value_name =
data->wide_def ? lvn_->GetSregValueWide(dest_s_reg) : lvn_->GetSregValue(dest_s_reg);
+ uint32_t dest_v_reg = mir_graph_->SRegToVReg(dest_s_reg);
for (size_t c = check_change + 1u, size = vreg_chains_.NumMIRs(); c != size; ++c) {
MIRData* d = vreg_chains_.GetMIRData(c);
if (d->is_move && d->wide_def == data->wide_def &&
@@ -731,8 +732,21 @@
if (!vreg_chains_.IsVRegUsed(check_change + 1u, c, new_dest_v_reg, mir_graph_) &&
(!d->wide_def ||
!vreg_chains_.IsVRegUsed(check_change + 1u, c, new_dest_v_reg + 1, mir_graph_))) {
- RecordPassKillMoveByRenamingSrcDef(check_change, c);
- return;
+ // If the move's destination vreg changed, check if the vreg we're trying
+ // to rename is unused after that change.
+ uint16_t dest_change = vreg_chains_.FindFirstChangeAfter(new_dest_v_reg, c);
+ if (d->wide_def) {
+ uint16_t dest_change_high = vreg_chains_.FindFirstChangeAfter(new_dest_v_reg + 1, c);
+ if (dest_change_high != kNPos &&
+ (dest_change == kNPos || dest_change_high < dest_change)) {
+ dest_change = dest_change_high;
+ }
+ }
+ if (dest_change == kNPos ||
+ !vreg_chains_.IsVRegUsed(dest_change + 1u, size, dest_v_reg, mir_graph_)) {
+ RecordPassKillMoveByRenamingSrcDef(check_change, c);
+ return;
+ }
}
}
}
diff --git a/compiler/dex/gvn_dead_code_elimination_test.cc b/compiler/dex/gvn_dead_code_elimination_test.cc
index 6ba91b6..4df0a8b 100644
--- a/compiler/dex/gvn_dead_code_elimination_test.cc
+++ b/compiler/dex/gvn_dead_code_elimination_test.cc
@@ -1933,6 +1933,78 @@
}
}
+TEST_F(GvnDeadCodeEliminationTestSimple, LongOverlaps2) {
+ static const MIRDef mirs[] = {
+ DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000u),
+ DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 2u, 0u),
+ DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 4u, 2u),
+ };
+
+ // The last insn should overlap the first and second.
+ static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 1, 2 };
+ PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+ PrepareMIRs(mirs);
+ static const int32_t wide_sregs[] = { 0, 2, 4 };
+ MarkAsWideSRegs(wide_sregs);
+ PerformGVN_DCE();
+
+ ASSERT_EQ(arraysize(mirs), value_names_.size());
+ EXPECT_EQ(value_names_[0], value_names_[1]);
+ EXPECT_EQ(value_names_[0], value_names_[2]);
+
+ static const bool eliminated[] = {
+ false, true, true,
+ };
+ static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+ for (size_t i = 0; i != arraysize(eliminated); ++i) {
+ bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+ EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+ }
+ // Check that the CONST_WIDE registers have been correctly renamed.
+ MIR* const_wide = &mirs_[0];
+ ASSERT_EQ(2u, const_wide->ssa_rep->num_defs);
+ EXPECT_EQ(4, const_wide->ssa_rep->defs[0]);
+ EXPECT_EQ(5, const_wide->ssa_rep->defs[1]);
+ EXPECT_EQ(1u, const_wide->dalvikInsn.vA);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, LongOverlaps3) {
+ static const MIRDef mirs[] = {
+ DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000u),
+ DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 2u, 0u),
+ DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 4u, 2u),
+ };
+
+ // The last insn should overlap the first and second.
+ static const int32_t sreg_to_vreg_map[] = { 2, 3, 0, 1, 1, 2 };
+ PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+ PrepareMIRs(mirs);
+ static const int32_t wide_sregs[] = { 0, 2, 4 };
+ MarkAsWideSRegs(wide_sregs);
+ PerformGVN_DCE();
+
+ ASSERT_EQ(arraysize(mirs), value_names_.size());
+ EXPECT_EQ(value_names_[0], value_names_[1]);
+ EXPECT_EQ(value_names_[0], value_names_[2]);
+
+ static const bool eliminated[] = {
+ false, true, true,
+ };
+ static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+ for (size_t i = 0; i != arraysize(eliminated); ++i) {
+ bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+ EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+ }
+ // Check that the CONST_WIDE registers have been correctly renamed.
+ MIR* const_wide = &mirs_[0];
+ ASSERT_EQ(2u, const_wide->ssa_rep->num_defs);
+ EXPECT_EQ(4, const_wide->ssa_rep->defs[0]);
+ EXPECT_EQ(5, const_wide->ssa_rep->defs[1]);
+ EXPECT_EQ(1u, const_wide->dalvikInsn.vA);
+}
+
TEST_F(GvnDeadCodeEliminationTestSimple, MixedOverlaps1) {
static const MIRDef mirs[] = {
DEF_CONST(3, Instruction::CONST, 0u, 1000u),
@@ -2093,4 +2165,37 @@
}
}
+TEST_F(GvnDeadCodeEliminationTestSimple, Dependancy) {
+ static const MIRDef mirs[] = {
+ DEF_MOVE(3, Instruction::MOVE, 5u, 1u), // move v5,v1
+ DEF_MOVE(3, Instruction::MOVE, 6u, 1u), // move v12,v1
+ DEF_MOVE(3, Instruction::MOVE, 7u, 0u), // move v13,v0
+ DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 8u, 2u), // move v0_1,v2_3
+ DEF_MOVE(3, Instruction::MOVE, 10u, 6u), // move v3,v12
+ DEF_MOVE(3, Instruction::MOVE, 11u, 4u), // move v2,v4
+ DEF_MOVE(3, Instruction::MOVE, 12u, 7u), // move v4,v13
+ DEF_MOVE(3, Instruction::MOVE, 13, 11u), // move v12,v2
+ DEF_MOVE(3, Instruction::MOVE, 14u, 10u), // move v2,v3
+ DEF_MOVE(3, Instruction::MOVE, 15u, 5u), // move v3,v5
+ DEF_MOVE(3, Instruction::MOVE, 16u, 12u), // move v5,v4
+ };
+
+ static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 12, 13, 0, 1, 3, 2, 4, 12, 2, 3, 5 };
+ PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+ PrepareMIRs(mirs);
+ static const int32_t wide_sregs[] = { 2, 8 };
+ MarkAsWideSRegs(wide_sregs);
+ PerformGVN_DCE();
+
+ static const bool eliminated[] = {
+ false, false, false, false, false, false, false, true, true, false, false,
+ };
+ static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+ for (size_t i = 0; i != arraysize(eliminated); ++i) {
+ bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+ EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+ }
+}
+
} // namespace art
