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

2 files changed, 121 insertions, 2 deletions

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<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, 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<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+}
+
 }  // namespace art