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

#include "com_android_art_rw_flags.h"
#include "common_dominator.h"
#include "optimizing/nodes.h"
#include "reference_type_propagation.h"

namespace art HIDDEN {

static constexpr size_t kMaxInstructionsInBranch = 1u;

HControlFlowSimplifier::HControlFlowSimplifier(HGraph* graph,
                                               OptimizingCompilerStats* stats,
                                               const char* name)
    : HOptimization(graph, name, stats) {
}

bool HControlFlowSimplifier::ReturnSinking() {
  HBasicBlock* exit = graph_->GetExitBlock();
  if (exit == nullptr) {
    return false;  // No exit block, only infinite loop(s).
  }

  size_t number_of_returns = 0u;
  bool saw_return = false;
  for (HBasicBlock* pred : exit->GetPredecessors()) {
    // TODO(solanes): We might have Return/ReturnVoid->TryBoundary->Exit. We can theoretically
    // handle them and move them out of the TryBoundary. However, it is a border case and it adds
    // codebase complexity.
    if (pred->GetLastInstruction()->IsReturn() || pred->GetLastInstruction()->IsReturnVoid()) {
      DCHECK(!pred->IsInLoop());  // Return can be in a loop only if it's in a try-block.
      saw_return |= pred->GetLastInstruction()->IsReturn();
      ++number_of_returns;
    }
  }

  if (number_of_returns < 2) {
    // Nothing to do.
    return false;
  }

  // `new_block` will coalesce the Return instructions into Phi+Return,
  // or the ReturnVoid instructions into a ReturnVoid.
  HBasicBlock* new_block = nullptr;
  HInstruction::InstructionKind return_kind =
      saw_return ? HInstruction::kReturn : HInstruction::kReturnVoid;
  HReturn* first_return = nullptr;  // The first `HReturn` shall be reused by the new block.
  HPhi* new_phi = nullptr;
  size_t new_phi_input_index = 0u;
  ArrayRef<HBasicBlock* const> rpo(graph_->GetReversePostOrder());
  size_t rpo_insert_index = 0u;
  for (size_t rpo_index : Range(rpo.size())) {
    HBasicBlock* pred = rpo[rpo_index];
    HInstruction* last_inst = pred->GetLastInstruction();
    DCHECK_IMPLIES(last_inst == nullptr, pred == exit);
    if (last_inst == nullptr ||                 // Exit block?
        last_inst->GetKind() != return_kind ||  // Not `HReturn`/`HReturnVoid`?
        pred->GetSingleSuccessor() != exit) {   // Leading to try boundary instead of `exit`?
      continue;
    }
    if (new_block == nullptr) {
      new_block = pred->SplitBefore(last_inst);
      if (saw_return) {
        first_return = last_inst->AsReturn();
        // Create the `new_phi`. We do it here since we need to know the type to assign to it.
        new_phi = new (graph_->GetAllocator()) HPhi(
            graph_->GetAllocator(),
            kNoRegNumber,
            /*number_of_inputs=*/ number_of_returns,
            DataType::Kind(first_return->InputAt(0)->GetType()));
        new_phi->SetRawInputAt(new_phi_input_index, first_return->InputAt(0));
        ++new_phi_input_index;
      }
    } else {
      pred->ReplaceSuccessor(exit, new_block);
      if (saw_return) {
        DCHECK(new_phi != nullptr);
        new_phi->SetRawInputAt(new_phi_input_index, last_inst->AsReturn()->InputAt(0));
        ++new_phi_input_index;
      }
      pred->ReplaceAndRemoveInstructionWith(
          last_inst, new (graph_->GetAllocator()) HGoto(last_inst->GetDexPc()));
    }
    rpo_insert_index = rpo_index + 1u;
  }
  if (saw_return) {
    DCHECK_EQ(number_of_returns, new_phi_input_index);
    DCHECK(new_phi != nullptr);
    new_block->AddPhi(new_phi);
    DCHECK(first_return != nullptr);
    first_return->ReplaceInput(new_phi, 0);
  }

  graph_->reverse_post_order_.insert(graph_->reverse_post_order_.begin() + rpo_insert_index,
                                     new_block);
  if (exit->GetPredecessors().size() == 1u) {
    HBasicBlock* dominator = exit->GetDominator();
    dominator->RemoveDominatedBlock(exit);
    new_block->SetDominator(dominator);
    dominator->AddDominatedBlock(new_block);
    exit->SetDominator(new_block);
    new_block->AddDominatedBlock(exit);
  } else {
    ArrayRef<HBasicBlock* const> predecessors(new_block->GetPredecessors());
    CommonDominator dominator(predecessors[0]);
    for (HBasicBlock* pred : predecessors.SubArray(/*pos=*/ 1u)) {
      dominator.Update(pred);
    }
    new_block->SetDominator(dominator.Get());
    dominator.Get()->AddDominatedBlock(new_block);
  }
  return true;
}

bool HControlFlowSimplifier::TrySimplifyPackedSwitch(HBasicBlock* block,
                                                     ScopedArenaAllocator* allocator) {
  DCHECK(!block->GetInstructions().IsEmpty());
  DCHECK(block->GetLastInstruction()->IsPackedSwitch());
  HPackedSwitch* packed_switch = block->GetLastInstruction()->AsPackedSwitch();

  // Defensively check if we have at least 4 entries. This should be true as long as we build
  // a decision tree for smaller switches, see `DexSwitchTable::ShouldBuildDecisionTree()`.
  static constexpr size_t kMinEntries = 4u;
  size_t num_entries = packed_switch->GetNumEntries();
  if (num_entries < kMinEntries) {
    return false;
  }

  // Check if all non-default successors are single-goto blocks merging at the same block.
  ArrayRef<HBasicBlock* const> successors(block->GetSuccessors());
  DCHECK_EQ(num_entries + 1u, successors.size());
  if (!successors[0]->IsSingleGoto()) {
    return false;
  }
  HBasicBlock* merge = successors[0]->GetSingleSuccessor();
  for (size_t i : Range(1, num_entries)) {
    if (!successors[i]->IsSingleGoto() || successors[i]->GetSingleSuccessor() != merge) {
      return false;
    }
  }

  // Check if the `merge` has at most one Phi.
  HPhi* phi = nullptr;
  if (merge->GetPhis().IsEmpty()) {
    // We won't even need a constant table load to simplify this.
  } else if (merge->HasSinglePhi()) {
    phi = merge->GetFirstPhi()->AsPhi();
    DCHECK(phi != nullptr);
  } else {
    return false;  // Do not simplify when there are two or more phis.
  }

  auto get_value = [](HInstruction* input, int64_t* value) {
    if (input->IsIntConstant()) {
      *value = input->AsIntConstant()->GetValue();
    } else if (input->IsLongConstant()) {
      *value = input->AsLongConstant()->GetValue();
    } else if (input->IsFloatConstant()) {
      *value = input->AsFloatConstant()->GetValueAsUint64();
    } else if (input->IsDoubleConstant()) {
      *value = input->AsDoubleConstant()->GetValueAsUint64();
    } else {
      return false;
    }
    return true;
  };

  // Check if the default case can be included in the simplified pattern.
  HBasicBlock* default_block = successors[num_entries];
  int64_t default_value = 0;
  bool with_default =
      default_block->IsSingleGoto() &&
      default_block->GetSingleSuccessor() == merge &&
      (phi == nullptr || get_value(phi->InputAt(merge->GetPredecessorIndexOf(default_block)),
                                   &default_value));
  bool with_default_index_0 = with_default && packed_switch->GetStartValue() == 1;

  ArrayRef<int64_t> entries;
  if (phi != nullptr) {
    // Check if all the phi's non-default inputs are constants and collect the values.
    size_t size = num_entries + (with_default ? 1u : 0u);
    entries = ArrayRef<int64_t>(
        allocator->AllocArray<int64_t>(size, kArenaAllocControlFlowSimplifier), size);
    ArrayRef<int64_t> non_default_entries =
        entries.SubArray(with_default_index_0 ? 1u : 0u, num_entries);
    for (size_t i : Range(num_entries)) {
      size_t predecessor_index = merge->GetPredecessorIndexOf(successors[i]);
      if (!get_value(phi->InputAt(predecessor_index), &non_default_entries[i])) {
        return false;
      }
    }
    if (with_default) {
      entries[with_default_index_0 ? 0u : num_entries] = default_value;
    }
  }

  // Determine table type.
  DataType::Type table_type = (phi != nullptr) ? phi->GetType() : DataType::Type::kVoid;
  if (DataType::Kind(table_type) == DataType::Type::kInt32) {
    // Try to narrow down the type to save space.
    auto [min_it, max_it] = std::minmax_element(entries.begin(), entries.end());
    DCHECK_GE(*min_it, std::numeric_limits<int32_t>::min());
    DCHECK_LE(*max_it, std::numeric_limits<int32_t>::max());
    bool has_negative = (*min_it < 0);
    int max_value_to_encode = has_negative
        ? dchecked_integral_cast<int32_t>(std::max(*max_it, -1 - *min_it))
        : dchecked_integral_cast<int32_t>(*max_it);
    if (!has_negative && max_value_to_encode <= 1) {
      table_type = DataType::Type::kBool;
    } else if (max_value_to_encode <= std::numeric_limits<int8_t>::max()) {
      table_type = DataType::Type::kInt8;
    } else if (!has_negative && max_value_to_encode <= std::numeric_limits<uint8_t>::max()) {
      table_type = DataType::Type::kUint8;
    } else if (max_value_to_encode <= std::numeric_limits<int16_t>::max()) {
      table_type = DataType::Type::kInt16;
    } else if (!has_negative && max_value_to_encode <= std::numeric_limits<uint16_t>::max()) {
      table_type = DataType::Type::kUint16;
    } else {
      DCHECK_EQ(table_type, DataType::Type::kInt32);  // Keep the `kInt32`.
    }
  }

  // Prepare the index calculation.
  uint32_t dex_pc = packed_switch->GetDexPc();
  HInstruction* index = packed_switch->InputAt(0);
  if (packed_switch->GetStartValue() != 0 && !with_default_index_0) {
    HInstruction* addend = graph_->GetIntConstant(-packed_switch->GetStartValue());
    index = new (graph_->GetAllocator()) HAdd(DataType::Type::kInt32, index, addend, dex_pc);
    block->InsertInstructionBefore(index, packed_switch);
  }
  // Prepare the comparison with the upper bound.
  HInstruction* bound = graph_->GetIntConstant(num_entries + (with_default_index_0 ? 1 : 0));
  HBelow* below = new (graph_->GetAllocator()) HBelow(index, bound, dex_pc);
  block->InsertInstructionBefore(below, packed_switch);
  if (with_default) {
    // Insert `HSelect` to clamp the index.
    HInstruction* false_value = graph_->GetIntConstant(with_default_index_0 ? 0 : num_entries);
    index = new (graph_->GetAllocator()) HSelect(below, index, false_value, dex_pc);
    block->InsertInstructionBefore(index, packed_switch);
  }
  if (phi != nullptr) {
    // Insert constant table load and update the phi input we intend to keep.
    HLoadConstantTableEntry* load = new (graph_->GetAllocator()) HLoadConstantTableEntry(
        table_type, index, ArrayRef<const int64_t>(entries), graph_->GetAllocator(), dex_pc);
    if (with_default) {
      block->InsertInstructionBefore(load, packed_switch);
    } else {
      successors[0]->InsertInstructionBefore(load, successors[0]->GetFirstInstruction());
    }
    phi->ReplaceInput(load, merge->GetPredecessorIndexOf(successors[0]));
  }
  // Remove the default successor if `with_default` and all non-default successors,
  // except the first. This also removes `phi` inputs and replaces the Phi with the
  // `load` if it's the only remaining input.
  // Note: Stop using `successors` as the underlying vector is being modified.
  for (size_t i : Range(with_default ? 0u : 1u, num_entries)) {
    block->GetSuccessors()[num_entries - i]->DisconnectAndDelete();
  }
  // If the merge block has only one predecessor now, update domination info and merge.
  if (merge->GetPredecessors().size() == 1u) {
    HBasicBlock* remaining_block = block->GetSuccessors()[0];
    DCHECK(remaining_block == merge->GetSinglePredecessor());
    DCHECK(merge->GetDominator() == block);
    block->RemoveDominatedBlock(merge);
    merge->SetDominator(remaining_block);
    remaining_block->AddDominatedBlock(merge);
    remaining_block->MergeWith(merge);
  }
  if (with_default) {
    // Merge `block` with its remaining successor.
    DCHECK(block->GetLastInstruction()->IsGoto());  // Updated by last `DisconnectAndDelete()`.
    block->MergeWith(block->GetSingleSuccessor());
  } else {
    // Replace the switch with `HBelow` and `HIf`.
    DCHECK_EQ(2u, block->GetSuccessors().size());
    HIf* if_ = new (graph_->GetAllocator()) HIf(below, dex_pc);
    block->ReplaceAndRemoveInstructionWith(packed_switch, if_);
  }

  MaybeRecordStat(stats_, MethodCompilationStat::kControlFlowSwitchSimplified);
  return true;
}

// Returns true if `block` has only one predecessor, ends with a Goto
// or a Return and contains at most `kMaxInstructionsInBranch` other
// movable instruction with no side-effects.
static bool IsSimpleBlock(HBasicBlock* block) {
  if (block->GetPredecessors().size() != 1u) {
    return false;
  }
  DCHECK(block->GetPhis().IsEmpty());

  size_t num_instructions = 0u;
  for (HInstructionIteratorPrefetchNext it(block->GetInstructions()); !it.Done(); it.Advance()) {
    HInstruction* instruction = it.Current();
    if (instruction->IsControlFlow()) {
      return instruction->IsGoto() || instruction->IsReturn();
    } else if (instruction->CanBeMoved() &&
               !instruction->HasSideEffects() &&
               !instruction->CanThrow()) {
      if (instruction->IsSelect() && instruction->AsSelect()->GetCondition()->GetBlock() == block) {
        // Count one HCondition and HSelect in the same block as a single instruction.
        // This enables finding nested selects.
        continue;
      } else if (++num_instructions > kMaxInstructionsInBranch) {
        return false;  // bail as soon as we exceed number of allowed instructions
      }
    } else {
      return false;
    }
  }

  LOG(FATAL) << "Unreachable";
  UNREACHABLE();
}

// Returns true if 'block1' and 'block2' are empty and merge into the
// same single successor.
static bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) {
  return block1->GetSingleSuccessor() == block2->GetSingleSuccessor();
}

// Search `block` for phis that have different inputs at `index1` and `index2`.
// If none is found, returns `{true, nullptr}`.
// If exactly one such `phi` is found, returns `{true, phi}`.
// Otherwise (if more than one such phi is found), returns `{false, nullptr}`.
static std::pair<bool, HPhi*> HasAtMostOnePhiWithDifferentInputs(HBasicBlock* block,
                                                                 size_t index1,
                                                                 size_t index2) {
  DCHECK_NE(index1, index2);

  HPhi* select_phi = nullptr;
  for (HInstructionIteratorPrefetchNext it(block->GetPhis()); !it.Done(); it.Advance()) {
    HPhi* phi = it.Current()->AsPhi();
    auto&& inputs = phi->GetInputs();
    if (inputs[index1] == inputs[index2]) {
      continue;
    }
    if (select_phi == nullptr) {
      // First phi found.
      select_phi = phi;
    } else {
      // More than one phi found, return null.
      return {false, nullptr};
    }
  }
  return {true, select_phi};
}

bool HControlFlowSimplifier::TryGenerateSelectSimpleDiamondPattern(
    HBasicBlock* block, ScopedArenaSafeMap<HInstruction*, HSelect*>* cache) {
  DCHECK(block->GetLastInstruction()->IsIf());
  HIf* if_instruction = block->GetLastInstruction()->AsIf();
  HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
  HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
  DCHECK_NE(true_block, false_block);

  if (!IsSimpleBlock(true_block) ||
      !IsSimpleBlock(false_block) ||
      !BlocksMergeTogether(true_block, false_block)) {
    return false;
  }
  HBasicBlock* merge_block = true_block->GetSingleSuccessor();

  // If the branches are not empty, move instructions in front of the If.
  // TODO(dbrazdil): This puts an instruction between If and its condition.
  //                 Implement moving of conditions to first users if possible.
  while (!true_block->IsSingleGoto() && !true_block->IsSingleReturn()) {
    HInstruction* instr = true_block->GetFirstInstruction();
    DCHECK(!instr->CanThrow());
    instr->MoveBefore(if_instruction);
  }
  while (!false_block->IsSingleGoto() && !false_block->IsSingleReturn()) {
    HInstruction* instr = false_block->GetFirstInstruction();
    DCHECK(!instr->CanThrow());
    instr->MoveBefore(if_instruction);
  }
  DCHECK(true_block->IsSingleGoto() || true_block->IsSingleReturn());
  DCHECK(false_block->IsSingleGoto() || false_block->IsSingleReturn());

  // Find the resulting true/false values.
  size_t predecessor_index_true = merge_block->GetPredecessorIndexOf(true_block);
  size_t predecessor_index_false = merge_block->GetPredecessorIndexOf(false_block);
  DCHECK_NE(predecessor_index_true, predecessor_index_false);

  bool both_successors_return = true_block->IsSingleReturn() && false_block->IsSingleReturn();
  // TODO(solanes): Extend to support multiple phis? e.g.
  //   int a, b;
  //   if (bool) {
  //     a = 0; b = 1;
  //   } else {
  //     a = 1; b = 2;
  //   }
  //   // use a and b
  bool at_most_one_phi_with_different_inputs = false;
  HPhi* phi = nullptr;
  HInstruction* true_value = nullptr;
  HInstruction* false_value = nullptr;
  if (both_successors_return) {
    // Note: This can create a select with the same then-value and else-value.
    true_value = true_block->GetFirstInstruction()->InputAt(0);
    false_value = false_block->GetFirstInstruction()->InputAt(0);
  } else {
    std::tie(at_most_one_phi_with_different_inputs, phi) = HasAtMostOnePhiWithDifferentInputs(
        merge_block, predecessor_index_true, predecessor_index_false);
    if (!at_most_one_phi_with_different_inputs) {
      return false;
    }
    if (phi != nullptr) {
      true_value = phi->InputAt(predecessor_index_true);
      false_value = phi->InputAt(predecessor_index_false);
    }  // else we don't need to create a `HSelect` at all.
  }
  DCHECK(both_successors_return || at_most_one_phi_with_different_inputs);

  // Create the Select instruction and insert it in front of the If.
  HInstruction* condition = if_instruction->InputAt(0);
  HSelect* select = nullptr;
  if (both_successors_return || phi != nullptr) {
    select = new (graph_->GetAllocator()) HSelect(condition,
                                                  true_value,
                                                  false_value,
                                                  if_instruction->GetDexPc());
    block->InsertInstructionBefore(select, if_instruction);
    if (both_successors_return) {
      if (true_value->GetType() == DataType::Type::kReference) {
        DCHECK(false_value->GetType() == DataType::Type::kReference);
        ReferenceTypePropagation::FixUpSelectType(select, graph_->GetHandleCache());
      }
      false_block->GetFirstInstruction()->ReplaceInput(select, 0);
    } else {
      if (phi->GetType() == DataType::Type::kReference) {
        select->SetReferenceTypeInfoIfValid(phi->GetReferenceTypeInfo());
      }
      phi->ReplaceInput(select, predecessor_index_false);  // We'll remove the true branch below.
    }
  }

  // Remove the true branch which removes the corresponding Phi input if needed.
  // If left only with the false branch, the Phi is automatically removed.
  true_block->DisconnectAndDelete();

  // Merge remaining blocks which are now connected with Goto.
  DCHECK_EQ(block->GetSingleSuccessor(), false_block);
  block->MergeWith(false_block);
  if (!both_successors_return && merge_block->GetPredecessors().size() == 1u) {
    DCHECK_IMPLIES(phi != nullptr, phi->GetBlock() == nullptr);
    DCHECK(merge_block->GetPhis().IsEmpty());
    DCHECK_EQ(block->GetSingleSuccessor(), merge_block);
    block->MergeWith(merge_block);
  }

  MaybeRecordStat(stats_, select != nullptr ? MethodCompilationStat::kControlFlowSelectGenerated
                                            : MethodCompilationStat::kControlFlowDiamondRemoved);

  // Very simple way of finding common subexpressions in the generated HSelect statements
  // (since this runs after GVN). Lookup by condition, and reuse latest one if possible
  // (due to post order, latest select is most likely replacement). If needed, we could
  // improve this by e.g. using the operands in the map as well.
  if (select != nullptr) {
    auto it = cache->find(condition);
    if (it == cache->end()) {
      cache->Put(condition, select);
    } else {
      // Found cached value. See if latest can replace cached in the HIR.
      HSelect* cached_select = it->second;
      DCHECK_EQ(cached_select->GetCondition(), select->GetCondition());
      if (cached_select->GetTrueValue() == select->GetTrueValue() &&
          cached_select->GetFalseValue() == select->GetFalseValue() &&
          select->StrictlyDominates(cached_select)) {
        cached_select->ReplaceWith(select);
        cached_select->GetBlock()->RemoveInstruction(cached_select);
      }
      it->second = select;  // always cache latest
    }
  }

  // No need to update dominance information, as we are simplifying
  // a simple diamond shape, where the join block is merged with the
  // entry block. Any following blocks would have had the join block
  // as a dominator, and `MergeWith` handles changing that to the
  // entry block
  return true;
}

HBasicBlock* HControlFlowSimplifier::TryFixupDoubleDiamondPattern(HBasicBlock* block) {
  DCHECK(block->GetLastInstruction()->IsIf());
  HIf* if_instruction = block->GetLastInstruction()->AsIf();
  HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
  HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
  DCHECK_NE(true_block, false_block);

  // One branch must be a single goto, and the other one the inner if.
  if (true_block->IsSingleGoto() == false_block->IsSingleGoto()) {
    return nullptr;
  }

  HBasicBlock* single_goto = true_block->IsSingleGoto() ? true_block : false_block;
  HBasicBlock* inner_if_block = true_block->IsSingleGoto() ? false_block : true_block;

  // The innner if branch has to be a block with just a comparison and an if.
  if (!inner_if_block->EndsWithIf() ||
      inner_if_block->GetLastInstruction()->AsIf()->InputAt(0) !=
          inner_if_block->GetFirstInstruction() ||
      inner_if_block->GetLastInstruction()->GetPrevious() !=
          inner_if_block->GetFirstInstruction() ||
      !inner_if_block->GetFirstInstruction()->IsCondition()) {
    return nullptr;
  }

  HIf* inner_if_instruction = inner_if_block->GetLastInstruction()->AsIf();
  HBasicBlock* inner_if_true_block = inner_if_instruction->IfTrueSuccessor();
  HBasicBlock* inner_if_false_block = inner_if_instruction->IfFalseSuccessor();
  if (!inner_if_true_block->IsSingleGoto() || !inner_if_false_block->IsSingleGoto()) {
    return nullptr;
  }

  // One must merge into the outer condition and the other must not.
  if (BlocksMergeTogether(single_goto, inner_if_true_block) ==
      BlocksMergeTogether(single_goto, inner_if_false_block)) {
    return nullptr;
  }

  // First merge merges the outer if with one of the inner if branches. The block must be a Phi and
  // a Goto.
  HBasicBlock* first_merge = single_goto->GetSingleSuccessor();
  if (first_merge->GetNumberOfPredecessors() != 2 ||
      first_merge->GetPhis().CountSize() != 1 ||
      !first_merge->GetLastInstruction()->IsGoto() ||
      first_merge->GetFirstInstruction() != first_merge->GetLastInstruction()) {
    return nullptr;
  }

  HPhi* first_phi = first_merge->GetFirstPhi()->AsPhi();

  // Second merge is first_merge and the remainder branch merging. It must be phi + goto, or phi +
  // return. Depending on the first merge, we define the second merge.
  HBasicBlock* merges_into_second_merge =
    BlocksMergeTogether(single_goto, inner_if_true_block)
      ? inner_if_false_block
      : inner_if_true_block;
  if (!BlocksMergeTogether(first_merge, merges_into_second_merge)) {
    return nullptr;
  }

  HBasicBlock* second_merge = merges_into_second_merge->GetSingleSuccessor();
  if (second_merge->GetNumberOfPredecessors() != 2 ||
      second_merge->GetPhis().CountSize() != 1 ||
      !(second_merge->GetLastInstruction()->IsGoto() ||
        second_merge->GetLastInstruction()->IsReturn()) ||
      second_merge->GetFirstInstruction() != second_merge->GetLastInstruction()) {
    return nullptr;
  }

  HPhi* second_phi = second_merge->GetFirstPhi()->AsPhi();
  size_t first_merge_index = second_merge->GetPredecessorIndexOf(first_merge);
  if (second_phi->InputAt(first_merge_index) != first_phi) {
    // The first phi does not merge into the second one. This is an odd case where `first_phi` is
    // dead but hasn't been eliminated from the graph yet.
    // TODO(solanes): We can refactor this method to do:
    //                1) Keep the `second_merge` alive instead of `first_merge`
    //                2) For all `first_phi` instances, fetch the appropriate `first_phi` input
    //                3) For the rest of the inputs, duplicate the value that was already present in
    //                `second_phi`.
    //                When we do this, we can eliminate this `if` case, but it would complicate the
    //                logic of this method.
    return nullptr;
  }

  size_t merges_into_second_merge_index =
      second_merge->GetPredecessorIndexOf(merges_into_second_merge);

  // Merge the phis.
  first_phi->AddInput(second_phi->InputAt(merges_into_second_merge_index));
  merges_into_second_merge->ReplaceSuccessor(second_merge, first_merge);
  second_phi->ReplaceWith(first_phi);
  second_merge->RemovePhi(second_phi);

  // Sort out the new domination before merging the blocks
  DCHECK_EQ(second_merge->GetSinglePredecessor(), first_merge);
  second_merge->GetDominator()->RemoveDominatedBlock(second_merge);
  second_merge->SetDominator(first_merge);
  first_merge->AddDominatedBlock(second_merge);
  first_merge->MergeWith(second_merge);

  // No need to update dominance information. There's a chance that `merges_into_second_merge`
  // doesn't come before `first_merge` but we don't need to fix it since `merges_into_second_merge`
  // will disappear from the graph altogether when doing the follow-up
  // TryGenerateSelectSimpleDiamondPattern.

  return inner_if_block;
}

bool HControlFlowSimplifier::TryFlattenMerge(HBasicBlock* block,
                                             size_t reverse_post_order_index,
                                             BitVectorView<size_t> visited_blocks) {
  DCHECK(block->GetFirstInstruction()->IsGoto());
  DCHECK_EQ(block->GetFirstInstruction(), block->GetLastInstruction());
  HBasicBlock* successor = block->GetSingleSuccessor();
  DCHECK(!graph_->IsExitBlock(successor));  // `HGoto` does not flow to exit block.
  if (block->GetPredecessors().size() < 2u || successor->GetPredecessors().size() < 2u) {
    return false;
  }
  if (block->IsCatchBlock() || successor->IsCatchBlock()) {
    // Phi inputs do not correspond to catch block predecessors. Do not flatten.
    return false;
  }
  if (block->GetLoopInformation() != successor->GetLoopInformation()) {
    // The `block` is a pre-header, including the case when `successor` is an irreducible
    // loop entry that's not actually marked as loop header in the `HLoopInformation`.
    return false;
  }
  if (block->IsInLoop()) {
    // Do not merge if the `block` or the `successor` is a loop header, including irreducible
    // loop entries that are not actually marked as loop header in the `HLoopInformation`.
    // Even for irreducible loops, check for the recorded loop header first.
    HLoopInformation* loop_info = block->GetLoopInformation();
    if (block == loop_info->GetHeader() || successor == loop_info->GetHeader()) {
      return false;
    }
    if (UNLIKELY(loop_info->IsIrreducible())) {
      auto is_loop_header = [loop_info](HBasicBlock* b) {
        DCHECK_EQ(loop_info, b->GetLoopInformation());
        auto&& predecessors = b->GetPredecessors();
        return std::any_of(
            predecessors.begin(),
            predecessors.end(),
            [loop_info](HBasicBlock* p) { return p->GetLoopInformation() != loop_info; });
      };
      if (is_loop_header(block) || is_loop_header(successor)) {
        return false;
      }
    }
  }

  block->TakeGotoBlockSuccessorsOtherPredecessorsAndMergePhis();

  // Fix up domination information for unmerged blocks before calling `MergeWith()`.
  HBasicBlock* dominator = successor->GetDominator();
  if (block->GetDominator() == dominator) {
    dominator->RemoveDominatedBlock(successor);
  } else {
    block->GetDominator()->RemoveDominatedBlock(block);
    block->SetDominator(dominator);
    dominator->ReplaceDominatedBlock(successor, block);
  }
  successor->SetDominator(block);
  block->AddDominatedBlock(successor);

  // Move predecessors before `block` in reverse post order if needed.
  ScopedArenaAllocator allocator(graph_->GetArenaStack());
  BitVectorView<size_t> predecessors_to_move = ArenaBitVector::CreateFixedSize(
      &allocator, graph_->GetBlocks().size(), kArenaAllocControlFlowSimplifier);
  ScopedArenaVector<HBasicBlock*> work_queue(allocator.Adapter(kArenaAllocControlFlowSimplifier));
  auto mark_predecessors = [&](HBasicBlock* current) {
    for (HBasicBlock* predecessor : current->GetPredecessors()) {
      if (visited_blocks.IsBitSet(predecessor->GetBlockId()) &&
          !predecessors_to_move.IsBitSet(predecessor->GetBlockId())) {
        predecessors_to_move.SetBit(predecessor->GetBlockId());
        work_queue.push_back(predecessor);
      }
    }
  };
  mark_predecessors(block);
  if (!work_queue.empty()) {
    do {
      HBasicBlock* current = work_queue.back();
      work_queue.pop_back();
      mark_predecessors(current);
    } while (!work_queue.empty());
    // Move blocks marked in `predecessors_to_move` to the correct position in the reverse
    // post order while extracting `block` and other unmarked blocks to a temporary vector.
    ScopedArenaVector<HBasicBlock*> extracted(allocator.Adapter(kArenaAllocControlFlowSimplifier));
    auto moved_end = graph_->reverse_post_order_.begin() + reverse_post_order_index;
    DCHECK_EQ(block, *moved_end);
    DCHECK(!predecessors_to_move.IsBitSet(block->GetBlockId()));
    extracted.push_back(block);
    auto move_it = std::next(moved_end);
    DCHECK(move_it != graph_->reverse_post_order_.end());
    while (*move_it != successor) {
      if (predecessors_to_move.IsBitSet((*move_it)->GetBlockId())) {
        *moved_end = *move_it;
        ++moved_end;
      } else {
        extracted.push_back(*move_it);
      }
      ++move_it;
      DCHECK(move_it != graph_->reverse_post_order_.end());
    }
    // Place extracted blocks in the freed range in reverse post order.
    DCHECK_EQ(static_cast<size_t>(std::distance(moved_end, move_it)), extracted.size());
    std::copy(extracted.begin(), extracted.end(), moved_end);
  }

  // Finish the merge using `MergeWith()`.
  block->MergeWith(successor);

  MaybeRecordStat(stats_, MethodCompilationStat::kControlFlowFlattenedMerge);
  return true;
}

bool HControlFlowSimplifier::Run() {
  bool simplified = com::android::art::rw::flags::packed_switch_simplification() && ReturnSinking();

  ScopedArenaAllocator allocator(graph_->GetArenaStack());
  // Select cache with local allocator for `TryGenerateSelectSimpleDiamondPattern()`.
  ScopedArenaSafeMap<HInstruction*, HSelect*> select_cache(
      std::less<HInstruction*>(), allocator.Adapter(kArenaAllocControlFlowSimplifier));
  // Mark visited blocks by block id for reverse post order fixup in `TryFlattenMerge()`.
  BitVectorView<size_t> visited_blocks = ArenaBitVector::CreateFixedSize(
      &allocator, graph_->GetBlocks().size(), kArenaAllocControlFlowSimplifier);

  // Iterate in post order in the case that simplifying a block exposes simplification
  // opportunities for earier blocks. Do not process the entry block.
  // We may remove blocks from the reverse post order array, so make the iteration very explicit.
  HBasicBlock* const * reverse_post_order_data = graph_->GetReversePostOrder().data();
  size_t reverse_post_order_index = graph_->GetReversePostOrder().size();
  while (reverse_post_order_index != /* Do not process entry block with index 0. */ 1u) {
    --reverse_post_order_index;
    HBasicBlock* block = reverse_post_order_data[reverse_post_order_index];
    DCHECK(block != nullptr);
    DCHECK(!block->GetInstructions().IsEmpty());
    HInstruction* last_inst = block->GetLastInstruction();
    bool block_may_have_moved_in_rpo = false;
    if (com::android::art::rw::flags::packed_switch_simplification() &&
        last_inst->IsPackedSwitch() &&
        TrySimplifyPackedSwitch(block, &allocator)) {
      simplified = true;
    } else if (com::android::art::rw::flags::packed_switch_simplification() &&
               last_inst->IsGoto() &&
               last_inst == block->GetFirstInstruction() &&
               TryFlattenMerge(block, reverse_post_order_index, visited_blocks)) {
      simplified = true;
      block_may_have_moved_in_rpo = true;
    } else if (last_inst->IsIf()) {
      if (TryGenerateSelectSimpleDiamondPattern(block, &select_cache)) {
        simplified = true;
      } else if (!com::android::art::rw::flags::packed_switch_simplification()) {
        // Note: The `TryFlattenMerge()` simplification above replaces the
        // `TryFixupDoubleDiamondPattern()` here if the flag is enabled.
        // Try to fix up the odd version of the double diamond pattern. If we could do it, it means
        // that we can generate two selects.
        HBasicBlock* inner_if_block = TryFixupDoubleDiamondPattern(block);
        if (inner_if_block != nullptr) {
          // Generate the selects now since `inner_if_block` should be after `block` in PostOrder.
          bool result = TryGenerateSelectSimpleDiamondPattern(inner_if_block, &select_cache);
          DCHECK(result);
          result = TryGenerateSelectSimpleDiamondPattern(block, &select_cache);
          DCHECK(result);
          simplified = true;
        }
      }
    }
    DCHECK_LT(block->GetBlockId(), graph_->GetBlocks().size());
    visited_blocks.SetBit(block->GetBlockId());
    // Blocks with higher indexes may have been removed and the `block` may have been moved
    // further back. Removing from a `std::vector<>` does not change the data pointer.
    DCHECK_EQ(reverse_post_order_data, graph_->GetReversePostOrder().data());
    DCHECK_LT(reverse_post_order_index, graph_->GetReversePostOrder().size());
    if (block_may_have_moved_in_rpo) {
      DCHECK_GE(IndexOfElement(graph_->GetReversePostOrder(), block), reverse_post_order_index);
    } else {
      DCHECK_EQ(block, reverse_post_order_data[reverse_post_order_index]);
    }
  }
  DCHECK_EQ(reverse_post_order_index, 1u);
  DCHECK(graph_->IsEntryBlock(reverse_post_order_data[0u]));

  return simplified;
}

}  // namespace art