123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467 |
- // 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 <string>
- #include "gmock/gmock.h"
- #include "source/opt/struct_cfg_analysis.h"
- #include "test/opt/assembly_builder.h"
- #include "test/opt/pass_fixture.h"
- #include "test/opt/pass_utils.h"
- namespace spvtools {
- namespace opt {
- namespace {
- using StructCFGAnalysisTest = PassTest<::testing::Test>;
- TEST_F(StructCFGAnalysisTest, BBInSelection) {
- const std::string text = R"(
- OpCapability Shader
- OpMemoryModel Logical GLSL450
- OpEntryPoint Fragment %main "main"
- %void = OpTypeVoid
- %bool = OpTypeBool
- %bool_undef = OpUndef %bool
- %uint = OpTypeInt 32 0
- %uint_undef = OpUndef %uint
- %void_func = OpTypeFunction %void
- %main = OpFunction %void None %void_func
- %1 = OpLabel
- OpSelectionMerge %3 None
- OpBranchConditional %undef_bool %2 %3
- %2 = OpLabel
- OpBranch %3
- %3 = OpLabel
- OpReturn
- OpFunctionEnd
- )";
- std::unique_ptr<IRContext> context =
- BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
- SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
- StructuredCFGAnalysis analysis(context.get());
- // The header is not in the construct.
- EXPECT_EQ(analysis.ContainingConstruct(1), 0);
- EXPECT_EQ(analysis.ContainingLoop(1), 0);
- EXPECT_EQ(analysis.MergeBlock(1), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
- // BB2 is in the construct.
- EXPECT_EQ(analysis.ContainingConstruct(2), 1);
- EXPECT_EQ(analysis.ContainingLoop(2), 0);
- EXPECT_EQ(analysis.MergeBlock(2), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
- // The merge node is not in the construct.
- EXPECT_EQ(analysis.ContainingConstruct(3), 0);
- EXPECT_EQ(analysis.ContainingLoop(3), 0);
- EXPECT_EQ(analysis.MergeBlock(3), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
- }
- TEST_F(StructCFGAnalysisTest, BBInLoop) {
- const std::string text = R"(
- OpCapability Shader
- OpMemoryModel Logical GLSL450
- OpEntryPoint Fragment %main "main"
- %void = OpTypeVoid
- %bool = OpTypeBool
- %bool_undef = OpUndef %bool
- %uint = OpTypeInt 32 0
- %uint_undef = OpUndef %uint
- %void_func = OpTypeFunction %void
- %main = OpFunction %void None %void_func
- %entry_lab = OpLabel
- OpBranch %1
- %1 = OpLabel
- OpLoopMerge %3 %4 None
- OpBranchConditional %undef_bool %2 %3
- %2 = OpLabel
- OpBranch %3
- %4 = OpLabel
- OpBranch %1
- %3 = OpLabel
- OpReturn
- OpFunctionEnd
- )";
- std::unique_ptr<IRContext> context =
- BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
- SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
- StructuredCFGAnalysis analysis(context.get());
- // The header is not in the construct.
- EXPECT_EQ(analysis.ContainingConstruct(1), 0);
- EXPECT_EQ(analysis.ContainingLoop(1), 0);
- EXPECT_EQ(analysis.MergeBlock(1), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
- // BB2 is in the construct.
- EXPECT_EQ(analysis.ContainingConstruct(2), 1);
- EXPECT_EQ(analysis.ContainingLoop(2), 1);
- EXPECT_EQ(analysis.MergeBlock(2), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
- // The merge node is not in the construct.
- EXPECT_EQ(analysis.ContainingConstruct(3), 0);
- EXPECT_EQ(analysis.ContainingLoop(3), 0);
- EXPECT_EQ(analysis.MergeBlock(3), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
- // The continue block is in the construct.
- EXPECT_EQ(analysis.ContainingConstruct(4), 1);
- EXPECT_EQ(analysis.ContainingLoop(4), 1);
- EXPECT_EQ(analysis.MergeBlock(4), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
- }
- TEST_F(StructCFGAnalysisTest, SelectionInLoop) {
- const std::string text = R"(
- OpCapability Shader
- OpMemoryModel Logical GLSL450
- OpEntryPoint Fragment %main "main"
- %void = OpTypeVoid
- %bool = OpTypeBool
- %bool_undef = OpUndef %bool
- %uint = OpTypeInt 32 0
- %uint_undef = OpUndef %uint
- %void_func = OpTypeFunction %void
- %main = OpFunction %void None %void_func
- %entry_lab = OpLabel
- OpBranch %1
- %1 = OpLabel
- OpLoopMerge %3 %4 None
- OpBranchConditional %undef_bool %2 %3
- %2 = OpLabel
- OpSelectionMerge %6 None
- OpBranchConditional %undef_bool %5 %6
- %5 = OpLabel
- OpBranch %6
- %6 = OpLabel
- OpBranch %3
- %4 = OpLabel
- OpBranch %1
- %3 = OpLabel
- OpReturn
- OpFunctionEnd
- )";
- std::unique_ptr<IRContext> context =
- BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
- SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
- StructuredCFGAnalysis analysis(context.get());
- // The loop header is not in either construct.
- EXPECT_EQ(analysis.ContainingConstruct(1), 0);
- EXPECT_EQ(analysis.ContainingLoop(1), 0);
- EXPECT_EQ(analysis.MergeBlock(1), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
- // Selection header is in the loop only.
- EXPECT_EQ(analysis.ContainingConstruct(2), 1);
- EXPECT_EQ(analysis.ContainingLoop(2), 1);
- EXPECT_EQ(analysis.MergeBlock(2), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
- // The loop merge node is not in either construct.
- EXPECT_EQ(analysis.ContainingConstruct(3), 0);
- EXPECT_EQ(analysis.ContainingLoop(3), 0);
- EXPECT_EQ(analysis.MergeBlock(3), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
- // The continue block is in the loop only.
- EXPECT_EQ(analysis.ContainingConstruct(4), 1);
- EXPECT_EQ(analysis.ContainingLoop(4), 1);
- EXPECT_EQ(analysis.MergeBlock(4), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
- // BB5 is in the selection fist and the loop.
- EXPECT_EQ(analysis.ContainingConstruct(5), 2);
- EXPECT_EQ(analysis.ContainingLoop(5), 1);
- EXPECT_EQ(analysis.MergeBlock(5), 6);
- EXPECT_EQ(analysis.LoopMergeBlock(5), 3);
- // The selection merge is in the loop only.
- EXPECT_EQ(analysis.ContainingConstruct(6), 1);
- EXPECT_EQ(analysis.ContainingLoop(6), 1);
- EXPECT_EQ(analysis.MergeBlock(6), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(6), 3);
- }
- TEST_F(StructCFGAnalysisTest, LoopInSelection) {
- const std::string text = R"(
- OpCapability Shader
- OpMemoryModel Logical GLSL450
- OpEntryPoint Fragment %main "main"
- %void = OpTypeVoid
- %bool = OpTypeBool
- %bool_undef = OpUndef %bool
- %uint = OpTypeInt 32 0
- %uint_undef = OpUndef %uint
- %void_func = OpTypeFunction %void
- %main = OpFunction %void None %void_func
- %entry_lab = OpLabel
- OpBranch %1
- %1 = OpLabel
- OpSelectionMerge %3 None
- OpBranchConditional %undef_bool %2 %3
- %2 = OpLabel
- OpLoopMerge %4 %5 None
- OpBranchConditional %undef_bool %4 %6
- %5 = OpLabel
- OpBranch %2
- %6 = OpLabel
- OpBranch %4
- %4 = OpLabel
- OpBranch %3
- %3 = OpLabel
- OpReturn
- OpFunctionEnd
- )";
- std::unique_ptr<IRContext> context =
- BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
- SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
- StructuredCFGAnalysis analysis(context.get());
- // The selection header is not in either construct.
- EXPECT_EQ(analysis.ContainingConstruct(1), 0);
- EXPECT_EQ(analysis.ContainingLoop(1), 0);
- EXPECT_EQ(analysis.MergeBlock(1), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
- // Loop header is in the selection only.
- EXPECT_EQ(analysis.ContainingConstruct(2), 1);
- EXPECT_EQ(analysis.ContainingLoop(2), 0);
- EXPECT_EQ(analysis.MergeBlock(2), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
- // The selection merge node is not in either construct.
- EXPECT_EQ(analysis.ContainingConstruct(3), 0);
- EXPECT_EQ(analysis.ContainingLoop(3), 0);
- EXPECT_EQ(analysis.MergeBlock(3), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
- // The loop merge is in the selection only.
- EXPECT_EQ(analysis.ContainingConstruct(4), 1);
- EXPECT_EQ(analysis.ContainingLoop(4), 0);
- EXPECT_EQ(analysis.MergeBlock(4), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(4), 0);
- // The loop continue target is in the loop.
- EXPECT_EQ(analysis.ContainingConstruct(5), 2);
- EXPECT_EQ(analysis.ContainingLoop(5), 2);
- EXPECT_EQ(analysis.MergeBlock(5), 4);
- EXPECT_EQ(analysis.LoopMergeBlock(5), 4);
- // BB6 is in the loop.
- EXPECT_EQ(analysis.ContainingConstruct(6), 2);
- EXPECT_EQ(analysis.ContainingLoop(6), 2);
- EXPECT_EQ(analysis.MergeBlock(6), 4);
- EXPECT_EQ(analysis.LoopMergeBlock(6), 4);
- }
- TEST_F(StructCFGAnalysisTest, SelectionInSelection) {
- const std::string text = R"(
- OpCapability Shader
- OpMemoryModel Logical GLSL450
- OpEntryPoint Fragment %main "main"
- %void = OpTypeVoid
- %bool = OpTypeBool
- %bool_undef = OpUndef %bool
- %uint = OpTypeInt 32 0
- %uint_undef = OpUndef %uint
- %void_func = OpTypeFunction %void
- %main = OpFunction %void None %void_func
- %entry_lab = OpLabel
- OpBranch %1
- %1 = OpLabel
- OpSelectionMerge %3 None
- OpBranchConditional %undef_bool %2 %3
- %2 = OpLabel
- OpSelectionMerge %4 None
- OpBranchConditional %undef_bool %4 %5
- %5 = OpLabel
- OpBranch %4
- %4 = OpLabel
- OpBranch %3
- %3 = OpLabel
- OpReturn
- OpFunctionEnd
- )";
- std::unique_ptr<IRContext> context =
- BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
- SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
- StructuredCFGAnalysis analysis(context.get());
- // The outer selection header is not in either construct.
- EXPECT_EQ(analysis.ContainingConstruct(1), 0);
- EXPECT_EQ(analysis.ContainingLoop(1), 0);
- EXPECT_EQ(analysis.MergeBlock(1), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
- // The inner header is in the outer selection.
- EXPECT_EQ(analysis.ContainingConstruct(2), 1);
- EXPECT_EQ(analysis.ContainingLoop(2), 0);
- EXPECT_EQ(analysis.MergeBlock(2), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
- // The outer merge node is not in either construct.
- EXPECT_EQ(analysis.ContainingConstruct(3), 0);
- EXPECT_EQ(analysis.ContainingLoop(3), 0);
- EXPECT_EQ(analysis.MergeBlock(3), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
- // The inner merge is in the outer selection.
- EXPECT_EQ(analysis.ContainingConstruct(4), 1);
- EXPECT_EQ(analysis.ContainingLoop(4), 0);
- EXPECT_EQ(analysis.MergeBlock(4), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(4), 0);
- // BB5 is in the inner selection.
- EXPECT_EQ(analysis.ContainingConstruct(5), 2);
- EXPECT_EQ(analysis.ContainingLoop(5), 0);
- EXPECT_EQ(analysis.MergeBlock(5), 4);
- EXPECT_EQ(analysis.LoopMergeBlock(5), 0);
- }
- TEST_F(StructCFGAnalysisTest, LoopInLoop) {
- const std::string text = R"(
- OpCapability Shader
- OpMemoryModel Logical GLSL450
- OpEntryPoint Fragment %main "main"
- %void = OpTypeVoid
- %bool = OpTypeBool
- %bool_undef = OpUndef %bool
- %uint = OpTypeInt 32 0
- %uint_undef = OpUndef %uint
- %void_func = OpTypeFunction %void
- %main = OpFunction %void None %void_func
- %entry_lab = OpLabel
- OpBranch %1
- %1 = OpLabel
- OpLoopMerge %3 %7 None
- OpBranchConditional %undef_bool %2 %3
- %2 = OpLabel
- OpLoopMerge %4 %5 None
- OpBranchConditional %undef_bool %4 %6
- %5 = OpLabel
- OpBranch %2
- %6 = OpLabel
- OpBranch %4
- %4 = OpLabel
- OpBranch %3
- %7 = OpLabel
- OpBranch %1
- %3 = OpLabel
- OpReturn
- OpFunctionEnd
- )";
- std::unique_ptr<IRContext> context =
- BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
- SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
- StructuredCFGAnalysis analysis(context.get());
- // The outer loop header is not in either construct.
- EXPECT_EQ(analysis.ContainingConstruct(1), 0);
- EXPECT_EQ(analysis.ContainingLoop(1), 0);
- EXPECT_EQ(analysis.MergeBlock(1), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
- // The inner loop header is in the outer loop.
- EXPECT_EQ(analysis.ContainingConstruct(2), 1);
- EXPECT_EQ(analysis.ContainingLoop(2), 1);
- EXPECT_EQ(analysis.MergeBlock(2), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
- // The outer merge node is not in either construct.
- EXPECT_EQ(analysis.ContainingConstruct(3), 0);
- EXPECT_EQ(analysis.ContainingLoop(3), 0);
- EXPECT_EQ(analysis.MergeBlock(3), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
- // The inner merge is in the outer loop.
- EXPECT_EQ(analysis.ContainingConstruct(4), 1);
- EXPECT_EQ(analysis.ContainingLoop(4), 1);
- EXPECT_EQ(analysis.MergeBlock(4), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
- // The inner continue target is in the inner loop.
- EXPECT_EQ(analysis.ContainingConstruct(5), 2);
- EXPECT_EQ(analysis.ContainingLoop(5), 2);
- EXPECT_EQ(analysis.MergeBlock(5), 4);
- EXPECT_EQ(analysis.LoopMergeBlock(5), 4);
- // BB6 is in the loop.
- EXPECT_EQ(analysis.ContainingConstruct(6), 2);
- EXPECT_EQ(analysis.ContainingLoop(6), 2);
- EXPECT_EQ(analysis.MergeBlock(6), 4);
- EXPECT_EQ(analysis.LoopMergeBlock(6), 4);
- // The outer continue target is in the outer loop.
- EXPECT_EQ(analysis.ContainingConstruct(7), 1);
- EXPECT_EQ(analysis.ContainingLoop(7), 1);
- EXPECT_EQ(analysis.MergeBlock(7), 3);
- EXPECT_EQ(analysis.LoopMergeBlock(7), 3);
- }
- TEST_F(StructCFGAnalysisTest, KernelTest) {
- const std::string text = R"(
- OpCapability Kernel
- OpMemoryModel Logical GLSL450
- OpEntryPoint Fragment %main "main"
- %void = OpTypeVoid
- %bool = OpTypeBool
- %bool_undef = OpUndef %bool
- %void_func = OpTypeFunction %void
- %main = OpFunction %void None %void_func
- %1 = OpLabel
- OpBranchConditional %undef_bool %2 %3
- %2 = OpLabel
- OpBranch %3
- %3 = OpLabel
- OpReturn
- OpFunctionEnd
- )";
- std::unique_ptr<IRContext> context =
- BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
- SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
- StructuredCFGAnalysis analysis(context.get());
- // No structured control flow, so none of the basic block are in any
- // construct.
- for (uint32_t i = 1; i <= 3; i++) {
- EXPECT_EQ(analysis.ContainingConstruct(i), 0);
- EXPECT_EQ(analysis.ContainingLoop(i), 0);
- EXPECT_EQ(analysis.MergeBlock(i), 0);
- EXPECT_EQ(analysis.LoopMergeBlock(i), 0);
- }
- }
- } // namespace
- } // namespace opt
- } // namespace spvtools
|