[spirv-reader] Check some merge block dominance
A merge block must be dominated by its own header.
This CL checks the cases where that fails because the
merge block is also the:
- the default or case header for a switch (a different header)
- the true-head, false-head, or premerge-head for an if-selection
with a different header
Bug: tint:3
Change-Id: I6dd1fae162e9d33bd9a0b43d3ca9558cebed058b
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/22680
Reviewed-by: dan sinclair <dsinclair@google.com>
diff --git a/src/reader/spirv/function.cc b/src/reader/spirv/function.cc
index d326ead..2322589 100644
--- a/src/reader/spirv/function.cc
+++ b/src/reader/spirv/function.cc
@@ -943,6 +943,17 @@
<< default_block->default_head_for->begin_id << " and "
<< construct->begin_id;
}
+ if ((default_block->header_for_merge != 0) &&
+ (default_block->header_for_merge != construct->begin_id)) {
+ // The switch instruction for this default block is an alternate path to
+ // the merge block, and hence the merge block is not dominated by its own
+ // (different) header.
+ return Fail() << "Block " << default_block->id
+ << " is the default block for switch-selection header "
+ << construct->begin_id << " and also the merge block for "
+ << default_block->header_for_merge
+ << " (violates dominance rule)";
+ }
default_block->default_head_for = construct.get();
default_block->default_is_merge = default_block->pos == construct->end_pos;
@@ -991,6 +1002,17 @@
<< " to case target block " << case_target_id
<< " escapes the selection construct";
}
+ if (case_block->header_for_merge != 0 &&
+ case_block->header_for_merge != construct->begin_id) {
+ // The switch instruction for this case block is an alternate path to
+ // the merge block, and hence the merge block is not dominated by its
+ // own (different) header.
+ return Fail() << "Block " << case_block->id
+ << " is a case block for switch-selection header "
+ << construct->begin_id << " and also the merge block for "
+ << case_block->header_for_merge
+ << " (violates dominance rule)";
+ }
// Mark the target as a case target.
if (case_block->case_head_for) {
@@ -1309,6 +1331,29 @@
false_head_info->exclusive_false_head_for = construct.get();
}
+ if ((true_head_info->header_for_merge != 0) &&
+ (true_head_info->header_for_merge != construct->begin_id)) {
+ // The OpBranchConditional instruction for the true head block is an
+ // alternate path to the merge block, and hence the merge block is not
+ // dominated by its own (different) header.
+ return Fail() << "Block " << true_head
+ << " is the true branch for if-selection header "
+ << construct->begin_id << " and also the merge block for header block "
+ << true_head_info->header_for_merge
+ << " (violates dominance rule)";
+ }
+ if ((false_head_info->header_for_merge != 0) &&
+ (false_head_info->header_for_merge != construct->begin_id)) {
+ // The OpBranchConditional instruction for the false head block is an
+ // alternate path to the merge block, and hence the merge block is not
+ // dominated by its own (different) header.
+ return Fail() << "Block " << false_head
+ << " is the false branch for if-selection header "
+ << construct->begin_id << " and also the merge block for header block "
+ << false_head_info->header_for_merge
+ << " (violates dominance rule)";
+ }
+
if (contains_true && contains_false && (true_head_pos != false_head_pos)) {
// This construct has both a "then" clause and an "else" clause.
//
@@ -1382,6 +1427,23 @@
auto* dest_block_info = GetBlockInfo(dest_id);
dest_block_info->premerge_head_for = construct.get();
if_header_info->premerge_head = dest_block_info;
+ if (dest_block_info->header_for_merge != 0) {
+ // Premerge has two edges coming into it, from the then-clause
+ // and the else-clause. It's also, by construction, not the
+ // merge block of the if-selection. So it must not be a merge
+ // block itself. The OpBranchConditional instruction for the
+ // false head block is an alternate path to the merge block, and
+ // hence the merge block is not dominated by its own (different)
+ // header.
+ return Fail()
+ << "Block " << premerge_id
+ << " is the merge block for " << dest_block_info->header_for_merge
+ << " but has alternate paths reaching it, starting from"
+ << " blocks " << true_head << " and " << false_head
+ << " which are the true and false branches for the"
+ << " if-selection header block " << construct->begin_id
+ << " (violates dominance rule)";
+ }
}
break;
}
diff --git a/src/reader/spirv/function_cfg_test.cc b/src/reader/spirv/function_cfg_test.cc
index 447c259..d3b7efc 100644
--- a/src/reader/spirv/function_cfg_test.cc
+++ b/src/reader/spirv/function_cfg_test.cc
@@ -79,15 +79,22 @@
)";
}
+/// Runs the necessary flow until and including finding switch case
+/// headers.
+/// @returns the result of finding switch case headers.
+bool FlowFindSwitchCaseHeaders(FunctionEmitter* fe) {
+ fe->RegisterBasicBlocks();
+ EXPECT_TRUE(fe->RegisterMerges()) << fe->parser()->error();
+ fe->ComputeBlockOrderAndPositions();
+ EXPECT_TRUE(fe->VerifyHeaderContinueMergeOrder()) << fe->parser()->error();
+ EXPECT_TRUE(fe->LabelControlFlowConstructs()) << 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) {
- fe->RegisterBasicBlocks();
- fe->ComputeBlockOrderAndPositions();
- EXPECT_TRUE(fe->VerifyHeaderContinueMergeOrder()) << fe->parser()->error();
- EXPECT_TRUE(fe->RegisterMerges()) << fe->parser()->error();
- EXPECT_TRUE(fe->LabelControlFlowConstructs()) << fe->parser()->error();
- EXPECT_TRUE(fe->FindSwitchCaseHeaders()) << fe->parser()->error();
+ EXPECT_TRUE(FlowFindSwitchCaseHeaders(fe)) << fe->parser()->error();
return fe->ClassifyCFGEdges();
}
@@ -3676,7 +3683,7 @@
"escapes the selection construct"));
}
-TEST_F(SpvParserTest, FindSwitchCaseHeaders_DefaultForTwoSwitches) {
+TEST_F(SpvParserTest, FindSwitchCaseHeaders_DefaultForTwoSwitches_AsMerge) {
auto assembly = CommonTypes() + R"(
%100 = OpFunction %void None %voidfn
@@ -3711,7 +3718,51 @@
fe.RegisterMerges();
fe.LabelControlFlowConstructs();
EXPECT_FALSE(fe.FindSwitchCaseHeaders());
- EXPECT_THAT(p->error(), Eq("Block 89 is declared as the default target for "
+ EXPECT_THAT(p->error(),
+ Eq("Block 89 is the default block for switch-selection header 10 "
+ "and also the merge block for 50 (violates dominance rule)"));
+}
+
+TEST_F(SpvParserTest,
+ FindSwitchCaseHeaders_DefaultForTwoSwitches_AsCaseClause) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %80 20 %20
+
+ %20 = OpLabel
+ OpBranch %50
+
+ %50 = OpLabel
+ OpSelectionMerge %89 None
+ OpSwitch %selector %80 60 %60
+
+ %60 = OpLabel
+ OpBranch %89 ; fallthrough
+
+ %80 = OpLabel ; default for both switches
+ OpBranch %89
+
+ %89 = OpLabel ; inner selection merge
+ OpBranch %99
+
+ %99 = OpLabel ; outer selection mege
+ 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 80 is declared as the default target for "
"two OpSwitch instructions, at blocks 10 and 50"));
}
@@ -5994,6 +6045,70 @@
"construct starting at block 50; branch bypasses merge block 80"));
}
+TEST_F(
+ SpvParserTest,
+ FindSwitchCaseHeaders_DomViolation_SwitchCase_CantBeMergeForOtherConstruct) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 20 %20 50 %50
+
+ %20 = OpLabel
+ OpSelectionMerge %50 None
+ OpBranchConditional %cond %30 %50
+
+ %30 = OpLabel
+ OpBranch %50
+
+ %50 = OpLabel ; case and merge block. Error
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowFindSwitchCaseHeaders(&fe));
+ EXPECT_THAT(p->error(),
+ Eq("Block 50 is a case block for switch-selection header 10 and "
+ "also the merge block for 20 (violates dominance rule)"));
+}
+
+TEST_F(
+ SpvParserTest,
+ ClassifyCFGEdges_DomViolation_SwitchDefault_CantBeMergeForOtherConstruct) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %50 20 %20
+
+ %20 = OpLabel
+ OpSelectionMerge %50 None
+ OpBranchConditional %cond %30 %50
+
+ %30 = OpLabel
+ OpBranch %50
+
+ %50 = OpLabel ; default-case and merge block. Error
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowFindSwitchCaseHeaders(&fe));
+ EXPECT_THAT(p->error(),
+ Eq("Block 50 is the default block for switch-selection header 10 "
+ "and also the merge block for 20 (violates dominance rule)"));
+}
+
TEST_F(SpvParserTest, ClassifyCFGEdges_TooManyBackedges) {
auto assembly = CommonTypes() + R"(
%100 = OpFunction %void None %voidfn
@@ -6653,6 +6768,96 @@
"a structured header (it has no merge instruction)"));
}
+TEST_F(SpvParserTest, FindIfSelectionInternalHeaders_DomViolation_Merge_CantBeTrueHeader) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %40 %20
+
+ %20 = OpLabel
+ OpSelectionMerge %40 None
+ OpBranchConditional %cond2 %30 %40
+
+ %30 = OpLabel
+ OpBranch %40
+
+ %40 = OpLabel ; inner merge, and true-head for outer if-selection
+ OpBranch %99
+
+ %99 = OpLabel ; outer merge
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowFindIfSelectionInternalHeaders(&fe));
+ EXPECT_THAT(p->error(), Eq("Block 40 is the true branch for if-selection header 10 and also the merge block for header block 20 (violates dominance rule)"));
+}
+
+TEST_F(SpvParserTest, FindIfSelectionInternalHeaders_DomViolation_Merge_CantBeFalseHeader) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %40
+
+ %20 = OpLabel
+ OpSelectionMerge %40 None
+ OpBranchConditional %cond %30 %40
+
+ %30 = OpLabel
+ OpBranch %40
+
+ %40 = OpLabel ; inner merge, and true-head for outer if-selection
+ OpBranch %99
+
+ %99 = OpLabel ; outer merge
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowFindIfSelectionInternalHeaders(&fe));
+ EXPECT_THAT(p->error(), Eq("Block 40 is the false branch for if-selection header 10 and also the merge block for header block 20 (violates dominance rule)"));
+}
+
+TEST_F(SpvParserTest, FindIfSelectionInternalHeaders_DomViolation_Merge_CantBePremerge) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel ; outer if-header
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %50
+
+ %20 = OpLabel
+ OpBranch %70
+
+ %50 = OpLabel ; inner if-header
+ OpSelectionMerge %70 None
+ OpBranchConditional %cond %60 %70
+
+ %60 = OpLabel
+ OpBranch %70
+
+ %70 = OpLabel ; inner merge, and premerge for outer if-selection
+ OpBranch %80
+
+ %80 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel ; outer merge
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowFindIfSelectionInternalHeaders(&fe));
+ EXPECT_THAT(p->error(), Eq("Block 70 is the merge block for 50 but has alternate paths reaching it, starting from blocks 20 and 50 which are the true and false branches for the if-selection header block 10 (violates dominance rule)"));
+}
+
TEST_F(SpvParserTest, DISABLED_Codegen_IfBreak_FromThen_ForwardWithinThen) {
// TODO(dneto): We can make this case work, if we injected
// if (!cond2) { rest-of-then-body }
