1 // Copyright (c) 2015-2016 The Khronos Group Inc. 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 #ifndef SOURCE_CFA_H_ 16 #define SOURCE_CFA_H_ 17 18 #include <algorithm> 19 #include <cassert> 20 #include <cstdint> 21 #include <functional> 22 #include <map> 23 #include <unordered_map> 24 #include <unordered_set> 25 #include <utility> 26 #include <vector> 27 28 namespace spvtools { 29 30 // Control Flow Analysis of control flow graphs of basic block nodes |BB|. 31 template <class BB> 32 class CFA { 33 using bb_ptr = BB*; 34 using cbb_ptr = const BB*; 35 using bb_iter = typename std::vector<BB*>::const_iterator; 36 using get_blocks_func = std::function<const std::vector<BB*>*(const BB*)>; 37 38 struct block_info { 39 cbb_ptr block; ///< pointer to the block 40 bb_iter iter; ///< Iterator to the current child node being processed 41 }; 42 43 /// Returns true if a block with @p id is found in the @p work_list vector 44 /// 45 /// @param[in] work_list Set of blocks visited in the the depth first 46 /// traversal 47 /// of the CFG 48 /// @param[in] id The ID of the block being checked 49 /// 50 /// @return true if the edge work_list.back().block->id() => id is a back-edge 51 static bool FindInWorkList(const std::vector<block_info>& work_list, 52 uint32_t id); 53 54 public: 55 /// @brief Depth first traversal starting from the \p entry BasicBlock 56 /// 57 /// This function performs a depth first traversal from the \p entry 58 /// BasicBlock and calls the pre/postorder functions when it needs to process 59 /// the node in pre order, post order. It also calls the backedge function 60 /// when a back edge is encountered. 61 /// 62 /// @param[in] entry The root BasicBlock of a CFG 63 /// @param[in] successor_func A function which will return a pointer to the 64 /// successor nodes 65 /// @param[in] preorder A function that will be called for every block in a 66 /// CFG following preorder traversal semantics 67 /// @param[in] postorder A function that will be called for every block in a 68 /// CFG following postorder traversal semantics 69 /// @param[in] backedge A function that will be called when a backedge is 70 /// encountered during a traversal 71 /// NOTE: The @p successor_func and predecessor_func each return a pointer to 72 /// a 73 /// collection such that iterators to that collection remain valid for the 74 /// lifetime of the algorithm. 75 static void DepthFirstTraversal( 76 const BB* entry, get_blocks_func successor_func, 77 std::function<void(cbb_ptr)> preorder, 78 std::function<void(cbb_ptr)> postorder, 79 std::function<void(cbb_ptr, cbb_ptr)> backedge); 80 81 /// @brief Calculates dominator edges for a set of blocks 82 /// 83 /// Computes dominators using the algorithm of Cooper, Harvey, and Kennedy 84 /// "A Simple, Fast Dominance Algorithm", 2001. 85 /// 86 /// The algorithm assumes there is a unique root node (a node without 87 /// predecessors), and it is therefore at the end of the postorder vector. 88 /// 89 /// This function calculates the dominator edges for a set of blocks in the 90 /// CFG. 91 /// Uses the dominator algorithm by Cooper et al. 92 /// 93 /// @param[in] postorder A vector of blocks in post order traversal 94 /// order 95 /// in a CFG 96 /// @param[in] predecessor_func Function used to get the predecessor nodes of 97 /// a 98 /// block 99 /// 100 /// @return the dominator tree of the graph, as a vector of pairs of nodes. 101 /// The first node in the pair is a node in the graph. The second node in the 102 /// pair is its immediate dominator in the sense of Cooper et.al., where a 103 /// block 104 /// without predecessors (such as the root node) is its own immediate 105 /// dominator. 106 static std::vector<std::pair<BB*, BB*>> CalculateDominators( 107 const std::vector<cbb_ptr>& postorder, get_blocks_func predecessor_func); 108 109 // Computes a minimal set of root nodes required to traverse, in the forward 110 // direction, the CFG represented by the given vector of blocks, and successor 111 // and predecessor functions. When considering adding two nodes, each having 112 // predecessors, favour using the one that appears earlier on the input blocks 113 // list. 114 static std::vector<BB*> TraversalRoots(const std::vector<BB*>& blocks, 115 get_blocks_func succ_func, 116 get_blocks_func pred_func); 117 118 static void ComputeAugmentedCFG( 119 std::vector<BB*>& ordered_blocks, BB* pseudo_entry_block, 120 BB* pseudo_exit_block, 121 std::unordered_map<const BB*, std::vector<BB*>>* augmented_successors_map, 122 std::unordered_map<const BB*, std::vector<BB*>>* 123 augmented_predecessors_map, 124 get_blocks_func succ_func, get_blocks_func pred_func); 125 }; 126 127 template <class BB> 128 bool CFA<BB>::FindInWorkList(const std::vector<block_info>& work_list, 129 uint32_t id) { 130 for (const auto b : work_list) { 131 if (b.block->id() == id) return true; 132 } 133 return false; 134 } 135 136 template <class BB> 137 void CFA<BB>::DepthFirstTraversal( 138 const BB* entry, get_blocks_func successor_func, 139 std::function<void(cbb_ptr)> preorder, 140 std::function<void(cbb_ptr)> postorder, 141 std::function<void(cbb_ptr, cbb_ptr)> backedge) { 142 std::unordered_set<uint32_t> processed; 143 144 /// NOTE: work_list is the sequence of nodes from the root node to the node 145 /// being processed in the traversal 146 std::vector<block_info> work_list; 147 work_list.reserve(10); 148 149 work_list.push_back({entry, std::begin(*successor_func(entry))}); 150 preorder(entry); 151 processed.insert(entry->id()); 152 153 while (!work_list.empty()) { 154 block_info& top = work_list.back(); 155 if (top.iter == end(*successor_func(top.block))) { 156 postorder(top.block); 157 work_list.pop_back(); 158 } else { 159 BB* child = *top.iter; 160 top.iter++; 161 if (FindInWorkList(work_list, child->id())) { 162 backedge(top.block, child); 163 } 164 if (processed.count(child->id()) == 0) { 165 preorder(child); 166 work_list.emplace_back( 167 block_info{child, std::begin(*successor_func(child))}); 168 processed.insert(child->id()); 169 } 170 } 171 } 172 } 173 174 template <class BB> 175 std::vector<std::pair<BB*, BB*>> CFA<BB>::CalculateDominators( 176 const std::vector<cbb_ptr>& postorder, get_blocks_func predecessor_func) { 177 struct block_detail { 178 size_t dominator; ///< The index of blocks's dominator in post order array 179 size_t postorder_index; ///< The index of the block in the post order array 180 }; 181 const size_t undefined_dom = postorder.size(); 182 183 std::unordered_map<cbb_ptr, block_detail> idoms; 184 for (size_t i = 0; i < postorder.size(); i++) { 185 idoms[postorder[i]] = {undefined_dom, i}; 186 } 187 idoms[postorder.back()].dominator = idoms[postorder.back()].postorder_index; 188 189 bool changed = true; 190 while (changed) { 191 changed = false; 192 for (auto b = postorder.rbegin() + 1; b != postorder.rend(); ++b) { 193 const std::vector<BB*>& predecessors = *predecessor_func(*b); 194 // Find the first processed/reachable predecessor that is reachable 195 // in the forward traversal. 196 auto res = std::find_if(std::begin(predecessors), std::end(predecessors), 197 [&idoms, undefined_dom](BB* pred) { 198 return idoms.count(pred) && 199 idoms[pred].dominator != undefined_dom; 200 }); 201 if (res == end(predecessors)) continue; 202 const BB* idom = *res; 203 size_t idom_idx = idoms[idom].postorder_index; 204 205 // all other predecessors 206 for (const auto* p : predecessors) { 207 if (idom == p) continue; 208 // Only consider nodes reachable in the forward traversal. 209 // Otherwise the intersection doesn't make sense and will never 210 // terminate. 211 if (!idoms.count(p)) continue; 212 if (idoms[p].dominator != undefined_dom) { 213 size_t finger1 = idoms[p].postorder_index; 214 size_t finger2 = idom_idx; 215 while (finger1 != finger2) { 216 while (finger1 < finger2) { 217 finger1 = idoms[postorder[finger1]].dominator; 218 } 219 while (finger2 < finger1) { 220 finger2 = idoms[postorder[finger2]].dominator; 221 } 222 } 223 idom_idx = finger1; 224 } 225 } 226 if (idoms[*b].dominator != idom_idx) { 227 idoms[*b].dominator = idom_idx; 228 changed = true; 229 } 230 } 231 } 232 233 std::vector<std::pair<bb_ptr, bb_ptr>> out; 234 for (auto idom : idoms) { 235 // NOTE: performing a const cast for convenient usage with 236 // UpdateImmediateDominators 237 out.push_back({const_cast<BB*>(std::get<0>(idom)), 238 const_cast<BB*>(postorder[std::get<1>(idom).dominator])}); 239 } 240 241 // Sort by postorder index to generate a deterministic ordering of edges. 242 std::sort( 243 out.begin(), out.end(), 244 [&idoms](const std::pair<bb_ptr, bb_ptr>& lhs, 245 const std::pair<bb_ptr, bb_ptr>& rhs) { 246 assert(lhs.first); 247 assert(lhs.second); 248 assert(rhs.first); 249 assert(rhs.second); 250 auto lhs_indices = std::make_pair(idoms[lhs.first].postorder_index, 251 idoms[lhs.second].postorder_index); 252 auto rhs_indices = std::make_pair(idoms[rhs.first].postorder_index, 253 idoms[rhs.second].postorder_index); 254 return lhs_indices < rhs_indices; 255 }); 256 return out; 257 } 258 259 template <class BB> 260 std::vector<BB*> CFA<BB>::TraversalRoots(const std::vector<BB*>& blocks, 261 get_blocks_func succ_func, 262 get_blocks_func pred_func) { 263 // The set of nodes which have been visited from any of the roots so far. 264 std::unordered_set<const BB*> visited; 265 266 auto mark_visited = [&visited](const BB* b) { visited.insert(b); }; 267 auto ignore_block = [](const BB*) {}; 268 auto ignore_blocks = [](const BB*, const BB*) {}; 269 270 auto traverse_from_root = [&mark_visited, &succ_func, &ignore_block, 271 &ignore_blocks](const BB* entry) { 272 DepthFirstTraversal(entry, succ_func, mark_visited, ignore_block, 273 ignore_blocks); 274 }; 275 276 std::vector<BB*> result; 277 278 // First collect nodes without predecessors. 279 for (auto block : blocks) { 280 if (pred_func(block)->empty()) { 281 assert(visited.count(block) == 0 && "Malformed graph!"); 282 result.push_back(block); 283 traverse_from_root(block); 284 } 285 } 286 287 // Now collect other stranded nodes. These must be in unreachable cycles. 288 for (auto block : blocks) { 289 if (visited.count(block) == 0) { 290 result.push_back(block); 291 traverse_from_root(block); 292 } 293 } 294 295 return result; 296 } 297 298 template <class BB> 299 void CFA<BB>::ComputeAugmentedCFG( 300 std::vector<BB*>& ordered_blocks, BB* pseudo_entry_block, 301 BB* pseudo_exit_block, 302 std::unordered_map<const BB*, std::vector<BB*>>* augmented_successors_map, 303 std::unordered_map<const BB*, std::vector<BB*>>* augmented_predecessors_map, 304 get_blocks_func succ_func, get_blocks_func pred_func) { 305 // Compute the successors of the pseudo-entry block, and 306 // the predecessors of the pseudo exit block. 307 auto sources = TraversalRoots(ordered_blocks, succ_func, pred_func); 308 309 // For the predecessor traversals, reverse the order of blocks. This 310 // will affect the post-dominance calculation as follows: 311 // - Suppose you have blocks A and B, with A appearing before B in 312 // the list of blocks. 313 // - Also, A branches only to B, and B branches only to A. 314 // - We want to compute A as dominating B, and B as post-dominating B. 315 // By using reversed blocks for predecessor traversal roots discovery, 316 // we'll add an edge from B to the pseudo-exit node, rather than from A. 317 // All this is needed to correctly process the dominance/post-dominance 318 // constraint when A is a loop header that points to itself as its 319 // own continue target, and B is the latch block for the loop. 320 std::vector<BB*> reversed_blocks(ordered_blocks.rbegin(), 321 ordered_blocks.rend()); 322 auto sinks = TraversalRoots(reversed_blocks, pred_func, succ_func); 323 324 // Wire up the pseudo entry block. 325 (*augmented_successors_map)[pseudo_entry_block] = sources; 326 for (auto block : sources) { 327 auto& augmented_preds = (*augmented_predecessors_map)[block]; 328 const auto preds = pred_func(block); 329 augmented_preds.reserve(1 + preds->size()); 330 augmented_preds.push_back(pseudo_entry_block); 331 augmented_preds.insert(augmented_preds.end(), preds->begin(), preds->end()); 332 } 333 334 // Wire up the pseudo exit block. 335 (*augmented_predecessors_map)[pseudo_exit_block] = sinks; 336 for (auto block : sinks) { 337 auto& augmented_succ = (*augmented_successors_map)[block]; 338 const auto succ = succ_func(block); 339 augmented_succ.reserve(1 + succ->size()); 340 augmented_succ.push_back(pseudo_exit_block); 341 augmented_succ.insert(augmented_succ.end(), succ->begin(), succ->end()); 342 } 343 } 344 345 } // namespace spvtools 346 347 #endif // SOURCE_CFA_H_ 348