[spirv-reader] Classify CFG edges
Classify CFG edges:
- loop backedge
- a structured exit:
- loop break
- loop continue
- selection break
- fallthrough
- forward (any of the rest)
Also error out when there should have been a merge instruction.
(More than one unique fallthrough or forward edge).
Includes lots of tests.
Bug: tint:3
Change-Id: I70f27680bdf098213056522abf04ac58a6b478ab
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/20481
Reviewed-by: dan sinclair <dsinclair@google.com>
diff --git a/src/reader/spirv/function.cc b/src/reader/spirv/function.cc
index f728e10..7d23923 100644
--- a/src/reader/spirv/function.cc
+++ b/src/reader/spirv/function.cc
@@ -443,6 +443,11 @@
if (!FindSwitchCaseHeaders()) {
return false;
}
+ if (!ClassifyCFGEdges()) {
+ return false;
+ }
+ // TODO(dneto): FindIfSelectionHeaders
+ // TODO(dneto): FindInvalidNestingBetweenSelections
if (!EmitFunctionVariables()) {
return false;
@@ -915,6 +920,237 @@
return success();
}
+BlockInfo* FunctionEmitter::HeaderForLoopOrContinue(const Construct* c) {
+ if (c->kind == Construct::kLoop) {
+ return GetBlockInfo(c->begin_id);
+ }
+ if (c->kind == Construct::kContinue) {
+ auto* continue_block = GetBlockInfo(c->begin_id);
+ return GetBlockInfo(continue_block->header_for_continue);
+ }
+ return nullptr;
+}
+
+bool FunctionEmitter::ClassifyCFGEdges() {
+ if (failed()) {
+ return false;
+ }
+
+ // Checks validity of CFG edges leaving each basic block. This implicitly
+ // checks dominance rules for headers and continue constructs.
+ //
+ // For each branch encountered, classify each edge (S,T) as:
+ // - a back-edge
+ // - a structured exit (specific ways of branching to enclosing construct)
+ // - a normal (forward) edge
+ //
+ // If more than one block is targeted by a normal edge, then S must be a
+ // structured header.
+ //
+ // Term: NEC(B) is the nearest enclosing construct for B.
+ //
+ // If edge (S,T) is a normal edge, and NEC(S) != NEC(T), then
+ // T is the header block of its NEC(T), and
+ // NEC(S) is the parent of NEC(T).
+
+ for (const auto src : block_order_) {
+ assert(src > 0);
+ auto* src_info = GetBlockInfo(src);
+ assert(src_info);
+ const auto src_pos = src_info->pos;
+ const auto& src_construct = *(src_info->construct);
+
+ // Compute the ordered list of unique successors.
+ std::vector<uint32_t> successors;
+ {
+ std::unordered_set<uint32_t> visited;
+ src_info->basic_block->ForEachSuccessorLabel(
+ [&successors, &visited](const uint32_t succ) {
+ if (visited.count(succ) == 0) {
+ successors.push_back(succ);
+ visited.insert(succ);
+ }
+ });
+ }
+
+ // There should only be one backedge per backedge block.
+ uint32_t num_backedges = 0;
+
+ // Track destinations for normal forward edges.
+ std::vector<uint32_t> normal_forward_edges;
+
+ if (successors.empty() && src_construct.enclosing_continue) {
+ // Kill and return are not allowed in a continue construct.
+ return Fail() << "Invalid function exit at block " << src
+ << " from continue construct starting at "
+ << src_construct.enclosing_continue->begin_id;
+ }
+
+ for (const auto dest : successors) {
+ const auto* dest_info = GetBlockInfo(dest);
+ // We've already checked terminators are sane.
+ assert(dest_info);
+ const auto dest_pos = dest_info->pos;
+
+ // Insert the edge kind entry and keep a handle to update
+ // its classification.
+ EdgeKind& edge_kind = src_info->succ_edge[dest];
+
+ if (src_pos >= dest_pos) {
+ // This is a backedge.
+ edge_kind = EdgeKind::kBack;
+ num_backedges++;
+ const auto* continue_construct = src_construct.enclosing_continue;
+ if (!continue_construct) {
+ return Fail() << "Invalid backedge (" << src << "->" << dest
+ << "): " << src << " is not in a continue construct";
+ }
+ if (src_pos != continue_construct->end_pos - 1) {
+ return Fail() << "Invalid exit (" << src << "->" << dest
+ << ") from continue construct: " << src
+ << " is not the last block in the continue construct "
+ "starting at "
+ << src_construct.begin_id
+ << " (violates post-dominance rule)";
+ }
+ const auto* ct_info = GetBlockInfo(continue_construct->begin_id);
+ assert(ct_info);
+ if (ct_info->header_for_continue != dest) {
+ return Fail()
+ << "Invalid backedge (" << src << "->" << dest
+ << "): does not branch to the corresponding loop header, "
+ "expected "
+ << ct_info->header_for_continue;
+ }
+ } else {
+ // This is a forward edge.
+ // For now, classify it that way, but we might update it.
+ edge_kind = EdgeKind::kForward;
+
+ // Exit from a continue construct can only be from the last block.
+ const auto* continue_construct = src_construct.enclosing_continue;
+ if (continue_construct != nullptr) {
+ if (continue_construct->ContainsPos(src_pos) &&
+ !continue_construct->ContainsPos(dest_pos) &&
+ (src_pos != continue_construct->end_pos - 1)) {
+ return Fail() << "Invalid exit (" << src << "->" << dest
+ << ") from continue construct: " << src
+ << " is not the last block in the continue construct "
+ "starting at "
+ << continue_construct->begin_id
+ << " (violates post-dominance rule)";
+ }
+ }
+
+ // Check valid structured exit cases.
+
+ const auto& header_info = *GetBlockInfo(src_construct.begin_id);
+ if (dest == header_info.merge_for_header) {
+ // Branch to construct's merge block.
+ const bool src_is_loop_header = header_info.continue_for_header != 0;
+ const bool src_is_continue_header =
+ header_info.header_for_continue != 0;
+ edge_kind = (src_is_loop_header || src_is_continue_header)
+ ? EdgeKind::kLoopBreak
+ : EdgeKind::kToMerge;
+ } else {
+ const auto* loop_or_continue_construct =
+ src_construct.enclosing_loop_or_continue;
+ if (loop_or_continue_construct != nullptr) {
+ // Check for break block or continue block.
+ const auto* loop_header_info =
+ HeaderForLoopOrContinue(loop_or_continue_construct);
+ if (loop_header_info == nullptr) {
+ return Fail() << "internal error: invalid construction of loop "
+ "related to block "
+ << loop_or_continue_construct->begin_id;
+ }
+ if (dest == loop_header_info->merge_for_header) {
+ // It's a break block for the innermost loop.
+ edge_kind = EdgeKind::kLoopBreak;
+ } else if (dest == loop_header_info->continue_for_header) {
+ // It's a continue block for the innermost loop construct.
+ // In this case loop_or_continue_construct can't be a continue
+ // construct, because then the branch to the continue target is
+ // a backedge, and this code is only looking at forward edges.
+ edge_kind = EdgeKind::kLoopContinue;
+ }
+ }
+ }
+
+ // A forward edge into a case construct that comes from something
+ // other than the OpSwitch is actually a fallthrough.
+ if (edge_kind == EdgeKind::kForward) {
+ const auto* switch_construct =
+ (dest_info->case_head_for ? dest_info->case_head_for
+ : dest_info->default_head_for);
+ if (switch_construct != nullptr) {
+ if (src != switch_construct->begin_id) {
+ edge_kind = EdgeKind::kCaseFallThrough;
+ }
+ }
+ }
+
+ if ((edge_kind == EdgeKind::kForward) ||
+ (edge_kind == EdgeKind::kCaseFallThrough)) {
+ // Check for an invalid forward exit out of this construct.
+ if (dest_info->pos >= src_construct.end_pos) {
+ return Fail()
+ << "Branch from block " << src << " to block " << dest
+ << " is an invalid exit from construct starting at block "
+ << src_construct.begin_id << "; branch bypasses block "
+ << src_construct.end_id;
+ }
+
+ normal_forward_edges.push_back(dest);
+
+ // Check dominance.
+
+ // Look for edges that violate the dominance condition: a branch
+ // from X to Y where:
+ // If Y is in a nearest enclosing continue construct headed by
+ // CT:
+ // Y is not CT, and
+ // In the structured order, X appears before CT order or
+ // after CT's backedge block.
+ // Otherwise, if Y is in a nearest enclosing construct
+ // headed by H:
+ // Y is not H, and
+ // In the structured order, X appears before H or after H's
+ // merge block.
+
+ const auto& dest_construct = *(dest_info->construct);
+ if (dest != dest_construct.begin_id &&
+ !dest_construct.ContainsPos(src_pos)) {
+ return Fail() << "Branch from " << src << " to " << dest
+ << " bypasses "
+ << (dest_construct.kind == Construct::kContinue
+ ? "continue target "
+ : "header ")
+ << dest_construct.begin_id
+ << " (dominance rule violated)";
+ }
+ }
+ } // end forward edge
+ } // end successor
+
+ if (num_backedges > 1) {
+ return Fail() << "Block " << src
+ << " has too many backedges: " << num_backedges;
+ }
+ if ((normal_forward_edges.size() > 1) &&
+ (src_info->merge_for_header == 0)) {
+ return Fail() << "Control flow diverges at block " << src << " (to "
+ << normal_forward_edges[0] << ", "
+ << normal_forward_edges[1]
+ << ") but it is not a structured header (it has no merge "
+ "instruction)";
+ }
+ }
+
+ return success();
+}
+
bool FunctionEmitter::EmitFunctionVariables() {
if (failed()) {
return false;
diff --git a/src/reader/spirv/function.h b/src/reader/spirv/function.h
index e228b92..e5bf677 100644
--- a/src/reader/spirv/function.h
+++ b/src/reader/spirv/function.h
@@ -38,6 +38,31 @@
namespace reader {
namespace spirv {
+/// Kinds of CFG edges.
+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.
+ kBack,
+ // An edge from a node to the merge block of the nearest enclosing structured
+ // construct. We write "ToMerge" to make it clear the destination block is
+ // the merge block, not the source block.
+ kToMerge,
+ // An edge from a node to the merge block of the nearest enclosing loop.
+ // The source block is a "break block" as defined by SPIR-V.
+ kLoopBreak,
+ // An edge from a node in a loop body to the associated continue target, where
+ // there are no other intervening loops or switches.
+ // The source block is a "continue block" as defined by SPIR-V.
+ kLoopContinue,
+ // 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.
+ kForward
+};
+
/// Bookkeeping info for a basic block.
struct BlockInfo {
/// Constructor
@@ -87,6 +112,9 @@
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;
+
+ /// Maps the ID of a successor block (in the CFG) to its edge classification.
+ std::unordered_map<uint32_t, EdgeKind> succ_edge;
};
inline std::ostream& operator<<(std::ostream& o, const BlockInfo& bi) {
@@ -127,6 +155,9 @@
/// @returns a FailStream on which to emit diagnostics.
FailStream& Fail() { return fail_stream_.Fail(); }
+ /// @returns the parser implementation
+ ParserImpl* parser() { return &parser_impl_; }
+
/// Emits the declaration, which comprises the name, parameters, and
/// return type. The function AST node is appended to the module
/// AST node.
@@ -184,6 +215,14 @@
/// @returns false on failure
bool FindSwitchCaseHeaders();
+ /// Classifies the successor CFG edges for the ordered basic blocks.
+ /// Also checks validity of each edge (populates the |succ_edge| field of
+ /// BlockInfo). Implicitly checks dominance rules for headers and continue
+ /// constructs. Assumes each block has been labeled with its control flow
+ /// construct.
+ /// @returns false on failure
+ bool ClassifyCFGEdges();
+
/// Emits declarations of function variables.
/// @returns false if emission failed.
bool EmitFunctionVariables();
@@ -243,6 +282,13 @@
ast::type::Type* GetVariableStoreType(
const spvtools::opt::Instruction& var_decl_inst);
+ /// Finds the loop header block for a loop construct or continue construct.
+ /// The loop header block is the block with the corresponding OpLoopMerge
+ /// instruction.
+ /// @param c the loop or continue construct
+ /// @returns the block info for the loop header.
+ BlockInfo* HeaderForLoopOrContinue(const Construct* c);
+
ParserImpl& parser_impl_;
ast::Module& ast_module_;
spvtools::opt::IRContext& ir_context_;
diff --git a/src/reader/spirv/function_cfg_test.cc b/src/reader/spirv/function_cfg_test.cc
index 5805bbe..9430456 100644
--- a/src/reader/spirv/function_cfg_test.cc
+++ b/src/reader/spirv/function_cfg_test.cc
@@ -61,6 +61,18 @@
)";
}
+/// 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();
+ return fe->ClassifyCFGEdges();
+}
+
TEST_F(SpvParserTest, TerminatorsAreSane_SingleBlock) {
auto* p = parser(test::Assemble(CommonTypes() + R"(
%100 = OpFunction %void None %voidfn
@@ -4153,11 +4165,1640 @@
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.
+TEST_F(SpvParserTest, ClassifyCFGEdges_ReturnInContinueConstruct) {
+ 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 ; body
+ OpBranch %50
+
+ %50 = OpLabel
+ OpReturn
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowClassifyCFGEdges(&fe)) << p->error();
+ EXPECT_THAT(p->error(), Eq("Invalid function exit at block 50 from continue "
+ "construct starting at 50"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_KillInContinueConstruct) {
+ 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 ; body
+ OpBranch %50
+
+ %50 = OpLabel
+ OpKill
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(), Eq("Invalid function exit at block 50 from continue "
+ "construct starting at 50"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_UnreachableInContinueConstruct) {
+ 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 ; body
+ OpBranch %50
+
+ %50 = OpLabel
+ OpUnreachable
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(), Eq("Invalid function exit at block 50 from continue "
+ "construct starting at 50"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_BackEdge_NotInContinueConstruct) {
+ 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 ; body
+ OpBranch %20 ; bad backedge
+
+ %50 = OpLabel ; continue target
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(
+ p->error(),
+ Eq("Invalid backedge (30->20): 30 is not in a continue construct"));
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_BackEdge_NotInLastBlockOfContinueConstruct) {
+ 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 ; body
+ OpBranch %50
+
+ %50 = OpLabel ; continue target
+ OpBranchConditional %cond %20 %60 ; bad branch to %20
+
+ %60 = OpLabel ; end of continue construct
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(),
+ Eq("Invalid exit (50->20) from continue construct: 50 is not the "
+ "last block in the continue construct starting at 50 "
+ "(violates post-dominance rule)"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_BackEdge_ToWrongHeader) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %99
+
+ %20 = OpLabel
+ OpLoopMerge %89 %50 None
+ OpBranchConditional %cond %30 %89
+
+ %30 = OpLabel ; loop body
+ OpBranch %50
+
+ %50 = OpLabel ; continue target
+ OpBranch %10
+
+ %89 = OpLabel ; inner merge
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(), Eq("Invalid backedge (50->10): does not branch to "
+ "the corresponding loop header, expected 20"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_BackEdge_SingleBlockLoop) {
+ 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 ; outer merge
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi20 = fe.GetBlockInfo(20);
+ ASSERT_NE(bi20, nullptr);
+ EXPECT_EQ(bi20->succ_edge.count(20), 1);
+ EXPECT_EQ(bi20->succ_edge[20], EdgeKind::kBack);
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_BackEdge_MultiBlockLoop_SingleBlockContinueConstruct) {
+ auto assembly = 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 ; continue target
+ OpBranch %20 ; good back edge
+
+ %99 = OpLabel ; outer merge
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi40 = fe.GetBlockInfo(40);
+ ASSERT_NE(bi40, nullptr);
+ EXPECT_EQ(bi40->succ_edge.count(20), 1);
+ EXPECT_EQ(bi40->succ_edge[20], EdgeKind::kBack);
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_BackEdge_MultiBlockLoop_MultiBlockContinueConstruct) {
+ auto assembly = 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 ; continue target
+ OpBranch %50
+
+ %50 = OpLabel
+ OpBranch %20 ; good back edge
+
+ %99 = OpLabel ; outer merge
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi50 = fe.GetBlockInfo(50);
+ ASSERT_NE(bi50, nullptr);
+ EXPECT_EQ(bi50->succ_edge.count(20), 1);
+ EXPECT_EQ(bi50->succ_edge[20], EdgeKind::kBack);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_PrematureExitFromContinueConstruct) {
+ auto assembly = 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 ; continue construct
+ OpBranchConditional %cond2 %99 %50 ; invalid early exit
+
+ %50 = OpLabel
+ OpBranch %20 ; back edge
+
+ %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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(),
+ Eq("Invalid exit (40->99) from continue construct: 40 is not the "
+ "last block in the continue construct starting at 40 "
+ "(violates post-dominance rule)"));
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_LoopBreak_FromLoopHeader_SingleBlockLoop) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel ; single block loop
+ OpLoopMerge %99 %20 None
+ OpBranchConditional %cond %20 %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_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(20);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kLoopBreak);
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_LoopBreak_FromLoopHeader_MultiBlockLoop) {
+ 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
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(20);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kLoopBreak);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_LoopBreak_FromContinueConstructHeader) {
+ 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 ; Single block continue construct
+ OpBranchConditional %cond2 %20 %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(30);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kLoopBreak);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_ToMerge_FromIfHeader) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %99
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(20);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kToMerge);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_ToMerge_FromIfThenElse) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %50
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %50 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ // Then clause
+ auto* bi20 = fe.GetBlockInfo(20);
+ ASSERT_NE(bi20, nullptr);
+ EXPECT_EQ(bi20->succ_edge.count(99), 1);
+ EXPECT_EQ(bi20->succ_edge[99], EdgeKind::kToMerge);
+
+ // Else clause
+ auto* bi50 = fe.GetBlockInfo(50);
+ ASSERT_NE(bi50, nullptr);
+ EXPECT_EQ(bi50->succ_edge.count(99), 1);
+ EXPECT_EQ(bi50->succ_edge[99], EdgeKind::kToMerge);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_ToMerge_FromSwitchCaseDirect) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %30 20 %99 ; directly to merge
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(10);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kToMerge);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_ToMerge_FromSwitchCaseBody) {
+ 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
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(20);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kToMerge);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_ToMerge_FromSwitchDefaultBody) {
+ 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
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(30);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kToMerge);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_ToMerge_FromSwitchDefaultIsMerge) {
+ 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
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(10);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kToMerge);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_LoopBreak_FromLoopBody) {
+ 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 %99 ; break-unless
+
+ %50 = OpLabel
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(30);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kLoopBreak);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_LoopBreak_FromContinueConstructTail) {
+ 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 ; continue target
+ OpBranch %60
+
+ %60 = OpLabel ; continue construct tail
+ OpBranchConditional %cond2 %20 %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(60);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kLoopBreak);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_LoopBreak_FromLoopBodyDirect) {
+ 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 ; unconditional break
+
+ %50 = OpLabel
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(30);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(99), 1);
+ EXPECT_EQ(bi->succ_edge[99], EdgeKind::kLoopBreak);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_LoopContinue_LoopBodyToContinue) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel
+ OpBranch %80 ; a forward edge
+
+ %80 = OpLabel
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(30);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(80), 1);
+ EXPECT_EQ(bi->succ_edge[80], EdgeKind::kLoopContinue);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_LoopContinue_FromNestedIf) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel
+ OpSelectionMerge %79 None
+ OpBranchConditional %cond2 %40 %79
+
+ %40 = OpLabel
+ OpBranch %80 ; continue
+
+ %79 = OpLabel ; inner merge
+ OpBranch %80
+
+ %80 = OpLabel ; continue target
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(40);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(80), 1);
+ EXPECT_EQ(bi->succ_edge[80], EdgeKind::kLoopContinue);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_LoopContinue_ConditionalFromNestedIf) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel
+ OpSelectionMerge %79 None
+ OpBranchConditional %cond2 %40 %79
+
+ %40 = OpLabel
+ OpBranchConditional %cond2 %80 %79 ; continue-if
+
+ %79 = OpLabel ; inner merge
+ OpBranch %80
+
+ %80 = OpLabel ; continue target
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(40);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(80), 1);
+ EXPECT_EQ(bi->succ_edge[80], EdgeKind::kLoopContinue);
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_LoopContinue_FromNestedSwitchCaseBody_Unconditional) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel
+ OpSelectionMerge %79 None
+ OpSwitch %selector %79 40 %40
+
+ %40 = OpLabel
+ OpBranch %80
+
+ %79 = OpLabel ; inner merge
+ OpBranch %80
+
+ %80 = OpLabel ; continue target
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(40);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(80), 1);
+ EXPECT_EQ(bi->succ_edge[80], EdgeKind::kLoopContinue);
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_LoopContinue_FromNestedSwitchCaseDirect_Error) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel
+ OpSelectionMerge %79 None
+ OpSwitch %selector %79 40 %80 ; continue here
+
+ %79 = OpLabel ; inner merge
+ OpBranch %80
+
+ %80 = OpLabel ; continue target
+ OpBranch %20
+
+ %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());
+ EXPECT_TRUE(fe.RegisterMerges());
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ EXPECT_THAT(p->error(), Eq("Switch branch from block 30 to case target block "
+ "80 escapes the selection construct"));
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_LoopContinue_FromNestedSwitchDefaultDirect_Error) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel
+ OpSelectionMerge %79 None
+ OpSwitch %selector %80 40 %79 ; continue here
+
+ %79 = OpLabel ; inner merge
+ OpBranch %80
+
+ %80 = OpLabel ; continue target
+ OpBranch %20
+
+ %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());
+ EXPECT_TRUE(fe.RegisterMerges());
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ EXPECT_FALSE(fe.FindSwitchCaseHeaders());
+ EXPECT_THAT(p->error(), Eq("Switch branch from block 30 to default block 80 "
+ "escapes the selection construct"));
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_LoopContinue_FromNestedSwitchDefaultBody_Conditional) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel
+ OpSelectionMerge %79 None
+ OpSwitch %selector %40 79 %79
+
+ %40 = OpLabel
+ OpBranchConditional %cond2 %80 %79
+
+ %79 = OpLabel ; inner merge
+ OpBranch %80
+
+ %80 = OpLabel ; continue target
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(40);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(80), 1);
+ EXPECT_EQ(bi->succ_edge[80], EdgeKind::kLoopContinue);
+}
+
+TEST_F(
+ SpvParserTest,
+ ClassifyCFGEdges_LoopContinue_FromNestedSwitchDefaultBody_Unconditional) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel
+ OpSelectionMerge %79 None
+ OpSwitch %selector %40 79 %79
+
+ %40 = OpLabel
+ OpBranch %80
+
+ %79 = OpLabel ; inner merge
+ OpBranch %80
+
+ %80 = OpLabel ; continue target
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(40);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(80), 1);
+ EXPECT_EQ(bi->succ_edge[80], EdgeKind::kLoopContinue);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Fallthrough_CaseTailToCase) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 20 %20 40 %40
+
+ %20 = OpLabel ; case 20
+ OpBranch %30
+
+ %30 = OpLabel
+ OpBranch %40 ; fallthrough
+
+ %40 = OpLabel ; case 40
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(30);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(40), 1);
+ EXPECT_EQ(bi->succ_edge[40], EdgeKind::kCaseFallThrough);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Fallthrough_CaseTailToDefaultNotMerge) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %40 20 %20
+
+ %20 = OpLabel ; case 20
+ OpBranch %30
+
+ %30 = OpLabel
+ OpBranch %40 ; fallthrough
+
+ %40 = OpLabel ; case 40
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(30);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(40), 1);
+ EXPECT_EQ(bi->succ_edge[40], EdgeKind::kCaseFallThrough);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Fallthrough_DefaultToCase) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %20 40 %40
+
+ %20 = OpLabel ; default
+ OpBranch %30
+
+ %30 = OpLabel
+ OpBranch %40 ; fallthrough
+
+ %40 = OpLabel ; case 40
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(30);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(40), 1);
+ EXPECT_EQ(bi->succ_edge[40], EdgeKind::kCaseFallThrough);
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_Fallthrough_CaseNonTailToCase_TrueBranch) {
+ // This is an unusual one, and is an error. Structurally it looks like this:
+ // switch (val) {
+ // case 0: {
+ // if (cond) {
+ // fallthrough;
+ // }
+ // something = 1;
+ // }
+ // case 1: { }
+ // }
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 20 %20 50 %50
+
+ %20 = OpLabel
+ OpSelectionMerge %49 None
+ OpBranchConditional %cond %30 %49
+
+ %30 = OpLabel
+ OpBranch %50 ; attempt to fallthrough
+
+ %49 = OpLabel
+ OpBranch %99
+
+ %50 = OpLabel
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(
+ p->error(),
+ Eq("Branch from 10 to 50 bypasses header 20 (dominance rule violated)"));
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_Fallthrough_CaseNonTailToCase_FalseBranch) {
+ // Like previous test, but taking the false branch.
+
+ // This is an unusual one, and is an error. Structurally it looks like this:
+ // switch (val) {
+ // case 0: {
+ // if (cond) {
+ // fallthrough;
+ // }
+ // something = 1;
+ // }
+ // case 1: { }
+ // }
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 20 %20 50 %50
+
+ %20 = OpLabel
+ OpSelectionMerge %49 None
+ OpBranchConditional %cond %49 %30 ;; this is the difference
+
+ %30 = OpLabel
+ OpBranch %50 ; attempt to fallthrough
+
+ %49 = OpLabel
+ OpBranch %99
+
+ %50 = OpLabel
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(
+ p->error(),
+ Eq("Branch from 10 to 50 bypasses header 20 (dominance rule violated)"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Forward_IfToThen) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %99
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(10);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(20), 1);
+ EXPECT_EQ(bi->succ_edge[20], EdgeKind::kForward);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Forward_IfToElse) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %99 %30
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(10);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(30), 1);
+ EXPECT_EQ(bi->succ_edge[30], EdgeKind::kForward);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Forward_SwitchToCase) {
+ 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
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(10);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(20), 1);
+ EXPECT_EQ(bi->succ_edge[20], EdgeKind::kForward);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Forward_SwitchToDefaultNotMerge) {
+ 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
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(10);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(30), 1);
+ EXPECT_EQ(bi->succ_edge[30], EdgeKind::kForward);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Forward_LoopHeadToBody) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel
+ OpBranch %80
+
+ %80 = OpLabel
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(20);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(30), 1);
+ EXPECT_EQ(bi->succ_edge[30], EdgeKind::kForward);
+}
+
+TEST_F(SpvParserTest, DISABLED_ClassifyCFGEdges_Forward_LoopToContinue) {
+ FAIL();
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_DomViolation_BeforeIfToSelectionInterior) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %50 ;%50 is a bad branch
+
+ %20 = OpLabel
+ OpSelectionMerge %89 None
+ OpBranchConditional %cond %50 %89
+
+ %50 = OpLabel
+ OpBranch %89
+
+ %89 = OpLabel
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(
+ p->error(),
+ Eq("Branch from 10 to 50 bypasses header 20 (dominance rule violated)"));
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_DomViolation_BeforeSwitchToSelectionInterior) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %50 ;%50 is a bad branch
+
+ %20 = OpLabel
+ OpSelectionMerge %89 None
+ OpSwitch %selector %89 50 %50
+
+ %50 = OpLabel
+ OpBranch %89
+
+ %89 = OpLabel
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(
+ p->error(),
+ Eq("Branch from 10 to 50 bypasses header 20 (dominance rule violated)"));
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_DomViolation_BeforeLoopToLoopBodyInterior) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %50 ;%50 is a bad branch
+
+ %20 = OpLabel
+ OpLoopMerge %89 %80 None
+ OpBranchConditional %cond %50 %89
+
+ %50 = OpLabel
+ OpBranch %89
+
+ %80 = OpLabel
+ OpBranch %20
+
+ %89 = OpLabel
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(),
+ // Weird error, but still we caught it.
+ // Preferred: Eq("Branch from 10 to 50 bypasses header 20
+ // (dominance rule violated)"))
+ Eq("Branch from 10 to 50 bypasses continue target 80 (dominance "
+ "rule violated)"))
+ << Dump(fe.block_order());
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_DomViolation_BeforeContinueToContinueInterior) {
+ 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 %60
+
+ %50 = OpLabel
+ OpBranch %60
+
+ %60 = OpLabel
+ OpBranch %20
+
+ %89 = OpLabel
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(),
+ Eq("Branch from block 30 to block 60 is an invalid exit from "
+ "construct starting at block 20; branch bypasses block 50"));
+}
+
+TEST_F(SpvParserTest,
+ ClassifyCFGEdges_DomViolation_AfterContinueToContinueInterior) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %80 %50 None
+ OpBranchConditional %cond %30 %80
+
+ %30 = OpLabel
+ OpBranch %50
+
+ %50 = OpLabel
+ OpBranch %60
+
+ %60 = OpLabel
+ OpBranch %20
+
+ %80 = OpLabel
+ OpBranch %60 ; bad branch
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(),
+ Eq("Branch from block 50 to block 60 is an invalid exit from "
+ "construct starting at block 50; branch bypasses block 80"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_TooManyBackedges) {
+ 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 %20 %50
+
+ %50 = OpLabel
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_FALSE(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(
+ p->error(),
+ Eq("Invalid backedge (30->20): 30 is not in a continue construct"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_NeededMerge_BranchConditional) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %20 = OpLabel
+ OpBranchConditional %cond %30 %40
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %40 = OpLabel
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(),
+ Eq("Control flow diverges at block 20 (to 30, 40) but it is not "
+ "a structured header (it has no merge instruction)"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_NeededMerge_Switch) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSwitch %selector %99 20 %20 30 %30
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %30 = OpLabel
+ 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(FlowClassifyCFGEdges(&fe));
+ EXPECT_THAT(p->error(),
+ Eq("Control flow diverges at block 10 (to 99, 20) but it is not "
+ "a structured header (it has no merge instruction)"));
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Pathological_Forward_LoopHeadSplitBody) {
+ // In this case the branch-conditional in the loop header is really also a
+ // selection header.
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %99 %80 None
+ OpBranchConditional %cond %30 %50 ; what to make of this?
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %50 = OpLabel
+ OpBranch %99
+
+ %80 = OpLabel
+ OpBranch %20
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi = fe.GetBlockInfo(20);
+ ASSERT_NE(bi, nullptr);
+ EXPECT_EQ(bi->succ_edge.count(30), 1);
+ EXPECT_EQ(bi->succ_edge[30], EdgeKind::kForward);
+ EXPECT_EQ(bi->succ_edge.count(50), 1);
+ EXPECT_EQ(bi->succ_edge[50], EdgeKind::kForward);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Pathological_Forward_Premerge) {
+ // Two arms of an if-selection converge early, before the merge block
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %30
+
+ %20 = OpLabel
+ OpBranch %50
+
+ %30 = OpLabel
+ OpBranch %50
+
+ %50 = OpLabel ; this is an early merge!
+ OpBranch %60
+
+ %60 = OpLabel ; still early merge
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi20 = fe.GetBlockInfo(20);
+ ASSERT_NE(bi20, nullptr);
+ EXPECT_EQ(bi20->succ_edge.count(50), 1);
+ EXPECT_EQ(bi20->succ_edge[50], EdgeKind::kForward);
+
+ auto* bi30 = fe.GetBlockInfo(30);
+ ASSERT_NE(bi30, nullptr);
+ EXPECT_EQ(bi30->succ_edge.count(50), 1);
+ EXPECT_EQ(bi30->succ_edge[50], EdgeKind::kForward);
+
+ auto* bi50 = fe.GetBlockInfo(50);
+ ASSERT_NE(bi50, nullptr);
+ EXPECT_EQ(bi50->succ_edge.count(60), 1);
+ EXPECT_EQ(bi50->succ_edge[60], EdgeKind::kForward);
+
+ auto* bi60 = fe.GetBlockInfo(60);
+ ASSERT_NE(bi60, nullptr);
+ EXPECT_EQ(bi60->succ_edge.count(99), 1);
+ EXPECT_EQ(bi60->succ_edge[99], EdgeKind::kToMerge);
+}
+
+TEST_F(SpvParserTest, ClassifyCFGEdges_Pathological_Forward_Regardless) {
+ // Both arms of an OpBranchConditional go to the same target.
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %20 ; same target!
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ EXPECT_TRUE(FlowClassifyCFGEdges(&fe));
+
+ auto* bi10 = fe.GetBlockInfo(10);
+ ASSERT_NE(bi10, nullptr);
+ EXPECT_EQ(bi10->succ_edge.count(20), 1);
+ EXPECT_EQ(bi10->succ_edge[20], EdgeKind::kForward);
+
+ auto* bi20 = fe.GetBlockInfo(20);
+ ASSERT_NE(bi20, nullptr);
+ EXPECT_EQ(bi20->succ_edge.count(99), 1);
+ EXPECT_EQ(bi20->succ_edge[99], EdgeKind::kToMerge);
+}
} // namespace
} // namespace spirv
