Dead code elimination based on GVN results.
Change-Id: I5b77411a8f088f0b561da14b123cf6b0501c9db5
diff --git a/compiler/dex/gvn_dead_code_elimination.cc b/compiler/dex/gvn_dead_code_elimination.cc
new file mode 100644
index 0000000..2e7f032
--- /dev/null
+++ b/compiler/dex/gvn_dead_code_elimination.cc
@@ -0,0 +1,1391 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <sstream>
+
+#include "gvn_dead_code_elimination.h"
+
+#include "base/bit_vector-inl.h"
+#include "base/macros.h"
+#include "compiler_enums.h"
+#include "dataflow_iterator-inl.h"
+#include "dex_instruction.h"
+#include "dex/mir_graph.h"
+#include "local_value_numbering.h"
+#include "utils/arena_bit_vector.h"
+
+namespace art {
+
+constexpr uint16_t GvnDeadCodeElimination::kNoValue;
+constexpr uint16_t GvnDeadCodeElimination::kNPos;
+
+inline uint16_t GvnDeadCodeElimination::MIRData::PrevChange(int v_reg) const {
+ DCHECK(has_def);
+ DCHECK(v_reg == vreg_def || v_reg == vreg_def + 1);
+ return (v_reg == vreg_def) ? prev_value.change : prev_value_high.change;
+}
+
+inline void GvnDeadCodeElimination::MIRData::SetPrevChange(int v_reg, uint16_t change) {
+ DCHECK(has_def);
+ DCHECK(v_reg == vreg_def || v_reg == vreg_def + 1);
+ if (v_reg == vreg_def) {
+ prev_value.change = change;
+ } else {
+ prev_value_high.change = change;
+ }
+}
+
+inline void GvnDeadCodeElimination::MIRData::RemovePrevChange(int v_reg, MIRData* prev_data) {
+ DCHECK_NE(PrevChange(v_reg), kNPos);
+ DCHECK(v_reg == prev_data->vreg_def || v_reg == prev_data->vreg_def + 1);
+ if (vreg_def == v_reg) {
+ if (prev_data->vreg_def == v_reg) {
+ prev_value = prev_data->prev_value;
+ low_def_over_high_word = prev_data->low_def_over_high_word;
+ } else {
+ prev_value = prev_data->prev_value_high;
+ low_def_over_high_word =
+ prev_data->prev_value_high.value != kNPos && !prev_data->high_def_over_low_word;
+ }
+ } else {
+ if (prev_data->vreg_def == v_reg) {
+ prev_value_high = prev_data->prev_value;
+ high_def_over_low_word =
+ prev_data->prev_value.value != kNPos && !prev_data->low_def_over_high_word;
+ } else {
+ prev_value_high = prev_data->prev_value_high;
+ high_def_over_low_word = prev_data->high_def_over_low_word;
+ }
+ }
+}
+
+GvnDeadCodeElimination::VRegChains::VRegChains(uint32_t num_vregs, ScopedArenaAllocator* alloc)
+ : num_vregs_(num_vregs),
+ vreg_data_(alloc->AllocArray<VRegValue>(num_vregs, kArenaAllocMisc)),
+ mir_data_(alloc->Adapter()) {
+ mir_data_.reserve(100);
+}
+
+inline void GvnDeadCodeElimination::VRegChains::Reset() {
+ DCHECK(mir_data_.empty());
+ std::fill_n(vreg_data_, num_vregs_, VRegValue());
+}
+
+void GvnDeadCodeElimination::VRegChains::AddMIRWithDef(MIR* mir, int v_reg, bool wide,
+ uint16_t new_value) {
+ uint16_t pos = mir_data_.size();
+ mir_data_.emplace_back(mir);
+ MIRData* data = &mir_data_.back();
+ data->has_def = true;
+ 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_);
+ vreg_data_[v_reg].value = new_value;
+ vreg_data_[v_reg].change = pos;
+
+ 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_);
+ vreg_data_[v_reg + 1].value = new_value;
+ vreg_data_[v_reg + 1].change = pos;
+ }
+}
+
+inline void GvnDeadCodeElimination::VRegChains::AddMIRWithoutDef(MIR* mir) {
+ mir_data_.emplace_back(mir);
+}
+
+void GvnDeadCodeElimination::VRegChains::RemoveLastMIRData() {
+ MIRData* data = LastMIRData();
+ if (data->has_def) {
+ DCHECK_EQ(vreg_data_[data->vreg_def].change, NumMIRs() - 1u);
+ vreg_data_[data->vreg_def] = data->prev_value;
+ 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;
+ }
+ }
+ mir_data_.pop_back();
+}
+
+void GvnDeadCodeElimination::VRegChains::RemoveTrailingNops() {
+ // There's at least one NOP to drop. There may be more.
+ MIRData* last_data = LastMIRData();
+ DCHECK(!last_data->must_keep && !last_data->has_def);
+ do {
+ DCHECK_EQ(static_cast<int>(last_data->mir->dalvikInsn.opcode), static_cast<int>(kMirOpNop));
+ mir_data_.pop_back();
+ if (mir_data_.empty()) {
+ break;
+ }
+ last_data = LastMIRData();
+ } while (!last_data->must_keep && !last_data->has_def);
+}
+
+inline size_t GvnDeadCodeElimination::VRegChains::NumMIRs() const {
+ return mir_data_.size();
+}
+
+inline GvnDeadCodeElimination::MIRData* GvnDeadCodeElimination::VRegChains::GetMIRData(size_t pos) {
+ DCHECK_LT(pos, mir_data_.size());
+ return &mir_data_[pos];
+}
+
+inline GvnDeadCodeElimination::MIRData* GvnDeadCodeElimination::VRegChains::LastMIRData() {
+ DCHECK(!mir_data_.empty());
+ return &mir_data_.back();
+}
+
+uint32_t GvnDeadCodeElimination::VRegChains::NumVRegs() const {
+ return num_vregs_;
+}
+
+void GvnDeadCodeElimination::VRegChains::InsertInitialValueHigh(int v_reg, uint16_t value) {
+ DCHECK_NE(value, kNoValue);
+ DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+ uint16_t change = vreg_data_[v_reg].change;
+ if (change == kNPos) {
+ vreg_data_[v_reg].value = value;
+ } else {
+ while (true) {
+ MIRData* data = &mir_data_[change];
+ DCHECK(data->vreg_def == v_reg || data->vreg_def + 1 == v_reg);
+ if (data->vreg_def == v_reg) { // Low word, use prev_value.
+ if (data->prev_value.change == kNPos) {
+ DCHECK_EQ(data->prev_value.value, kNoValue);
+ data->prev_value.value = value;
+ data->low_def_over_high_word = true;
+ break;
+ }
+ change = data->prev_value.change;
+ } else { // High word, use prev_value_high.
+ if (data->prev_value_high.change == kNPos) {
+ DCHECK_EQ(data->prev_value_high.value, kNoValue);
+ data->prev_value_high.value = value;
+ break;
+ }
+ change = data->prev_value_high.change;
+ }
+ }
+ }
+}
+
+void GvnDeadCodeElimination::VRegChains::UpdateInitialVRegValue(int v_reg, bool wide,
+ const LocalValueNumbering* lvn) {
+ DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+ if (!wide) {
+ if (vreg_data_[v_reg].value == kNoValue) {
+ uint16_t old_value = lvn->GetStartingVregValueNumber(v_reg);
+ if (old_value == kNoValue) {
+ // Maybe there was a wide value in v_reg before. Do not check for wide value in v_reg-1,
+ // that will be done only if we see a definition of v_reg-1, otherwise it's unnecessary.
+ old_value = lvn->GetStartingVregValueNumberWide(v_reg);
+ if (old_value != kNoValue) {
+ InsertInitialValueHigh(v_reg + 1, old_value);
+ }
+ }
+ vreg_data_[v_reg].value = old_value;
+ }
+ } else {
+ DCHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_);
+ bool check_high = true;
+ if (vreg_data_[v_reg].value == kNoValue) {
+ uint16_t old_value = lvn->GetStartingVregValueNumberWide(v_reg);
+ if (old_value != kNoValue) {
+ InsertInitialValueHigh(v_reg + 1, old_value);
+ check_high = false; // High word has been processed.
+ } else {
+ // Maybe there was a narrow value before. Do not check for wide value in v_reg-1,
+ // that will be done only if we see a definition of v_reg-1, otherwise it's unnecessary.
+ old_value = lvn->GetStartingVregValueNumber(v_reg);
+ }
+ vreg_data_[v_reg].value = old_value;
+ }
+ if (check_high && vreg_data_[v_reg + 1].value == kNoValue) {
+ uint16_t old_value = lvn->GetStartingVregValueNumber(v_reg + 1);
+ if (old_value == kNoValue && static_cast<size_t>(v_reg + 2) < num_vregs_) {
+ // Maybe there was a wide value before.
+ old_value = lvn->GetStartingVregValueNumberWide(v_reg + 1);
+ if (old_value != kNoValue) {
+ InsertInitialValueHigh(v_reg + 2, old_value);
+ }
+ }
+ vreg_data_[v_reg + 1].value = old_value;
+ }
+ }
+}
+
+inline uint16_t GvnDeadCodeElimination::VRegChains::LastChange(int v_reg) {
+ DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+ return vreg_data_[v_reg].change;
+}
+
+inline uint16_t GvnDeadCodeElimination::VRegChains::CurrentValue(int v_reg) {
+ DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+ return vreg_data_[v_reg].value;
+}
+
+uint16_t GvnDeadCodeElimination::VRegChains::FindKillHead(int v_reg, uint16_t cutoff) {
+ uint16_t current_value = this->CurrentValue(v_reg);
+ DCHECK_NE(current_value, kNoValue);
+ uint16_t change = LastChange(v_reg);
+ DCHECK_LT(change, mir_data_.size());
+ DCHECK_GE(change, cutoff);
+ bool match_high_word = (mir_data_[change].vreg_def != v_reg);
+ do {
+ MIRData* data = &mir_data_[change];
+ DCHECK(data->vreg_def == v_reg || data->vreg_def + 1 == v_reg);
+ if (data->vreg_def == v_reg) { // Low word, use prev_value.
+ if (data->prev_value.value == current_value &&
+ match_high_word == data->low_def_over_high_word) {
+ break;
+ }
+ change = data->prev_value.change;
+ } else { // High word, use prev_value_high.
+ if (data->prev_value_high.value == current_value &&
+ match_high_word != data->high_def_over_low_word) {
+ break;
+ }
+ change = data->prev_value_high.change;
+ }
+ if (change < cutoff) {
+ change = kNPos;
+ }
+ } while (change != kNPos);
+ return change;
+}
+
+uint16_t GvnDeadCodeElimination::VRegChains::FindFirstChangeAfter(int v_reg,
+ uint16_t change) const {
+ DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+ DCHECK_LT(change, mir_data_.size());
+ uint16_t result = kNPos;
+ uint16_t search_change = vreg_data_[v_reg].change;
+ while (search_change != kNPos && search_change > change) {
+ result = search_change;
+ search_change = mir_data_[search_change].PrevChange(v_reg);
+ }
+ return result;
+}
+
+void GvnDeadCodeElimination::VRegChains::ReplaceChange(uint16_t old_change, uint16_t new_change) {
+ const MIRData* old_data = GetMIRData(old_change);
+ DCHECK(old_data->has_def);
+ int count = old_data->wide_def ? 2 : 1;
+ for (int v_reg = old_data->vreg_def, end = old_data->vreg_def + count; v_reg != end; ++v_reg) {
+ uint16_t next_change = FindFirstChangeAfter(v_reg, old_change);
+ if (next_change == kNPos) {
+ DCHECK_EQ(vreg_data_[v_reg].change, old_change);
+ vreg_data_[v_reg].change = new_change;
+ } else {
+ DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), old_change);
+ mir_data_[next_change].SetPrevChange(v_reg, new_change);
+ }
+ }
+}
+
+void GvnDeadCodeElimination::VRegChains::RemoveChange(uint16_t change) {
+ MIRData* data = &mir_data_[change];
+ DCHECK(data->has_def);
+ int count = data->wide_def ? 2 : 1;
+ for (int v_reg = data->vreg_def, end = data->vreg_def + count; v_reg != end; ++v_reg) {
+ uint16_t next_change = FindFirstChangeAfter(v_reg, change);
+ 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;
+ } else {
+ DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), change);
+ mir_data_[next_change].RemovePrevChange(v_reg, data);
+ }
+ }
+}
+
+inline bool GvnDeadCodeElimination::VRegChains::IsTopChange(uint16_t change) const {
+ DCHECK_LT(change, mir_data_.size());
+ const MIRData* data = &mir_data_[change];
+ DCHECK(data->has_def);
+ DCHECK_LT(data->wide_def ? data->vreg_def + 1u : data->vreg_def, num_vregs_);
+ return vreg_data_[data->vreg_def].change == change &&
+ (!data->wide_def || vreg_data_[data->vreg_def + 1u].change == change);
+}
+
+bool GvnDeadCodeElimination::VRegChains::IsSRegUsed(uint16_t first_change, uint16_t last_change,
+ int s_reg) const {
+ DCHECK_LE(first_change, last_change);
+ DCHECK_LE(last_change, mir_data_.size());
+ for (size_t c = first_change; c != last_change; ++c) {
+ SSARepresentation* ssa_rep = mir_data_[c].mir->ssa_rep;
+ for (int i = 0; i != ssa_rep->num_uses; ++i) {
+ if (ssa_rep->uses[i] == s_reg) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+void GvnDeadCodeElimination::VRegChains::RenameSRegUses(uint16_t first_change, uint16_t last_change,
+ int old_s_reg, int new_s_reg, bool wide) {
+ for (size_t c = first_change; c != last_change; ++c) {
+ SSARepresentation* ssa_rep = mir_data_[c].mir->ssa_rep;
+ for (int i = 0; i != ssa_rep->num_uses; ++i) {
+ if (ssa_rep->uses[i] == old_s_reg) {
+ ssa_rep->uses[i] = new_s_reg;
+ if (wide) {
+ ++i;
+ DCHECK_LT(i, ssa_rep->num_uses);
+ ssa_rep->uses[i] = new_s_reg + 1;
+ }
+ }
+ }
+ }
+}
+
+void GvnDeadCodeElimination::VRegChains::RenameVRegUses(uint16_t first_change, uint16_t last_change,
+ int old_s_reg, int old_v_reg,
+ int new_s_reg, int new_v_reg) {
+ for (size_t c = first_change; c != last_change; ++c) {
+ MIR* mir = mir_data_[c].mir;
+ if (IsInstructionBinOp2Addr(mir->dalvikInsn.opcode) &&
+ mir->ssa_rep->uses[0] == old_s_reg && old_v_reg != new_v_reg) {
+ // Rewrite binop_2ADDR with plain binop before doing the register rename.
+ ChangeBinOp2AddrToPlainBinOp(mir);
+ }
+ uint64_t df_attr = MIRGraph::GetDataFlowAttributes(mir);
+ size_t use = 0u;
+#define REPLACE_VREG(REG) \
+ if ((df_attr & DF_U##REG) != 0) { \
+ if (mir->ssa_rep->uses[use] == old_s_reg) { \
+ DCHECK_EQ(mir->dalvikInsn.v##REG, static_cast<uint32_t>(old_v_reg)); \
+ mir->dalvikInsn.v##REG = new_v_reg; \
+ mir->ssa_rep->uses[use] = new_s_reg; \
+ if ((df_attr & DF_##REG##_WIDE) != 0) { \
+ DCHECK_EQ(mir->ssa_rep->uses[use + 1], old_s_reg + 1); \
+ mir->ssa_rep->uses[use + 1] = new_s_reg + 1; \
+ } \
+ } \
+ use += ((df_attr & DF_##REG##_WIDE) != 0) ? 2 : 1; \
+ }
+ REPLACE_VREG(A)
+ REPLACE_VREG(B)
+ REPLACE_VREG(C)
+#undef REPLACE_VREG
+ // We may encounter an out-of-order Phi which we need to ignore, otherwise we should
+ // only be asked to rename registers specified by DF_UA, DF_UB and DF_UC.
+ DCHECK_EQ(use,
+ static_cast<int>(mir->dalvikInsn.opcode) == kMirOpPhi
+ ? 0u
+ : static_cast<size_t>(mir->ssa_rep->num_uses));
+ }
+}
+
+GvnDeadCodeElimination::GvnDeadCodeElimination(const GlobalValueNumbering* gvn,
+ ScopedArenaAllocator* alloc)
+ : gvn_(gvn),
+ mir_graph_(gvn_->GetMirGraph()),
+ vreg_chains_(mir_graph_->GetNumOfCodeAndTempVRs(), alloc),
+ bb_(nullptr),
+ lvn_(nullptr),
+ no_uses_all_since_(0u),
+ unused_vregs_(new (alloc) ArenaBitVector(alloc, vreg_chains_.NumVRegs(), false)),
+ vregs_to_kill_(new (alloc) ArenaBitVector(alloc, vreg_chains_.NumVRegs(), false)),
+ kill_heads_(alloc->AllocArray<uint16_t>(vreg_chains_.NumVRegs(), kArenaAllocMisc)),
+ changes_to_kill_(alloc->Adapter()),
+ dependent_vregs_(new (alloc) ArenaBitVector(alloc, vreg_chains_.NumVRegs(), false)) {
+ changes_to_kill_.reserve(16u);
+}
+
+void GvnDeadCodeElimination::Apply(BasicBlock* bb) {
+ bb_ = bb;
+ lvn_ = gvn_->GetLvn(bb->id);
+
+ RecordPass();
+ BackwardPass();
+
+ DCHECK_EQ(no_uses_all_since_, 0u);
+ lvn_ = nullptr;
+ bb_ = nullptr;
+}
+
+void GvnDeadCodeElimination::RecordPass() {
+ // Record MIRs with vreg definition data, eliminate single instructions.
+ vreg_chains_.Reset();
+ DCHECK_EQ(no_uses_all_since_, 0u);
+ for (MIR* mir = bb_->first_mir_insn; mir != nullptr; mir = mir->next) {
+ if (RecordMIR(mir)) {
+ RecordPassTryToKillOverwrittenMoveOrMoveSrc();
+ RecordPassTryToKillLastMIR();
+ }
+ }
+}
+
+void GvnDeadCodeElimination::BackwardPass() {
+ // Now process MIRs in reverse order, trying to eliminate them.
+ unused_vregs_->ClearAllBits(); // Implicitly depend on all vregs at the end of BB.
+ while (vreg_chains_.NumMIRs() != 0u) {
+ if (BackwardPassTryToKillLastMIR()) {
+ continue;
+ }
+ BackwardPassProcessLastMIR();
+ }
+}
+
+void GvnDeadCodeElimination::KillMIR(MIRData* data) {
+ DCHECK(!data->must_keep);
+ DCHECK(!data->uses_all_vregs);
+ DCHECK(data->has_def);
+ DCHECK(data->mir->ssa_rep->num_defs == 1 || data->mir->ssa_rep->num_defs == 2);
+
+ KillMIR(data->mir);
+ data->has_def = false;
+ data->is_move = false;
+ data->is_move_src = false;
+}
+
+void GvnDeadCodeElimination::KillMIR(MIR* mir) {
+ mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
+ mir->ssa_rep->num_uses = 0;
+ mir->ssa_rep->num_defs = 0;
+}
+
+void GvnDeadCodeElimination::ChangeBinOp2AddrToPlainBinOp(MIR* mir) {
+ mir->dalvikInsn.vC = mir->dalvikInsn.vB;
+ mir->dalvikInsn.vB = mir->dalvikInsn.vA;
+ mir->dalvikInsn.opcode = static_cast<Instruction::Code>(
+ mir->dalvikInsn.opcode - Instruction::ADD_INT_2ADDR + Instruction::ADD_INT);
+}
+
+MIR* GvnDeadCodeElimination::CreatePhi(int s_reg, bool fp) {
+ int v_reg = mir_graph_->SRegToVReg(s_reg);
+ MIR* phi = mir_graph_->NewMIR();
+ phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi);
+ phi->dalvikInsn.vA = v_reg;
+ phi->offset = bb_->start_offset;
+ phi->m_unit_index = 0; // Arbitrarily assign all Phi nodes to outermost method.
+
+ phi->ssa_rep = static_cast<struct SSARepresentation *>(mir_graph_->GetArena()->Alloc(
+ sizeof(SSARepresentation), kArenaAllocDFInfo));
+
+ mir_graph_->AllocateSSADefData(phi, 1);
+ phi->ssa_rep->defs[0] = s_reg;
+ phi->ssa_rep->fp_def[0] = fp;
+
+ size_t num_uses = bb_->predecessors.size();
+ mir_graph_->AllocateSSAUseData(phi, num_uses);
+ std::fill_n(phi->ssa_rep->fp_use, num_uses, fp);
+ size_t idx = 0u;
+ for (BasicBlockId pred_id : bb_->predecessors) {
+ BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_id);
+ DCHECK(pred_bb != nullptr);
+ phi->ssa_rep->uses[idx] = pred_bb->data_flow_info->vreg_to_ssa_map_exit[v_reg];
+ DCHECK_NE(phi->ssa_rep->uses[idx], INVALID_SREG);
+ idx++;
+ }
+
+ phi->meta.phi_incoming = static_cast<BasicBlockId*>(mir_graph_->GetArena()->Alloc(
+ sizeof(BasicBlockId) * num_uses, kArenaAllocDFInfo));
+ std::copy(bb_->predecessors.begin(), bb_->predecessors.end(), phi->meta.phi_incoming);
+ bb_->PrependMIR(phi);
+ return phi;
+}
+
+MIR* GvnDeadCodeElimination::RenameSRegDefOrCreatePhi(uint16_t def_change, uint16_t last_change,
+ MIR* mir_to_kill) {
+ DCHECK(mir_to_kill->ssa_rep->num_defs == 1 || mir_to_kill->ssa_rep->num_defs == 2);
+ bool wide = (mir_to_kill->ssa_rep->num_defs != 1);
+ int new_s_reg = mir_to_kill->ssa_rep->defs[0];
+
+ // Just before we kill mir_to_kill, we need to replace the previous SSA reg assigned to the
+ // same dalvik reg to keep consistency with subsequent instructions. However, if there's no
+ // defining MIR for that dalvik reg, the preserved valus must come from its predecessors
+ // and we need to create a new Phi (a degenerate Phi if there's only a single predecessor).
+ if (def_change == kNPos) {
+ bool fp = mir_to_kill->ssa_rep->fp_def[0];
+ if (wide) {
+ DCHECK_EQ(new_s_reg + 1, mir_to_kill->ssa_rep->defs[1]);
+ DCHECK_EQ(fp, mir_to_kill->ssa_rep->fp_def[1]);
+ DCHECK_EQ(mir_graph_->SRegToVReg(new_s_reg) + 1, mir_graph_->SRegToVReg(new_s_reg + 1));
+ CreatePhi(new_s_reg + 1, fp); // High word Phi.
+ }
+ return CreatePhi(new_s_reg, fp);
+ } else {
+ DCHECK_LT(def_change, last_change);
+ DCHECK_LE(last_change, vreg_chains_.NumMIRs());
+ MIRData* def_data = vreg_chains_.GetMIRData(def_change);
+ DCHECK(def_data->has_def);
+ int old_s_reg = def_data->mir->ssa_rep->defs[0];
+ DCHECK_NE(old_s_reg, new_s_reg);
+ DCHECK_EQ(mir_graph_->SRegToVReg(old_s_reg), mir_graph_->SRegToVReg(new_s_reg));
+ def_data->mir->ssa_rep->defs[0] = new_s_reg;
+ if (wide) {
+ if (static_cast<int>(def_data->mir->dalvikInsn.opcode) == kMirOpPhi) {
+ // Currently the high word Phi is always located after the low word Phi.
+ MIR* phi_high = def_data->mir->next;
+ DCHECK(phi_high != nullptr && static_cast<int>(phi_high->dalvikInsn.opcode) == kMirOpPhi);
+ DCHECK_EQ(phi_high->ssa_rep->defs[0], old_s_reg + 1);
+ phi_high->ssa_rep->defs[0] = new_s_reg + 1;
+ } else {
+ DCHECK_EQ(def_data->mir->ssa_rep->defs[1], old_s_reg + 1);
+ def_data->mir->ssa_rep->defs[1] = new_s_reg + 1;
+ }
+ }
+ vreg_chains_.RenameSRegUses(def_change + 1u, last_change, old_s_reg, new_s_reg, wide);
+ return nullptr;
+ }
+}
+
+
+void GvnDeadCodeElimination::BackwardPassProcessLastMIR() {
+ MIRData* data = vreg_chains_.LastMIRData();
+ if (data->uses_all_vregs) {
+ DCHECK(data->must_keep);
+ unused_vregs_->ClearAllBits();
+ DCHECK_EQ(no_uses_all_since_, vreg_chains_.NumMIRs());
+ --no_uses_all_since_;
+ while (no_uses_all_since_ != 0u &&
+ !vreg_chains_.GetMIRData(no_uses_all_since_ - 1u)->uses_all_vregs) {
+ --no_uses_all_since_;
+ }
+ } else {
+ if (data->has_def) {
+ unused_vregs_->SetBit(data->vreg_def);
+ if (data->wide_def) {
+ unused_vregs_->SetBit(data->vreg_def + 1);
+ }
+ }
+ for (int i = 0, num_uses = data->mir->ssa_rep->num_uses; i != num_uses; ++i) {
+ int v_reg = mir_graph_->SRegToVReg(data->mir->ssa_rep->uses[i]);
+ unused_vregs_->ClearBit(v_reg);
+ }
+ }
+ vreg_chains_.RemoveLastMIRData();
+}
+
+void GvnDeadCodeElimination::RecordPassKillMoveByRenamingSrcDef(uint16_t src_change,
+ uint16_t move_change) {
+ DCHECK_LT(src_change, move_change);
+ MIRData* src_data = vreg_chains_.GetMIRData(src_change);
+ MIRData* move_data = vreg_chains_.GetMIRData(move_change);
+ DCHECK(src_data->is_move_src);
+ DCHECK_EQ(src_data->wide_def, move_data->wide_def);
+ DCHECK(move_data->prev_value.change == kNPos || move_data->prev_value.change <= src_change);
+ DCHECK(!move_data->wide_def || move_data->prev_value_high.change == kNPos ||
+ move_data->prev_value_high.change <= src_change);
+
+ int old_s_reg = src_data->mir->ssa_rep->defs[0];
+ // NOTE: old_s_reg may differ from move_data->mir->ssa_rep->uses[0]; value names must match.
+ int new_s_reg = move_data->mir->ssa_rep->defs[0];
+ DCHECK_NE(old_s_reg, new_s_reg);
+
+ if (IsInstructionBinOp2Addr(src_data->mir->dalvikInsn.opcode) &&
+ src_data->vreg_def != move_data->vreg_def) {
+ // Rewrite binop_2ADDR with plain binop before doing the register rename.
+ ChangeBinOp2AddrToPlainBinOp(src_data->mir);
+ }
+ // Remove src_change from the vreg chain(s).
+ vreg_chains_.RemoveChange(src_change);
+ // Replace the move_change with the src_change, copying all necessary data.
+ src_data->is_move_src = move_data->is_move_src;
+ src_data->low_def_over_high_word = move_data->low_def_over_high_word;
+ src_data->high_def_over_low_word = move_data->high_def_over_low_word;
+ src_data->vreg_def = move_data->vreg_def;
+ src_data->prev_value = move_data->prev_value;
+ src_data->prev_value_high = move_data->prev_value_high;
+ src_data->mir->dalvikInsn.vA = move_data->vreg_def;
+ src_data->mir->ssa_rep->defs[0] = new_s_reg;
+ if (move_data->wide_def) {
+ DCHECK_EQ(src_data->mir->ssa_rep->defs[1], old_s_reg + 1);
+ src_data->mir->ssa_rep->defs[1] = new_s_reg + 1;
+ }
+ vreg_chains_.ReplaceChange(move_change, src_change);
+
+ // Rename uses and kill the move.
+ vreg_chains_.RenameVRegUses(src_change + 1u, vreg_chains_.NumMIRs(),
+ old_s_reg, mir_graph_->SRegToVReg(old_s_reg),
+ new_s_reg, mir_graph_->SRegToVReg(new_s_reg));
+ KillMIR(move_data);
+}
+
+void GvnDeadCodeElimination::RecordPassTryToKillOverwrittenMoveOrMoveSrc(uint16_t check_change) {
+ MIRData* data = vreg_chains_.GetMIRData(check_change);
+ DCHECK(data->is_move || data->is_move_src);
+ int32_t dest_s_reg = data->mir->ssa_rep->defs[0];
+
+ if (data->is_move) {
+ // Check if source vreg has changed since the MOVE.
+ int32_t src_s_reg = data->mir->ssa_rep->uses[0];
+ uint32_t src_v_reg = mir_graph_->SRegToVReg(src_s_reg);
+ uint16_t src_change = vreg_chains_.FindFirstChangeAfter(src_v_reg, check_change);
+ bool wide = data->wide_def;
+ if (wide) {
+ uint16_t src_change_high = vreg_chains_.FindFirstChangeAfter(src_v_reg + 1, check_change);
+ if (src_change_high != kNPos && (src_change == kNPos || src_change_high < src_change)) {
+ src_change = src_change_high;
+ }
+ }
+ if (src_change == kNPos ||
+ !vreg_chains_.IsSRegUsed(src_change + 1u, vreg_chains_.NumMIRs(), dest_s_reg)) {
+ // We can simply change all uses of dest to src.
+ size_t rename_end = (src_change != kNPos) ? src_change + 1u : vreg_chains_.NumMIRs();
+ vreg_chains_.RenameVRegUses(check_change + 1u, rename_end,
+ dest_s_reg, mir_graph_->SRegToVReg(dest_s_reg),
+ src_s_reg, mir_graph_->SRegToVReg(src_s_reg));
+
+ // Now, remove the MOVE from the vreg chain(s) and kill it.
+ vreg_chains_.RemoveChange(check_change);
+ KillMIR(data);
+ return;
+ }
+ }
+
+ if (data->is_move_src) {
+ // 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);
+ 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 &&
+ (d->prev_value.change == kNPos || d->prev_value.change <= check_change) &&
+ (!d->wide_def ||
+ d->prev_value_high.change == kNPos || d->prev_value_high.change <= check_change)) {
+ // Compare value names to find move to move.
+ int32_t src_s_reg = d->mir->ssa_rep->uses[0];
+ uint16_t src_name =
+ (d->wide_def ? lvn_->GetSregValueWide(src_s_reg) : lvn_->GetSregValue(src_s_reg));
+ if (value_name == src_name) {
+ RecordPassKillMoveByRenamingSrcDef(check_change, c);
+ return;
+ }
+ }
+ }
+ }
+}
+
+void GvnDeadCodeElimination::RecordPassTryToKillOverwrittenMoveOrMoveSrc() {
+ // Check if we're overwriting a the result of a move or the definition of a source of a move.
+ // For MOVE_WIDE, we may be overwriting partially; if that's the case, check that the other
+ // word wasn't previously overwritten - we would have tried to rename back then.
+ MIRData* data = vreg_chains_.LastMIRData();
+ if (!data->has_def) {
+ return;
+ }
+ // NOTE: Instructions such as new-array implicitly use all vregs (if they throw) but they can
+ // define a move source which can be renamed. Therefore we allow the checked change to be the
+ // change before no_uses_all_since_. This has no effect on moves as they never use all vregs.
+ if (data->prev_value.change != kNPos && data->prev_value.change + 1u >= no_uses_all_since_) {
+ MIRData* check_data = vreg_chains_.GetMIRData(data->prev_value.change);
+ bool try_to_kill = false;
+ if (!check_data->is_move && !check_data->is_move_src) {
+ DCHECK(!try_to_kill);
+ } else if (!check_data->wide_def) {
+ // Narrow move; always fully overwritten by the last MIR.
+ try_to_kill = true;
+ } else if (data->low_def_over_high_word) {
+ // Overwriting only the high word; is the low word still valid?
+ DCHECK_EQ(check_data->vreg_def + 1u, data->vreg_def);
+ if (vreg_chains_.LastChange(check_data->vreg_def) == data->prev_value.change) {
+ try_to_kill = true;
+ }
+ } else if (!data->wide_def) {
+ // Overwriting only the low word, is the high word still valid?
+ if (vreg_chains_.LastChange(data->vreg_def + 1) == data->prev_value.change) {
+ try_to_kill = true;
+ }
+ } else {
+ // Overwriting both words; was the high word still from the same move?
+ if (data->prev_value_high.change == data->prev_value.change) {
+ try_to_kill = true;
+ }
+ }
+ if (try_to_kill) {
+ RecordPassTryToKillOverwrittenMoveOrMoveSrc(data->prev_value.change);
+ }
+ }
+ if (data->wide_def && data->high_def_over_low_word &&
+ data->prev_value_high.change != kNPos &&
+ data->prev_value_high.change + 1u >= no_uses_all_since_) {
+ MIRData* check_data = vreg_chains_.GetMIRData(data->prev_value_high.change);
+ bool try_to_kill = false;
+ if (!check_data->is_move && !check_data->is_move_src) {
+ DCHECK(!try_to_kill);
+ } else if (!check_data->wide_def) {
+ // Narrow move; always fully overwritten by the last MIR.
+ try_to_kill = true;
+ } else if (vreg_chains_.LastChange(check_data->vreg_def + 1) ==
+ data->prev_value_high.change) {
+ // High word is still valid.
+ try_to_kill = true;
+ }
+ if (try_to_kill) {
+ RecordPassTryToKillOverwrittenMoveOrMoveSrc(data->prev_value_high.change);
+ }
+ }
+}
+
+void GvnDeadCodeElimination::RecordPassTryToKillLastMIR() {
+ MIRData* last_data = vreg_chains_.LastMIRData();
+ if (last_data->must_keep) {
+ return;
+ }
+ if (UNLIKELY(!last_data->has_def)) {
+ // Must be an eliminated MOVE. Drop its data and data of all eliminated MIRs before it.
+ vreg_chains_.RemoveTrailingNops();
+ return;
+ }
+
+ // Try to kill a sequence of consecutive definitions of the same vreg. Allow mixing
+ // wide and non-wide defs; consider high word dead if low word has been overwritten.
+ uint16_t current_value = vreg_chains_.CurrentValue(last_data->vreg_def);
+ uint16_t change = vreg_chains_.NumMIRs() - 1u;
+ MIRData* data = last_data;
+ while (data->prev_value.value != current_value) {
+ --change;
+ if (data->prev_value.change == kNPos || data->prev_value.change != change) {
+ return;
+ }
+ data = vreg_chains_.GetMIRData(data->prev_value.change);
+ if (data->must_keep || !data->has_def || data->vreg_def != last_data->vreg_def) {
+ return;
+ }
+ }
+
+ bool wide = last_data->wide_def;
+ if (wide) {
+ // Check that the low word is valid.
+ if (data->low_def_over_high_word) {
+ return;
+ }
+ // Check that the high word is valid.
+ MIRData* high_data = data;
+ if (!high_data->wide_def) {
+ uint16_t high_change = vreg_chains_.FindFirstChangeAfter(data->vreg_def + 1, change);
+ DCHECK_NE(high_change, kNPos);
+ high_data = vreg_chains_.GetMIRData(high_change);
+ DCHECK_EQ(high_data->vreg_def, data->vreg_def);
+ }
+ if (high_data->prev_value_high.value != current_value || high_data->high_def_over_low_word) {
+ return;
+ }
+ }
+
+ MIR* phi = RenameSRegDefOrCreatePhi(data->prev_value.change, change, last_data->mir);
+ for (size_t i = 0, count = vreg_chains_.NumMIRs() - change; i != count; ++i) {
+ KillMIR(vreg_chains_.LastMIRData()->mir);
+ vreg_chains_.RemoveLastMIRData();
+ }
+ if (phi != nullptr) {
+ // Though the Phi has been added to the beginning, we can put the MIRData at the end.
+ vreg_chains_.AddMIRWithDef(phi, phi->dalvikInsn.vA, wide, current_value);
+ // Reset the previous value to avoid eventually eliminating the Phi itself (unless unused).
+ last_data = vreg_chains_.LastMIRData();
+ last_data->prev_value.value = kNoValue;
+ last_data->prev_value_high.value = kNoValue;
+ }
+}
+
+uint16_t GvnDeadCodeElimination::FindChangesToKill(uint16_t first_change, uint16_t last_change) {
+ // Process dependencies for changes in range [first_change, last_change) and record all
+ // changes that we need to kill. Return kNPos if there's a dependent change that must be
+ // kept unconditionally; otherwise the end of the range processed before encountering
+ // a change that defines a dalvik reg that we need to keep (last_change on full success).
+ changes_to_kill_.clear();
+ dependent_vregs_->ClearAllBits();
+ for (size_t change = first_change; change != last_change; ++change) {
+ MIRData* data = vreg_chains_.GetMIRData(change);
+ DCHECK(!data->uses_all_vregs);
+ bool must_not_depend = data->must_keep;
+ bool depends = false;
+ // Check if the MIR defines a vreg we're trying to eliminate.
+ if (data->has_def && vregs_to_kill_->IsBitSet(data->vreg_def)) {
+ if (change < kill_heads_[data->vreg_def]) {
+ must_not_depend = true;
+ } else {
+ depends = true;
+ }
+ }
+ if (data->has_def && data->wide_def && vregs_to_kill_->IsBitSet(data->vreg_def + 1)) {
+ if (change < kill_heads_[data->vreg_def + 1]) {
+ must_not_depend = true;
+ } else {
+ depends = true;
+ }
+ }
+ if (!depends) {
+ // Check for dependency through SSA reg uses.
+ SSARepresentation* ssa_rep = data->mir->ssa_rep;
+ for (int i = 0; i != ssa_rep->num_uses; ++i) {
+ if (dependent_vregs_->IsBitSet(mir_graph_->SRegToVReg(ssa_rep->uses[i]))) {
+ depends = true;
+ break;
+ }
+ }
+ }
+ // Now check if we can eliminate the insn if we need to.
+ if (depends && must_not_depend) {
+ return kNPos;
+ }
+ if (depends && data->has_def &&
+ vreg_chains_.IsTopChange(change) && !vregs_to_kill_->IsBitSet(data->vreg_def) &&
+ !unused_vregs_->IsBitSet(data->vreg_def) &&
+ (!data->wide_def || !unused_vregs_->IsBitSet(data->vreg_def + 1))) {
+ // This is a top change but neither unnecessary nor one of the top kill changes.
+ return change;
+ }
+ // Finally, update the data.
+ if (depends) {
+ changes_to_kill_.push_back(change);
+ if (data->has_def) {
+ dependent_vregs_->SetBit(data->vreg_def);
+ if (data->wide_def) {
+ dependent_vregs_->SetBit(data->vreg_def + 1);
+ }
+ }
+ } else {
+ if (data->has_def) {
+ dependent_vregs_->ClearBit(data->vreg_def);
+ if (data->wide_def) {
+ dependent_vregs_->ClearBit(data->vreg_def + 1);
+ }
+ }
+ }
+ }
+ return last_change;
+}
+
+void GvnDeadCodeElimination::BackwardPassTryToKillRevertVRegs() {
+}
+
+bool GvnDeadCodeElimination::BackwardPassTryToKillLastMIR() {
+ MIRData* last_data = vreg_chains_.LastMIRData();
+ if (last_data->must_keep) {
+ return false;
+ }
+ DCHECK(!last_data->uses_all_vregs);
+ if (!last_data->has_def) {
+ // Previously eliminated.
+ DCHECK_EQ(static_cast<int>(last_data->mir->dalvikInsn.opcode), static_cast<int>(kMirOpNop));
+ vreg_chains_.RemoveTrailingNops();
+ return true;
+ }
+ if (unused_vregs_->IsBitSet(last_data->vreg_def) ||
+ (last_data->wide_def && unused_vregs_->IsBitSet(last_data->vreg_def + 1))) {
+ if (last_data->wide_def) {
+ // For wide defs, one of the vregs may still be considered needed, fix that.
+ unused_vregs_->SetBit(last_data->vreg_def);
+ unused_vregs_->SetBit(last_data->vreg_def + 1);
+ }
+ KillMIR(last_data->mir);
+ vreg_chains_.RemoveLastMIRData();
+ return true;
+ }
+
+ vregs_to_kill_->ClearAllBits();
+ size_t num_mirs = vreg_chains_.NumMIRs();
+ DCHECK_NE(num_mirs, 0u);
+ uint16_t kill_change = num_mirs - 1u;
+ uint16_t start = num_mirs;
+ size_t num_killed_top_changes = 0u;
+ while (num_killed_top_changes != kMaxNumTopChangesToKill &&
+ kill_change != kNPos && kill_change != num_mirs) {
+ ++num_killed_top_changes;
+
+ DCHECK(vreg_chains_.IsTopChange(kill_change));
+ MIRData* data = vreg_chains_.GetMIRData(kill_change);
+ int count = data->wide_def ? 2 : 1;
+ for (int v_reg = data->vreg_def, end = data->vreg_def + count; v_reg != end; ++v_reg) {
+ uint16_t kill_head = vreg_chains_.FindKillHead(v_reg, no_uses_all_since_);
+ if (kill_head == kNPos) {
+ return false;
+ }
+ kill_heads_[v_reg] = kill_head;
+ vregs_to_kill_->SetBit(v_reg);
+ start = std::min(start, kill_head);
+ }
+ DCHECK_LT(start, vreg_chains_.NumMIRs());
+
+ kill_change = FindChangesToKill(start, num_mirs);
+ }
+
+ if (kill_change != num_mirs) {
+ return false;
+ }
+
+ // Kill all MIRs marked as dependent.
+ for (uint32_t v_reg : vregs_to_kill_->Indexes()) {
+ // Rename s_regs or create Phi only once for each MIR (only for low word).
+ MIRData* data = vreg_chains_.GetMIRData(vreg_chains_.LastChange(v_reg));
+ DCHECK(data->has_def);
+ if (data->vreg_def == v_reg) {
+ MIRData* kill_head_data = vreg_chains_.GetMIRData(kill_heads_[v_reg]);
+ RenameSRegDefOrCreatePhi(kill_head_data->PrevChange(v_reg), num_mirs, data->mir);
+ } else {
+ DCHECK_EQ(data->vreg_def + 1u, v_reg);
+ DCHECK_EQ(vreg_chains_.GetMIRData(kill_heads_[v_reg - 1u])->PrevChange(v_reg - 1u),
+ vreg_chains_.GetMIRData(kill_heads_[v_reg])->PrevChange(v_reg));
+ }
+ }
+ unused_vregs_->Union(vregs_to_kill_);
+ for (auto it = changes_to_kill_.rbegin(), end = changes_to_kill_.rend(); it != end; ++it) {
+ MIRData* data = vreg_chains_.GetMIRData(*it);
+ DCHECK(!data->must_keep);
+ DCHECK(data->has_def);
+ vreg_chains_.RemoveChange(*it);
+ KillMIR(data);
+ }
+
+ vreg_chains_.RemoveTrailingNops();
+ return true;
+}
+
+bool GvnDeadCodeElimination::RecordMIR(MIR* mir) {
+ bool must_keep = false;
+ bool uses_all_vregs = false;
+ bool is_move = false;
+ uint16_t opcode = mir->dalvikInsn.opcode;
+ switch (opcode) {
+ case kMirOpPhi: {
+ // We can't recognize wide variables in Phi from num_defs == 2 as we've got two Phis instead.
+ DCHECK_EQ(mir->ssa_rep->num_defs, 1);
+ int s_reg = mir->ssa_rep->defs[0];
+ bool wide = false;
+ uint16_t new_value = lvn_->GetSregValue(s_reg);
+ if (new_value == kNoValue) {
+ wide = true;
+ new_value = lvn_->GetSregValueWide(s_reg);
+ if (new_value == kNoValue) {
+ return false; // Ignore the high word Phi.
+ }
+ }
+
+ int v_reg = mir_graph_->SRegToVReg(s_reg);
+ DCHECK_EQ(vreg_chains_.CurrentValue(v_reg), kNoValue); // No previous def for v_reg.
+ if (wide) {
+ DCHECK_EQ(vreg_chains_.CurrentValue(v_reg + 1), kNoValue);
+ }
+ vreg_chains_.AddMIRWithDef(mir, v_reg, wide, new_value);
+ return true; // Avoid the common processing.
+ }
+
+ case kMirOpNop:
+ case Instruction::NOP:
+ // Don't record NOPs.
+ return false;
+
+ case kMirOpCheck:
+ must_keep = true;
+ uses_all_vregs = true;
+ break;
+
+ case Instruction::RETURN_VOID:
+ case Instruction::RETURN:
+ case Instruction::RETURN_OBJECT:
+ case Instruction::RETURN_WIDE:
+ case Instruction::GOTO:
+ case Instruction::GOTO_16:
+ case Instruction::GOTO_32:
+ case Instruction::PACKED_SWITCH:
+ case Instruction::SPARSE_SWITCH:
+ case Instruction::IF_EQ:
+ case Instruction::IF_NE:
+ case Instruction::IF_LT:
+ case Instruction::IF_GE:
+ case Instruction::IF_GT:
+ case Instruction::IF_LE:
+ case Instruction::IF_EQZ:
+ case Instruction::IF_NEZ:
+ case Instruction::IF_LTZ:
+ case Instruction::IF_GEZ:
+ case Instruction::IF_GTZ:
+ case Instruction::IF_LEZ:
+ case kMirOpFusedCmplFloat:
+ case kMirOpFusedCmpgFloat:
+ case kMirOpFusedCmplDouble:
+ case kMirOpFusedCmpgDouble:
+ case kMirOpFusedCmpLong:
+ must_keep = true;
+ uses_all_vregs = true; // Keep the implicit dependencies on all vregs.
+ break;
+
+ case Instruction::CONST_CLASS:
+ case Instruction::CONST_STRING:
+ case Instruction::CONST_STRING_JUMBO:
+ // NOTE: While we're currently treating CONST_CLASS, CONST_STRING and CONST_STRING_JUMBO
+ // as throwing but we could conceivably try and eliminate those exceptions if we're
+ // retrieving the class/string repeatedly.
+ must_keep = true;
+ uses_all_vregs = true;
+ break;
+
+ case Instruction::MONITOR_ENTER:
+ case Instruction::MONITOR_EXIT:
+ // We can actually try and optimize across the acquire operation of MONITOR_ENTER,
+ // the value names provided by GVN reflect the possible changes to memory visibility.
+ // NOTE: In ART, MONITOR_ENTER and MONITOR_EXIT can throw only NPE.
+ must_keep = true;
+ uses_all_vregs = (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0;
+ break;
+
+ case Instruction::INVOKE_DIRECT:
+ case Instruction::INVOKE_DIRECT_RANGE:
+ case Instruction::INVOKE_VIRTUAL:
+ case Instruction::INVOKE_VIRTUAL_RANGE:
+ case Instruction::INVOKE_SUPER:
+ case Instruction::INVOKE_SUPER_RANGE:
+ case Instruction::INVOKE_INTERFACE:
+ case Instruction::INVOKE_INTERFACE_RANGE:
+ case Instruction::INVOKE_STATIC:
+ case Instruction::INVOKE_STATIC_RANGE:
+ case Instruction::CHECK_CAST:
+ case Instruction::THROW:
+ case Instruction::FILLED_NEW_ARRAY:
+ case Instruction::FILLED_NEW_ARRAY_RANGE:
+ case Instruction::FILL_ARRAY_DATA:
+ must_keep = true;
+ uses_all_vregs = true;
+ break;
+
+ case Instruction::NEW_INSTANCE:
+ case Instruction::NEW_ARRAY:
+ must_keep = true;
+ uses_all_vregs = true;
+ break;
+
+ case kMirOpNullCheck:
+ DCHECK_EQ(mir->ssa_rep->num_uses, 1);
+ if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) {
+ mir->ssa_rep->num_uses = 0;
+ mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
+ return false;
+ }
+ must_keep = true;
+ uses_all_vregs = true;
+ break;
+
+ case Instruction::MOVE_RESULT:
+ case Instruction::MOVE_RESULT_OBJECT:
+ case Instruction::MOVE_RESULT_WIDE:
+ break;
+
+ case Instruction::INSTANCE_OF:
+ break;
+
+ case Instruction::MOVE_EXCEPTION:
+ must_keep = true;
+ break;
+
+ case kMirOpCopy:
+ case Instruction::MOVE:
+ case Instruction::MOVE_FROM16:
+ case Instruction::MOVE_16:
+ case Instruction::MOVE_WIDE:
+ case Instruction::MOVE_WIDE_FROM16:
+ case Instruction::MOVE_WIDE_16:
+ case Instruction::MOVE_OBJECT:
+ case Instruction::MOVE_OBJECT_FROM16:
+ case Instruction::MOVE_OBJECT_16: {
+ is_move = true;
+ // If the MIR defining src vreg is known, allow renaming all uses of src vreg to dest vreg
+ // while updating the defining MIR to directly define dest vreg. However, changing Phi's
+ // def this way doesn't work without changing MIRs in other BBs.
+ int src_v_reg = mir_graph_->SRegToVReg(mir->ssa_rep->uses[0]);
+ int src_change = vreg_chains_.LastChange(src_v_reg);
+ if (src_change != kNPos) {
+ MIRData* src_data = vreg_chains_.GetMIRData(src_change);
+ if (static_cast<int>(src_data->mir->dalvikInsn.opcode) != kMirOpPhi) {
+ src_data->is_move_src = true;
+ }
+ }
+ break;
+ }
+
+ case Instruction::CONST_4:
+ case Instruction::CONST_16:
+ case Instruction::CONST:
+ case Instruction::CONST_HIGH16:
+ case Instruction::CONST_WIDE_16:
+ case Instruction::CONST_WIDE_32:
+ case Instruction::CONST_WIDE:
+ case Instruction::CONST_WIDE_HIGH16:
+ case Instruction::ARRAY_LENGTH:
+ case Instruction::CMPL_FLOAT:
+ case Instruction::CMPG_FLOAT:
+ case Instruction::CMPL_DOUBLE:
+ case Instruction::CMPG_DOUBLE:
+ case Instruction::CMP_LONG:
+ case Instruction::NEG_INT:
+ case Instruction::NOT_INT:
+ case Instruction::NEG_LONG:
+ case Instruction::NOT_LONG:
+ case Instruction::NEG_FLOAT:
+ case Instruction::NEG_DOUBLE:
+ case Instruction::INT_TO_LONG:
+ case Instruction::INT_TO_FLOAT:
+ case Instruction::INT_TO_DOUBLE:
+ case Instruction::LONG_TO_INT:
+ case Instruction::LONG_TO_FLOAT:
+ case Instruction::LONG_TO_DOUBLE:
+ case Instruction::FLOAT_TO_INT:
+ case Instruction::FLOAT_TO_LONG:
+ case Instruction::FLOAT_TO_DOUBLE:
+ case Instruction::DOUBLE_TO_INT:
+ case Instruction::DOUBLE_TO_LONG:
+ case Instruction::DOUBLE_TO_FLOAT:
+ case Instruction::INT_TO_BYTE:
+ case Instruction::INT_TO_CHAR:
+ case Instruction::INT_TO_SHORT:
+ case Instruction::ADD_INT:
+ case Instruction::SUB_INT:
+ case Instruction::MUL_INT:
+ case Instruction::AND_INT:
+ case Instruction::OR_INT:
+ case Instruction::XOR_INT:
+ case Instruction::SHL_INT:
+ case Instruction::SHR_INT:
+ case Instruction::USHR_INT:
+ case Instruction::ADD_LONG:
+ case Instruction::SUB_LONG:
+ case Instruction::MUL_LONG:
+ case Instruction::AND_LONG:
+ case Instruction::OR_LONG:
+ case Instruction::XOR_LONG:
+ case Instruction::SHL_LONG:
+ case Instruction::SHR_LONG:
+ case Instruction::USHR_LONG:
+ case Instruction::ADD_FLOAT:
+ case Instruction::SUB_FLOAT:
+ case Instruction::MUL_FLOAT:
+ case Instruction::DIV_FLOAT:
+ case Instruction::REM_FLOAT:
+ case Instruction::ADD_DOUBLE:
+ case Instruction::SUB_DOUBLE:
+ case Instruction::MUL_DOUBLE:
+ case Instruction::DIV_DOUBLE:
+ case Instruction::REM_DOUBLE:
+ case Instruction::ADD_INT_2ADDR:
+ case Instruction::SUB_INT_2ADDR:
+ case Instruction::MUL_INT_2ADDR:
+ case Instruction::AND_INT_2ADDR:
+ case Instruction::OR_INT_2ADDR:
+ case Instruction::XOR_INT_2ADDR:
+ case Instruction::SHL_INT_2ADDR:
+ case Instruction::SHR_INT_2ADDR:
+ case Instruction::USHR_INT_2ADDR:
+ case Instruction::ADD_LONG_2ADDR:
+ case Instruction::SUB_LONG_2ADDR:
+ case Instruction::MUL_LONG_2ADDR:
+ case Instruction::AND_LONG_2ADDR:
+ case Instruction::OR_LONG_2ADDR:
+ case Instruction::XOR_LONG_2ADDR:
+ case Instruction::SHL_LONG_2ADDR:
+ case Instruction::SHR_LONG_2ADDR:
+ case Instruction::USHR_LONG_2ADDR:
+ case Instruction::ADD_FLOAT_2ADDR:
+ case Instruction::SUB_FLOAT_2ADDR:
+ case Instruction::MUL_FLOAT_2ADDR:
+ case Instruction::DIV_FLOAT_2ADDR:
+ case Instruction::REM_FLOAT_2ADDR:
+ case Instruction::ADD_DOUBLE_2ADDR:
+ case Instruction::SUB_DOUBLE_2ADDR:
+ case Instruction::MUL_DOUBLE_2ADDR:
+ case Instruction::DIV_DOUBLE_2ADDR:
+ case Instruction::REM_DOUBLE_2ADDR:
+ case Instruction::ADD_INT_LIT16:
+ case Instruction::RSUB_INT:
+ case Instruction::MUL_INT_LIT16:
+ case Instruction::AND_INT_LIT16:
+ case Instruction::OR_INT_LIT16:
+ case Instruction::XOR_INT_LIT16:
+ case Instruction::ADD_INT_LIT8:
+ case Instruction::RSUB_INT_LIT8:
+ case Instruction::MUL_INT_LIT8:
+ case Instruction::AND_INT_LIT8:
+ case Instruction::OR_INT_LIT8:
+ case Instruction::XOR_INT_LIT8:
+ case Instruction::SHL_INT_LIT8:
+ case Instruction::SHR_INT_LIT8:
+ case Instruction::USHR_INT_LIT8:
+ break;
+
+ case Instruction::DIV_INT:
+ case Instruction::REM_INT:
+ case Instruction::DIV_LONG:
+ case Instruction::REM_LONG:
+ case Instruction::DIV_INT_2ADDR:
+ case Instruction::REM_INT_2ADDR:
+ case Instruction::DIV_LONG_2ADDR:
+ case Instruction::REM_LONG_2ADDR:
+ if ((mir->optimization_flags & MIR_IGNORE_DIV_ZERO_CHECK) == 0) {
+ must_keep = true;
+ uses_all_vregs = true;
+ }
+ break;
+
+ case Instruction::DIV_INT_LIT16:
+ case Instruction::REM_INT_LIT16:
+ case Instruction::DIV_INT_LIT8:
+ case Instruction::REM_INT_LIT8:
+ if (mir->dalvikInsn.vC == 0) { // Explicit division by 0?
+ must_keep = true;
+ uses_all_vregs = true;
+ }
+ break;
+
+ case Instruction::AGET_OBJECT:
+ case Instruction::AGET:
+ case Instruction::AGET_WIDE:
+ case Instruction::AGET_BOOLEAN:
+ case Instruction::AGET_BYTE:
+ case Instruction::AGET_CHAR:
+ case Instruction::AGET_SHORT:
+ if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
+ (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) == 0) {
+ must_keep = true;
+ uses_all_vregs = true;
+ }
+ break;
+
+ case Instruction::APUT_OBJECT:
+ case Instruction::APUT:
+ case Instruction::APUT_WIDE:
+ case Instruction::APUT_BYTE:
+ case Instruction::APUT_BOOLEAN:
+ case Instruction::APUT_SHORT:
+ case Instruction::APUT_CHAR:
+ must_keep = true;
+ if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
+ (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) == 0) {
+ uses_all_vregs = true;
+ }
+ break;
+
+ case Instruction::IGET_OBJECT:
+ case Instruction::IGET:
+ case Instruction::IGET_WIDE:
+ case Instruction::IGET_BOOLEAN:
+ case Instruction::IGET_BYTE:
+ case Instruction::IGET_CHAR:
+ case Instruction::IGET_SHORT: {
+ const MirIFieldLoweringInfo& info = mir_graph_->GetIFieldLoweringInfo(mir);
+ if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
+ !info.IsResolved() || !info.FastGet()) {
+ must_keep = true;
+ uses_all_vregs = true;
+ } else if (info.IsVolatile()) {
+ must_keep = true;
+ }
+ break;
+ }
+
+ case Instruction::IPUT_OBJECT:
+ case Instruction::IPUT:
+ case Instruction::IPUT_WIDE:
+ case Instruction::IPUT_BOOLEAN:
+ case Instruction::IPUT_BYTE:
+ case Instruction::IPUT_CHAR:
+ case Instruction::IPUT_SHORT: {
+ must_keep = true;
+ const MirIFieldLoweringInfo& info = mir_graph_->GetIFieldLoweringInfo(mir);
+ if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
+ !info.IsResolved() || !info.FastPut()) {
+ uses_all_vregs = true;
+ }
+ break;
+ }
+
+ case Instruction::SGET_OBJECT:
+ case Instruction::SGET:
+ case Instruction::SGET_WIDE:
+ case Instruction::SGET_BOOLEAN:
+ case Instruction::SGET_BYTE:
+ case Instruction::SGET_CHAR:
+ case Instruction::SGET_SHORT: {
+ const MirSFieldLoweringInfo& info = mir_graph_->GetSFieldLoweringInfo(mir);
+ if ((mir->optimization_flags & MIR_CLASS_IS_INITIALIZED) == 0 ||
+ !info.IsResolved() || !info.FastGet()) {
+ must_keep = true;
+ uses_all_vregs = true;
+ } else if (info.IsVolatile()) {
+ must_keep = true;
+ }
+ break;
+ }
+
+ case Instruction::SPUT_OBJECT:
+ case Instruction::SPUT:
+ case Instruction::SPUT_WIDE:
+ case Instruction::SPUT_BOOLEAN:
+ case Instruction::SPUT_BYTE:
+ case Instruction::SPUT_CHAR:
+ case Instruction::SPUT_SHORT: {
+ must_keep = true;
+ const MirSFieldLoweringInfo& info = mir_graph_->GetSFieldLoweringInfo(mir);
+ if ((mir->optimization_flags & MIR_CLASS_IS_INITIALIZED) == 0 ||
+ !info.IsResolved() || !info.FastPut()) {
+ uses_all_vregs = true;
+ }
+ break;
+ }
+
+ default:
+ LOG(FATAL) << "Unexpected opcode: " << opcode;
+ UNREACHABLE();
+ break;
+ }
+
+ if (mir->ssa_rep->num_defs != 0) {
+ DCHECK(mir->ssa_rep->num_defs == 1 || mir->ssa_rep->num_defs == 2);
+ bool wide = (mir->ssa_rep->num_defs == 2);
+ int s_reg = mir->ssa_rep->defs[0];
+ int v_reg = mir_graph_->SRegToVReg(s_reg);
+ uint16_t new_value = wide ? lvn_->GetSregValueWide(s_reg) : lvn_->GetSregValue(s_reg);
+ DCHECK_NE(new_value, kNoValue);
+
+ vreg_chains_.UpdateInitialVRegValue(v_reg, wide, lvn_);
+ vreg_chains_.AddMIRWithDef(mir, v_reg, wide, new_value);
+ if (is_move) {
+ // Allow renaming all uses of dest vreg to src vreg.
+ vreg_chains_.LastMIRData()->is_move = true;
+ }
+ } else {
+ vreg_chains_.AddMIRWithoutDef(mir);
+ DCHECK(!is_move) << opcode;
+ }
+
+ if (must_keep) {
+ MIRData* last_data = vreg_chains_.LastMIRData();
+ last_data->must_keep = true;
+ if (uses_all_vregs) {
+ last_data->uses_all_vregs = true;
+ no_uses_all_since_ = vreg_chains_.NumMIRs();
+ }
+ } else {
+ DCHECK_NE(mir->ssa_rep->num_defs, 0) << opcode;
+ DCHECK(!uses_all_vregs) << opcode;
+ }
+ return true;
+}
+
+} // namespace art