// Copyright (c) 2017 Google 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 <array>
#include <memory>
#include <string>
#include <vector>

#include "gmock/gmock.h"
#include "source/opt/dominator_analysis.h"
#include "source/opt/iterator.h"
#include "source/opt/pass.h"
#include "test/opt/assembly_builder.h"
#include "test/opt/function_utils.h"
#include "test/opt/pass_fixture.h"
#include "test/opt/pass_utils.h"

namespace spvtools {
namespace opt {
namespace {

using ::testing::UnorderedElementsAre;
using PassClassTest = PassTest<::testing::Test>;

// Check that x dominates y, and
//   if x != y then
//      x strictly dominates y and
//      y does not dominate x and
//      y does not strictly dominate x
//   if x == x then
//      x does not strictly dominate itself
void check_dominance(const DominatorAnalysisBase& dom_tree, const Function* fn,
                     uint32_t x, uint32_t y) {
  SCOPED_TRACE("Check dominance properties for Basic Block " +
               std::to_string(x) + " and " + std::to_string(y));
  EXPECT_TRUE(dom_tree.Dominates(spvtest::GetBasicBlock(fn, x),
                                 spvtest::GetBasicBlock(fn, y)));
  EXPECT_TRUE(dom_tree.Dominates(x, y));
  if (x == y) {
    EXPECT_FALSE(dom_tree.StrictlyDominates(x, x));
  } else {
    EXPECT_TRUE(dom_tree.StrictlyDominates(x, y));
    EXPECT_FALSE(dom_tree.Dominates(y, x));
    EXPECT_FALSE(dom_tree.StrictlyDominates(y, x));
  }
}

// Check that x does not dominates y and vice versa
void check_no_dominance(const DominatorAnalysisBase& dom_tree,
                        const Function* fn, uint32_t x, uint32_t y) {
  SCOPED_TRACE("Check no domination for Basic Block " + std::to_string(x) +
               " and " + std::to_string(y));
  EXPECT_FALSE(dom_tree.Dominates(spvtest::GetBasicBlock(fn, x),
                                  spvtest::GetBasicBlock(fn, y)));
  EXPECT_FALSE(dom_tree.Dominates(x, y));
  EXPECT_FALSE(dom_tree.StrictlyDominates(spvtest::GetBasicBlock(fn, x),
                                          spvtest::GetBasicBlock(fn, y)));
  EXPECT_FALSE(dom_tree.StrictlyDominates(x, y));

  EXPECT_FALSE(dom_tree.Dominates(spvtest::GetBasicBlock(fn, y),
                                  spvtest::GetBasicBlock(fn, x)));
  EXPECT_FALSE(dom_tree.Dominates(y, x));
  EXPECT_FALSE(dom_tree.StrictlyDominates(spvtest::GetBasicBlock(fn, y),
                                          spvtest::GetBasicBlock(fn, x)));
  EXPECT_FALSE(dom_tree.StrictlyDominates(y, x));
}

TEST_F(PassClassTest, DominatorSimpleCFG) {
  const std::string text = R"(
               OpCapability Addresses
               OpCapability Kernel
               OpMemoryModel Physical64 OpenCL
               OpEntryPoint Kernel %1 "main"
          %2 = OpTypeVoid
          %3 = OpTypeFunction %2
          %4 = OpTypeBool
          %5 = OpTypeInt 32 0
          %6 = OpConstant %5 0
          %7 = OpConstantFalse %4
          %8 = OpConstantTrue %4
          %9 = OpConstant %5 1
          %1 = OpFunction %2 None %3
         %10 = OpLabel
               OpBranch %11
         %11 = OpLabel
               OpSwitch %6 %12 1 %13
         %12 = OpLabel
               OpBranch %14
         %13 = OpLabel
               OpBranch %14
         %14 = OpLabel
               OpBranchConditional %8 %11 %15
         %15 = OpLabel
               OpReturn
               OpFunctionEnd
)";
  // clang-format on
  std::unique_ptr<IRContext> context =
      BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
  Module* module = context->module();
  EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
                             << text << std::endl;
  const Function* fn = spvtest::GetFunction(module, 1);
  const BasicBlock* entry = spvtest::GetBasicBlock(fn, 10);
  EXPECT_EQ(entry, fn->entry().get())
      << "The entry node is not the expected one";

  // Test normal dominator tree
  {
    DominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
    EXPECT_TRUE(
        dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));

    // (strict) dominance checks
    for (uint32_t id : {10, 11, 12, 13, 14, 15})
      check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 10, 11);
    check_dominance(dom_tree, fn, 10, 12);
    check_dominance(dom_tree, fn, 10, 13);
    check_dominance(dom_tree, fn, 10, 14);
    check_dominance(dom_tree, fn, 10, 15);

    check_dominance(dom_tree, fn, 11, 12);
    check_dominance(dom_tree, fn, 11, 13);
    check_dominance(dom_tree, fn, 11, 14);
    check_dominance(dom_tree, fn, 11, 15);

    check_dominance(dom_tree, fn, 14, 15);

    check_no_dominance(dom_tree, fn, 12, 13);
    check_no_dominance(dom_tree, fn, 12, 14);
    check_no_dominance(dom_tree, fn, 13, 14);

    // check with some invalid inputs
    EXPECT_FALSE(dom_tree.Dominates(nullptr, entry));
    EXPECT_FALSE(dom_tree.Dominates(entry, nullptr));
    EXPECT_FALSE(dom_tree.Dominates(static_cast<BasicBlock*>(nullptr),
                                    static_cast<BasicBlock*>(nullptr)));
    EXPECT_FALSE(dom_tree.Dominates(10, 1));
    EXPECT_FALSE(dom_tree.Dominates(1, 10));
    EXPECT_FALSE(dom_tree.Dominates(1, 1));

    EXPECT_FALSE(dom_tree.StrictlyDominates(nullptr, entry));
    EXPECT_FALSE(dom_tree.StrictlyDominates(entry, nullptr));
    EXPECT_FALSE(dom_tree.StrictlyDominates(nullptr, nullptr));
    EXPECT_FALSE(dom_tree.StrictlyDominates(10, 1));
    EXPECT_FALSE(dom_tree.StrictlyDominates(1, 10));
    EXPECT_FALSE(dom_tree.StrictlyDominates(1, 1));

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
    EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());
    EXPECT_EQ(dom_tree.ImmediateDominator(nullptr), nullptr);

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              spvtest::GetBasicBlock(fn, 10));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              spvtest::GetBasicBlock(fn, 11));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
              spvtest::GetBasicBlock(fn, 11));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 14)),
              spvtest::GetBasicBlock(fn, 11));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 15)),
              spvtest::GetBasicBlock(fn, 14));
  }

  // Test post dominator tree
  {
    PostDominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
    EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 15));

    // (strict) dominance checks
    for (uint32_t id : {10, 11, 12, 13, 14, 15})
      check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 14, 10);
    check_dominance(dom_tree, fn, 14, 11);
    check_dominance(dom_tree, fn, 14, 12);
    check_dominance(dom_tree, fn, 14, 13);

    check_dominance(dom_tree, fn, 15, 10);
    check_dominance(dom_tree, fn, 15, 11);
    check_dominance(dom_tree, fn, 15, 12);
    check_dominance(dom_tree, fn, 15, 13);
    check_dominance(dom_tree, fn, 15, 14);

    check_no_dominance(dom_tree, fn, 13, 12);
    check_no_dominance(dom_tree, fn, 12, 11);
    check_no_dominance(dom_tree, fn, 13, 11);

    // check with some invalid inputs
    EXPECT_FALSE(dom_tree.Dominates(nullptr, entry));
    EXPECT_FALSE(dom_tree.Dominates(entry, nullptr));
    EXPECT_FALSE(dom_tree.Dominates(static_cast<BasicBlock*>(nullptr),
                                    static_cast<BasicBlock*>(nullptr)));
    EXPECT_FALSE(dom_tree.Dominates(10, 1));
    EXPECT_FALSE(dom_tree.Dominates(1, 10));
    EXPECT_FALSE(dom_tree.Dominates(1, 1));

    EXPECT_FALSE(dom_tree.StrictlyDominates(nullptr, entry));
    EXPECT_FALSE(dom_tree.StrictlyDominates(entry, nullptr));
    EXPECT_FALSE(dom_tree.StrictlyDominates(nullptr, nullptr));
    EXPECT_FALSE(dom_tree.StrictlyDominates(10, 1));
    EXPECT_FALSE(dom_tree.StrictlyDominates(1, 10));
    EXPECT_FALSE(dom_tree.StrictlyDominates(1, 1));

    EXPECT_EQ(dom_tree.ImmediateDominator(nullptr), nullptr);

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              spvtest::GetBasicBlock(fn, 14));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              spvtest::GetBasicBlock(fn, 14));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
              spvtest::GetBasicBlock(fn, 14));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 14)),
              spvtest::GetBasicBlock(fn, 15));

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 15)),
              cfg.pseudo_exit_block());

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);
  }
}

TEST_F(PassClassTest, DominatorIrreducibleCFG) {
  const std::string text = R"(
               OpCapability Addresses
               OpCapability Kernel
               OpMemoryModel Physical64 OpenCL
               OpEntryPoint Kernel %1 "main"
          %2 = OpTypeVoid
          %3 = OpTypeFunction %2
          %4 = OpTypeBool
          %5 = OpTypeInt 32 0
          %6 = OpConstantFalse %4
          %7 = OpConstantTrue %4
          %1 = OpFunction %2 None %3
          %8 = OpLabel
               OpBranch %9
          %9 = OpLabel
               OpBranchConditional %7 %10 %11
         %10 = OpLabel
               OpBranch %11
         %11 = OpLabel
               OpBranchConditional %7 %10 %12
         %12 = OpLabel
               OpReturn
               OpFunctionEnd
)";
  // clang-format on
  std::unique_ptr<IRContext> context =
      BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
  Module* module = context->module();
  EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
                             << text << std::endl;
  const Function* fn = spvtest::GetFunction(module, 1);

  const BasicBlock* entry = spvtest::GetBasicBlock(fn, 8);
  EXPECT_EQ(entry, fn->entry().get())
      << "The entry node is not the expected one";

  // Check normal dominator tree
  {
    DominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
    EXPECT_TRUE(
        dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));

    // (strict) dominance checks
    for (uint32_t id : {8, 9, 10, 11, 12})
      check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 8, 9);
    check_dominance(dom_tree, fn, 8, 10);
    check_dominance(dom_tree, fn, 8, 11);
    check_dominance(dom_tree, fn, 8, 12);

    check_dominance(dom_tree, fn, 9, 10);
    check_dominance(dom_tree, fn, 9, 11);
    check_dominance(dom_tree, fn, 9, 12);

    check_dominance(dom_tree, fn, 11, 12);

    check_no_dominance(dom_tree, fn, 10, 11);

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
    EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 9)),
              spvtest::GetBasicBlock(fn, 8));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
              spvtest::GetBasicBlock(fn, 9));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              spvtest::GetBasicBlock(fn, 9));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              spvtest::GetBasicBlock(fn, 11));
  }

  // Check post dominator tree
  {
    PostDominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
    EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 12));

    // (strict) dominance checks
    for (uint32_t id : {8, 9, 10, 11, 12})
      check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 12, 8);
    check_dominance(dom_tree, fn, 12, 10);
    check_dominance(dom_tree, fn, 12, 11);
    check_dominance(dom_tree, fn, 12, 12);

    check_dominance(dom_tree, fn, 11, 8);
    check_dominance(dom_tree, fn, 11, 9);
    check_dominance(dom_tree, fn, 11, 10);

    check_dominance(dom_tree, fn, 9, 8);

    EXPECT_EQ(dom_tree.ImmediateDominator(entry),
              spvtest::GetBasicBlock(fn, 9));

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 9)),
              spvtest::GetBasicBlock(fn, 11));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
              spvtest::GetBasicBlock(fn, 11));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              spvtest::GetBasicBlock(fn, 12));

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              cfg.pseudo_exit_block());

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);
  }
}

TEST_F(PassClassTest, DominatorLoopToSelf) {
  const std::string text = R"(
               OpCapability Addresses
               OpCapability Kernel
               OpMemoryModel Physical64 OpenCL
               OpEntryPoint Kernel %1 "main"
          %2 = OpTypeVoid
          %3 = OpTypeFunction %2
          %4 = OpTypeBool
          %5 = OpTypeInt 32 0
          %6 = OpConstant %5 0
          %7 = OpConstantFalse %4
          %8 = OpConstantTrue %4
          %9 = OpConstant %5 1
          %1 = OpFunction %2 None %3
         %10 = OpLabel
               OpBranch %11
         %11 = OpLabel
               OpSwitch %6 %12 1 %11
         %12 = OpLabel
               OpReturn
               OpFunctionEnd
)";
  // clang-format on
  std::unique_ptr<IRContext> context =
      BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
  Module* module = context->module();
  EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
                             << text << std::endl;
  const Function* fn = spvtest::GetFunction(module, 1);

  const BasicBlock* entry = spvtest::GetBasicBlock(fn, 10);
  EXPECT_EQ(entry, fn->entry().get())
      << "The entry node is not the expected one";

  // Check normal dominator tree
  {
    DominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
    EXPECT_TRUE(
        dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));

    // (strict) dominance checks
    for (uint32_t id : {10, 11, 12}) check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 10, 11);
    check_dominance(dom_tree, fn, 10, 12);
    check_dominance(dom_tree, fn, 11, 12);

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
    EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              spvtest::GetBasicBlock(fn, 10));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              spvtest::GetBasicBlock(fn, 11));

    std::array<uint32_t, 3> node_order = {{10, 11, 12}};
    {
      // Test dominator tree iteration order.
      DominatorTree::iterator node_it = dom_tree.GetDomTree().begin();
      DominatorTree::iterator node_end = dom_tree.GetDomTree().end();
      for (uint32_t id : node_order) {
        EXPECT_NE(node_it, node_end);
        EXPECT_EQ(node_it->id(), id);
        node_it++;
      }
      EXPECT_EQ(node_it, node_end);
    }
    {
      // Same as above, but with const iterators.
      DominatorTree::const_iterator node_it = dom_tree.GetDomTree().cbegin();
      DominatorTree::const_iterator node_end = dom_tree.GetDomTree().cend();
      for (uint32_t id : node_order) {
        EXPECT_NE(node_it, node_end);
        EXPECT_EQ(node_it->id(), id);
        node_it++;
      }
      EXPECT_EQ(node_it, node_end);
    }
    {
      // Test dominator tree iteration order.
      DominatorTree::post_iterator node_it = dom_tree.GetDomTree().post_begin();
      DominatorTree::post_iterator node_end = dom_tree.GetDomTree().post_end();
      for (uint32_t id : make_range(node_order.rbegin(), node_order.rend())) {
        EXPECT_NE(node_it, node_end);
        EXPECT_EQ(node_it->id(), id);
        node_it++;
      }
      EXPECT_EQ(node_it, node_end);
    }
    {
      // Same as above, but with const iterators.
      DominatorTree::const_post_iterator node_it =
          dom_tree.GetDomTree().post_cbegin();
      DominatorTree::const_post_iterator node_end =
          dom_tree.GetDomTree().post_cend();
      for (uint32_t id : make_range(node_order.rbegin(), node_order.rend())) {
        EXPECT_NE(node_it, node_end);
        EXPECT_EQ(node_it->id(), id);
        node_it++;
      }
      EXPECT_EQ(node_it, node_end);
    }
  }

  // Check post dominator tree
  {
    PostDominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
    EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 12));

    // (strict) dominance checks
    for (uint32_t id : {10, 11, 12}) check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 12, 10);
    check_dominance(dom_tree, fn, 12, 11);
    check_dominance(dom_tree, fn, 12, 12);

    EXPECT_EQ(dom_tree.ImmediateDominator(entry),
              spvtest::GetBasicBlock(fn, 11));

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              spvtest::GetBasicBlock(fn, 12));

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              cfg.pseudo_exit_block());

    std::array<uint32_t, 3> node_order = {{12, 11, 10}};
    {
      // Test dominator tree iteration order.
      DominatorTree::iterator node_it = tree.begin();
      DominatorTree::iterator node_end = tree.end();
      for (uint32_t id : node_order) {
        EXPECT_NE(node_it, node_end);
        EXPECT_EQ(node_it->id(), id);
        node_it++;
      }
      EXPECT_EQ(node_it, node_end);
    }
    {
      // Same as above, but with const iterators.
      DominatorTree::const_iterator node_it = tree.cbegin();
      DominatorTree::const_iterator node_end = tree.cend();
      for (uint32_t id : node_order) {
        EXPECT_NE(node_it, node_end);
        EXPECT_EQ(node_it->id(), id);
        node_it++;
      }
      EXPECT_EQ(node_it, node_end);
    }
    {
      // Test dominator tree iteration order.
      DominatorTree::post_iterator node_it = dom_tree.GetDomTree().post_begin();
      DominatorTree::post_iterator node_end = dom_tree.GetDomTree().post_end();
      for (uint32_t id : make_range(node_order.rbegin(), node_order.rend())) {
        EXPECT_NE(node_it, node_end);
        EXPECT_EQ(node_it->id(), id);
        node_it++;
      }
      EXPECT_EQ(node_it, node_end);
    }
    {
      // Same as above, but with const iterators.
      DominatorTree::const_post_iterator node_it =
          dom_tree.GetDomTree().post_cbegin();
      DominatorTree::const_post_iterator node_end =
          dom_tree.GetDomTree().post_cend();
      for (uint32_t id : make_range(node_order.rbegin(), node_order.rend())) {
        EXPECT_NE(node_it, node_end);
        EXPECT_EQ(node_it->id(), id);
        node_it++;
      }
      EXPECT_EQ(node_it, node_end);
    }
  }
}

TEST_F(PassClassTest, DominatorUnreachableInLoop) {
  const std::string text = R"(
               OpCapability Addresses
               OpCapability Kernel
               OpMemoryModel Physical64 OpenCL
               OpEntryPoint Kernel %1 "main"
          %2 = OpTypeVoid
          %3 = OpTypeFunction %2
          %4 = OpTypeBool
          %5 = OpTypeInt 32 0
          %6 = OpConstant %5 0
          %7 = OpConstantFalse %4
          %8 = OpConstantTrue %4
          %9 = OpConstant %5 1
          %1 = OpFunction %2 None %3
         %10 = OpLabel
               OpBranch %11
         %11 = OpLabel
               OpSwitch %6 %12 1 %13
         %12 = OpLabel
               OpBranch %14
         %13 = OpLabel
               OpUnreachable
         %14 = OpLabel
               OpBranchConditional %8 %11 %15
         %15 = OpLabel
               OpReturn
               OpFunctionEnd
)";
  // clang-format on
  std::unique_ptr<IRContext> context =
      BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
  Module* module = context->module();
  EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
                             << text << std::endl;
  const Function* fn = spvtest::GetFunction(module, 1);

  const BasicBlock* entry = spvtest::GetBasicBlock(fn, 10);
  EXPECT_EQ(entry, fn->entry().get())
      << "The entry node is not the expected one";

  // Check normal dominator tree
  {
    DominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
    EXPECT_TRUE(
        dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));

    // (strict) dominance checks
    for (uint32_t id : {10, 11, 12, 13, 14, 15})
      check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 10, 11);
    check_dominance(dom_tree, fn, 10, 13);
    check_dominance(dom_tree, fn, 10, 12);
    check_dominance(dom_tree, fn, 10, 14);
    check_dominance(dom_tree, fn, 10, 15);

    check_dominance(dom_tree, fn, 11, 12);
    check_dominance(dom_tree, fn, 11, 13);
    check_dominance(dom_tree, fn, 11, 14);
    check_dominance(dom_tree, fn, 11, 15);

    check_dominance(dom_tree, fn, 12, 14);
    check_dominance(dom_tree, fn, 12, 15);

    check_dominance(dom_tree, fn, 14, 15);

    check_no_dominance(dom_tree, fn, 13, 12);
    check_no_dominance(dom_tree, fn, 13, 14);
    check_no_dominance(dom_tree, fn, 13, 15);

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
    EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              spvtest::GetBasicBlock(fn, 10));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              spvtest::GetBasicBlock(fn, 11));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
              spvtest::GetBasicBlock(fn, 11));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 14)),
              spvtest::GetBasicBlock(fn, 12));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 15)),
              spvtest::GetBasicBlock(fn, 14));
  }

  // Check post dominator tree.
  {
    PostDominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // (strict) dominance checks.
    for (uint32_t id : {10, 11, 12, 13, 14, 15})
      check_dominance(dom_tree, fn, id, id);

    check_no_dominance(dom_tree, fn, 15, 10);
    check_no_dominance(dom_tree, fn, 15, 11);
    check_no_dominance(dom_tree, fn, 15, 12);
    check_no_dominance(dom_tree, fn, 15, 13);
    check_no_dominance(dom_tree, fn, 15, 14);

    check_dominance(dom_tree, fn, 14, 12);

    check_no_dominance(dom_tree, fn, 13, 10);
    check_no_dominance(dom_tree, fn, 13, 11);
    check_no_dominance(dom_tree, fn, 13, 12);
    check_no_dominance(dom_tree, fn, 13, 14);
    check_no_dominance(dom_tree, fn, 13, 15);

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
              spvtest::GetBasicBlock(fn, 11));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              spvtest::GetBasicBlock(fn, 14));

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 15)),
              cfg.pseudo_exit_block());
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
              cfg.pseudo_exit_block());
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 14)),
              cfg.pseudo_exit_block());
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              cfg.pseudo_exit_block());
  }
}

TEST_F(PassClassTest, DominatorInfinitLoop) {
  const std::string text = R"(
               OpCapability Addresses
               OpCapability Kernel
               OpMemoryModel Physical64 OpenCL
               OpEntryPoint Kernel %1 "main"
          %2 = OpTypeVoid
          %3 = OpTypeFunction %2
          %4 = OpTypeBool
          %5 = OpTypeInt 32 0
          %6 = OpConstant %5 0
          %7 = OpConstantFalse %4
          %8 = OpConstantTrue %4
          %9 = OpConstant %5 1
          %1 = OpFunction %2 None %3
         %10 = OpLabel
               OpBranch %11
         %11 = OpLabel
               OpSwitch %6 %12 1 %13
         %12 = OpLabel
               OpReturn
         %13 = OpLabel
               OpBranch %13
               OpFunctionEnd
)";
  // clang-format on
  std::unique_ptr<IRContext> context =
      BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
  Module* module = context->module();
  EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
                             << text << std::endl;
  const Function* fn = spvtest::GetFunction(module, 1);

  const BasicBlock* entry = spvtest::GetBasicBlock(fn, 10);
  EXPECT_EQ(entry, fn->entry().get())
      << "The entry node is not the expected one";
  // Check normal dominator tree
  {
    DominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
    EXPECT_TRUE(
        dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));

    // (strict) dominance checks
    for (uint32_t id : {10, 11, 12, 13}) check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 10, 11);
    check_dominance(dom_tree, fn, 10, 12);
    check_dominance(dom_tree, fn, 10, 13);

    check_dominance(dom_tree, fn, 11, 12);
    check_dominance(dom_tree, fn, 11, 13);

    check_no_dominance(dom_tree, fn, 13, 12);

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
    EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              spvtest::GetBasicBlock(fn, 10));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              spvtest::GetBasicBlock(fn, 11));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
              spvtest::GetBasicBlock(fn, 11));
  }

  // Check post dominator tree
  {
    PostDominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
    EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 12));

    // (strict) dominance checks
    for (uint32_t id : {10, 11, 12}) check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 12, 11);
    check_dominance(dom_tree, fn, 12, 10);

    // 13 should be completely out of tree as it's unreachable from exit nodes
    check_no_dominance(dom_tree, fn, 12, 13);
    check_no_dominance(dom_tree, fn, 11, 13);
    check_no_dominance(dom_tree, fn, 10, 13);

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
              cfg.pseudo_exit_block());

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
              spvtest::GetBasicBlock(fn, 11));

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
              spvtest::GetBasicBlock(fn, 12));
  }
}

TEST_F(PassClassTest, DominatorUnreachableFromEntry) {
  const std::string text = R"(
               OpCapability Addresses
               OpCapability Addresses
               OpCapability Kernel
               OpMemoryModel Physical64 OpenCL
               OpEntryPoint Kernel %1 "main"
          %2 = OpTypeVoid
          %3 = OpTypeFunction %2
          %4 = OpTypeBool
          %5 = OpTypeInt 32 0
          %6 = OpConstantFalse %4
          %7 = OpConstantTrue %4
          %1 = OpFunction %2 None %3
          %8 = OpLabel
               OpBranch %9
          %9 = OpLabel
               OpReturn
         %10 = OpLabel
               OpBranch %9
               OpFunctionEnd
)";
  // clang-format on
  std::unique_ptr<IRContext> context =
      BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
  Module* module = context->module();
  EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
                             << text << std::endl;
  const Function* fn = spvtest::GetFunction(module, 1);

  const BasicBlock* entry = spvtest::GetBasicBlock(fn, 8);
  EXPECT_EQ(entry, fn->entry().get())
      << "The entry node is not the expected one";

  // Check dominator tree
  {
    DominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
    EXPECT_TRUE(
        dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));

    // (strict) dominance checks
    for (uint32_t id : {8, 9}) check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 8, 9);

    check_no_dominance(dom_tree, fn, 10, 8);
    check_no_dominance(dom_tree, fn, 10, 9);

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
    EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());

    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 9)),
              spvtest::GetBasicBlock(fn, 8));
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
              nullptr);
  }

  // Check post dominator tree
  {
    PostDominatorAnalysis dom_tree;
    const CFG& cfg = *context->cfg();
    dom_tree.InitializeTree(cfg, fn);

    // Inspect the actual tree
    DominatorTree& tree = dom_tree.GetDomTree();
    EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
    EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 9));

    // (strict) dominance checks
    for (uint32_t id : {8, 9, 10}) check_dominance(dom_tree, fn, id, id);

    check_dominance(dom_tree, fn, 9, 8);
    check_dominance(dom_tree, fn, 9, 10);

    EXPECT_EQ(dom_tree.ImmediateDominator(entry),
              spvtest::GetBasicBlock(fn, 9));

    EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 9)),
              cfg.pseudo_exit_block());
    EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
              spvtest::GetBasicBlock(fn, 9));
  }
}

TEST_F(PassClassTest, DominationForInstructions) {
  const std::string text = R"(
               OpCapability Shader
          %1 = OpExtInstImport "GLSL.std.450"
               OpMemoryModel Logical GLSL450
               OpEntryPoint Fragment %4 "main"
               OpExecutionMode %4 OriginUpperLeft
               OpSource ESSL 310
          %2 = OpTypeVoid
          %3 = OpTypeFunction %2
          %6 = OpTypeInt 32 1
          %7 = OpTypeBool
          %8 = OpConstantTrue %7
          %9 = OpConstant %6 37
         %10 = OpConstant %6 3
         %13 = OpConstant %6 5
          %4 = OpFunction %2 None %3
          %5 = OpLabel
         %12 = OpIAdd %6 %9 %10
         %15 = OpISub %6 %12 %13
               OpSelectionMerge %18 None
               OpBranchConditional %8 %16 %17
         %16 = OpLabel
         %20 = OpISub %6 %12 %13
               OpBranch %18
         %17 = OpLabel
         %21 = OpISub %6 %12 %13
               OpBranch %18
         %18 = OpLabel
         %22 = OpISub %6 %12 %13
               OpReturn
               OpFunctionEnd
  )";

  // clang-format on
  std::unique_ptr<IRContext> context =
      BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
  EXPECT_NE(nullptr, context->module()) << "Assembling failed for shader:\n"
                                        << text << std::endl;

  {
    const DominatorAnalysis* dominator_analysis = context->GetDominatorAnalysis(
        spvtest::GetFunction(context->module(), 4));

    EXPECT_TRUE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(12),
                                      context->get_def_use_mgr()->GetDef(15)));
    EXPECT_FALSE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
                                      context->get_def_use_mgr()->GetDef(12)));
    EXPECT_TRUE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(5),
                                      context->get_def_use_mgr()->GetDef(12)));
    EXPECT_FALSE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(12),
                                      context->get_def_use_mgr()->GetDef(5)));
    EXPECT_TRUE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
                                      context->get_def_use_mgr()->GetDef(16)));
    EXPECT_TRUE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
                                      context->get_def_use_mgr()->GetDef(21)));
    EXPECT_TRUE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
                                      context->get_def_use_mgr()->GetDef(18)));
    EXPECT_TRUE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
                                      context->get_def_use_mgr()->GetDef(22)));
    EXPECT_FALSE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(20),
                                      context->get_def_use_mgr()->GetDef(22)));
    EXPECT_FALSE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(21),
                                      context->get_def_use_mgr()->GetDef(22)));
    EXPECT_TRUE(
        dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
                                      context->get_def_use_mgr()->GetDef(15)));
  }
  {
    const PostDominatorAnalysis* post_dominator_analysis =
        context->GetPostDominatorAnalysis(
            spvtest::GetFunction(context->module(), 4));

    EXPECT_TRUE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(15),
        context->get_def_use_mgr()->GetDef(12)));
    EXPECT_FALSE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(12),
        context->get_def_use_mgr()->GetDef(15)));
    EXPECT_TRUE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(12),
        context->get_def_use_mgr()->GetDef(5)));
    EXPECT_FALSE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(5),
        context->get_def_use_mgr()->GetDef(12)));
    EXPECT_FALSE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(16),
        context->get_def_use_mgr()->GetDef(15)));
    EXPECT_FALSE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(21),
        context->get_def_use_mgr()->GetDef(15)));
    EXPECT_TRUE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(18),
        context->get_def_use_mgr()->GetDef(15)));
    EXPECT_TRUE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(22),
        context->get_def_use_mgr()->GetDef(15)));
    EXPECT_TRUE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(22),
        context->get_def_use_mgr()->GetDef(20)));
    EXPECT_TRUE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(22),
        context->get_def_use_mgr()->GetDef(21)));
    EXPECT_TRUE(post_dominator_analysis->Dominates(
        context->get_def_use_mgr()->GetDef(15),
        context->get_def_use_mgr()->GetDef(15)));
  }
}

}  // namespace
}  // namespace opt
}  // namespace spvtools