SPIRV-Tools/test/reduce/structured_loop_to_selection_test.cpp
alan-baker 05de650371
Use structural reachability in CFG checks (#4849)
Fixes https://crbug.com/oss-fuzz48578

* Adds structural reachability to basic blocks
  * calculated in same manner as reachability, but using structural
    successors
* Change structured CFG validation to use structural reachability
  instead of reachability
* Fix some invalid reducer cases
2022-07-06 17:43:32 -04:00

3625 lines
117 KiB
C++

// Copyright (c) 2018 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/reduce/structured_loop_to_selection_reduction_opportunity_finder.h"
#include "source/opt/build_module.h"
#include "source/reduce/reduction_opportunity.h"
#include "test/reduce/reduce_test_util.h"
namespace spvtools {
namespace reduce {
namespace {
TEST(StructuredLoopToSelectionReductionPassTest, LoopyShader1) {
std::string shader = 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 = OpTypePointer Function %6
%9 = OpConstant %6 0
%16 = OpConstant %6 100
%17 = OpTypeBool
%20 = OpConstant %6 1
%4 = OpFunction %2 None %3
%5 = OpLabel
%8 = OpVariable %7 Function
OpStore %8 %9
OpBranch %10
%10 = OpLabel
OpLoopMerge %12 %13 None
OpBranch %14
%14 = OpLabel
%15 = OpLoad %6 %8
%18 = OpSLessThan %17 %15 %16
OpBranchConditional %18 %11 %12
%11 = OpLabel
OpBranch %13
%13 = OpLabel
%19 = OpLoad %6 %8
%21 = OpIAdd %6 %19 %20
OpStore %8 %21
OpBranch %10
%12 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = 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 = OpTypePointer Function %6
%9 = OpConstant %6 0
%16 = OpConstant %6 100
%17 = OpTypeBool
%20 = OpConstant %6 1
%22 = OpConstantTrue %17
%4 = OpFunction %2 None %3
%5 = OpLabel
%8 = OpVariable %7 Function
OpStore %8 %9
OpBranch %10
%10 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %22 %14 %12
%14 = OpLabel
%15 = OpLoad %6 %8
%18 = OpSLessThan %17 %15 %16
OpBranchConditional %18 %11 %12
%11 = OpLabel
OpBranch %12
%13 = OpLabel
%19 = OpLoad %6 %8
%21 = OpIAdd %6 %19 %20
OpStore %8 %21
OpBranch %10
%12 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, LoopyShader2) {
std::string shader = 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 = OpTypePointer Function %6
%9 = OpConstant %6 0
%16 = OpConstant %6 100
%17 = OpTypeBool
%28 = OpConstant %6 1
%4 = OpFunction %2 None %3
%5 = OpLabel
%8 = OpVariable %7 Function
%19 = OpVariable %7 Function
%32 = OpVariable %7 Function
%40 = OpVariable %7 Function
OpStore %8 %9
OpBranch %10
%10 = OpLabel
OpLoopMerge %12 %13 None
OpBranch %14
%14 = OpLabel
%15 = OpLoad %6 %8
%18 = OpSLessThan %17 %15 %16
OpBranchConditional %18 %11 %12
%11 = OpLabel
OpStore %19 %9
OpBranch %20
%20 = OpLabel
OpLoopMerge %22 %23 None
OpBranch %24
%24 = OpLabel
%25 = OpLoad %6 %19
%26 = OpSLessThan %17 %25 %16
OpBranchConditional %26 %21 %22
%21 = OpLabel
OpBranch %23
%23 = OpLabel
%27 = OpLoad %6 %19
%29 = OpIAdd %6 %27 %28
OpStore %19 %29
OpBranch %20
%22 = OpLabel
OpBranch %13
%13 = OpLabel
%30 = OpLoad %6 %8
%31 = OpIAdd %6 %30 %28
OpStore %8 %31
OpBranch %10
%12 = OpLabel
OpStore %32 %9
OpBranch %33
%33 = OpLabel
OpLoopMerge %35 %36 None
OpBranch %37
%37 = OpLabel
%38 = OpLoad %6 %32
%39 = OpSLessThan %17 %38 %16
OpBranchConditional %39 %34 %35
%34 = OpLabel
OpStore %40 %9
OpBranch %41
%41 = OpLabel
OpLoopMerge %43 %44 None
OpBranch %45
%45 = OpLabel
%46 = OpLoad %6 %40
%47 = OpSLessThan %17 %46 %16
OpBranchConditional %47 %42 %43
%42 = OpLabel
OpBranch %44
%44 = OpLabel
%48 = OpLoad %6 %40
%49 = OpIAdd %6 %48 %28
OpStore %40 %49
OpBranch %41
%43 = OpLabel
OpBranch %36
%36 = OpLabel
%50 = OpLoad %6 %32
%51 = OpIAdd %6 %50 %28
OpStore %32 %51
OpBranch %33
%35 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(4, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = 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 = OpTypePointer Function %6
%9 = OpConstant %6 0
%16 = OpConstant %6 100
%17 = OpTypeBool
%28 = OpConstant %6 1
%52 = OpConstantTrue %17
%4 = OpFunction %2 None %3
%5 = OpLabel
%8 = OpVariable %7 Function
%19 = OpVariable %7 Function
%32 = OpVariable %7 Function
%40 = OpVariable %7 Function
OpStore %8 %9
OpBranch %10
%10 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %52 %14 %12
%14 = OpLabel
%15 = OpLoad %6 %8
%18 = OpSLessThan %17 %15 %16
OpBranchConditional %18 %11 %12
%11 = OpLabel
OpStore %19 %9
OpBranch %20
%20 = OpLabel
OpLoopMerge %22 %23 None
OpBranch %24
%24 = OpLabel
%25 = OpLoad %6 %19
%26 = OpSLessThan %17 %25 %16
OpBranchConditional %26 %21 %22
%21 = OpLabel
OpBranch %23
%23 = OpLabel
%27 = OpLoad %6 %19
%29 = OpIAdd %6 %27 %28
OpStore %19 %29
OpBranch %20
%22 = OpLabel
OpBranch %12
%13 = OpLabel
%30 = OpLoad %6 %8
%31 = OpIAdd %6 %30 %28
OpStore %8 %31
OpBranch %10
%12 = OpLabel
OpStore %32 %9
OpBranch %33
%33 = OpLabel
OpLoopMerge %35 %36 None
OpBranch %37
%37 = OpLabel
%38 = OpLoad %6 %32
%39 = OpSLessThan %17 %38 %16
OpBranchConditional %39 %34 %35
%34 = OpLabel
OpStore %40 %9
OpBranch %41
%41 = OpLabel
OpLoopMerge %43 %44 None
OpBranch %45
%45 = OpLabel
%46 = OpLoad %6 %40
%47 = OpSLessThan %17 %46 %16
OpBranchConditional %47 %42 %43
%42 = OpLabel
OpBranch %44
%44 = OpLabel
%48 = OpLoad %6 %40
%49 = OpIAdd %6 %48 %28
OpStore %40 %49
OpBranch %41
%43 = OpLabel
OpBranch %36
%36 = OpLabel
%50 = OpLoad %6 %32
%51 = OpIAdd %6 %50 %28
OpStore %32 %51
OpBranch %33
%35 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
ASSERT_TRUE(ops[1]->PreconditionHolds());
ops[1]->TryToApply();
CheckValid(env, context.get());
std::string after_op_1 = 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 = OpTypePointer Function %6
%9 = OpConstant %6 0
%16 = OpConstant %6 100
%17 = OpTypeBool
%28 = OpConstant %6 1
%52 = OpConstantTrue %17
%4 = OpFunction %2 None %3
%5 = OpLabel
%8 = OpVariable %7 Function
%19 = OpVariable %7 Function
%32 = OpVariable %7 Function
%40 = OpVariable %7 Function
OpStore %8 %9
OpBranch %10
%10 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %52 %14 %12
%14 = OpLabel
%15 = OpLoad %6 %8
%18 = OpSLessThan %17 %15 %16
OpBranchConditional %18 %11 %12
%11 = OpLabel
OpStore %19 %9
OpBranch %20
%20 = OpLabel
OpSelectionMerge %22 None
OpBranchConditional %52 %24 %22
%24 = OpLabel
%25 = OpLoad %6 %19
%26 = OpSLessThan %17 %25 %16
OpBranchConditional %26 %21 %22
%21 = OpLabel
OpBranch %22
%23 = OpLabel
%27 = OpLoad %6 %19
%29 = OpIAdd %6 %27 %28
OpStore %19 %29
OpBranch %20
%22 = OpLabel
OpBranch %12
%13 = OpLabel
%30 = OpLoad %6 %8
%31 = OpIAdd %6 %30 %28
OpStore %8 %31
OpBranch %10
%12 = OpLabel
OpStore %32 %9
OpBranch %33
%33 = OpLabel
OpLoopMerge %35 %36 None
OpBranch %37
%37 = OpLabel
%38 = OpLoad %6 %32
%39 = OpSLessThan %17 %38 %16
OpBranchConditional %39 %34 %35
%34 = OpLabel
OpStore %40 %9
OpBranch %41
%41 = OpLabel
OpLoopMerge %43 %44 None
OpBranch %45
%45 = OpLabel
%46 = OpLoad %6 %40
%47 = OpSLessThan %17 %46 %16
OpBranchConditional %47 %42 %43
%42 = OpLabel
OpBranch %44
%44 = OpLabel
%48 = OpLoad %6 %40
%49 = OpIAdd %6 %48 %28
OpStore %40 %49
OpBranch %41
%43 = OpLabel
OpBranch %36
%36 = OpLabel
%50 = OpLoad %6 %32
%51 = OpIAdd %6 %50 %28
OpStore %32 %51
OpBranch %33
%35 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_1, context.get());
ASSERT_TRUE(ops[2]->PreconditionHolds());
ops[2]->TryToApply();
CheckValid(env, context.get());
std::string after_op_2 = 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 = OpTypePointer Function %6
%9 = OpConstant %6 0
%16 = OpConstant %6 100
%17 = OpTypeBool
%28 = OpConstant %6 1
%52 = OpConstantTrue %17
%4 = OpFunction %2 None %3
%5 = OpLabel
%8 = OpVariable %7 Function
%19 = OpVariable %7 Function
%32 = OpVariable %7 Function
%40 = OpVariable %7 Function
OpStore %8 %9
OpBranch %10
%10 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %52 %14 %12
%14 = OpLabel
%15 = OpLoad %6 %8
%18 = OpSLessThan %17 %15 %16
OpBranchConditional %18 %11 %12
%11 = OpLabel
OpStore %19 %9
OpBranch %20
%20 = OpLabel
OpSelectionMerge %22 None
OpBranchConditional %52 %24 %22
%24 = OpLabel
%25 = OpLoad %6 %19
%26 = OpSLessThan %17 %25 %16
OpBranchConditional %26 %21 %22
%21 = OpLabel
OpBranch %22
%23 = OpLabel
%27 = OpLoad %6 %19
%29 = OpIAdd %6 %27 %28
OpStore %19 %29
OpBranch %20
%22 = OpLabel
OpBranch %12
%13 = OpLabel
%30 = OpLoad %6 %8
%31 = OpIAdd %6 %30 %28
OpStore %8 %31
OpBranch %10
%12 = OpLabel
OpStore %32 %9
OpBranch %33
%33 = OpLabel
OpSelectionMerge %35 None
OpBranchConditional %52 %37 %35
%37 = OpLabel
%38 = OpLoad %6 %32
%39 = OpSLessThan %17 %38 %16
OpBranchConditional %39 %34 %35
%34 = OpLabel
OpStore %40 %9
OpBranch %41
%41 = OpLabel
OpLoopMerge %43 %44 None
OpBranch %45
%45 = OpLabel
%46 = OpLoad %6 %40
%47 = OpSLessThan %17 %46 %16
OpBranchConditional %47 %42 %43
%42 = OpLabel
OpBranch %44
%44 = OpLabel
%48 = OpLoad %6 %40
%49 = OpIAdd %6 %48 %28
OpStore %40 %49
OpBranch %41
%43 = OpLabel
OpBranch %35
%36 = OpLabel
%50 = OpLoad %6 %32
%51 = OpIAdd %6 %50 %28
OpStore %32 %51
OpBranch %33
%35 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_2, context.get());
ASSERT_TRUE(ops[3]->PreconditionHolds());
ops[3]->TryToApply();
CheckValid(env, context.get());
std::string after_op_3 = 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 = OpTypePointer Function %6
%9 = OpConstant %6 0
%16 = OpConstant %6 100
%17 = OpTypeBool
%28 = OpConstant %6 1
%52 = OpConstantTrue %17
%4 = OpFunction %2 None %3
%5 = OpLabel
%8 = OpVariable %7 Function
%19 = OpVariable %7 Function
%32 = OpVariable %7 Function
%40 = OpVariable %7 Function
OpStore %8 %9
OpBranch %10
%10 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %52 %14 %12
%14 = OpLabel
%15 = OpLoad %6 %8
%18 = OpSLessThan %17 %15 %16
OpBranchConditional %18 %11 %12
%11 = OpLabel
OpStore %19 %9
OpBranch %20
%20 = OpLabel
OpSelectionMerge %22 None
OpBranchConditional %52 %24 %22
%24 = OpLabel
%25 = OpLoad %6 %19
%26 = OpSLessThan %17 %25 %16
OpBranchConditional %26 %21 %22
%21 = OpLabel
OpBranch %22
%23 = OpLabel
%27 = OpLoad %6 %19
%29 = OpIAdd %6 %27 %28
OpStore %19 %29
OpBranch %20
%22 = OpLabel
OpBranch %12
%13 = OpLabel
%30 = OpLoad %6 %8
%31 = OpIAdd %6 %30 %28
OpStore %8 %31
OpBranch %10
%12 = OpLabel
OpStore %32 %9
OpBranch %33
%33 = OpLabel
OpSelectionMerge %35 None
OpBranchConditional %52 %37 %35
%37 = OpLabel
%38 = OpLoad %6 %32
%39 = OpSLessThan %17 %38 %16
OpBranchConditional %39 %34 %35
%34 = OpLabel
OpStore %40 %9
OpBranch %41
%41 = OpLabel
OpSelectionMerge %43 None
OpBranchConditional %52 %45 %43
%45 = OpLabel
%46 = OpLoad %6 %40
%47 = OpSLessThan %17 %46 %16
OpBranchConditional %47 %42 %43
%42 = OpLabel
OpBranch %43
%44 = OpLabel
%48 = OpLoad %6 %40
%49 = OpIAdd %6 %48 %28
OpStore %40 %49
OpBranch %41
%43 = OpLabel
OpBranch %35
%36 = OpLabel
%50 = OpLoad %6 %32
%51 = OpIAdd %6 %50 %28
OpStore %32 %51
OpBranch %33
%35 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_3, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, LoopyShader3) {
std::string shader = 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 = OpTypePointer Function %6
%9 = OpConstant %6 10
%16 = OpConstant %6 0
%17 = OpTypeBool
%20 = OpConstant %6 1
%23 = OpConstant %6 3
%40 = OpConstant %6 5
%4 = OpFunction %2 None %3
%5 = OpLabel
%8 = OpVariable %7 Function
OpStore %8 %9
OpBranch %10
%10 = OpLabel
OpLoopMerge %12 %13 None
OpBranch %14
%14 = OpLabel
%15 = OpLoad %6 %8
%18 = OpSGreaterThan %17 %15 %16
OpBranchConditional %18 %11 %12
%11 = OpLabel
%19 = OpLoad %6 %8
%21 = OpISub %6 %19 %20
OpStore %8 %21
%22 = OpLoad %6 %8
%24 = OpSLessThan %17 %22 %23
OpSelectionMerge %26 None
OpBranchConditional %24 %25 %26
%25 = OpLabel
OpBranch %13
%26 = OpLabel
OpBranch %28
%28 = OpLabel
OpLoopMerge %30 %31 None
OpBranch %29
%29 = OpLabel
%32 = OpLoad %6 %8
%33 = OpISub %6 %32 %20
OpStore %8 %33
%34 = OpLoad %6 %8
%35 = OpIEqual %17 %34 %20
OpSelectionMerge %37 None
OpBranchConditional %35 %36 %37
%36 = OpLabel
OpReturn ; This return spoils everything: it means the merge does not post-dominate the header.
%37 = OpLabel
OpBranch %31
%31 = OpLabel
%39 = OpLoad %6 %8
%41 = OpSGreaterThan %17 %39 %40
OpBranchConditional %41 %28 %30
%30 = OpLabel
OpBranch %13
%13 = OpLabel
OpBranch %10
%12 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(0, ops.size());
}
TEST(StructuredLoopToSelectionReductionPassTest, LoopyShader4) {
std::string shader = 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 = OpTypePointer Function %6
%8 = OpTypeFunction %6 %7
%13 = OpConstant %6 0
%22 = OpTypeBool
%25 = OpConstant %6 1
%39 = OpConstant %6 100
%4 = OpFunction %2 None %3
%5 = OpLabel
%45 = OpVariable %7 Function
%46 = OpVariable %7 Function
%47 = OpVariable %7 Function
%32 = OpVariable %7 Function
%42 = OpVariable %7 Function
OpStore %32 %13
OpBranch %33
%33 = OpLabel
OpLoopMerge %35 %36 None
OpBranch %37
%37 = OpLabel
%38 = OpLoad %6 %32
%40 = OpSLessThan %22 %38 %39
OpBranchConditional %40 %34 %35
%34 = OpLabel
OpBranch %36
%36 = OpLabel
%41 = OpLoad %6 %32
OpStore %42 %25
OpStore %45 %13
OpStore %46 %13
OpBranch %48
%48 = OpLabel
OpLoopMerge %49 %50 None
OpBranch %51
%51 = OpLabel
%52 = OpLoad %6 %46
%53 = OpLoad %6 %42
%54 = OpSLessThan %22 %52 %53
OpBranchConditional %54 %55 %49
%55 = OpLabel
%56 = OpLoad %6 %45
%57 = OpIAdd %6 %56 %25
OpStore %45 %57
OpBranch %50
%50 = OpLabel
%58 = OpLoad %6 %46
%59 = OpIAdd %6 %58 %25
OpStore %46 %59
OpBranch %48
%49 = OpLabel
%60 = OpLoad %6 %45
OpStore %47 %60
%43 = OpLoad %6 %47
%44 = OpIAdd %6 %41 %43
OpStore %32 %44
OpBranch %33
%35 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
// Initially there are two opportunities.
ASSERT_EQ(2, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = 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 = OpTypePointer Function %6
%8 = OpTypeFunction %6 %7
%13 = OpConstant %6 0
%22 = OpTypeBool
%25 = OpConstant %6 1
%39 = OpConstant %6 100
%61 = OpConstantTrue %22
%62 = OpUndef %6
%4 = OpFunction %2 None %3
%5 = OpLabel
%45 = OpVariable %7 Function
%46 = OpVariable %7 Function
%47 = OpVariable %7 Function
%32 = OpVariable %7 Function
%42 = OpVariable %7 Function
OpStore %32 %13
OpBranch %33
%33 = OpLabel
OpSelectionMerge %35 None
OpBranchConditional %61 %37 %35
%37 = OpLabel
%38 = OpLoad %6 %32
%40 = OpSLessThan %22 %38 %39
OpBranchConditional %40 %34 %35
%34 = OpLabel
OpBranch %35
%36 = OpLabel
%41 = OpLoad %6 %32
OpStore %42 %25
OpStore %45 %13
OpStore %46 %13
OpBranch %48
%48 = OpLabel
OpLoopMerge %49 %50 None
OpBranch %51
%51 = OpLabel
%52 = OpLoad %6 %46
%53 = OpLoad %6 %42
%54 = OpSLessThan %22 %52 %53
OpBranchConditional %54 %55 %49
%55 = OpLabel
%56 = OpLoad %6 %45
%57 = OpIAdd %6 %56 %25
OpStore %45 %57
OpBranch %50
%50 = OpLabel
%58 = OpLoad %6 %46
%59 = OpIAdd %6 %58 %25
OpStore %46 %59
OpBranch %48
%49 = OpLabel
%60 = OpLoad %6 %45
OpStore %47 %60
%43 = OpLoad %6 %47
%44 = OpIAdd %6 %62 %43
OpStore %32 %44
OpBranch %33
%35 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
// Applying the first opportunity has killed the second opportunity, because
// there was a loop embedded in the continue target of the loop we have just
// eliminated; the continue-embedded loop is now unreachable.
ASSERT_FALSE(ops[1]->PreconditionHolds());
}
TEST(StructuredLoopToSelectionReductionPassTest, ConditionalBreak1) {
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main"
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpName %4 "main"
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%10 = OpTypeBool
%11 = OpConstantFalse %10
%4 = OpFunction %2 None %3
%5 = OpLabel
OpBranch %6
%6 = OpLabel
OpLoopMerge %8 %9 None
OpBranch %7
%7 = OpLabel
OpSelectionMerge %13 None
OpBranchConditional %11 %12 %13
%12 = OpLabel
OpBranch %8
%13 = OpLabel
OpBranch %9
%9 = OpLabel
OpBranchConditional %11 %6 %8
%8 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main"
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpName %4 "main"
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%10 = OpTypeBool
%11 = OpConstantFalse %10
%14 = OpConstantTrue %10
%4 = OpFunction %2 None %3
%5 = OpLabel
OpBranch %6
%6 = OpLabel
OpSelectionMerge %8 None
OpBranchConditional %14 %7 %8
%7 = OpLabel
OpSelectionMerge %13 None
OpBranchConditional %11 %12 %13
%12 = OpLabel
OpBranch %13
%13 = OpLabel
OpBranch %8
%9 = OpLabel
OpBranchConditional %11 %6 %8
%8 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, ConditionalBreak2) {
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main"
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpName %4 "main"
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%10 = OpTypeBool
%11 = OpConstantFalse %10
%4 = OpFunction %2 None %3
%5 = OpLabel
OpBranch %6
%6 = OpLabel
OpLoopMerge %8 %9 None
OpBranch %7
%7 = OpLabel
OpSelectionMerge %13 None
OpBranchConditional %11 %8 %13
%13 = OpLabel
OpBranch %9
%9 = OpLabel
OpBranchConditional %11 %6 %8
%8 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main"
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpName %4 "main"
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%10 = OpTypeBool
%11 = OpConstantFalse %10
%14 = OpConstantTrue %10
%4 = OpFunction %2 None %3
%5 = OpLabel
OpBranch %6
%6 = OpLabel
OpSelectionMerge %8 None
OpBranchConditional %14 %7 %8
%7 = OpLabel
OpSelectionMerge %13 None
OpBranchConditional %11 %13 %13
%13 = OpLabel
OpBranch %8
%9 = OpLabel
OpBranchConditional %11 %6 %8
%8 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, UnconditionalBreak) {
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main"
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpName %4 "main"
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%4 = OpFunction %2 None %3
%5 = OpLabel
OpBranch %6
%6 = OpLabel
OpLoopMerge %8 %9 None
OpBranch %7
%7 = OpLabel
OpBranch %8
%9 = OpLabel
OpBranch %6
%8 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main"
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpName %4 "main"
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%10 = OpTypeBool
%11 = OpConstantTrue %10
%4 = OpFunction %2 None %3
%5 = OpLabel
OpBranch %6
%6 = OpLabel
OpSelectionMerge %8 None
OpBranchConditional %11 %7 %8
%7 = OpLabel
OpBranch %8
%9 = OpLabel
OpBranch %6
%8 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, Complex) {
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main" %3
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
OpMemberDecorate %4 0 Offset 0
OpMemberDecorate %4 1 Offset 4
OpMemberDecorate %4 2 Offset 8
OpMemberDecorate %4 3 Offset 12
OpDecorate %4 Block
OpDecorate %5 DescriptorSet 0
OpDecorate %5 Binding 0
OpDecorate %3 Location 0
%6 = OpTypeVoid
%7 = OpTypeFunction %6
%8 = OpTypeBool
%9 = OpTypePointer Function %8
%10 = OpTypeInt 32 1
%4 = OpTypeStruct %10 %10 %10 %10
%11 = OpTypePointer Uniform %4
%5 = OpVariable %11 Uniform
%12 = OpConstant %10 0
%13 = OpTypePointer Uniform %10
%14 = OpTypeInt 32 0
%15 = OpConstant %14 0
%16 = OpConstant %10 1
%17 = OpConstant %10 2
%18 = OpConstant %10 3
%19 = OpTypePointer Function %10
%20 = OpConstantFalse %8
%21 = OpTypeFloat 32
%22 = OpTypeVector %21 4
%23 = OpTypePointer Output %22
%3 = OpVariable %23 Output
%2 = OpFunction %6 None %7
%24 = OpLabel
%25 = OpVariable %9 Function
%26 = OpVariable %9 Function
%27 = OpVariable %9 Function
%28 = OpVariable %9 Function
%29 = OpVariable %9 Function
%30 = OpVariable %19 Function
%31 = OpAccessChain %13 %5 %12
%32 = OpLoad %10 %31
%33 = OpINotEqual %8 %32 %15
OpStore %25 %33
%34 = OpAccessChain %13 %5 %16
%35 = OpLoad %10 %34
%36 = OpINotEqual %8 %35 %15
OpStore %26 %36
%37 = OpAccessChain %13 %5 %17
%38 = OpLoad %10 %37
%39 = OpINotEqual %8 %38 %15
OpStore %27 %39
%40 = OpAccessChain %13 %5 %18
%41 = OpLoad %10 %40
%42 = OpINotEqual %8 %41 %15
OpStore %28 %42
%43 = OpLoad %8 %25
OpStore %29 %43
OpStore %30 %12
OpBranch %44
%44 = OpLabel
OpLoopMerge %45 %46 None
OpBranch %47
%47 = OpLabel
%48 = OpLoad %8 %29
OpBranchConditional %48 %49 %45
%49 = OpLabel
%50 = OpLoad %8 %25
OpSelectionMerge %51 None
OpBranchConditional %50 %52 %51
%52 = OpLabel
%53 = OpLoad %8 %26
OpStore %29 %53
%54 = OpLoad %10 %30
%55 = OpIAdd %10 %54 %16
OpStore %30 %55
OpBranch %51
%51 = OpLabel
%56 = OpLoad %8 %26
OpSelectionMerge %57 None
OpBranchConditional %56 %58 %57
%58 = OpLabel
%59 = OpLoad %10 %30
%60 = OpIAdd %10 %59 %16
OpStore %30 %60
%61 = OpLoad %8 %29
%62 = OpLoad %8 %25
%63 = OpLogicalOr %8 %61 %62
OpStore %29 %63
%64 = OpLoad %8 %27
OpSelectionMerge %65 None
OpBranchConditional %64 %66 %65
%66 = OpLabel
%67 = OpLoad %10 %30
%68 = OpIAdd %10 %67 %17
OpStore %30 %68
%69 = OpLoad %8 %29
%70 = OpLogicalNot %8 %69
OpStore %29 %70
OpBranch %46
%65 = OpLabel
%71 = OpLoad %8 %29
%72 = OpLogicalOr %8 %71 %20
OpStore %29 %72
OpBranch %46
%57 = OpLabel
OpBranch %73
%73 = OpLabel
OpLoopMerge %74 %75 None
OpBranch %76
%76 = OpLabel
%77 = OpLoad %8 %28
OpSelectionMerge %78 None
OpBranchConditional %77 %79 %80
%79 = OpLabel
%81 = OpLoad %10 %30
OpSelectionMerge %82 None
OpSwitch %81 %83 1 %84 2 %85
%83 = OpLabel
OpBranch %82
%84 = OpLabel
%86 = OpLoad %8 %29
%87 = OpSelect %10 %86 %16 %17
%88 = OpLoad %10 %30
%89 = OpIAdd %10 %88 %87
OpStore %30 %89
OpBranch %82
%85 = OpLabel
OpBranch %75
%82 = OpLabel
%90 = OpLoad %8 %27
OpSelectionMerge %91 None
OpBranchConditional %90 %92 %91
%92 = OpLabel
OpBranch %75
%91 = OpLabel
OpBranch %78
%80 = OpLabel
OpBranch %74
%78 = OpLabel
OpBranch %75
%75 = OpLabel
%93 = OpLoad %8 %29
OpBranchConditional %93 %73 %74
%74 = OpLabel
OpBranch %46
%46 = OpLabel
OpBranch %44
%45 = OpLabel
%94 = OpLoad %10 %30
%95 = OpConvertSToF %21 %94
%96 = OpCompositeConstruct %22 %95 %95 %95 %95
OpStore %3 %96
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(2, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main" %3
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
OpMemberDecorate %4 0 Offset 0
OpMemberDecorate %4 1 Offset 4
OpMemberDecorate %4 2 Offset 8
OpMemberDecorate %4 3 Offset 12
OpDecorate %4 Block
OpDecorate %5 DescriptorSet 0
OpDecorate %5 Binding 0
OpDecorate %3 Location 0
%6 = OpTypeVoid
%7 = OpTypeFunction %6
%8 = OpTypeBool
%9 = OpTypePointer Function %8
%10 = OpTypeInt 32 1
%4 = OpTypeStruct %10 %10 %10 %10
%11 = OpTypePointer Uniform %4
%5 = OpVariable %11 Uniform
%12 = OpConstant %10 0
%13 = OpTypePointer Uniform %10
%14 = OpTypeInt 32 0
%15 = OpConstant %14 0
%16 = OpConstant %10 1
%17 = OpConstant %10 2
%18 = OpConstant %10 3
%19 = OpTypePointer Function %10
%20 = OpConstantFalse %8
%21 = OpTypeFloat 32
%22 = OpTypeVector %21 4
%23 = OpTypePointer Output %22
%3 = OpVariable %23 Output
%97 = OpConstantTrue %8
%2 = OpFunction %6 None %7
%24 = OpLabel
%25 = OpVariable %9 Function
%26 = OpVariable %9 Function
%27 = OpVariable %9 Function
%28 = OpVariable %9 Function
%29 = OpVariable %9 Function
%30 = OpVariable %19 Function
%31 = OpAccessChain %13 %5 %12
%32 = OpLoad %10 %31
%33 = OpINotEqual %8 %32 %15
OpStore %25 %33
%34 = OpAccessChain %13 %5 %16
%35 = OpLoad %10 %34
%36 = OpINotEqual %8 %35 %15
OpStore %26 %36
%37 = OpAccessChain %13 %5 %17
%38 = OpLoad %10 %37
%39 = OpINotEqual %8 %38 %15
OpStore %27 %39
%40 = OpAccessChain %13 %5 %18
%41 = OpLoad %10 %40
%42 = OpINotEqual %8 %41 %15
OpStore %28 %42
%43 = OpLoad %8 %25
OpStore %29 %43
OpStore %30 %12
OpBranch %44
%44 = OpLabel
OpSelectionMerge %45 None ; Was OpLoopMerge %45 %46 None
OpBranchConditional %97 %47 %45 ; Was OpBranch %47
%47 = OpLabel
%48 = OpLoad %8 %29
OpBranchConditional %48 %49 %45
%49 = OpLabel
%50 = OpLoad %8 %25
OpSelectionMerge %51 None
OpBranchConditional %50 %52 %51
%52 = OpLabel
%53 = OpLoad %8 %26
OpStore %29 %53
%54 = OpLoad %10 %30
%55 = OpIAdd %10 %54 %16
OpStore %30 %55
OpBranch %51
%51 = OpLabel
%56 = OpLoad %8 %26
OpSelectionMerge %57 None
OpBranchConditional %56 %58 %57
%58 = OpLabel
%59 = OpLoad %10 %30
%60 = OpIAdd %10 %59 %16
OpStore %30 %60
%61 = OpLoad %8 %29
%62 = OpLoad %8 %25
%63 = OpLogicalOr %8 %61 %62
OpStore %29 %63
%64 = OpLoad %8 %27
OpSelectionMerge %65 None
OpBranchConditional %64 %66 %65
%66 = OpLabel
%67 = OpLoad %10 %30
%68 = OpIAdd %10 %67 %17
OpStore %30 %68
%69 = OpLoad %8 %29
%70 = OpLogicalNot %8 %69
OpStore %29 %70
OpBranch %65 ; Was OpBranch %46
%65 = OpLabel
%71 = OpLoad %8 %29
%72 = OpLogicalOr %8 %71 %20
OpStore %29 %72
OpBranch %57 ; Was OpBranch %46
%57 = OpLabel
OpBranch %73
%73 = OpLabel
OpLoopMerge %74 %75 None
OpBranch %76
%76 = OpLabel
%77 = OpLoad %8 %28
OpSelectionMerge %78 None
OpBranchConditional %77 %79 %80
%79 = OpLabel
%81 = OpLoad %10 %30
OpSelectionMerge %82 None
OpSwitch %81 %83 1 %84 2 %85
%83 = OpLabel
OpBranch %82
%84 = OpLabel
%86 = OpLoad %8 %29
%87 = OpSelect %10 %86 %16 %17
%88 = OpLoad %10 %30
%89 = OpIAdd %10 %88 %87
OpStore %30 %89
OpBranch %82
%85 = OpLabel
OpBranch %75
%82 = OpLabel
%90 = OpLoad %8 %27
OpSelectionMerge %91 None
OpBranchConditional %90 %92 %91
%92 = OpLabel
OpBranch %75
%91 = OpLabel
OpBranch %78
%80 = OpLabel
OpBranch %74
%78 = OpLabel
OpBranch %75
%75 = OpLabel
%93 = OpLoad %8 %29
OpBranchConditional %93 %73 %74
%74 = OpLabel
OpBranch %45 ; Was OpBranch %46
%46 = OpLabel
OpBranch %44
%45 = OpLabel
%94 = OpLoad %10 %30
%95 = OpConvertSToF %21 %94
%96 = OpCompositeConstruct %22 %95 %95 %95 %95
OpStore %3 %96
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
ASSERT_TRUE(ops[1]->PreconditionHolds());
ops[1]->TryToApply();
CheckValid(env, context.get());
std::string after_op_1 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main" %3
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
OpMemberDecorate %4 0 Offset 0
OpMemberDecorate %4 1 Offset 4
OpMemberDecorate %4 2 Offset 8
OpMemberDecorate %4 3 Offset 12
OpDecorate %4 Block
OpDecorate %5 DescriptorSet 0
OpDecorate %5 Binding 0
OpDecorate %3 Location 0
%6 = OpTypeVoid
%7 = OpTypeFunction %6
%8 = OpTypeBool
%9 = OpTypePointer Function %8
%10 = OpTypeInt 32 1
%4 = OpTypeStruct %10 %10 %10 %10
%11 = OpTypePointer Uniform %4
%5 = OpVariable %11 Uniform
%12 = OpConstant %10 0
%13 = OpTypePointer Uniform %10
%14 = OpTypeInt 32 0
%15 = OpConstant %14 0
%16 = OpConstant %10 1
%17 = OpConstant %10 2
%18 = OpConstant %10 3
%19 = OpTypePointer Function %10
%20 = OpConstantFalse %8
%21 = OpTypeFloat 32
%22 = OpTypeVector %21 4
%23 = OpTypePointer Output %22
%3 = OpVariable %23 Output
%97 = OpConstantTrue %8
%2 = OpFunction %6 None %7
%24 = OpLabel
%25 = OpVariable %9 Function
%26 = OpVariable %9 Function
%27 = OpVariable %9 Function
%28 = OpVariable %9 Function
%29 = OpVariable %9 Function
%30 = OpVariable %19 Function
%31 = OpAccessChain %13 %5 %12
%32 = OpLoad %10 %31
%33 = OpINotEqual %8 %32 %15
OpStore %25 %33
%34 = OpAccessChain %13 %5 %16
%35 = OpLoad %10 %34
%36 = OpINotEqual %8 %35 %15
OpStore %26 %36
%37 = OpAccessChain %13 %5 %17
%38 = OpLoad %10 %37
%39 = OpINotEqual %8 %38 %15
OpStore %27 %39
%40 = OpAccessChain %13 %5 %18
%41 = OpLoad %10 %40
%42 = OpINotEqual %8 %41 %15
OpStore %28 %42
%43 = OpLoad %8 %25
OpStore %29 %43
OpStore %30 %12
OpBranch %44
%44 = OpLabel
OpSelectionMerge %45 None ; Was OpLoopMerge %45 %46 None
OpBranchConditional %97 %47 %45 ; Was OpBranch %47
%47 = OpLabel
%48 = OpLoad %8 %29
OpBranchConditional %48 %49 %45
%49 = OpLabel
%50 = OpLoad %8 %25
OpSelectionMerge %51 None
OpBranchConditional %50 %52 %51
%52 = OpLabel
%53 = OpLoad %8 %26
OpStore %29 %53
%54 = OpLoad %10 %30
%55 = OpIAdd %10 %54 %16
OpStore %30 %55
OpBranch %51
%51 = OpLabel
%56 = OpLoad %8 %26
OpSelectionMerge %57 None
OpBranchConditional %56 %58 %57
%58 = OpLabel
%59 = OpLoad %10 %30
%60 = OpIAdd %10 %59 %16
OpStore %30 %60
%61 = OpLoad %8 %29
%62 = OpLoad %8 %25
%63 = OpLogicalOr %8 %61 %62
OpStore %29 %63
%64 = OpLoad %8 %27
OpSelectionMerge %65 None
OpBranchConditional %64 %66 %65
%66 = OpLabel
%67 = OpLoad %10 %30
%68 = OpIAdd %10 %67 %17
OpStore %30 %68
%69 = OpLoad %8 %29
%70 = OpLogicalNot %8 %69
OpStore %29 %70
OpBranch %65 ; Was OpBranch %46
%65 = OpLabel
%71 = OpLoad %8 %29
%72 = OpLogicalOr %8 %71 %20
OpStore %29 %72
OpBranch %57 ; Was OpBranch %46
%57 = OpLabel
OpBranch %73
%73 = OpLabel
OpSelectionMerge %74 None ; Was OpLoopMerge %74 %75 None
OpBranchConditional %97 %76 %74 ; Was OpBranch %76
%76 = OpLabel
%77 = OpLoad %8 %28
OpSelectionMerge %78 None
OpBranchConditional %77 %79 %80
%79 = OpLabel
%81 = OpLoad %10 %30
OpSelectionMerge %82 None
OpSwitch %81 %83 1 %84 2 %85
%83 = OpLabel
OpBranch %82
%84 = OpLabel
%86 = OpLoad %8 %29
%87 = OpSelect %10 %86 %16 %17
%88 = OpLoad %10 %30
%89 = OpIAdd %10 %88 %87
OpStore %30 %89
OpBranch %82
%85 = OpLabel
OpBranch %82
%82 = OpLabel
%90 = OpLoad %8 %27
OpSelectionMerge %91 None
OpBranchConditional %90 %92 %91
%92 = OpLabel
OpBranch %91
%91 = OpLabel
OpBranch %78
%80 = OpLabel
OpBranch %78 ; Was OpBranch %74
%78 = OpLabel
OpBranch %74
%75 = OpLabel
%93 = OpLoad %8 %29
OpBranchConditional %93 %73 %74
%74 = OpLabel
OpBranch %45 ; Was OpBranch %46
%46 = OpLabel
OpBranch %44
%45 = OpLabel
%94 = OpLoad %10 %30
%95 = OpConvertSToF %21 %94
%96 = OpCompositeConstruct %22 %95 %95 %95 %95
OpStore %3 %96
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_1, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, ComplexOptimized) {
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main" %3
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
OpMemberDecorate %4 0 Offset 0
OpMemberDecorate %4 1 Offset 4
OpMemberDecorate %4 2 Offset 8
OpMemberDecorate %4 3 Offset 12
OpDecorate %4 Block
OpDecorate %5 DescriptorSet 0
OpDecorate %5 Binding 0
OpDecorate %3 Location 0
%6 = OpTypeVoid
%7 = OpTypeFunction %6
%8 = OpTypeBool
%10 = OpTypeInt 32 1
%4 = OpTypeStruct %10 %10 %10 %10
%11 = OpTypePointer Uniform %4
%5 = OpVariable %11 Uniform
%12 = OpConstant %10 0
%13 = OpTypePointer Uniform %10
%14 = OpTypeInt 32 0
%15 = OpConstant %14 0
%16 = OpConstant %10 1
%17 = OpConstant %10 2
%18 = OpConstant %10 3
%20 = OpConstantFalse %8
%21 = OpTypeFloat 32
%22 = OpTypeVector %21 4
%23 = OpTypePointer Output %22
%3 = OpVariable %23 Output
%2 = OpFunction %6 None %7
%24 = OpLabel
%31 = OpAccessChain %13 %5 %12
%32 = OpLoad %10 %31
%33 = OpINotEqual %8 %32 %15
%34 = OpAccessChain %13 %5 %16
%35 = OpLoad %10 %34
%36 = OpINotEqual %8 %35 %15
%37 = OpAccessChain %13 %5 %17
%38 = OpLoad %10 %37
%39 = OpINotEqual %8 %38 %15
%40 = OpAccessChain %13 %5 %18
%41 = OpLoad %10 %40
%42 = OpINotEqual %8 %41 %15
OpBranch %44
%44 = OpLabel
%98 = OpPhi %10 %12 %24 %107 %46
%97 = OpPhi %8 %33 %24 %105 %46
OpLoopMerge %45 %46 None
OpBranchConditional %97 %49 %45
%49 = OpLabel
OpSelectionMerge %51 None
OpBranchConditional %33 %52 %51
%52 = OpLabel
%55 = OpIAdd %10 %98 %16
OpBranch %51
%51 = OpLabel
%100 = OpPhi %10 %98 %49 %55 %52
%113 = OpSelect %8 %33 %36 %97
OpSelectionMerge %57 None
OpBranchConditional %36 %58 %57
%58 = OpLabel
%60 = OpIAdd %10 %100 %16
%63 = OpLogicalOr %8 %113 %33
OpSelectionMerge %65 None
OpBranchConditional %39 %66 %65
%66 = OpLabel
%68 = OpIAdd %10 %100 %18
%70 = OpLogicalNot %8 %63
OpBranch %46
%65 = OpLabel
%72 = OpLogicalOr %8 %63 %20
OpBranch %46
%57 = OpLabel
OpBranch %73
%73 = OpLabel
%99 = OpPhi %10 %100 %57 %109 %75
OpLoopMerge %74 %75 None
OpBranch %76
%76 = OpLabel
OpSelectionMerge %78 None
OpBranchConditional %42 %79 %80
%79 = OpLabel
OpSelectionMerge %82 None
OpSwitch %99 %83 1 %84 2 %85
%83 = OpLabel
OpBranch %82
%84 = OpLabel
%87 = OpSelect %10 %113 %16 %17
%89 = OpIAdd %10 %99 %87
OpBranch %82
%85 = OpLabel
OpBranch %75
%82 = OpLabel
%110 = OpPhi %10 %99 %83 %89 %84
OpSelectionMerge %91 None
OpBranchConditional %39 %92 %91
%92 = OpLabel
OpBranch %75
%91 = OpLabel
OpBranch %78
%80 = OpLabel
OpBranch %74
%78 = OpLabel
OpBranch %75
%75 = OpLabel
%109 = OpPhi %10 %99 %85 %110 %92 %110 %78
OpBranchConditional %113 %73 %74
%74 = OpLabel
%108 = OpPhi %10 %99 %80 %109 %75
OpBranch %46
%46 = OpLabel
%107 = OpPhi %10 %68 %66 %60 %65 %108 %74
%105 = OpPhi %8 %70 %66 %72 %65 %113 %74
OpBranch %44
%45 = OpLabel
%95 = OpConvertSToF %21 %98
%96 = OpCompositeConstruct %22 %95 %95 %95 %95
OpStore %3 %96
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(2, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main" %3
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
OpMemberDecorate %4 0 Offset 0
OpMemberDecorate %4 1 Offset 4
OpMemberDecorate %4 2 Offset 8
OpMemberDecorate %4 3 Offset 12
OpDecorate %4 Block
OpDecorate %5 DescriptorSet 0
OpDecorate %5 Binding 0
OpDecorate %3 Location 0
%6 = OpTypeVoid
%7 = OpTypeFunction %6
%8 = OpTypeBool
%10 = OpTypeInt 32 1
%4 = OpTypeStruct %10 %10 %10 %10
%11 = OpTypePointer Uniform %4
%5 = OpVariable %11 Uniform
%12 = OpConstant %10 0
%13 = OpTypePointer Uniform %10
%14 = OpTypeInt 32 0
%15 = OpConstant %14 0
%16 = OpConstant %10 1
%17 = OpConstant %10 2
%18 = OpConstant %10 3
%20 = OpConstantFalse %8
%21 = OpTypeFloat 32
%22 = OpTypeVector %21 4
%23 = OpTypePointer Output %22
%3 = OpVariable %23 Output
%114 = OpUndef %10
%115 = OpUndef %8
%2 = OpFunction %6 None %7
%24 = OpLabel
%31 = OpAccessChain %13 %5 %12
%32 = OpLoad %10 %31
%33 = OpINotEqual %8 %32 %15
%34 = OpAccessChain %13 %5 %16
%35 = OpLoad %10 %34
%36 = OpINotEqual %8 %35 %15
%37 = OpAccessChain %13 %5 %17
%38 = OpLoad %10 %37
%39 = OpINotEqual %8 %38 %15
%40 = OpAccessChain %13 %5 %18
%41 = OpLoad %10 %40
%42 = OpINotEqual %8 %41 %15
OpBranch %44
%44 = OpLabel
%98 = OpPhi %10 %12 %24 %114 %46
%97 = OpPhi %8 %33 %24 %115 %46
OpSelectionMerge %45 None ; Was OpLoopMerge %45 %46 None
OpBranchConditional %97 %49 %45
%49 = OpLabel
OpSelectionMerge %51 None
OpBranchConditional %33 %52 %51
%52 = OpLabel
%55 = OpIAdd %10 %98 %16
OpBranch %51
%51 = OpLabel
%100 = OpPhi %10 %98 %49 %55 %52
%113 = OpSelect %8 %33 %36 %97
OpSelectionMerge %57 None
OpBranchConditional %36 %58 %57
%58 = OpLabel
%60 = OpIAdd %10 %100 %16
%63 = OpLogicalOr %8 %113 %33
OpSelectionMerge %65 None
OpBranchConditional %39 %66 %65
%66 = OpLabel
%68 = OpIAdd %10 %100 %18
%70 = OpLogicalNot %8 %63
OpBranch %65 ; Was OpBranch %46
%65 = OpLabel
%72 = OpLogicalOr %8 %63 %20
OpBranch %57 ; Was OpBranch %46
%57 = OpLabel
OpBranch %73
%73 = OpLabel
%99 = OpPhi %10 %100 %57 %109 %75
OpLoopMerge %74 %75 None
OpBranch %76
%76 = OpLabel
OpSelectionMerge %78 None
OpBranchConditional %42 %79 %80
%79 = OpLabel
OpSelectionMerge %82 None
OpSwitch %99 %83 1 %84 2 %85
%83 = OpLabel
OpBranch %82
%84 = OpLabel
%87 = OpSelect %10 %113 %16 %17
%89 = OpIAdd %10 %99 %87
OpBranch %82
%85 = OpLabel
OpBranch %75
%82 = OpLabel
%110 = OpPhi %10 %99 %83 %89 %84
OpSelectionMerge %91 None
OpBranchConditional %39 %92 %91
%92 = OpLabel
OpBranch %75
%91 = OpLabel
OpBranch %78
%80 = OpLabel
OpBranch %74
%78 = OpLabel
OpBranch %75
%75 = OpLabel
%109 = OpPhi %10 %99 %85 %110 %92 %110 %78
OpBranchConditional %113 %73 %74
%74 = OpLabel
%108 = OpPhi %10 %99 %80 %109 %75
OpBranch %45 ; Was OpBranch %46
%46 = OpLabel
%107 = OpPhi %10 ; Was OpPhi %10 %68 %66 %60 %65 %108 %74
%105 = OpPhi %8 ; Was OpPhi %8 %70 %66 %72 %65 %113 %74
OpBranch %44
%45 = OpLabel
%95 = OpConvertSToF %21 %98
%96 = OpCompositeConstruct %22 %95 %95 %95 %95
OpStore %3 %96
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
ASSERT_TRUE(ops[1]->PreconditionHolds());
ops[1]->TryToApply();
CheckValid(env, context.get());
std::string after_op_1 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main" %3
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
OpMemberDecorate %4 0 Offset 0
OpMemberDecorate %4 1 Offset 4
OpMemberDecorate %4 2 Offset 8
OpMemberDecorate %4 3 Offset 12
OpDecorate %4 Block
OpDecorate %5 DescriptorSet 0
OpDecorate %5 Binding 0
OpDecorate %3 Location 0
%6 = OpTypeVoid
%7 = OpTypeFunction %6
%8 = OpTypeBool
%10 = OpTypeInt 32 1
%4 = OpTypeStruct %10 %10 %10 %10
%11 = OpTypePointer Uniform %4
%5 = OpVariable %11 Uniform
%12 = OpConstant %10 0
%13 = OpTypePointer Uniform %10
%14 = OpTypeInt 32 0
%15 = OpConstant %14 0
%16 = OpConstant %10 1
%17 = OpConstant %10 2
%18 = OpConstant %10 3
%20 = OpConstantFalse %8
%21 = OpTypeFloat 32
%22 = OpTypeVector %21 4
%23 = OpTypePointer Output %22
%3 = OpVariable %23 Output
%114 = OpUndef %10
%115 = OpUndef %8
%116 = OpConstantTrue %8
%2 = OpFunction %6 None %7
%24 = OpLabel
%31 = OpAccessChain %13 %5 %12
%32 = OpLoad %10 %31
%33 = OpINotEqual %8 %32 %15
%34 = OpAccessChain %13 %5 %16
%35 = OpLoad %10 %34
%36 = OpINotEqual %8 %35 %15
%37 = OpAccessChain %13 %5 %17
%38 = OpLoad %10 %37
%39 = OpINotEqual %8 %38 %15
%40 = OpAccessChain %13 %5 %18
%41 = OpLoad %10 %40
%42 = OpINotEqual %8 %41 %15
OpBranch %44
%44 = OpLabel
%98 = OpPhi %10 %12 %24 %114 %46
%97 = OpPhi %8 %33 %24 %115 %46
OpSelectionMerge %45 None ; Was OpLoopMerge %45 %46 None
OpBranchConditional %97 %49 %45
%49 = OpLabel
OpSelectionMerge %51 None
OpBranchConditional %33 %52 %51
%52 = OpLabel
%55 = OpIAdd %10 %98 %16
OpBranch %51
%51 = OpLabel
%100 = OpPhi %10 %98 %49 %55 %52
%113 = OpSelect %8 %33 %36 %97
OpSelectionMerge %57 None
OpBranchConditional %36 %58 %57
%58 = OpLabel
%60 = OpIAdd %10 %100 %16
%63 = OpLogicalOr %8 %113 %33
OpSelectionMerge %65 None
OpBranchConditional %39 %66 %65
%66 = OpLabel
%68 = OpIAdd %10 %100 %18
%70 = OpLogicalNot %8 %63
OpBranch %65 ; Was OpBranch %46
%65 = OpLabel
%72 = OpLogicalOr %8 %63 %20
OpBranch %57 ; Was OpBranch %46
%57 = OpLabel
OpBranch %73
%73 = OpLabel
%99 = OpPhi %10 %100 %57 %114 %75
OpSelectionMerge %74 None ; Was OpLoopMerge %74 %75 None
OpBranchConditional %116 %76 %74
%76 = OpLabel
OpSelectionMerge %78 None
OpBranchConditional %42 %79 %80
%79 = OpLabel
OpSelectionMerge %82 None
OpSwitch %99 %83 1 %84 2 %85
%83 = OpLabel
OpBranch %82
%84 = OpLabel
%87 = OpSelect %10 %113 %16 %17
%89 = OpIAdd %10 %99 %87
OpBranch %82
%85 = OpLabel
OpBranch %82 ; Was OpBranch %75
%82 = OpLabel
%110 = OpPhi %10 %99 %83 %89 %84 %114 %85 ; Was OpPhi %10 %99 %83 %89 %84
OpSelectionMerge %91 None
OpBranchConditional %39 %92 %91
%92 = OpLabel
OpBranch %91 ; OpBranch %75
%91 = OpLabel
OpBranch %78
%80 = OpLabel
OpBranch %78 ; Was OpBranch %74
%78 = OpLabel
OpBranch %74 ; Was OpBranch %75
%75 = OpLabel
%109 = OpPhi %10 ; Was OpPhi %10 %99 %85 %110 %92 %110 %78
OpBranchConditional %115 %73 %74
%74 = OpLabel
%108 = OpPhi %10 %114 %75 %114 %78 %114 %73 ; Was OpPhi %10 %99 %80 %109 %75
OpBranch %45 ; Was OpBranch %46
%46 = OpLabel
%107 = OpPhi %10 ; Was OpPhi %10 %68 %66 %60 %65 %108 %74
%105 = OpPhi %8 ; Was OpPhi %8 %70 %66 %72 %65 %113 %74
OpBranch %44
%45 = OpLabel
%95 = OpConvertSToF %21 %98
%96 = OpCompositeConstruct %22 %95 %95 %95 %95
OpStore %3 %96
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_1, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, DominanceIssue) {
// Exposes a scenario where redirecting edges results in uses of ids being
// non-dominated. We replace such uses with OpUndef to account for this.
std::string shader = 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
%5 = OpTypeInt 32 1
%7 = OpTypePointer Function %5
%6 = OpTypeBool
%8 = OpConstantTrue %6
%9 = OpConstant %5 10
%10 = OpConstant %5 20
%11 = OpConstant %5 30
%4 = OpFunction %2 None %3
%12 = OpLabel
OpBranch %13
%13 = OpLabel
OpLoopMerge %14 %15 None
OpBranch %16
%16 = OpLabel
OpSelectionMerge %17 None
OpBranchConditional %8 %18 %19
%18 = OpLabel
OpBranch %14
%19 = OpLabel
%20 = OpIAdd %5 %9 %10
OpBranch %17
%17 = OpLabel
%21 = OpIAdd %5 %20 %11
OpBranchConditional %8 %14 %15
%15 = OpLabel
OpBranch %13
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string expected = 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
%5 = OpTypeInt 32 1
%7 = OpTypePointer Function %5
%6 = OpTypeBool
%8 = OpConstantTrue %6
%9 = OpConstant %5 10
%10 = OpConstant %5 20
%11 = OpConstant %5 30
%22 = OpUndef %5
%4 = OpFunction %2 None %3
%12 = OpLabel
OpBranch %13
%13 = OpLabel
OpSelectionMerge %14 None
OpBranchConditional %8 %16 %14
%16 = OpLabel
OpSelectionMerge %17 None
OpBranchConditional %8 %18 %19
%18 = OpLabel
OpBranch %17
%19 = OpLabel
%20 = OpIAdd %5 %9 %10
OpBranch %17
%17 = OpLabel
%21 = OpIAdd %5 %22 %11
OpBranchConditional %8 %14 %14
%15 = OpLabel
OpBranch %13
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, AccessChainIssue) {
// Exposes a scenario where redirecting edges results in a use of an id
// generated by an access chain being non-dominated.
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main" %56
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpMemberDecorate %28 0 Offset 0
OpDecorate %28 Block
OpDecorate %30 DescriptorSet 0
OpDecorate %30 Binding 0
OpDecorate %56 Location 0
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%6 = OpTypeFloat 32
%7 = OpTypeVector %6 2
%8 = OpTypePointer Function %7
%60 = OpTypePointer Private %7
%10 = OpConstant %6 0
%11 = OpConstantComposite %7 %10 %10
%12 = OpTypePointer Function %6
%59 = OpTypePointer Private %6
%14 = OpTypeInt 32 1
%15 = OpTypePointer Function %14
%17 = OpConstant %14 0
%24 = OpConstant %14 100
%25 = OpTypeBool
%28 = OpTypeStruct %6
%29 = OpTypePointer Uniform %28
%30 = OpVariable %29 Uniform
%31 = OpTypePointer Uniform %6
%39 = OpTypeInt 32 0
%40 = OpConstant %39 1
%45 = OpConstant %39 0
%52 = OpConstant %14 1
%54 = OpTypeVector %6 4
%55 = OpTypePointer Output %54
%56 = OpVariable %55 Output
%9 = OpVariable %60 Private
%4 = OpFunction %2 None %3
%5 = OpLabel
%13 = OpVariable %12 Function
%16 = OpVariable %15 Function
%38 = OpVariable %12 Function
OpStore %9 %11
OpStore %13 %10
OpStore %16 %17
OpBranch %18
%18 = OpLabel
OpLoopMerge %20 %21 None
OpBranch %22
%22 = OpLabel
%23 = OpLoad %14 %16
%26 = OpSLessThan %25 %23 %24
OpBranchConditional %26 %19 %20
%19 = OpLabel
%27 = OpLoad %14 %16
%32 = OpAccessChain %31 %30 %17
%33 = OpLoad %6 %32
%34 = OpConvertFToS %14 %33
%35 = OpSLessThan %25 %27 %34
OpSelectionMerge %37 None
OpBranchConditional %35 %36 %44
%36 = OpLabel
%41 = OpAccessChain %59 %9 %40
%42 = OpLoad %6 %41
OpStore %38 %42
OpBranch %20
%44 = OpLabel
%46 = OpAccessChain %59 %9 %45
OpBranch %37
%37 = OpLabel
%47 = OpLoad %6 %46
OpStore %38 %47
%48 = OpLoad %6 %38
%49 = OpLoad %6 %13
%50 = OpFAdd %6 %49 %48
OpStore %13 %50
OpBranch %21
%21 = OpLabel
%51 = OpLoad %14 %16
%53 = OpIAdd %14 %51 %52
OpStore %16 %53
OpBranch %18
%20 = OpLabel
%57 = OpLoad %6 %13
%58 = OpCompositeConstruct %54 %57 %57 %57 %57
OpStore %56 %58
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string expected = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main" %56
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpMemberDecorate %28 0 Offset 0
OpDecorate %28 Block
OpDecorate %30 DescriptorSet 0
OpDecorate %30 Binding 0
OpDecorate %56 Location 0
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%6 = OpTypeFloat 32
%7 = OpTypeVector %6 2
%8 = OpTypePointer Function %7
%60 = OpTypePointer Private %7
%10 = OpConstant %6 0
%11 = OpConstantComposite %7 %10 %10
%12 = OpTypePointer Function %6
%59 = OpTypePointer Private %6
%14 = OpTypeInt 32 1
%15 = OpTypePointer Function %14
%17 = OpConstant %14 0
%24 = OpConstant %14 100
%25 = OpTypeBool
%28 = OpTypeStruct %6
%29 = OpTypePointer Uniform %28
%30 = OpVariable %29 Uniform
%31 = OpTypePointer Uniform %6
%39 = OpTypeInt 32 0
%40 = OpConstant %39 1
%45 = OpConstant %39 0
%52 = OpConstant %14 1
%54 = OpTypeVector %6 4
%55 = OpTypePointer Output %54
%56 = OpVariable %55 Output
%9 = OpVariable %60 Private
%61 = OpConstantTrue %25
%62 = OpVariable %59 Private
%4 = OpFunction %2 None %3
%5 = OpLabel
%13 = OpVariable %12 Function
%16 = OpVariable %15 Function
%38 = OpVariable %12 Function
OpStore %9 %11
OpStore %13 %10
OpStore %16 %17
OpBranch %18
%18 = OpLabel
OpSelectionMerge %20 None
OpBranchConditional %61 %22 %20
%22 = OpLabel
%23 = OpLoad %14 %16
%26 = OpSLessThan %25 %23 %24
OpBranchConditional %26 %19 %20
%19 = OpLabel
%27 = OpLoad %14 %16
%32 = OpAccessChain %31 %30 %17
%33 = OpLoad %6 %32
%34 = OpConvertFToS %14 %33
%35 = OpSLessThan %25 %27 %34
OpSelectionMerge %37 None
OpBranchConditional %35 %36 %44
%36 = OpLabel
%41 = OpAccessChain %59 %9 %40
%42 = OpLoad %6 %41
OpStore %38 %42
OpBranch %37
%44 = OpLabel
%46 = OpAccessChain %59 %9 %45
OpBranch %37
%37 = OpLabel
%47 = OpLoad %6 %62
OpStore %38 %47
%48 = OpLoad %6 %38
%49 = OpLoad %6 %13
%50 = OpFAdd %6 %49 %48
OpStore %13 %50
OpBranch %20
%21 = OpLabel
%51 = OpLoad %14 %16
%53 = OpIAdd %14 %51 %52
OpStore %16 %53
OpBranch %18
%20 = OpLabel
%57 = OpLoad %6 %13
%58 = OpCompositeConstruct %54 %57 %57 %57 %57
OpStore %56 %58
OpReturn
OpFunctionEnd
)";
CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, DominanceAndPhiIssue) {
// Exposes an interesting scenario where a use in a phi stops being dominated
// by the block with which it is associated in the phi.
std::string shader = 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
%17 = OpTypeBool
%18 = OpConstantTrue %17
%19 = OpConstantFalse %17
%20 = OpTypeInt 32 1
%21 = OpConstant %20 5
%22 = OpConstant %20 6
%4 = OpFunction %2 None %3
%5 = OpLabel
OpBranch %6
%6 = OpLabel
OpLoopMerge %16 %15 None
OpBranch %7
%7 = OpLabel
OpSelectionMerge %13 None
OpBranchConditional %18 %8 %9
%8 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %18 %10 %11
%9 = OpLabel
OpBranch %16
%10 = OpLabel
OpBranch %16
%11 = OpLabel
%23 = OpIAdd %20 %21 %22
OpBranch %12
%12 = OpLabel
OpBranch %13
%13 = OpLabel
OpBranch %14
%14 = OpLabel
%24 = OpPhi %20 %23 %13
OpBranchConditional %19 %15 %16
%15 = OpLabel
OpBranch %6
%16 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string expected = 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
%17 = OpTypeBool
%18 = OpConstantTrue %17
%19 = OpConstantFalse %17
%20 = OpTypeInt 32 1
%21 = OpConstant %20 5
%22 = OpConstant %20 6
%25 = OpUndef %20
%4 = OpFunction %2 None %3
%5 = OpLabel
OpBranch %6
%6 = OpLabel
OpSelectionMerge %16 None
OpBranchConditional %18 %7 %16
%7 = OpLabel
OpSelectionMerge %13 None
OpBranchConditional %18 %8 %9
%8 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %18 %10 %11
%9 = OpLabel
OpBranch %13
%10 = OpLabel
OpBranch %12
%11 = OpLabel
%23 = OpIAdd %20 %21 %22
OpBranch %12
%12 = OpLabel
OpBranch %13
%13 = OpLabel
OpBranch %14
%14 = OpLabel
%24 = OpPhi %20 %25 %13
OpBranchConditional %19 %16 %16
%15 = OpLabel
OpBranch %6
%16 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, OpLineBeforeOpPhi) {
// Test to ensure the pass knows OpLine and OpPhi instructions can be
// interleaved.
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpString "somefile"
%4 = OpTypeVoid
%5 = OpTypeFunction %4
%6 = OpTypeInt 32 1
%7 = OpConstant %6 10
%8 = OpConstant %6 20
%9 = OpConstant %6 30
%10 = OpTypeBool
%11 = OpConstantTrue %10
%2 = OpFunction %4 None %5
%12 = OpLabel
OpBranch %13
%13 = OpLabel
OpLoopMerge %14 %15 None
OpBranch %16
%16 = OpLabel
OpSelectionMerge %17 None
OpBranchConditional %11 %18 %19
%18 = OpLabel
%20 = OpIAdd %6 %7 %8
%21 = OpIAdd %6 %7 %9
OpBranch %17
%19 = OpLabel
OpBranch %14
%17 = OpLabel
%22 = OpPhi %6 %20 %18
OpLine %3 0 0
%23 = OpPhi %6 %21 %18
OpBranch %15
%15 = OpLabel
OpBranch %13
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string expected = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpString "somefile"
%4 = OpTypeVoid
%5 = OpTypeFunction %4
%6 = OpTypeInt 32 1
%7 = OpConstant %6 10
%8 = OpConstant %6 20
%9 = OpConstant %6 30
%10 = OpTypeBool
%11 = OpConstantTrue %10
%24 = OpUndef %6
%2 = OpFunction %4 None %5
%12 = OpLabel
OpBranch %13
%13 = OpLabel
OpSelectionMerge %14 None
OpBranchConditional %11 %16 %14
%16 = OpLabel
OpSelectionMerge %17 None
OpBranchConditional %11 %18 %19
%18 = OpLabel
%20 = OpIAdd %6 %7 %8
%21 = OpIAdd %6 %7 %9
OpBranch %17
%19 = OpLabel
OpBranch %17
%17 = OpLabel
%22 = OpPhi %6 %20 %18 %24 %19
OpLine %3 0 0
%23 = OpPhi %6 %21 %18 %24 %19
OpBranch %14
%15 = OpLabel
OpBranch %13
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest,
SelectionMergeIsContinueTarget) {
// Example where a loop's continue target is also the target of a selection.
// In this scenario we cautiously do not apply the transformation.
std::string shader = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%3 = OpTypeBool
%4 = OpTypeFunction %2
%1 = OpFunction %2 None %4
%5 = OpLabel
%6 = OpUndef %3
OpBranch %7
%7 = OpLabel
%8 = OpPhi %3 %6 %5 %9 %10
OpLoopMerge %11 %10 None
OpBranch %12
%12 = OpLabel
%13 = OpUndef %3
OpSelectionMerge %10 None
OpBranchConditional %13 %14 %10
%14 = OpLabel
OpBranch %10
%10 = OpLabel
%9 = OpUndef %3
OpBranchConditional %9 %7 %11
%11 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
// There should be no opportunities.
ASSERT_EQ(0, ops.size());
}
TEST(StructuredLoopToSelectionReductionPassTest,
SwitchSelectionMergeIsContinueTarget) {
// Another example where a loop's continue target is also the target of a
// selection; this time a selection associated with an OpSwitch. We
// cautiously do not apply the transformation.
std::string shader = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%3 = OpTypeBool
%5 = OpTypeInt 32 1
%4 = OpTypeFunction %2
%6 = OpConstant %5 2
%7 = OpConstantTrue %3
%1 = OpFunction %2 None %4
%8 = OpLabel
OpBranch %9
%9 = OpLabel
OpLoopMerge %14 %15 None
OpBranchConditional %7 %10 %14
%10 = OpLabel
OpSelectionMerge %15 None
OpSwitch %6 %12 1 %11 2 %11 3 %15
%11 = OpLabel
OpBranch %12
%12 = OpLabel
OpBranch %15
%15 = OpLabel
OpBranch %9
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
// There should be no opportunities.
ASSERT_EQ(0, ops.size());
}
TEST(StructuredLoopToSelectionReductionPassTest, ContinueTargetIsSwitchTarget) {
std::string shader = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%3 = OpTypeBool
%5 = OpTypeInt 32 1
%4 = OpTypeFunction %2
%6 = OpConstant %5 2
%7 = OpConstantTrue %3
%1 = OpFunction %2 None %4
%8 = OpLabel
OpBranch %9
%9 = OpLabel
OpLoopMerge %14 %12 None
OpBranchConditional %7 %10 %14
%10 = OpLabel
OpSelectionMerge %15 None
OpSwitch %6 %12 1 %11 2 %11 3 %15
%11 = OpLabel
OpBranch %12
%12 = OpLabel
OpBranch %9
%15 = OpLabel
OpBranch %14
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string expected = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%3 = OpTypeBool
%5 = OpTypeInt 32 1
%4 = OpTypeFunction %2
%6 = OpConstant %5 2
%7 = OpConstantTrue %3
%1 = OpFunction %2 None %4
%8 = OpLabel
OpBranch %9
%9 = OpLabel
OpSelectionMerge %14 None
OpBranchConditional %7 %10 %14
%10 = OpLabel
OpSelectionMerge %15 None
OpSwitch %6 %15 1 %11 2 %11 3 %15
%11 = OpLabel
OpBranch %15
%12 = OpLabel
OpBranch %9
%15 = OpLabel
OpBranch %14
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest,
MultipleSwitchTargetsAreContinueTarget) {
std::string shader = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%3 = OpTypeBool
%5 = OpTypeInt 32 1
%4 = OpTypeFunction %2
%6 = OpConstant %5 2
%7 = OpConstantTrue %3
%1 = OpFunction %2 None %4
%8 = OpLabel
OpBranch %9
%9 = OpLabel
OpLoopMerge %14 %12 None
OpBranchConditional %7 %10 %14
%10 = OpLabel
OpSelectionMerge %15 None
OpSwitch %6 %11 1 %12 2 %12 3 %15
%11 = OpLabel
OpBranch %12
%12 = OpLabel
OpBranch %9
%15 = OpLabel
OpBranch %14
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string expected = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%3 = OpTypeBool
%5 = OpTypeInt 32 1
%4 = OpTypeFunction %2
%6 = OpConstant %5 2
%7 = OpConstantTrue %3
%1 = OpFunction %2 None %4
%8 = OpLabel
OpBranch %9
%9 = OpLabel
OpSelectionMerge %14 None
OpBranchConditional %7 %10 %14
%10 = OpLabel
OpSelectionMerge %15 None
OpSwitch %6 %11 1 %15 2 %15 3 %15
%11 = OpLabel
OpBranch %15
%12 = OpLabel
OpBranch %9
%15 = OpLabel
OpBranch %14
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, LoopBranchesStraightToMerge) {
std::string shader = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%4 = OpTypeFunction %2
%1 = OpFunction %2 None %4
%8 = OpLabel
OpBranch %9
%9 = OpLabel
OpLoopMerge %14 %12 None
OpBranch %14
%12 = OpLabel
OpBranch %9
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string expected = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%4 = OpTypeFunction %2
%15 = OpTypeBool
%16 = OpConstantTrue %15
%1 = OpFunction %2 None %4
%8 = OpLabel
OpBranch %9
%9 = OpLabel
OpSelectionMerge %14 None
OpBranchConditional %16 %14 %14
%12 = OpLabel
OpBranch %9
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest,
LoopConditionallyJumpsToMergeOrContinue) {
std::string shader = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%3 = OpTypeBool
%4 = OpTypeFunction %2
%7 = OpConstantTrue %3
%1 = OpFunction %2 None %4
%8 = OpLabel
OpBranch %9
%9 = OpLabel
OpLoopMerge %14 %12 None
OpBranchConditional %7 %14 %12
%12 = OpLabel
OpBranch %9
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string expected = R"(
OpCapability Shader
OpMemoryModel Logical GLSL450
OpEntryPoint Vertex %1 "main"
%2 = OpTypeVoid
%3 = OpTypeBool
%4 = OpTypeFunction %2
%7 = OpConstantTrue %3
%1 = OpFunction %2 None %4
%8 = OpLabel
OpBranch %9
%9 = OpLabel
OpSelectionMerge %14 None
OpBranchConditional %7 %14 %14
%12 = OpLabel
OpBranch %9
%14 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, MultipleAccessChains) {
std::string shader = 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 = OpTypeStruct %6
%8 = OpTypeStruct %7
%9 = OpTypePointer Function %8
%11 = OpConstant %6 3
%12 = OpConstantComposite %7 %11
%13 = OpConstantComposite %8 %12
%14 = OpTypePointer Function %7
%16 = OpConstant %6 0
%19 = OpTypePointer Function %6
%15 = OpTypeBool
%18 = OpConstantTrue %15
%4 = OpFunction %2 None %3
%5 = OpLabel
%10 = OpVariable %9 Function
%20 = OpVariable %19 Function
OpStore %10 %13
OpBranch %23
%23 = OpLabel
OpLoopMerge %25 %26 None
OpBranch %27
%27 = OpLabel
OpSelectionMerge %28 None
OpBranchConditional %18 %29 %25
%29 = OpLabel
%17 = OpAccessChain %14 %10 %16
OpBranch %28
%28 = OpLabel
%21 = OpAccessChain %19 %17 %16
%22 = OpLoad %6 %21
%24 = OpAccessChain %19 %10 %16 %16
OpStore %24 %22
OpBranch %25
%26 = OpLabel
OpBranch %23
%25 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string expected = 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 = OpTypeStruct %6
%8 = OpTypeStruct %7
%9 = OpTypePointer Function %8
%11 = OpConstant %6 3
%12 = OpConstantComposite %7 %11
%13 = OpConstantComposite %8 %12
%14 = OpTypePointer Function %7
%16 = OpConstant %6 0
%19 = OpTypePointer Function %6
%15 = OpTypeBool
%18 = OpConstantTrue %15
%4 = OpFunction %2 None %3
%5 = OpLabel
%10 = OpVariable %9 Function
%20 = OpVariable %19 Function
%30 = OpVariable %14 Function
OpStore %10 %13
OpBranch %23
%23 = OpLabel
OpSelectionMerge %25 None
OpBranchConditional %18 %27 %25
%27 = OpLabel
OpSelectionMerge %28 None
OpBranchConditional %18 %29 %28
%29 = OpLabel
%17 = OpAccessChain %14 %10 %16
OpBranch %28
%28 = OpLabel
%21 = OpAccessChain %19 %30 %16
%22 = OpLoad %6 %21
%24 = OpAccessChain %19 %10 %16 %16
OpStore %24 %22
OpBranch %25
%26 = OpLabel
OpBranch %23
%25 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest,
UnreachableInnerLoopContinueBranchingToOuterLoopMerge) {
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeBool
%6 = OpConstantTrue %5
%2 = OpFunction %3 None %4
%7 = OpLabel
OpBranch %8
%8 = OpLabel
OpLoopMerge %9 %10 None
OpBranch %11
%11 = OpLabel
OpLoopMerge %12 %13 None
OpBranch %12
%13 = OpLabel
OpBranch %11
%12 = OpLabel
OpBranch %10
%10 = OpLabel
OpBranchConditional %6 %9 %8
%9 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(2, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeBool
%6 = OpConstantTrue %5
%2 = OpFunction %3 None %4
%7 = OpLabel
OpBranch %8
%8 = OpLabel
OpSelectionMerge %9 None
OpBranchConditional %6 %11 %9
%11 = OpLabel
OpLoopMerge %12 %13 None
OpBranch %12
%13 = OpLabel
OpBranch %11
%12 = OpLabel
OpBranch %9
%10 = OpLabel
OpBranchConditional %6 %9 %8
%9 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
ASSERT_TRUE(ops[1]->PreconditionHolds());
ops[1]->TryToApply();
CheckValid(env, context.get());
std::string after_op_1 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeBool
%6 = OpConstantTrue %5
%2 = OpFunction %3 None %4
%7 = OpLabel
OpBranch %8
%8 = OpLabel
OpSelectionMerge %9 None
OpBranchConditional %6 %11 %9
%11 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %6 %12 %12
%13 = OpLabel
OpBranch %11
%12 = OpLabel
OpBranch %9
%10 = OpLabel
OpBranchConditional %6 %9 %8
%9 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_1, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest,
UnreachableInnerLoopContinueBranchingToOuterLoopMerge2) {
// In this test, the unreachable continue is composed of multiple blocks.
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeBool
%6 = OpConstantTrue %5
%2 = OpFunction %3 None %4
%7 = OpLabel
OpBranch %8
%8 = OpLabel
OpLoopMerge %9 %10 None
OpBranch %11
%11 = OpLabel
OpLoopMerge %12 %13 None
OpBranch %12
%13 = OpLabel
OpBranch %14
%14 = OpLabel
OpBranch %11
%12 = OpLabel
OpBranch %10
%10 = OpLabel
OpBranchConditional %6 %9 %8
%9 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(2, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeBool
%6 = OpConstantTrue %5
%2 = OpFunction %3 None %4
%7 = OpLabel
OpBranch %8
%8 = OpLabel
OpSelectionMerge %9 None
OpBranchConditional %6 %11 %9
%11 = OpLabel
OpLoopMerge %12 %13 None
OpBranch %12
%13 = OpLabel
OpBranch %14
%14 = OpLabel
OpBranch %11
%12 = OpLabel
OpBranch %9
%10 = OpLabel
OpBranchConditional %6 %9 %8
%9 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
ASSERT_TRUE(ops[1]->PreconditionHolds());
ops[1]->TryToApply();
CheckValid(env, context.get());
std::string after_op_1 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeBool
%6 = OpConstantTrue %5
%2 = OpFunction %3 None %4
%7 = OpLabel
OpBranch %8
%8 = OpLabel
OpSelectionMerge %9 None
OpBranchConditional %6 %11 %9
%11 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %6 %12 %12
%13 = OpLabel
OpBranch %14
%14 = OpLabel
OpBranch %11
%12 = OpLabel
OpBranch %9
%10 = OpLabel
OpBranchConditional %6 %9 %8
%9 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_1, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest,
InnerLoopHeaderBranchesToOuterLoopMerge) {
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeBool
%6 = OpConstantTrue %5
%2 = OpFunction %3 None %4
%7 = OpLabel
OpBranch %8
%8 = OpLabel
OpLoopMerge %9 %10 None
OpBranch %11
%11 = OpLabel
OpLoopMerge %12 %13 None
OpBranchConditional %6 %9 %13
%13 = OpLabel
OpBranchConditional %6 %11 %12
%12 = OpLabel
OpBranch %10
%10 = OpLabel
OpBranchConditional %6 %9 %8
%9 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
// We cannot transform the inner loop due to its header jumping straight to
// the outer loop merge (the inner loop's merge does not post-dominate its
// header).
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeBool
%6 = OpConstantTrue %5
%2 = OpFunction %3 None %4
%7 = OpLabel
OpBranch %8
%8 = OpLabel
OpSelectionMerge %9 None
OpBranchConditional %6 %11 %9
%11 = OpLabel
OpLoopMerge %12 %13 None
OpBranchConditional %6 %12 %13
%13 = OpLabel
OpBranchConditional %6 %11 %12
%12 = OpLabel
OpBranch %9
%10 = OpLabel
OpBranchConditional %6 %9 %8
%9 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
// Now look again for more opportunities.
ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
// What was the inner loop should now be transformable, as the jump to the
// outer loop's merge has been redirected.
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_another_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeBool
%6 = OpConstantTrue %5
%2 = OpFunction %3 None %4
%7 = OpLabel
OpBranch %8
%8 = OpLabel
OpSelectionMerge %9 None
OpBranchConditional %6 %11 %9
%11 = OpLabel
OpSelectionMerge %12 None
OpBranchConditional %6 %12 %12
%13 = OpLabel
OpBranchConditional %6 %11 %12
%12 = OpLabel
OpBranch %9
%10 = OpLabel
OpBranchConditional %6 %9 %8
%9 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_another_op_0, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, LongAccessChains) {
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %2 "main"
OpExecutionMode %2 OriginUpperLeft
OpSource ESSL 310
%3 = OpTypeVoid
%4 = OpTypeFunction %3
%5 = OpTypeInt 32 1
%6 = OpTypeInt 32 0
%7 = OpConstant %6 5
%8 = OpTypeArray %5 %7
%9 = OpTypeStruct %8
%10 = OpTypeStruct %9 %9
%11 = OpConstant %6 2
%12 = OpTypeArray %10 %11
%13 = OpTypeStruct %12
%14 = OpTypePointer Function %13
%15 = OpConstant %5 0
%16 = OpConstant %5 1
%17 = OpConstant %5 2
%18 = OpConstant %5 3
%19 = OpConstant %5 4
%20 = OpConstantComposite %8 %15 %16 %17 %18 %19
%21 = OpConstantComposite %9 %20
%22 = OpConstant %5 5
%23 = OpConstant %5 6
%24 = OpConstant %5 7
%25 = OpConstant %5 8
%26 = OpConstant %5 9
%27 = OpConstantComposite %8 %22 %23 %24 %25 %26
%28 = OpConstantComposite %9 %27
%29 = OpConstantComposite %10 %21 %28
%30 = OpConstant %5 10
%31 = OpConstant %5 11
%32 = OpConstant %5 12
%33 = OpConstant %5 13
%34 = OpConstant %5 14
%35 = OpConstantComposite %8 %30 %31 %32 %33 %34
%36 = OpConstantComposite %9 %35
%37 = OpConstant %5 15
%38 = OpConstant %5 16
%39 = OpConstant %5 17
%40 = OpConstant %5 18
%41 = OpConstant %5 19
%42 = OpConstantComposite %8 %37 %38 %39 %40 %41
%43 = OpConstantComposite %9 %42
%44 = OpConstantComposite %10 %36 %43
%45 = OpConstantComposite %12 %29 %44
%46 = OpConstantComposite %13 %45
%47 = OpTypePointer Function %12
%48 = OpTypePointer Function %10
%49 = OpTypePointer Function %9
%50 = OpTypePointer Function %8
%51 = OpTypePointer Function %5
%52 = OpTypeBool
%53 = OpConstantTrue %52
%2 = OpFunction %3 None %4
%54 = OpLabel
%55 = OpVariable %14 Function
OpStore %55 %46
OpBranch %56
%56 = OpLabel
OpLoopMerge %57 %58 None
OpBranchConditional %53 %57 %59
%59 = OpLabel
OpSelectionMerge %60 None
OpBranchConditional %53 %61 %57
%61 = OpLabel
%62 = OpAccessChain %47 %55 %15
OpBranch %63
%63 = OpLabel
OpSelectionMerge %64 None
OpBranchConditional %53 %65 %57
%65 = OpLabel
%66 = OpAccessChain %48 %62 %16
OpBranch %67
%67 = OpLabel
OpSelectionMerge %68 None
OpBranchConditional %53 %69 %57
%69 = OpLabel
%70 = OpAccessChain %49 %66 %16
OpBranch %71
%71 = OpLabel
OpSelectionMerge %72 None
OpBranchConditional %53 %73 %57
%73 = OpLabel
%74 = OpAccessChain %50 %70 %15
OpBranch %75
%75 = OpLabel
OpSelectionMerge %76 None
OpBranchConditional %53 %77 %57
%77 = OpLabel
%78 = OpAccessChain %51 %74 %17
OpBranch %79
%79 = OpLabel
OpSelectionMerge %80 None
OpBranchConditional %53 %81 %57
%81 = OpLabel
%82 = OpLoad %5 %78
OpBranch %80
%80 = OpLabel
OpBranch %76
%76 = OpLabel
OpBranch %72
%72 = OpLabel
OpBranch %68
%68 = OpLabel
OpBranch %64
%64 = OpLabel
OpBranch %60
%60 = OpLabel
OpBranch %58
%58 = OpLabel
OpBranch %56
%57 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
// TODO(2183): When we have a more general solution for handling access
// chains, write an expected result for this test.
// std::string expected = R"(
// Expected text for transformed shader
//)";
// CheckEqual(env, expected, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest, LoopyShaderWithOpDecorate) {
// A shader containing a function that contains a loop and some definitions
// that are "used" in OpDecorate instructions (outside the function). These
// "uses" were causing segfaults because we try to calculate their dominance
// information, which doesn't make sense.
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main" %9
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpName %4 "main"
OpName %9 "_GLF_color"
OpName %14 "buf0"
OpMemberName %14 0 "a"
OpName %16 ""
OpDecorate %9 RelaxedPrecision
OpDecorate %9 Location 0
OpMemberDecorate %14 0 RelaxedPrecision
OpMemberDecorate %14 0 Offset 0
OpDecorate %14 Block
OpDecorate %16 DescriptorSet 0
OpDecorate %16 Binding 0
OpDecorate %21 RelaxedPrecision
OpDecorate %35 RelaxedPrecision
OpDecorate %36 RelaxedPrecision
OpDecorate %39 RelaxedPrecision
OpDecorate %40 RelaxedPrecision
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%6 = OpTypeFloat 32
%7 = OpTypeVector %6 4
%8 = OpTypePointer Output %7
%9 = OpVariable %8 Output
%10 = OpConstant %6 1
%11 = OpConstantComposite %7 %10 %10 %10 %10
%14 = OpTypeStruct %6
%15 = OpTypePointer Uniform %14
%16 = OpVariable %15 Uniform
%17 = OpTypeInt 32 1
%18 = OpConstant %17 0
%19 = OpTypePointer Uniform %6
%28 = OpConstant %6 2
%29 = OpTypeBool
%31 = OpTypeInt 32 0
%32 = OpConstant %31 0
%33 = OpTypePointer Output %6
%4 = OpFunction %2 None %3
%5 = OpLabel
OpStore %9 %11
%20 = OpAccessChain %19 %16 %18
%21 = OpLoad %6 %20
OpBranch %22
%22 = OpLabel
%40 = OpPhi %6 %21 %5 %39 %23
%30 = OpFOrdLessThan %29 %40 %28
OpLoopMerge %24 %23 None
OpBranchConditional %30 %23 %24
%23 = OpLabel
%34 = OpAccessChain %33 %9 %32
%35 = OpLoad %6 %34
%36 = OpFAdd %6 %35 %10
OpStore %34 %36
%39 = OpFAdd %6 %40 %10
OpBranch %22
%24 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(1, ops.size());
ASSERT_TRUE(ops[0]->PreconditionHolds());
ops[0]->TryToApply();
CheckValid(env, context.get());
std::string after_op_0 = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
OpMemoryModel Logical GLSL450
OpEntryPoint Fragment %4 "main" %9
OpExecutionMode %4 OriginUpperLeft
OpSource ESSL 310
OpName %4 "main"
OpName %9 "_GLF_color"
OpName %14 "buf0"
OpMemberName %14 0 "a"
OpName %16 ""
OpDecorate %9 RelaxedPrecision
OpDecorate %9 Location 0
OpMemberDecorate %14 0 RelaxedPrecision
OpMemberDecorate %14 0 Offset 0
OpDecorate %14 Block
OpDecorate %16 DescriptorSet 0
OpDecorate %16 Binding 0
OpDecorate %21 RelaxedPrecision
OpDecorate %35 RelaxedPrecision
OpDecorate %36 RelaxedPrecision
OpDecorate %39 RelaxedPrecision
OpDecorate %40 RelaxedPrecision
%2 = OpTypeVoid
%3 = OpTypeFunction %2
%6 = OpTypeFloat 32
%7 = OpTypeVector %6 4
%8 = OpTypePointer Output %7
%9 = OpVariable %8 Output
%10 = OpConstant %6 1
%11 = OpConstantComposite %7 %10 %10 %10 %10
%14 = OpTypeStruct %6
%15 = OpTypePointer Uniform %14
%16 = OpVariable %15 Uniform
%17 = OpTypeInt 32 1
%18 = OpConstant %17 0
%19 = OpTypePointer Uniform %6
%28 = OpConstant %6 2
%29 = OpTypeBool
%31 = OpTypeInt 32 0
%32 = OpConstant %31 0
%33 = OpTypePointer Output %6
%41 = OpUndef %6 ; Added
%4 = OpFunction %2 None %3
%5 = OpLabel
OpStore %9 %11
%20 = OpAccessChain %19 %16 %18
%21 = OpLoad %6 %20
OpBranch %22
%22 = OpLabel
%40 = OpPhi %6 %21 %5 %41 %23 ; Changed
%30 = OpFOrdLessThan %29 %40 %28
OpSelectionMerge %24 None ; Changed
OpBranchConditional %30 %24 %24
%23 = OpLabel
%34 = OpAccessChain %33 %9 %32
%35 = OpLoad %6 %34
%36 = OpFAdd %6 %35 %10
OpStore %34 %36
%39 = OpFAdd %6 %41 %10 ; Changed
OpBranch %22
%24 = OpLabel
OpReturn
OpFunctionEnd
)";
CheckEqual(env, after_op_0, context.get());
}
TEST(StructuredLoopToSelectionReductionPassTest,
LoopWithCombinedHeaderAndContinue) {
// A shader containing a loop where the header is also the continue target.
// For now, we don't simplify such loops.
std::string shader = 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 = OpTypeBool
%30 = OpConstantFalse %6
%4 = OpFunction %2 None %3
%5 = OpLabel
OpBranch %10
%10 = OpLabel ; loop header and continue target
OpLoopMerge %12 %10 None
OpBranchConditional %30 %10 %12
%12 = OpLabel
OpReturn
OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
const auto ops = StructuredLoopToSelectionReductionOpportunityFinder()
.GetAvailableOpportunities(context.get(), 0);
ASSERT_EQ(0, ops.size());
}
} // namespace
} // namespace reduce
} // namespace spvtools