compiler/optimizing/nodes.cc

/*
 * Copyright (C) 2014 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 "nodes.h"

#include "code_generator.h"
#include "ssa_builder.h"
#include "base/bit_vector-inl.h"
#include "base/bit_utils.h"
#include "utils/growable_array.h"
#include "scoped_thread_state_change.h"

namespace art {

void HGraph::AddBlock(HBasicBlock* block) {
  block->SetBlockId(blocks_.Size());
  blocks_.Add(block);
}

void HGraph::FindBackEdges(ArenaBitVector* visited) {
  ArenaBitVector visiting(arena_, blocks_.Size(), false);
  VisitBlockForBackEdges(entry_block_, visited, &visiting);
}

static void RemoveAsUser(HInstruction* instruction) {
  for (size_t i = 0; i < instruction->InputCount(); i++) {
    instruction->RemoveAsUserOfInput(i);
  }

  for (HEnvironment* environment = instruction->GetEnvironment();
       environment != nullptr;
       environment = environment->GetParent()) {
    for (size_t i = 0, e = environment->Size(); i < e; ++i) {
      if (environment->GetInstructionAt(i) != nullptr) {
        environment->RemoveAsUserOfInput(i);
      }
    }
  }
}

void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const {
  for (size_t i = 0; i < blocks_.Size(); ++i) {
    if (!visited.IsBitSet(i)) {
      HBasicBlock* block = blocks_.Get(i);
      DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage";
      for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
        RemoveAsUser(it.Current());
      }
    }
  }
}

void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
  for (size_t i = 0; i < blocks_.Size(); ++i) {
    if (!visited.IsBitSet(i)) {
      HBasicBlock* block = blocks_.Get(i);
      // We only need to update the successor, which might be live.
      for (HBasicBlock* successor : block->GetSuccessors()) {
        successor->RemovePredecessor(block);
      }
      // Remove the block from the list of blocks, so that further analyses
      // never see it.
      blocks_.Put(i, nullptr);
    }
  }
}

void HGraph::VisitBlockForBackEdges(HBasicBlock* block,
                                    ArenaBitVector* visited,
                                    ArenaBitVector* visiting) {
  int id = block->GetBlockId();
  if (visited->IsBitSet(id)) return;

  visited->SetBit(id);
  visiting->SetBit(id);
  for (HBasicBlock* successor : block->GetSuccessors()) {
    if (visiting->IsBitSet(successor->GetBlockId())) {
      successor->AddBackEdge(block);
    } else {
      VisitBlockForBackEdges(successor, visited, visiting);
    }
  }
  visiting->ClearBit(id);
}

void HGraph::BuildDominatorTree() {
  // (1) Simplify the CFG so that catch blocks have only exceptional incoming
  //     edges. This invariant simplifies building SSA form because Phis cannot
  //     collect both normal- and exceptional-flow values at the same time.
  SimplifyCatchBlocks();

  ArenaBitVector visited(arena_, blocks_.Size(), false);

  // (2) Find the back edges in the graph doing a DFS traversal.
  FindBackEdges(&visited);

  // (3) Remove instructions and phis from blocks not visited during
  //     the initial DFS as users from other instructions, so that
  //     users can be safely removed before uses later.
  RemoveInstructionsAsUsersFromDeadBlocks(visited);

  // (4) Remove blocks not visited during the initial DFS.
  //     Step (4) requires dead blocks to be removed from the
  //     predecessors list of live blocks.
  RemoveDeadBlocks(visited);

  // (5) Simplify the CFG now, so that we don't need to recompute
  //     dominators and the reverse post order.
  SimplifyCFG();

  // (6) Compute the dominance information and the reverse post order.
  ComputeDominanceInformation();
}

void HGraph::ClearDominanceInformation() {
  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
    it.Current()->ClearDominanceInformation();
  }
  reverse_post_order_.Reset();
}

void HBasicBlock::ClearDominanceInformation() {
  dominated_blocks_.clear();
  dominator_ = nullptr;
}

void HGraph::ComputeDominanceInformation() {
  DCHECK(reverse_post_order_.IsEmpty());
  GrowableArray<size_t> visits(arena_, blocks_.Size());
  visits.SetSize(blocks_.Size());
  reverse_post_order_.Add(entry_block_);
  for (HBasicBlock* successor : entry_block_->GetSuccessors()) {
    VisitBlockForDominatorTree(successor, entry_block_, &visits);
  }
}

HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const {
  ArenaBitVector visited(arena_, blocks_.Size(), false);
  // Walk the dominator tree of the first block and mark the visited blocks.
  while (first != nullptr) {
    visited.SetBit(first->GetBlockId());
    first = first->GetDominator();
  }
  // Walk the dominator tree of the second block until a marked block is found.
  while (second != nullptr) {
    if (visited.IsBitSet(second->GetBlockId())) {
      return second;
    }
    second = second->GetDominator();
  }
  LOG(ERROR) << "Could not find common dominator";
  return nullptr;
}

void HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
                                        HBasicBlock* predecessor,
                                        GrowableArray<size_t>* visits) {
  if (block->GetDominator() == nullptr) {
    block->SetDominator(predecessor);
  } else {
    block->SetDominator(FindCommonDominator(block->GetDominator(), predecessor));
  }

  visits->Increment(block->GetBlockId());
  // Once all the forward edges have been visited, we know the immediate
  // dominator of the block. We can then start visiting its successors.
  if (visits->Get(block->GetBlockId()) ==
      block->GetPredecessors().size() - block->NumberOfBackEdges()) {
    block->GetDominator()->AddDominatedBlock(block);
    reverse_post_order_.Add(block);
    for (HBasicBlock* successor : block->GetSuccessors()) {
      VisitBlockForDominatorTree(successor, block, visits);
    }
  }
}

void HGraph::TransformToSsa() {
  DCHECK(!reverse_post_order_.IsEmpty());
  SsaBuilder ssa_builder(this);
  ssa_builder.BuildSsa();
}

HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) {
  HBasicBlock* new_block = new (arena_) HBasicBlock(this, successor->GetDexPc());
  AddBlock(new_block);
  // Use `InsertBetween` to ensure the predecessor index and successor index of
  // `block` and `successor` are preserved.
  new_block->InsertBetween(block, successor);
  return new_block;
}

void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) {
  // Insert a new node between `block` and `successor` to split the
  // critical edge.
  HBasicBlock* new_block = SplitEdge(block, successor);
  new_block->AddInstruction(new (arena_) HGoto());
  if (successor->IsLoopHeader()) {
    // If we split at a back edge boundary, make the new block the back edge.
    HLoopInformation* info = successor->GetLoopInformation();
    if (info->IsBackEdge(*block)) {
      info->RemoveBackEdge(block);
      info->AddBackEdge(new_block);
    }
  }
}

void HGraph::SimplifyLoop(HBasicBlock* header) {
  HLoopInformation* info = header->GetLoopInformation();

  // Make sure the loop has only one pre header. This simplifies SSA building by having
  // to just look at the pre header to know which locals are initialized at entry of the
  // loop.
  size_t number_of_incomings = header->GetPredecessors().size() - info->NumberOfBackEdges();
  if (number_of_incomings != 1) {
    HBasicBlock* pre_header = new (arena_) HBasicBlock(this, header->GetDexPc());
    AddBlock(pre_header);
    pre_header->AddInstruction(new (arena_) HGoto());

    for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
      HBasicBlock* predecessor = header->GetPredecessor(pred);
      if (!info->IsBackEdge(*predecessor)) {
        predecessor->ReplaceSuccessor(header, pre_header);
        pred--;
      }
    }
    pre_header->AddSuccessor(header);
  }

  // Make sure the first predecessor of a loop header is the incoming block.
  if (info->IsBackEdge(*header->GetPredecessor(0))) {
    HBasicBlock* to_swap = header->GetPredecessor(0);
    for (size_t pred = 1, e = header->GetPredecessors().size(); pred < e; ++pred) {
      HBasicBlock* predecessor = header->GetPredecessor(pred);
      if (!info->IsBackEdge(*predecessor)) {
        header->predecessors_[pred] = to_swap;
        header->predecessors_[0] = predecessor;
        break;
      }
    }
  }

  // Place the suspend check at the beginning of the header, so that live registers
  // will be known when allocating registers. Note that code generation can still
  // generate the suspend check at the back edge, but needs to be careful with
  // loop phi spill slots (which are not written to at back edge).
  HInstruction* first_instruction = header->GetFirstInstruction();
  if (!first_instruction->IsSuspendCheck()) {
    HSuspendCheck* check = new (arena_) HSuspendCheck(header->GetDexPc());
    header->InsertInstructionBefore(check, first_instruction);
    first_instruction = check;
  }
  info->SetSuspendCheck(first_instruction->AsSuspendCheck());
}

static bool CheckIfPredecessorAtIsExceptional(const HBasicBlock& block, size_t pred_idx) {
  HBasicBlock* predecessor = block.GetPredecessor(pred_idx);
  if (!predecessor->EndsWithTryBoundary()) {
    // Only edges from HTryBoundary can be exceptional.
    return false;
  }
  HTryBoundary* try_boundary = predecessor->GetLastInstruction()->AsTryBoundary();
  if (try_boundary->GetNormalFlowSuccessor() == &block) {
    // This block is the normal-flow successor of `try_boundary`, but it could
    // also be one of its exception handlers if catch blocks have not been
    // simplified yet. Predecessors are unordered, so we will consider the first
    // occurrence to be the normal edge and a possible second occurrence to be
    // the exceptional edge.
    return !block.IsFirstIndexOfPredecessor(predecessor, pred_idx);
  } else {
    // This is not the normal-flow successor of `try_boundary`, hence it must be
    // one of its exception handlers.
    DCHECK(try_boundary->HasExceptionHandler(block));
    return true;
  }
}

void HGraph::SimplifyCatchBlocks() {
  for (size_t i = 0; i < blocks_.Size(); ++i) {
    HBasicBlock* catch_block = blocks_.Get(i);
    if (!catch_block->IsCatchBlock()) {
      continue;
    }

    bool exceptional_predecessors_only = true;
    for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) {
      if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) {
        exceptional_predecessors_only = false;
        break;
      }
    }

    if (!exceptional_predecessors_only) {
      // Catch block has normal-flow predecessors and needs to be simplified.
      // Splitting the block before its first instruction moves all its
      // instructions into `normal_block` and links the two blocks with a Goto.
      // Afterwards, incoming normal-flow edges are re-linked to `normal_block`,
      // leaving `catch_block` with the exceptional edges only.
      // Note that catch blocks with normal-flow predecessors cannot begin with
      // a MOVE_EXCEPTION instruction, as guaranteed by the verifier.
      DCHECK(!catch_block->GetFirstInstruction()->IsLoadException());
      HBasicBlock* normal_block = catch_block->SplitBefore(catch_block->GetFirstInstruction());
      for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) {
        if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) {
          catch_block->GetPredecessor(j)->ReplaceSuccessor(catch_block, normal_block);
          --j;
        }
      }
    }
  }
}

void HGraph::ComputeTryBlockInformation() {
  // Iterate in reverse post order to propagate try membership information from
  // predecessors to their successors.
  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
    HBasicBlock* block = it.Current();
    if (block->IsEntryBlock() || block->IsCatchBlock()) {
      // Catch blocks after simplification have only exceptional predecessors
      // and hence are never in tries.
      continue;
    }

    // Infer try membership from the first predecessor. Having simplified loops,
    // the first predecessor can never be a back edge and therefore it must have
    // been visited already and had its try membership set.
    HBasicBlock* first_predecessor = block->GetPredecessor(0);
    DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor));
    const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors();
    if (try_entry != nullptr) {
      block->SetTryCatchInformation(new (arena_) TryCatchInformation(*try_entry));
    }
  }
}

bool HGraph::HasTryCatch() const {
  for (size_t i = 0, e = blocks_.Size(); i < e; ++i) {
    HBasicBlock* block = blocks_.Get(i);
    if (block != nullptr && (block->IsTryBlock() || block->IsCatchBlock())) {
      return true;
    }
  }
  return false;
}

void HGraph::SimplifyCFG() {
  // Simplify the CFG for future analysis, and code generation:
  // (1): Split critical edges.
  // (2): Simplify loops by having only one back edge, and one preheader.
  for (size_t i = 0; i < blocks_.Size(); ++i) {
    HBasicBlock* block = blocks_.Get(i);
    if (block == nullptr) continue;
    if (block->NumberOfNormalSuccessors() > 1) {
      for (size_t j = 0; j < block->GetSuccessors().size(); ++j) {
        HBasicBlock* successor = block->GetSuccessor(j);
        DCHECK(!successor->IsCatchBlock());
        if (successor->GetPredecessors().size() > 1) {
          SplitCriticalEdge(block, successor);
          --j;
        }
      }
    }
    if (block->IsLoopHeader()) {
      SimplifyLoop(block);
    }
  }
}

bool HGraph::AnalyzeNaturalLoops() const {
  // Order does not matter.
  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
    HBasicBlock* block = it.Current();
    if (block->IsLoopHeader()) {
      if (block->IsCatchBlock()) {
        // TODO: Dealing with exceptional back edges could be tricky because
        //       they only approximate the real control flow. Bail out for now.
        return false;
      }
      HLoopInformation* info = block->GetLoopInformation();
      if (!info->Populate()) {
        // Abort if the loop is non natural. We currently bailout in such cases.
        return false;
      }
    }
  }
  return true;
}

void HGraph::InsertConstant(HConstant* constant) {
  // New constants are inserted before the final control-flow instruction
  // of the graph, or at its end if called from the graph builder.
  if (entry_block_->EndsWithControlFlowInstruction()) {
    entry_block_->InsertInstructionBefore(constant, entry_block_->GetLastInstruction());
  } else {
    entry_block_->AddInstruction(constant);
  }
}

HNullConstant* HGraph::GetNullConstant() {
  // For simplicity, don't bother reviving the cached null constant if it is
  // not null and not in a block. Otherwise, we need to clear the instruction
  // id and/or any invariants the graph is assuming when adding new instructions.
  if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) {
    cached_null_constant_ = new (arena_) HNullConstant();
    InsertConstant(cached_null_constant_);
  }
  return cached_null_constant_;
}

HCurrentMethod* HGraph::GetCurrentMethod() {
  // For simplicity, don't bother reviving the cached current method if it is
  // not null and not in a block. Otherwise, we need to clear the instruction
  // id and/or any invariants the graph is assuming when adding new instructions.
  if ((cached_current_method_ == nullptr) || (cached_current_method_->GetBlock() == nullptr)) {
    cached_current_method_ = new (arena_) HCurrentMethod(
        Is64BitInstructionSet(instruction_set_) ? Primitive::kPrimLong : Primitive::kPrimInt);
    if (entry_block_->GetFirstInstruction() == nullptr) {
      entry_block_->AddInstruction(cached_current_method_);
    } else {
      entry_block_->InsertInstructionBefore(
          cached_current_method_, entry_block_->GetFirstInstruction());
    }
  }
  return cached_current_method_;
}

HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value) {
  switch (type) {
    case Primitive::Type::kPrimBoolean:
      DCHECK(IsUint<1>(value));
      FALLTHROUGH_INTENDED;
    case Primitive::Type::kPrimByte:
    case Primitive::Type::kPrimChar:
    case Primitive::Type::kPrimShort:
    case Primitive::Type::kPrimInt:
      DCHECK(IsInt(Primitive::ComponentSize(type) * kBitsPerByte, value));
      return GetIntConstant(static_cast<int32_t>(value));

    case Primitive::Type::kPrimLong:
      return GetLongConstant(value);

    default:
      LOG(FATAL) << "Unsupported constant type";
      UNREACHABLE();
  }
}

void HGraph::CacheFloatConstant(HFloatConstant* constant) {
  int32_t value = bit_cast<int32_t, float>(constant->GetValue());
  DCHECK(cached_float_constants_.find(value) == cached_float_constants_.end());
  cached_float_constants_.Overwrite(value, constant);
}

void HGraph::CacheDoubleConstant(HDoubleConstant* constant) {
  int64_t value = bit_cast<int64_t, double>(constant->GetValue());
  DCHECK(cached_double_constants_.find(value) == cached_double_constants_.end());
  cached_double_constants_.Overwrite(value, constant);
}

void HLoopInformation::Add(HBasicBlock* block) {
  blocks_.SetBit(block->GetBlockId());
}

void HLoopInformation::Remove(HBasicBlock* block) {
  blocks_.ClearBit(block->GetBlockId());
}

void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
  if (blocks_.IsBitSet(block->GetBlockId())) {
    return;
  }

  blocks_.SetBit(block->GetBlockId());
  block->SetInLoop(this);
  for (HBasicBlock* predecessor : block->GetPredecessors()) {
    PopulateRecursive(predecessor);
  }
}

bool HLoopInformation::Populate() {
  DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
  for (size_t i = 0, e = GetBackEdges().Size(); i < e; ++i) {
    HBasicBlock* back_edge = GetBackEdges().Get(i);
    DCHECK(back_edge->GetDominator() != nullptr);
    if (!header_->Dominates(back_edge)) {
      // This loop is not natural. Do not bother going further.
      return false;
    }

    // Populate this loop: starting with the back edge, recursively add predecessors
    // that are not already part of that loop. Set the header as part of the loop
    // to end the recursion.
    // This is a recursive implementation of the algorithm described in
    // "Advanced Compiler Design & Implementation" (Muchnick) p192.
    blocks_.SetBit(header_->GetBlockId());
    PopulateRecursive(back_edge);
  }
  return true;
}

void HLoopInformation::Update() {
  HGraph* graph = header_->GetGraph();
  for (uint32_t id : blocks_.Indexes()) {
    HBasicBlock* block = graph->GetBlocks().Get(id);
    // Reset loop information of non-header blocks inside the loop, except
    // members of inner nested loops because those should already have been
    // updated by their own LoopInformation.
    if (block->GetLoopInformation() == this && block != header_) {
      block->SetLoopInformation(nullptr);
    }
  }
  blocks_.ClearAllBits();

  if (back_edges_.IsEmpty()) {
    // The loop has been dismantled, delete its suspend check and remove info
    // from the header.
    DCHECK(HasSuspendCheck());
    header_->RemoveInstruction(suspend_check_);
    header_->SetLoopInformation(nullptr);
    header_ = nullptr;
    suspend_check_ = nullptr;
  } else {
    if (kIsDebugBuild) {
      for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
        DCHECK(header_->Dominates(back_edges_.Get(i)));
      }
    }
    // This loop still has reachable back edges. Repopulate the list of blocks.
    bool populate_successful = Populate();
    DCHECK(populate_successful);
  }
}

HBasicBlock* HLoopInformation::GetPreHeader() const {
  return header_->GetDominator();
}

bool HLoopInformation::Contains(const HBasicBlock& block) const {
  return blocks_.IsBitSet(block.GetBlockId());
}

bool HLoopInformation::IsIn(const HLoopInformation& other) const {
  return other.blocks_.IsBitSet(header_->GetBlockId());
}

size_t HLoopInformation::GetLifetimeEnd() const {
  size_t last_position = 0;
  for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
    last_position = std::max(back_edges_.Get(i)->GetLifetimeEnd(), last_position);
  }
  return last_position;
}

bool HBasicBlock::Dominates(HBasicBlock* other) const {
  // Walk up the dominator tree from `other`, to find out if `this`
  // is an ancestor.
  HBasicBlock* current = other;
  while (current != nullptr) {
    if (current == this) {
      return true;
    }
    current = current->GetDominator();
  }
  return false;
}

static void UpdateInputsUsers(HInstruction* instruction) {
  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
    instruction->InputAt(i)->AddUseAt(instruction, i);
  }
  // Environment should be created later.
  DCHECK(!instruction->HasEnvironment());
}

void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial,
                                                  HInstruction* replacement) {
  DCHECK(initial->GetBlock() == this);
  InsertInstructionBefore(replacement, initial);
  initial->ReplaceWith(replacement);
  RemoveInstruction(initial);
}

static void Add(HInstructionList* instruction_list,
                HBasicBlock* block,
                HInstruction* instruction) {
  DCHECK(instruction->GetBlock() == nullptr);
  DCHECK_EQ(instruction->GetId(), -1);
  instruction->SetBlock(block);
  instruction->SetId(block->GetGraph()->GetNextInstructionId());
  UpdateInputsUsers(instruction);
  instruction_list->AddInstruction(instruction);
}

void HBasicBlock::AddInstruction(HInstruction* instruction) {
  Add(&instructions_, this, instruction);
}

void HBasicBlock::AddPhi(HPhi* phi) {
  Add(&phis_, this, phi);
}

void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
  DCHECK(!cursor->IsPhi());
  DCHECK(!instruction->IsPhi());
  DCHECK_EQ(instruction->GetId(), -1);
  DCHECK_NE(cursor->GetId(), -1);
  DCHECK_EQ(cursor->GetBlock(), this);
  DCHECK(!instruction->IsControlFlow());
  instruction->SetBlock(this);
  instruction->SetId(GetGraph()->GetNextInstructionId());
  UpdateInputsUsers(instruction);
  instructions_.InsertInstructionBefore(instruction, cursor);
}

void HBasicBlock::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) {
  DCHECK(!cursor->IsPhi());
  DCHECK(!instruction->IsPhi());
  DCHECK_EQ(instruction->GetId(), -1);
  DCHECK_NE(cursor->GetId(), -1);
  DCHECK_EQ(cursor->GetBlock(), this);
  DCHECK(!instruction->IsControlFlow());
  DCHECK(!cursor->IsControlFlow());
  instruction->SetBlock(this);
  instruction->SetId(GetGraph()->GetNextInstructionId());
  UpdateInputsUsers(instruction);
  instructions_.InsertInstructionAfter(instruction, cursor);
}

void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) {
  DCHECK_EQ(phi->GetId(), -1);
  DCHECK_NE(cursor->GetId(), -1);
  DCHECK_EQ(cursor->GetBlock(), this);
  phi->SetBlock(this);
  phi->SetId(GetGraph()->GetNextInstructionId());
  UpdateInputsUsers(phi);
  phis_.InsertInstructionAfter(phi, cursor);
}

static void Remove(HInstructionList* instruction_list,
                   HBasicBlock* block,
                   HInstruction* instruction,
                   bool ensure_safety) {
  DCHECK_EQ(block, instruction->GetBlock());
  instruction->SetBlock(nullptr);
  instruction_list->RemoveInstruction(instruction);
  if (ensure_safety) {
    DCHECK(instruction->GetUses().IsEmpty());
    DCHECK(instruction->GetEnvUses().IsEmpty());
    RemoveAsUser(instruction);
  }
}

void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) {
  DCHECK(!instruction->IsPhi());
  Remove(&instructions_, this, instruction, ensure_safety);
}

void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) {
  Remove(&phis_, this, phi, ensure_safety);
}

void HBasicBlock::RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety) {
  if (instruction->IsPhi()) {
    RemovePhi(instruction->AsPhi(), ensure_safety);
  } else {
    RemoveInstruction(instruction, ensure_safety);
  }
}

void HEnvironment::CopyFrom(const GrowableArray<HInstruction*>& locals) {
  for (size_t i = 0; i < locals.Size(); i++) {
    HInstruction* instruction = locals.Get(i);
    SetRawEnvAt(i, instruction);
    if (instruction != nullptr) {
      instruction->AddEnvUseAt(this, i);
    }
  }
}

void HEnvironment::CopyFrom(HEnvironment* env) {
  for (size_t i = 0; i < env->Size(); i++) {
    HInstruction* instruction = env->GetInstructionAt(i);
    SetRawEnvAt(i, instruction);
    if (instruction != nullptr) {
      instruction->AddEnvUseAt(this, i);
    }
  }
}

void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env,
                                                 HBasicBlock* loop_header) {
  DCHECK(loop_header->IsLoopHeader());
  for (size_t i = 0; i < env->Size(); i++) {
    HInstruction* instruction = env->GetInstructionAt(i);
    SetRawEnvAt(i, instruction);
    if (instruction == nullptr) {
      continue;
    }
    if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) {
      // At the end of the loop pre-header, the corresponding value for instruction
      // is the first input of the phi.
      HInstruction* initial = instruction->AsPhi()->InputAt(0);
      DCHECK(initial->GetBlock()->Dominates(loop_header));
      SetRawEnvAt(i, initial);
      initial->AddEnvUseAt(this, i);
    } else {
      instruction->AddEnvUseAt(this, i);
    }
  }
}

void HEnvironment::RemoveAsUserOfInput(size_t index) const {
  const HUserRecord<HEnvironment*> user_record = vregs_.Get(index);
  user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode());
}

HInstruction* HInstruction::GetNextDisregardingMoves() const {
  HInstruction* next = GetNext();
  while (next != nullptr && next->IsParallelMove()) {
    next = next->GetNext();
  }
  return next;
}

HInstruction* HInstruction::GetPreviousDisregardingMoves() const {
  HInstruction* previous = GetPrevious();
  while (previous != nullptr && previous->IsParallelMove()) {
    previous = previous->GetPrevious();
  }
  return previous;
}

void HInstructionList::AddInstruction(HInstruction* instruction) {
  if (first_instruction_ == nullptr) {
    DCHECK(last_instruction_ == nullptr);
    first_instruction_ = last_instruction_ = instruction;
  } else {
    last_instruction_->next_ = instruction;
    instruction->previous_ = last_instruction_;
    last_instruction_ = instruction;
  }
}

void HInstructionList::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
  DCHECK(Contains(cursor));
  if (cursor == first_instruction_) {
    cursor->previous_ = instruction;
    instruction->next_ = cursor;
    first_instruction_ = instruction;
  } else {
    instruction->previous_ = cursor->previous_;
    instruction->next_ = cursor;
    cursor->previous_ = instruction;
    instruction->previous_->next_ = instruction;
  }
}

void HInstructionList::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) {
  DCHECK(Contains(cursor));
  if (cursor == last_instruction_) {
    cursor->next_ = instruction;
    instruction->previous_ = cursor;
    last_instruction_ = instruction;
  } else {
    instruction->next_ = cursor->next_;
    instruction->previous_ = cursor;
    cursor->next_ = instruction;
    instruction->next_->previous_ = instruction;
  }
}

void HInstructionList::RemoveInstruction(HInstruction* instruction) {
  if (instruction->previous_ != nullptr) {
    instruction->previous_->next_ = instruction->next_;
  }
  if (instruction->next_ != nullptr) {
    instruction->next_->previous_ = instruction->previous_;
  }
  if (instruction == first_instruction_) {
    first_instruction_ = instruction->next_;
  }
  if (instruction == last_instruction_) {
    last_instruction_ = instruction->previous_;
  }
}

bool HInstructionList::Contains(HInstruction* instruction) const {
  for (HInstructionIterator it(*this); !it.Done(); it.Advance()) {
    if (it.Current() == instruction) {
      return true;
    }
  }
  return false;
}

bool HInstructionList::FoundBefore(const HInstruction* instruction1,
                                   const HInstruction* instruction2) const {
  DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock());
  for (HInstructionIterator it(*this); !it.Done(); it.Advance()) {
    if (it.Current() == instruction1) {
      return true;
    }
    if (it.Current() == instruction2) {
      return false;
    }
  }
  LOG(FATAL) << "Did not find an order between two instructions of the same block.";
  return true;
}

bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const {
  if (other_instruction == this) {
    // An instruction does not strictly dominate itself.
    return false;
  }
  HBasicBlock* block = GetBlock();
  HBasicBlock* other_block = other_instruction->GetBlock();
  if (block != other_block) {
    return GetBlock()->Dominates(other_instruction->GetBlock());
  } else {
    // If both instructions are in the same block, ensure this
    // instruction comes before `other_instruction`.
    if (IsPhi()) {
      if (!other_instruction->IsPhi()) {
        // Phis appear before non phi-instructions so this instruction
        // dominates `other_instruction`.
        return true;
      } else {
        // There is no order among phis.
        LOG(FATAL) << "There is no dominance between phis of a same block.";
        return false;
      }
    } else {
      // `this` is not a phi.
      if (other_instruction->IsPhi()) {
        // Phis appear before non phi-instructions so this instruction
        // does not dominate `other_instruction`.
        return false;
      } else {
        // Check whether this instruction comes before
        // `other_instruction` in the instruction list.
        return block->GetInstructions().FoundBefore(this, other_instruction);
      }
    }
  }
}

void HInstruction::ReplaceWith(HInstruction* other) {
  DCHECK(other != nullptr);
  for (HUseIterator<HInstruction*> it(GetUses()); !it.Done(); it.Advance()) {
    HUseListNode<HInstruction*>* current = it.Current();
    HInstruction* user = current->GetUser();
    size_t input_index = current->GetIndex();
    user->SetRawInputAt(input_index, other);
    other->AddUseAt(user, input_index);
  }

  for (HUseIterator<HEnvironment*> it(GetEnvUses()); !it.Done(); it.Advance()) {
    HUseListNode<HEnvironment*>* current = it.Current();
    HEnvironment* user = current->GetUser();
    size_t input_index = current->GetIndex();
    user->SetRawEnvAt(input_index, other);
    other->AddEnvUseAt(user, input_index);
  }

  uses_.Clear();
  env_uses_.Clear();
}

void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
  RemoveAsUserOfInput(index);
  SetRawInputAt(index, replacement);
  replacement->AddUseAt(this, index);
}

size_t HInstruction::EnvironmentSize() const {
  return HasEnvironment() ? environment_->Size() : 0;
}

void HPhi::AddInput(HInstruction* input) {
  DCHECK(input->GetBlock() != nullptr);
  inputs_.Add(HUserRecord<HInstruction*>(input));
  input->AddUseAt(this, inputs_.Size() - 1);
}

void HPhi::RemoveInputAt(size_t index) {
  RemoveAsUserOfInput(index);
  inputs_.DeleteAt(index);
  for (size_t i = index, e = InputCount(); i < e; ++i) {
    InputRecordAt(i).GetUseNode()->SetIndex(i);
  }
}

#define DEFINE_ACCEPT(name, super)                                             \
void H##name::Accept(HGraphVisitor* visitor) {                                 \
  visitor->Visit##name(this);                                                  \
}

FOR_EACH_INSTRUCTION(DEFINE_ACCEPT)

#undef DEFINE_ACCEPT

void HGraphVisitor::VisitInsertionOrder() {
  const GrowableArray<HBasicBlock*>& blocks = graph_->GetBlocks();
  for (size_t i = 0 ; i < blocks.Size(); i++) {
    HBasicBlock* block = blocks.Get(i);
    if (block != nullptr) {
      VisitBasicBlock(block);
    }
  }
}

void HGraphVisitor::VisitReversePostOrder() {
  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
    VisitBasicBlock(it.Current());
  }
}

void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
    it.Current()->Accept(this);
  }
  for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
    it.Current()->Accept(this);
  }
}

HConstant* HTypeConversion::TryStaticEvaluation() const {
  HGraph* graph = GetBlock()->GetGraph();
  if (GetInput()->IsIntConstant()) {
    int32_t value = GetInput()->AsIntConstant()->GetValue();
    switch (GetResultType()) {
      case Primitive::kPrimLong:
        return graph->GetLongConstant(static_cast<int64_t>(value));
      case Primitive::kPrimFloat:
        return graph->GetFloatConstant(static_cast<float>(value));
      case Primitive::kPrimDouble:
        return graph->GetDoubleConstant(static_cast<double>(value));
      default:
        return nullptr;
    }
  } else if (GetInput()->IsLongConstant()) {
    int64_t value = GetInput()->AsLongConstant()->GetValue();
    switch (GetResultType()) {
      case Primitive::kPrimInt:
        return graph->GetIntConstant(static_cast<int32_t>(value));
      case Primitive::kPrimFloat:
        return graph->GetFloatConstant(static_cast<float>(value));
      case Primitive::kPrimDouble:
        return graph->GetDoubleConstant(static_cast<double>(value));
      default:
        return nullptr;
    }
  } else if (GetInput()->IsFloatConstant()) {
    float value = GetInput()->AsFloatConstant()->GetValue();
    switch (GetResultType()) {
      case Primitive::kPrimInt:
        if (std::isnan(value))
          return graph->GetIntConstant(0);
        if (value >= kPrimIntMax)
          return graph->GetIntConstant(kPrimIntMax);
        if (value <= kPrimIntMin)
          return graph->GetIntConstant(kPrimIntMin);
        return graph->GetIntConstant(static_cast<int32_t>(value));
      case Primitive::kPrimLong:
        if (std::isnan(value))
          return graph->GetLongConstant(0);
        if (value >= kPrimLongMax)
          return graph->GetLongConstant(kPrimLongMax);
        if (value <= kPrimLongMin)
          return graph->GetLongConstant(kPrimLongMin);
        return graph->GetLongConstant(static_cast<int64_t>(value));
      case Primitive::kPrimDouble:
        return graph->GetDoubleConstant(static_cast<double>(value));
      default:
        return nullptr;
    }
  } else if (GetInput()->IsDoubleConstant()) {
    double value = GetInput()->AsDoubleConstant()->GetValue();
    switch (GetResultType()) {
      case Primitive::kPrimInt:
        if (std::isnan(value))
          return graph->GetIntConstant(0);
        if (value >= kPrimIntMax)
          return graph->GetIntConstant(kPrimIntMax);
        if (value <= kPrimLongMin)
          return graph->GetIntConstant(kPrimIntMin);
        return graph->GetIntConstant(static_cast<int32_t>(value));
      case Primitive::kPrimLong:
        if (std::isnan(value))
          return graph->GetLongConstant(0);
        if (value >= kPrimLongMax)
          return graph->GetLongConstant(kPrimLongMax);
        if (value <= kPrimLongMin)
          return graph->GetLongConstant(kPrimLongMin);
        return graph->GetLongConstant(static_cast<int64_t>(value));
      case Primitive::kPrimFloat:
        return graph->GetFloatConstant(static_cast<float>(value));
      default:
        return nullptr;
    }
  }
  return nullptr;
}

HConstant* HUnaryOperation::TryStaticEvaluation() const {
  if (GetInput()->IsIntConstant()) {
    return Evaluate(GetInput()->AsIntConstant());
  } else if (GetInput()->IsLongConstant()) {
    return Evaluate(GetInput()->AsLongConstant());
  }
  return nullptr;
}

HConstant* HBinaryOperation::TryStaticEvaluation() const {
  if (GetLeft()->IsIntConstant()) {
    if (GetRight()->IsIntConstant()) {
      return Evaluate(GetLeft()->AsIntConstant(), GetRight()->AsIntConstant());
    } else if (GetRight()->IsLongConstant()) {
      return Evaluate(GetLeft()->AsIntConstant(), GetRight()->AsLongConstant());
    }
  } else if (GetLeft()->IsLongConstant()) {
    if (GetRight()->IsIntConstant()) {
      return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsIntConstant());
    } else if (GetRight()->IsLongConstant()) {
      return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsLongConstant());
    }
  }
  return nullptr;
}

HConstant* HBinaryOperation::GetConstantRight() const {
  if (GetRight()->IsConstant()) {
    return GetRight()->AsConstant();
  } else if (IsCommutative() && GetLeft()->IsConstant()) {
    return GetLeft()->AsConstant();
  } else {
    return nullptr;
  }
}

// If `GetConstantRight()` returns one of the input, this returns the other
// one. Otherwise it returns null.
HInstruction* HBinaryOperation::GetLeastConstantLeft() const {
  HInstruction* most_constant_right = GetConstantRight();
  if (most_constant_right == nullptr) {
    return nullptr;
  } else if (most_constant_right == GetLeft()) {
    return GetRight();
  } else {
    return GetLeft();
  }
}

bool HCondition::IsBeforeWhenDisregardMoves(HInstruction* instruction) const {
  return this == instruction->GetPreviousDisregardingMoves();
}

bool HInstruction::Equals(HInstruction* other) const {
  if (!InstructionTypeEquals(other)) return false;
  DCHECK_EQ(GetKind(), other->GetKind());
  if (!InstructionDataEquals(other)) return false;
  if (GetType() != other->GetType()) return false;
  if (InputCount() != other->InputCount()) return false;

  for (size_t i = 0, e = InputCount(); i < e; ++i) {
    if (InputAt(i) != other->InputAt(i)) return false;
  }
  DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode());
  return true;
}

std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs) {
#define DECLARE_CASE(type, super) case HInstruction::k##type: os << #type; break;
  switch (rhs) {
    FOR_EACH_INSTRUCTION(DECLARE_CASE)
    default:
      os << "Unknown instruction kind " << static_cast<int>(rhs);
      break;
  }
#undef DECLARE_CASE
  return os;
}

void HInstruction::MoveBefore(HInstruction* cursor) {
  next_->previous_ = previous_;
  if (previous_ != nullptr) {
    previous_->next_ = next_;
  }
  if (block_->instructions_.first_instruction_ == this) {
    block_->instructions_.first_instruction_ = next_;
  }
  DCHECK_NE(block_->instructions_.last_instruction_, this);

  previous_ = cursor->previous_;
  if (previous_ != nullptr) {
    previous_->next_ = this;
  }
  next_ = cursor;
  cursor->previous_ = this;
  block_ = cursor->block_;

  if (block_->instructions_.first_instruction_ == cursor) {
    block_->instructions_.first_instruction_ = this;
  }
}

HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) {
  DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented";
  DCHECK_EQ(cursor->GetBlock(), this);

  HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc());
  new_block->instructions_.first_instruction_ = cursor;
  new_block->instructions_.last_instruction_ = instructions_.last_instruction_;
  instructions_.last_instruction_ = cursor->previous_;
  if (cursor->previous_ == nullptr) {
    instructions_.first_instruction_ = nullptr;
  } else {
    cursor->previous_->next_ = nullptr;
    cursor->previous_ = nullptr;
  }

  new_block->instructions_.SetBlockOfInstructions(new_block);
  AddInstruction(new (GetGraph()->GetArena()) HGoto());

  for (HBasicBlock* successor : GetSuccessors()) {
    new_block->successors_.push_back(successor);
    successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block;
  }
  successors_.clear();
  AddSuccessor(new_block);

  GetGraph()->AddBlock(new_block);
  return new_block;
}

HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) {
  DCHECK(!cursor->IsControlFlow());
  DCHECK_NE(instructions_.last_instruction_, cursor);
  DCHECK_EQ(cursor->GetBlock(), this);

  HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc());
  new_block->instructions_.first_instruction_ = cursor->GetNext();
  new_block->instructions_.last_instruction_ = instructions_.last_instruction_;
  cursor->next_->previous_ = nullptr;
  cursor->next_ = nullptr;
  instructions_.last_instruction_ = cursor;

  new_block->instructions_.SetBlockOfInstructions(new_block);
  for (HBasicBlock* successor : GetSuccessors()) {
    new_block->successors_.push_back(successor);
    successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block;
  }
  successors_.clear();

  for (HBasicBlock* dominated : GetDominatedBlocks()) {
    dominated->dominator_ = new_block;
    new_block->dominated_blocks_.push_back(dominated);
  }
  dominated_blocks_.clear();
  return new_block;
}

const HTryBoundary* HBasicBlock::ComputeTryEntryOfSuccessors() const {
  if (EndsWithTryBoundary()) {
    HTryBoundary* try_boundary = GetLastInstruction()->AsTryBoundary();
    if (try_boundary->IsEntry()) {
      DCHECK(!IsTryBlock());
      return try_boundary;
    } else {
      DCHECK(IsTryBlock());
      DCHECK(try_catch_information_->GetTryEntry().HasSameExceptionHandlersAs(*try_boundary));
      return nullptr;
    }
  } else if (IsTryBlock()) {
    return &try_catch_information_->GetTryEntry();
  } else {
    return nullptr;
  }
}

static bool HasOnlyOneInstruction(const HBasicBlock& block) {
  return block.GetPhis().IsEmpty()
      && !block.GetInstructions().IsEmpty()
      && block.GetFirstInstruction() == block.GetLastInstruction();
}

bool HBasicBlock::IsSingleGoto() const {
  return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsGoto();
}

bool HBasicBlock::IsSingleTryBoundary() const {
  return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsTryBoundary();
}

bool HBasicBlock::EndsWithControlFlowInstruction() const {
  return !GetInstructions().IsEmpty() && GetLastInstruction()->IsControlFlow();
}

bool HBasicBlock::EndsWithIf() const {
  return !GetInstructions().IsEmpty() && GetLastInstruction()->IsIf();
}

bool HBasicBlock::EndsWithTryBoundary() const {
  return !GetInstructions().IsEmpty() && GetLastInstruction()->IsTryBoundary();
}

bool HBasicBlock::HasSinglePhi() const {
  return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr;
}

bool HTryBoundary::HasSameExceptionHandlersAs(const HTryBoundary& other) const {
  if (GetBlock()->GetSuccessors().size() != other.GetBlock()->GetSuccessors().size()) {
    return false;
  }

  // Exception handlers need to be stored in the same order.
  for (HExceptionHandlerIterator it1(*this), it2(other);
       !it1.Done();
       it1.Advance(), it2.Advance()) {
    DCHECK(!it2.Done());
    if (it1.Current() != it2.Current()) {
      return false;
    }
  }
  return true;
}

size_t HInstructionList::CountSize() const {
  size_t size = 0;
  HInstruction* current = first_instruction_;
  for (; current != nullptr; current = current->GetNext()) {
    size++;
  }
  return size;
}

void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const {
  for (HInstruction* current = first_instruction_;
       current != nullptr;
       current = current->GetNext()) {
    current->SetBlock(block);
  }
}

void HInstructionList::AddAfter(HInstruction* cursor, const HInstructionList& instruction_list) {
  DCHECK(Contains(cursor));
  if (!instruction_list.IsEmpty()) {
    if (cursor == last_instruction_) {
      last_instruction_ = instruction_list.last_instruction_;
    } else {
      cursor->next_->previous_ = instruction_list.last_instruction_;
    }
    instruction_list.last_instruction_->next_ = cursor->next_;
    cursor->next_ = instruction_list.first_instruction_;
    instruction_list.first_instruction_->previous_ = cursor;
  }
}

void HInstructionList::Add(const HInstructionList& instruction_list) {
  if (IsEmpty()) {
    first_instruction_ = instruction_list.first_instruction_;
    last_instruction_ = instruction_list.last_instruction_;
  } else {
    AddAfter(last_instruction_, instruction_list);
  }
}

void HBasicBlock::DisconnectAndDelete() {
  // Dominators must be removed after all the blocks they dominate. This way
  // a loop header is removed last, a requirement for correct loop information
  // iteration.
  DCHECK(dominated_blocks_.empty());

  // Remove the block from all loops it is included in.
  for (HLoopInformationOutwardIterator it(*this); !it.Done(); it.Advance()) {
    HLoopInformation* loop_info = it.Current();
    loop_info->Remove(this);
    if (loop_info->IsBackEdge(*this)) {
      // If this was the last back edge of the loop, we deliberately leave the
      // loop in an inconsistent state and will fail SSAChecker unless the
      // entire loop is removed during the pass.
      loop_info->RemoveBackEdge(this);
    }
  }

  // Disconnect the block from its predecessors and update their control-flow
  // instructions.
  for (HBasicBlock* predecessor : predecessors_) {
    HInstruction* last_instruction = predecessor->GetLastInstruction();
    predecessor->RemoveInstruction(last_instruction);
    predecessor->RemoveSuccessor(this);
    if (predecessor->GetSuccessors().size() == 1u) {
      DCHECK(last_instruction->IsIf());
      predecessor->AddInstruction(new (graph_->GetArena()) HGoto());
    } else {
      // The predecessor has no remaining successors and therefore must be dead.
      // We deliberately leave it without a control-flow instruction so that the
      // SSAChecker fails unless it is not removed during the pass too.
      DCHECK_EQ(predecessor->GetSuccessors().size(), 0u);
    }
  }
  predecessors_.clear();

  // Disconnect the block from its successors and update their phis.
  for (HBasicBlock* successor : successors_) {
    // Delete this block from the list of predecessors.
    size_t this_index = successor->GetPredecessorIndexOf(this);
    successor->predecessors_.erase(successor->predecessors_.begin() + this_index);

    // Check that `successor` has other predecessors, otherwise `this` is the
    // dominator of `successor` which violates the order DCHECKed at the top.
    DCHECK(!successor->predecessors_.empty());

    // Remove this block's entries in the successor's phis.
    if (successor->predecessors_.size() == 1u) {
      // The successor has just one predecessor left. Replace phis with the only
      // remaining input.
      for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
        HPhi* phi = phi_it.Current()->AsPhi();
        phi->ReplaceWith(phi->InputAt(1 - this_index));
        successor->RemovePhi(phi);
      }
    } else {
      for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
        phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
      }
    }
  }
  successors_.clear();

  // Disconnect from the dominator.
  dominator_->RemoveDominatedBlock(this);
  SetDominator(nullptr);

  // Delete from the graph. The function safely deletes remaining instructions
  // and updates the reverse post order.
  graph_->DeleteDeadBlock(this);
  SetGraph(nullptr);
}

void HBasicBlock::MergeWith(HBasicBlock* other) {
  DCHECK_EQ(GetGraph(), other->GetGraph());
  DCHECK(ContainsElement(dominated_blocks_, other));
  DCHECK_EQ(GetSingleSuccessor(), other);
  DCHECK_EQ(other->GetSinglePredecessor(), this);
  DCHECK(other->GetPhis().IsEmpty());

  // Move instructions from `other` to `this`.
  DCHECK(EndsWithControlFlowInstruction());
  RemoveInstruction(GetLastInstruction());
  instructions_.Add(other->GetInstructions());
  other->instructions_.SetBlockOfInstructions(this);
  other->instructions_.Clear();

  // Remove `other` from the loops it is included in.
  for (HLoopInformationOutwardIterator it(*other); !it.Done(); it.Advance()) {
    HLoopInformation* loop_info = it.Current();
    loop_info->Remove(other);
    if (loop_info->IsBackEdge(*other)) {
      loop_info->ReplaceBackEdge(other, this);
    }
  }

  // Update links to the successors of `other`.
  successors_.clear();
  while (!other->successors_.empty()) {
    HBasicBlock* successor = other->GetSuccessor(0);
    successor->ReplacePredecessor(other, this);
  }

  // Update the dominator tree.
  RemoveDominatedBlock(other);
  for (HBasicBlock* dominated : other->GetDominatedBlocks()) {
    dominated_blocks_.push_back(dominated);
    dominated->SetDominator(this);
  }
  other->dominated_blocks_.clear();
  other->dominator_ = nullptr;

  // Clear the list of predecessors of `other` in preparation of deleting it.
  other->predecessors_.clear();

  // Delete `other` from the graph. The function updates reverse post order.
  graph_->DeleteDeadBlock(other);
  other->SetGraph(nullptr);
}

void HBasicBlock::MergeWithInlined(HBasicBlock* other) {
  DCHECK_NE(GetGraph(), other->GetGraph());
  DCHECK(GetDominatedBlocks().empty());
  DCHECK(GetSuccessors().empty());
  DCHECK(!EndsWithControlFlowInstruction());
  DCHECK(other->GetSinglePredecessor()->IsEntryBlock());
  DCHECK(other->GetPhis().IsEmpty());
  DCHECK(!other->IsInLoop());

  // Move instructions from `other` to `this`.
  instructions_.Add(other->GetInstructions());
  other->instructions_.SetBlockOfInstructions(this);

  // Update links to the successors of `other`.
  successors_.clear();
  while (!other->successors_.empty()) {
    HBasicBlock* successor = other->GetSuccessor(0);
    successor->ReplacePredecessor(other, this);
  }

  // Update the dominator tree.
  for (HBasicBlock* dominated : other->GetDominatedBlocks()) {
    dominated_blocks_.push_back(dominated);
    dominated->SetDominator(this);
  }
  other->dominated_blocks_.clear();
  other->dominator_ = nullptr;
  other->graph_ = nullptr;
}

void HBasicBlock::ReplaceWith(HBasicBlock* other) {
  while (!GetPredecessors().empty()) {
    HBasicBlock* predecessor = GetPredecessor(0);
    predecessor->ReplaceSuccessor(this, other);
  }
  while (!GetSuccessors().empty()) {
    HBasicBlock* successor = GetSuccessor(0);
    successor->ReplacePredecessor(this, other);
  }
  for (HBasicBlock* dominated : GetDominatedBlocks()) {
    other->AddDominatedBlock(dominated);
  }
  GetDominator()->ReplaceDominatedBlock(this, other);
  other->SetDominator(GetDominator());
  dominator_ = nullptr;
  graph_ = nullptr;
}

// Create space in `blocks` for adding `number_of_new_blocks` entries
// starting at location `at`. Blocks after `at` are moved accordingly.
static void MakeRoomFor(GrowableArray<HBasicBlock*>* blocks,
                        size_t number_of_new_blocks,
                        size_t at) {
  size_t old_size = blocks->Size();
  size_t new_size = old_size + number_of_new_blocks;
  blocks->SetSize(new_size);
  for (size_t i = old_size - 1, j = new_size - 1; i > at; --i, --j) {
    blocks->Put(j, blocks->Get(i));
  }
}

void HGraph::DeleteDeadBlock(HBasicBlock* block) {
  DCHECK_EQ(block->GetGraph(), this);
  DCHECK(block->GetSuccessors().empty());
  DCHECK(block->GetPredecessors().empty());
  DCHECK(block->GetDominatedBlocks().empty());
  DCHECK(block->GetDominator() == nullptr);

  for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
    block->RemoveInstruction(it.Current());
  }
  for (HBackwardInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
    block->RemovePhi(it.Current()->AsPhi());
  }

  if (block->IsExitBlock()) {
    exit_block_ = nullptr;
  }

  reverse_post_order_.Delete(block);
  blocks_.Put(block->GetBlockId(), nullptr);
}

HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
  DCHECK(HasExitBlock()) << "Unimplemented scenario";
  // Update the environments in this graph to have the invoke's environment
  // as parent.
  {
    HReversePostOrderIterator it(*this);
    it.Advance();  // Skip the entry block, we do not need to update the entry's suspend check.
    for (; !it.Done(); it.Advance()) {
      HBasicBlock* block = it.Current();
      for (HInstructionIterator instr_it(block->GetInstructions());
           !instr_it.Done();
           instr_it.Advance()) {
        HInstruction* current = instr_it.Current();
        if (current->NeedsEnvironment()) {
          current->GetEnvironment()->SetAndCopyParentChain(
              outer_graph->GetArena(), invoke->GetEnvironment());
        }
      }
    }
  }
  outer_graph->UpdateMaximumNumberOfOutVRegs(GetMaximumNumberOfOutVRegs());
  if (HasBoundsChecks()) {
    outer_graph->SetHasBoundsChecks(true);
  }

  HInstruction* return_value = nullptr;
  if (GetBlocks().Size() == 3) {
    // Simple case of an entry block, a body block, and an exit block.
    // Put the body block's instruction into `invoke`'s block.
    HBasicBlock* body = GetBlocks().Get(1);
    DCHECK(GetBlocks().Get(0)->IsEntryBlock());
    DCHECK(GetBlocks().Get(2)->IsExitBlock());
    DCHECK(!body->IsExitBlock());
    HInstruction* last = body->GetLastInstruction();

    invoke->GetBlock()->instructions_.AddAfter(invoke, body->GetInstructions());
    body->GetInstructions().SetBlockOfInstructions(invoke->GetBlock());

    // Replace the invoke with the return value of the inlined graph.
    if (last->IsReturn()) {
      return_value = last->InputAt(0);
      invoke->ReplaceWith(return_value);
    } else {
      DCHECK(last->IsReturnVoid());
    }

    invoke->GetBlock()->RemoveInstruction(last);
  } else {
    // Need to inline multiple blocks. We split `invoke`'s block
    // into two blocks, merge the first block of the inlined graph into
    // the first half, and replace the exit block of the inlined graph
    // with the second half.
    ArenaAllocator* allocator = outer_graph->GetArena();
    HBasicBlock* at = invoke->GetBlock();
    HBasicBlock* to = at->SplitAfter(invoke);

    HBasicBlock* first = entry_block_->GetSuccessor(0);
    DCHECK(!first->IsInLoop());
    at->MergeWithInlined(first);
    exit_block_->ReplaceWith(to);

    // Update all predecessors of the exit block (now the `to` block)
    // to not `HReturn` but `HGoto` instead.
    bool returns_void = to->GetPredecessor(0)->GetLastInstruction()->IsReturnVoid();
    if (to->GetPredecessors().size() == 1) {
      HBasicBlock* predecessor = to->GetPredecessor(0);
      HInstruction* last = predecessor->GetLastInstruction();
      if (!returns_void) {
        return_value = last->InputAt(0);
      }
      predecessor->AddInstruction(new (allocator) HGoto());
      predecessor->RemoveInstruction(last);
    } else {
      if (!returns_void) {
        // There will be multiple returns.
        return_value = new (allocator) HPhi(
            allocator, kNoRegNumber, 0, HPhi::ToPhiType(invoke->GetType()));
        to->AddPhi(return_value->AsPhi());
      }
      for (HBasicBlock* predecessor : to->GetPredecessors()) {
        HInstruction* last = predecessor->GetLastInstruction();
        if (!returns_void) {
          return_value->AsPhi()->AddInput(last->InputAt(0));
        }
        predecessor->AddInstruction(new (allocator) HGoto());
        predecessor->RemoveInstruction(last);
      }
    }

    if (return_value != nullptr) {
      invoke->ReplaceWith(return_value);
    }

    // Update the meta information surrounding blocks:
    // (1) the graph they are now in,
    // (2) the reverse post order of that graph,
    // (3) the potential loop information they are now in.

    // We don't add the entry block, the exit block, and the first block, which
    // has been merged with `at`.
    static constexpr int kNumberOfSkippedBlocksInCallee = 3;

    // We add the `to` block.
    static constexpr int kNumberOfNewBlocksInCaller = 1;
    size_t blocks_added = (reverse_post_order_.Size() - kNumberOfSkippedBlocksInCallee)
        + kNumberOfNewBlocksInCaller;

    // Find the location of `at` in the outer graph's reverse post order. The new
    // blocks will be added after it.
    size_t index_of_at = 0;
    while (outer_graph->reverse_post_order_.Get(index_of_at) != at) {
      index_of_at++;
    }
    MakeRoomFor(&outer_graph->reverse_post_order_, blocks_added, index_of_at);

    // Do a reverse post order of the blocks in the callee and do (1), (2),
    // and (3) to the blocks that apply.
    HLoopInformation* info = at->GetLoopInformation();
    for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
      HBasicBlock* current = it.Current();
      if (current != exit_block_ && current != entry_block_ && current != first) {
        DCHECK(!current->IsInLoop());
        DCHECK(current->GetGraph() == this);
        current->SetGraph(outer_graph);
        outer_graph->AddBlock(current);
        outer_graph->reverse_post_order_.Put(++index_of_at, current);
        if (info != nullptr) {
          current->SetLoopInformation(info);
          for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) {
            loop_it.Current()->Add(current);
          }
        }
      }
    }

    // Do (1), (2), and (3) to `to`.
    to->SetGraph(outer_graph);
    outer_graph->AddBlock(to);
    outer_graph->reverse_post_order_.Put(++index_of_at, to);
    if (info != nullptr) {
      to->SetLoopInformation(info);
      for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) {
        loop_it.Current()->Add(to);
      }
      if (info->IsBackEdge(*at)) {
        // Only `to` can become a back edge, as the inlined blocks
        // are predecessors of `to`.
        info->ReplaceBackEdge(at, to);
      }
    }
  }

  // Update the next instruction id of the outer graph, so that instructions
  // added later get bigger ids than those in the inner graph.
  outer_graph->SetCurrentInstructionId(GetNextInstructionId());

  // Walk over the entry block and:
  // - Move constants from the entry block to the outer_graph's entry block,
  // - Replace HParameterValue instructions with their real value.
  // - Remove suspend checks, that hold an environment.
  // We must do this after the other blocks have been inlined, otherwise ids of
  // constants could overlap with the inner graph.
  size_t parameter_index = 0;
  for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) {
    HInstruction* current = it.Current();
    if (current->IsNullConstant()) {
      current->ReplaceWith(outer_graph->GetNullConstant());
    } else if (current->IsIntConstant()) {
      current->ReplaceWith(outer_graph->GetIntConstant(current->AsIntConstant()->GetValue()));
    } else if (current->IsLongConstant()) {
      current->ReplaceWith(outer_graph->GetLongConstant(current->AsLongConstant()->GetValue()));
    } else if (current->IsFloatConstant()) {
      current->ReplaceWith(outer_graph->GetFloatConstant(current->AsFloatConstant()->GetValue()));
    } else if (current->IsDoubleConstant()) {
      current->ReplaceWith(outer_graph->GetDoubleConstant(current->AsDoubleConstant()->GetValue()));
    } else if (current->IsParameterValue()) {
      if (kIsDebugBuild
          && invoke->IsInvokeStaticOrDirect()
          && invoke->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()) {
        // Ensure we do not use the last input of `invoke`, as it
        // contains a clinit check which is not an actual argument.
        size_t last_input_index = invoke->InputCount() - 1;
        DCHECK(parameter_index != last_input_index);
      }
      current->ReplaceWith(invoke->InputAt(parameter_index++));
    } else if (current->IsCurrentMethod()) {
      current->ReplaceWith(outer_graph->GetCurrentMethod());
    } else {
      DCHECK(current->IsGoto() || current->IsSuspendCheck());
      entry_block_->RemoveInstruction(current);
    }
  }

  // Finally remove the invoke from the caller.
  invoke->GetBlock()->RemoveInstruction(invoke);

  return return_value;
}

/*
 * Loop will be transformed to:
 *       old_pre_header
 *             |
 *          if_block
 *           /    \
 *  dummy_block   deopt_block
 *           \    /
 *       new_pre_header
 *             |
 *           header
 */
void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) {
  DCHECK(header->IsLoopHeader());
  HBasicBlock* pre_header = header->GetDominator();

  // Need this to avoid critical edge.
  HBasicBlock* if_block = new (arena_) HBasicBlock(this, header->GetDexPc());
  // Need this to avoid critical edge.
  HBasicBlock* dummy_block = new (arena_) HBasicBlock(this, header->GetDexPc());
  HBasicBlock* deopt_block = new (arena_) HBasicBlock(this, header->GetDexPc());
  HBasicBlock* new_pre_header = new (arena_) HBasicBlock(this, header->GetDexPc());
  AddBlock(if_block);
  AddBlock(dummy_block);
  AddBlock(deopt_block);
  AddBlock(new_pre_header);

  header->ReplacePredecessor(pre_header, new_pre_header);
  pre_header->successors_.clear();
  pre_header->dominated_blocks_.clear();

  pre_header->AddSuccessor(if_block);
  if_block->AddSuccessor(dummy_block);  // True successor
  if_block->AddSuccessor(deopt_block);  // False successor
  dummy_block->AddSuccessor(new_pre_header);
  deopt_block->AddSuccessor(new_pre_header);

  pre_header->dominated_blocks_.push_back(if_block);
  if_block->SetDominator(pre_header);
  if_block->dominated_blocks_.push_back(dummy_block);
  dummy_block->SetDominator(if_block);
  if_block->dominated_blocks_.push_back(deopt_block);
  deopt_block->SetDominator(if_block);
  if_block->dominated_blocks_.push_back(new_pre_header);
  new_pre_header->SetDominator(if_block);
  new_pre_header->dominated_blocks_.push_back(header);
  header->SetDominator(new_pre_header);

  size_t index_of_header = 0;
  while (reverse_post_order_.Get(index_of_header) != header) {
    index_of_header++;
  }
  MakeRoomFor(&reverse_post_order_, 4, index_of_header - 1);
  reverse_post_order_.Put(index_of_header++, if_block);
  reverse_post_order_.Put(index_of_header++, dummy_block);
  reverse_post_order_.Put(index_of_header++, deopt_block);
  reverse_post_order_.Put(index_of_header++, new_pre_header);

  HLoopInformation* info = pre_header->GetLoopInformation();
  if (info != nullptr) {
    if_block->SetLoopInformation(info);
    dummy_block->SetLoopInformation(info);
    deopt_block->SetLoopInformation(info);
    new_pre_header->SetLoopInformation(info);
    for (HLoopInformationOutwardIterator loop_it(*pre_header);
         !loop_it.Done();
         loop_it.Advance()) {
      loop_it.Current()->Add(if_block);
      loop_it.Current()->Add(dummy_block);
      loop_it.Current()->Add(deopt_block);
      loop_it.Current()->Add(new_pre_header);
    }
  }
}

void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) {
  if (kIsDebugBuild) {
    DCHECK_EQ(GetType(), Primitive::kPrimNot);
    ScopedObjectAccess soa(Thread::Current());
    DCHECK(rti.IsValid()) << "Invalid RTI for " << DebugName();
    if (IsBoundType()) {
      // Having the test here spares us from making the method virtual just for
      // the sake of a DCHECK.
      ReferenceTypeInfo upper_bound_rti = AsBoundType()->GetUpperBound();
      DCHECK(upper_bound_rti.IsSupertypeOf(rti))
          << " upper_bound_rti: " << upper_bound_rti
          << " rti: " << rti;
      DCHECK(!upper_bound_rti.GetTypeHandle()->IsFinal() || rti.IsExact());
    }
  }
  reference_type_info_ = rti;
}

ReferenceTypeInfo::ReferenceTypeInfo() : type_handle_(TypeHandle()), is_exact_(false) {}

ReferenceTypeInfo::ReferenceTypeInfo(TypeHandle type_handle, bool is_exact)
    : type_handle_(type_handle), is_exact_(is_exact) {
  if (kIsDebugBuild) {
    ScopedObjectAccess soa(Thread::Current());
    DCHECK(IsValidHandle(type_handle));
  }
}

std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) {
  ScopedObjectAccess soa(Thread::Current());
  os << "["
     << " is_valid=" << rhs.IsValid()
     << " type=" << (!rhs.IsValid() ? "?" : PrettyClass(rhs.GetTypeHandle().Get()))
     << " is_exact=" << rhs.IsExact()
     << " ]";
  return os;
}

bool HInstruction::HasAnyEnvironmentUseBefore(HInstruction* other) {
  // For now, assume that instructions in different blocks may use the
  // environment.
  // TODO: Use the control flow to decide if this is true.
  if (GetBlock() != other->GetBlock()) {
    return true;
  }

  // We know that we are in the same block. Walk from 'this' to 'other',
  // checking to see if there is any instruction with an environment.
  HInstruction* current = this;
  for (; current != other && current != nullptr; current = current->GetNext()) {
    // This is a conservative check, as the instruction result may not be in
    // the referenced environment.
    if (current->HasEnvironment()) {
      return true;
    }
  }

  // We should have been called with 'this' before 'other' in the block.
  // Just confirm this.
  DCHECK(current != nullptr);
  return false;
}

void HInstruction::RemoveEnvironmentUsers() {
  for (HUseIterator<HEnvironment*> use_it(GetEnvUses()); !use_it.Done(); use_it.Advance()) {
    HUseListNode<HEnvironment*>* user_node = use_it.Current();
    HEnvironment* user = user_node->GetUser();
    user->SetRawEnvAt(user_node->GetIndex(), nullptr);
  }
  env_uses_.Clear();
}

}  // namespace art