| // Copyright 2020 The Tint Authors. |
| // |
| // 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 "gmock/gmock.h" |
| #include "src/reader/spirv/function.h" |
| #include "src/reader/spirv/parser_impl_test_helper.h" |
| #include "src/reader/spirv/spirv_tools_helpers_test.h" |
| |
| namespace tint { |
| namespace reader { |
| namespace spirv { |
| namespace { |
| |
| using ::testing::Eq; |
| using ::testing::HasSubstr; |
| |
| // Make a local name so it's easier to triage errors. |
| using SpvParserCFGTest = SpvParserTest; |
| |
| std::string Dump(const std::vector<uint32_t>& v) { |
| std::ostringstream o; |
| o << "{"; |
| for (auto a : v) { |
| o << a << " "; |
| } |
| o << "}"; |
| return o.str(); |
| } |
| |
| using ::testing::ElementsAre; |
| using ::testing::Eq; |
| using ::testing::UnorderedElementsAre; |
| |
| std::string CommonTypes() { |
| return R"( |
| OpCapability Shader |
| OpMemoryModel Logical Simple |
| OpEntryPoint Fragment %100 "main" |
| OpExecutionMode %100 OriginUpperLeft |
| |
| OpName %var "var" |
| |
| %void = OpTypeVoid |
| %voidfn = OpTypeFunction %void |
| |
| %bool = OpTypeBool |
| %cond = OpConstantNull %bool |
| %cond2 = OpConstantTrue %bool |
| %cond3 = OpConstantFalse %bool |
| |
| %uint = OpTypeInt 32 0 |
| %int = OpTypeInt 32 1 |
| %selector = OpConstant %uint 42 |
| %signed_selector = OpConstant %int 42 |
| |
| %uintfn = OpTypeFunction %uint |
| |
| %uint_0 = OpConstant %uint 0 |
| %uint_1 = OpConstant %uint 1 |
| %uint_2 = OpConstant %uint 2 |
| %uint_3 = OpConstant %uint 3 |
| %uint_4 = OpConstant %uint 4 |
| %uint_5 = OpConstant %uint 5 |
| %uint_6 = OpConstant %uint 6 |
| %uint_7 = OpConstant %uint 7 |
| %uint_8 = OpConstant %uint 8 |
| %uint_10 = OpConstant %uint 10 |
| %uint_20 = OpConstant %uint 20 |
| %uint_30 = OpConstant %uint 30 |
| %uint_40 = OpConstant %uint 40 |
| %uint_50 = OpConstant %uint 50 |
| %uint_90 = OpConstant %uint 90 |
| %uint_99 = OpConstant %uint 99 |
| |
| %ptr_Private_uint = OpTypePointer Private %uint |
| %var = OpVariable %ptr_Private_uint Private |
| |
| %999 = OpConstant %uint 999 |
| )"; |
| } |
| |
| /// Runs the necessary flow until and including labeling control |
| /// flow constructs. |
| /// @returns the result of labeling control flow constructs. |
| bool FlowLabelControlFlowConstructs(FunctionEmitter* fe) { |
| fe->RegisterBasicBlocks(); |
| EXPECT_TRUE(fe->RegisterMerges()) << fe->parser()->error(); |
| fe->ComputeBlockOrderAndPositions(); |
| EXPECT_TRUE(fe->VerifyHeaderContinueMergeOrder()) << fe->parser()->error(); |
| return fe->LabelControlFlowConstructs(); |
| } |
| |
| /// Runs the necessary flow until and including finding switch case |
| /// headers. |
| /// @returns the result of finding switch case headers. |
| bool FlowFindSwitchCaseHeaders(FunctionEmitter* fe) { |
| EXPECT_TRUE(FlowLabelControlFlowConstructs(fe)) << fe->parser()->error(); |
| return fe->FindSwitchCaseHeaders(); |
| } |
| |
| /// Runs the necessary flow until and including classify CFG edges, |
| /// @returns the result of classify CFG edges. |
| bool FlowClassifyCFGEdges(FunctionEmitter* fe) { |
| EXPECT_TRUE(FlowFindSwitchCaseHeaders(fe)) << fe->parser()->error(); |
| return fe->ClassifyCFGEdges(); |
| } |
| |
| /// Runs the necessary flow until and including finding if-selection |
| /// internal headers. |
| /// @returns the result of classify CFG edges. |
| bool FlowFindIfSelectionInternalHeaders(FunctionEmitter* fe) { |
| EXPECT_TRUE(FlowClassifyCFGEdges(fe)) << fe->parser()->error(); |
| return fe->FindIfSelectionInternalHeaders(); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_SingleBlock) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %42 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.TerminatorsAreValid()); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_Sequence) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %20 = OpLabel |
| OpBranch %30 |
| |
| %30 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.TerminatorsAreValid()) << p->error(); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_If) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %20 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranchConditional %cond %30 %40 |
| |
| %30 = OpLabel |
| OpBranch %99 |
| |
| %40 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.TerminatorsAreValid()) << p->error(); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_Switch) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %80 20 %20 30 %30 |
| |
| %20 = OpLabel |
| OpBranch %30 ; fall through |
| |
| %30 = OpLabel |
| OpBranch %99 |
| |
| %80 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.TerminatorsAreValid()); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_Loop_SingleBlock) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %20 None |
| OpBranchConditional %cond %20 %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.TerminatorsAreValid()); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_Loop_Simple) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %40 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %40 |
| |
| %40 = OpLabel |
| OpBranch %20 ; back edge |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.TerminatorsAreValid()); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_Kill) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpKill |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.TerminatorsAreValid()); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_Unreachable) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpUnreachable |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.TerminatorsAreValid()); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_MissingTerminator) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| |
| OpFunctionEnd |
| )")); |
| // The SPIRV-Tools internal representation rejects this case earlier. |
| EXPECT_FALSE(p->BuildAndParseInternalModuleExceptFunctions()); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_DisallowLoopToEntryBlock) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpBranch %10 ; not allowed |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.TerminatorsAreValid()); |
| EXPECT_THAT(p->error(), Eq("Block 20 branches to function entry block 10")); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_DisallowNonBlock) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %999 ; definitely wrong |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.TerminatorsAreValid()); |
| EXPECT_THAT(p->error(), |
| Eq("Block 10 in function 100 branches to 999 which is " |
| "not a block in the function")); |
| } |
| |
| TEST_F(SpvParserCFGTest, TerminatorsAreValid_DisallowBlockInDifferentFunction) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %210 |
| |
| OpFunctionEnd |
| |
| |
| %200 = OpFunction %void None %voidfn |
| |
| %210 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.TerminatorsAreValid()); |
| EXPECT_THAT(p->error(), Eq("Block 10 in function 100 branches to 210 which " |
| "is not a block in the function")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_NoMerges) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.RegisterMerges()); |
| |
| const auto* bi = fe.GetBlockInfo(10); |
| ASSERT_NE(bi, nullptr); |
| EXPECT_EQ(bi->merge_for_header, 0u); |
| EXPECT_EQ(bi->continue_for_header, 0u); |
| EXPECT_EQ(bi->header_for_merge, 0u); |
| EXPECT_EQ(bi->header_for_continue, 0u); |
| EXPECT_FALSE(bi->is_continue_entire_loop); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_GoodSelectionMerge_BranchConditional) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranchConditional %cond %20 %99 |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.RegisterMerges()); |
| |
| // Header points to the merge |
| const auto* bi10 = fe.GetBlockInfo(10); |
| ASSERT_NE(bi10, nullptr); |
| EXPECT_EQ(bi10->merge_for_header, 99u); |
| EXPECT_EQ(bi10->continue_for_header, 0u); |
| EXPECT_EQ(bi10->header_for_merge, 0u); |
| EXPECT_EQ(bi10->header_for_continue, 0u); |
| EXPECT_FALSE(bi10->is_continue_entire_loop); |
| |
| // Middle block is neither header nor merge |
| const auto* bi20 = fe.GetBlockInfo(20); |
| ASSERT_NE(bi20, nullptr); |
| EXPECT_EQ(bi20->merge_for_header, 0u); |
| EXPECT_EQ(bi20->continue_for_header, 0u); |
| EXPECT_EQ(bi20->header_for_merge, 0u); |
| EXPECT_EQ(bi20->header_for_continue, 0u); |
| EXPECT_FALSE(bi20->is_continue_entire_loop); |
| |
| // Merge block points to the header |
| const auto* bi99 = fe.GetBlockInfo(99); |
| ASSERT_NE(bi99, nullptr); |
| EXPECT_EQ(bi99->merge_for_header, 0u); |
| EXPECT_EQ(bi99->continue_for_header, 0u); |
| EXPECT_EQ(bi99->header_for_merge, 10u); |
| EXPECT_EQ(bi99->header_for_continue, 0u); |
| EXPECT_FALSE(bi99->is_continue_entire_loop); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_GoodSelectionMerge_Switch) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %99 20 %20 |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.RegisterMerges()); |
| |
| // Header points to the merge |
| const auto* bi10 = fe.GetBlockInfo(10); |
| ASSERT_NE(bi10, nullptr); |
| EXPECT_EQ(bi10->merge_for_header, 99u); |
| EXPECT_EQ(bi10->continue_for_header, 0u); |
| EXPECT_EQ(bi10->header_for_merge, 0u); |
| EXPECT_EQ(bi10->header_for_continue, 0u); |
| EXPECT_FALSE(bi10->is_continue_entire_loop); |
| |
| // Middle block is neither header nor merge |
| const auto* bi20 = fe.GetBlockInfo(20); |
| ASSERT_NE(bi20, nullptr); |
| EXPECT_EQ(bi20->merge_for_header, 0u); |
| EXPECT_EQ(bi20->continue_for_header, 0u); |
| EXPECT_EQ(bi20->header_for_merge, 0u); |
| EXPECT_EQ(bi20->header_for_continue, 0u); |
| EXPECT_FALSE(bi20->is_continue_entire_loop); |
| |
| // Merge block points to the header |
| const auto* bi99 = fe.GetBlockInfo(99); |
| ASSERT_NE(bi99, nullptr); |
| EXPECT_EQ(bi99->merge_for_header, 0u); |
| EXPECT_EQ(bi99->continue_for_header, 0u); |
| EXPECT_EQ(bi99->header_for_merge, 10u); |
| EXPECT_EQ(bi99->header_for_continue, 0u); |
| EXPECT_FALSE(bi99->is_continue_entire_loop); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_GoodLoopMerge_SingleBlockLoop) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %20 None |
| OpBranchConditional %cond %20 %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.RegisterMerges()); |
| |
| // Entry block is not special |
| const auto* bi10 = fe.GetBlockInfo(10); |
| ASSERT_NE(bi10, nullptr); |
| EXPECT_EQ(bi10->merge_for_header, 0u); |
| EXPECT_EQ(bi10->continue_for_header, 0u); |
| EXPECT_EQ(bi10->header_for_merge, 0u); |
| EXPECT_EQ(bi10->header_for_continue, 0u); |
| EXPECT_FALSE(bi10->is_continue_entire_loop); |
| |
| // Single block loop is its own continue, and marked as single block loop. |
| const auto* bi20 = fe.GetBlockInfo(20); |
| ASSERT_NE(bi20, nullptr); |
| EXPECT_EQ(bi20->merge_for_header, 99u); |
| EXPECT_EQ(bi20->continue_for_header, 20u); |
| EXPECT_EQ(bi20->header_for_merge, 0u); |
| EXPECT_EQ(bi20->header_for_continue, 20u); |
| EXPECT_TRUE(bi20->is_continue_entire_loop); |
| |
| // Merge block points to the header |
| const auto* bi99 = fe.GetBlockInfo(99); |
| ASSERT_NE(bi99, nullptr); |
| EXPECT_EQ(bi99->merge_for_header, 0u); |
| EXPECT_EQ(bi99->continue_for_header, 0u); |
| EXPECT_EQ(bi99->header_for_merge, 20u); |
| EXPECT_EQ(bi99->header_for_continue, 0u); |
| EXPECT_FALSE(bi99->is_continue_entire_loop); |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| RegisterMerges_GoodLoopMerge_MultiBlockLoop_ContinueIsHeader) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %20 None |
| OpBranch %40 |
| |
| %40 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.RegisterMerges()); |
| |
| // Loop header points to continue (itself) and merge |
| const auto* bi20 = fe.GetBlockInfo(20); |
| ASSERT_NE(bi20, nullptr); |
| EXPECT_EQ(bi20->merge_for_header, 99u); |
| EXPECT_EQ(bi20->continue_for_header, 20u); |
| EXPECT_EQ(bi20->header_for_merge, 0u); |
| EXPECT_EQ(bi20->header_for_continue, 20u); |
| EXPECT_TRUE(bi20->is_continue_entire_loop); |
| |
| // Backedge block, but is not a declared header, merge, or continue |
| const auto* bi40 = fe.GetBlockInfo(40); |
| ASSERT_NE(bi40, nullptr); |
| EXPECT_EQ(bi40->merge_for_header, 0u); |
| EXPECT_EQ(bi40->continue_for_header, 0u); |
| EXPECT_EQ(bi40->header_for_merge, 0u); |
| EXPECT_EQ(bi40->header_for_continue, 0u); |
| EXPECT_FALSE(bi40->is_continue_entire_loop); |
| |
| // Merge block points to the header |
| const auto* bi99 = fe.GetBlockInfo(99); |
| ASSERT_NE(bi99, nullptr); |
| EXPECT_EQ(bi99->merge_for_header, 0u); |
| EXPECT_EQ(bi99->continue_for_header, 0u); |
| EXPECT_EQ(bi99->header_for_merge, 20u); |
| EXPECT_EQ(bi99->header_for_continue, 0u); |
| EXPECT_FALSE(bi99->is_continue_entire_loop); |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| RegisterMerges_GoodLoopMerge_MultiBlockLoop_ContinueIsNotHeader_Branch) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %40 None |
| OpBranch %30 |
| |
| %30 = OpLabel |
| OpBranchConditional %cond %40 %99 |
| |
| %40 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.RegisterMerges()); |
| |
| // Loop header points to continue and merge |
| const auto* bi20 = fe.GetBlockInfo(20); |
| ASSERT_NE(bi20, nullptr); |
| EXPECT_EQ(bi20->merge_for_header, 99u); |
| EXPECT_EQ(bi20->continue_for_header, 40u); |
| EXPECT_EQ(bi20->header_for_merge, 0u); |
| EXPECT_EQ(bi20->header_for_continue, 0u); |
| EXPECT_FALSE(bi20->is_continue_entire_loop); |
| |
| // Continue block points to header |
| const auto* bi40 = fe.GetBlockInfo(40); |
| ASSERT_NE(bi40, nullptr); |
| EXPECT_EQ(bi40->merge_for_header, 0u); |
| EXPECT_EQ(bi40->continue_for_header, 0u); |
| EXPECT_EQ(bi40->header_for_merge, 0u); |
| EXPECT_EQ(bi40->header_for_continue, 20u); |
| EXPECT_FALSE(bi40->is_continue_entire_loop); |
| |
| // Merge block points to the header |
| const auto* bi99 = fe.GetBlockInfo(99); |
| ASSERT_NE(bi99, nullptr); |
| EXPECT_EQ(bi99->merge_for_header, 0u); |
| EXPECT_EQ(bi99->continue_for_header, 0u); |
| EXPECT_EQ(bi99->header_for_merge, 20u); |
| EXPECT_EQ(bi99->header_for_continue, 0u); |
| EXPECT_FALSE(bi99->is_continue_entire_loop); |
| } |
| |
| TEST_F( |
| SpvParserCFGTest, |
| RegisterMerges_GoodLoopMerge_MultiBlockLoop_ContinueIsNotHeader_BranchConditional) { // NOLINT |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %40 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %40 |
| |
| %40 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_TRUE(fe.RegisterMerges()); |
| |
| // Loop header points to continue and merge |
| const auto* bi20 = fe.GetBlockInfo(20); |
| ASSERT_NE(bi20, nullptr); |
| EXPECT_EQ(bi20->merge_for_header, 99u); |
| EXPECT_EQ(bi20->continue_for_header, 40u); |
| EXPECT_EQ(bi20->header_for_merge, 0u); |
| EXPECT_EQ(bi20->header_for_continue, 0u); |
| EXPECT_FALSE(bi20->is_continue_entire_loop); |
| |
| // Continue block points to header |
| const auto* bi40 = fe.GetBlockInfo(40); |
| ASSERT_NE(bi40, nullptr); |
| EXPECT_EQ(bi40->merge_for_header, 0u); |
| EXPECT_EQ(bi40->continue_for_header, 0u); |
| EXPECT_EQ(bi40->header_for_merge, 0u); |
| EXPECT_EQ(bi40->header_for_continue, 20u); |
| EXPECT_FALSE(bi40->is_continue_entire_loop); |
| |
| // Merge block points to the header |
| const auto* bi99 = fe.GetBlockInfo(99); |
| ASSERT_NE(bi99, nullptr); |
| EXPECT_EQ(bi99->merge_for_header, 0u); |
| EXPECT_EQ(bi99->continue_for_header, 0u); |
| EXPECT_EQ(bi99->header_for_merge, 20u); |
| EXPECT_EQ(bi99->header_for_continue, 0u); |
| EXPECT_FALSE(bi99->is_continue_entire_loop); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_SelectionMerge_BadTerminator) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT(p->error(), Eq("Selection header 10 does not end in an " |
| "OpBranchConditional or OpSwitch instruction")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_LoopMerge_BadTerminator) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %40 None |
| OpSwitch %selector %99 30 %30 |
| |
| %30 = OpLabel |
| OpBranch %99 |
| |
| %40 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT(p->error(), Eq("Loop header 20 does not end in an OpBranch or " |
| "OpBranchConditional instruction")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_BadMergeBlock) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %void None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT(p->error(), |
| Eq("Structured header block 10 declares invalid merge block 2")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_HeaderIsItsOwnMerge) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %10 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT(p->error(), |
| Eq("Structured header block 10 cannot be its own merge block")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_MergeReused) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %49 None |
| OpBranchConditional %cond %20 %49 |
| |
| %20 = OpLabel |
| OpBranch %49 |
| |
| %49 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpSelectionMerge %49 None ; can't reuse merge block |
| OpBranchConditional %cond %60 %99 |
| |
| %60 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT( |
| p->error(), |
| Eq("Block 49 declared as merge block for more than one header: 10, 50")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_EntryBlockIsLoopHeader) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpLoopMerge %99 %30 None |
| OpBranchConditional %cond %10 %99 |
| |
| %30 = OpLabel |
| OpBranch %10 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT(p->error(), |
| Eq("Function entry block 10 cannot be a loop header")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_BadContinueTarget) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %999 None |
| OpBranchConditional %cond %20 %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT(p->error(), |
| Eq("Structured header 20 declares invalid continue target 999")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_MergeSameAsContinue) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %50 %50 None |
| OpBranchConditional %cond %20 %99 |
| |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT(p->error(), |
| Eq("Invalid structured header block 20: declares block 50 as " |
| "both its merge block and continue target")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_ContinueReused) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %49 %40 None |
| OpBranchConditional %cond %30 %49 |
| |
| %30 = OpLabel |
| OpBranch %40 |
| |
| %40 = OpLabel |
| OpBranch %20 |
| |
| %49 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpLoopMerge %99 %40 None |
| OpBranchConditional %cond %60 %99 |
| |
| %60 = OpLabel |
| OpBranch %70 |
| |
| %70 = OpLabel |
| OpBranch %50 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT(p->error(), Eq("Block 40 declared as continue target for more " |
| "than one header: 20, 50")); |
| } |
| |
| TEST_F(SpvParserCFGTest, RegisterMerges_SingleBlockLoop_NotItsOwnContinue) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %30 None |
| OpBranchConditional %cond %20 %99 |
| |
| %30 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| EXPECT_FALSE(fe.RegisterMerges()); |
| EXPECT_THAT( |
| p->error(), |
| Eq("Block 20 branches to itself but is not its own continue target")); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_OneBlock) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %42 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(42)); |
| |
| const auto* bi = fe.GetBlockInfo(42); |
| ASSERT_NE(bi, nullptr); |
| EXPECT_EQ(bi->pos, 0u); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_IgnoreStaticalyUnreachable) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %15 = OpLabel ; statically dead |
| OpReturn |
| |
| %20 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_KillIsDeadEnd) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %15 = OpLabel ; statically dead |
| OpReturn |
| |
| %20 = OpLabel |
| OpKill ; Kill doesn't lead anywhere |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_UnreachableIsDeadEnd) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %15 = OpLabel ; statically dead |
| OpReturn |
| |
| %20 = OpLabel |
| OpUnreachable ; Unreachable doesn't lead anywhere |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_ReorderSequence) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranchConditional %cond %20 %30 |
| |
| %30 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpBranch %30 ; backtrack, but does dominate %30 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 99)); |
| |
| const auto* bi10 = fe.GetBlockInfo(10); |
| ASSERT_NE(bi10, nullptr); |
| EXPECT_EQ(bi10->pos, 0u); |
| const auto* bi20 = fe.GetBlockInfo(20); |
| ASSERT_NE(bi20, nullptr); |
| EXPECT_EQ(bi20->pos, 1u); |
| const auto* bi30 = fe.GetBlockInfo(30); |
| ASSERT_NE(bi30, nullptr); |
| EXPECT_EQ(bi30->pos, 2u); |
| const auto* bi99 = fe.GetBlockInfo(99); |
| ASSERT_NE(bi99, nullptr); |
| EXPECT_EQ(bi99->pos, 3u); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_DupConditionalBranch) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranchConditional %cond %20 %20 |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_RespectConditionalBranchOrder) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranchConditional %cond %20 %30 |
| |
| %30 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel ; dominated by %20, so follow %20 |
| OpReturn |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_TrueOnlyBranch) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranchConditional %cond %20 %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_FalseOnlyBranch) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranchConditional %cond %99 %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_SwitchOrderNaturallyReversed) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %99 20 %20 30 %30 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %30 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 30, 20, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| ComputeBlockOrder_SwitchWithDefaultOrderNaturallyReversed) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %80 20 %20 30 %30 |
| |
| %80 = OpLabel ; the default case |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %30 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 30, 20, 80, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Switch_DefaultSameAsACase) { |
| auto p = parser(test::Assemble(CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %30 20 %20 30 %30 40 %40 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %30 = OpLabel |
| OpBranch %99 |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| %40 = OpLabel |
| OpBranch %99 |
| |
| OpFunctionEnd |
| )")); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 40, 20, 30, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_RespectSwitchCaseFallthrough) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| ; SPIR-V validation requires a fallthrough destination to immediately |
| ; follow the source. So %20 -> %40, %30 -> %50 |
| OpSwitch %selector %99 20 %20 40 %40 30 %30 50 %50 |
| |
| %50 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %40 = OpLabel |
| OpBranch %99 |
| |
| %30 = OpLabel |
| OpBranch %50 ; fallthrough |
| |
| %20 = OpLabel |
| OpBranch %40 ; fallthrough |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 30, 50, 20, 40, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| ComputeBlockOrder_RespectSwitchCaseFallthrough_FromDefault) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %80 20 %20 30 %30 40 %40 |
| |
| %80 = OpLabel ; the default case |
| OpBranch %30 ; fallthrough to another case |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %40 = OpLabel |
| OpBranch %99 |
| |
| %30 = OpLabel |
| OpBranch %40 |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 80, 30, 40, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| ComputeBlockOrder_RespectSwitchCaseFallthrough_FromCaseToDefaultToCase) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %80 20 %20 30 %30 |
| |
| %20 = OpLabel |
| OpBranch %80 ; fallthrough to default |
| |
| %80 = OpLabel ; the default case |
| OpBranch %30 ; fallthrough to 30 |
| |
| %30 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel ; dominated by %30, so follow %30 |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 80, 30, 99)) << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| ComputeBlockOrder_SwitchCasesFallthrough_OppositeDirections) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %99 20 %20 30 %30 40 %40 50 %50 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpBranch %30 ; forward |
| |
| %40 = OpLabel |
| OpBranch %99 |
| |
| %30 = OpLabel |
| OpBranch %99 |
| |
| ; SPIR-V doesn't actually allow a fall-through that goes backward in the |
| ; module. But the block ordering algorithm tolerates it. |
| %50 = OpLabel |
| OpBranch %40 ; backward |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 50, 40, 20, 30, 99)) |
| << assembly; |
| |
| // We're deliberately testing a case that SPIR-V doesn't allow. |
| p->DeliberatelyInvalidSpirv(); |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| ComputeBlockOrder_RespectSwitchCaseFallthrough_Interleaved) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| ; SPIR-V validation requires a fallthrough destination to immediately |
| ; follow the source. So %20 -> %40 |
| OpSwitch %selector %99 20 %20 40 %40 30 %30 50 %50 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpBranch %40 |
| |
| %30 = OpLabel |
| OpBranch %50 |
| |
| %40 = OpLabel |
| OpBranch %60 |
| |
| %50 = OpLabel |
| OpBranch %70 |
| |
| %60 = OpLabel |
| OpBranch %99 |
| |
| %70 = OpLabel |
| OpBranch %99 |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 30, 50, 70, 20, 40, 60, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Nest_If_Contains_If) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranchConditional %cond %20 %50 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpSelectionMerge %49 None |
| OpBranchConditional %cond %30 %40 |
| |
| %49 = OpLabel |
| OpBranch %99 |
| |
| %30 = OpLabel |
| OpBranch %49 |
| |
| %40 = OpLabel |
| OpBranch %49 |
| |
| %50 = OpLabel |
| OpSelectionMerge %79 None |
| OpBranchConditional %cond %60 %70 |
| |
| %79 = OpLabel |
| OpBranch %99 |
| |
| %60 = OpLabel |
| OpBranch %79 |
| |
| %70 = OpLabel |
| OpBranch %79 |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), |
| ElementsAre(10, 20, 30, 40, 49, 50, 60, 70, 79, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Nest_If_In_SwitchCase) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %50 20 %20 50 %50 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpSelectionMerge %49 None |
| OpBranchConditional %cond %30 %40 |
| |
| %49 = OpLabel |
| OpBranch %99 |
| |
| %30 = OpLabel |
| OpBranch %49 |
| |
| %40 = OpLabel |
| OpBranch %49 |
| |
| %50 = OpLabel |
| OpSelectionMerge %79 None |
| OpBranchConditional %cond %60 %70 |
| |
| %79 = OpLabel |
| OpBranch %99 |
| |
| %60 = OpLabel |
| OpBranch %79 |
| |
| %70 = OpLabel |
| OpBranch %79 |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), |
| ElementsAre(10, 20, 30, 40, 49, 50, 60, 70, 79, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Nest_IfFallthrough_In_SwitchCase) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %50 20 %20 50 %50 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpSelectionMerge %49 None |
| OpBranchConditional %cond %30 %40 |
| |
| %49 = OpLabel |
| OpBranchConditional %cond %99 %50 ; fallthrough |
| |
| %30 = OpLabel |
| OpBranch %49 |
| |
| %40 = OpLabel |
| OpBranch %49 |
| |
| %50 = OpLabel |
| OpSelectionMerge %79 None |
| OpBranchConditional %cond %60 %70 |
| |
| %79 = OpLabel |
| OpBranch %99 |
| |
| %60 = OpLabel |
| OpBranch %79 |
| |
| %70 = OpLabel |
| OpBranch %79 |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), |
| ElementsAre(10, 20, 30, 40, 49, 50, 60, 70, 79, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Nest_IfBreak_In_SwitchCase) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpSwitch %selector %50 20 %20 50 %50 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| %20 = OpLabel |
| OpSelectionMerge %49 None |
| OpBranchConditional %cond %99 %40 ; break-if |
| |
| %40 = OpLabel |
| OpBranch %49 |
| |
| %49 = OpLabel |
| OpBranch %99 |
| |
| %50 = OpLabel |
| OpSelectionMerge %79 None |
| OpBranchConditional %cond %60 %99 ; break-unless |
| |
| %60 = OpLabel |
| OpBranch %79 |
| |
| %79 = OpLabel ; dominated by 60, so must follow 60 |
| OpBranch %99 |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 40, 49, 50, 60, 79, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_SingleBlock_Simple) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| ; The entry block can't be the target of a branch |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %20 None |
| OpBranchConditional %cond %20 %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 99)) << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_SingleBlock_Infinite) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| ; The entry block can't be the target of a branch |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %20 None |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 99)) << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_SingleBlock_DupInfinite) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| ; The entry block can't be the target of a branch |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %20 None |
| OpBranchConditional %cond %20 %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 99)) << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_HeaderHasBreakIf) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 ; like While |
| |
| %30 = OpLabel ; trivial body |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 50, 99)) << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_HeaderHasBreakUnless) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %99 %30 ; has break-unless |
| |
| %30 = OpLabel ; trivial body |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 50, 99)) << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_BodyHasBreak) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %99 ; break |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 50, 99)) << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_BodyHasBreakIf) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranchConditional %cond2 %99 %40 ; break-if |
| |
| %40 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 40, 50, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_BodyHasBreakUnless) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranchConditional %cond2 %40 %99 ; break-unless |
| |
| %40 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 40, 50, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Body_If) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpSelectionMerge %49 None |
| OpBranchConditional %cond2 %40 %45 ; nested if |
| |
| %40 = OpLabel |
| OpBranch %49 |
| |
| %45 = OpLabel |
| OpBranch %49 |
| |
| %49 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 40, 45, 49, 50, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Body_If_Break) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpSelectionMerge %49 None |
| OpBranchConditional %cond2 %40 %49 ; nested if |
| |
| %40 = OpLabel |
| OpBranch %99 ; break from nested if |
| |
| %49 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 40, 49, 50, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_BodyHasContinueIf) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranchConditional %cond2 %50 %40 ; continue-if |
| |
| %40 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 40, 50, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_BodyHasContinueUnless) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranchConditional %cond2 %40 %50 ; continue-unless |
| |
| %40 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 40, 50, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Body_If_Continue) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpSelectionMerge %49 None |
| OpBranchConditional %cond2 %40 %49 ; nested if |
| |
| %40 = OpLabel |
| OpBranch %50 ; continue from nested if |
| |
| %49 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 40, 49, 50, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Body_Switch) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpSelectionMerge %49 None |
| OpSwitch %selector %49 40 %40 45 %45 ; fully nested switch |
| |
| %40 = OpLabel |
| OpBranch %49 |
| |
| %45 = OpLabel |
| OpBranch %49 |
| |
| %49 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 45, 40, 49, 50, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Body_Switch_CaseBreaks) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpSelectionMerge %49 None |
| OpSwitch %selector %49 40 %40 45 %45 |
| |
| %40 = OpLabel |
| ; This case breaks out of the loop. This is not possible in C |
| ; because "break" will escape the switch only. |
| OpBranch %99 |
| |
| %45 = OpLabel |
| OpBranch %49 |
| |
| %49 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 45, 40, 49, 50, 99)) |
| << assembly; |
| |
| // Fails SPIR-V validation: |
| // Branch from block 40 to block 99 is an invalid exit from construct starting |
| // at block 30; branch bypasses merge block 49 |
| p->DeliberatelyInvalidSpirv(); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Body_Switch_CaseContinues) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpSelectionMerge %49 None |
| OpSwitch %selector %49 40 %40 45 %45 |
| |
| %40 = OpLabel |
| OpBranch %50 ; continue bypasses switch merge |
| |
| %45 = OpLabel |
| OpBranch %49 |
| |
| %49 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 45, 40, 49, 50, 99)) |
| << assembly; |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_BodyHasSwitchContinueBreak) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| ; OpSwitch must be preceded by a selection merge |
| OpSwitch %selector %99 50 %50 ; default is break, 50 is continue |
| |
| %40 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| EXPECT_FALSE(p->Parse()); |
| EXPECT_FALSE(p->success()); |
| EXPECT_THAT(p->error(), |
| HasSubstr("OpSwitch must be preceeded by an OpSelectionMerge")); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Continue_Sequence) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranch %60 |
| |
| %60 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 50, 60, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Continue_ContainsIf) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpSelectionMerge %89 None |
| OpBranchConditional %cond2 %60 %70 |
| |
| %89 = OpLabel |
| OpBranch %20 ; backedge |
| |
| %60 = OpLabel |
| OpBranch %89 |
| |
| %70 = OpLabel |
| OpBranch %89 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 50, 60, 70, 89, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Continue_HasBreakIf) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranchConditional %cond2 %99 %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 50, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Continue_HasBreakUnless) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpBranchConditional %cond2 %20 %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 50, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Continue_SwitchBreak) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| ; Updated SPIR-V rule: |
| ; OpSwitch must be preceded by a selection. |
| OpSwitch %selector %20 99 %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| EXPECT_FALSE(p->Parse()); |
| EXPECT_FALSE(p->success()); |
| EXPECT_THAT(p->error(), |
| HasSubstr("OpSwitch must be preceeded by an OpSelectionMerge")); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Loop) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpLoopMerge %49 %40 None |
| OpBranchConditional %cond2 %35 %49 |
| |
| %35 = OpLabel |
| OpBranch %37 |
| |
| %37 = OpLabel |
| OpBranch %40 |
| |
| %40 = OpLabel ; inner loop's continue |
| OpBranch %30 ; backedge |
| |
| %49 = OpLabel ; inner loop's merge |
| OpBranch %50 |
| |
| %50 = OpLabel ; outer loop's continue |
| OpBranch %20 ; outer loop's backege |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), |
| ElementsAre(10, 20, 30, 35, 37, 40, 49, 50, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Loop_InnerBreak) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpLoopMerge %49 %40 None |
| OpBranchConditional %cond2 %35 %49 |
| |
| %35 = OpLabel |
| OpBranchConditional %cond3 %49 %37 ; break to inner merge |
| |
| %37 = OpLabel |
| OpBranch %40 |
| |
| %40 = OpLabel ; inner loop's continue |
| OpBranch %30 ; backedge |
| |
| %49 = OpLabel ; inner loop's merge |
| OpBranch %50 |
| |
| %50 = OpLabel ; outer loop's continue |
| OpBranch %20 ; outer loop's backege |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), |
| ElementsAre(10, 20, 30, 35, 37, 40, 49, 50, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Loop_InnerContinue) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpLoopMerge %49 %40 None |
| OpBranchConditional %cond2 %35 %49 |
| |
| %35 = OpLabel |
| OpBranchConditional %cond3 %37 %49 ; continue to inner continue target |
| |
| %37 = OpLabel |
| OpBranch %40 |
| |
| %40 = OpLabel ; inner loop's continue |
| OpBranch %30 ; backedge |
| |
| %49 = OpLabel ; inner loop's merge |
| OpBranch %50 |
| |
| %50 = OpLabel ; outer loop's continue |
| OpBranch %20 ; outer loop's backege |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), |
| ElementsAre(10, 20, 30, 35, 37, 40, 49, 50, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Loop_InnerContinueBreaks) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpLoopMerge %49 %40 None |
| OpBranchConditional %cond2 %35 %49 |
| |
| %35 = OpLabel |
| OpBranch %37 |
| |
| %37 = OpLabel |
| OpBranch %40 |
| |
| %40 = OpLabel ; inner loop's continue |
| OpBranchConditional %cond3 %30 %49 ; backedge and inner break |
| |
| %49 = OpLabel ; inner loop's merge |
| OpBranch %50 |
| |
| %50 = OpLabel ; outer loop's continue |
| OpBranch %20 ; outer loop's backege |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), |
| ElementsAre(10, 20, 30, 35, 37, 40, 49, 50, 99)); |
| } |
| |
| TEST_F(SpvParserCFGTest, ComputeBlockOrder_Loop_Loop_InnerContinueContinues) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpLoopMerge %49 %40 None |
| OpBranchConditional %cond2 %35 %49 |
| |
| %35 = OpLabel |
| OpBranch %37 |
| |
| %37 = OpLabel |
| OpBranch %40 |
| |
| %40 = OpLabel ; inner loop's continue |
| OpBranchConditional %cond3 %30 %50 ; backedge and continue to outer |
| |
| %49 = OpLabel ; inner loop's merge |
| OpBranch %50 |
| |
| %50 = OpLabel ; outer loop's continue |
| OpBranch %20 ; outer loop's backege |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), |
| ElementsAre(10, 20, 30, 35, 37, 40, 49, 50, 99)); |
| |
| p->DeliberatelyInvalidSpirv(); |
| // SPIR-V validation fails: |
| // block <ID> 40[%40] exits the continue headed by <ID> 40[%40], but not |
| // via a structured exit" |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| ComputeBlockOrder_Loop_Loop_SwitchBackedgeBreakContinue) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %50 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpLoopMerge %49 %40 None |
| OpBranchConditional %cond2 %35 %49 |
| |
| %35 = OpLabel |
| OpBranch %37 |
| |
| %37 = OpLabel |
| OpBranch %40 |
| |
| %40 = OpLabel ; inner loop's continue |
| ; This switch does triple duty: |
| ; default -> backedge |
| ; 49 -> loop break |
| ; 49 -> inner loop break |
| ; 50 -> outer loop continue |
| OpSwitch %selector %30 49 %49 50 %50 |
| |
| %49 = OpLabel ; inner loop's merge |
| OpBranch %50 |
| |
| %50 = OpLabel ; outer loop's continue |
| OpBranch %20 ; outer loop's backege |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| |
| EXPECT_THAT(fe.block_order(), |
| ElementsAre(10, 20, 30, 35, 37, 40, 49, 50, 99)); |
| |
| p->DeliberatelyInvalidSpirv(); |
| // SPIR-V validation fails: |
| // block <ID> 40[%40] exits the continue headed by <ID> 40[%40], but not |
| // via a structured exit" |
| } |
| |
| TEST_F(SpvParserCFGTest, VerifyHeaderContinueMergeOrder_Selection_Good) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpSelectionMerge %99 None |
| OpBranchConditional %cond %20 %30 |
| |
| %20 = OpLabel |
| OpBranch %99 |
| |
| %30 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| fe.RegisterMerges(); |
| EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder()); |
| } |
| |
| TEST_F(SpvParserCFGTest, VerifyHeaderContinueMergeOrder_SingleBlockLoop_Good) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %20 None |
| OpBranchConditional %cond %20 %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| fe.RegisterMerges(); |
| EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder()) << p->error(); |
| } |
| |
| TEST_F(SpvParserCFGTest, VerifyHeaderContinueMergeOrder_MultiBlockLoop_Good) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpLoopMerge %99 %30 None |
| OpBranchConditional %cond %30 %99 |
| |
| %30 = OpLabel |
| OpBranch %20 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| fe.RegisterMerges(); |
| EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder()); |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| VerifyHeaderContinueMergeOrder_HeaderDoesNotStrictlyDominateMerge) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpSelectionMerge %20 None ; this is backward |
| OpBranchConditional %cond2 %60 %99 |
| |
| %60 = OpLabel |
| OpBranch %99 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| fe.RegisterMerges(); |
| EXPECT_FALSE(fe.VerifyHeaderContinueMergeOrder()); |
| EXPECT_THAT(p->error(), |
| Eq("Header 50 does not strictly dominate its merge block 20")) |
| << *fe.GetBlockInfo(50) << std::endl |
| << *fe.GetBlockInfo(20) << std::endl |
| << Dump(fe.block_order()); |
| } |
| |
| TEST_F( |
| SpvParserCFGTest, |
| VerifyHeaderContinueMergeOrder_HeaderDoesNotStrictlyDominateContinueTarget) { // NOLINT |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %20 |
| |
| %20 = OpLabel |
| OpBranch %50 |
| |
| %50 = OpLabel |
| OpLoopMerge %99 %20 None ; this is backward |
| OpBranchConditional %cond %60 %99 |
| |
| %60 = OpLabel |
| OpBranch %50 |
| |
| %99 = OpLabel |
| OpReturn |
| |
| OpFunctionEnd |
| )"; |
| auto p = parser(test::Assemble(assembly)); |
| ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error(); |
| auto fe = p->function_emitter(100); |
| fe.RegisterBasicBlocks(); |
| fe.ComputeBlockOrderAndPositions(); |
| fe.RegisterMerges(); |
| EXPECT_FALSE(fe.VerifyHeaderContinueMergeOrder()); |
| EXPECT_THAT(p->error(), |
| Eq("Loop header 50 does not dominate its continue target 20")) |
| << *fe.GetBlockInfo(50) << std::endl |
| << *fe.GetBlockInfo(20) << std::endl |
| << Dump(fe.block_order()); |
| } |
| |
| TEST_F(SpvParserCFGTest, |
| VerifyHeaderContinueMergeOrder_MergeInsideContinueTarget) { |
| auto assembly = CommonTypes() + R"( |
| %100 = OpFunction %void None %voidfn |
| |
| %10 = OpLabel |
| OpBranch %50 |
| |
|