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
28namespace spvtools {
29
30// Control Flow Analysis of control flow graphs of basic block nodes |BB|.
31template <class BB>
32class 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
127template <class BB>
128bool 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
136template <class BB>
137void 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
174template <class BB>
175std::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
259template <class BB>
260std::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
298template <class BB>
299void 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