Add control dependence analysis to opt (#4380)
Control dependence analysis constructs a control dependence graph,
representing the conditions for a block's execution relative to the
results of other blocks with conditional branches, etc.
This is an analysis pass that will be useful for the linter and
potentially also useful in opt. Currently it is unused except for the
added unit tests.
diff --git a/Android.mk b/Android.mk
index bdcdda9..057731f 100644
--- a/Android.mk
+++ b/Android.mk
@@ -88,6 +88,7 @@
source/opt/composite.cpp \
source/opt/const_folding_rules.cpp \
source/opt/constants.cpp \
+ source/opt/control_dependence.cpp \
source/opt/convert_to_half_pass.cpp \
source/opt/copy_prop_arrays.cpp \
source/opt/dead_branch_elim_pass.cpp \
diff --git a/BUILD.gn b/BUILD.gn
index 32a44ff..fea0279 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -606,6 +606,8 @@
"source/opt/const_folding_rules.h",
"source/opt/constants.cpp",
"source/opt/constants.h",
+ "source/opt/control_dependence.cpp",
+ "source/opt/control_dependence.h",
"source/opt/convert_to_half_pass.cpp",
"source/opt/convert_to_half_pass.h",
"source/opt/copy_prop_arrays.cpp",
diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt
index 0e41b20..f6ebcfa 100644
--- a/source/opt/CMakeLists.txt
+++ b/source/opt/CMakeLists.txt
@@ -27,6 +27,7 @@
composite.h
const_folding_rules.h
constants.h
+ control_dependence.h
convert_to_half_pass.h
copy_prop_arrays.h
dead_branch_elim_pass.h
@@ -133,6 +134,7 @@
composite.cpp
const_folding_rules.cpp
constants.cpp
+ control_dependence.cpp
convert_to_half_pass.cpp
copy_prop_arrays.cpp
dead_branch_elim_pass.cpp
diff --git a/source/opt/control_dependence.cpp b/source/opt/control_dependence.cpp
new file mode 100644
index 0000000..f4879e0
--- /dev/null
+++ b/source/opt/control_dependence.cpp
@@ -0,0 +1,156 @@
+// Copyright (c) 2021 Google LLC.
+//
+// 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 "source/opt/control_dependence.h"
+
+#include <cassert>
+#include <tuple>
+#include <utility>
+#include <vector>
+
+#include "source/opt/basic_block.h"
+#include "source/opt/cfg.h"
+#include "source/opt/dominator_analysis.h"
+#include "source/opt/function.h"
+#include "source/opt/instruction.h"
+#include "spirv/unified1/spirv.h"
+
+// Computes the control dependence graph (CDG) using the algorithm in Cytron
+// 1991, "Efficiently Computing Static Single Assignment Form and the Control
+// Dependence Graph." It relies on the fact that the control dependence sources
+// (blocks on which a block is control dependent) are exactly the post-dominance
+// frontier for that block. The explanation and proofs are given in Section 6 of
+// that paper.
+// Link: https://www.cs.utexas.edu/~pingali/CS380C/2010/papers/ssaCytron.pdf
+//
+// The algorithm in Section 4.2 of the same paper is used to construct the
+// dominance frontier. It uses the post-dominance tree, which is available in
+// the IR context.
+
+namespace spvtools {
+namespace opt {
+constexpr uint32_t ControlDependenceAnalysis::kPseudoEntryBlock;
+
+uint32_t ControlDependence::GetConditionID(const CFG& cfg) const {
+ if (source_bb_id() == 0) {
+ // Entry dependence; return 0.
+ return 0;
+ }
+ const BasicBlock* source_bb = cfg.block(source_bb_id());
+ const Instruction* branch = source_bb->terminator();
+ assert((branch->opcode() == SpvOpBranchConditional ||
+ branch->opcode() == SpvOpSwitch) &&
+ "invalid control dependence; last instruction must be conditional "
+ "branch or switch");
+ return branch->GetSingleWordInOperand(0);
+}
+
+bool ControlDependence::operator<(const ControlDependence& other) const {
+ return std::tie(source_bb_id_, target_bb_id_, branch_target_bb_id_) <
+ std::tie(other.source_bb_id_, other.target_bb_id_,
+ other.branch_target_bb_id_);
+}
+
+bool ControlDependence::operator==(const ControlDependence& other) const {
+ return std::tie(source_bb_id_, target_bb_id_, branch_target_bb_id_) ==
+ std::tie(other.source_bb_id_, other.target_bb_id_,
+ other.branch_target_bb_id_);
+}
+
+std::ostream& operator<<(std::ostream& os, const ControlDependence& dep) {
+ os << dep.source_bb_id() << "->" << dep.target_bb_id();
+ if (dep.branch_target_bb_id() != dep.target_bb_id()) {
+ os << " through " << dep.branch_target_bb_id();
+ }
+ return os;
+}
+
+void ControlDependenceAnalysis::ComputePostDominanceFrontiers(
+ const CFG& cfg, const PostDominatorAnalysis& pdom) {
+ // Compute post-dominance frontiers (reverse graph).
+ // The dominance frontier for a block X is equal to (Equation 4)
+ // DF_local(X) U { B in DF_up(Z) | X = ipdom(Z) }
+ // (ipdom(Z) is the immediate post-dominator of Z.)
+ // where
+ // DF_local(X) = { Y | X -> Y in CFG, X does not strictly post-dominate Y }
+ // represents the contribution of X's predecessors to the DF, and
+ // DF_up(Z) = { Y | Y in DF(Z), ipdom(Z) does not strictly post-dominate Y }
+ // (note: ipdom(Z) = X.)
+ // represents the contribution of a block to its immediate post-
+ // dominator's DF.
+ // This is computed in one pass through a post-order traversal of the
+ // post-dominator tree.
+
+ // Assert that there is a block other than the pseudo exit in the pdom tree,
+ // as we need one to get the function entry point (as the pseudo exit is not
+ // actually part of the function.)
+ assert(!cfg.IsPseudoExitBlock(pdom.GetDomTree().post_begin()->bb_));
+ Function* function = pdom.GetDomTree().post_begin()->bb_->GetParent();
+ uint32_t function_entry = function->entry()->id();
+ // Explicitly initialize pseudo-entry block, as it doesn't depend on anything,
+ // so it won't be initialized in the following loop.
+ reverse_nodes_[kPseudoEntryBlock] = {};
+ for (auto it = pdom.GetDomTree().post_cbegin();
+ it != pdom.GetDomTree().post_cend(); ++it) {
+ ComputePostDominanceFrontierForNode(cfg, pdom, function_entry, *it);
+ }
+}
+
+void ControlDependenceAnalysis::ComputePostDominanceFrontierForNode(
+ const CFG& cfg, const PostDominatorAnalysis& pdom, uint32_t function_entry,
+ const DominatorTreeNode& pdom_node) {
+ const uint32_t label = pdom_node.id();
+ ControlDependenceList& edges = reverse_nodes_[label];
+ for (uint32_t pred : cfg.preds(label)) {
+ if (!pdom.StrictlyDominates(label, pred)) {
+ edges.push_back(ControlDependence(pred, label));
+ }
+ }
+ if (label == function_entry) {
+ // Add edge from pseudo-entry to entry.
+ // In CDG construction, an edge is added from entry to exit, so only the
+ // exit node can post-dominate entry.
+ edges.push_back(ControlDependence(kPseudoEntryBlock, label));
+ }
+ for (DominatorTreeNode* child : pdom_node) {
+ // Note: iterate dependences by value, as we need a copy.
+ for (const ControlDependence& dep : reverse_nodes_[child->id()]) {
+ // Special-case pseudo-entry, as above.
+ if (dep.source_bb_id() == kPseudoEntryBlock ||
+ !pdom.StrictlyDominates(label, dep.source_bb_id())) {
+ edges.push_back(ControlDependence(dep.source_bb_id(), label,
+ dep.branch_target_bb_id()));
+ }
+ }
+ }
+}
+
+void ControlDependenceAnalysis::ComputeControlDependenceGraph(
+ const CFG& cfg, const PostDominatorAnalysis& pdom) {
+ ComputePostDominanceFrontiers(cfg, pdom);
+ ComputeForwardGraphFromReverse();
+}
+
+void ControlDependenceAnalysis::ComputeForwardGraphFromReverse() {
+ for (const auto& entry : reverse_nodes_) {
+ // Ensure an entry is created for each node.
+ forward_nodes_[entry.first];
+ for (const ControlDependence& dep : entry.second) {
+ forward_nodes_[dep.source_bb_id()].push_back(dep);
+ }
+ }
+}
+
+} // namespace opt
+} // namespace spvtools
diff --git a/source/opt/control_dependence.h b/source/opt/control_dependence.h
new file mode 100644
index 0000000..920e4dc
--- /dev/null
+++ b/source/opt/control_dependence.h
@@ -0,0 +1,199 @@
+// Copyright (c) 2021 Google LLC.
+//
+// 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 SOURCE_OPT_CONTROL_DEPENDENCE_H_
+#define SOURCE_OPT_CONTROL_DEPENDENCE_H_
+
+#include <algorithm>
+#include <cstdint>
+#include <functional>
+#include <ostream>
+#include <unordered_map>
+#include <vector>
+
+#include "source/opt/cfg.h"
+#include "source/opt/dominator_analysis.h"
+
+namespace spvtools {
+namespace opt {
+
+class ControlDependence {
+ public:
+ // The label of the source of this dependence, i.e. the block on which the
+ // target is dependent on.
+ // A |source_bb_id| of 0 represents an "entry" dependence, meaning that the
+ // execution of |target_bb_id| is only dependent on entry to the function.
+ uint32_t source_bb_id() const { return source_bb_id_; }
+ // The label of the target of this dependence, i.e. the block which is
+ // dependent on the source.
+ uint32_t target_bb_id() const { return target_bb_id_; }
+ // The label of the target of the *branch* for this dependence.
+ // Equal to the ID of the entry block for entry dependences.
+ //
+ // For example, for the partial CFG pictured below:
+ // 1 ---> 2 ---> 4 ---> 6
+ // \ \ ^
+ // \-> 3 \-> 5 -----/
+ // Block 6 is control dependent on block 1, but this dependence comes from the
+ // branch 1 -> 2, so in this case the branch target ID would be 2.
+ uint32_t branch_target_bb_id() const { return branch_target_bb_id_; }
+
+ // Create a direct control dependence from BB ID |source| to |target|.
+ ControlDependence(uint32_t source, uint32_t target)
+ : source_bb_id_(source),
+ target_bb_id_(target),
+ branch_target_bb_id_(target) {}
+ // Create a control dependence from BB ID |source| to |target| through the
+ // branch from |source| to |branch_target|.
+ ControlDependence(uint32_t source, uint32_t target, uint32_t branch_target)
+ : source_bb_id_(source),
+ target_bb_id_(target),
+ branch_target_bb_id_(branch_target) {}
+
+ // Gets the ID of the conditional value for the branch corresponding to this
+ // control dependence. This is the first input operand for both
+ // OpConditionalBranch and OpSwitch.
+ // Returns 0 for entry dependences.
+ uint32_t GetConditionID(const CFG& cfg) const;
+
+ bool operator==(const ControlDependence& other) const;
+ bool operator!=(const ControlDependence& other) const {
+ return !(*this == other);
+ }
+
+ // Comparison operators, ordered lexicographically. Total ordering.
+ bool operator<(const ControlDependence& other) const;
+ bool operator>(const ControlDependence& other) const { return other < *this; }
+ bool operator<=(const ControlDependence& other) const {
+ return !(*this > other);
+ }
+ bool operator>=(const ControlDependence& other) const {
+ return !(*this < other);
+ }
+
+ private:
+ uint32_t source_bb_id_;
+ uint32_t target_bb_id_;
+ uint32_t branch_target_bb_id_;
+};
+
+// Prints |dep| to |os| in a human-readable way. For example,
+// 1->2 (target_bb_id = branch_target_bb_id = 2)
+// 3->4 through 5 (target_bb_id = 4, branch_target_bb_id = 5)
+std::ostream& operator<<(std::ostream& os, const ControlDependence& dep);
+
+// Represents the control dependence graph. A basic block is control dependent
+// on another if the result of that block (e.g. the condition of a conditional
+// branch) influences whether it is executed or not. More formally, a block A is
+// control dependent on B iff:
+// 1. there exists a path from A to the exit node that does *not* go through B
+// (i.e., A does not postdominate B), and
+// 2. there exists a path B -> b_1 -> ... -> b_n -> A such that A post-dominates
+// all nodes b_i.
+class ControlDependenceAnalysis {
+ public:
+ // Map basic block labels to control dependencies/dependents.
+ // Not guaranteed to be in any particular order.
+ using ControlDependenceList = std::vector<ControlDependence>;
+ using ControlDependenceListMap =
+ std::unordered_map<uint32_t, ControlDependenceList>;
+
+ // 0, the label number for the pseudo entry block.
+ // All control dependences on the pseudo entry block are of type kEntry, and
+ // vice versa.
+ static constexpr uint32_t kPseudoEntryBlock = 0;
+
+ // Build the control dependence graph for the given control flow graph |cfg|
+ // and corresponding post-dominator analysis |pdom|.
+ void ComputeControlDependenceGraph(const CFG& cfg,
+ const PostDominatorAnalysis& pdom);
+
+ // Get the list of the nodes that depend on a block.
+ // Return value is not guaranteed to be in any particular order.
+ const ControlDependenceList& GetDependenceTargets(uint32_t block) const {
+ return forward_nodes_.at(block);
+ }
+
+ // Get the list of the nodes on which a block depends on.
+ // Return value is not guaranteed to be in any particular order.
+ const ControlDependenceList& GetDependenceSources(uint32_t block) const {
+ return reverse_nodes_.at(block);
+ }
+
+ // Runs the function |f| on each block label in the CDG. If any iteration
+ // returns false, immediately stops iteration and returns false. Otherwise
+ // returns true. Nodes are iterated in some undefined order, including the
+ // pseudo-entry block.
+ bool WhileEachBlockLabel(std::function<bool(uint32_t)> f) const {
+ for (const auto& entry : forward_nodes_) {
+ if (!f(entry.first)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ // Runs the function |f| on each block label in the CDG. Nodes are iterated in
+ // some undefined order, including the pseudo-entry block.
+ void ForEachBlockLabel(std::function<void(uint32_t)> f) const {
+ WhileEachBlockLabel([&f](uint32_t label) {
+ f(label);
+ return true;
+ });
+ }
+
+ // Returns true if the block |id| exists in the control dependence graph.
+ // This can be false even if the block exists in the function when it is part
+ // of an infinite loop, since it is not part of the post-dominator tree.
+ bool DoesBlockExist(uint32_t id) const {
+ return forward_nodes_.count(id) > 0;
+ }
+
+ // Returns true if block |a| is dependent on block |b|.
+ bool IsDependent(uint32_t a, uint32_t b) const {
+ if (!DoesBlockExist(a)) return false;
+ // BBs tend to have more dependents (targets) than they are dependent on
+ // (sources), so search sources.
+ const ControlDependenceList& a_sources = GetDependenceSources(a);
+ return std::find_if(a_sources.begin(), a_sources.end(),
+ [b](const ControlDependence& dep) {
+ return dep.source_bb_id() == b;
+ }) != a_sources.end();
+ }
+
+ private:
+ // Computes the post-dominance frontiers (i.e. the reverse CDG) for each node
+ // in the post-dominator tree. Only modifies reverse_nodes_; forward_nodes_ is
+ // not modified.
+ void ComputePostDominanceFrontiers(const CFG& cfg,
+ const PostDominatorAnalysis& pdom);
+ // Computes the post-dominance frontier for a specific node |pdom_node| in the
+ // post-dominator tree. Result is placed in reverse_nodes_[pdom_node.id()].
+ void ComputePostDominanceFrontierForNode(const CFG& cfg,
+ const PostDominatorAnalysis& pdom,
+ uint32_t function_entry,
+ const DominatorTreeNode& pdom_node);
+
+ // Computes the forward graph (forward_nodes_) from the reverse graph
+ // (reverse_nodes_).
+ void ComputeForwardGraphFromReverse();
+
+ ControlDependenceListMap forward_nodes_;
+ ControlDependenceListMap reverse_nodes_;
+};
+
+} // namespace opt
+} // namespace spvtools
+
+#endif // SOURCE_OPT_CONTROL_DEPENDENCE_H_
diff --git a/test/opt/CMakeLists.txt b/test/opt/CMakeLists.txt
index 621a6aa..0331246 100644
--- a/test/opt/CMakeLists.txt
+++ b/test/opt/CMakeLists.txt
@@ -28,6 +28,7 @@
compact_ids_test.cpp
constants_test.cpp
constant_manager_test.cpp
+ control_dependence.cpp
convert_relaxed_to_half_test.cpp
copy_prop_array_test.cpp
dead_branch_elim_test.cpp
diff --git a/test/opt/control_dependence.cpp b/test/opt/control_dependence.cpp
new file mode 100644
index 0000000..02793f1
--- /dev/null
+++ b/test/opt/control_dependence.cpp
@@ -0,0 +1,269 @@
+// Copyright (c) 2021 Google LLC.
+//
+// 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 "source/opt/control_dependence.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "gmock/gmock-matchers.h"
+#include "gtest/gtest.h"
+#include "source/opt/build_module.h"
+#include "source/opt/cfg.h"
+#include "test/opt/function_utils.h"
+
+namespace spvtools {
+namespace opt {
+
+namespace {
+void GatherEdges(const ControlDependenceAnalysis& cdg,
+ std::vector<ControlDependence>& ret) {
+ cdg.ForEachBlockLabel([&](uint32_t label) {
+ ret.reserve(ret.size() + cdg.GetDependenceTargets(label).size());
+ ret.insert(ret.end(), cdg.GetDependenceTargets(label).begin(),
+ cdg.GetDependenceTargets(label).end());
+ });
+ std::sort(ret.begin(), ret.end());
+ // Verify that reverse graph is the same.
+ std::vector<ControlDependence> reverse_edges;
+ reverse_edges.reserve(ret.size());
+ cdg.ForEachBlockLabel([&](uint32_t label) {
+ reverse_edges.insert(reverse_edges.end(),
+ cdg.GetDependenceSources(label).begin(),
+ cdg.GetDependenceSources(label).end());
+ });
+ std::sort(reverse_edges.begin(), reverse_edges.end());
+ ASSERT_THAT(reverse_edges, testing::ElementsAreArray(ret));
+}
+
+using ControlDependenceTest = ::testing::Test;
+
+TEST(ControlDependenceTest, DependenceSimpleCFG) {
+ const std::string text = R"(
+ OpCapability Addresses
+ OpCapability Kernel
+ OpMemoryModel Physical64 OpenCL
+ OpEntryPoint Kernel %1 "main"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %4 = OpTypeBool
+ %5 = OpTypeInt 32 0
+ %6 = OpConstant %5 0
+ %7 = OpConstantFalse %4
+ %8 = OpConstantTrue %4
+ %9 = OpConstant %5 1
+ %1 = OpFunction %2 None %3
+ %10 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ OpSwitch %6 %12 1 %13
+ %12 = OpLabel
+ OpBranch %14
+ %13 = OpLabel
+ OpBranch %14
+ %14 = OpLabel
+ OpBranchConditional %8 %15 %16
+ %15 = OpLabel
+ OpBranch %19
+ %16 = OpLabel
+ OpBranchConditional %8 %17 %18
+ %17 = OpLabel
+ OpBranch %18
+ %18 = OpLabel
+ OpBranch %19
+ %19 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ // CFG: (all edges pointing downward)
+ // %10
+ // |
+ // %11
+ // / \ (R: %6 == 1, L: default)
+ // %12 %13
+ // \ /
+ // %14
+ // T/ \F
+ // %15 %16
+ // | T/ |F
+ // | %17|
+ // | \ |
+ // | %18
+ // | /
+ // %19
+
+ std::unique_ptr<IRContext> context =
+ BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
+ SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+ Module* module = context->module();
+ EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
+ << text << std::endl;
+ const Function* fn = spvtest::GetFunction(module, 1);
+ const BasicBlock* entry = spvtest::GetBasicBlock(fn, 10);
+ EXPECT_EQ(entry, fn->entry().get())
+ << "The entry node is not the expected one";
+
+ {
+ PostDominatorAnalysis pdom;
+ const CFG& cfg = *context->cfg();
+ pdom.InitializeTree(cfg, fn);
+ ControlDependenceAnalysis cdg;
+ cdg.ComputeControlDependenceGraph(cfg, pdom);
+
+ EXPECT_TRUE(cdg.IsDependent(12, 11));
+ EXPECT_TRUE(cdg.IsDependent(13, 11));
+ EXPECT_TRUE(cdg.IsDependent(15, 14));
+ EXPECT_TRUE(cdg.IsDependent(16, 14));
+ EXPECT_TRUE(cdg.IsDependent(18, 14));
+ EXPECT_TRUE(cdg.IsDependent(17, 16));
+ EXPECT_TRUE(cdg.IsDependent(10, 0));
+ EXPECT_TRUE(cdg.IsDependent(11, 0));
+ EXPECT_TRUE(cdg.IsDependent(14, 0));
+ EXPECT_TRUE(cdg.IsDependent(19, 0));
+ EXPECT_FALSE(cdg.IsDependent(14, 11));
+ EXPECT_FALSE(cdg.IsDependent(17, 14));
+ EXPECT_FALSE(cdg.IsDependent(19, 14));
+ EXPECT_FALSE(cdg.IsDependent(12, 0));
+
+ std::vector<ControlDependence> edges;
+ GatherEdges(cdg, edges);
+ EXPECT_THAT(edges,
+ testing::ElementsAre(
+ ControlDependence(0, 10), ControlDependence(0, 11, 10),
+ ControlDependence(0, 14, 10), ControlDependence(0, 19, 10),
+ ControlDependence(11, 12), ControlDependence(11, 13),
+ ControlDependence(14, 15), ControlDependence(14, 16),
+ ControlDependence(14, 18, 16), ControlDependence(16, 17)));
+
+ const uint32_t expected_condition_ids[] = {
+ 0, 0, 0, 0, 6, 6, 8, 8, 8, 8,
+ };
+
+ for (uint32_t i = 0; i < edges.size(); i++) {
+ EXPECT_EQ(expected_condition_ids[i], edges[i].GetConditionID(cfg));
+ }
+ }
+}
+
+TEST(ControlDependenceTest, DependencePaperCFG) {
+ const std::string text = R"(
+ OpCapability Addresses
+ OpCapability Kernel
+ OpMemoryModel Physical64 OpenCL
+ OpEntryPoint Kernel %101 "main"
+ %102 = OpTypeVoid
+ %103 = OpTypeFunction %102
+ %104 = OpTypeBool
+ %108 = OpConstantTrue %104
+ %101 = OpFunction %102 None %103
+ %1 = OpLabel
+ OpBranch %2
+ %2 = OpLabel
+ OpBranchConditional %108 %3 %7
+ %3 = OpLabel
+ OpBranchConditional %108 %4 %5
+ %4 = OpLabel
+ OpBranch %6
+ %5 = OpLabel
+ OpBranch %6
+ %6 = OpLabel
+ OpBranch %8
+ %7 = OpLabel
+ OpBranch %8
+ %8 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpBranchConditional %108 %10 %11
+ %10 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ OpBranchConditional %108 %12 %9
+ %12 = OpLabel
+ OpBranchConditional %108 %13 %2
+ %13 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ // CFG: (edges pointing downward if no arrow)
+ // %1
+ // |
+ // %2 <----+
+ // T/ \F |
+ // %3 \ |
+ // T/ \F \ |
+ // %4 %5 %7 |
+ // \ / / |
+ // %6 / |
+ // \ / |
+ // %8 |
+ // | |
+ // %9 <-+ |
+ // T/ | | |
+ // %10 | | |
+ // \ | | |
+ // %11-F+ |
+ // T| |
+ // %12-F---+
+ // T|
+ // %13
+
+ std::unique_ptr<IRContext> context =
+ BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
+ SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+ Module* module = context->module();
+ EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
+ << text << std::endl;
+ const Function* fn = spvtest::GetFunction(module, 101);
+ const BasicBlock* entry = spvtest::GetBasicBlock(fn, 1);
+ EXPECT_EQ(entry, fn->entry().get())
+ << "The entry node is not the expected one";
+
+ {
+ PostDominatorAnalysis pdom;
+ const CFG& cfg = *context->cfg();
+ pdom.InitializeTree(cfg, fn);
+ ControlDependenceAnalysis cdg;
+ cdg.ComputeControlDependenceGraph(cfg, pdom);
+
+ std::vector<ControlDependence> edges;
+ GatherEdges(cdg, edges);
+ EXPECT_THAT(
+ edges, testing::ElementsAre(
+ ControlDependence(0, 1), ControlDependence(0, 2, 1),
+ ControlDependence(0, 8, 1), ControlDependence(0, 9, 1),
+ ControlDependence(0, 11, 1), ControlDependence(0, 12, 1),
+ ControlDependence(0, 13, 1), ControlDependence(2, 3),
+ ControlDependence(2, 6, 3), ControlDependence(2, 7),
+ ControlDependence(3, 4), ControlDependence(3, 5),
+ ControlDependence(9, 10), ControlDependence(11, 9),
+ ControlDependence(11, 11, 9), ControlDependence(12, 2),
+ ControlDependence(12, 8, 2), ControlDependence(12, 9, 2),
+ ControlDependence(12, 11, 2), ControlDependence(12, 12, 2)));
+
+ const uint32_t expected_condition_ids[] = {
+ 0, 0, 0, 0, 0, 0, 0, 108, 108, 108,
+ 108, 108, 108, 108, 108, 108, 108, 108, 108, 108,
+ };
+
+ for (uint32_t i = 0; i < edges.size(); i++) {
+ EXPECT_EQ(expected_condition_ids[i], edges[i].GetConditionID(cfg));
+ }
+ }
+}
+
+} // namespace
+} // namespace opt
+} // namespace spvtools
