| // Copyright (c) 2019 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/conditional_branch_to_simple_conditional_branch_opportunity_finder.h" |
| |
| #include "source/opt/build_module.h" |
| #include "source/reduce/reduction_opportunity.h" |
| #include "source/reduce/reduction_pass.h" |
| #include "test/reduce/reduce_test_util.h" |
| |
| namespace spvtools { |
| namespace reduce { |
| namespace { |
| |
| const spv_target_env kEnv = SPV_ENV_UNIVERSAL_1_3; |
| |
| TEST(ConditionalBranchToSimpleConditionalBranchTest, Diamond) { |
| // A test with the following structure. |
| // |
| // selection header |
| // OpBranchConditional |
| // | | |
| // b b |
| // | | |
| // selection merge |
| // |
| // There should be two opportunities for redirecting the OpBranchConditional |
| // targets: redirecting the true to false, and vice-versa. E.g. false to true: |
| // |
| // selection header |
| // OpBranchConditional |
| // || |
| // b b |
| // | | |
| // selection merge |
| |
| std::string shader = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpSelectionMerge %11 None |
| OpBranchConditional %8 %12 %13 |
| %12 = OpLabel |
| OpBranch %11 |
| %13 = OpLabel |
| OpBranch %11 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| |
| )"; |
| |
| auto context = BuildModule(kEnv, nullptr, shader, kReduceAssembleOption); |
| |
| CheckValid(kEnv, context.get()); |
| |
| auto ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| |
| ASSERT_EQ(2, ops.size()); |
| |
| ASSERT_TRUE(ops[0]->PreconditionHolds()); |
| ASSERT_TRUE(ops[1]->PreconditionHolds()); |
| ops[0]->TryToApply(); |
| // The other opportunity should now be disabled. |
| ASSERT_FALSE(ops[1]->PreconditionHolds()); |
| |
| CheckValid(kEnv, context.get()); |
| |
| { |
| std::string after = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpSelectionMerge %11 None |
| OpBranchConditional %8 %12 %12 |
| %12 = OpLabel |
| OpBranch %11 |
| %13 = OpLabel |
| OpBranch %11 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| )"; |
| CheckEqual(kEnv, after, context.get()); |
| } |
| |
| ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| ASSERT_EQ(0, ops.size()); |
| |
| // Start again, and apply the other op. |
| context = BuildModule(kEnv, nullptr, shader, kReduceAssembleOption); |
| |
| CheckValid(kEnv, context.get()); |
| |
| ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| ASSERT_EQ(2, ops.size()); |
| |
| ASSERT_TRUE(ops[0]->PreconditionHolds()); |
| ASSERT_TRUE(ops[1]->PreconditionHolds()); |
| ops[1]->TryToApply(); |
| // The other opportunity should now be disabled. |
| ASSERT_FALSE(ops[0]->PreconditionHolds()); |
| |
| CheckValid(kEnv, context.get()); |
| |
| { |
| std::string after2 = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpSelectionMerge %11 None |
| OpBranchConditional %8 %13 %13 |
| %12 = OpLabel |
| OpBranch %11 |
| %13 = OpLabel |
| OpBranch %11 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| )"; |
| CheckEqual(kEnv, after2, context.get()); |
| } |
| } |
| |
| TEST(ConditionalBranchToSimpleConditionalBranchTest, AlreadySimplified) { |
| // A test with the following structure. |
| // |
| // selection header |
| // OpBranchConditional |
| // || |
| // b b |
| // | | |
| // selection merge |
| // |
| // There should be no opportunities for redirecting the OpBranchConditional |
| // as it is already simplified. |
| // |
| |
| std::string shader = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpSelectionMerge %11 None |
| OpBranchConditional %8 %12 %12 |
| %12 = OpLabel |
| OpBranch %11 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| |
| )"; |
| |
| auto context = BuildModule(kEnv, nullptr, shader, kReduceAssembleOption); |
| |
| CheckValid(kEnv, context.get()); |
| |
| auto ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| |
| ASSERT_EQ(0, ops.size()); |
| } |
| |
| TEST(ConditionalBranchToSimpleConditionalBranchTest, DontRemoveBackEdge) { |
| // A test with the following structure. The loop has a continue construct that |
| // ends with OpBranchConditional. The OpBranchConditional can be simplified, |
| // but only to point to the loop header, otherwise we have removed the |
| // back-edge. Thus, there should be one opportunity instead of two. |
| // |
| // loop header |
| // | |
| // loop continue target and back-edge block |
| // OpBranchConditional |
| // | | |
| // loop merge (to loop header^) |
| |
| std::string shader = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpLoopMerge %11 %12 None |
| OpBranch %12 |
| %12 = OpLabel |
| OpBranchConditional %8 %11 %10 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| )"; |
| |
| const auto context = |
| BuildModule(kEnv, nullptr, shader, kReduceAssembleOption); |
| |
| CheckValid(kEnv, context.get()); |
| |
| auto ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| |
| ASSERT_EQ(1, ops.size()); |
| |
| ASSERT_TRUE(ops[0]->PreconditionHolds()); |
| ops[0]->TryToApply(); |
| CheckValid(kEnv, context.get()); |
| |
| std::string after = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpLoopMerge %11 %12 None |
| OpBranch %12 |
| %12 = OpLabel |
| OpBranchConditional %8 %10 %10 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| )"; |
| CheckEqual(kEnv, after, context.get()); |
| |
| ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| ASSERT_EQ(0, ops.size()); |
| } |
| |
| TEST(ConditionalBranchToSimpleConditionalBranchTest, |
| DontRemoveBackEdgeCombinedHeaderContinue) { |
| // A test with the following structure. |
| // |
| // loop header and continue target and back-edge block |
| // OpBranchConditional |
| // | | |
| // loop merge (to loop header^) |
| // |
| // The OpBranchConditional-to-header edge must not be removed, so there should |
| // only be one opportunity. It should change both targets to be to the loop |
| // header. |
| |
| std::string shader = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpLoopMerge %11 %10 None |
| OpBranchConditional %8 %11 %10 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| )"; |
| |
| const auto context = |
| BuildModule(kEnv, nullptr, shader, kReduceAssembleOption); |
| |
| CheckValid(kEnv, context.get()); |
| |
| auto ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| |
| ASSERT_EQ(1, ops.size()); |
| |
| ASSERT_TRUE(ops[0]->PreconditionHolds()); |
| ops[0]->TryToApply(); |
| CheckValid(kEnv, context.get()); |
| |
| std::string after = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpLoopMerge %11 %10 None |
| OpBranchConditional %8 %10 %10 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| )"; |
| CheckEqual(kEnv, after, context.get()); |
| |
| ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| ASSERT_EQ(0, ops.size()); |
| } |
| |
| TEST(ConditionalBranchToSimpleConditionalBranchTest, BackEdgeUnreachable) { |
| // A test with the following structure. I.e. a loop with an unreachable |
| // continue construct that ends with OpBranchConditional. |
| // |
| // loop header |
| // | |
| // | loop continue target (unreachable) |
| // | | |
| // | back-edge block (unreachable) |
| // | OpBranchConditional |
| // | | | |
| // loop merge (to loop header^) |
| // |
| // The branch to the loop header must not be removed, even though the continue |
| // construct is unreachable. So there should only be one opportunity to make |
| // the true and false targets of the OpBranchConditional to point to the loop |
| // header. |
| |
| std::string shader = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpLoopMerge %11 %12 None |
| OpBranch %11 |
| %12 = OpLabel |
| OpBranch %13 |
| %13 = OpLabel |
| OpBranchConditional %8 %11 %10 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| )"; |
| |
| const auto context = |
| BuildModule(kEnv, nullptr, shader, kReduceAssembleOption); |
| |
| CheckValid(kEnv, context.get()); |
| |
| auto ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| |
| ASSERT_EQ(1, ops.size()); |
| |
| ASSERT_TRUE(ops[0]->PreconditionHolds()); |
| ops[0]->TryToApply(); |
| CheckValid(kEnv, context.get()); |
| |
| std::string after = R"( |
| OpCapability Shader |
| %1 = OpExtInstImport "GLSL.std.450" |
| OpMemoryModel Logical GLSL450 |
| OpEntryPoint Fragment %2 "main" |
| OpExecutionMode %2 OriginUpperLeft |
| OpSource ESSL 310 |
| OpName %2 "main" |
| %3 = OpTypeVoid |
| %4 = OpTypeFunction %3 |
| %5 = OpTypeInt 32 1 |
| %6 = OpTypePointer Function %5 |
| %7 = OpTypeBool |
| %8 = OpConstantTrue %7 |
| %2 = OpFunction %3 None %4 |
| %9 = OpLabel |
| OpBranch %10 |
| %10 = OpLabel |
| OpLoopMerge %11 %12 None |
| OpBranch %11 |
| %12 = OpLabel |
| OpBranch %13 |
| %13 = OpLabel |
| OpBranchConditional %8 %10 %10 |
| %11 = OpLabel |
| OpReturn |
| OpFunctionEnd |
| )"; |
| CheckEqual(kEnv, after, context.get()); |
| |
| ops = ConditionalBranchToSimpleConditionalBranchOpportunityFinder() |
| .GetAvailableOpportunities(context.get()); |
| ASSERT_EQ(0, ops.size()); |
| } |
| |
| } // namespace |
| } // namespace reduce |
| } // namespace spvtools |
