[spirv-reader] Label control flow constructs
Label basic blocks with:
- their nearest enclosing structured control flow constructs.
- their nearest enclosing continue construct, if any
- their nearest enclosing loop construct, if any
A construct consists of a span of blocks in the computed block order.
It knows its parent construct, if any, and its nesting depth.
Bug: tint:3
Change-Id: Ia945706e8ea2435d6c40fb4e36dc2daeeb9780d0
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/20421
Reviewed-by: dan sinclair <dsinclair@google.com>
diff --git a/BUILD.gn b/BUILD.gn
index 5ee239f..2307476 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -377,6 +377,8 @@
source_set("libtint_spv_reader_src") {
sources = [
+ "src/reader/spirv/construct.h",
+ "src/reader/spirv/construct.cc",
"src/reader/spirv/enum_converter.cc",
"src/reader/spirv/enum_converter.h",
"src/reader/spirv/fail_stream.h",
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index b53a9fb..a47d829 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -199,6 +199,8 @@
if(${TINT_BUILD_SPV_READER})
list(APPEND TINT_LIB_SRCS
+ reader/spirv/construct.h
+ reader/spirv/construct.cc
reader/spirv/enum_converter.h
reader/spirv/enum_converter.cc
reader/spirv/fail_stream.h
diff --git a/src/reader/spirv/construct.cc b/src/reader/spirv/construct.cc
new file mode 100644
index 0000000..b1ef7de
--- /dev/null
+++ b/src/reader/spirv/construct.cc
@@ -0,0 +1,50 @@
+// Copyright 2020 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "src/reader/spirv/construct.h"
+
+namespace tint {
+namespace reader {
+namespace spirv {
+
+Construct::Construct(const Construct* the_parent,
+ int the_depth,
+ Kind the_kind,
+ uint32_t the_begin_id,
+ uint32_t the_end_id,
+ uint32_t the_begin_pos,
+ uint32_t the_end_pos)
+ : parent(the_parent),
+ enclosing_continue(
+ // Compute the enclosing continue construct. Doing this in the
+ // constructor member list lets us make the member const.
+ the_kind == kContinue
+ ? this
+ : (parent ? parent->enclosing_continue : nullptr)),
+ enclosing_loop_or_continue(
+ // Compute the enclosing loop or continue construct. Doing this
+ // in the constructor member list lets us make the member const.
+ (the_kind == kLoop || the_kind == kContinue)
+ ? this
+ : (parent ? parent->enclosing_loop_or_continue : nullptr)),
+ depth(the_depth),
+ kind(the_kind),
+ begin_id(the_begin_id),
+ end_id(the_end_id),
+ begin_pos(the_begin_pos),
+ end_pos(the_end_pos) {}
+
+} // namespace spirv
+} // namespace reader
+} // namespace tint
diff --git a/src/reader/spirv/construct.h b/src/reader/spirv/construct.h
new file mode 100644
index 0000000..f458868
--- /dev/null
+++ b/src/reader/spirv/construct.h
@@ -0,0 +1,194 @@
+// Copyright 2020 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SRC_READER_SPIRV_CONSTRUCT_H_
+#define SRC_READER_SPIRV_CONSTRUCT_H_
+
+#include <cstdint>
+#include <memory>
+#include <ostream>
+#include <sstream>
+#include <vector>
+
+namespace tint {
+namespace reader {
+namespace spirv {
+
+/// A structured construct, consisting of a set of basic blocks.
+/// A construct is a span of blocks in the computed block order,
+/// and will appear contiguously in the WGSL source.
+struct Construct {
+ /// Enumeration for the kinds of structured constructs.
+ enum Kind {
+ kFunction, // The whole function.
+ kSelection, // A SPIR-V selection construct
+ kLoop, // A SPIR-V loop construct
+ kContinue, // A SPIR-V continue construct
+ };
+
+ /// Constructor
+ /// @param the_parent parent construct
+ /// @param the_depth construct nesting depth
+ /// @param the_kind construct kind
+ /// @param the_begin_id block id of the first block in the construct
+ /// @param the_end_id block id of the first block after the construct, or 0
+ /// @param the_begin_pos block order position of the_begin_id
+ /// @param the_end_pos block order position of the_end_id or a too-large value
+ Construct(const Construct* the_parent,
+ int the_depth,
+ Kind the_kind,
+ uint32_t the_begin_id,
+ uint32_t the_end_id,
+ uint32_t the_begin_pos,
+ uint32_t the_end_pos);
+
+ /// @param pos a block position
+ /// @returns true if the given block position is inside this construct.
+ bool ContainsPos(uint32_t pos) const {
+ return begin_pos <= pos && pos < end_pos;
+ }
+
+ /// The nearest enclosing construct (other than itself), or nullptr if
+ /// this construct represents the entire function.
+ const Construct* const parent = nullptr;
+ /// The nearest continue construct, if one exists. A construct encloses
+ /// itself.
+ const Construct* const enclosing_continue = nullptr;
+ /// The nearest enclosing loop or continue construct, if one exists.
+ /// A construct encloses itself.
+ const Construct* const enclosing_loop_or_continue = nullptr;
+
+ /// Control flow nesting depth. The entry block is at nesting depth 0.
+ const int depth = 0;
+ /// The construct kind
+ const Kind kind = kFunction;
+ /// The id of the first block in this structure.
+ const uint32_t begin_id = 0;
+ /// 0 for kFunction, or the id of the block immediately after this construct
+ /// in the computed block order.
+ const uint32_t end_id = 0;
+ /// The position of block |begin_id| in the computed block order.
+ const uint32_t begin_pos = 0;
+ /// The position of block |end_id| in the block order, or the number of
+ /// block order elements if |end_id| is 0.
+ const uint32_t end_pos = 0;
+};
+
+using ConstructList = std::vector<std::unique_ptr<Construct>>;
+
+/// Converts a construct kind to a string.
+/// @param kind the construct kind to convert
+/// @returns the string representation
+inline std::string ToString(Construct::Kind kind) {
+ switch (kind) {
+ case Construct::kFunction:
+ return "Function";
+ case Construct::kSelection:
+ return "Selection";
+ case Construct::kLoop:
+ return "Loop";
+ case Construct::kContinue:
+ return "Continue";
+ }
+ return "NONE";
+}
+
+/// Converts a construct into a short summary string.
+/// @param c the construct, which can be null
+/// @returns a short summary string
+inline std::string ToStringBrief(const Construct* c) {
+ if (c) {
+ std::stringstream ss;
+ ss << ToString(c->kind) << "@" << c->begin_id;
+ return ss.str();
+ }
+ return "null";
+}
+
+/// Emits a construct to a stream.
+/// @param o the stream
+/// @param c the structured construct
+/// @returns the stream
+inline std::ostream& operator<<(std::ostream& o, const Construct& c) {
+ o << "Construct{ " << ToString(c.kind) << " [" << c.begin_pos << ","
+ << c.end_pos << ")"
+ << " begin_id:" << c.begin_id << " end_id:" << c.end_id
+ << " depth:" << c.depth;
+
+ o << " parent:" << ToStringBrief(c.parent);
+
+ if (c.enclosing_continue) {
+ o << " in-c:" << ToStringBrief(c.enclosing_continue);
+ }
+
+ if (c.enclosing_loop_or_continue != c.enclosing_continue) {
+ o << " in-c-l:" << ToStringBrief(c.enclosing_loop_or_continue);
+ }
+
+ o << " }";
+ return o;
+}
+
+/// Emits a construct to a stream.
+/// @param o the stream
+/// @param c the structured construct
+/// @returns the stream
+inline std::ostream& operator<<(std::ostream& o,
+ const std::unique_ptr<Construct>& c) {
+ return o << *(c.get());
+}
+
+/// Converts a construct to a string.
+/// @param c the construct
+/// @returns the string representation
+inline std::string ToString(const Construct& c) {
+ std::stringstream ss;
+ ss << c;
+ return ss.str();
+}
+
+/// Converts a unique pointer to a construct to a string.
+/// @param c the construct
+/// @returns the string representation
+inline std::string ToString(const std::unique_ptr<Construct>& c) {
+ return ToString(*(c.get()));
+}
+
+/// Emits a construct list to a stream.
+/// @param o the stream
+/// @param cl the construct list
+/// @returns the stream
+inline std::ostream& operator<<(std::ostream& o, const ConstructList& cl) {
+ o << "ConstructList{\n";
+ for (const auto& c : cl) {
+ o << " " << c << "\n";
+ }
+ o << "}";
+ return o;
+}
+
+/// Converts a construct list to a string.
+/// @param cl the construct list
+/// @returns the string representation
+inline std::string ToString(const ConstructList& cl) {
+ std::stringstream ss;
+ ss << cl;
+ return ss.str();
+}
+
+} // namespace spirv
+} // namespace reader
+} // namespace tint
+
+#endif // SRC_READER_SPIRV_CONSTRUCT_H_
diff --git a/src/reader/spirv/function.cc b/src/reader/spirv/function.cc
index 27f4b20..86fc03a 100644
--- a/src/reader/spirv/function.cc
+++ b/src/reader/spirv/function.cc
@@ -437,6 +437,9 @@
if (!VerifyHeaderContinueMergeOrder()) {
return false;
}
+ if (!LabelControlFlowConstructs()) {
+ return false;
+ }
if (!EmitFunctionVariables()) {
return false;
@@ -660,6 +663,149 @@
return success();
}
+bool FunctionEmitter::LabelControlFlowConstructs() {
+ // Label each block in the block order with its nearest enclosing structured
+ // control flow construct. Populates the |construct| member of BlockInfo.
+
+ // Keep a stack of enclosing structured control flow constructs. Start
+ // with the synthetic construct representing the entire function.
+ //
+ // Scan from left to right in the block order, and check conditions
+ // on each block in the following order:
+ //
+ // a. When you reach a merge block, the top of the stack should
+ // be the associated header. Pop it off.
+ // b. When you reach a header, push it on the stack.
+ // c. When you reach a continue target, push it on the stack.
+ // (A block can be both a header and a continue target, in the case
+ // of a single-block loop, in which case it should also be its
+ // own backedge block.)
+ // c. When you reach a block with an edge branching backward (in the
+ // structured order) to block T:
+ // T should be a loop header, and the top of the stack should be a
+ // continue target associated with T.
+ // This is the end of the continue construct. Pop the continue
+ // target off the stack.
+ // (Note: We pop the merge off first because a merge block that marks
+ // the end of one construct can be a single-block loop. So that block
+ // is a merge, a header, a continue target, and a backedge block.
+ // But we want to finish processing of the merge before dealing with
+ // the loop.)
+ //
+ // In the same scan, mark each basic block with the nearest enclosing
+ // header: the most recent header for which we haven't reached its merge
+ // block. Also mark the the most recent continue target for which we
+ // haven't reached the backedge block.
+
+ assert(block_order_.size() > 0);
+ constructs_.clear();
+ const auto entry_id = block_order_[0];
+
+ // The stack of enclosing constructs.
+ std::vector<Construct*> enclosing;
+
+ // Creates a control flow construct and pushes it onto the stack.
+ // Its parent is the top of the stack, or nullptr if the stack is empty.
+ // Returns the newly created construct.
+ auto push_construct = [this, &enclosing](size_t depth, Construct::Kind k,
+ uint32_t begin_id,
+ uint32_t end_id) -> Construct* {
+ const auto begin_pos = GetBlockInfo(begin_id)->pos;
+ const auto end_pos =
+ end_id == 0 ? uint32_t(block_order_.size()) : GetBlockInfo(end_id)->pos;
+ const auto* parent = enclosing.empty() ? nullptr : enclosing.back();
+ // A loop construct is added right after its associated continue construct.
+ // In that case, adjust the parent up.
+ if (k == Construct::kLoop) {
+ assert(parent);
+ assert(parent->kind == Construct::kContinue);
+ parent = parent->parent;
+ }
+ constructs_.push_back(std::make_unique<Construct>(
+ parent, int(depth), k, begin_id, end_id, begin_pos, end_pos));
+ Construct* result = constructs_.back().get();
+ enclosing.push_back(result);
+ return result;
+ };
+
+ // Make a synthetic kFunction construct to enclose all blocks in the function.
+ push_construct(0, Construct::kFunction, entry_id, 0);
+ // The entry block can be a selection construct, so be sure to process
+ // it anyway.
+
+ for (uint32_t i = 0; i < block_order_.size(); ++i) {
+ const auto block_id = block_order_[i];
+ assert(block_id > 0);
+ auto* block_info = GetBlockInfo(block_id);
+ assert(block_info);
+
+ if (enclosing.empty()) {
+ return Fail() << "internal error: too many merge blocks before block "
+ << block_id;
+ }
+ const Construct* top = enclosing.back();
+
+ while (block_id == top->end_id) {
+ // We've reached a predeclared end of the construct. Pop it off the
+ // stack.
+ enclosing.pop_back();
+ if (enclosing.empty()) {
+ return Fail() << "internal error: too many merge blocks before block "
+ << block_id;
+ }
+ top = enclosing.back();
+ }
+
+ const auto merge = block_info->merge_for_header;
+ if (merge != 0) {
+ // The current block is a header.
+ const auto header = block_id;
+ const auto* header_info = block_info;
+ const auto depth = 1 + top->depth;
+ const auto ct = header_info->continue_for_header;
+ if (ct != 0) {
+ // The current block is a loop header.
+ // We should see the continue construct after the loop construct, so
+ // push the loop construct last.
+
+ // From the interval rule, the continue construct consists of blocks
+ // in the block order, starting at the continue target, until just
+ // before the merge block.
+ top = push_construct(depth, Construct::kContinue, ct, merge);
+ // A single block loop has an empty loop construct.
+ if (!header_info->is_single_block_loop) {
+ // From the interval rule, the loop construct consists of blocks
+ // in the block order, starting at the header, until just
+ // before the continue target.
+ top = push_construct(depth, Construct::kLoop, header, ct);
+ }
+ } else {
+ // From the interval rule, the selection construct consists of blocks
+ // in the block order, starting at the header, until just before the
+ // merge block.
+ top = push_construct(depth, Construct::kSelection, header, merge);
+ }
+ }
+
+ assert(top);
+ block_info->construct = top;
+ }
+
+ // At the end of the block list, we should only have the kFunction construct
+ // left.
+ if (enclosing.size() != 1) {
+ return Fail() << "internal error: unbalanced structured constructs when "
+ "labeling structured constructs: ended with "
+ << enclosing.size() - 1 << " unterminated constructs";
+ }
+ const auto* top = enclosing[0];
+ if (top->kind != Construct::kFunction || top->depth != 0) {
+ return Fail() << "internal error: outermost construct is not a function?!";
+ }
+
+ return success();
+}
+
bool FunctionEmitter::EmitFunctionVariables() {
if (failed()) {
return false;
diff --git a/src/reader/spirv/function.h b/src/reader/spirv/function.h
index 349a30b..e554aa3 100644
--- a/src/reader/spirv/function.h
+++ b/src/reader/spirv/function.h
@@ -29,6 +29,7 @@
#include "source/opt/type_manager.h"
#include "src/ast/expression.h"
#include "src/ast/module.h"
+#include "src/reader/spirv/construct.h"
#include "src/reader/spirv/fail_stream.h"
#include "src/reader/spirv/namer.h"
#include "src/reader/spirv/parser_impl.h"
@@ -66,6 +67,9 @@
/// Is this block a single-block loop: A loop header that declares itself
/// as its own continue target, and has branch to itself.
bool is_single_block_loop = false;
+
+ /// The immediately enclosing structured construct.
+ const Construct* construct = nullptr;
};
inline std::ostream& operator<<(std::ostream& o, const BlockInfo& bi) {
@@ -147,6 +151,17 @@
/// @returns false if invalid nesting was detected
bool VerifyHeaderContinueMergeOrder();
+ /// Labels each basic block with its nearest enclosing structured construct.
+ /// Populates the |construct| member of BlockInfo, and the |constructs_| list.
+ /// Assumes terminators are sane and merges have been registered, block
+ /// order has been computed, and each block is labeled with its position.
+ /// Checks nesting of structured control flow constructs.
+ /// @returns false if bad nesting has been detected
+ bool LabelControlFlowConstructs();
+
+ /// @returns the structured constructs
+ const ConstructList& constructs() const { return constructs_; }
+
/// Emits declarations of function variables.
/// @returns false if emission failed.
bool EmitFunctionVariables();
@@ -227,6 +242,9 @@
// Mapping from block ID to its bookkeeping info.
std::unordered_map<uint32_t, std::unique_ptr<BlockInfo>> block_info_;
+
+ // Structured constructs, where enclosing constructs precede their children.
+ ConstructList constructs_;
};
} // namespace spirv
diff --git a/src/reader/spirv/function_cfg_test.cc b/src/reader/spirv/function_cfg_test.cc
index 9a42247..da99ab4 100644
--- a/src/reader/spirv/function_cfg_test.cc
+++ b/src/reader/spirv/function_cfg_test.cc
@@ -2751,6 +2751,795 @@
<< Dump(fe.block_order());
}
+TEST_F(SpvParserTest,
+ LabelControlFlowConstructs_OuterConstructIsFunction_SingleBlock) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ EXPECT_EQ(fe.constructs().size(), 1u);
+ auto& c = fe.constructs().front();
+ EXPECT_THAT(ToString(c), Eq("Construct{ Function [0,1) begin_id:10 end_id:0 "
+ "depth:0 parent:null }"));
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, c.get());
+}
+
+TEST_F(SpvParserTest,
+ LabelControlFlowConstructs_OuterConstructIsFunction_MultiBlock) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %5
+
+ %5 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ EXPECT_EQ(fe.constructs().size(), 1u);
+ auto& c = fe.constructs().front();
+ EXPECT_THAT(ToString(c), Eq("Construct{ Function [0,2) begin_id:10 end_id:0 "
+ "depth:0 parent:null }"));
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, c.get());
+ EXPECT_EQ(fe.GetBlockInfo(5)->construct, c.get());
+}
+
+TEST_F(SpvParserTest,
+ LabelControlFlowConstructs_FunctionIsOnlyIfSelectionAndItsMerge) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %30
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 2u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,4) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Selection [0,3) begin_id:10 end_id:99 depth:1 parent:Function@10 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(
+ SpvParserTest,
+ LabelControlFlowConstructs_PaddingBlocksBeforeAndAfterStructuredConstruct) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %5 = OpLabel
+ OpBranch %10
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %30
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpBranch %200
+
+ %200 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 2u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,6) begin_id:5 end_id:0 depth:0 parent:null }
+ Construct{ Selection [1,4) begin_id:10 end_id:99 depth:1 parent:Function@5 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(5)->construct, constructs[0].get());
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+ EXPECT_EQ(fe.GetBlockInfo(200)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_SwitchSelection) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %40 20 %20 30 %30
+
+ %20 = OpLabel
+ OpBranch %99
+
+ %30 = OpLabel
+ OpBranch %99
+
+ %40 = OpLabel
+ OpBranch %99
+
+ %99 = OpLabel
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 2u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,5) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Selection [0,4) begin_id:10 end_id:99 depth:1 parent:Function@10 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(40)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_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
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 2u);
+ // A single-block loop consists *only* of a continue target with one block in
+ // it.
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,3) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Continue [1,2) begin_id:20 end_id:99 depth:1 parent:Function@10 in-c:Continue@20 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[0].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_MultiBlockLoop) {
+ 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
+ OpBranch %50
+
+ %50 = OpLabel
+ OpBranch %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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ // A single-block loop consists *only* of a continue target with one block in
+ // it.
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,6) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Continue [3,5) begin_id:40 end_id:99 depth:1 parent:Function@10 in-c:Continue@40 }
+ Construct{ Loop [1,3) begin_id:20 end_id:40 depth:1 parent:Function@10 in-c-l:Loop@20 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[0].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(40)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(50)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest,
+ LabelControlFlowConstructs_MergeBlockIsAlsoSingleBlockLoop) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %50 None
+ OpBranchConditional %cond %20 %50
+
+ %20 = OpLabel
+ OpBranch %50
+
+ ; %50 is the merge block for the selection starting at 10,
+ ; and its own continue target.
+ %50 = OpLabel
+ OpLoopMerge %99 %50 None
+ OpBranchConditional %cond %50 %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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 3u);
+ // A single-block loop consists *only* of a continue target with one block in
+ // it.
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,4) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Selection [0,2) begin_id:10 end_id:50 depth:1 parent:Function@10 }
+ Construct{ Continue [2,3) begin_id:50 end_id:99 depth:1 parent:Function@10 in-c:Continue@50 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(50)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest,
+ LabelControlFlowConstructs_MergeBlockIsAlsoMultiBlockLoopHeader) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %50 None
+ OpBranchConditional %cond %20 %50
+
+ %20 = OpLabel
+ OpBranch %50
+
+ ; %50 is the merge block for the selection starting at 10,
+ ; and a loop block header but not its own continue target.
+ %50 = OpLabel
+ OpLoopMerge %99 %60 None
+ OpBranchConditional %cond %60 %99
+
+ %60 = OpLabel
+ OpBranch %50
+
+ %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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 4u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,5) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Selection [0,2) begin_id:10 end_id:50 depth:1 parent:Function@10 }
+ Construct{ Continue [3,4) begin_id:60 end_id:99 depth:1 parent:Function@10 in-c:Continue@60 }
+ Construct{ Loop [2,3) begin_id:50 end_id:60 depth:1 parent:Function@10 in-c-l:Loop@50 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(50)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(60)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_Nest_If_If) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %50
+
+ %20 = OpLabel
+ OpSelectionMerge %40 None
+ OpBranchConditional %cond %30 %40 ;; true only
+
+ %30 = OpLabel
+ OpBranch %40
+
+ %40 = OpLabel ; merge for first inner "if"
+ OpBranch %49
+
+ %49 = OpLabel ; an extra padding block
+ OpBranch %99
+
+ %50 = OpLabel
+ OpSelectionMerge %89 None
+ OpBranchConditional %cond %89 %60 ;; false only
+
+ %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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 4u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,9) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Selection [0,8) begin_id:10 end_id:99 depth:1 parent:Function@10 }
+ Construct{ Selection [1,3) begin_id:20 end_id:40 depth:2 parent:Selection@10 }
+ Construct{ Selection [5,7) begin_id:50 end_id:89 depth:2 parent:Selection@10 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(40)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(49)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(50)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(60)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(89)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_Nest_Switch_If) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpSwitch %selector %99 20 %20 50 %50
+
+ %20 = OpLabel ; if-then nested in case 20
+ OpSelectionMerge %49 None
+ OpBranchConditional %cond %30 %49
+
+ %30 = OpLabel
+ OpBranch %49
+
+ %49 = OpLabel
+ OpBranch %99
+
+ %50 = OpLabel ; unles-then nested in case 50
+ OpSelectionMerge %89 None
+ OpBranchConditional %cond %89 %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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 4u);
+ // The ordering among siblings depends on the computed block order.
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,8) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Selection [0,7) begin_id:10 end_id:99 depth:1 parent:Function@10 }
+ Construct{ Selection [1,3) begin_id:50 end_id:89 depth:2 parent:Selection@10 }
+ Construct{ Selection [4,6) begin_id:20 end_id:49 depth:2 parent:Selection@10 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(49)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(50)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(60)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(89)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_Nest_If_Switch) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %99
+
+ %20 = OpLabel
+ OpSelectionMerge %89 None
+ OpSwitch %selector %89 20 %30
+
+ %30 = 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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 3u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,5) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Selection [0,4) begin_id:10 end_id:99 depth:1 parent:Function@10 }
+ Construct{ Selection [1,3) begin_id:20 end_id:89 depth:2 parent:Selection@10 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(89)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_Nest_Loop_Loop) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %89 %50 None
+ OpBranchConditional %cond %30 %99
+
+ %30 = OpLabel ; single block loop
+ OpLoopMerge %40 %30 None
+ OpBranchConditional %cond2 %30 %40
+
+ %40 = OpLabel ; padding block
+ OpBranch %50
+
+ %50 = OpLabel ; outer continue target
+ OpBranch %60
+
+ %60 = OpLabel
+ OpBranch %20
+
+ %89 = OpLabel ; outer 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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 4u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,8) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Continue [4,6) begin_id:50 end_id:89 depth:1 parent:Function@10 in-c:Continue@50 }
+ Construct{ Loop [1,4) begin_id:20 end_id:50 depth:1 parent:Function@10 in-c-l:Loop@20 }
+ Construct{ Continue [2,3) begin_id:30 end_id:40 depth:2 parent:Loop@20 in-c:Continue@30 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[0].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(40)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(50)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(60)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(89)->construct, constructs[0].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_Nest_Loop_If) {
+ 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 ; If, nested in the loop construct
+ OpSelectionMerge %49 None
+ OpBranchConditional %cond2 %40 %49
+
+ %40 = OpLabel
+ OpBranch %49
+
+ %49 = OpLabel ; merge for inner if
+ OpBranch %80
+
+ %80 = OpLabel ; continue target
+ OpBranch %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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 4u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,7) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Continue [5,6) begin_id:80 end_id:99 depth:1 parent:Function@10 in-c:Continue@80 }
+ Construct{ Loop [1,5) begin_id:20 end_id:80 depth:1 parent:Function@10 in-c-l:Loop@20 }
+ Construct{ Selection [2,4) begin_id:30 end_id:49 depth:2 parent:Loop@20 in-c-l:Loop@20 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[0].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(40)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(49)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(80)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_Nest_LoopContinue_If) {
+ 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 ; If, nested at the top of the continue construct head
+ OpSelectionMerge %49 None
+ OpBranchConditional %cond2 %40 %49
+
+ %40 = OpLabel
+ OpBranch %49
+
+ %49 = OpLabel ; merge for inner if, backedge
+ OpBranch %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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 4u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,6) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Continue [2,5) begin_id:30 end_id:99 depth:1 parent:Function@10 in-c:Continue@30 }
+ Construct{ Loop [1,2) begin_id:20 end_id:30 depth:1 parent:Function@10 in-c-l:Loop@20 }
+ Construct{ Selection [2,4) begin_id:30 end_id:49 depth:2 parent:Continue@30 in-c:Continue@30 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[0].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(40)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(49)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_Nest_If_SingleBlockLoop) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %99
+
+ %20 = OpLabel
+ OpLoopMerge %89 %20 None
+ OpBranchConditional %cond %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();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 3u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,4) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Selection [0,3) begin_id:10 end_id:99 depth:1 parent:Function@10 }
+ Construct{ Continue [1,2) begin_id:20 end_id:89 depth:2 parent:Selection@10 in-c:Continue@20 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
+TEST_F(SpvParserTest, LabelControlFlowConstructs_Nest_If_MultiBlockLoop) {
+ auto assembly = CommonTypes() + R"(
+ %100 = OpFunction %void None %voidfn
+
+ %10 = OpLabel
+ OpSelectionMerge %99 None
+ OpBranchConditional %cond %20 %99
+
+ %20 = OpLabel ; start loop body
+ OpLoopMerge %89 %40 None
+ OpBranchConditional %cond %30 %89
+
+ %30 = OpLabel ; body block
+ OpBranch %40
+
+ %40 = OpLabel ; continue target
+ OpBranch %50
+
+ %50 = OpLabel ; backedge block
+ OpBranch %20
+
+ %89 = OpLabel ; merge for the loop
+ OpBranch %20
+
+ %99 = OpLabel ; merge for the if
+ OpReturn
+
+ OpFunctionEnd
+)";
+ auto* p = parser(test::Assemble(assembly));
+ ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << p->error();
+ FunctionEmitter fe(p, *spirv_function(100));
+ fe.RegisterBasicBlocks();
+ fe.ComputeBlockOrderAndPositions();
+ fe.RegisterMerges();
+ EXPECT_TRUE(fe.LabelControlFlowConstructs());
+ const auto& constructs = fe.constructs();
+ EXPECT_EQ(constructs.size(), 4u);
+ EXPECT_THAT(ToString(constructs), Eq(R"(ConstructList{
+ Construct{ Function [0,7) begin_id:10 end_id:0 depth:0 parent:null }
+ Construct{ Selection [0,6) begin_id:10 end_id:99 depth:1 parent:Function@10 }
+ Construct{ Continue [3,5) begin_id:40 end_id:89 depth:2 parent:Selection@10 in-c:Continue@40 }
+ Construct{ Loop [1,3) begin_id:20 end_id:40 depth:2 parent:Selection@10 in-c-l:Loop@20 }
+})")) << constructs;
+ // The block records the nearest enclosing construct.
+ EXPECT_EQ(fe.GetBlockInfo(10)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(20)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(30)->construct, constructs[3].get());
+ EXPECT_EQ(fe.GetBlockInfo(40)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(50)->construct, constructs[2].get());
+ EXPECT_EQ(fe.GetBlockInfo(89)->construct, constructs[1].get());
+ EXPECT_EQ(fe.GetBlockInfo(99)->construct, constructs[0].get());
+}
+
} // namespace
} // namespace spirv
} // namespace reader
