From a4426cff8a81e6af05aa8cc44c162110ccf2d397 Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Wed, 22 Oct 2014 17:15:53 +0100 Subject: [PATCH] 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 --- compiler/dex/global_value_numbering.cc | 13 +--- compiler/dex/global_value_numbering.h | 14 +++++ compiler/dex/global_value_numbering_test.cc | 94 +++++++++++++++++++++++++++++ compiler/dex/local_value_numbering.cc | 76 +++++++++++++++++------ compiler/dex/local_value_numbering.h | 14 ++--- 5 files changed, 173 insertions(+), 38 deletions(-) diff --git a/compiler/dex/global_value_numbering.cc b/compiler/dex/global_value_numbering.cc index f0f7a7051..d311bc76f 100644 --- a/compiler/dex/global_value_numbering.cc +++ b/compiler/dex/global_value_numbering.cc @@ -70,12 +70,7 @@ LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb, 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 @@ LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb, 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 df554cdad..a4a7602c4 100644 --- a/compiler/dex/global_value_numbering.h +++ b/compiler/dex/global_value_numbering.h @@ -105,6 +105,19 @@ class GlobalValueNumbering { 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 @@ class GlobalValueNumbering { ScopedArenaVector 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 82a11a55b..d1bca291b 100644 --- a/compiler/dex/global_value_numbering_test.cc +++ b/compiler/dex/global_value_numbering_test.cc @@ -25,6 +25,8 @@ namespace art { 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 @@ class GlobalValueNumberingTest : public testing::Test { { 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(kMirOpPhi), 0, 0u, 2u, { src1, src2 }, 1, { reg } } @@ -341,6 +345,8 @@ class GlobalValueNumberingTest : public testing::Test { 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 @@ class GlobalValueNumberingTest : public testing::Test { ArenaBitVector* live_in_v_; }; +constexpr uint16_t GlobalValueNumberingTest::kNoValue; + class GlobalValueNumberingTestDiamond : public GlobalValueNumberingTest { public: GlobalValueNumberingTestDiamond(); @@ -981,6 +989,92 @@ TEST_F(GlobalValueNumberingTestDiamond, Phi) { 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 8b7ae20b9..5456f4d0a 100644 --- a/compiler/dex/local_value_numbering.cc +++ b/compiler/dex/local_value_numbering.cc @@ -374,6 +374,12 @@ void LocalValueNumbering::MergeOne(const LocalValueNumbering& other, MergeType m 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 @@ void LocalValueNumbering::PruneNonAliasingRefsForCatch() { 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 @@ void LocalValueNumbering::MergeNullChecked() { 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 @@ void LocalValueNumbering::Merge(MergeType merge_type) { 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::HandleEscapingRef(uint16_t base) { } } +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 @@ uint16_t LocalValueNumbering::HandlePhi(MIR* mir) { // 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 @@ uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) { 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 c60da32b9..dd8d2db8f 100644 --- a/compiler/dex/local_value_numbering.h +++ b/compiler/dex/local_value_numbering.h @@ -44,14 +44,6 @@ class LocalValueNumbering { 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 @@ class LocalValueNumbering { 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 @@ class LocalValueNumbering { } 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 @@ class LocalValueNumbering { 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); -- 2.11.0