// Copyright (c) 2015-2016 The Khronos Group Inc.
//
// 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 <cassert>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include "source/cfa.h"
#include "source/opcode.h"
#include "source/spirv_constant.h"
#include "source/spirv_validator_options.h"
#include "source/val/basic_block.h"
#include "source/val/construct.h"
#include "source/val/function.h"
#include "source/val/validate.h"
#include "source/val/validation_state.h"

namespace spvtools {
namespace val {
namespace {

spv_result_t ValidatePhi(ValidationState_t& _, const Instruction* inst) {
  auto block = inst->block();
  size_t num_in_ops = inst->words().size() - 3;
  if (num_in_ops % 2 != 0) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "OpPhi does not have an equal number of incoming values and "
              "basic blocks.";
  }

  if (_.IsVoidType(inst->type_id())) {
    return _.diag(SPV_ERROR_INVALID_DATA, inst)
           << "OpPhi must not have void result type";
  }
  if (_.IsPointerType(inst->type_id()) &&
      _.addressing_model() == spv::AddressingModel::Logical) {
    if (!_.features().variable_pointers) {
      return _.diag(SPV_ERROR_INVALID_DATA, inst)
             << "Using pointers with OpPhi requires capability "
             << "VariablePointers or VariablePointersStorageBuffer";
    }
  }

  const Instruction* type_inst = _.FindDef(inst->type_id());
  assert(type_inst);
  const spv::Op type_opcode = type_inst->opcode();

  if (!_.options()->before_hlsl_legalization &&
      !_.HasCapability(spv::Capability::BindlessTextureNV)) {
    if (type_opcode == spv::Op::OpTypeSampledImage ||
        (_.HasCapability(spv::Capability::Shader) &&
         (type_opcode == spv::Op::OpTypeImage ||
          type_opcode == spv::Op::OpTypeSampler))) {
      return _.diag(SPV_ERROR_INVALID_ID, inst)
             << "Result type cannot be Op" << spvOpcodeString(type_opcode);
    }
  }

  // Create a uniqued vector of predecessor ids for comparison against
  // incoming values. OpBranchConditional %cond %label %label produces two
  // predecessors in the CFG.
  std::vector<uint32_t> pred_ids;
  std::transform(block->predecessors()->begin(), block->predecessors()->end(),
                 std::back_inserter(pred_ids),
                 [](const BasicBlock* b) { return b->id(); });
  std::sort(pred_ids.begin(), pred_ids.end());
  pred_ids.erase(std::unique(pred_ids.begin(), pred_ids.end()), pred_ids.end());

  size_t num_edges = num_in_ops / 2;
  if (num_edges != pred_ids.size()) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "OpPhi's number of incoming blocks (" << num_edges
           << ") does not match block's predecessor count ("
           << block->predecessors()->size() << ").";
  }

  std::unordered_set<uint32_t> observed_predecessors;

  for (size_t i = 3; i < inst->words().size(); ++i) {
    auto inc_id = inst->word(i);
    if (i % 2 == 1) {
      // Incoming value type must match the phi result type.
      auto inc_type_id = _.GetTypeId(inc_id);
      if (inst->type_id() != inc_type_id) {
        return _.diag(SPV_ERROR_INVALID_ID, inst)
               << "OpPhi's result type <id> " << _.getIdName(inst->type_id())
               << " does not match incoming value <id> " << _.getIdName(inc_id)
               << " type <id> " << _.getIdName(inc_type_id) << ".";
      }
    } else {
      if (_.GetIdOpcode(inc_id) != spv::Op::OpLabel) {
        return _.diag(SPV_ERROR_INVALID_ID, inst)
               << "OpPhi's incoming basic block <id> " << _.getIdName(inc_id)
               << " is not an OpLabel.";
      }

      // Incoming basic block must be an immediate predecessor of the phi's
      // block.
      if (!std::binary_search(pred_ids.begin(), pred_ids.end(), inc_id)) {
        return _.diag(SPV_ERROR_INVALID_ID, inst)
               << "OpPhi's incoming basic block <id> " << _.getIdName(inc_id)
               << " is not a predecessor of <id> " << _.getIdName(block->id())
               << ".";
      }

      // We must not have already seen this predecessor as one of the phi's
      // operands.
      if (observed_predecessors.count(inc_id) != 0) {
        return _.diag(SPV_ERROR_INVALID_ID, inst)
               << "OpPhi references incoming basic block <id> "
               << _.getIdName(inc_id) << " multiple times.";
      }

      // Note the fact that we have now observed this predecessor.
      observed_predecessors.insert(inc_id);
    }
  }

  return SPV_SUCCESS;
}

spv_result_t ValidateBranch(ValidationState_t& _, const Instruction* inst) {
  // target operands must be OpLabel
  const auto id = inst->GetOperandAs<uint32_t>(0);
  const auto target = _.FindDef(id);
  if (!target || spv::Op::OpLabel != target->opcode()) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "'Target Label' operands for OpBranch must be the ID "
              "of an OpLabel instruction";
  }

  return SPV_SUCCESS;
}

spv_result_t ValidateBranchConditional(ValidationState_t& _,
                                       const Instruction* inst) {
  // num_operands is either 3 or 5 --- if 5, the last two need to be literal
  // integers
  const auto num_operands = inst->operands().size();
  if (num_operands != 3 && num_operands != 5) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "OpBranchConditional requires either 3 or 5 parameters";
  }

  // grab the condition operand and check that it is a bool
  const auto cond_id = inst->GetOperandAs<uint32_t>(0);
  const auto cond_op = _.FindDef(cond_id);
  if (!cond_op || !cond_op->type_id() ||
      !_.IsBoolScalarType(cond_op->type_id())) {
    return _.diag(SPV_ERROR_INVALID_ID, inst) << "Condition operand for "
                                                 "OpBranchConditional must be "
                                                 "of boolean type";
  }

  // target operands must be OpLabel
  // note that we don't need to check that the target labels are in the same
  // function,
  // PerformCfgChecks already checks for that
  const auto true_id = inst->GetOperandAs<uint32_t>(1);
  const auto true_target = _.FindDef(true_id);
  if (!true_target || spv::Op::OpLabel != true_target->opcode()) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "The 'True Label' operand for OpBranchConditional must be the "
              "ID of an OpLabel instruction";
  }

  const auto false_id = inst->GetOperandAs<uint32_t>(2);
  const auto false_target = _.FindDef(false_id);
  if (!false_target || spv::Op::OpLabel != false_target->opcode()) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "The 'False Label' operand for OpBranchConditional must be the "
              "ID of an OpLabel instruction";
  }

  // A similar requirement for SPV_KHR_maximal_reconvergence is deferred until
  // entry point call trees have been reconrded.
  if (_.version() >= SPV_SPIRV_VERSION_WORD(1, 6) && true_id == false_id) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "In SPIR-V 1.6 or later, True Label and False Label must be "
              "different labels";
  }

  return SPV_SUCCESS;
}

spv_result_t ValidateSwitch(ValidationState_t& _, const Instruction* inst) {
  const auto num_operands = inst->operands().size();
  // At least two operands (selector, default), any more than that are
  // literal/target.

  const auto sel_type_id = _.GetOperandTypeId(inst, 0);
  if (!_.IsIntScalarType(sel_type_id)) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "Selector type must be OpTypeInt";
  }

  const auto default_label = _.FindDef(inst->GetOperandAs<uint32_t>(1));
  if (default_label->opcode() != spv::Op::OpLabel) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "Default must be an OpLabel instruction";
  }

  // target operands must be OpLabel
  for (size_t i = 2; i < num_operands; i += 2) {
    // literal, id
    const auto id = inst->GetOperandAs<uint32_t>(i + 1);
    const auto target = _.FindDef(id);
    if (!target || spv::Op::OpLabel != target->opcode()) {
      return _.diag(SPV_ERROR_INVALID_ID, inst)
             << "'Target Label' operands for OpSwitch must be IDs of an "
                "OpLabel instruction";
    }
  }

  return SPV_SUCCESS;
}

spv_result_t ValidateReturnValue(ValidationState_t& _,
                                 const Instruction* inst) {
  const auto value_id = inst->GetOperandAs<uint32_t>(0);
  const auto value = _.FindDef(value_id);
  if (!value || !value->type_id()) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "OpReturnValue Value <id> " << _.getIdName(value_id)
           << " does not represent a value.";
  }
  auto value_type = _.FindDef(value->type_id());
  if (!value_type || spv::Op::OpTypeVoid == value_type->opcode()) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "OpReturnValue value's type <id> "
           << _.getIdName(value->type_id()) << " is missing or void.";
  }

  if (_.addressing_model() == spv::AddressingModel::Logical &&
      (spv::Op::OpTypePointer == value_type->opcode() ||
       spv::Op::OpTypeUntypedPointerKHR == value_type->opcode()) &&
      !_.features().variable_pointers && !_.options()->relax_logical_pointer) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "OpReturnValue value's type <id> "
           << _.getIdName(value->type_id())
           << " is a pointer, which is invalid in the Logical addressing "
              "model.";
  }

  const auto function = inst->function();
  const auto return_type = _.FindDef(function->GetResultTypeId());
  if (!return_type || return_type->id() != value_type->id()) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "OpReturnValue Value <id> " << _.getIdName(value_id)
           << "s type does not match OpFunction's return type.";
  }

  return SPV_SUCCESS;
}

uint32_t operator>>(const spv::LoopControlShift& lhs,
                    const spv::LoopControlShift& rhs) {
  return uint32_t(lhs) >> uint32_t(rhs);
}

spv_result_t ValidateLoopMerge(ValidationState_t& _, const Instruction* inst) {
  const auto merge_id = inst->GetOperandAs<uint32_t>(0);
  const auto merge = _.FindDef(merge_id);
  if (!merge || merge->opcode() != spv::Op::OpLabel) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "Merge Block " << _.getIdName(merge_id) << " must be an OpLabel";
  }
  if (merge_id == inst->block()->id()) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "Merge Block may not be the block containing the OpLoopMerge\n";
  }

  const auto continue_id = inst->GetOperandAs<uint32_t>(1);
  const auto continue_target = _.FindDef(continue_id);
  if (!continue_target || continue_target->opcode() != spv::Op::OpLabel) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "Continue Target " << _.getIdName(continue_id)
           << " must be an OpLabel";
  }

  if (merge_id == continue_id) {
    return _.diag(SPV_ERROR_INVALID_ID, inst)
           << "Merge Block and Continue Target must be different ids";
  }

  const auto loop_control = inst->GetOperandAs<spv::LoopControlShift>(2);
  if ((loop_control >> spv::LoopControlShift::Unroll) & 0x1 &&
      (loop_control >> spv::LoopControlShift::DontUnroll) & 0x1) {
    return _.diag(SPV_ERROR_INVALID_DATA, inst)
           << "Unroll and DontUnroll loop controls must not both be specified";
  }
  if ((loop_control >> spv::LoopControlShift::DontUnroll) & 0x1 &&
      (loop_control >> spv::LoopControlShift::PeelCount) & 0x1) {
    return _.diag(SPV_ERROR_INVALID_DATA, inst) << "PeelCount and DontUnroll "
                                                   "loop controls must not "
                                                   "both be specified";
  }
  if ((loop_control >> spv::LoopControlShift::DontUnroll) & 0x1 &&
      (loop_control >> spv::LoopControlShift::PartialCount) & 0x1) {
    return _.diag(SPV_ERROR_INVALID_DATA, inst) << "PartialCount and "
                                                   "DontUnroll loop controls "
                                                   "must not both be specified";
  }

  uint32_t operand = 3;
  if ((loop_control >> spv::LoopControlShift::DependencyLength) & 0x1) {
    ++operand;
  }
  if ((loop_control >> spv::LoopControlShift::MinIterations) & 0x1) {
    ++operand;
  }
  if ((loop_control >> spv::LoopControlShift::MaxIterations) & 0x1) {
    ++operand;
  }
  if ((loop_control >> spv::LoopControlShift::IterationMultiple) & 0x1) {
    if (inst->operands().size() < operand ||
        inst->GetOperandAs<uint32_t>(operand) == 0) {
      return _.diag(SPV_ERROR_INVALID_DATA, inst) << "IterationMultiple loop "
                                                     "control operand must be "
                                                     "greater than zero";
    }
    ++operand;
  }
  if ((loop_control >> spv::LoopControlShift::PeelCount) & 0x1) {
    ++operand;
  }
  if ((loop_control >> spv::LoopControlShift::PartialCount) & 0x1) {
    ++operand;
  }

  // That the right number of operands is present is checked by the parser. The
  // above code tracks operands for expanded validation checking in the future.

  return SPV_SUCCESS;
}

}  // namespace

void printDominatorList(const BasicBlock& b) {
  std::cout << b.id() << " is dominated by: ";
  const BasicBlock* bb = &b;
  while (bb->immediate_dominator() != bb) {
    bb = bb->immediate_dominator();
    std::cout << bb->id() << " ";
  }
}

#define CFG_ASSERT(ASSERT_FUNC, TARGET) \
  if (spv_result_t rcode = ASSERT_FUNC(_, TARGET)) return rcode

spv_result_t FirstBlockAssert(ValidationState_t& _, uint32_t target) {
  if (_.current_function().IsFirstBlock(target)) {
    return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(_.current_function().id()))
           << "First block " << _.getIdName(target) << " of function "
           << _.getIdName(_.current_function().id()) << " is targeted by block "
           << _.getIdName(_.current_function().current_block()->id());
  }
  return SPV_SUCCESS;
}

spv_result_t MergeBlockAssert(ValidationState_t& _, uint32_t merge_block) {
  if (_.current_function().IsBlockType(merge_block, kBlockTypeMerge)) {
    return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(_.current_function().id()))
           << "Block " << _.getIdName(merge_block)
           << " is already a merge block for another header";
  }
  return SPV_SUCCESS;
}

/// Update the continue construct's exit blocks once the backedge blocks are
/// identified in the CFG.
void UpdateContinueConstructExitBlocks(
    Function& function,
    const std::vector<std::pair<uint32_t, uint32_t>>& back_edges) {
  auto& constructs = function.constructs();
  // TODO(umar): Think of a faster way to do this
  for (auto& edge : back_edges) {
    uint32_t back_edge_block_id;
    uint32_t loop_header_block_id;
    std::tie(back_edge_block_id, loop_header_block_id) = edge;
    auto is_this_header = [=](Construct& c) {
      return c.type() == ConstructType::kLoop &&
             c.entry_block()->id() == loop_header_block_id;
    };

    for (auto construct : constructs) {
      if (is_this_header(construct)) {
        Construct* continue_construct =
            construct.corresponding_constructs().back();
        assert(continue_construct->type() == ConstructType::kContinue);

        BasicBlock* back_edge_block;
        std::tie(back_edge_block, std::ignore) =
            function.GetBlock(back_edge_block_id);
        continue_construct->set_exit(back_edge_block);
      }
    }
  }
}

std::tuple<std::string, std::string, std::string> ConstructNames(
    ConstructType type) {
  std::string construct_name, header_name, exit_name;

  switch (type) {
    case ConstructType::kSelection:
      construct_name = "selection";
      header_name = "selection header";
      exit_name = "merge block";
      break;
    case ConstructType::kLoop:
      construct_name = "loop";
      header_name = "loop header";
      exit_name = "merge block";
      break;
    case ConstructType::kContinue:
      construct_name = "continue";
      header_name = "continue target";
      exit_name = "back-edge block";
      break;
    case ConstructType::kCase:
      construct_name = "case";
      header_name = "case entry block";
      exit_name = "case exit block";
      break;
    default:
      assert(1 == 0 && "Not defined type");
  }

  return std::make_tuple(construct_name, header_name, exit_name);
}

/// Constructs an error message for construct validation errors
std::string ConstructErrorString(const Construct& construct,
                                 const std::string& header_string,
                                 const std::string& exit_string,
                                 const std::string& dominate_text) {
  std::string construct_name, header_name, exit_name;
  std::tie(construct_name, header_name, exit_name) =
      ConstructNames(construct.type());

  // TODO(umar): Add header block for continue constructs to error message
  return "The " + construct_name + " construct with the " + header_name + " " +
         header_string + " " + dominate_text + " the " + exit_name + " " +
         exit_string;
}

// Finds the fall through case construct of |target_block| and records it in
// |case_fall_through|. Returns SPV_ERROR_INVALID_CFG if the case construct
// headed by |target_block| branches to multiple case constructs.
spv_result_t FindCaseFallThrough(
    ValidationState_t& _, BasicBlock* target_block, uint32_t* case_fall_through,
    const Construct& switch_construct,
    const std::unordered_set<uint32_t>& case_targets) {
  const auto* merge = switch_construct.exit_block();
  std::vector<BasicBlock*> stack;
  stack.push_back(target_block);
  std::unordered_set<const BasicBlock*> visited;
  bool target_reachable = target_block->structurally_reachable();
  while (!stack.empty()) {
    auto block = stack.back();
    stack.pop_back();

    if (block == merge) continue;

    if (!visited.insert(block).second) continue;

    if (target_reachable && block->structurally_reachable() &&
        target_block->structurally_dominates(*block)) {
      // Still in the case construct.
      for (auto successor : *block->successors()) {
        stack.push_back(successor);
      }
    } else {
      // Exiting the case construct to non-merge block.
      if (!case_targets.count(block->id())) {
        // We have already filtered out the following:
        //  * The switch's merge
        //  * Other case targets
        //  * Blocks in the same case construct
        //
        // So the only remaining valid branches are the structured exits from
        // the overall selection construct of the switch.
        if (switch_construct.IsStructuredExit(_, block)) {
          continue;
        }

        return _.diag(SPV_ERROR_INVALID_CFG, target_block->label())
               << "Case construct that targets "
               << _.getIdName(target_block->id())
               << " has invalid branch to block " << _.getIdName(block->id())
               << " (not another case construct, corresponding merge, outer "
                  "loop merge or outer loop continue)";
      }

      if (*case_fall_through == 0u) {
        if (target_block != block) {
          *case_fall_through = block->id();
        }
      } else if (*case_fall_through != block->id()) {
        // Case construct has at most one branch to another case construct.
        return _.diag(SPV_ERROR_INVALID_CFG, target_block->label())
               << "Case construct that targets "
               << _.getIdName(target_block->id())
               << " has branches to multiple other case construct targets "
               << _.getIdName(*case_fall_through) << " and "
               << _.getIdName(block->id());
      }
    }
  }

  return SPV_SUCCESS;
}

spv_result_t StructuredSwitchChecks(ValidationState_t& _, Function* function,
                                    const Construct& switch_construct) {
  const auto* header = switch_construct.entry_block();
  const auto* merge = switch_construct.exit_block();
  const auto* switch_inst = header->terminator();
  std::unordered_set<uint32_t> case_targets;
  for (uint32_t i = 1; i < switch_inst->operands().size(); i += 2) {
    uint32_t target = switch_inst->GetOperandAs<uint32_t>(i);
    if (target != merge->id()) case_targets.insert(target);
  }
  // Tracks how many times each case construct is targeted by another case
  // construct.
  std::map<uint32_t, uint32_t> num_fall_through_targeted;
  uint32_t default_case_fall_through = 0u;
  uint32_t default_target = switch_inst->GetOperandAs<uint32_t>(1u);
  bool default_appears_multiple_times = false;
  for (uint32_t i = 3; i < switch_inst->operands().size(); i += 2) {
    if (default_target == switch_inst->GetOperandAs<uint32_t>(i)) {
      default_appears_multiple_times = true;
      break;
    }
  }

  std::unordered_map<uint32_t, uint32_t> seen_to_fall_through;
  for (uint32_t i = 1; i < switch_inst->operands().size(); i += 2) {
    uint32_t target = switch_inst->GetOperandAs<uint32_t>(i);
    if (target == merge->id()) continue;

    uint32_t case_fall_through = 0u;
    auto seen_iter = seen_to_fall_through.find(target);
    if (seen_iter == seen_to_fall_through.end()) {
      const auto target_block = function->GetBlock(target).first;
      // OpSwitch must dominate all its case constructs.
      if (header->structurally_reachable() &&
          target_block->structurally_reachable() &&
          !header->structurally_dominates(*target_block)) {
        return _.diag(SPV_ERROR_INVALID_CFG, header->label())
               << "Switch header " << _.getIdName(header->id())
               << " does not structurally dominate its case construct "
               << _.getIdName(target);
      }

      if (auto error = FindCaseFallThrough(_, target_block, &case_fall_through,
                                           switch_construct, case_targets)) {
        return error;
      }

      // Track how many time the fall through case has been targeted.
      if (case_fall_through != 0u) {
        auto where = num_fall_through_targeted.lower_bound(case_fall_through);
        if (where == num_fall_through_targeted.end() ||
            where->first != case_fall_through) {
          num_fall_through_targeted.insert(
              where, std::make_pair(case_fall_through, 1));
        } else {
          where->second++;
        }
      }
      seen_to_fall_through.insert(std::make_pair(target, case_fall_through));
    } else {
      case_fall_through = seen_iter->second;
    }

    if (case_fall_through == default_target &&
        !default_appears_multiple_times) {
      case_fall_through = default_case_fall_through;
    }
    if (case_fall_through != 0u) {
      bool is_default = i == 1;
      if (is_default) {
        default_case_fall_through = case_fall_through;
      } else {
        // Allow code like:
        // case x:
        // case y:
        //   ...
        // case z:
        //
        // Where x and y target the same block and fall through to z.
        uint32_t j = i;
        while ((j + 2 < switch_inst->operands().size()) &&
               target == switch_inst->GetOperandAs<uint32_t>(j + 2)) {
          j += 2;
        }
        // If Target T1 branches to Target T2, or if Target T1 branches to the
        // Default target and the Default target branches to Target T2, then T1
        // must immediately precede T2 in the list of OpSwitch Target operands.
        if ((switch_inst->operands().size() < j + 2) ||
            (case_fall_through != switch_inst->GetOperandAs<uint32_t>(j + 2))) {
          return _.diag(SPV_ERROR_INVALID_CFG, switch_inst)
                 << "Case construct that targets " << _.getIdName(target)
                 << " has branches to the case construct that targets "
                 << _.getIdName(case_fall_through)
                 << ", but does not immediately precede it in the "
                    "OpSwitch's target list";
        }
      }
    }
  }

  // Each case construct must be branched to by at most one other case
  // construct.
  for (const auto& pair : num_fall_through_targeted) {
    if (pair.second > 1) {
      return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(pair.first))
             << "Multiple case constructs have branches to the case construct "
                "that targets "
             << _.getIdName(pair.first);
    }
  }

  return SPV_SUCCESS;
}

// Validates that all CFG divergences (i.e. conditional branch or switch) are
// structured correctly. Either divergence is preceded by a merge instruction
// or the divergence introduces at most one unseen label.
spv_result_t ValidateStructuredSelections(
    ValidationState_t& _, const std::vector<const BasicBlock*>& postorder) {
  std::unordered_set<uint32_t> seen;
  for (auto iter = postorder.rbegin(); iter != postorder.rend(); ++iter) {
    const auto* block = *iter;
    const auto* terminator = block->terminator();
    if (!terminator) continue;
    const auto index = terminator - &_.ordered_instructions()[0];
    auto* merge = &_.ordered_instructions()[index - 1];
    // Marks merges and continues as seen.
    if (merge->opcode() == spv::Op::OpSelectionMerge) {
      seen.insert(merge->GetOperandAs<uint32_t>(0));
    } else if (merge->opcode() == spv::Op::OpLoopMerge) {
      seen.insert(merge->GetOperandAs<uint32_t>(0));
      seen.insert(merge->GetOperandAs<uint32_t>(1));
    } else {
      // Only track the pointer if it is a merge instruction.
      merge = nullptr;
    }

    // Skip unreachable blocks.
    if (!block->structurally_reachable()) continue;

    if (terminator->opcode() == spv::Op::OpBranchConditional) {
      const auto true_label = terminator->GetOperandAs<uint32_t>(1);
      const auto false_label = terminator->GetOperandAs<uint32_t>(2);
      // Mark the upcoming blocks as seen now, but only error out if this block
      // was missing a merge instruction and both labels hadn't been seen
      // previously.
      const bool true_label_unseen = seen.insert(true_label).second;
      const bool false_label_unseen = seen.insert(false_label).second;
      if ((!merge || merge->opcode() == spv::Op::OpLoopMerge) &&
          true_label_unseen && false_label_unseen) {
        return _.diag(SPV_ERROR_INVALID_CFG, terminator)
               << "Selection must be structured";
      }
    } else if (terminator->opcode() == spv::Op::OpSwitch) {
      if (!merge) {
        return _.diag(SPV_ERROR_INVALID_CFG, terminator)
               << "OpSwitch must be preceded by an OpSelectionMerge "
                  "instruction";
      }
      // Mark the targets as seen.
      for (uint32_t i = 1; i < terminator->operands().size(); i += 2) {
        const auto target = terminator->GetOperandAs<uint32_t>(i);
        seen.insert(target);
      }
    }
  }

  return SPV_SUCCESS;
}

spv_result_t StructuredControlFlowChecks(
    ValidationState_t& _, Function* function,
    const std::vector<std::pair<uint32_t, uint32_t>>& back_edges,
    const std::vector<const BasicBlock*>& postorder) {
  /// Check all backedges target only loop headers and have exactly one
  /// back-edge branching to it

  // Map a loop header to blocks with back-edges to the loop header.
  std::map<uint32_t, std::unordered_set<uint32_t>> loop_latch_blocks;
  for (auto back_edge : back_edges) {
    uint32_t back_edge_block;
    uint32_t header_block;
    std::tie(back_edge_block, header_block) = back_edge;
    if (!function->IsBlockType(header_block, kBlockTypeLoop)) {
      return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(back_edge_block))
             << "Back-edges (" << _.getIdName(back_edge_block) << " -> "
             << _.getIdName(header_block)
             << ") can only be formed between a block and a loop header.";
    }
    loop_latch_blocks[header_block].insert(back_edge_block);
  }

  // Check the loop headers have exactly one back-edge branching to it
  for (BasicBlock* loop_header : function->ordered_blocks()) {
    if (!loop_header->structurally_reachable()) continue;
    if (!loop_header->is_type(kBlockTypeLoop)) continue;
    auto loop_header_id = loop_header->id();
    auto num_latch_blocks = loop_latch_blocks[loop_header_id].size();
    if (num_latch_blocks != 1) {
      return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(loop_header_id))
             << "Loop header " << _.getIdName(loop_header_id)
             << " is targeted by " << num_latch_blocks
             << " back-edge blocks but the standard requires exactly one";
    }
  }

  // Check construct rules
  for (const Construct& construct : function->constructs()) {
    auto header = construct.entry_block();
    if (!header->structurally_reachable()) continue;
    auto merge = construct.exit_block();

    if (!merge) {
      std::string construct_name, header_name, exit_name;
      std::tie(construct_name, header_name, exit_name) =
          ConstructNames(construct.type());
      return _.diag(SPV_ERROR_INTERNAL, _.FindDef(header->id()))
             << "Construct " + construct_name + " with " + header_name + " " +
                    _.getIdName(header->id()) + " does not have a " +
                    exit_name + ". This may be a bug in the validator.";
    }

    // If the header is reachable, the merge is guaranteed to be structurally
    // reachable.
    if (!header->structurally_dominates(*merge)) {
      return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
             << ConstructErrorString(construct, _.getIdName(header->id()),
                                     _.getIdName(merge->id()),
                                     "does not structurally dominate");
    }

    // If it's really a merge block for a selection or loop, then it must be
    // *strictly* structrually dominated by the header.
    if (construct.ExitBlockIsMergeBlock() && (header == merge)) {
      return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
             << ConstructErrorString(construct, _.getIdName(header->id()),
                                     _.getIdName(merge->id()),
                                     "does not strictly structurally dominate");
    }

    // Check post-dominance for continue constructs.  But dominance and
    // post-dominance only make sense when the construct is reachable.
    if (construct.type() == ConstructType::kContinue) {
      if (!merge->structurally_postdominates(*header)) {
        return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
               << ConstructErrorString(construct, _.getIdName(header->id()),
                                       _.getIdName(merge->id()),
                                       "is not structurally post dominated by");
      }
    }

    Construct::ConstructBlockSet construct_blocks = construct.blocks(function);
    std::string construct_name, header_name, exit_name;
    std::tie(construct_name, header_name, exit_name) =
        ConstructNames(construct.type());
    for (auto block : construct_blocks) {
      // Check that all exits from the construct are via structured exits.
      for (auto succ : *block->successors()) {
        if (!construct_blocks.count(succ) &&
            !construct.IsStructuredExit(_, succ)) {
          return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
                 << "block <ID> " << _.getIdName(block->id()) << " exits the "
                 << construct_name << " headed by <ID> "
                 << _.getIdName(header->id())
                 << ", but not via a structured exit";
        }
      }
      if (block == header) continue;
      // Check that for all non-header blocks, all predecessors are within this
      // construct.
      for (auto pred : *block->predecessors()) {
        if (pred->structurally_reachable() && !construct_blocks.count(pred)) {
          return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(pred->id()))
                 << "block <ID> " << pred->id() << " branches to the "
                 << construct_name << " construct, but not to the "
                 << header_name << " <ID> " << header->id();
        }
      }

      if (block->is_type(BlockType::kBlockTypeSelection) ||
          block->is_type(BlockType::kBlockTypeLoop)) {
        size_t index = (block->terminator() - &_.ordered_instructions()[0]) - 1;
        const auto& merge_inst = _.ordered_instructions()[index];
        if (merge_inst.opcode() == spv::Op::OpSelectionMerge ||
            merge_inst.opcode() == spv::Op::OpLoopMerge) {
          uint32_t merge_id = merge_inst.GetOperandAs<uint32_t>(0);
          auto merge_block = function->GetBlock(merge_id).first;
          if (merge_block->structurally_reachable() &&
              !construct_blocks.count(merge_block)) {
            return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
                   << "Header block " << _.getIdName(block->id())
                   << " is contained in the " << construct_name
                   << " construct headed by " << _.getIdName(header->id())
                   << ", but its merge block " << _.getIdName(merge_id)
                   << " is not";
          }
        }
      }
    }

    if (construct.type() == ConstructType::kLoop) {
      // If the continue target differs from the loop header, then check that
      // all edges into the continue construct come from within the loop.
      const auto index = header->terminator() - &_.ordered_instructions()[0];
      const auto& merge_inst = _.ordered_instructions()[index - 1];
      const auto continue_id = merge_inst.GetOperandAs<uint32_t>(1);
      const auto* continue_inst = _.FindDef(continue_id);
      // OpLabel instructions aren't stored as part of the basic block for
      // legacy reaasons. Grab the next instruction and use it's block pointer
      // instead.
      const auto next_index =
          (continue_inst - &_.ordered_instructions()[0]) + 1;
      const auto& next_inst = _.ordered_instructions()[next_index];
      const auto* continue_target = next_inst.block();
      if (header->id() != continue_id) {
        for (auto pred : *continue_target->predecessors()) {
          if (!pred->structurally_reachable()) {
            continue;
          }
          // Ignore back-edges from within the continue construct.
          bool is_back_edge = false;
          for (auto back_edge : back_edges) {
            uint32_t back_edge_block;
            uint32_t header_block;
            std::tie(back_edge_block, header_block) = back_edge;
            if (header_block == continue_id && back_edge_block == pred->id())
              is_back_edge = true;
          }
          if (!construct_blocks.count(pred) && !is_back_edge) {
            return _.diag(SPV_ERROR_INVALID_CFG, pred->terminator())
                   << "Block " << _.getIdName(pred->id())
                   << " branches to the loop continue target "
                   << _.getIdName(continue_id)
                   << ", but is not contained in the associated loop construct "
                   << _.getIdName(header->id());
          }
        }
      }
    }

    // Checks rules for case constructs.
    if (construct.type() == ConstructType::kSelection &&
        header->terminator()->opcode() == spv::Op::OpSwitch) {
      if (auto error = StructuredSwitchChecks(_, function, construct)) {
        return error;
      }
    }
  }

  if (auto error = ValidateStructuredSelections(_, postorder)) {
    return error;
  }

  return SPV_SUCCESS;
}

spv_result_t MaximalReconvergenceChecks(ValidationState_t& _) {
  // Find all the entry points with the MaximallyReconvergencesKHR execution
  // mode.
  std::unordered_set<uint32_t> maximal_funcs;
  std::unordered_set<uint32_t> maximal_entry_points;
  for (auto entry_point : _.entry_points()) {
    const auto* exec_modes = _.GetExecutionModes(entry_point);
    if (exec_modes &&
        exec_modes->count(spv::ExecutionMode::MaximallyReconvergesKHR)) {
      maximal_entry_points.insert(entry_point);
      maximal_funcs.insert(entry_point);
    }
  }

  if (maximal_entry_points.empty()) {
    return SPV_SUCCESS;
  }

  // Find all the functions reachable from a maximal reconvergence entry point.
  for (const auto& func : _.functions()) {
    const auto& entry_points = _.EntryPointReferences(func.id());
    for (auto id : entry_points) {
      if (maximal_entry_points.count(id)) {
        maximal_funcs.insert(func.id());
        break;
      }
    }
  }

  // Check for conditional branches with the same true and false targets.
  for (const auto& inst : _.ordered_instructions()) {
    if (inst.opcode() == spv::Op::OpBranchConditional) {
      const auto true_id = inst.GetOperandAs<uint32_t>(1);
      const auto false_id = inst.GetOperandAs<uint32_t>(2);
      if (true_id == false_id && maximal_funcs.count(inst.function()->id())) {
        return _.diag(SPV_ERROR_INVALID_ID, &inst)
               << "In entry points using the MaximallyReconvergesKHR execution "
                  "mode, True Label and False Label must be different labels";
      }
    }
  }

  // Check for invalid multiple predecessors. Only loop headers, continue
  // targets, merge targets or switch targets or defaults may have multiple
  // unique predecessors.
  for (const auto& func : _.functions()) {
    if (!maximal_funcs.count(func.id())) continue;

    for (const auto* block : func.ordered_blocks()) {
      std::unordered_set<uint32_t> unique_preds;
      const auto* preds = block->predecessors();
      if (!preds) continue;

      for (const auto* pred : *preds) {
        unique_preds.insert(pred->id());
      }
      if (unique_preds.size() < 2) continue;

      const auto* terminator = block->terminator();
      const auto index = terminator - &_.ordered_instructions()[0];
      const auto* pre_terminator = &_.ordered_instructions()[index - 1];
      if (pre_terminator->opcode() == spv::Op::OpLoopMerge) continue;

      const auto* label = _.FindDef(block->id());
      bool ok = false;
      for (const auto& pair : label->uses()) {
        const auto* use_inst = pair.first;
        switch (use_inst->opcode()) {
          case spv::Op::OpSelectionMerge:
          case spv::Op::OpLoopMerge:
          case spv::Op::OpSwitch:
            ok = true;
            break;
          default:
            break;
        }
      }
      if (!ok) {
        return _.diag(SPV_ERROR_INVALID_CFG, label)
               << "In entry points using the MaximallyReconvergesKHR "
                  "execution mode, this basic block must not have multiple "
                  "unique predecessors";
      }
    }
  }

  return SPV_SUCCESS;
}

spv_result_t PerformCfgChecks(ValidationState_t& _) {
  for (auto& function : _.functions()) {
    // Check all referenced blocks are defined within a function
    if (function.undefined_block_count() != 0) {
      std::string undef_blocks("{");
      bool first = true;
      for (auto undefined_block : function.undefined_blocks()) {
        undef_blocks += _.getIdName(undefined_block);
        if (!first) {
          undef_blocks += " ";
        }
        first = false;
      }
      return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(function.id()))
             << "Block(s) " << undef_blocks << "}"
             << " are referenced but not defined in function "
             << _.getIdName(function.id());
    }

    // Set each block's immediate dominator.
    //
    // We want to analyze all the blocks in the function, even in degenerate
    // control flow cases including unreachable blocks.  So use the augmented
    // CFG to ensure we cover all the blocks.
    std::vector<const BasicBlock*> postorder;
    auto ignore_block = [](const BasicBlock*) {};
    auto no_terminal_blocks = [](const BasicBlock*) { return false; };
    if (!function.ordered_blocks().empty()) {
      /// calculate dominators
      CFA<BasicBlock>::DepthFirstTraversal(
          function.first_block(), function.AugmentedCFGSuccessorsFunction(),
          ignore_block, [&](const BasicBlock* b) { postorder.push_back(b); },
          no_terminal_blocks);
      auto edges = CFA<BasicBlock>::CalculateDominators(
          postorder, function.AugmentedCFGPredecessorsFunction());
      for (auto edge : edges) {
        if (edge.first != edge.second)
          edge.first->SetImmediateDominator(edge.second);
      }
    }

    auto& blocks = function.ordered_blocks();
    if (!blocks.empty()) {
      // Check if the order of blocks in the binary appear before the blocks
      // they dominate
      for (auto block = begin(blocks) + 1; block != end(blocks); ++block) {
        if (auto idom = (*block)->immediate_dominator()) {
          if (idom != function.pseudo_entry_block() &&
              block == std::find(begin(blocks), block, idom)) {
            return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(idom->id()))
                   << "Block " << _.getIdName((*block)->id())
                   << " appears in the binary before its dominator "
                   << _.getIdName(idom->id());
          }
        }
      }
      // If we have structured control flow, check that no block has a control
      // flow nesting depth larger than the limit.
      if (_.HasCapability(spv::Capability::Shader)) {
        const int control_flow_nesting_depth_limit =
            _.options()->universal_limits_.max_control_flow_nesting_depth;
        for (auto block = begin(blocks); block != end(blocks); ++block) {
          if (function.GetBlockDepth(*block) >
              control_flow_nesting_depth_limit) {
            return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef((*block)->id()))
                   << "Maximum Control Flow nesting depth exceeded.";
          }
        }
      }
    }

    /// Structured control flow checks are only required for shader capabilities
    if (_.HasCapability(spv::Capability::Shader)) {
      // Calculate structural dominance.
      postorder.clear();
      std::vector<const BasicBlock*> postdom_postorder;
      std::vector<std::pair<uint32_t, uint32_t>> back_edges;
      if (!function.ordered_blocks().empty()) {
        /// calculate dominators
        CFA<BasicBlock>::DepthFirstTraversal(
            function.first_block(),
            function.AugmentedStructuralCFGSuccessorsFunction(), ignore_block,
            [&](const BasicBlock* b) { postorder.push_back(b); },
            no_terminal_blocks);
        auto edges = CFA<BasicBlock>::CalculateDominators(
            postorder, function.AugmentedStructuralCFGPredecessorsFunction());
        for (auto edge : edges) {
          if (edge.first != edge.second)
            edge.first->SetImmediateStructuralDominator(edge.second);
        }

        /// calculate post dominators
        CFA<BasicBlock>::DepthFirstTraversal(
            function.pseudo_exit_block(),
            function.AugmentedStructuralCFGPredecessorsFunction(), ignore_block,
            [&](const BasicBlock* b) { postdom_postorder.push_back(b); },
            no_terminal_blocks);
        auto postdom_edges = CFA<BasicBlock>::CalculateDominators(
            postdom_postorder,
            function.AugmentedStructuralCFGSuccessorsFunction());
        for (auto edge : postdom_edges) {
          edge.first->SetImmediateStructuralPostDominator(edge.second);
        }
        /// calculate back edges.
        CFA<BasicBlock>::DepthFirstTraversal(
            function.pseudo_entry_block(),
            function.AugmentedStructuralCFGSuccessorsFunction(), ignore_block,
            ignore_block,
            [&](const BasicBlock* from, const BasicBlock* to) {
              // A back edge must be a real edge. Since the augmented successors
              // contain structural edges, filter those from consideration.
              for (const auto* succ : *(from->successors())) {
                if (succ == to) back_edges.emplace_back(from->id(), to->id());
              }
            },
            no_terminal_blocks);
      }
      UpdateContinueConstructExitBlocks(function, back_edges);

      if (auto error =
              StructuredControlFlowChecks(_, &function, back_edges, postorder))
        return error;
    }
  }

  if (auto error = MaximalReconvergenceChecks(_)) {
    return error;
  }

  return SPV_SUCCESS;
}

spv_result_t CfgPass(ValidationState_t& _, const Instruction* inst) {
  spv::Op opcode = inst->opcode();
  switch (opcode) {
    case spv::Op::OpLabel:
      if (auto error = _.current_function().RegisterBlock(inst->id()))
        return error;

      // TODO(github:1661) This should be done in the
      // ValidationState::RegisterInstruction method but because of the order of
      // passes the OpLabel ends up not being part of the basic block it starts.
      _.current_function().current_block()->set_label(inst);
      break;
    case spv::Op::OpLoopMerge: {
      uint32_t merge_block = inst->GetOperandAs<uint32_t>(0);
      uint32_t continue_block = inst->GetOperandAs<uint32_t>(1);
      CFG_ASSERT(MergeBlockAssert, merge_block);

      if (auto error = _.current_function().RegisterLoopMerge(merge_block,
                                                              continue_block))
        return error;
    } break;
    case spv::Op::OpSelectionMerge: {
      uint32_t merge_block = inst->GetOperandAs<uint32_t>(0);
      CFG_ASSERT(MergeBlockAssert, merge_block);

      if (auto error = _.current_function().RegisterSelectionMerge(merge_block))
        return error;
    } break;
    case spv::Op::OpBranch: {
      uint32_t target = inst->GetOperandAs<uint32_t>(0);
      CFG_ASSERT(FirstBlockAssert, target);

      _.current_function().RegisterBlockEnd({target});
    } break;
    case spv::Op::OpBranchConditional: {
      uint32_t tlabel = inst->GetOperandAs<uint32_t>(1);
      uint32_t flabel = inst->GetOperandAs<uint32_t>(2);
      CFG_ASSERT(FirstBlockAssert, tlabel);
      CFG_ASSERT(FirstBlockAssert, flabel);

      _.current_function().RegisterBlockEnd({tlabel, flabel});
    } break;

    case spv::Op::OpSwitch: {
      std::vector<uint32_t> cases;
      for (size_t i = 1; i < inst->operands().size(); i += 2) {
        uint32_t target = inst->GetOperandAs<uint32_t>(i);
        CFG_ASSERT(FirstBlockAssert, target);
        cases.push_back(target);
      }
      _.current_function().RegisterBlockEnd({cases});
    } break;
    case spv::Op::OpReturn: {
      const uint32_t return_type = _.current_function().GetResultTypeId();
      const Instruction* return_type_inst = _.FindDef(return_type);
      assert(return_type_inst);
      if (return_type_inst->opcode() != spv::Op::OpTypeVoid)
        return _.diag(SPV_ERROR_INVALID_CFG, inst)
               << "OpReturn can only be called from a function with void "
               << "return type.";
      _.current_function().RegisterBlockEnd(std::vector<uint32_t>());
      break;
    }
    case spv::Op::OpKill:
    case spv::Op::OpReturnValue:
    case spv::Op::OpUnreachable:
    case spv::Op::OpTerminateInvocation:
    case spv::Op::OpIgnoreIntersectionKHR:
    case spv::Op::OpTerminateRayKHR:
    case spv::Op::OpEmitMeshTasksEXT:
      _.current_function().RegisterBlockEnd(std::vector<uint32_t>());
      // Ops with dedicated passes check for the Execution Model there
      if (opcode == spv::Op::OpKill) {
        _.current_function().RegisterExecutionModelLimitation(
            spv::ExecutionModel::Fragment,
            "OpKill requires Fragment execution model");
      }
      if (opcode == spv::Op::OpTerminateInvocation) {
        _.current_function().RegisterExecutionModelLimitation(
            spv::ExecutionModel::Fragment,
            "OpTerminateInvocation requires Fragment execution model");
      }
      if (opcode == spv::Op::OpIgnoreIntersectionKHR) {
        _.current_function().RegisterExecutionModelLimitation(
            spv::ExecutionModel::AnyHitKHR,
            "OpIgnoreIntersectionKHR requires AnyHitKHR execution model");
      }
      if (opcode == spv::Op::OpTerminateRayKHR) {
        _.current_function().RegisterExecutionModelLimitation(
            spv::ExecutionModel::AnyHitKHR,
            "OpTerminateRayKHR requires AnyHitKHR execution model");
      }

      break;
    default:
      break;
  }
  return SPV_SUCCESS;
}

void ReachabilityPass(ValidationState_t& _) {
  for (auto& f : _.functions()) {
    std::vector<BasicBlock*> stack;
    auto entry = f.first_block();
    // Skip function declarations.
    if (entry) stack.push_back(entry);

    while (!stack.empty()) {
      auto block = stack.back();
      stack.pop_back();

      if (block->reachable()) continue;

      block->set_reachable(true);
      for (auto succ : *block->successors()) {
        stack.push_back(succ);
      }
    }
  }

  // Repeat for structural reachability.
  for (auto& f : _.functions()) {
    std::vector<BasicBlock*> stack;
    auto entry = f.first_block();
    // Skip function declarations.
    if (entry) stack.push_back(entry);

    while (!stack.empty()) {
      auto block = stack.back();
      stack.pop_back();

      if (block->structurally_reachable()) continue;

      block->set_structurally_reachable(true);
      for (auto succ : *block->structural_successors()) {
        stack.push_back(succ);
      }
    }
  }
}

spv_result_t ControlFlowPass(ValidationState_t& _, const Instruction* inst) {
  switch (inst->opcode()) {
    case spv::Op::OpPhi:
      if (auto error = ValidatePhi(_, inst)) return error;
      break;
    case spv::Op::OpBranch:
      if (auto error = ValidateBranch(_, inst)) return error;
      break;
    case spv::Op::OpBranchConditional:
      if (auto error = ValidateBranchConditional(_, inst)) return error;
      break;
    case spv::Op::OpReturnValue:
      if (auto error = ValidateReturnValue(_, inst)) return error;
      break;
    case spv::Op::OpSwitch:
      if (auto error = ValidateSwitch(_, inst)) return error;
      break;
    case spv::Op::OpLoopMerge:
      if (auto error = ValidateLoopMerge(_, inst)) return error;
      break;
    default:
      break;
  }

  return SPV_SUCCESS;
}

}  // namespace val
}  // namespace spvtools