// Copyright (c) 2020 Google LLC
//
// 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 "source/fuzz/transformation_merge_function_returns.h"

#include "source/fuzz/comparator_deep_blocks_first.h"
#include "source/fuzz/fuzzer_util.h"

namespace spvtools {
namespace fuzz {

TransformationMergeFunctionReturns::TransformationMergeFunctionReturns(
    protobufs::TransformationMergeFunctionReturns message)
    : message_(std::move(message)) {}

TransformationMergeFunctionReturns::TransformationMergeFunctionReturns(
    uint32_t function_id, uint32_t outer_header_id,
    uint32_t unreachable_continue_id, uint32_t outer_return_id,
    uint32_t return_val_id, uint32_t any_returnable_val_id,
    const std::vector<protobufs::ReturnMergingInfo>& returns_merging_info) {
  message_.set_function_id(function_id);
  message_.set_outer_header_id(outer_header_id);
  message_.set_unreachable_continue_id(unreachable_continue_id);
  message_.set_outer_return_id(outer_return_id);
  message_.set_return_val_id(return_val_id);
  message_.set_any_returnable_val_id(any_returnable_val_id);
  for (const auto& return_merging_info : returns_merging_info) {
    *message_.add_return_merging_info() = return_merging_info;
  }
}

bool TransformationMergeFunctionReturns::IsApplicable(
    opt::IRContext* ir_context,
    const TransformationContext& transformation_context) const {
  auto function = ir_context->GetFunction(message_.function_id());
  // The function must exist.
  if (!function) {
    return false;
  }

  // The entry block must end in an unconditional branch.
  if (function->entry()->terminator()->opcode() != spv::Op::OpBranch) {
    return false;
  }

  // The module must contain an OpConstantTrue instruction.
  if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
                                        true, false)) {
    return false;
  }

  // The module must contain an OpConstantFalse instruction.
  if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
                                        false, false)) {
    return false;
  }

  // Check that the fresh ids provided are fresh and distinct.
  std::set<uint32_t> used_fresh_ids;
  for (uint32_t id :
       {message_.outer_header_id(), message_.unreachable_continue_id(),
        message_.outer_return_id()}) {
    if (!id || !CheckIdIsFreshAndNotUsedByThisTransformation(id, ir_context,
                                                             &used_fresh_ids)) {
      return false;
    }
  }

  // Check the additional fresh id required if the function is not void.
  auto function_type = ir_context->get_type_mgr()->GetType(function->type_id());
  assert(function_type && "The function type should always exist.");

  if (!function_type->AsVoid() &&
      (!message_.return_val_id() ||
       !CheckIdIsFreshAndNotUsedByThisTransformation(
           message_.return_val_id(), ir_context, &used_fresh_ids))) {
    return false;
  }

  // Get a map from the types for which ids are available at the end of the
  // entry block to one of the ids with that type. We compute this here to avoid
  // potentially doing it multiple times later on.
  auto types_to_available_ids =
      GetTypesToIdAvailableAfterEntryBlock(ir_context);

  // Get the reachable return blocks.
  auto return_blocks =
      fuzzerutil::GetReachableReturnBlocks(ir_context, message_.function_id());

  // Map each merge block of loops containing reachable return blocks to the
  // corresponding returning predecessors (all the blocks that, at the end of
  // the transformation, will branch to the merge block because the function is
  // returning).
  std::map<uint32_t, std::set<uint32_t>> merge_blocks_to_returning_preds;
  for (uint32_t block : return_blocks) {
    uint32_t merge_block =
        ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(block);

    while (merge_block != 0) {
      // If we have seen this merge block before, update the corresponding set
      // and break out of the loop.
      if (merge_blocks_to_returning_preds.count(merge_block)) {
        merge_blocks_to_returning_preds[merge_block].emplace(block);
        break;
      }

      // If we have not seen this merge block before, add a new entry and walk
      // up the loop tree.
      merge_blocks_to_returning_preds.emplace(merge_block,
                                              std::set<uint32_t>({block}));

      // Walk up the loop tree.
      block = merge_block;
      merge_block =
          ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(merge_block);
    }
  }

  // Instructions in the relevant merge blocks must be restricted to OpLabel,
  // OpPhi and OpBranch.
  for (const auto& merge_block_entry : merge_blocks_to_returning_preds) {
    uint32_t merge_block = merge_block_entry.first;
    bool all_instructions_allowed =
        ir_context->get_instr_block(merge_block)
            ->WhileEachInst([](opt::Instruction* inst) {
              return inst->opcode() == spv::Op::OpLabel ||
                     inst->opcode() == spv::Op::OpPhi ||
                     inst->opcode() == spv::Op::OpBranch;
            });
    if (!all_instructions_allowed) {
      return false;
    }
  }

  auto merge_blocks_to_info = GetMappingOfMergeBlocksToInfo();

  // For each relevant merge block, check that the correct ids are available.
  for (const auto& merge_block_entry : merge_blocks_to_returning_preds) {
    if (!CheckThatTheCorrectIdsAreGivenForMergeBlock(
            merge_block_entry.first, merge_blocks_to_info,
            types_to_available_ids, function_type->AsVoid(), ir_context,
            transformation_context, &used_fresh_ids)) {
      return false;
    }
  }

  // If the function has a non-void return type, and there are merge loops which
  // contain return instructions, we need to check that either:
  // - |message_.any_returnable_val_id| exists. In this case, it must have the
  //   same type as the return type of the function and be available at the end
  //   of the entry block.
  // - a suitable id, available at the end of the entry block can be found in
  //   the module.
  if (!function_type->AsVoid() && !merge_blocks_to_returning_preds.empty()) {
    auto returnable_val_def =
        ir_context->get_def_use_mgr()->GetDef(message_.any_returnable_val_id());
    if (!returnable_val_def) {
      // Check if a suitable id can be found in the module.
      if (types_to_available_ids.count(function->type_id()) == 0) {
        return false;
      }
    } else if (returnable_val_def->type_id() != function->type_id()) {
      return false;
    } else if (!fuzzerutil::IdIsAvailableBeforeInstruction(
                   ir_context, function->entry()->terminator(),
                   message_.any_returnable_val_id())) {
      // The id must be available at the end of the entry block.
      return false;
    }
  }

  // Check that adding new predecessors to the relevant merge blocks does not
  // render any instructions invalid (each id definition must still dominate
  // each of its uses).
  if (!CheckDefinitionsStillDominateUsesAfterAddingNewPredecessors(
          ir_context, function, merge_blocks_to_returning_preds)) {
    return false;
  }

  return true;
}

void TransformationMergeFunctionReturns::Apply(
    opt::IRContext* ir_context,
    TransformationContext* transformation_context) const {
  auto function = ir_context->GetFunction(message_.function_id());
  auto function_type = ir_context->get_type_mgr()->GetType(function->type_id());

  // Get a map from the types for which ids are available at the end of the
  // entry block to one of the ids with that type. We compute this here to avoid
  // potentially doing it multiple times later on.
  auto types_to_available_ids =
      GetTypesToIdAvailableAfterEntryBlock(ir_context);

  uint32_t bool_type = fuzzerutil::MaybeGetBoolType(ir_context);

  uint32_t constant_true = fuzzerutil::MaybeGetBoolConstant(
      ir_context, *transformation_context, true, false);

  uint32_t constant_false = fuzzerutil::MaybeGetBoolConstant(
      ir_context, *transformation_context, false, false);

  // Get the reachable return blocks.
  auto return_blocks =
      fuzzerutil::GetReachableReturnBlocks(ir_context, message_.function_id());

  // Keep a map from the relevant merge blocks to a mapping from each of the
  // returning predecessors to the corresponding pair (return value,
  // boolean specifying whether the function is returning). Returning
  // predecessors are blocks in the loop (not further nested inside loops),
  // which either return or are merge blocks of nested loops containing return
  // instructions.
  std::map<uint32_t, std::map<uint32_t, std::pair<uint32_t, uint32_t>>>
      merge_blocks_to_returning_predecessors;

  // Initialise the map, mapping each relevant merge block to an empty map.
  for (uint32_t ret_block_id : return_blocks) {
    uint32_t merge_block_id =
        ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(ret_block_id);

    while (merge_block_id != 0 &&
           !merge_blocks_to_returning_predecessors.count(merge_block_id)) {
      merge_blocks_to_returning_predecessors.emplace(
          merge_block_id, std::map<uint32_t, std::pair<uint32_t, uint32_t>>());
      merge_block_id = ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(
          merge_block_id);
    }
  }

  // Get a reference to an instruction with the same type id as the function's
  // return type, if the type of the function is not void and ther are loops
  // containing return instructions.
  uint32_t returnable_val_id = 0;
  if (!function_type->AsVoid() &&
      !merge_blocks_to_returning_predecessors.empty()) {
    // If |message.any_returnable_val_id| can be found in the module, use it.
    // Otherwise, use another suitable id found in the module.
    auto returnable_val_def =
        ir_context->get_def_use_mgr()->GetDef(message_.any_returnable_val_id());
    returnable_val_id = returnable_val_def
                            ? returnable_val_def->result_id()
                            : types_to_available_ids[function->type_id()];
  }

  // Keep a map from all the new predecessors of the merge block of the new
  // outer loop, to the related return value ids.
  std::map<uint32_t, uint32_t> outer_merge_predecessors;

  // Adjust the return blocks and add the related information to the map or
  // |outer_merge_predecessors| set.
  for (uint32_t ret_block_id : return_blocks) {
    auto ret_block = ir_context->get_instr_block(ret_block_id);

    // Get the return value id (if the function is not void).
    uint32_t ret_val_id =
        function_type->AsVoid()
            ? 0
            : ret_block->terminator()->GetSingleWordInOperand(0);

    uint32_t merge_block_id =
        ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(ret_block_id);

    // Add a new entry to the map corresponding to the merge block of the
    // innermost enclosing loop (or that of the new outer loop if there is no
    // enclosing loop).
    if (merge_block_id != 0) {
      merge_blocks_to_returning_predecessors[merge_block_id].emplace(
          ret_block_id,
          std::pair<uint32_t, uint32_t>(ret_val_id, constant_true));
    } else {
      // If there is no enclosing loop, the block will branch to the merge block
      // of the new outer loop.
      merge_block_id = message_.outer_return_id();
      outer_merge_predecessors.emplace(ret_block_id, ret_val_id);
    }

    // Replace the return instruction with an unconditional branch.
    ret_block->terminator()->SetOpcode(spv::Op::OpBranch);
    ret_block->terminator()->SetInOperands(
        {{SPV_OPERAND_TYPE_ID, {merge_block_id}}});
  }

  // Get a list of all the relevant merge blocks.
  std::vector<uint32_t> merge_blocks;
  merge_blocks.reserve(merge_blocks_to_returning_predecessors.size());
  for (const auto& entry : merge_blocks_to_returning_predecessors) {
    merge_blocks.emplace_back(entry.first);
  }

  // Sort the list so that deeper merge blocks come first.
  // We need to consider deeper merge blocks first so that, when a merge block
  // is considered, all the merge blocks enclosed by the corresponding loop have
  // already been considered and, thus, the mapping from this merge block to the
  // returning predecessors is complete.
  std::sort(merge_blocks.begin(), merge_blocks.end(),
            ComparatorDeepBlocksFirst(ir_context));

  auto merge_blocks_to_info = GetMappingOfMergeBlocksToInfo();

  // Adjust the merge blocks and add the related information to the map or
  // |outer_merge_predecessors| set.
  for (uint32_t merge_block_id : merge_blocks) {
    // Get the info corresponding to |merge_block| from the map, if a
    // corresponding entry exists. Otherwise use overflow ids and find suitable
    // ids in the module.
    protobufs::ReturnMergingInfo* info =
        merge_blocks_to_info.count(merge_block_id)
            ? &merge_blocks_to_info[merge_block_id]
            : nullptr;

    uint32_t is_returning_id =
        info ? info->is_returning_id()
             : transformation_context->GetOverflowIdSource()
                   ->GetNextOverflowId();

    uint32_t maybe_return_val_id = 0;
    if (!function_type->AsVoid()) {
      maybe_return_val_id = info ? info->maybe_return_val_id()
                                 : transformation_context->GetOverflowIdSource()
                                       ->GetNextOverflowId();
    }

    // Map from existing OpPhi to overflow ids. If there is no mapping, get an
    // empty map.
    auto phi_to_id = info ? fuzzerutil::RepeatedUInt32PairToMap(
                                *merge_blocks_to_info[merge_block_id]
                                     .mutable_opphi_to_suitable_id())
                          : std::map<uint32_t, uint32_t>();

    // Get a reference to the info related to the returning predecessors.
    const auto& returning_preds =
        merge_blocks_to_returning_predecessors[merge_block_id];

    // Get a set of the original predecessors.
    auto preds_list = ir_context->cfg()->preds(merge_block_id);
    auto preds = std::set<uint32_t>(preds_list.begin(), preds_list.end());

    auto merge_block = ir_context->get_instr_block(merge_block_id);

    // Adjust the existing OpPhi instructions.
    merge_block->ForEachPhiInst(
        [&preds, &returning_preds, &phi_to_id,
         &types_to_available_ids](opt::Instruction* inst) {
          // We need a placeholder value id. If |phi_to_id| contains a mapping
          // for this instruction, we use the given id, otherwise a suitable id
          // for the instruction's type from |types_to_available_ids|.
          uint32_t placeholder_val_id =
              phi_to_id.count(inst->result_id())
                  ? phi_to_id[inst->result_id()]
                  : types_to_available_ids[inst->type_id()];
          assert(placeholder_val_id &&
                 "We should always be able to find a suitable if the "
                 "transformation is applicable.");

          // Add a pair of operands (placeholder id, new predecessor) for each
          // new predecessor of the merge block.
          for (const auto& entry : returning_preds) {
            // A returning predecessor may already be a predecessor of the
            // block. In that case, we should not add new operands.
            // Each entry is in the form (predecessor, {return val, is
            // returning}).
            if (!preds.count(entry.first)) {
              inst->AddOperand({SPV_OPERAND_TYPE_ID, {placeholder_val_id}});
              inst->AddOperand({SPV_OPERAND_TYPE_ID, {entry.first}});
            }
          }
        });

    // If the function is not void, add a new OpPhi instructions to collect the
    // return value from the returning predecessors.
    if (!function_type->AsVoid()) {
      opt::Instruction::OperandList operand_list;

      // Add two operands (return value, predecessor) for each returning
      // predecessor.
      for (auto entry : returning_preds) {
        // Each entry is in the form (predecessor, {return value,
        // is returning}).
        operand_list.emplace_back(
            opt::Operand{SPV_OPERAND_TYPE_ID, {entry.second.first}});
        operand_list.emplace_back(
            opt::Operand{SPV_OPERAND_TYPE_ID, {entry.first}});
      }

      // Add two operands for each original predecessor from which the function
      // does not return.
      for (uint32_t original_pred : preds) {
        // Only add operands if the function cannot be returning from this
        // block.
        if (returning_preds.count(original_pred)) {
          continue;
        }

        operand_list.emplace_back(
            opt::Operand{SPV_OPERAND_TYPE_ID, {returnable_val_id}});
        operand_list.emplace_back(
            opt::Operand{SPV_OPERAND_TYPE_ID, {original_pred}});
      }

      // Insert the instruction.
      merge_block->begin()->InsertBefore(MakeUnique<opt::Instruction>(
          ir_context, spv::Op::OpPhi, function->type_id(), maybe_return_val_id,
          std::move(operand_list)));

      fuzzerutil::UpdateModuleIdBound(ir_context, maybe_return_val_id);
    }

    // Add an OpPhi instruction deciding whether the function is returning.
    {
      opt::Instruction::OperandList operand_list;

      // Add two operands (return value, is returning) for each returning
      // predecessor.
      for (auto entry : returning_preds) {
        // Each entry is in the form (predecessor, {return value,
        // is returning}).
        operand_list.emplace_back(
            opt::Operand{SPV_OPERAND_TYPE_ID, {entry.second.second}});
        operand_list.emplace_back(
            opt::Operand{SPV_OPERAND_TYPE_ID, {entry.first}});
      }

      // Add two operands for each original predecessor from which the function
      // does not return.
      for (uint32_t original_pred : preds) {
        // Only add operands if the function cannot be returning from this
        // block.
        if (returning_preds.count(original_pred)) {
          continue;
        }

        operand_list.emplace_back(
            opt::Operand{SPV_OPERAND_TYPE_ID, {constant_false}});
        operand_list.emplace_back(
            opt::Operand{SPV_OPERAND_TYPE_ID, {original_pred}});
      }

      // Insert the instruction.
      merge_block->begin()->InsertBefore(MakeUnique<opt::Instruction>(
          ir_context, spv::Op::OpPhi, bool_type, is_returning_id,
          std::move(operand_list)));

      fuzzerutil::UpdateModuleIdBound(ir_context, is_returning_id);
    }

    // Change the branching instruction of the block.
    assert(merge_block->terminator()->opcode() == spv::Op::OpBranch &&
           "Each block should branch unconditionally to the next.");

    // Add a new entry to the map corresponding to the merge block of the
    // innermost enclosing loop (or that of the new outer loop if there is no
    // enclosing loop).
    uint32_t enclosing_merge =
        ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(merge_block_id);
    if (enclosing_merge == 0) {
      enclosing_merge = message_.outer_return_id();
      outer_merge_predecessors.emplace(merge_block_id, maybe_return_val_id);
    } else {
      merge_blocks_to_returning_predecessors[enclosing_merge].emplace(
          merge_block_id,
          std::pair<uint32_t, uint32_t>(maybe_return_val_id, is_returning_id));
    }

    // Get the current successor.
    uint32_t original_succ =
        merge_block->terminator()->GetSingleWordInOperand(0);
    // Leave the instruction as it is if the block already branches to the merge
    // block of the enclosing loop.
    if (original_succ == enclosing_merge) {
      continue;
    }

    // The block should branch to |enclosing_merge| if |is_returning_id| is
    // true, to |original_succ| otherwise.
    merge_block->terminator()->SetOpcode(spv::Op::OpBranchConditional);
    merge_block->terminator()->SetInOperands(
        {{SPV_OPERAND_TYPE_ID, {is_returning_id}},
         {SPV_OPERAND_TYPE_ID, {enclosing_merge}},
         {SPV_OPERAND_TYPE_ID, {original_succ}}});
  }

  assert(function->entry()->terminator()->opcode() == spv::Op::OpBranch &&
         "The entry block should branch unconditionally to another block.");
  uint32_t block_after_entry =
      function->entry()->terminator()->GetSingleWordInOperand(0);

  // Create the header for the new outer loop.
  auto outer_loop_header =
      MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
          ir_context, spv::Op::OpLabel, 0, message_.outer_header_id(),
          opt::Instruction::OperandList()));

  fuzzerutil::UpdateModuleIdBound(ir_context, message_.outer_header_id());

  // Add the instruction:
  //   OpLoopMerge %outer_return_id %unreachable_continue_id None
  outer_loop_header->AddInstruction(MakeUnique<opt::Instruction>(
      ir_context, spv::Op::OpLoopMerge, 0, 0,
      opt::Instruction::OperandList{
          {SPV_OPERAND_TYPE_ID, {message_.outer_return_id()}},
          {SPV_OPERAND_TYPE_ID, {message_.unreachable_continue_id()}},
          {SPV_OPERAND_TYPE_LOOP_CONTROL,
           {uint32_t(spv::LoopControlMask::MaskNone)}}}));

  // Add unconditional branch to %block_after_entry.
  outer_loop_header->AddInstruction(MakeUnique<opt::Instruction>(
      ir_context, spv::Op::OpBranch, 0, 0,
      opt::Instruction::OperandList{
          {SPV_OPERAND_TYPE_ID, {block_after_entry}}}));

  // Insert the header right after the entry block.
  function->InsertBasicBlockAfter(std::move(outer_loop_header),
                                  function->entry().get());

  // Update the branching instruction of the entry block.
  function->entry()->terminator()->SetInOperands(
      {{SPV_OPERAND_TYPE_ID, {message_.outer_header_id()}}});

  // If the entry block is referenced in an OpPhi instruction, the header for
  // the new loop should be referenced instead.
  ir_context->get_def_use_mgr()->ForEachUse(
      function->entry()->id(),
      [this](opt::Instruction* use_instruction, uint32_t use_operand_index) {
        if (use_instruction->opcode() == spv::Op::OpPhi) {
          use_instruction->SetOperand(use_operand_index,
                                      {message_.outer_header_id()});
        }
      });

  // Create the merge block for the loop (and return block for the function).
  auto outer_return_block =
      MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
          ir_context, spv::Op::OpLabel, 0, message_.outer_return_id(),
          opt::Instruction::OperandList()));

  fuzzerutil::UpdateModuleIdBound(ir_context, message_.outer_return_id());

  // If the function is not void, insert an instruction to collect the return
  // value from the predecessors and an OpReturnValue instruction.
  if (!function_type->AsVoid()) {
    opt::Instruction::OperandList operand_list;

    // Add two operands (return value, predecessor) for each predecessor.
    for (auto entry : outer_merge_predecessors) {
      // Each entry is in the form (predecessor, return value).
      operand_list.emplace_back(
          opt::Operand{SPV_OPERAND_TYPE_ID, {entry.second}});
      operand_list.emplace_back(
          opt::Operand{SPV_OPERAND_TYPE_ID, {entry.first}});
    }

    // Insert the OpPhi instruction.
    outer_return_block->AddInstruction(MakeUnique<opt::Instruction>(
        ir_context, spv::Op::OpPhi, function->type_id(),
        message_.return_val_id(), std::move(operand_list)));

    fuzzerutil::UpdateModuleIdBound(ir_context, message_.return_val_id());

    // Insert the OpReturnValue instruction.
    outer_return_block->AddInstruction(MakeUnique<opt::Instruction>(
        ir_context, spv::Op::OpReturnValue, 0, 0,
        opt::Instruction::OperandList{
            {SPV_OPERAND_TYPE_ID, {message_.return_val_id()}}}));
  } else {
    // Insert an OpReturn instruction (the function is void).
    outer_return_block->AddInstruction(MakeUnique<opt::Instruction>(
        ir_context, spv::Op::OpReturn, 0, 0, opt::Instruction::OperandList{}));
  }

  // Insert the new return block at the end of the function.
  function->AddBasicBlock(std::move(outer_return_block));

  // Create the unreachable continue block associated with the enclosing loop.
  auto unreachable_continue_block =
      MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
          ir_context, spv::Op::OpLabel, 0, message_.unreachable_continue_id(),
          opt::Instruction::OperandList()));

  fuzzerutil::UpdateModuleIdBound(ir_context,
                                  message_.unreachable_continue_id());

  // Insert an branch back to the loop header, to create a back edge.
  unreachable_continue_block->AddInstruction(MakeUnique<opt::Instruction>(
      ir_context, spv::Op::OpBranch, 0, 0,
      opt::Instruction::OperandList{
          {SPV_OPERAND_TYPE_ID, {message_.outer_header_id()}}}));

  // Insert the unreachable continue block at the end of the function.
  function->AddBasicBlock(std::move(unreachable_continue_block));

  // All analyses must be invalidated because the structure of the module was
  // changed.
  ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
}

std::unordered_set<uint32_t> TransformationMergeFunctionReturns::GetFreshIds()
    const {
  std::unordered_set<uint32_t> result;
  result.emplace(message_.outer_header_id());
  result.emplace(message_.unreachable_continue_id());
  result.emplace(message_.outer_return_id());
  // |message_.return_val_info| can be 0 if the function is void.
  if (message_.return_val_id()) {
    result.emplace(message_.return_val_id());
  }

  for (const auto& merging_info : message_.return_merging_info()) {
    result.emplace(merging_info.is_returning_id());
    // |maybe_return_val_id| can be 0 if the function is void.
    if (merging_info.maybe_return_val_id()) {
      result.emplace(merging_info.maybe_return_val_id());
    }
  }

  return result;
}

protobufs::Transformation TransformationMergeFunctionReturns::ToMessage()
    const {
  protobufs::Transformation result;
  *result.mutable_merge_function_returns() = message_;
  return result;
}

std::map<uint32_t, protobufs::ReturnMergingInfo>
TransformationMergeFunctionReturns::GetMappingOfMergeBlocksToInfo() const {
  std::map<uint32_t, protobufs::ReturnMergingInfo> result;
  for (const auto& info : message_.return_merging_info()) {
    result.emplace(info.merge_block_id(), info);
  }
  return result;
}

std::map<uint32_t, uint32_t>
TransformationMergeFunctionReturns::GetTypesToIdAvailableAfterEntryBlock(
    opt::IRContext* ir_context) const {
  std::map<uint32_t, uint32_t> result;
  // Consider all global declarations
  for (auto& global : ir_context->module()->types_values()) {
    if (global.HasResultId() && global.type_id()) {
      result.emplace(global.type_id(), global.result_id());
    }
  }

  auto function = ir_context->GetFunction(message_.function_id());
  assert(function && "The function must exist.");

  // Consider all function parameters
  function->ForEachParam([&result](opt::Instruction* param) {
    if (param->HasResultId() && param->type_id()) {
      result.emplace(param->type_id(), param->result_id());
    }
  });

  // Consider all the instructions in the entry block.
  for (auto& inst : *function->entry()) {
    if (inst.HasResultId() && inst.type_id()) {
      result.emplace(inst.type_id(), inst.result_id());
    }
  }

  return result;
}

bool TransformationMergeFunctionReturns::
    CheckDefinitionsStillDominateUsesAfterAddingNewPredecessors(
        opt::IRContext* ir_context, const opt::Function* function,
        const std::map<uint32_t, std::set<uint32_t>>&
            merge_blocks_to_new_predecessors) {
  for (const auto& merge_block_entry : merge_blocks_to_new_predecessors) {
    uint32_t merge_block = merge_block_entry.first;
    const auto& returning_preds = merge_block_entry.second;

    // Find a list of blocks in which there might be problematic definitions.
    // These are all the blocks that dominate the merge block but do not
    // dominate all of the new predecessors.
    std::vector<opt::BasicBlock*> problematic_blocks;

    auto dominator_analysis = ir_context->GetDominatorAnalysis(function);

    // Start from the immediate dominator of the merge block.
    auto current_block = dominator_analysis->ImmediateDominator(merge_block);
    assert(current_block &&
           "Each merge block should have at least one dominator.");

    for (uint32_t pred : returning_preds) {
      while (!dominator_analysis->Dominates(current_block->id(), pred)) {
        // The current block does not dominate all of the new predecessor
        // blocks, so it might be problematic.
        problematic_blocks.emplace_back(current_block);

        // Walk up the dominator tree.
        current_block = dominator_analysis->ImmediateDominator(current_block);
        assert(current_block &&
               "We should be able to find a dominator for all the blocks, "
               "since they must all be dominated at least by the header.");
      }
    }

    // Identify the loop header corresponding to the merge block.
    uint32_t loop_header =
        fuzzerutil::GetLoopFromMergeBlock(ir_context, merge_block);

    // For all the ids defined in blocks inside |problematic_blocks|, check that
    // all their uses are either:
    // - inside the loop (or in the loop header). If this is the case, the path
    //   from the definition to the use does not go through the merge block, so
    //   adding new predecessor to it is not a problem.
    // - inside an OpPhi instruction in the merge block. If this is the case,
    //   the definition does not need to dominate the merge block.
    for (auto block : problematic_blocks) {
      assert((block->id() == loop_header ||
              ir_context->GetStructuredCFGAnalysis()->ContainingLoop(
                  block->id()) == loop_header) &&
             "The problematic blocks should all be inside the loop (also "
             "considering the header).");
      bool dominance_rules_maintained =
          block->WhileEachInst([ir_context, loop_header,
                                merge_block](opt::Instruction* instruction) {
            // Instruction without a result id do not cause any problems.
            if (!instruction->HasResultId()) {
              return true;
            }

            // Check that all the uses of the id are inside the loop.
            return ir_context->get_def_use_mgr()->WhileEachUse(
                instruction->result_id(),
                [ir_context, loop_header, merge_block](
                    opt::Instruction* inst_use, uint32_t /* unused */) {
                  uint32_t block_use =
                      ir_context->get_instr_block(inst_use)->id();

                  // The usage is OK if it is inside the loop (including the
                  // header).
                  if (block_use == loop_header ||
                      ir_context->GetStructuredCFGAnalysis()->ContainingLoop(
                          block_use)) {
                    return true;
                  }

                  // The usage is OK if it is inside an OpPhi instruction in the
                  // merge block.
                  return block_use == merge_block &&
                         inst_use->opcode() == spv::Op::OpPhi;
                });
          });

      // If not all instructions in the block satisfy the requirement, the
      // transformation is not applicable.
      if (!dominance_rules_maintained) {
        return false;
      }
    }
  }

  return true;
}

bool TransformationMergeFunctionReturns::
    CheckThatTheCorrectIdsAreGivenForMergeBlock(
        uint32_t merge_block,
        const std::map<uint32_t, protobufs::ReturnMergingInfo>&
            merge_blocks_to_info,
        const std::map<uint32_t, uint32_t>& types_to_available_id,
        bool function_is_void, opt::IRContext* ir_context,
        const TransformationContext& transformation_context,
        std::set<uint32_t>* used_fresh_ids) {
  // A map from OpPhi ids to ids of the same type available at the beginning
  // of the merge block.
  std::map<uint32_t, uint32_t> phi_to_id;

  if (merge_blocks_to_info.count(merge_block) > 0) {
    // If the map contains an entry for the merge block, check that the fresh
    // ids are fresh and distinct.
    auto info = merge_blocks_to_info.at(merge_block);
    if (!info.is_returning_id() ||
        !CheckIdIsFreshAndNotUsedByThisTransformation(
            info.is_returning_id(), ir_context, used_fresh_ids)) {
      return false;
    }

    if (!function_is_void &&
        (!info.maybe_return_val_id() ||
         !CheckIdIsFreshAndNotUsedByThisTransformation(
             info.maybe_return_val_id(), ir_context, used_fresh_ids))) {
      return false;
    }

    // Get the mapping from OpPhis to suitable ids.
    phi_to_id = fuzzerutil::RepeatedUInt32PairToMap(
        *info.mutable_opphi_to_suitable_id());
  } else {
    // If the map does not contain an entry for the merge block, check that
    // overflow ids are available.
    if (!transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
      return false;
    }
  }

  // For each OpPhi instruction, check that a suitable placeholder id is
  // available.
  bool suitable_info_for_phi =
      ir_context->get_instr_block(merge_block)
          ->WhileEachPhiInst([ir_context, &phi_to_id,
                              &types_to_available_id](opt::Instruction* inst) {
            if (phi_to_id.count(inst->result_id()) > 0) {
              // If there exists a mapping for this instruction and the
              // placeholder id exists in the module, check that it has the
              // correct type and it is available before the instruction.
              auto placeholder_def = ir_context->get_def_use_mgr()->GetDef(
                  phi_to_id[inst->result_id()]);
              if (placeholder_def) {
                if (inst->type_id() != placeholder_def->type_id()) {
                  return false;
                }
                if (!fuzzerutil::IdIsAvailableBeforeInstruction(
                        ir_context, inst, placeholder_def->result_id())) {
                  return false;
                }

                return true;
              }
            }

            // If there is no mapping, check if there is a suitable id
            // available at the end of the entry block.
            return types_to_available_id.count(inst->type_id()) > 0;
          });

  if (!suitable_info_for_phi) {
    return false;
  }

  return true;
}

}  // namespace fuzz
}  // namespace spvtools