third_party/SPIRV-Tools/test/opt/loop_optimizations/nested_loops.cpp - platform/external/swiftshader - Git at Google

 // 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 <memory>
 #include <string>
 #include <unordered_set>
 #include <vector>

 #include "gmock/gmock.h"
 #include "source/opt/iterator.h"
 #include "source/opt/loop_descriptor.h"
 #include "source/opt/pass.h"
 #include "source/opt/tree_iterator.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;

 bool Validate(const std::vector<uint32_t>& bin) {
   spv_target_env target_env = SPV_ENV_UNIVERSAL_1_2;
   spv_context spvContext = spvContextCreate(target_env);
   spv_diagnostic diagnostic = nullptr;
   spv_const_binary_t binary = {bin.data(), bin.size()};
   spv_result_t error = spvValidate(spvContext, &binary, &diagnostic);
   if (error != 0) spvDiagnosticPrint(diagnostic);
   spvDiagnosticDestroy(diagnostic);
   spvContextDestroy(spvContext);
   return error == 0;
 }

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

 /*
 Generated from the following GLSL
 #version 330 core
 layout(location = 0) out vec4 c;
 void main() {
   int i = 0;
   for (; i < 10; ++i) {
     int j = 0;
     int k = 0;
     for (; j < 11; ++j) {}
     for (; k < 12; ++k) {}
   }
 }
 */
 TEST_F(PassClassTest, BasicVisitFromEntryPoint) {
   const std::string text = R"(
                OpCapability Shader
           %1 = OpExtInstImport "GLSL.std.450"
                OpMemoryModel Logical GLSL450
                OpEntryPoint Fragment %2 "main" %3
                OpExecutionMode %2 OriginUpperLeft
                OpSource GLSL 330
                OpName %2 "main"
                OpName %4 "i"
                OpName %5 "j"
                OpName %6 "k"
                OpName %3 "c"
                OpDecorate %3 Location 0
           %7 = OpTypeVoid
           %8 = OpTypeFunction %7
           %9 = OpTypeInt 32 1
          %10 = OpTypePointer Function %9
          %11 = OpConstant %9 0
          %12 = OpConstant %9 10
          %13 = OpTypeBool
          %14 = OpConstant %9 11
          %15 = OpConstant %9 1
          %16 = OpConstant %9 12
          %17 = OpTypeFloat 32
          %18 = OpTypeVector %17 4
          %19 = OpTypePointer Output %18
           %3 = OpVariable %19 Output
           %2 = OpFunction %7 None %8
          %20 = OpLabel
           %4 = OpVariable %10 Function
           %5 = OpVariable %10 Function
           %6 = OpVariable %10 Function
                OpStore %4 %11
                OpBranch %21
          %21 = OpLabel
                OpLoopMerge %22 %23 None
                OpBranch %24
          %24 = OpLabel
          %25 = OpLoad %9 %4
          %26 = OpSLessThan %13 %25 %12
                OpBranchConditional %26 %27 %22
          %27 = OpLabel
                OpStore %5 %11
                OpStore %6 %11
                OpBranch %28
          %28 = OpLabel
                OpLoopMerge %29 %30 None
                OpBranch %31
          %31 = OpLabel
          %32 = OpLoad %9 %5
          %33 = OpSLessThan %13 %32 %14
                OpBranchConditional %33 %34 %29
          %34 = OpLabel
                OpBranch %30
          %30 = OpLabel
          %35 = OpLoad %9 %5
          %36 = OpIAdd %9 %35 %15
                OpStore %5 %36
                OpBranch %28
          %29 = OpLabel
                OpBranch %37
          %37 = OpLabel
                OpLoopMerge %38 %39 None
                OpBranch %40
          %40 = OpLabel
          %41 = OpLoad %9 %6
          %42 = OpSLessThan %13 %41 %16
                OpBranchConditional %42 %43 %38
          %43 = OpLabel
                OpBranch %39
          %39 = OpLabel
          %44 = OpLoad %9 %6
          %45 = OpIAdd %9 %44 %15
                OpStore %6 %45
                OpBranch %37
          %38 = OpLabel
                OpBranch %23
          %23 = OpLabel
          %46 = OpLoad %9 %4
          %47 = OpIAdd %9 %46 %15
                OpStore %4 %47
                OpBranch %21
          %22 = OpLabel
                OpReturn
                OpFunctionEnd
   )";
   // clang-format on
   std::unique_ptr<IRContext> context =
       BuildModule(SPV_ENV_UNIVERSAL_1_1, 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* f = spvtest::GetFunction(module, 2);
   LoopDescriptor& ld = *context->GetLoopDescriptor(f);

   EXPECT_EQ(ld.NumLoops(), 3u);

   // Invalid basic block id.
   EXPECT_EQ(ld[0u], nullptr);
   // Not a loop header.
   EXPECT_EQ(ld[20], nullptr);

   Loop& parent_loop = *ld[21];
   EXPECT_TRUE(parent_loop.HasNestedLoops());
   EXPECT_FALSE(parent_loop.IsNested());
   EXPECT_EQ(parent_loop.GetDepth(), 1u);
   EXPECT_EQ(std::distance(parent_loop.begin(), parent_loop.end()), 2u);
   EXPECT_EQ(parent_loop.GetHeaderBlock(), spvtest::GetBasicBlock(f, 21));
   EXPECT_EQ(parent_loop.GetLatchBlock(), spvtest::GetBasicBlock(f, 23));
   EXPECT_EQ(parent_loop.GetMergeBlock(), spvtest::GetBasicBlock(f, 22));

   Loop& child_loop_1 = *ld[28];
   EXPECT_FALSE(child_loop_1.HasNestedLoops());
   EXPECT_TRUE(child_loop_1.IsNested());
   EXPECT_EQ(child_loop_1.GetDepth(), 2u);
   EXPECT_EQ(std::distance(child_loop_1.begin(), child_loop_1.end()), 0u);
   EXPECT_EQ(child_loop_1.GetHeaderBlock(), spvtest::GetBasicBlock(f, 28));
   EXPECT_EQ(child_loop_1.GetLatchBlock(), spvtest::GetBasicBlock(f, 30));
   EXPECT_EQ(child_loop_1.GetMergeBlock(), spvtest::GetBasicBlock(f, 29));

   Loop& child_loop_2 = *ld[37];
   EXPECT_FALSE(child_loop_2.HasNestedLoops());
   EXPECT_TRUE(child_loop_2.IsNested());
   EXPECT_EQ(child_loop_2.GetDepth(), 2u);
   EXPECT_EQ(std::distance(child_loop_2.begin(), child_loop_2.end()), 0u);
   EXPECT_EQ(child_loop_2.GetHeaderBlock(), spvtest::GetBasicBlock(f, 37));
   EXPECT_EQ(child_loop_2.GetLatchBlock(), spvtest::GetBasicBlock(f, 39));
   EXPECT_EQ(child_loop_2.GetMergeBlock(), spvtest::GetBasicBlock(f, 38));
 }

 static void CheckLoopBlocks(Loop* loop,
                             std::unordered_set<uint32_t>* expected_ids) {
   SCOPED_TRACE("Check loop " + std::to_string(loop->GetHeaderBlock()->id()));
   for (uint32_t bb_id : loop->GetBlocks()) {
     EXPECT_EQ(expected_ids->count(bb_id), 1u);
     expected_ids->erase(bb_id);
   }
   EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
   EXPECT_EQ(expected_ids->size(), 0u);
 }

 /*
 Generated from the following GLSL
 #version 330 core
 layout(location = 0) out vec4 c;
 void main() {
   int i = 0;
   for (; i < 10; ++i) {
     for (int j = 0; j < 11; ++j) {
       if (j < 5) {
         for (int k = 0; k < 12; ++k) {}
       }
       else {}
       for (int k = 0; k < 12; ++k) {}
     }
   }
 }*/
 TEST_F(PassClassTest, TripleNestedLoop) {
   const std::string text = R"(
                OpCapability Shader
           %1 = OpExtInstImport "GLSL.std.450"
                OpMemoryModel Logical GLSL450
                OpEntryPoint Fragment %2 "main" %3
                OpExecutionMode %2 OriginUpperLeft
                OpSource GLSL 330
                OpName %2 "main"
                OpName %4 "i"
                OpName %5 "j"
                OpName %6 "k"
                OpName %7 "k"
                OpName %3 "c"
                OpDecorate %3 Location 0
           %8 = OpTypeVoid
           %9 = OpTypeFunction %8
          %10 = OpTypeInt 32 1
          %11 = OpTypePointer Function %10
          %12 = OpConstant %10 0
          %13 = OpConstant %10 10
          %14 = OpTypeBool
          %15 = OpConstant %10 11
          %16 = OpConstant %10 5
          %17 = OpConstant %10 12
          %18 = OpConstant %10 1
          %19 = OpTypeFloat 32
          %20 = OpTypeVector %19 4
          %21 = OpTypePointer Output %20
           %3 = OpVariable %21 Output
           %2 = OpFunction %8 None %9
          %22 = OpLabel
           %4 = OpVariable %11 Function
           %5 = OpVariable %11 Function
           %6 = OpVariable %11 Function
           %7 = OpVariable %11 Function
                OpStore %4 %12
                OpBranch %23
          %23 = OpLabel
                OpLoopMerge %24 %25 None
                OpBranch %26
          %26 = OpLabel
          %27 = OpLoad %10 %4
          %28 = OpSLessThan %14 %27 %13
                OpBranchConditional %28 %29 %24
          %29 = OpLabel
                OpStore %5 %12
                OpBranch %30
          %30 = OpLabel
                OpLoopMerge %31 %32 None
                OpBranch %33
          %33 = OpLabel
          %34 = OpLoad %10 %5
          %35 = OpSLessThan %14 %34 %15
                OpBranchConditional %35 %36 %31
          %36 = OpLabel
          %37 = OpLoad %10 %5
          %38 = OpSLessThan %14 %37 %16
                OpSelectionMerge %39 None
                OpBranchConditional %38 %40 %39
          %40 = OpLabel
                OpStore %6 %12
                OpBranch %41
          %41 = OpLabel
                OpLoopMerge %42 %43 None
                OpBranch %44
          %44 = OpLabel
          %45 = OpLoad %10 %6
          %46 = OpSLessThan %14 %45 %17
                OpBranchConditional %46 %47 %42
          %47 = OpLabel
                OpBranch %43
          %43 = OpLabel
          %48 = OpLoad %10 %6
          %49 = OpIAdd %10 %48 %18
                OpStore %6 %49
                OpBranch %41
          %42 = OpLabel
                OpBranch %39
          %39 = OpLabel
                OpStore %7 %12
                OpBranch %50
          %50 = OpLabel
                OpLoopMerge %51 %52 None
                OpBranch %53
          %53 = OpLabel
          %54 = OpLoad %10 %7
          %55 = OpSLessThan %14 %54 %17
                OpBranchConditional %55 %56 %51
          %56 = OpLabel
                OpBranch %52
          %52 = OpLabel
          %57 = OpLoad %10 %7
          %58 = OpIAdd %10 %57 %18
                OpStore %7 %58
                OpBranch %50
          %51 = OpLabel
                OpBranch %32
          %32 = OpLabel
          %59 = OpLoad %10 %5
          %60 = OpIAdd %10 %59 %18
                OpStore %5 %60
                OpBranch %30
          %31 = OpLabel
                OpBranch %25
          %25 = OpLabel
          %61 = OpLoad %10 %4
          %62 = OpIAdd %10 %61 %18
                OpStore %4 %62
                OpBranch %23
          %24 = OpLabel
                OpReturn
                OpFunctionEnd
   )";
   // clang-format on
   std::unique_ptr<IRContext> context =
       BuildModule(SPV_ENV_UNIVERSAL_1_1, 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* f = spvtest::GetFunction(module, 2);
   LoopDescriptor& ld = *context->GetLoopDescriptor(f);

   EXPECT_EQ(ld.NumLoops(), 4u);

   // Invalid basic block id.
   EXPECT_EQ(ld[0u], nullptr);
   // Not in a loop.
   EXPECT_EQ(ld[22], nullptr);

   // Check that we can map basic block to the correct loop.
   // The following block ids do not belong to a loop.
   for (uint32_t bb_id : {22, 24}) EXPECT_EQ(ld[bb_id], nullptr);

   {
     std::unordered_set<uint32_t> basic_block_in_loop = {
         {23, 26, 29, 30, 33, 36, 40, 41, 44, 47, 43,
          42, 39, 50, 53, 56, 52, 51, 32, 31, 25}};
     Loop* loop = ld[23];
     CheckLoopBlocks(loop, &basic_block_in_loop);

     EXPECT_TRUE(loop->HasNestedLoops());
     EXPECT_FALSE(loop->IsNested());
     EXPECT_EQ(loop->GetDepth(), 1u);
     EXPECT_EQ(std::distance(loop->begin(), loop->end()), 1u);
     EXPECT_EQ(loop->GetPreHeaderBlock(), spvtest::GetBasicBlock(f, 22));
     EXPECT_EQ(loop->GetHeaderBlock(), spvtest::GetBasicBlock(f, 23));
     EXPECT_EQ(loop->GetLatchBlock(), spvtest::GetBasicBlock(f, 25));
     EXPECT_EQ(loop->GetMergeBlock(), spvtest::GetBasicBlock(f, 24));
     EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
     EXPECT_FALSE(loop->IsInsideLoop(loop->GetPreHeaderBlock()));
   }

   {
     std::unordered_set<uint32_t> basic_block_in_loop = {
         {30, 33, 36, 40, 41, 44, 47, 43, 42, 39, 50, 53, 56, 52, 51, 32}};
     Loop* loop = ld[30];
     CheckLoopBlocks(loop, &basic_block_in_loop);

     EXPECT_TRUE(loop->HasNestedLoops());
     EXPECT_TRUE(loop->IsNested());
     EXPECT_EQ(loop->GetDepth(), 2u);
     EXPECT_EQ(std::distance(loop->begin(), loop->end()), 2u);
     EXPECT_EQ(loop->GetPreHeaderBlock(), spvtest::GetBasicBlock(f, 29));
     EXPECT_EQ(loop->GetHeaderBlock(), spvtest::GetBasicBlock(f, 30));
     EXPECT_EQ(loop->GetLatchBlock(), spvtest::GetBasicBlock(f, 32));
     EXPECT_EQ(loop->GetMergeBlock(), spvtest::GetBasicBlock(f, 31));
     EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
     EXPECT_FALSE(loop->IsInsideLoop(loop->GetPreHeaderBlock()));
   }

   {
     std::unordered_set<uint32_t> basic_block_in_loop = {{41, 44, 47, 43}};
     Loop* loop = ld[41];
     CheckLoopBlocks(loop, &basic_block_in_loop);

     EXPECT_FALSE(loop->HasNestedLoops());
     EXPECT_TRUE(loop->IsNested());
     EXPECT_EQ(loop->GetDepth(), 3u);
     EXPECT_EQ(std::distance(loop->begin(), loop->end()), 0u);
     EXPECT_EQ(loop->GetPreHeaderBlock(), spvtest::GetBasicBlock(f, 40));
     EXPECT_EQ(loop->GetHeaderBlock(), spvtest::GetBasicBlock(f, 41));
     EXPECT_EQ(loop->GetLatchBlock(), spvtest::GetBasicBlock(f, 43));
     EXPECT_EQ(loop->GetMergeBlock(), spvtest::GetBasicBlock(f, 42));
     EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
     EXPECT_FALSE(loop->IsInsideLoop(loop->GetPreHeaderBlock()));
   }

   {
     std::unordered_set<uint32_t> basic_block_in_loop = {{50, 53, 56, 52}};
     Loop* loop = ld[50];
     CheckLoopBlocks(loop, &basic_block_in_loop);

     EXPECT_FALSE(loop->HasNestedLoops());
     EXPECT_TRUE(loop->IsNested());
     EXPECT_EQ(loop->GetDepth(), 3u);
     EXPECT_EQ(std::distance(loop->begin(), loop->end()), 0u);
     EXPECT_EQ(loop->GetPreHeaderBlock(), spvtest::GetBasicBlock(f, 39));
     EXPECT_EQ(loop->GetHeaderBlock(), spvtest::GetBasicBlock(f, 50));
     EXPECT_EQ(loop->GetLatchBlock(), spvtest::GetBasicBlock(f, 52));
     EXPECT_EQ(loop->GetMergeBlock(), spvtest::GetBasicBlock(f, 51));
     EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
     EXPECT_FALSE(loop->IsInsideLoop(loop->GetPreHeaderBlock()));
   }

   // Make sure LoopDescriptor gives us the inner most loop when we query for
   // loops.
   for (const BasicBlock& bb : *f) {
     if (Loop* loop = ld[&bb]) {
       for (Loop& sub_loop :
            make_range(++TreeDFIterator<Loop>(loop), TreeDFIterator<Loop>())) {
         EXPECT_FALSE(sub_loop.IsInsideLoop(bb.id()));
       }
     }
   }
 }

 /*
 Generated from the following GLSL
 #version 330 core
 layout(location = 0) out vec4 c;
 void main() {
   for (int i = 0; i < 10; ++i) {
     for (int j = 0; j < 11; ++j) {
       for (int k = 0; k < 11; ++k) {}
     }
     for (int k = 0; k < 12; ++k) {}
   }
 }
 */
 TEST_F(PassClassTest, LoopParentTest) {
   const std::string text = R"(
                OpCapability Shader
           %1 = OpExtInstImport "GLSL.std.450"
                OpMemoryModel Logical GLSL450
                OpEntryPoint Fragment %2 "main" %3
                OpExecutionMode %2 OriginUpperLeft
                OpSource GLSL 330
                OpName %2 "main"
                OpName %4 "i"
                OpName %5 "j"
                OpName %6 "k"
                OpName %7 "k"
                OpName %3 "c"
                OpDecorate %3 Location 0
           %8 = OpTypeVoid
           %9 = OpTypeFunction %8
          %10 = OpTypeInt 32 1
          %11 = OpTypePointer Function %10
          %12 = OpConstant %10 0
          %13 = OpConstant %10 10
          %14 = OpTypeBool
          %15 = OpConstant %10 11
          %16 = OpConstant %10 1
          %17 = OpConstant %10 12
          %18 = OpTypeFloat 32
          %19 = OpTypeVector %18 4
          %20 = OpTypePointer Output %19
           %3 = OpVariable %20 Output
           %2 = OpFunction %8 None %9
          %21 = OpLabel
           %4 = OpVariable %11 Function
           %5 = OpVariable %11 Function
           %6 = OpVariable %11 Function
           %7 = OpVariable %11 Function
                OpStore %4 %12
                OpBranch %22
          %22 = OpLabel
                OpLoopMerge %23 %24 None
                OpBranch %25
          %25 = OpLabel
          %26 = OpLoad %10 %4
          %27 = OpSLessThan %14 %26 %13
                OpBranchConditional %27 %28 %23
          %28 = OpLabel
                OpStore %5 %12
                OpBranch %29
          %29 = OpLabel
                OpLoopMerge %30 %31 None
                OpBranch %32
          %32 = OpLabel
          %33 = OpLoad %10 %5
          %34 = OpSLessThan %14 %33 %15
                OpBranchConditional %34 %35 %30
          %35 = OpLabel
                OpStore %6 %12
                OpBranch %36
          %36 = OpLabel
                OpLoopMerge %37 %38 None
                OpBranch %39
          %39 = OpLabel
          %40 = OpLoad %10 %6
          %41 = OpSLessThan %14 %40 %15
                OpBranchConditional %41 %42 %37
          %42 = OpLabel
                OpBranch %38
          %38 = OpLabel
          %43 = OpLoad %10 %6
          %44 = OpIAdd %10 %43 %16
                OpStore %6 %44
                OpBranch %36
          %37 = OpLabel
                OpBranch %31
          %31 = OpLabel
          %45 = OpLoad %10 %5
          %46 = OpIAdd %10 %45 %16
                OpStore %5 %46
                OpBranch %29
          %30 = OpLabel
                OpStore %7 %12
                OpBranch %47
          %47 = OpLabel
                OpLoopMerge %48 %49 None
                OpBranch %50
          %50 = OpLabel
          %51 = OpLoad %10 %7
          %52 = OpSLessThan %14 %51 %17
                OpBranchConditional %52 %53 %48
          %53 = OpLabel
                OpBranch %49
          %49 = OpLabel
          %54 = OpLoad %10 %7
          %55 = OpIAdd %10 %54 %16
                OpStore %7 %55
                OpBranch %47
          %48 = OpLabel
                OpBranch %24
          %24 = OpLabel
          %56 = OpLoad %10 %4
          %57 = OpIAdd %10 %56 %16
                OpStore %4 %57
                OpBranch %22
          %23 = OpLabel
                OpReturn
                OpFunctionEnd
   )";
   // clang-format on
   std::unique_ptr<IRContext> context =
       BuildModule(SPV_ENV_UNIVERSAL_1_1, 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* f = spvtest::GetFunction(module, 2);
   LoopDescriptor& ld = *context->GetLoopDescriptor(f);

   EXPECT_EQ(ld.NumLoops(), 4u);

   {
     Loop& loop = *ld[22];
     EXPECT_TRUE(loop.HasNestedLoops());
     EXPECT_FALSE(loop.IsNested());
     EXPECT_EQ(loop.GetDepth(), 1u);
     EXPECT_EQ(loop.GetParent(), nullptr);
   }

   {
     Loop& loop = *ld[29];
     EXPECT_TRUE(loop.HasNestedLoops());
     EXPECT_TRUE(loop.IsNested());
     EXPECT_EQ(loop.GetDepth(), 2u);
     EXPECT_EQ(loop.GetParent(), ld[22]);
   }

   {
     Loop& loop = *ld[36];
     EXPECT_FALSE(loop.HasNestedLoops());
     EXPECT_TRUE(loop.IsNested());
     EXPECT_EQ(loop.GetDepth(), 3u);
     EXPECT_EQ(loop.GetParent(), ld[29]);
   }

   {
     Loop& loop = *ld[47];
     EXPECT_FALSE(loop.HasNestedLoops());
     EXPECT_TRUE(loop.IsNested());
     EXPECT_EQ(loop.GetDepth(), 2u);
     EXPECT_EQ(loop.GetParent(), ld[22]);
   }
 }

 /*
 Generated from the following GLSL + --eliminate-local-multi-store
 The preheader of loop %33 and %41 were removed as well.

 #version 330 core
 void main() {
   int a = 0;
   for (int i = 0; i < 10; ++i) {
     if (i == 0) {
       a = 1;
     } else {
       a = 2;
     }
     for (int j = 0; j < 11; ++j) {
       a++;
     }
   }
   for (int k = 0; k < 12; ++k) {}
 }
 */
 TEST_F(PassClassTest, CreatePreheaderTest) {
   const std::string text = R"(
                OpCapability Shader
           %1 = OpExtInstImport "GLSL.std.450"
                OpMemoryModel Logical GLSL450
                OpEntryPoint Fragment %2 "main"
                OpExecutionMode %2 OriginUpperLeft
                OpSource GLSL 330
                OpName %2 "main"
           %3 = OpTypeVoid
           %4 = OpTypeFunction %3
           %5 = OpTypeInt 32 1
           %6 = OpTypePointer Function %5
           %7 = OpConstant %5 0
           %8 = OpConstant %5 10
           %9 = OpTypeBool
          %10 = OpConstant %5 1
          %11 = OpConstant %5 2
          %12 = OpConstant %5 11
          %13 = OpConstant %5 12
          %14 = OpUndef %5
           %2 = OpFunction %3 None %4
          %15 = OpLabel
                OpBranch %16
          %16 = OpLabel
          %17 = OpPhi %5 %7 %15 %18 %19
          %20 = OpPhi %5 %7 %15 %21 %19
          %22 = OpPhi %5 %14 %15 %23 %19
                OpLoopMerge %41 %19 None
                OpBranch %25
          %25 = OpLabel
          %26 = OpSLessThan %9 %20 %8
                OpBranchConditional %26 %27 %41
          %27 = OpLabel
          %28 = OpIEqual %9 %20 %7
                OpSelectionMerge %33 None
                OpBranchConditional %28 %30 %31
          %30 = OpLabel
                OpBranch %33
          %31 = OpLabel
                OpBranch %33
          %33 = OpLabel
          %18 = OpPhi %5 %10 %30 %11 %31 %34 %35
          %23 = OpPhi %5 %7 %30 %7 %31 %36 %35
                OpLoopMerge %37 %35 None
                OpBranch %38
          %38 = OpLabel
          %39 = OpSLessThan %9 %23 %12
                OpBranchConditional %39 %40 %37
          %40 = OpLabel
          %34 = OpIAdd %5 %18 %10
                OpBranch %35
          %35 = OpLabel
          %36 = OpIAdd %5 %23 %10
                OpBranch %33
          %37 = OpLabel
                OpBranch %19
          %19 = OpLabel
          %21 = OpIAdd %5 %20 %10
                OpBranch %16
          %41 = OpLabel
          %42 = OpPhi %5 %7 %25 %43 %44
                OpLoopMerge %45 %44 None
                OpBranch %46
          %46 = OpLabel
          %47 = OpSLessThan %9 %42 %13
                OpBranchConditional %47 %48 %45
          %48 = OpLabel
                OpBranch %44
          %44 = OpLabel
          %43 = OpIAdd %5 %42 %10
                OpBranch %41
          %45 = OpLabel
                OpReturn
                OpFunctionEnd
   )";
   // clang-format on
   std::unique_ptr<IRContext> context =
       BuildModule(SPV_ENV_UNIVERSAL_1_1, 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* f = spvtest::GetFunction(module, 2);
   LoopDescriptor& ld = *context->GetLoopDescriptor(f);
   // No invalidation of the cfg should occur during this test.
   CFG* cfg = context->cfg();

   EXPECT_EQ(ld.NumLoops(), 3u);

   {
     Loop& loop = *ld[16];
     EXPECT_TRUE(loop.HasNestedLoops());
     EXPECT_FALSE(loop.IsNested());
     EXPECT_EQ(loop.GetDepth(), 1u);
     EXPECT_EQ(loop.GetParent(), nullptr);
   }

   {
     Loop& loop = *ld[33];
     EXPECT_EQ(loop.GetPreHeaderBlock(), nullptr);
     EXPECT_NE(loop.GetOrCreatePreHeaderBlock(), nullptr);
     // Make sure the loop descriptor was properly updated.
     EXPECT_EQ(ld[loop.GetPreHeaderBlock()], ld[16]);
     {
       const std::vector<uint32_t>& preds =
           cfg->preds(loop.GetPreHeaderBlock()->id());
       std::unordered_set<uint32_t> pred_set(preds.begin(), preds.end());
       EXPECT_EQ(pred_set.size(), 2u);
       EXPECT_TRUE(pred_set.count(30));
       EXPECT_TRUE(pred_set.count(31));
       // Check the phi instructions.
       loop.GetPreHeaderBlock()->ForEachPhiInst([&pred_set](Instruction* phi) {
         for (uint32_t i = 1; i < phi->NumInOperands(); i += 2) {
           EXPECT_TRUE(pred_set.count(phi->GetSingleWordInOperand(i)));
         }
       });
     }
     {
       const std::vector<uint32_t>& preds =
           cfg->preds(loop.GetHeaderBlock()->id());
       std::unordered_set<uint32_t> pred_set(preds.begin(), preds.end());
       EXPECT_EQ(pred_set.size(), 2u);
       EXPECT_TRUE(pred_set.count(loop.GetPreHeaderBlock()->id()));
       EXPECT_TRUE(pred_set.count(35));
       // Check the phi instructions.
       loop.GetHeaderBlock()->ForEachPhiInst([&pred_set](Instruction* phi) {
         for (uint32_t i = 1; i < phi->NumInOperands(); i += 2) {
           EXPECT_TRUE(pred_set.count(phi->GetSingleWordInOperand(i)));
         }
       });
     }
   }

   {
     Loop& loop = *ld[41];
     EXPECT_EQ(loop.GetPreHeaderBlock(), nullptr);
     EXPECT_NE(loop.GetOrCreatePreHeaderBlock(), nullptr);
     EXPECT_EQ(ld[loop.GetPreHeaderBlock()], nullptr);
     EXPECT_EQ(cfg->preds(loop.GetPreHeaderBlock()->id()).size(), 1u);
     EXPECT_EQ(cfg->preds(loop.GetPreHeaderBlock()->id())[0], 25u);
     // Check the phi instructions.
     loop.GetPreHeaderBlock()->ForEachPhiInst([](Instruction* phi) {
       EXPECT_EQ(phi->NumInOperands(), 2u);
       EXPECT_EQ(phi->GetSingleWordInOperand(1), 25u);
     });
     {
       const std::vector<uint32_t>& preds =
           cfg->preds(loop.GetHeaderBlock()->id());
       std::unordered_set<uint32_t> pred_set(preds.begin(), preds.end());
       EXPECT_EQ(pred_set.size(), 2u);
       EXPECT_TRUE(pred_set.count(loop.GetPreHeaderBlock()->id()));
       EXPECT_TRUE(pred_set.count(44));
       // Check the phi instructions.
       loop.GetHeaderBlock()->ForEachPhiInst([&pred_set](Instruction* phi) {
         for (uint32_t i = 1; i < phi->NumInOperands(); i += 2) {
           EXPECT_TRUE(pred_set.count(phi->GetSingleWordInOperand(i)));
         }
       });
     }
   }

   // Make sure pre-header insertion leaves the module valid.
   std::vector<uint32_t> bin;
   context->module()->ToBinary(&bin, true);
   EXPECT_TRUE(Validate(bin));
 }

 }  // namespace
 }  // namespace opt
 }  // namespace spvtools
	// 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 <memory>
	#include <string>
	#include <unordered_set>
	#include <vector>

	#include "gmock/gmock.h"
	#include "source/opt/iterator.h"
	#include "source/opt/loop_descriptor.h"
	#include "source/opt/pass.h"
	#include "source/opt/tree_iterator.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;

	bool Validate(const std::vector<uint32_t>& bin) {
	spv_target_env target_env = SPV_ENV_UNIVERSAL_1_2;
	spv_context spvContext = spvContextCreate(target_env);
	spv_diagnostic diagnostic = nullptr;
	spv_const_binary_t binary = {bin.data(), bin.size()};
	spv_result_t error = spvValidate(spvContext, &binary, &diagnostic);
	if (error != 0) spvDiagnosticPrint(diagnostic);
	spvDiagnosticDestroy(diagnostic);
	spvContextDestroy(spvContext);
	return error == 0;
	}

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

	/*
	Generated from the following GLSL
	#version 330 core
	layout(location = 0) out vec4 c;
	void main() {
	int i = 0;
	for (; i < 10; ++i) {
	int j = 0;
	int k = 0;
	for (; j < 11; ++j) {}
	for (; k < 12; ++k) {}
	}
	}
	*/
	TEST_F(PassClassTest, BasicVisitFromEntryPoint) {
	const std::string text = R"(
	OpCapability Shader
	%1 = OpExtInstImport "GLSL.std.450"
	OpMemoryModel Logical GLSL450
	OpEntryPoint Fragment %2 "main" %3
	OpExecutionMode %2 OriginUpperLeft
	OpSource GLSL 330
	OpName %2 "main"
	OpName %4 "i"
	OpName %5 "j"
	OpName %6 "k"
	OpName %3 "c"
	OpDecorate %3 Location 0
	%7 = OpTypeVoid
	%8 = OpTypeFunction %7
	%9 = OpTypeInt 32 1
	%10 = OpTypePointer Function %9
	%11 = OpConstant %9 0
	%12 = OpConstant %9 10
	%13 = OpTypeBool
	%14 = OpConstant %9 11
	%15 = OpConstant %9 1
	%16 = OpConstant %9 12
	%17 = OpTypeFloat 32
	%18 = OpTypeVector %17 4
	%19 = OpTypePointer Output %18
	%3 = OpVariable %19 Output
	%2 = OpFunction %7 None %8
	%20 = OpLabel
	%4 = OpVariable %10 Function
	%5 = OpVariable %10 Function
	%6 = OpVariable %10 Function
	OpStore %4 %11
	OpBranch %21
	%21 = OpLabel
	OpLoopMerge %22 %23 None
	OpBranch %24
	%24 = OpLabel
	%25 = OpLoad %9 %4
	%26 = OpSLessThan %13 %25 %12
	OpBranchConditional %26 %27 %22
	%27 = OpLabel
	OpStore %5 %11
	OpStore %6 %11
	OpBranch %28
	%28 = OpLabel
	OpLoopMerge %29 %30 None
	OpBranch %31
	%31 = OpLabel
	%32 = OpLoad %9 %5
	%33 = OpSLessThan %13 %32 %14
	OpBranchConditional %33 %34 %29
	%34 = OpLabel
	OpBranch %30
	%30 = OpLabel
	%35 = OpLoad %9 %5
	%36 = OpIAdd %9 %35 %15
	OpStore %5 %36
	OpBranch %28
	%29 = OpLabel
	OpBranch %37
	%37 = OpLabel
	OpLoopMerge %38 %39 None
	OpBranch %40
	%40 = OpLabel
	%41 = OpLoad %9 %6
	%42 = OpSLessThan %13 %41 %16
	OpBranchConditional %42 %43 %38
	%43 = OpLabel
	OpBranch %39
	%39 = OpLabel
	%44 = OpLoad %9 %6
	%45 = OpIAdd %9 %44 %15
	OpStore %6 %45
	OpBranch %37
	%38 = OpLabel
	OpBranch %23
	%23 = OpLabel
	%46 = OpLoad %9 %4
	%47 = OpIAdd %9 %46 %15
	OpStore %4 %47
	OpBranch %21
	%22 = OpLabel
	OpReturn
	OpFunctionEnd
	)";
	// clang-format on
	std::unique_ptr<IRContext> context =
	BuildModule(SPV_ENV_UNIVERSAL_1_1, 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* f = spvtest::GetFunction(module, 2);
	LoopDescriptor& ld = *context->GetLoopDescriptor(f);

	EXPECT_EQ(ld.NumLoops(), 3u);

	// Invalid basic block id.
	EXPECT_EQ(ld[0u], nullptr);
	// Not a loop header.
	EXPECT_EQ(ld[20], nullptr);

	Loop& parent_loop = *ld[21];
	EXPECT_TRUE(parent_loop.HasNestedLoops());
	EXPECT_FALSE(parent_loop.IsNested());
	EXPECT_EQ(parent_loop.GetDepth(), 1u);
	EXPECT_EQ(std::distance(parent_loop.begin(), parent_loop.end()), 2u);
	EXPECT_EQ(parent_loop.GetHeaderBlock(), spvtest::GetBasicBlock(f, 21));
	EXPECT_EQ(parent_loop.GetLatchBlock(), spvtest::GetBasicBlock(f, 23));
	EXPECT_EQ(parent_loop.GetMergeBlock(), spvtest::GetBasicBlock(f, 22));

	Loop& child_loop_1 = *ld[28];
	EXPECT_FALSE(child_loop_1.HasNestedLoops());
	EXPECT_TRUE(child_loop_1.IsNested());
	EXPECT_EQ(child_loop_1.GetDepth(), 2u);
	EXPECT_EQ(std::distance(child_loop_1.begin(), child_loop_1.end()), 0u);
	EXPECT_EQ(child_loop_1.GetHeaderBlock(), spvtest::GetBasicBlock(f, 28));
	EXPECT_EQ(child_loop_1.GetLatchBlock(), spvtest::GetBasicBlock(f, 30));
	EXPECT_EQ(child_loop_1.GetMergeBlock(), spvtest::GetBasicBlock(f, 29));

	Loop& child_loop_2 = *ld[37];
	EXPECT_FALSE(child_loop_2.HasNestedLoops());
	EXPECT_TRUE(child_loop_2.IsNested());
	EXPECT_EQ(child_loop_2.GetDepth(), 2u);
	EXPECT_EQ(std::distance(child_loop_2.begin(), child_loop_2.end()), 0u);
	EXPECT_EQ(child_loop_2.GetHeaderBlock(), spvtest::GetBasicBlock(f, 37));
	EXPECT_EQ(child_loop_2.GetLatchBlock(), spvtest::GetBasicBlock(f, 39));
	EXPECT_EQ(child_loop_2.GetMergeBlock(), spvtest::GetBasicBlock(f, 38));
	}

	static void CheckLoopBlocks(Loop* loop,
	std::unordered_set<uint32_t>* expected_ids) {
	SCOPED_TRACE("Check loop " + std::to_string(loop->GetHeaderBlock()->id()));
	for (uint32_t bb_id : loop->GetBlocks()) {
	EXPECT_EQ(expected_ids->count(bb_id), 1u);
	expected_ids->erase(bb_id);
	}
	EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
	EXPECT_EQ(expected_ids->size(), 0u);
	}

	/*
	Generated from the following GLSL
	#version 330 core
	layout(location = 0) out vec4 c;
	void main() {
	int i = 0;
	for (; i < 10; ++i) {
	for (int j = 0; j < 11; ++j) {
	if (j < 5) {
	for (int k = 0; k < 12; ++k) {}
	}
	else {}
	for (int k = 0; k < 12; ++k) {}
	}
	}
	}*/
	TEST_F(PassClassTest, TripleNestedLoop) {
	const std::string text = R"(
	OpCapability Shader
	%1 = OpExtInstImport "GLSL.std.450"
	OpMemoryModel Logical GLSL450
	OpEntryPoint Fragment %2 "main" %3
	OpExecutionMode %2 OriginUpperLeft
	OpSource GLSL 330
	OpName %2 "main"
	OpName %4 "i"
	OpName %5 "j"
	OpName %6 "k"
	OpName %7 "k"
	OpName %3 "c"
	OpDecorate %3 Location 0
	%8 = OpTypeVoid
	%9 = OpTypeFunction %8
	%10 = OpTypeInt 32 1
	%11 = OpTypePointer Function %10
	%12 = OpConstant %10 0
	%13 = OpConstant %10 10
	%14 = OpTypeBool
	%15 = OpConstant %10 11
	%16 = OpConstant %10 5
	%17 = OpConstant %10 12
	%18 = OpConstant %10 1
	%19 = OpTypeFloat 32
	%20 = OpTypeVector %19 4
	%21 = OpTypePointer Output %20
	%3 = OpVariable %21 Output
	%2 = OpFunction %8 None %9
	%22 = OpLabel
	%4 = OpVariable %11 Function
	%5 = OpVariable %11 Function
	%6 = OpVariable %11 Function
	%7 = OpVariable %11 Function
	OpStore %4 %12
	OpBranch %23
	%23 = OpLabel
	OpLoopMerge %24 %25 None
	OpBranch %26
	%26 = OpLabel
	%27 = OpLoad %10 %4
	%28 = OpSLessThan %14 %27 %13
	OpBranchConditional %28 %29 %24
	%29 = OpLabel
	OpStore %5 %12
	OpBranch %30
	%30 = OpLabel
	OpLoopMerge %31 %32 None
	OpBranch %33
	%33 = OpLabel
	%34 = OpLoad %10 %5
	%35 = OpSLessThan %14 %34 %15
	OpBranchConditional %35 %36 %31
	%36 = OpLabel
	%37 = OpLoad %10 %5
	%38 = OpSLessThan %14 %37 %16
	OpSelectionMerge %39 None
	OpBranchConditional %38 %40 %39
	%40 = OpLabel
	OpStore %6 %12
	OpBranch %41
	%41 = OpLabel
	OpLoopMerge %42 %43 None
	OpBranch %44
	%44 = OpLabel
	%45 = OpLoad %10 %6
	%46 = OpSLessThan %14 %45 %17
	OpBranchConditional %46 %47 %42
	%47 = OpLabel
	OpBranch %43
	%43 = OpLabel
	%48 = OpLoad %10 %6
	%49 = OpIAdd %10 %48 %18
	OpStore %6 %49
	OpBranch %41
	%42 = OpLabel
	OpBranch %39
	%39 = OpLabel
	OpStore %7 %12
	OpBranch %50
	%50 = OpLabel
	OpLoopMerge %51 %52 None
	OpBranch %53
	%53 = OpLabel
	%54 = OpLoad %10 %7
	%55 = OpSLessThan %14 %54 %17
	OpBranchConditional %55 %56 %51
	%56 = OpLabel
	OpBranch %52
	%52 = OpLabel
	%57 = OpLoad %10 %7
	%58 = OpIAdd %10 %57 %18
	OpStore %7 %58
	OpBranch %50
	%51 = OpLabel
	OpBranch %32
	%32 = OpLabel
	%59 = OpLoad %10 %5
	%60 = OpIAdd %10 %59 %18
	OpStore %5 %60
	OpBranch %30
	%31 = OpLabel
	OpBranch %25
	%25 = OpLabel
	%61 = OpLoad %10 %4
	%62 = OpIAdd %10 %61 %18
	OpStore %4 %62
	OpBranch %23
	%24 = OpLabel
	OpReturn
	OpFunctionEnd
	)";
	// clang-format on
	std::unique_ptr<IRContext> context =
	BuildModule(SPV_ENV_UNIVERSAL_1_1, 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* f = spvtest::GetFunction(module, 2);
	LoopDescriptor& ld = *context->GetLoopDescriptor(f);

	EXPECT_EQ(ld.NumLoops(), 4u);

	// Invalid basic block id.
	EXPECT_EQ(ld[0u], nullptr);
	// Not in a loop.
	EXPECT_EQ(ld[22], nullptr);

	// Check that we can map basic block to the correct loop.
	// The following block ids do not belong to a loop.
	for (uint32_t bb_id : {22, 24}) EXPECT_EQ(ld[bb_id], nullptr);

	{
	std::unordered_set<uint32_t> basic_block_in_loop = {
	{23, 26, 29, 30, 33, 36, 40, 41, 44, 47, 43,
	42, 39, 50, 53, 56, 52, 51, 32, 31, 25}};
	Loop* loop = ld[23];
	CheckLoopBlocks(loop, &basic_block_in_loop);

	EXPECT_TRUE(loop->HasNestedLoops());
	EXPECT_FALSE(loop->IsNested());
	EXPECT_EQ(loop->GetDepth(), 1u);
	EXPECT_EQ(std::distance(loop->begin(), loop->end()), 1u);
	EXPECT_EQ(loop->GetPreHeaderBlock(), spvtest::GetBasicBlock(f, 22));
	EXPECT_EQ(loop->GetHeaderBlock(), spvtest::GetBasicBlock(f, 23));
	EXPECT_EQ(loop->GetLatchBlock(), spvtest::GetBasicBlock(f, 25));
	EXPECT_EQ(loop->GetMergeBlock(), spvtest::GetBasicBlock(f, 24));
	EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
	EXPECT_FALSE(loop->IsInsideLoop(loop->GetPreHeaderBlock()));
	}

	{
	std::unordered_set<uint32_t> basic_block_in_loop = {
	{30, 33, 36, 40, 41, 44, 47, 43, 42, 39, 50, 53, 56, 52, 51, 32}};
	Loop* loop = ld[30];
	CheckLoopBlocks(loop, &basic_block_in_loop);

	EXPECT_TRUE(loop->HasNestedLoops());
	EXPECT_TRUE(loop->IsNested());
	EXPECT_EQ(loop->GetDepth(), 2u);
	EXPECT_EQ(std::distance(loop->begin(), loop->end()), 2u);
	EXPECT_EQ(loop->GetPreHeaderBlock(), spvtest::GetBasicBlock(f, 29));
	EXPECT_EQ(loop->GetHeaderBlock(), spvtest::GetBasicBlock(f, 30));
	EXPECT_EQ(loop->GetLatchBlock(), spvtest::GetBasicBlock(f, 32));
	EXPECT_EQ(loop->GetMergeBlock(), spvtest::GetBasicBlock(f, 31));
	EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
	EXPECT_FALSE(loop->IsInsideLoop(loop->GetPreHeaderBlock()));
	}

	{
	std::unordered_set<uint32_t> basic_block_in_loop = {{41, 44, 47, 43}};
	Loop* loop = ld[41];
	CheckLoopBlocks(loop, &basic_block_in_loop);

	EXPECT_FALSE(loop->HasNestedLoops());
	EXPECT_TRUE(loop->IsNested());
	EXPECT_EQ(loop->GetDepth(), 3u);
	EXPECT_EQ(std::distance(loop->begin(), loop->end()), 0u);
	EXPECT_EQ(loop->GetPreHeaderBlock(), spvtest::GetBasicBlock(f, 40));
	EXPECT_EQ(loop->GetHeaderBlock(), spvtest::GetBasicBlock(f, 41));
	EXPECT_EQ(loop->GetLatchBlock(), spvtest::GetBasicBlock(f, 43));
	EXPECT_EQ(loop->GetMergeBlock(), spvtest::GetBasicBlock(f, 42));
	EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
	EXPECT_FALSE(loop->IsInsideLoop(loop->GetPreHeaderBlock()));
	}

	{
	std::unordered_set<uint32_t> basic_block_in_loop = {{50, 53, 56, 52}};
	Loop* loop = ld[50];
	CheckLoopBlocks(loop, &basic_block_in_loop);

	EXPECT_FALSE(loop->HasNestedLoops());
	EXPECT_TRUE(loop->IsNested());
	EXPECT_EQ(loop->GetDepth(), 3u);
	EXPECT_EQ(std::distance(loop->begin(), loop->end()), 0u);
	EXPECT_EQ(loop->GetPreHeaderBlock(), spvtest::GetBasicBlock(f, 39));
	EXPECT_EQ(loop->GetHeaderBlock(), spvtest::GetBasicBlock(f, 50));
	EXPECT_EQ(loop->GetLatchBlock(), spvtest::GetBasicBlock(f, 52));
	EXPECT_EQ(loop->GetMergeBlock(), spvtest::GetBasicBlock(f, 51));
	EXPECT_FALSE(loop->IsInsideLoop(loop->GetMergeBlock()));
	EXPECT_FALSE(loop->IsInsideLoop(loop->GetPreHeaderBlock()));
	}

	// Make sure LoopDescriptor gives us the inner most loop when we query for
	// loops.
	for (const BasicBlock& bb : *f) {
	if (Loop* loop = ld[&bb]) {
	for (Loop& sub_loop :
	make_range(++TreeDFIterator<Loop>(loop), TreeDFIterator<Loop>())) {
	EXPECT_FALSE(sub_loop.IsInsideLoop(bb.id()));
	}
	}
	}
	}

	/*
	Generated from the following GLSL
	#version 330 core
	layout(location = 0) out vec4 c;
	void main() {
	for (int i = 0; i < 10; ++i) {
	for (int j = 0; j < 11; ++j) {
	for (int k = 0; k < 11; ++k) {}
	}
	for (int k = 0; k < 12; ++k) {}
	}
	}
	*/
	TEST_F(PassClassTest, LoopParentTest) {
	const std::string text = R"(
	OpCapability Shader
	%1 = OpExtInstImport "GLSL.std.450"
	OpMemoryModel Logical GLSL450
	OpEntryPoint Fragment %2 "main" %3
	OpExecutionMode %2 OriginUpperLeft
	OpSource GLSL 330
	OpName %2 "main"
	OpName %4 "i"
	OpName %5 "j"
	OpName %6 "k"
	OpName %7 "k"
	OpName %3 "c"
	OpDecorate %3 Location 0
	%8 = OpTypeVoid
	%9 = OpTypeFunction %8
	%10 = OpTypeInt 32 1
	%11 = OpTypePointer Function %10
	%12 = OpConstant %10 0
	%13 = OpConstant %10 10
	%14 = OpTypeBool
	%15 = OpConstant %10 11
	%16 = OpConstant %10 1
	%17 = OpConstant %10 12
	%18 = OpTypeFloat 32
	%19 = OpTypeVector %18 4
	%20 = OpTypePointer Output %19
	%3 = OpVariable %20 Output
	%2 = OpFunction %8 None %9
	%21 = OpLabel
	%4 = OpVariable %11 Function
	%5 = OpVariable %11 Function
	%6 = OpVariable %11 Function
	%7 = OpVariable %11 Function
	OpStore %4 %12
	OpBranch %22
	%22 = OpLabel
	OpLoopMerge %23 %24 None
	OpBranch %25
	%25 = OpLabel
	%26 = OpLoad %10 %4
	%27 = OpSLessThan %14 %26 %13
	OpBranchConditional %27 %28 %23
	%28 = OpLabel
	OpStore %5 %12
	OpBranch %29
	%29 = OpLabel
	OpLoopMerge %30 %31 None
	OpBranch %32
	%32 = OpLabel
	%33 = OpLoad %10 %5
	%34 = OpSLessThan %14 %33 %15
	OpBranchConditional %34 %35 %30
	%35 = OpLabel
	OpStore %6 %12
	OpBranch %36
	%36 = OpLabel
	OpLoopMerge %37 %38 None
	OpBranch %39
	%39 = OpLabel
	%40 = OpLoad %10 %6
	%41 = OpSLessThan %14 %40 %15
	OpBranchConditional %41 %42 %37
	%42 = OpLabel
	OpBranch %38
	%38 = OpLabel
	%43 = OpLoad %10 %6
	%44 = OpIAdd %10 %43 %16
	OpStore %6 %44
	OpBranch %36
	%37 = OpLabel
	OpBranch %31
	%31 = OpLabel
	%45 = OpLoad %10 %5
	%46 = OpIAdd %10 %45 %16
	OpStore %5 %46
	OpBranch %29
	%30 = OpLabel
	OpStore %7 %12
	OpBranch %47
	%47 = OpLabel
	OpLoopMerge %48 %49 None
	OpBranch %50
	%50 = OpLabel
	%51 = OpLoad %10 %7
	%52 = OpSLessThan %14 %51 %17
	OpBranchConditional %52 %53 %48
	%53 = OpLabel
	OpBranch %49
	%49 = OpLabel
	%54 = OpLoad %10 %7
	%55 = OpIAdd %10 %54 %16
	OpStore %7 %55
	OpBranch %47
	%48 = OpLabel
	OpBranch %24
	%24 = OpLabel
	%56 = OpLoad %10 %4
	%57 = OpIAdd %10 %56 %16
	OpStore %4 %57
	OpBranch %22
	%23 = OpLabel
	OpReturn
	OpFunctionEnd
	)";
	// clang-format on
	std::unique_ptr<IRContext> context =
	BuildModule(SPV_ENV_UNIVERSAL_1_1, 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* f = spvtest::GetFunction(module, 2);
	LoopDescriptor& ld = *context->GetLoopDescriptor(f);

	EXPECT_EQ(ld.NumLoops(), 4u);

	{
	Loop& loop = *ld[22];
	EXPECT_TRUE(loop.HasNestedLoops());
	EXPECT_FALSE(loop.IsNested());
	EXPECT_EQ(loop.GetDepth(), 1u);
	EXPECT_EQ(loop.GetParent(), nullptr);
	}

	{
	Loop& loop = *ld[29];
	EXPECT_TRUE(loop.HasNestedLoops());
	EXPECT_TRUE(loop.IsNested());
	EXPECT_EQ(loop.GetDepth(), 2u);
	EXPECT_EQ(loop.GetParent(), ld[22]);
	}

	{
	Loop& loop = *ld[36];
	EXPECT_FALSE(loop.HasNestedLoops());
	EXPECT_TRUE(loop.IsNested());
	EXPECT_EQ(loop.GetDepth(), 3u);
	EXPECT_EQ(loop.GetParent(), ld[29]);
	}

	{
	Loop& loop = *ld[47];
	EXPECT_FALSE(loop.HasNestedLoops());
	EXPECT_TRUE(loop.IsNested());
	EXPECT_EQ(loop.GetDepth(), 2u);
	EXPECT_EQ(loop.GetParent(), ld[22]);
	}
	}

	/*
	Generated from the following GLSL + --eliminate-local-multi-store
	The preheader of loop %33 and %41 were removed as well.

	#version 330 core
	void main() {
	int a = 0;
	for (int i = 0; i < 10; ++i) {
	if (i == 0) {
	a = 1;
	} else {
	a = 2;
	}
	for (int j = 0; j < 11; ++j) {
	a++;
	}
	}
	for (int k = 0; k < 12; ++k) {}
	}
	*/
	TEST_F(PassClassTest, CreatePreheaderTest) {
	const std::string text = R"(
	OpCapability Shader
	%1 = OpExtInstImport "GLSL.std.450"
	OpMemoryModel Logical GLSL450
	OpEntryPoint Fragment %2 "main"
	OpExecutionMode %2 OriginUpperLeft
	OpSource GLSL 330
	OpName %2 "main"
	%3 = OpTypeVoid
	%4 = OpTypeFunction %3
	%5 = OpTypeInt 32 1
	%6 = OpTypePointer Function %5
	%7 = OpConstant %5 0
	%8 = OpConstant %5 10
	%9 = OpTypeBool
	%10 = OpConstant %5 1
	%11 = OpConstant %5 2
	%12 = OpConstant %5 11
	%13 = OpConstant %5 12
	%14 = OpUndef %5
	%2 = OpFunction %3 None %4
	%15 = OpLabel
	OpBranch %16
	%16 = OpLabel
	%17 = OpPhi %5 %7 %15 %18 %19
	%20 = OpPhi %5 %7 %15 %21 %19
	%22 = OpPhi %5 %14 %15 %23 %19
	OpLoopMerge %41 %19 None
	OpBranch %25
	%25 = OpLabel
	%26 = OpSLessThan %9 %20 %8
	OpBranchConditional %26 %27 %41
	%27 = OpLabel
	%28 = OpIEqual %9 %20 %7
	OpSelectionMerge %33 None
	OpBranchConditional %28 %30 %31
	%30 = OpLabel
	OpBranch %33
	%31 = OpLabel
	OpBranch %33
	%33 = OpLabel
	%18 = OpPhi %5 %10 %30 %11 %31 %34 %35
	%23 = OpPhi %5 %7 %30 %7 %31 %36 %35
	OpLoopMerge %37 %35 None
	OpBranch %38
	%38 = OpLabel
	%39 = OpSLessThan %9 %23 %12
	OpBranchConditional %39 %40 %37
	%40 = OpLabel
	%34 = OpIAdd %5 %18 %10
	OpBranch %35
	%35 = OpLabel
	%36 = OpIAdd %5 %23 %10
	OpBranch %33
	%37 = OpLabel
	OpBranch %19
	%19 = OpLabel
	%21 = OpIAdd %5 %20 %10
	OpBranch %16
	%41 = OpLabel
	%42 = OpPhi %5 %7 %25 %43 %44
	OpLoopMerge %45 %44 None
	OpBranch %46
	%46 = OpLabel
	%47 = OpSLessThan %9 %42 %13
	OpBranchConditional %47 %48 %45
	%48 = OpLabel
	OpBranch %44
	%44 = OpLabel
	%43 = OpIAdd %5 %42 %10
	OpBranch %41
	%45 = OpLabel
	OpReturn
	OpFunctionEnd
	)";
	// clang-format on
	std::unique_ptr<IRContext> context =
	BuildModule(SPV_ENV_UNIVERSAL_1_1, 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* f = spvtest::GetFunction(module, 2);
	LoopDescriptor& ld = *context->GetLoopDescriptor(f);
	// No invalidation of the cfg should occur during this test.
	CFG* cfg = context->cfg();

	EXPECT_EQ(ld.NumLoops(), 3u);

	{
	Loop& loop = *ld[16];
	EXPECT_TRUE(loop.HasNestedLoops());
	EXPECT_FALSE(loop.IsNested());
	EXPECT_EQ(loop.GetDepth(), 1u);
	EXPECT_EQ(loop.GetParent(), nullptr);
	}

	{
	Loop& loop = *ld[33];
	EXPECT_EQ(loop.GetPreHeaderBlock(), nullptr);
	EXPECT_NE(loop.GetOrCreatePreHeaderBlock(), nullptr);
	// Make sure the loop descriptor was properly updated.
	EXPECT_EQ(ld[loop.GetPreHeaderBlock()], ld[16]);
	{
	const std::vector<uint32_t>& preds =
	cfg->preds(loop.GetPreHeaderBlock()->id());
	std::unordered_set<uint32_t> pred_set(preds.begin(), preds.end());
	EXPECT_EQ(pred_set.size(), 2u);
	EXPECT_TRUE(pred_set.count(30));
	EXPECT_TRUE(pred_set.count(31));
	// Check the phi instructions.
	loop.GetPreHeaderBlock()->ForEachPhiInst([&pred_set](Instruction* phi) {
	for (uint32_t i = 1; i < phi->NumInOperands(); i += 2) {
	EXPECT_TRUE(pred_set.count(phi->GetSingleWordInOperand(i)));
	}
	});
	}
	{
	const std::vector<uint32_t>& preds =
	cfg->preds(loop.GetHeaderBlock()->id());
	std::unordered_set<uint32_t> pred_set(preds.begin(), preds.end());
	EXPECT_EQ(pred_set.size(), 2u);
	EXPECT_TRUE(pred_set.count(loop.GetPreHeaderBlock()->id()));
	EXPECT_TRUE(pred_set.count(35));
	// Check the phi instructions.
	loop.GetHeaderBlock()->ForEachPhiInst([&pred_set](Instruction* phi) {
	for (uint32_t i = 1; i < phi->NumInOperands(); i += 2) {
	EXPECT_TRUE(pred_set.count(phi->GetSingleWordInOperand(i)));
	}
	});
	}
	}

	{
	Loop& loop = *ld[41];
	EXPECT_EQ(loop.GetPreHeaderBlock(), nullptr);
	EXPECT_NE(loop.GetOrCreatePreHeaderBlock(), nullptr);
	EXPECT_EQ(ld[loop.GetPreHeaderBlock()], nullptr);
	EXPECT_EQ(cfg->preds(loop.GetPreHeaderBlock()->id()).size(), 1u);
	EXPECT_EQ(cfg->preds(loop.GetPreHeaderBlock()->id())[0], 25u);
	// Check the phi instructions.
	loop.GetPreHeaderBlock()->ForEachPhiInst([](Instruction* phi) {
	EXPECT_EQ(phi->NumInOperands(), 2u);
	EXPECT_EQ(phi->GetSingleWordInOperand(1), 25u);
	});
	{
	const std::vector<uint32_t>& preds =
	cfg->preds(loop.GetHeaderBlock()->id());
	std::unordered_set<uint32_t> pred_set(preds.begin(), preds.end());
	EXPECT_EQ(pred_set.size(), 2u);
	EXPECT_TRUE(pred_set.count(loop.GetPreHeaderBlock()->id()));
	EXPECT_TRUE(pred_set.count(44));
	// Check the phi instructions.
	loop.GetHeaderBlock()->ForEachPhiInst([&pred_set](Instruction* phi) {
	for (uint32_t i = 1; i < phi->NumInOperands(); i += 2) {
	EXPECT_TRUE(pred_set.count(phi->GetSingleWordInOperand(i)));
	}
	});
	}
	}

	// Make sure pre-header insertion leaves the module valid.
	std::vector<uint32_t> bin;
	context->module()->ToBinary(&bin, true);
	EXPECT_TRUE(Validate(bin));
	}

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