[spirv-reader] Find switch case headers
Bug: tint:3
Change-Id: I66785fd6cbbe1432a4eda3f3258e4b9b0457f303
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/20422
Reviewed-by: dan sinclair <dsinclair@google.com>
diff --git a/src/reader/spirv/function.cc b/src/reader/spirv/function.cc
index 1f24a10..eb0ef83 100644
--- a/src/reader/spirv/function.cc
+++ b/src/reader/spirv/function.cc
@@ -440,6 +440,9 @@
if (!LabelControlFlowConstructs()) {
return false;
}
+ if (!FindSwitchCaseHeaders()) {
+ return false;
+ }
if (!EmitFunctionVariables()) {
return false;
@@ -806,6 +809,111 @@
return success();
}
+bool FunctionEmitter::FindSwitchCaseHeaders() {
+ if (failed()) {
+ return false;
+ }
+ for (auto& construct : constructs_) {
+ if (construct->kind != Construct::kSelection) {
+ continue;
+ }
+ const auto* branch =
+ GetBlockInfo(construct->begin_id)->basic_block->terminator();
+ if (branch->opcode() != SpvOpSwitch) {
+ continue;
+ }
+
+ // Mark the default block
+ const auto default_id = branch->GetSingleWordInOperand(1);
+ auto* default_block = GetBlockInfo(default_id);
+ // A default target can't be a backedge.
+ if (construct->begin_pos >= default_block->pos) {
+ // An OpSwitch must dominate its cases. Also, it can't be a self-loop
+ // as that would be a backedge, and backedges can only target a loop,
+ // and loops use an OpLoopMerge instruction, which can't preceded an
+ // OpSwitch.
+ return Fail() << "Switch branch from block " << construct->begin_id
+ << " to default target block " << default_id
+ << " can't be a back-edge";
+ }
+ // A default target can be the merge block, but can't go past it.
+ if (construct->end_pos < default_block->pos) {
+ return Fail() << "Switch branch from block " << construct->begin_id
+ << " to default block " << default_id
+ << " escapes the selection construct";
+ }
+ if (default_block->default_head_for) {
+ // An OpSwitch must dominate its cases, including the default target.
+ return Fail() << "Block " << default_id
+ << " is declared as the default target for two OpSwitch "
+ "instructions, at blocks "
+ << default_block->default_head_for->begin_id << " and "
+ << construct->begin_id;
+ }
+
+ default_block->default_head_for = construct.get();
+ default_block->default_is_merge = default_block->pos == construct->end_pos;
+
+ // Map a case target to the list of values selecting that case.
+ std::unordered_map<uint32_t, std::vector<uint64_t>> block_to_values;
+ std::vector<uint32_t> case_targets;
+ std::unordered_set<uint64_t> case_values;
+
+ // Process case targets.
+ for (uint32_t iarg = 2; iarg + 1 < branch->NumInOperands(); iarg += 2) {
+ const auto o = branch->GetInOperand(iarg);
+ const auto value = branch->GetInOperand(iarg).AsLiteralUint64();
+ const auto case_target_id = branch->GetSingleWordInOperand(iarg + 1);
+
+ if (case_values.count(value)) {
+ return Fail() << "Duplicate case value " << value
+ << " in OpSwitch in block " << construct->begin_id;
+ }
+ case_values.insert(value);
+ if (block_to_values.count(case_target_id) == 0) {
+ case_targets.push_back(case_target_id);
+ }
+ block_to_values[case_target_id].push_back(value);
+ }
+
+ for (uint32_t case_target_id : case_targets) {
+ auto* case_block = GetBlockInfo(case_target_id);
+
+ case_block->case_values = std::make_unique<std::vector<uint64_t>>(std::move(block_to_values[case_target_id]));
+
+ // A case target can't be a back-edge.
+ if (construct->begin_pos >= case_block->pos) {
+ // An OpSwitch must dominate its cases. Also, it can't be a self-loop
+ // as that would be a backedge, and backedges can only target a loop,
+ // and loops use an OpLoopMerge instruction, which can't preceded an
+ // OpSwitch.
+ return Fail() << "Switch branch from block " << construct->begin_id
+ << " to case target block " << case_target_id
+ << " can't be a back-edge";
+ }
+ // A case target can be the merge block, but can't go past it.
+ if (construct->end_pos < case_block->pos) {
+ return Fail() << "Switch branch from block " << construct->begin_id
+ << " to case target block " << case_target_id
+ << " escapes the selection construct";
+ }
+
+ // Mark the target as a case target.
+ if (case_block->case_head_for) {
+ // An OpSwitch must dominate its cases.
+ return Fail()
+ << "Block " << case_target_id
+ << " is declared as the switch case target for two OpSwitch "
+ "instructions, at blocks "
+ << case_block->case_head_for->begin_id << " and "
+ << construct->begin_id;
+ }
+ case_block->case_head_for = construct.get();
+ }
+ }
+ return success();
+}
+
bool FunctionEmitter::EmitFunctionVariables() {
if (failed()) {
return false;
diff --git a/src/reader/spirv/function.h b/src/reader/spirv/function.h
index e554aa3..e228b92 100644
--- a/src/reader/spirv/function.h
+++ b/src/reader/spirv/function.h
@@ -70,6 +70,23 @@
/// The immediately enclosing structured construct.
const Construct* construct = nullptr;
+
+ /// The following fields record relationships among blocks in a selection
+ /// construct for an OpSwitch instruction.
+
+ /// If not null, then the pointed-at construct is a selection for an OpSwitch,
+ /// and this block is a case target for it. We say this block "heads" the
+ /// case construct.
+ const Construct* case_head_for = nullptr;
+ /// If not null, then the pointed-at construct is a selection for an OpSwitch,
+ /// and this block is the default target for it. We say this block "heads"
+ /// the default case construct.
+ const Construct* default_head_for = nullptr;
+ /// Is this a default target for a switch, and is it also the merge for its
+ /// switch?
+ bool default_is_merge = false;
+ /// The list of switch values that cause a branch to this block.
+ std::unique_ptr<std::vector<uint64_t>> case_values;
};
inline std::ostream& operator<<(std::ostream& o, const BlockInfo& bi) {
@@ -162,6 +179,11 @@
/// @returns the structured constructs
const ConstructList& constructs() const { return constructs_; }
+ /// Marks blocks targets of a switch, either as the head of a case or
+ /// as the default target.
+ /// @returns false on failure
+ bool FindSwitchCaseHeaders();
+
/// Emits declarations of function variables.
/// @returns false if emission failed.
bool EmitFunctionVariables();
diff --git a/src/reader/spirv/function_cfg_test.cc b/src/reader/spirv/function_cfg_test.cc
index da99ab4..5805bbe 100644
--- a/src/reader/spirv/function_cfg_test.cc
+++ b/src/reader/spirv/function_cfg_test.cc
@@ -39,6 +39,7 @@
using ::testing::ElementsAre;
using ::testing::Eq;
+using ::testing::UnorderedElementsAre;
std::string CommonTypes() {
return R"(
@@ -3540,6 +3541,624 @@
EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
}
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_DefaultIsLongRangeBackedge) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %10 30 %30
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ EXPECT_THAT(p->error(), Eq("Switch branch from block 20 to default target "
+ "block 10 can't be a back-edge"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_DefaultIsSelfLoop) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %20 30 %30
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ // Self-loop that isn't its own continue target is already rejected with a
+ // different message.
+ EXPECT_THAT(
+ p->error(),
+ Eq("Block 20 branches to itself but is not its own continue target"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_DefaultCantEscapeSwitch) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %50 None
+ OpSwitch %selector %99 30 %30 ; default goes past the merge
+
+ %30 = OpLabel
+ OpBranch %50
+
+ %50 = OpLabel ; merge
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ EXPECT_THAT(p->error(), Eq("Switch branch from block 10 to default block 99 "
+ "escapes the selection construct"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_DefaultForTwoSwitches) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %89 20 %20
+
+ %20 = OpLabel
+ OpBranch %50
+
+ %50 = OpLabel
+ OpSelectionMerge %89 None
+ OpSwitch %selector %89 60 %60
+
+ %60 = OpLabel
+ OpBranch %89
+
+ %89 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ EXPECT_THAT(p->error(), Eq("Block 89 is declared as the default target for "
+ "two OpSwitch instructions, at blocks 10 and 50"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_CaseIsLongRangeBackedge) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 10 %10
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ EXPECT_THAT(p->error(), Eq("Switch branch from block 20 to case target "
+ "block 10 can't be a back-edge"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_CaseIsSelfLoop) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 20 %20
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ // The error is caught earlier
+ EXPECT_THAT(
+ p->error(),
+ Eq("Block 20 branches to itself but is not its own continue target"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_CaseCanBeSwitchMerge) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 20 %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_TRUE(fe.FindSwitchCaseHeaders());
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_CaseCantEscapeSwitch) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None ; force %99 to be very late in block order
+ OpBranchConditional %cond %20 %99
+
+ %20 = OpLabel
+ OpSelectionMerge %89 None
+ OpSwitch %selector %89 20 %99
+
+ %89 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ EXPECT_THAT(p->error(), Eq("Switch branch from block 20 to case target block "
+ "99 escapes the selection construct"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_CaseForMoreThanOneSwitch) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 20 %20 50 %50
+
+ %20 = OpLabel
+ OpSelectionMerge %89 None
+ OpSwitch %selector %89 50 %50
+
+ %50 = OpLabel
+ OpBranch %89
+
+ %89 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ EXPECT_THAT(p->error(),
+ Eq("Block 50 is declared as the switch case target for two "
+ "OpSwitch instructions, at blocks 10 and 20"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_CaseIsMergeForAnotherConstruct) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %49 None
+ OpSwitch %selector %49 20 %20
+
+ %20 = OpLabel
+ OpBranch %49
+
+ %49 = OpLabel
+ OpBranch %50
+
+ %50 = OpLabel
+ OpSelectionMerge %20 None ; points back to the case.
+ OpBranchConditional %cond %60 %99
+
+ %60 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ EXPECT_THAT(p->error(), Eq("Switch branch from block 10 to case target block "
+ "20 escapes the selection construct"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_NoSwitch) {
+ 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();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_TRUE(fe.FindSwitchCaseHeaders());
+
+ const auto* bi10 = fe.GetBlockInfo(10);
+ ASSERT_NE(bi10, nullptr);
+ EXPECT_EQ(bi10->case_head_for, nullptr);
+ EXPECT_EQ(bi10->default_head_for, nullptr);
+ EXPECT_FALSE(bi10->default_is_merge);
+ EXPECT_EQ(bi10->case_values.get(), nullptr);
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_DefaultIsMerge) {
+ auto assembly = 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
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_TRUE(fe.FindSwitchCaseHeaders());
+
+ const auto* bi99 = fe.GetBlockInfo(99);
+ ASSERT_NE(bi99, nullptr);
+ EXPECT_EQ(bi99->case_head_for, nullptr);
+ ASSERT_NE(bi99->default_head_for, nullptr);
+ EXPECT_EQ(bi99->default_head_for->begin_id, 10);
+ EXPECT_TRUE(bi99->default_is_merge);
+ EXPECT_EQ(bi99->case_values.get(), nullptr);
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_DefaultIsNotMerge) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %30 20 %20
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_TRUE(fe.FindSwitchCaseHeaders());
+
+ const auto* bi30 = fe.GetBlockInfo(30);
+ ASSERT_NE(bi30, nullptr);
+ EXPECT_EQ(bi30->case_head_for, nullptr);
+ ASSERT_NE(bi30->default_head_for, nullptr);
+ EXPECT_EQ(bi30->default_head_for->begin_id, 10);
+ EXPECT_FALSE(bi30->default_is_merge);
+ EXPECT_EQ(bi30->case_values.get(), nullptr);
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_CaseIsNotDefault) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %30 200 %20
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_TRUE(fe.FindSwitchCaseHeaders());
+
+ const auto* bi20 = fe.GetBlockInfo(20);
+ ASSERT_NE(bi20, nullptr);
+ ASSERT_NE(bi20->case_head_for, nullptr);
+ EXPECT_EQ(bi20->case_head_for->begin_id, 10);
+ EXPECT_EQ(bi20->default_head_for, nullptr);
+ EXPECT_FALSE(bi20->default_is_merge);
+ EXPECT_THAT(*(bi20->case_values.get()), UnorderedElementsAre(200));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_CaseIsDefault) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %20 200 %20
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_TRUE(fe.FindSwitchCaseHeaders());
+
+ const auto* bi20 = fe.GetBlockInfo(20);
+ ASSERT_NE(bi20, nullptr);
+ ASSERT_NE(bi20->case_head_for, nullptr);
+ EXPECT_EQ(bi20->case_head_for->begin_id, 10);
+ EXPECT_EQ(bi20->default_head_for, bi20->case_head_for);
+ EXPECT_FALSE(bi20->default_is_merge);
+ EXPECT_THAT(*(bi20->case_values.get()), UnorderedElementsAre(200));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_ManyCasesWithSameValue_Error) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 200 %20 200 %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();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+
+ EXPECT_THAT(p->error(),
+ Eq("Duplicate case value 200 in OpSwitch in block 10"));
+}
+
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_ManyValuesWithSameCase) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 200 %20 300 %20
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ EXPECT_TRUE(fe.FindSwitchCaseHeaders());
+
+ const auto* bi20 = fe.GetBlockInfo(20);
+ ASSERT_NE(bi20, nullptr);
+ ASSERT_NE(bi20->case_head_for, nullptr);
+ EXPECT_EQ(bi20->case_head_for->begin_id, 10);
+ EXPECT_EQ(bi20->default_head_for, nullptr);
+ EXPECT_FALSE(bi20->default_is_merge);
+ EXPECT_THAT(*(bi20->case_values.get()), UnorderedElementsAre(200, 300));
+}
+
+TEST_F(SpvParserTest, DISABLED_BranchEscapesIfConstruct) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %99
+
+ %20 = OpLabel
+ OpSelectionMerge %50 None
+ OpBranchConditional %cond2 %30 %50
+
+ %30 = OpLabel
+ OpBranch %80 ; bad exit to %80
+
+ %50 = OpLabel
+ OpBranch %80
+
+ %80 = OpLabel ; bad target
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe.VerifyHeaderContinueMergeOrder());
+ fe.RegisterMerges();
+ fe.LabelControlFlowConstructs();
+ fe.FindSwitchCaseHeaders();
+ // Some further processing
+ EXPECT_THAT(p->error(), Eq("something"));
+}
+
+// TODO(dneto): Ok for a case target to branch directly to the merge
+// TODO(dneto): Ok for a case target to be a "break block", i.e. branch to exit
+// of enclosing loop.
+// TODO(dneto): Ok for a case target to be a "continue block", i.e. branch to
+// continue target of enclosing loop.
+
} // namespace
} // namespace spirv
} // namespace reader
