• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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