divergence_analysis_test.cpp

// Copyright (c) 2021 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/lint/divergence_analysis.h"

#include <string>

#include "gtest/gtest.h"
#include "source/opt/build_module.h"
#include "source/opt/ir_context.h"
#include "source/opt/module.h"
#include "spirv-tools/libspirv.h"

namespace spvtools {
namespace lint {
namespace {

void CLIMessageConsumer(spv_message_level_t level, const char*,
                        const spv_position_t& position, const char* message) {
  switch (level) {
    case SPV_MSG_FATAL:
    case SPV_MSG_INTERNAL_ERROR:
    case SPV_MSG_ERROR:
      std::cerr << "error: line " << position.index << ": " << message
                << std::endl;
      break;
    case SPV_MSG_WARNING:
      std::cout << "warning: line " << position.index << ": " << message
                << std::endl;
      break;
    case SPV_MSG_INFO:
      std::cout << "info: line " << position.index << ": " << message
                << std::endl;
      break;
    default:
      break;
  }
}

class DivergenceTest : public ::testing::Test {
 protected:
  std::unique_ptr<opt::IRContext> context_;
  std::unique_ptr<DivergenceAnalysis> divergence_;

  void Build(std::string text, uint32_t function_id = 1) {
    context_ = BuildModule(SPV_ENV_UNIVERSAL_1_0, CLIMessageConsumer, text,
                           SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
    ASSERT_NE(nullptr, context_.get());
    opt::Module* module = context_->module();
    ASSERT_NE(nullptr, module);
    // First function should have the given ID.
    ASSERT_NE(module->begin(), module->end());
    opt::Function* function = &*module->begin();
    ASSERT_EQ(function->result_id(), function_id);
    divergence_.reset(new DivergenceAnalysis(*context_));
    divergence_->Run(function);
  }
};

// Makes assertions a bit shorter.
using Level = DivergenceAnalysis::DivergenceLevel;

namespace {
std::string Preamble() {
  return R"(
               OpCapability Shader
               OpMemoryModel Logical GLSL450
               OpEntryPoint Fragment %1 "main" %x %y
	       OpExecutionMode %1 OriginLowerLeft
               OpDecorate %y Flat
       %void = OpTypeVoid
     %void_f = OpTypeFunction %void
       %bool = OpTypeBool
      %float = OpTypeFloat 32
      %false = OpConstantFalse %bool
       %true = OpConstantTrue %bool
       %zero = OpConstant %float 0
        %one = OpConstant %float 1
        %x_t = OpTypePointer Input %float
          %x = OpVariable %x_t Input
          %y = OpVariable %x_t Input
          %1 = OpFunction %void None %void_f
  )";
}
}  // namespace

TEST_F(DivergenceTest, SimpleTest) {
  // pseudocode:
  //     %10:
  //     %11 = load x
  //     if (%12 = (%11 < 0)) {
  //       %13:
  //       // do nothing
  //     }
  //     %14:
  //     return
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %11 = OpLoad %float %x
         %12 = OpFOrdLessThan %bool %11 %zero
               OpSelectionMerge %14 None
               OpBranchConditional %12 %13 %14
         %13 = OpLabel
               OpBranch %14
         %14 = OpLabel
               OpReturn
               OpFunctionEnd
  )"));
  // Control flow divergence.
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
  EXPECT_EQ(12, divergence_->GetDivergenceSource(13));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(14));
  // Value divergence.
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
  EXPECT_EQ(0, divergence_->GetDivergenceSource(11));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(11, divergence_->GetDivergenceSource(12));
}

TEST_F(DivergenceTest, FlowTypesTest) {
  // pseudocode:
  //   %10:
  //   %11 = load x
  //   %12 = x < 0 // data -> data
  //   if (%12) {
  //     %13: // data -> control
  //     if (true) {
  //       %14: // control -> control
  //     }
  //     %15:
  //     %16 = 1
  //   } else {
  //     %17:
  //     %18 = 2
  //   }
  //   %19:
  //   %19 = phi(%16 from %15, %18 from %17) // control -> data
  //   return
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %11 = OpLoad %float %x
         %12 = OpFOrdLessThan %bool %11 %zero
               OpSelectionMerge %19 None
               OpBranchConditional %12 %13 %17
         %13 = OpLabel
               OpSelectionMerge %15 None
               OpBranchConditional %true %14 %15
         %14 = OpLabel
               OpBranch %15
         %15 = OpLabel
         %16 = OpFAdd %float %zero %zero
               OpBranch %19
         %17 = OpLabel
         %18 = OpFAdd %float %zero %one
               OpBranch %19
         %19 = OpLabel
         %20 = OpPhi %float %16 %15 %18 %17
               OpReturn
               OpFunctionEnd
  )"));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
  EXPECT_EQ(0, divergence_->GetDivergenceSource(11));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(11, divergence_->GetDivergenceSource(12));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
  EXPECT_EQ(12, divergence_->GetDivergenceSource(13));
  EXPECT_EQ(10, divergence_->GetDivergenceDependenceSource(13));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
  EXPECT_EQ(13, divergence_->GetDivergenceSource(14));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
  EXPECT_EQ(12, divergence_->GetDivergenceSource(15));
  EXPECT_EQ(10, divergence_->GetDivergenceDependenceSource(15));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(16));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(17));
  EXPECT_EQ(12, divergence_->GetDivergenceSource(17));
  EXPECT_EQ(10, divergence_->GetDivergenceDependenceSource(17));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(18));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(19));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(20));
  EXPECT_TRUE(divergence_->GetDivergenceSource(20) == 15 ||
              divergence_->GetDivergenceDependenceSource(20) == 17)
      << "Got: " << divergence_->GetDivergenceDependenceSource(20);
}

TEST_F(DivergenceTest, ExitDependenceTest) {
  // pseudocode:
  //   %10:
  //   %11 = load x
  //   %12 = %11 < 0
  //   %13:
  //   do {
  //     %14:
  //     if (%12) {
  //       %15:
  //       continue;
  //     }
  //     %16:
  //     %17:
  //     continue;
  //   } %18: while(false);
  //   %19:
  //   return
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %11 = OpLoad %float %x
         %12 = OpFOrdLessThan %bool %11 %zero ; data -> data
               OpBranch %13
         %13 = OpLabel
               OpLoopMerge %19 %18 None
               OpBranch %14
         %14 = OpLabel
               OpSelectionMerge %16 None
               OpBranchConditional %12 %15 %16
         %15 = OpLabel
               OpBranch %18  ; continue
         %16 = OpLabel
               OpBranch %17
         %17 = OpLabel
               OpBranch %18  ; continue
         %18 = OpLabel
               OpBranchConditional %false %13 %19
         %19 = OpLabel
               OpReturn
               OpFunctionEnd
  )"));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
  EXPECT_EQ(0, divergence_->GetDivergenceSource(11));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(11, divergence_->GetDivergenceSource(12));

  // Since both branches continue, there's no divergent control dependence
  // to 13.
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(13));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(14));

  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
  EXPECT_EQ(12, divergence_->GetDivergenceSource(15));
  EXPECT_EQ(14, divergence_->GetDivergenceDependenceSource(15));

  // These two blocks are outside the if but are still control dependent.
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(16));
  EXPECT_EQ(12, divergence_->GetDivergenceSource(16));
  EXPECT_EQ(14, divergence_->GetDivergenceDependenceSource(16));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(17));
  EXPECT_EQ(12, divergence_->GetDivergenceSource(17));
  EXPECT_EQ(14, divergence_->GetDivergenceDependenceSource(17));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(18));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(19));
}

TEST_F(DivergenceTest, ReconvergencePromotionTest) {
  // pseudocode:
  // %10:
  // %11 = load y
  // %12 = %11 < 0
  // if (%12) {
  //   %13:
  //   %14:
  //   %15:
  //   if (true) {
  //     %16:
  //   }
  //   // Reconvergence *not* guaranteed as
  //   // control is not uniform on the IG level
  //   // at %15.
  //   %17:
  //   %18:
  //   %19:
  //   %20 = load x
  // }
  // %21:
  // %22 = phi(%11, %20)
  // return
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %11 = OpLoad %float %y
         %12 = OpFOrdLessThan %bool %11 %zero
               OpSelectionMerge %21 None
               OpBranchConditional %12 %13 %21
         %13 = OpLabel
               OpBranch %14
         %14 = OpLabel
               OpBranch %15
         %15 = OpLabel
               OpSelectionMerge %17 None
               OpBranchConditional %true %16 %17
         %16 = OpLabel
               OpBranch %17
         %17 = OpLabel
               OpBranch %18
         %18 = OpLabel
               OpBranch %19
         %19 = OpLabel
         %20 = OpLoad %float %y
               OpBranch %21
         %21 = OpLabel
         %22 = OpPhi %float %11 %10 %20 %19
               OpReturn
               OpFunctionEnd
  )"));
  ASSERT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
  ASSERT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(21));

  ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(11));
  ASSERT_EQ(0, divergence_->GetDivergenceSource(11));
  ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(12));
  ASSERT_EQ(11, divergence_->GetDivergenceSource(12));
  ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(13));
  ASSERT_EQ(12, divergence_->GetDivergenceSource(13));
  ASSERT_EQ(10, divergence_->GetDivergenceDependenceSource(13));
  ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(14));
  ASSERT_EQ(12, divergence_->GetDivergenceSource(14));
  ASSERT_EQ(10, divergence_->GetDivergenceDependenceSource(14));
  ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(15));
  ASSERT_EQ(12, divergence_->GetDivergenceSource(15));
  ASSERT_EQ(10, divergence_->GetDivergenceDependenceSource(15));
  ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(16));
  ASSERT_EQ(15, divergence_->GetDivergenceSource(16));

  ASSERT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(17));
  ASSERT_EQ(12, divergence_->GetDivergenceSource(17));
  ASSERT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(18));
  ASSERT_EQ(12, divergence_->GetDivergenceSource(18));
  ASSERT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(19));
  ASSERT_EQ(12, divergence_->GetDivergenceSource(19));

  ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(20));
  ASSERT_EQ(0, divergence_->GetDivergenceSource(20));
  ASSERT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(22));
  ASSERT_EQ(19, divergence_->GetDivergenceSource(22));
  ASSERT_EQ(10, divergence_->GetDivergenceDependenceSource(15));
}

TEST_F(DivergenceTest, FunctionCallTest) {
  // pseudocode:
  // %2() {
  //   %20:
  //   %21 = load x
  //   %22 = %21 < 0
  //   if (%22) {
  //     %23:
  //     return
  //   }
  //   %24:
  //   return
  // }
  //
  // main() {
  //   %10:
  //   %11 = %2();
  //   // Reconvergence *not* guaranteed.
  //   %12:
  //   return
  // }
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %11 = OpFunctionCall %void %2
               OpBranch %12
         %12 = OpLabel
               OpReturn
               OpFunctionEnd

          %2 = OpFunction %void None %void_f
         %20 = OpLabel
         %21 = OpLoad %float %x
         %22 = OpFOrdLessThan %bool %21 %zero
               OpSelectionMerge %24 None
               OpBranchConditional %22 %23 %24
         %23 = OpLabel
               OpReturn
         %24 = OpLabel
               OpReturn
               OpFunctionEnd
  )"));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
  // Conservatively assume function return value is uniform.
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(11));
  // TODO(dongja): blocks reachable from diverging function calls should be
  // divergent.
  // EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(12));  // Wrong!
}

TEST_F(DivergenceTest, LateMergeTest) {
  // pseudocode:
  // %10:
  // %11 = load y
  // %12 = %11 < 0
  // [merge: %15]
  // if (%12) {
  //   %13:
  // }
  // %14: // Reconvergence hasn't happened by here.
  // %15:
  // return
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %11 = OpLoad %float %x
         %12 = OpFOrdLessThan %bool %11 %zero
               OpSelectionMerge %15 None
               OpBranchConditional %12 %13 %14
         %13 = OpLabel
               OpBranch %14
         %14 = OpLabel
               OpBranch %15
         %15 = OpLabel
               OpReturn
               OpFunctionEnd
  )"));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
  // TODO(dongja):
  // EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(14));  // Wrong!
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(15));
}

// The following series of tests makes sure that we find the least fixpoint.
TEST_F(DivergenceTest, UniformFixpointTest) {
  // pseudocode:
  //   %10:
  //   %20 = load x
  //   %21 = load y
  //   do {
  //     %11:
  //     %12:
  //     %13 = phi(%zero from %11, %14 from %16)
  //     %14 = %13 + 1
  //     %15 = %13 < 1
  //   } %16: while (%15)
  //   %17:
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %20 = OpLoad %float %x
         %21 = OpLoad %float %y
               OpBranch %11
         %11 = OpLabel
         %13 = OpPhi %float %zero %10 %14 %16
               OpLoopMerge %17 %16 None
               OpBranch %12
         %12 = OpLabel
         %14 = OpFAdd %float %13 %one
         %15 = OpFOrdLessThan %bool %13 %one
               OpBranch %16
         %16 = OpLabel
               OpBranchConditional %15 %11 %17
         %17 = OpLabel
               OpReturn
               OpFunctionEnd
  )"));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(11));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(13));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(14));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(15));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(16));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
}

TEST_F(DivergenceTest, PartiallyUniformFixpointTest) {
  // pseudocode:
  //   %10:
  //   %20 = load x
  //   %21 = load y
  //   do {
  //     %11:
  //     %12:
  //     %13 = phi(%zero from %11, %14 from %16)
  //     %14 = %13 + 1
  //     %15 = %13 < %21
  //   } %16: while (%15)
  //   %17:
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %20 = OpLoad %float %x
         %21 = OpLoad %float %y
               OpBranch %11
         %11 = OpLabel
         %13 = OpPhi %float %zero %10 %14 %16
               OpLoopMerge %17 %16 None
               OpBranch %12
         %12 = OpLabel
         %14 = OpFAdd %float %13 %one
         %15 = OpFOrdLessThan %bool %13 %21
               OpBranch %16
         %16 = OpLabel
               OpBranchConditional %15 %11 %17
         %17 = OpLabel
               OpReturn
               OpFunctionEnd
  )"));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
  EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(11));
  EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(13));
  EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(14));
  EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(15));
  EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(16));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
}

TEST_F(DivergenceTest, DivergentFixpointTest) {
  // pseudocode:
  //   %10:
  //   %20 = load x
  //   %21 = load y
  //   do {
  //     %11:
  //     %12:
  //     %13 = phi(%zero from %11, %14 from %16)
  //     %14 = %13 + 1
  //     %15 = %13 < %20
  //   } %16: while (%15)
  //   %17:
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %20 = OpLoad %float %x
         %21 = OpLoad %float %y
               OpBranch %11
         %11 = OpLabel
         %13 = OpPhi %float %zero %10 %14 %16
               OpLoopMerge %17 %16 None
               OpBranch %12
         %12 = OpLabel
         %14 = OpFAdd %float %13 %one
         %15 = OpFOrdLessThan %bool %13 %20
               OpBranch %16
         %16 = OpLabel
               OpBranchConditional %15 %11 %17
         %17 = OpLabel
               OpReturn
               OpFunctionEnd
  )"));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(16));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
}

TEST_F(DivergenceTest, DivergentOverridesPartiallyUniformTest) {
  // pseudocode:
  //   %10:
  //   %20 = load x
  //   %21 = load y
  //   %11:
  //   do {
  //     %12:
  //     %13 = phi(%21 from %11, %14 from %16)
  //     %14 = %13 + 1
  //     %15 = %13 < %20
  //   } %16: while (%15)
  //   %17:
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %20 = OpLoad %float %x
         %21 = OpLoad %float %y
               OpBranch %11
         %11 = OpLabel
         %13 = OpPhi %float %zero %10 %14 %16
               OpLoopMerge %17 %16 None
               OpBranch %12
         %12 = OpLabel
         %14 = OpFAdd %float %13 %one
         %15 = OpFOrdLessThan %bool %13 %20
               OpBranch %16
         %16 = OpLabel
               OpBranchConditional %15 %11 %17
         %17 = OpLabel
               OpReturn
               OpFunctionEnd
  )"));

  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(16));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
}

TEST_F(DivergenceTest, NestedFixpointTest) {
  // pseudocode:
  //   %10:
  //   %20 = load x
  //   %21 = load y
  //   do {
  //     %22:
  //     %23:
  //     %24 = phi(%zero from %22, %25 from %26)
  //     %11:
  //     do {
  //       %12:
  //       %13 = phi(%zero from %11, %14 from %16)
  //       %14 = %13 + 1
  //       %15 = %13 < %24
  //     } %16: while (%15)
  //     %17:
  //     %25 = load x
  //   } %26: while (false)
  //   %27:
  //   return
  ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
         %10 = OpLabel
         %20 = OpLoad %float %x
         %21 = OpLoad %float %y
               OpBranch %22
         %22 = OpLabel
         %24 = OpPhi %float %zero %10 %25 %26
               OpLoopMerge %27 %26 None
               OpBranch %23
         %23 = OpLabel
               OpBranch %11
         %11 = OpLabel
         %13 = OpPhi %float %zero %23 %14 %16
               OpLoopMerge %17 %16 None
               OpBranch %12
         %12 = OpLabel
         %14 = OpFAdd %float %13 %one
         %15 = OpFOrdLessThan %bool %13 %24
               OpBranch %16
         %16 = OpLabel
               OpBranchConditional %15 %11 %17
         %17 = OpLabel
         %25 = OpLoad %float %x
               OpBranch %26
         %26 = OpLabel
               OpBranchConditional %false %22 %27
         %27 = OpLabel
               OpReturn
               OpFunctionEnd
  )"));
  // This test makes sure that divergent values flowing upward can influence the
  // fixpoint of a loop.
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(16));
  // Control of the outer loop is still uniform.
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(22));
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(23));
  // Seed divergent values.
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(24));
  EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(25));
  // Outer loop control.
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(26));
  // Merged.
  EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(27));
}

}  // namespace
}  // namespace lint
}  // namespace spvtools