Quick: Fix DCE to mark wide register overlaps correctly.
Previously we missed some cases of overlap with registers
coming from previous blocks.
Bug: 20640451
(cherry picked from commit 83d46ef1eaa8fdecadfdb9564d80e50b42646c37)
Change-Id: I1be879edfbc900b70cee411d9e31e5a4b524530a
diff --git a/compiler/dex/gvn_dead_code_elimination.cc b/compiler/dex/gvn_dead_code_elimination.cc
index a4319c3..6e1e414 100644
--- a/compiler/dex/gvn_dead_code_elimination.cc
+++ b/compiler/dex/gvn_dead_code_elimination.cc
@@ -20,6 +20,7 @@
#include "base/bit_vector-inl.h"
#include "base/macros.h"
+#include "base/allocator.h"
#include "compiler_enums.h"
#include "dataflow_iterator-inl.h"
#include "dex_instruction.h"
@@ -75,6 +76,9 @@
GvnDeadCodeElimination::VRegChains::VRegChains(uint32_t num_vregs, ScopedArenaAllocator* alloc)
: num_vregs_(num_vregs),
vreg_data_(alloc->AllocArray<VRegValue>(num_vregs, kArenaAllocMisc)),
+ vreg_high_words_(num_vregs, false, Allocator::GetNoopAllocator(),
+ BitVector::BitsToWords(num_vregs),
+ alloc->AllocArray<uint32_t>(BitVector::BitsToWords(num_vregs))),
mir_data_(alloc->Adapter()) {
mir_data_.reserve(100);
}
@@ -82,6 +86,7 @@
inline void GvnDeadCodeElimination::VRegChains::Reset() {
DCHECK(mir_data_.empty());
std::fill_n(vreg_data_, num_vregs_, VRegValue());
+ vreg_high_words_.ClearAllBits();
}
void GvnDeadCodeElimination::VRegChains::AddMIRWithDef(MIR* mir, int v_reg, bool wide,
@@ -93,24 +98,26 @@
data->wide_def = wide;
data->vreg_def = v_reg;
- if (vreg_data_[v_reg].change != kNPos &&
- mir_data_[vreg_data_[v_reg].change].vreg_def + 1 == v_reg) {
- data->low_def_over_high_word = true;
- }
- data->prev_value = vreg_data_[v_reg];
DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+ data->prev_value = vreg_data_[v_reg];
+ data->low_def_over_high_word =
+ (vreg_data_[v_reg].change != kNPos)
+ ? GetMIRData(vreg_data_[v_reg].change)->vreg_def + 1 == v_reg
+ : vreg_high_words_.IsBitSet(v_reg);
vreg_data_[v_reg].value = new_value;
vreg_data_[v_reg].change = pos;
+ vreg_high_words_.ClearBit(v_reg);
if (wide) {
- if (vreg_data_[v_reg + 1].change != kNPos &&
- mir_data_[vreg_data_[v_reg + 1].change].vreg_def == v_reg + 1) {
- data->high_def_over_low_word = true;
- }
- data->prev_value_high = vreg_data_[v_reg + 1];
DCHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_);
+ data->prev_value_high = vreg_data_[v_reg + 1];
+ data->high_def_over_low_word =
+ (vreg_data_[v_reg + 1].change != kNPos)
+ ? GetMIRData(vreg_data_[v_reg + 1].change)->vreg_def == v_reg + 1
+ : !vreg_high_words_.IsBitSet(v_reg + 1);
vreg_data_[v_reg + 1].value = new_value;
vreg_data_[v_reg + 1].change = pos;
+ vreg_high_words_.SetBit(v_reg + 1);
}
}
@@ -123,9 +130,17 @@
if (data->has_def) {
DCHECK_EQ(vreg_data_[data->vreg_def].change, NumMIRs() - 1u);
vreg_data_[data->vreg_def] = data->prev_value;
+ DCHECK(!vreg_high_words_.IsBitSet(data->vreg_def));
+ if (data->low_def_over_high_word) {
+ vreg_high_words_.SetBit(data->vreg_def);
+ }
if (data->wide_def) {
DCHECK_EQ(vreg_data_[data->vreg_def + 1].change, NumMIRs() - 1u);
vreg_data_[data->vreg_def + 1] = data->prev_value_high;
+ DCHECK(vreg_high_words_.IsBitSet(data->vreg_def + 1));
+ if (data->high_def_over_low_word) {
+ vreg_high_words_.ClearBit(data->vreg_def + 1);
+ }
}
}
mir_data_.pop_back();
@@ -169,6 +184,7 @@
uint16_t change = vreg_data_[v_reg].change;
if (change == kNPos) {
vreg_data_[v_reg].value = value;
+ vreg_high_words_.SetBit(v_reg);
} else {
while (true) {
MIRData* data = &mir_data_[change];
@@ -208,6 +224,7 @@
}
}
vreg_data_[v_reg].value = old_value;
+ DCHECK(!vreg_high_words_.IsBitSet(v_reg)); // Keep marked as low word.
}
} else {
DCHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_);
@@ -223,6 +240,7 @@
old_value = lvn->GetStartingVregValueNumber(v_reg);
}
vreg_data_[v_reg].value = old_value;
+ DCHECK(!vreg_high_words_.IsBitSet(v_reg)); // Keep marked as low word.
}
if (check_high && vreg_data_[v_reg + 1].value == kNoValue) {
uint16_t old_value = lvn->GetStartingVregValueNumber(v_reg + 1);
@@ -234,6 +252,7 @@
}
}
vreg_data_[v_reg + 1].value = old_value;
+ DCHECK(!vreg_high_words_.IsBitSet(v_reg + 1)); // Keep marked as low word.
}
}
}
@@ -300,6 +319,8 @@
if (next_change == kNPos) {
DCHECK_EQ(vreg_data_[v_reg].change, old_change);
vreg_data_[v_reg].change = new_change;
+ DCHECK_EQ(vreg_high_words_.IsBitSet(v_reg), v_reg == old_data->vreg_def + 1);
+ // No change in vreg_high_words_.
} else {
DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), old_change);
mir_data_[next_change].SetPrevChange(v_reg, new_change);
@@ -316,6 +337,12 @@
if (next_change == kNPos) {
DCHECK_EQ(vreg_data_[v_reg].change, change);
vreg_data_[v_reg] = (data->vreg_def == v_reg) ? data->prev_value : data->prev_value_high;
+ DCHECK_EQ(vreg_high_words_.IsBitSet(v_reg), v_reg == data->vreg_def + 1);
+ if (data->vreg_def == v_reg && data->low_def_over_high_word) {
+ vreg_high_words_.SetBit(v_reg);
+ } else if (data->vreg_def != v_reg && data->high_def_over_low_word) {
+ vreg_high_words_.ClearBit(v_reg);
+ }
} else {
DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), change);
mir_data_[next_change].RemovePrevChange(v_reg, data);
diff --git a/compiler/dex/gvn_dead_code_elimination.h b/compiler/dex/gvn_dead_code_elimination.h
index bc75a01..06022db 100644
--- a/compiler/dex/gvn_dead_code_elimination.h
+++ b/compiler/dex/gvn_dead_code_elimination.h
@@ -121,6 +121,7 @@
private:
const uint32_t num_vregs_;
VRegValue* const vreg_data_;
+ BitVector vreg_high_words_;
ScopedArenaVector<MIRData> mir_data_;
};
diff --git a/compiler/dex/gvn_dead_code_elimination_test.cc b/compiler/dex/gvn_dead_code_elimination_test.cc
index efb32bb..4f81273 100644
--- a/compiler/dex/gvn_dead_code_elimination_test.cc
+++ b/compiler/dex/gvn_dead_code_elimination_test.cc
@@ -1896,4 +1896,39 @@
EXPECT_EQ(2u, phi->dalvikInsn.vA);
}
+TEST_F(GvnDeadCodeEliminationTestDiamond, LongOverlaps1) {
+ static const MIRDef mirs[] = {
+ DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000u),
+ DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 2u, 1000u),
+ DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 4u, 0u),
+ DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 6u, 2u),
+ DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 8u, 4u),
+ DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 10u, 6u),
+ };
+
+ // The last insn should overlap the first and second.
+ static const int32_t sreg_to_vreg_map[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3 };
+ PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+ PrepareMIRs(mirs);
+ static const int32_t wide_sregs[] = { 0, 2, 4, 6, 8, 10 };
+ 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]);
+ EXPECT_EQ(value_names_[0], value_names_[3]);
+ EXPECT_EQ(value_names_[0], value_names_[4]);
+
+ static const bool eliminated[] = {
+ false, false, false, false, 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
diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index 65cb028..39ce0d2 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -24,11 +24,6 @@
namespace art {
-// The number of words necessary to encode bits.
-static constexpr uint32_t BitsToWords(uint32_t bits) {
- return RoundUp(bits, 32) / 32;
-}
-
// TODO: replace excessive argument defaulting when we are at gcc 4.7
// or later on host with delegating constructor support. Specifically,
// starts_bits and storage_size/storage are mutually exclusive.
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index be4d363..6e4367a 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -20,6 +20,8 @@
#include <stdint.h>
#include <iterator>
+#include "utils.h"
+
namespace art {
class Allocator;
@@ -116,6 +118,11 @@
virtual ~BitVector();
+ // The number of words necessary to encode bits.
+ static constexpr uint32_t BitsToWords(uint32_t bits) {
+ return RoundUp(bits, kWordBits) / kWordBits;
+ }
+
// Mark the specified bit as "set".
void SetBit(uint32_t idx) {
/*
