/*
 * 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 "base/allocator.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)),
      vreg_high_words_(num_vregs, false, Allocator::GetNoopAllocator(),
                       BitVector::BitsToWords(num_vregs),
                       alloc->AllocArray<uint32_t>(BitVector::BitsToWords(num_vregs))),
      mir_data_(alloc->Adapter()) {
  mir_data_.reserve(100);
}

inline void GvnDeadCodeElimination::VRegChains::Reset() {
  DCHECK(mir_data_.empty());
  std::fill_n(vreg_data_, num_vregs_, VRegValue());
  vreg_high_words_.ClearAllBits();
}

void GvnDeadCodeElimination::VRegChains::AddMIRWithDef(MIR* mir, int v_reg, bool wide,
                                                       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;

  DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
  data->prev_value = vreg_data_[v_reg];
  data->low_def_over_high_word =
      (vreg_data_[v_reg].change != kNPos)
      ? GetMIRData(vreg_data_[v_reg].change)->vreg_def + 1 == v_reg
      : vreg_high_words_.IsBitSet(v_reg);
  vreg_data_[v_reg].value = new_value;
  vreg_data_[v_reg].change = pos;
  vreg_high_words_.ClearBit(v_reg);

  if (wide) {
    DCHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_);
    data->prev_value_high = vreg_data_[v_reg + 1];
    data->high_def_over_low_word =
        (vreg_data_[v_reg + 1].change != kNPos)
        ? GetMIRData(vreg_data_[v_reg + 1].change)->vreg_def == v_reg + 1
        : !vreg_high_words_.IsBitSet(v_reg + 1);
    vreg_data_[v_reg + 1].value = new_value;
    vreg_data_[v_reg + 1].change = pos;
    vreg_high_words_.SetBit(v_reg + 1);
  }
}

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;
    DCHECK(!vreg_high_words_.IsBitSet(data->vreg_def));
    if (data->low_def_over_high_word) {
      vreg_high_words_.SetBit(data->vreg_def);
    }
    if (data->wide_def) {
      DCHECK_EQ(vreg_data_[data->vreg_def + 1].change, NumMIRs() - 1u);
      vreg_data_[data->vreg_def + 1] = data->prev_value_high;
      DCHECK(vreg_high_words_.IsBitSet(data->vreg_def + 1));
      if (data->high_def_over_low_word) {
        vreg_high_words_.ClearBit(data->vreg_def + 1);
      }
    }
  }
  mir_data_.pop_back();
}

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;
    vreg_high_words_.SetBit(v_reg);
  } 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;
      DCHECK(!vreg_high_words_.IsBitSet(v_reg));  // Keep marked as low word.
    }
  } 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;
      DCHECK(!vreg_high_words_.IsBitSet(v_reg));  // Keep marked as low word.
    }
    if (check_high && vreg_data_[v_reg + 1].value == kNoValue) {
      uint16_t old_value = lvn->GetStartingVregValueNumber(v_reg + 1);
      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;
      DCHECK(!vreg_high_words_.IsBitSet(v_reg + 1));  // Keep marked as low word.
    }
  }
}

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;
      DCHECK_EQ(vreg_high_words_.IsBitSet(v_reg), v_reg == old_data->vreg_def + 1);
      // No change in vreg_high_words_.
    } else {
      DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), old_change);
      mir_data_[next_change].SetPrevChange(v_reg, new_change);
    }
  }
}

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;
      DCHECK_EQ(vreg_high_words_.IsBitSet(v_reg), v_reg == data->vreg_def + 1);
      if (data->vreg_def == v_reg && data->low_def_over_high_word) {
        vreg_high_words_.SetBit(v_reg);
      } else if (data->vreg_def != v_reg &&
          (data->high_def_over_low_word || data->prev_value_high.value == kNoValue)) {
        vreg_high_words_.ClearBit(v_reg);
      }
    } else {
      DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), change);
      mir_data_[next_change].RemovePrevChange(v_reg, data);
    }
  }
}

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;
}

bool GvnDeadCodeElimination::VRegChains::IsVRegUsed(uint16_t first_change, uint16_t last_change,
                                                    int v_reg, MIRGraph* mir_graph) 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 (mir_graph->SRegToVReg(ssa_rep->uses[i]) == v_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) {
  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;

  size_t num_uses = bb_->predecessors.size();
  mir_graph_->AllocateSSAUseData(phi, num_uses);
  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 values 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) {
    if (wide) {
      DCHECK_EQ(new_s_reg + 1, mir_to_kill->ssa_rep->defs[1]);
      DCHECK_EQ(mir_graph_->SRegToVReg(new_s_reg) + 1, mir_graph_->SRegToVReg(new_s_reg + 1));
      CreatePhi(new_s_reg + 1);  // High word Phi.
    }
    MIR* phi = CreatePhi(new_s_reg);
    // If this is a degenerate Phi with all inputs being the same SSA reg, we need to its uses.
    DCHECK_NE(phi->ssa_rep->num_uses, 0u);
    int old_s_reg = phi->ssa_rep->uses[0];
    bool all_same = true;
    for (size_t i = 1u, num = phi->ssa_rep->num_uses; i != num; ++i) {
      if (phi->ssa_rep->uses[i] != old_s_reg) {
        all_same = false;
        break;
      }
    }
    if (all_same) {
      vreg_chains_.RenameSRegUses(0u, last_change, old_s_reg, new_s_reg, wide);
    }
    return phi;
  } 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) {
          // Check if the move's destination vreg is unused between check_change and the move.
          uint32_t new_dest_v_reg = mir_graph_->SRegToVReg(d->mir->ssa_rep->defs[0]);
          if (!vreg_chains_.IsVRegUsed(check_change + 1u, c, new_dest_v_reg, mir_graph_) &&
              (!d->wide_def ||
               !vreg_chains_.IsVRegUsed(check_change + 1u, c, new_dest_v_reg + 1, mir_graph_))) {
            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: {
      // Determine if this Phi is merging wide regs.
      RegLocation raw_dest = gvn_->GetMirGraph()->GetRawDest(mir);
      if (raw_dest.high_word) {
        // This is the high part of a wide reg. Ignore the Phi.
        return false;
      }
      bool wide = raw_dest.wide;
      // Record the value.
      DCHECK_EQ(mir->ssa_rep->num_defs, 1);
      int s_reg = mir->ssa_rep->defs[0];
      uint16_t new_value = wide ? lvn_->GetSregValueWide(s_reg) : lvn_->GetSregValue(s_reg);

      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::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 Instruction::CHECK_CAST:
      DCHECK_EQ(mir->ssa_rep->num_uses, 1);
      must_keep = true;  // Keep for type information even if MIR_IGNORE_CHECK_CAST.
      uses_all_vregs = (mir->optimization_flags & MIR_IGNORE_CHECK_CAST) == 0;
      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();
  }

  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