blob: 4878a7f87422dc61d9a372a62d521807cdd5e474 [file] [log] [blame]
// Copyright 2020 The Dawn & Tint Authors
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include "gmock/gmock.h"
#include "src/tint/lang/spirv/reader/ast_parser/function.h"
#include "src/tint/lang/spirv/reader/ast_parser/helper_test.h"
#include "src/tint/lang/spirv/reader/ast_parser/spirv_tools_helpers_test.h"
#include "src/tint/utils/text/string_stream.h"
namespace tint::spirv::reader::ast_parser {
namespace {
using ::testing::Eq;
using ::testing::HasSubstr;
// Make a local name so it's easier to triage errors.
using SpvParserCFGTest = SpirvASTParserTest;
std::string Dump(const std::vector<uint32_t>& v) {
tint::StringStream 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) {
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, ClassifyCFGEdges_Fallthrough_IsError) {
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);
EXPECT_FALSE(FlowClassifyCFGEdges(&fe)) << p->error();
// Some further processing
EXPECT_THAT(p->error(), Eq("Fallthrough not permitted in WGSL"));
}
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_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
%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 preceded 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 preceded 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());
tint::StringStream result;
result << *fe.GetBlockInfo(50) << "\n" << *fe.GetBlockInfo(20) << "\n";
EXPECT_THAT(p->error(), Eq("Header 50 does not strictly dominate its merge block 20"))
<< result.str() << Dump(fe.block_order());
}
TEST_F(SpvParserCFGTest,
VerifyHeaderContinueMergeOrder_HeaderDoesNotStrictlyDominateContinueTarget) {
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());
tint::StringStream str;
str << *fe.GetBlockInfo(50) << "\n" << *fe.GetBlockInfo(20) << "\n";
EXPECT_THAT(p->error(), Eq("Loop header 50 does not dominate its continue target 20"))
<< str.str() << Dump(fe.block_order());
}
TEST_F(SpvParserCFGTest, VerifyHeaderContinueMergeOrder_MergeInsideContinueTarget) {
auto assembly = CommonTypes() + R"(
%100 = OpFunction %void None %voidfn
%10 = OpLabel
OpBranch %50
%50 = OpLabel
OpLoopMerge %60 %70 None
OpBranchConditional %cond %60 %99
%60 = OpLabel
OpBranch %70
%70 = 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("Merge block 60 for loop headed at block 50 appears at or "
"before the loop's continue construct headed by block 70"))
<< Dump(fe.block_order());
}
TEST_F(SpvParserCFGTest, LabelControlFlowConstructs_OuterConstructIsFunction_SingleBlock) {
auto assembly = CommonTypes() + R"(
%100 = OpFunction %void None %voidfn
%10 = 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.LabelControlFlowConstructs());
EXPECT_EQ(fe.constructs().Length(), 1u);
auto& c = fe.constructs().Front();
EXPECT_THAT(ToString(c), Eq("Construct{ Function [0,1) begin_id:10 end_id:0 "
"depth:0 parent:null }"));
EXPECT_EQ(fe.GetBlockInfo(10)->construct, c.get());
}
TEST_F(SpvParserCFGTest, LabelControlFlowConstructs_OuterConstructIsFunction_MultiBlock) {
auto assembly = CommonTypes() + R"(
%100 = OpFunction %void None %voidfn
%10 = OpLabel
OpBranch %5
%5 = 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.LabelControlFlowConstructs());
EXPECT_EQ(fe.constructs().Length(), 1u);
auto& c = fe.constructs().Front();
EXPECT_THAT(ToString(c), Eq("Construct{ Function [0,2) begin_id:10 end_id:0 "
"depth:0 parent:null }"));
EXPECT_EQ(fe.GetBlockInfo(10)->construct, c.get());
EXPECT_EQ(fe.GetBlockInfo(5)->construct, c.get());
}
TEST_F(SpvParserCFGTest, LabelControlFlowConstructs_FunctionIsOnlyIfSelectionAndItsMerge) {
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.LabelControlFlowConstructs());
const auto& constructs = fe.constructs();
EXPECT_EQ(constructs.Length(), 2u);
tint::StringStream str;
str << constructs;
EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
Construct{ Function [0,4) begin_id:10 end_id:0 depth:0 parent:null }
Construct{ IfSelection [0,3) begin_id:10 end_id:99 depth:1 parent:Function@10 }
})")) << str.str();
// The block records the nearest enclosing construct.
EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[1].get());
EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[1].get());
EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
}
TEST_F(SpvParserCFGTest,
LabelControlFlowConstructs_PaddingBlocksBeforeAndAfterStructuredConstruct) {
auto assembly = CommonTypes() + R"(
%100 = OpFunction %void None %voidfn
%5 = OpLabel
OpBranch %10
%10 = OpLabel
OpSelectionMerge %99 None
OpBranchConditional %cond %20 %30
%20 = OpLabel
OpBranch %99
%30 = OpLabel
OpBranch %99
%99 = OpLabel
OpBranch %200
%200 = 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.LabelControlFlowConstructs());
const auto& constructs = fe.constructs();
EXPECT_EQ(constructs.Length(), 2u);
tint::StringStream str;
str << constructs;
EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
Construct{ Function [0,6) begin_id:5 end_id:0 depth:0 parent:null }
Construct{ IfSelection [1,4) begin_id:10 end_id:99 depth:1 parent:Function@5 }
})")) << str.str();
// The block records the nearest enclosing construct.
EXPECT_EQ(fe.GetBlockInfo(5)->construct, constructs[0].get());
EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[1].get());
EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[1].get());
EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
EXPECT_EQ(fe.GetBlockInfo(200)->construct, constructs[0].get());
}
TEST_F(SpvParserCFGTest, LabelControlFlowConstructs_SwitchSelection) {
auto assembly = CommonTypes() + R"(
%100 = OpFunction %void None %voidfn
%10 = OpLabel
OpSelectionMerge %99 None
OpSwitch %selector %40 20 %20 30 %30
%20 = OpLabel
OpBranch %99
%30 = OpLabel
OpBranch %99
%40 = 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.LabelControlFlowConstructs());
const auto& constructs = fe.constructs();
EXPECT_EQ(constructs.Length(), 2u