Quick: Fix wide Phi detection in GVN, clean up INVOKEs.
The detection of a wide Phi has been incorrectly looking at
the current LVN's wide sreg value map but we only intersect
live values and thus very often lose the information. This
results in failure to identify identical values, i.e.
potential missed optimizations. It also caused the bloating
of the global value map with values we would not use.
Rewrite the wide Phi detection to use the first merged LVN's
notion of wide sreg. For this to work we also need to use
the method's shorty to mark wide arguments.
Also clean up INVOKEs' processing to avoid another source
of bloating the global value map.
Bug: 16398693
Change-Id: I76718af7d62a8c6883ef43e4f47058f7eaf479e1
diff --git a/compiler/dex/global_value_numbering.cc b/compiler/dex/global_value_numbering.cc
index f0f7a70..d311bc7 100644
--- a/compiler/dex/global_value_numbering.cc
+++ b/compiler/dex/global_value_numbering.cc
@@ -70,12 +70,7 @@
DCHECK(work_lvn_.get() == nullptr);
work_lvn_.reset(new (allocator) LocalValueNumbering(this, bb->id, allocator));
if (bb->block_type == kEntryBlock) {
- if ((cu_->access_flags & kAccStatic) == 0) {
- // If non-static method, mark "this" as non-null
- int this_reg = cu_->mir_graph->GetFirstInVR();
- uint16_t value_name = work_lvn_->GetSRegValueName(this_reg);
- work_lvn_->SetValueNameNullChecked(value_name);
- }
+ work_lvn_->PrepareEntryBlock();
DCHECK(bb->first_mir_insn == nullptr); // modifications_allowed_ is irrelevant.
} else {
// To avoid repeated allocation on the ArenaStack, reuse a single vector kept as a member.
@@ -127,12 +122,6 @@
CHECK(!merge_lvns_.empty());
if (merge_lvns_.size() == 1u) {
work_lvn_->MergeOne(*merge_lvns_[0], merge_type);
- BasicBlock* pred_bb = mir_graph_->GetBasicBlock(merge_lvns_[0]->Id());
- if (HasNullCheckLastInsn(pred_bb, bb->id)) {
- int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0];
- uint16_t value_name = merge_lvns_[0]->GetSRegValueName(s_reg);
- work_lvn_->SetValueNameNullChecked(value_name);
- }
} else {
work_lvn_->Merge(merge_type);
}
diff --git a/compiler/dex/global_value_numbering.h b/compiler/dex/global_value_numbering.h
index df554cd..a4a7602 100644
--- a/compiler/dex/global_value_numbering.h
+++ b/compiler/dex/global_value_numbering.h
@@ -105,6 +105,19 @@
return res;
}
+ // Look up a value in the global value map, don't add a new entry if there was none before.
+ uint16_t FindValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
+ uint16_t res;
+ uint64_t key = BuildKey(op, operand1, operand2, modifier);
+ ValueMap::iterator lb = global_value_map_.lower_bound(key);
+ if (lb != global_value_map_.end() && lb->first == key) {
+ res = lb->second;
+ } else {
+ res = kNoValue;
+ }
+ return res;
+ }
+
// Check if the exact value is stored in the global value map.
bool HasValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier,
uint16_t value) const {
@@ -253,6 +266,7 @@
ScopedArenaVector<const LocalValueNumbering*> merge_lvns_; // Not owning.
friend class LocalValueNumbering;
+ friend class GlobalValueNumberingTest;
DISALLOW_COPY_AND_ASSIGN(GlobalValueNumbering);
};
diff --git a/compiler/dex/global_value_numbering_test.cc b/compiler/dex/global_value_numbering_test.cc
index 82a11a5..d1bca29 100644
--- a/compiler/dex/global_value_numbering_test.cc
+++ b/compiler/dex/global_value_numbering_test.cc
@@ -25,6 +25,8 @@
class GlobalValueNumberingTest : public testing::Test {
protected:
+ static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue;
+
struct IFieldDef {
uint16_t field_idx;
uintptr_t declaring_dex_file;
@@ -125,6 +127,8 @@
{ bb, opcode, 0u, 0u, 1, { reg }, 0, { } }
#define DEF_MOVE(bb, opcode, reg, src) \
{ bb, opcode, 0u, 0u, 1, { src }, 1, { reg } }
+#define DEF_MOVE_WIDE(bb, opcode, reg, src) \
+ { bb, opcode, 0u, 0u, 2, { src, src + 1 }, 2, { reg, reg + 1 } }
#define DEF_PHI2(bb, reg, src1, src2) \
{ bb, static_cast<Instruction::Code>(kMirOpPhi), 0, 0u, 2u, { src1, src2 }, 1, { reg } }
@@ -341,6 +345,8 @@
cu_.mir_graph->ssa_base_vregs_.push_back(i);
cu_.mir_graph->ssa_subscripts_.push_back(0);
}
+ // Set shorty for a void-returning method without arguments.
+ cu_.shorty = "V";
}
static constexpr size_t kMaxSsaRegs = 16384u;
@@ -356,6 +362,8 @@
ArenaBitVector* live_in_v_;
};
+constexpr uint16_t GlobalValueNumberingTest::kNoValue;
+
class GlobalValueNumberingTestDiamond : public GlobalValueNumberingTest {
public:
GlobalValueNumberingTestDiamond();
@@ -981,6 +989,92 @@
EXPECT_EQ(value_names_[18], value_names_[21]);
}
+TEST_F(GlobalValueNumberingTestDiamond, PhiWide) {
+ static const MIRDef mirs[] = {
+ DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000),
+ DEF_CONST_WIDE(4, Instruction::CONST_WIDE, 2u, 2000),
+ DEF_CONST_WIDE(5, Instruction::CONST_WIDE, 4u, 3000),
+ DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 6u, 0u),
+ DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 8u, 2u),
+ DEF_MOVE_WIDE(5, Instruction::MOVE_WIDE, 10u, 0u),
+ DEF_MOVE_WIDE(5, Instruction::MOVE_WIDE, 12u, 4u),
+ DEF_PHI2(6, 14u, 6u, 10u), // Same as CONST_WIDE 0u (1000).
+ DEF_PHI2(6, 15u, 7u, 11u), // Same as CONST_WIDE 0u (1000), high word.
+ DEF_PHI2(6, 16u, 6u, 0u), // Same as CONST_WIDE 0u (1000).
+ DEF_PHI2(6, 17u, 7u, 1u), // Same as CONST_WIDE 0u (1000), high word.
+ DEF_PHI2(6, 18u, 0u, 10u), // Same as CONST_WIDE 0u (1000).
+ DEF_PHI2(6, 19u, 1u, 11u), // Same as CONST_WIDE 0u (1000), high word.
+ DEF_PHI2(6, 20u, 8u, 10u), // Merge 2u (2000) and 0u (1000).
+ DEF_PHI2(6, 21u, 9u, 11u), // Merge 2u (2000) and 0u (1000), high word.
+ DEF_PHI2(6, 22u, 2u, 10u), // Merge 2u (2000) and 0u (1000).
+ DEF_PHI2(6, 23u, 3u, 11u), // Merge 2u (2000) and 0u (1000), high word.
+ DEF_PHI2(6, 24u, 8u, 0u), // Merge 2u (2000) and 0u (1000).
+ DEF_PHI2(6, 25u, 9u, 1u), // Merge 2u (2000) and 0u (1000), high word.
+ DEF_PHI2(6, 26u, 2u, 0u), // Merge 2u (2000) and 0u (1000).
+ DEF_PHI2(6, 27u, 5u, 1u), // Merge 2u (2000) and 0u (1000), high word.
+ DEF_PHI2(6, 28u, 6u, 12u), // Merge 0u (1000) and 4u (3000).
+ DEF_PHI2(6, 29u, 7u, 13u), // Merge 0u (1000) and 4u (3000), high word.
+ DEF_PHI2(6, 30u, 0u, 12u), // Merge 0u (1000) and 4u (3000).
+ DEF_PHI2(6, 31u, 1u, 13u), // Merge 0u (1000) and 4u (3000), high word.
+ DEF_PHI2(6, 32u, 6u, 4u), // Merge 0u (1000) and 4u (3000).
+ DEF_PHI2(6, 33u, 7u, 5u), // Merge 0u (1000) and 4u (3000), high word.
+ DEF_PHI2(6, 34u, 0u, 4u), // Merge 0u (1000) and 4u (3000).
+ DEF_PHI2(6, 35u, 1u, 5u), // Merge 0u (1000) and 4u (3000), high word.
+ DEF_PHI2(6, 36u, 8u, 12u), // Merge 2u (2000) and 4u (3000).
+ DEF_PHI2(6, 37u, 9u, 13u), // Merge 2u (2000) and 4u (3000), high word.
+ DEF_PHI2(6, 38u, 2u, 12u), // Merge 2u (2000) and 4u (3000).
+ DEF_PHI2(6, 39u, 3u, 13u), // Merge 2u (2000) and 4u (3000), high word.
+ DEF_PHI2(6, 40u, 8u, 4u), // Merge 2u (2000) and 4u (3000).
+ DEF_PHI2(6, 41u, 9u, 5u), // Merge 2u (2000) and 4u (3000), high word.
+ DEF_PHI2(6, 42u, 2u, 4u), // Merge 2u (2000) and 4u (3000).
+ DEF_PHI2(6, 43u, 3u, 5u), // Merge 2u (2000) and 4u (3000), high word.
+ };
+
+ PrepareMIRs(mirs);
+ PerformGVN();
+ ASSERT_EQ(arraysize(mirs), value_names_.size());
+ EXPECT_EQ(value_names_[0], value_names_[7]);
+ EXPECT_EQ(value_names_[0], value_names_[9]);
+ EXPECT_EQ(value_names_[0], value_names_[11]);
+ EXPECT_NE(value_names_[13], value_names_[0]);
+ EXPECT_NE(value_names_[13], value_names_[1]);
+ EXPECT_NE(value_names_[13], value_names_[2]);
+ EXPECT_EQ(value_names_[13], value_names_[15]);
+ EXPECT_EQ(value_names_[13], value_names_[17]);
+ EXPECT_EQ(value_names_[13], value_names_[19]);
+ EXPECT_NE(value_names_[21], value_names_[0]);
+ EXPECT_NE(value_names_[21], value_names_[1]);
+ EXPECT_NE(value_names_[21], value_names_[2]);
+ EXPECT_NE(value_names_[21], value_names_[13]);
+ EXPECT_EQ(value_names_[21], value_names_[23]);
+ EXPECT_EQ(value_names_[21], value_names_[25]);
+ EXPECT_EQ(value_names_[21], value_names_[27]);
+ EXPECT_NE(value_names_[29], value_names_[0]);
+ EXPECT_NE(value_names_[29], value_names_[1]);
+ EXPECT_NE(value_names_[29], value_names_[2]);
+ EXPECT_NE(value_names_[29], value_names_[13]);
+ EXPECT_NE(value_names_[29], value_names_[21]);
+ EXPECT_EQ(value_names_[29], value_names_[31]);
+ EXPECT_EQ(value_names_[29], value_names_[33]);
+ EXPECT_EQ(value_names_[29], value_names_[35]);
+ // High words should get kNoValue.
+ EXPECT_EQ(value_names_[8], kNoValue);
+ EXPECT_EQ(value_names_[10], kNoValue);
+ EXPECT_EQ(value_names_[12], kNoValue);
+ EXPECT_EQ(value_names_[14], kNoValue);
+ EXPECT_EQ(value_names_[16], kNoValue);
+ EXPECT_EQ(value_names_[18], kNoValue);
+ EXPECT_EQ(value_names_[20], kNoValue);
+ EXPECT_EQ(value_names_[22], kNoValue);
+ EXPECT_EQ(value_names_[24], kNoValue);
+ EXPECT_EQ(value_names_[26], kNoValue);
+ EXPECT_EQ(value_names_[28], kNoValue);
+ EXPECT_EQ(value_names_[30], kNoValue);
+ EXPECT_EQ(value_names_[32], kNoValue);
+ EXPECT_EQ(value_names_[34], kNoValue);
+ EXPECT_EQ(value_names_[36], kNoValue);
+}
+
TEST_F(GlobalValueNumberingTestLoop, NonAliasingIFields) {
static const IFieldDef ifields[] = {
{ 0u, 1u, 0u, false }, // Int.
diff --git a/compiler/dex/local_value_numbering.cc b/compiler/dex/local_value_numbering.cc
index 8b7ae20..5456f4d 100644
--- a/compiler/dex/local_value_numbering.cc
+++ b/compiler/dex/local_value_numbering.cc
@@ -374,6 +374,12 @@
range_checked_ = other.range_checked_;
null_checked_ = other.null_checked_;
+ const BasicBlock* pred_bb = gvn_->GetBasicBlock(other.Id());
+ if (GlobalValueNumbering::HasNullCheckLastInsn(pred_bb, Id())) {
+ int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0];
+ null_checked_.insert(other.GetOperandValue(s_reg));
+ }
+
if (merge_type == kCatchMerge) {
// Memory is clobbered. Use new memory version and don't merge aliasing locations.
global_memory_version_ = NewMemoryVersion(&merge_new_memory_version_);
@@ -465,10 +471,7 @@
DCHECK(mir != nullptr);
// Only INVOKEs can leak and clobber non-aliasing references if they throw.
if ((mir->dalvikInsn.FlagsOf() & Instruction::kInvoke) != 0) {
- for (uint16_t i = 0u; i != mir->ssa_rep->num_uses; ++i) {
- uint16_t value_name = lvn->GetOperandValue(mir->ssa_rep->uses[i]);
- non_aliasing_refs_.erase(value_name);
- }
+ HandleInvokeArgs(mir, lvn);
}
}
}
@@ -681,7 +684,7 @@
const BasicBlock* least_entries_bb = gvn_->GetBasicBlock(least_entries_lvn->Id());
if (gvn_->HasNullCheckLastInsn(least_entries_bb, id_)) {
int s_reg = least_entries_bb->last_mir_insn->ssa_rep->uses[0];
- uint32_t value_name = least_entries_lvn->GetSRegValueName(s_reg);
+ uint32_t value_name = least_entries_lvn->GetOperandValue(s_reg);
merge_names_.clear();
merge_names_.resize(gvn_->merge_lvns_.size(), value_name);
if (gvn_->NullCheckedInAllPredecessors(merge_names_)) {
@@ -953,6 +956,26 @@
AliasingArrayVersions>>();
}
+void LocalValueNumbering::PrepareEntryBlock() {
+ uint32_t vreg = gvn_->GetMirGraph()->GetFirstInVR();
+ CompilationUnit* cu = gvn_->GetCompilationUnit();
+ const char* shorty = cu->shorty;
+ ++shorty; // Skip return value.
+ if ((cu->access_flags & kAccStatic) == 0) {
+ // If non-static method, mark "this" as non-null
+ uint16_t value_name = GetOperandValue(vreg);
+ ++vreg;
+ null_checked_.insert(value_name);
+ }
+ for ( ; *shorty != 0; ++shorty, ++vreg) {
+ if (*shorty == 'J' || *shorty == 'D') {
+ uint16_t value_name = GetOperandValueWide(vreg);
+ SetOperandValueWide(vreg, value_name);
+ ++vreg;
+ }
+ }
+}
+
uint16_t LocalValueNumbering::MarkNonAliasingNonNull(MIR* mir) {
uint16_t res = GetOperandValue(mir->ssa_rep->defs[0]);
DCHECK(null_checked_.find(res) == null_checked_.end());
@@ -1039,12 +1062,30 @@
}
}
+void LocalValueNumbering::HandleInvokeArgs(const MIR* mir, const LocalValueNumbering* mir_lvn) {
+ const int32_t* uses = mir->ssa_rep->uses;
+ const int32_t* uses_end = uses + mir->ssa_rep->num_uses;
+ while (uses != uses_end) {
+ uint16_t sreg = *uses;
+ ++uses;
+ // Avoid LookupValue() so that we don't store new values in the global value map.
+ auto local_it = mir_lvn->sreg_value_map_.find(sreg);
+ if (local_it != mir_lvn->sreg_value_map_.end()) {
+ non_aliasing_refs_.erase(local_it->second);
+ } else {
+ uint16_t value_name = gvn_->FindValue(kNoValue, sreg, kNoValue, kNoValue);
+ if (value_name != kNoValue) {
+ non_aliasing_refs_.erase(value_name);
+ }
+ }
+ }
+}
+
uint16_t LocalValueNumbering::HandlePhi(MIR* mir) {
if (gvn_->merge_lvns_.empty()) {
// Running LVN without a full GVN?
return kNoValue;
}
- int16_t num_uses = mir->ssa_rep->num_uses;
int32_t* uses = mir->ssa_rep->uses;
// Try to find out if this is merging wide regs.
if (mir->ssa_rep->defs[0] != 0 &&
@@ -1052,18 +1093,20 @@
// This is the high part of a wide reg. Ignore the Phi.
return kNoValue;
}
- bool wide = false;
- for (int16_t i = 0; i != num_uses; ++i) {
- if (sreg_wide_value_map_.count(uses[i]) != 0u) {
- wide = true;
- break;
- }
+ BasicBlockId* incoming = mir->meta.phi_incoming;
+ int16_t pos = 0;
+ // Check if we're merging a wide value based on the first merged LVN.
+ const LocalValueNumbering* first_lvn = gvn_->merge_lvns_[0];
+ DCHECK_LT(pos, mir->ssa_rep->num_uses);
+ while (incoming[pos] != first_lvn->Id()) {
+ ++pos;
+ DCHECK_LT(pos, mir->ssa_rep->num_uses);
}
+ int first_s_reg = uses[pos];
+ bool wide = (first_lvn->sreg_wide_value_map_.count(first_s_reg) != 0u);
// Iterate over *merge_lvns_ and skip incoming sregs for BBs without associated LVN.
uint16_t value_name = kNoValue;
merge_names_.clear();
- BasicBlockId* incoming = mir->meta.phi_incoming;
- int16_t pos = 0;
bool same_values = true;
for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
DCHECK_LT(pos, mir->ssa_rep->num_uses);
@@ -1468,10 +1511,7 @@
case Instruction::INVOKE_STATIC:
case Instruction::INVOKE_STATIC_RANGE:
// Make ref args aliasing.
- for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) {
- uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]);
- non_aliasing_refs_.erase(reg);
- }
+ HandleInvokeArgs(mir, this);
HandleInvokeOrClInitOrAcquireOp(mir);
break;
diff --git a/compiler/dex/local_value_numbering.h b/compiler/dex/local_value_numbering.h
index c60da32..dd8d2db 100644
--- a/compiler/dex/local_value_numbering.h
+++ b/compiler/dex/local_value_numbering.h
@@ -44,14 +44,6 @@
bool Equals(const LocalValueNumbering& other) const;
- uint16_t GetSRegValueName(uint16_t s_reg) const {
- return GetOperandValue(s_reg);
- }
-
- void SetValueNameNullChecked(uint16_t value_name) {
- null_checked_.insert(value_name);
- }
-
bool IsValueNullChecked(uint16_t value_name) const {
return null_checked_.find(value_name) != null_checked_.end();
}
@@ -73,6 +65,7 @@
void MergeOne(const LocalValueNumbering& other, MergeType merge_type);
void Merge(MergeType merge_type); // Merge gvn_->merge_lvns_.
+ void PrepareEntryBlock();
uint16_t GetValueNumber(MIR* mir);
@@ -121,18 +114,22 @@
}
void SetOperandValue(uint16_t s_reg, uint16_t value) {
+ DCHECK_EQ(sreg_wide_value_map_.count(s_reg), 0u);
SetOperandValueImpl(s_reg, value, &sreg_value_map_);
}
uint16_t GetOperandValue(int s_reg) const {
+ DCHECK_EQ(sreg_wide_value_map_.count(s_reg), 0u);
return GetOperandValueImpl(s_reg, &sreg_value_map_);
}
void SetOperandValueWide(uint16_t s_reg, uint16_t value) {
+ DCHECK_EQ(sreg_value_map_.count(s_reg), 0u);
SetOperandValueImpl(s_reg, value, &sreg_wide_value_map_);
}
uint16_t GetOperandValueWide(int s_reg) const {
+ DCHECK_EQ(sreg_value_map_.count(s_reg), 0u);
return GetOperandValueImpl(s_reg, &sreg_wide_value_map_);
}
@@ -300,6 +297,7 @@
void HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index);
void HandlePutObject(MIR* mir);
void HandleEscapingRef(uint16_t base);
+ void HandleInvokeArgs(const MIR* mir, const LocalValueNumbering* mir_lvn);
uint16_t HandlePhi(MIR* mir);
uint16_t HandleAGet(MIR* mir, uint16_t opcode);
void HandleAPut(MIR* mir, uint16_t opcode);