[spirv-reader] kIfBreak edge counts toward divergence
This fixes the pathological cases nobody wants, and arguably
should be added to the SPIR-V spec.
If we really really want to support these cases, we can revisit.
Bug: tint:3
Change-Id: I0a75490d451676caa0933e3761098ba1fe3f8b60
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/22664
Reviewed-by: dan sinclair <dsinclair@google.com>
diff --git a/src/reader/spirv/function.cc b/src/reader/spirv/function.cc
index d91c7e5..d326ead 100644
--- a/src/reader/spirv/function.cc
+++ b/src/reader/spirv/function.cc
@@ -1072,8 +1072,9 @@
// There should only be one backedge per backedge block.
uint32_t num_backedges = 0;
- // Track destinations for normal forward edges, either kForward
- // or kCaseFallThrough
+ // Track destinations for normal forward edges, either kForward,
+ // kCaseFallThrough, or kIfBreak. These count toward the need
+ // to have a merge instruction.
std::vector<uint32_t> normal_forward_edges;
if (successors.empty() && src_construct.enclosing_continue) {
@@ -1190,6 +1191,14 @@
}
}
+ // The edge-kind has been finalized.
+
+ if ((edge_kind == EdgeKind::kForward) ||
+ (edge_kind == EdgeKind::kCaseFallThrough) ||
+ (edge_kind == EdgeKind::kIfBreak)) {
+ normal_forward_edges.push_back(dest);
+ }
+
if ((edge_kind == EdgeKind::kForward) ||
(edge_kind == EdgeKind::kCaseFallThrough)) {
// Check for an invalid forward exit out of this construct.
@@ -1220,8 +1229,6 @@
<< end_block_desc << " " << end_block;
}
- normal_forward_edges.push_back(dest);
-
// Check dominance.
// Look for edges that violate the dominance condition: a branch
diff --git a/src/reader/spirv/function.h b/src/reader/spirv/function.h
index f37f23f..b98eedf 100644
--- a/src/reader/spirv/function.h
+++ b/src/reader/spirv/function.h
@@ -42,6 +42,19 @@
namespace spirv {
/// Kinds of CFG edges.
+//
+// The edge kinds are used in many ways.
+//
+// For example, consider the edges leaving a basic block and going to distinct
+// targets. If the total number of kForward + kIfBreak + kCaseFallThrough edges
+// is more than 1, then the block must be a structured header, i.e. it needs
+// a merge instruction to declare the control flow divergence and associated
+// reconvergence point. Those those edge kinds count toward divergence
+// because SPIR-v is designed to easily map back to structured control flow
+// in GLSL (and C). In GLSL and C, those forward-flow edges don't have a
+// special statement to express them. The other forward edges: kSwitchBreak,
+// kLoopBreak, and kLoopContinue directly map to 'break', 'break', and
+// 'continue', respectively.
enum class EdgeKind {
// A back-edge: An edge from a node to one of its ancestors in a depth-first
// search from the entry block.
@@ -64,10 +77,7 @@
kIfBreak,
// An edge from one switch case to the next sibling switch case.
kCaseFallThrough,
- // None of the above. By structured control flow rules, there can be at most
- // one forward edge leaving a basic block. Otherwise there must have been a
- // merge instruction declaring the divergence and associated reconvergence
- // point.
+ // None of the above.
kForward
};
diff --git a/src/reader/spirv/function_cfg_test.cc b/src/reader/spirv/function_cfg_test.cc
index 7dfcb60..9cc8304 100644
--- a/src/reader/spirv/function_cfg_test.cc
+++ b/src/reader/spirv/function_cfg_test.cc
@@ -6529,8 +6529,9 @@
"a structured header (it has no merge instruction)"));
}
-TEST_F(SpvParserTest,
- FindIfSelectionInternalHeaders_IfBreak_FromThen_ForwardWithinThen) {
+TEST_F(SpvParserTest, ClassifyCFGEdges_IfBreak_FromThen_ForwardWithinThen) {
+ // Arguably SPIR-V allows this configuration. We're debating whether to ban
+ // it.
// TODO(dneto): We can make this case work, if we injected
// if (!cond2) { rest-of-then-body }
// at block 30
@@ -6554,33 +6555,24 @@
auto* p = parser(test::Assemble(assembly));
ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
FunctionEmitter fe(p, *spirv_function(100));
- EXPECT_TRUE(FlowFindIfSelectionInternalHeaders(&fe));
+ EXPECT_FALSE(FlowClassifyCFGEdges(&fe));
EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 80, 99));
auto* bi20 = fe.GetBlockInfo(20);
ASSERT_NE(bi20, nullptr);
- ASSERT_NE(bi20->true_head_for, nullptr);
- EXPECT_EQ(bi20->true_head_for->begin_id, 10u);
- EXPECT_EQ(bi20->false_head_for, nullptr);
- EXPECT_EQ(bi20->premerge_head_for, nullptr);
- EXPECT_EQ(bi20->exclusive_false_head_for, nullptr);
EXPECT_EQ(bi20->succ_edge.count(80), 1u);
EXPECT_EQ(bi20->succ_edge[80], EdgeKind::kForward);
EXPECT_EQ(bi20->succ_edge.count(99), 1u);
EXPECT_EQ(bi20->succ_edge[99], EdgeKind::kIfBreak);
- auto* bi80 = fe.GetBlockInfo(80);
- ASSERT_NE(bi80, nullptr);
- EXPECT_EQ(bi80->true_head_for, nullptr);
- EXPECT_EQ(bi80->false_head_for, nullptr);
- EXPECT_EQ(bi80->premerge_head_for, nullptr);
- EXPECT_EQ(bi80->exclusive_false_head_for, nullptr);
- EXPECT_EQ(bi80->succ_edge.count(99), 1u);
- EXPECT_EQ(bi80->succ_edge[99], EdgeKind::kIfBreak);
+ EXPECT_THAT(p->error(),
+ Eq("Control flow diverges at block 20 (to 99, 80) but it is not "
+ "a structured header (it has no merge instruction)"));
}
-TEST_F(SpvParserTest,
- FindIfSelectionInternalHeaders_IfBreak_FromElse_ForwardWithinElse) {
+TEST_F(SpvParserTest, ClassifyCFGEdges_IfBreak_FromElse_ForwardWithinElse) {
+ // Arguably SPIR-V allows this configuration. We're debating whether to ban
+ // it.
// TODO(dneto): We can make this case work, if we injected
// if (!cond2) { rest-of-else-body }
// at block 30
@@ -6607,33 +6599,22 @@
auto* p = parser(test::Assemble(assembly));
ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
FunctionEmitter fe(p, *spirv_function(100));
- EXPECT_TRUE(FlowFindIfSelectionInternalHeaders(&fe));
+ EXPECT_FALSE(FlowClassifyCFGEdges(&fe));
EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 80, 99));
auto* bi30 = fe.GetBlockInfo(30);
ASSERT_NE(bi30, nullptr);
- EXPECT_EQ(bi30->true_head_for, nullptr);
- ASSERT_NE(bi30->false_head_for, nullptr);
- EXPECT_EQ(bi30->false_head_for->begin_id, 10u);
- EXPECT_EQ(bi30->premerge_head_for, nullptr);
- EXPECT_EQ(bi30->exclusive_false_head_for, nullptr);
EXPECT_EQ(bi30->succ_edge.count(80), 1u);
EXPECT_EQ(bi30->succ_edge[80], EdgeKind::kForward);
EXPECT_EQ(bi30->succ_edge.count(99), 1u);
EXPECT_EQ(bi30->succ_edge[99], EdgeKind::kIfBreak);
- auto* bi80 = fe.GetBlockInfo(80);
- ASSERT_NE(bi80, nullptr);
- EXPECT_EQ(bi80->true_head_for, nullptr);
- EXPECT_EQ(bi80->false_head_for, nullptr);
- EXPECT_EQ(bi80->premerge_head_for, nullptr);
- EXPECT_EQ(bi80->exclusive_false_head_for, nullptr);
- EXPECT_EQ(bi80->succ_edge.count(99), 1u);
- EXPECT_EQ(bi80->succ_edge[99], EdgeKind::kIfBreak);
+ EXPECT_THAT(p->error(),
+ Eq("Control flow diverges at block 30 (to 99, 80) but it is not "
+ "a structured header (it has no merge instruction)"));
}
-TEST_F(SpvParserTest,
- FindIfSelectionInternalHeaders_IfBreak_WithForwardToPremerge_IsError) {
+TEST_F(SpvParserTest, ClassifyCFGEdges_IfBreak_WithForwardToPremerge_IsError) {
auto assembly = CommonTypes() + R"(
%100 = OpFunction %void None %voidfn
@@ -6657,12 +6638,19 @@
auto* p = parser(test::Assemble(assembly));
ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
FunctionEmitter fe(p, *spirv_function(100));
- EXPECT_FALSE(FlowFindIfSelectionInternalHeaders(&fe));
+ EXPECT_FALSE(FlowClassifyCFGEdges(&fe));
EXPECT_THAT(fe.block_order(), ElementsAre(10, 20, 30, 80, 99));
- EXPECT_THAT(
- p->error(),
- Eq("Block 20 in if-selection headed at block 10 branches to both the "
- "merge block 99 and also to block 80 later in the selection"));
+
+ auto* bi20 = fe.GetBlockInfo(20);
+ ASSERT_NE(bi20, nullptr);
+ EXPECT_EQ(bi20->succ_edge.count(80), 1u);
+ EXPECT_EQ(bi20->succ_edge[80], EdgeKind::kForward);
+ EXPECT_EQ(bi20->succ_edge.count(99), 1u);
+ EXPECT_EQ(bi20->succ_edge[99], EdgeKind::kIfBreak);
+
+ EXPECT_THAT(p->error(),
+ Eq("Control flow diverges at block 20 (to 99, 80) but it is not "
+ "a structured header (it has no merge instruction)"));
}
TEST_F(SpvParserTest, DISABLED_Codegen_IfBreak_FromThen_ForwardWithinThen) {
