From 0d9982daaff119e709d0424a700042751120bd60 Mon Sep 17 00:00:00 2001 From: Serguei Katkov Date: Mon, 10 Aug 2015 12:59:02 +0600 Subject: 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 (cherry picked from commit 2f2f17399f6bdfc5ec94a875152c31ef79620520) Change-Id: I1f08c99cedbe4fd1b96cad11f17d60ab551c7cf7 --- compiler/dex/gvn_dead_code_elimination.cc | 18 ++++- compiler/dex/gvn_dead_code_elimination_test.cc | 105 +++++++++++++++++++++++++ 2 files changed, 121 insertions(+), 2 deletions(-) (limited to 'compiler') 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 @@ void GvnDeadCodeElimination::RecordPassTryToKillOverwrittenMoveOrMoveSrc(uint16_ // 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 @@ void GvnDeadCodeElimination::RecordPassTryToKillOverwrittenMoveOrMoveSrc(uint16_ 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(GvnDeadCodeEliminationTestDiamond, LongOverlaps1) { } } +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(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(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, ArrayLengthThrows) { } } +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(mirs_[i].dalvikInsn.opcode) == kMirOpNop); + EXPECT_EQ(eliminated[i], actually_eliminated) << i; + } +} + } // namespace art -- cgit v1.1