Merge "Quick: Fix wide Phi detection in GVN, clean up INVOKEs."
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);
