1 // Copyright (c) 2021 Google LLC.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "source/opt/control_dependence.h"
16
17 #include <cassert>
18 #include <tuple>
19
20 #include "source/opt/basic_block.h"
21 #include "source/opt/cfg.h"
22 #include "source/opt/dominator_analysis.h"
23 #include "source/opt/function.h"
24 #include "source/opt/instruction.h"
25
26 // Computes the control dependence graph (CDG) using the algorithm in Cytron
27 // 1991, "Efficiently Computing Static Single Assignment Form and the Control
28 // Dependence Graph." It relies on the fact that the control dependence sources
29 // (blocks on which a block is control dependent) are exactly the post-dominance
30 // frontier for that block. The explanation and proofs are given in Section 6 of
31 // that paper.
32 // Link: https://www.cs.utexas.edu/~pingali/CS380C/2010/papers/ssaCytron.pdf
33 //
34 // The algorithm in Section 4.2 of the same paper is used to construct the
35 // dominance frontier. It uses the post-dominance tree, which is available in
36 // the IR context.
37
38 namespace spvtools {
39 namespace opt {
40 constexpr uint32_t ControlDependenceAnalysis::kPseudoEntryBlock;
41
GetConditionID(const CFG & cfg) const42 uint32_t ControlDependence::GetConditionID(const CFG& cfg) const {
43 if (source_bb_id() == 0) {
44 // Entry dependence; return 0.
45 return 0;
46 }
47 const BasicBlock* source_bb = cfg.block(source_bb_id());
48 const Instruction* branch = source_bb->terminator();
49 assert((branch->opcode() == spv::Op::OpBranchConditional ||
50 branch->opcode() == spv::Op::OpSwitch) &&
51 "invalid control dependence; last instruction must be conditional "
52 "branch or switch");
53 return branch->GetSingleWordInOperand(0);
54 }
55
operator <(const ControlDependence & other) const56 bool ControlDependence::operator<(const ControlDependence& other) const {
57 return std::tie(source_bb_id_, target_bb_id_, branch_target_bb_id_) <
58 std::tie(other.source_bb_id_, other.target_bb_id_,
59 other.branch_target_bb_id_);
60 }
61
operator ==(const ControlDependence & other) const62 bool ControlDependence::operator==(const ControlDependence& other) const {
63 return std::tie(source_bb_id_, target_bb_id_, branch_target_bb_id_) ==
64 std::tie(other.source_bb_id_, other.target_bb_id_,
65 other.branch_target_bb_id_);
66 }
67
operator <<(std::ostream & os,const ControlDependence & dep)68 std::ostream& operator<<(std::ostream& os, const ControlDependence& dep) {
69 os << dep.source_bb_id() << "->" << dep.target_bb_id();
70 if (dep.branch_target_bb_id() != dep.target_bb_id()) {
71 os << " through " << dep.branch_target_bb_id();
72 }
73 return os;
74 }
75
ComputePostDominanceFrontiers(const CFG & cfg,const PostDominatorAnalysis & pdom)76 void ControlDependenceAnalysis::ComputePostDominanceFrontiers(
77 const CFG& cfg, const PostDominatorAnalysis& pdom) {
78 // Compute post-dominance frontiers (reverse graph).
79 // The dominance frontier for a block X is equal to (Equation 4)
80 // DF_local(X) U { B in DF_up(Z) | X = ipdom(Z) }
81 // (ipdom(Z) is the immediate post-dominator of Z.)
82 // where
83 // DF_local(X) = { Y | X -> Y in CFG, X does not strictly post-dominate Y }
84 // represents the contribution of X's predecessors to the DF, and
85 // DF_up(Z) = { Y | Y in DF(Z), ipdom(Z) does not strictly post-dominate Y }
86 // (note: ipdom(Z) = X.)
87 // represents the contribution of a block to its immediate post-
88 // dominator's DF.
89 // This is computed in one pass through a post-order traversal of the
90 // post-dominator tree.
91
92 // Assert that there is a block other than the pseudo exit in the pdom tree,
93 // as we need one to get the function entry point (as the pseudo exit is not
94 // actually part of the function.)
95 assert(!cfg.IsPseudoExitBlock(pdom.GetDomTree().post_begin()->bb_));
96 Function* function = pdom.GetDomTree().post_begin()->bb_->GetParent();
97 uint32_t function_entry = function->entry()->id();
98 // Explicitly initialize pseudo-entry block, as it doesn't depend on anything,
99 // so it won't be initialized in the following loop.
100 reverse_nodes_[kPseudoEntryBlock] = {};
101 for (auto it = pdom.GetDomTree().post_cbegin();
102 it != pdom.GetDomTree().post_cend(); ++it) {
103 ComputePostDominanceFrontierForNode(cfg, pdom, function_entry, *it);
104 }
105 }
106
ComputePostDominanceFrontierForNode(const CFG & cfg,const PostDominatorAnalysis & pdom,uint32_t function_entry,const DominatorTreeNode & pdom_node)107 void ControlDependenceAnalysis::ComputePostDominanceFrontierForNode(
108 const CFG& cfg, const PostDominatorAnalysis& pdom, uint32_t function_entry,
109 const DominatorTreeNode& pdom_node) {
110 const uint32_t label = pdom_node.id();
111 ControlDependenceList& edges = reverse_nodes_[label];
112 for (uint32_t pred : cfg.preds(label)) {
113 if (!pdom.StrictlyDominates(label, pred)) {
114 edges.push_back(ControlDependence(pred, label));
115 }
116 }
117 if (label == function_entry) {
118 // Add edge from pseudo-entry to entry.
119 // In CDG construction, an edge is added from entry to exit, so only the
120 // exit node can post-dominate entry.
121 edges.push_back(ControlDependence(kPseudoEntryBlock, label));
122 }
123 for (DominatorTreeNode* child : pdom_node) {
124 // Note: iterate dependences by value, as we need a copy.
125 for (const ControlDependence& dep : reverse_nodes_[child->id()]) {
126 // Special-case pseudo-entry, as above.
127 if (dep.source_bb_id() == kPseudoEntryBlock ||
128 !pdom.StrictlyDominates(label, dep.source_bb_id())) {
129 edges.push_back(ControlDependence(dep.source_bb_id(), label,
130 dep.branch_target_bb_id()));
131 }
132 }
133 }
134 }
135
ComputeControlDependenceGraph(const CFG & cfg,const PostDominatorAnalysis & pdom)136 void ControlDependenceAnalysis::ComputeControlDependenceGraph(
137 const CFG& cfg, const PostDominatorAnalysis& pdom) {
138 ComputePostDominanceFrontiers(cfg, pdom);
139 ComputeForwardGraphFromReverse();
140 }
141
ComputeForwardGraphFromReverse()142 void ControlDependenceAnalysis::ComputeForwardGraphFromReverse() {
143 for (const auto& entry : reverse_nodes_) {
144 // Ensure an entry is created for each node.
145 forward_nodes_[entry.first];
146 for (const ControlDependence& dep : entry.second) {
147 forward_nodes_[dep.source_bb_id()].push_back(dep);
148 }
149 }
150 }
151
152 } // namespace opt
153 } // namespace spvtools
154