1 /*
2 * Copyright 2016-2020 Arm Limited
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "spirv_cfg.hpp"
18 #include "spirv_cross.hpp"
19 #include <algorithm>
20 #include <assert.h>
21
22 using namespace std;
23
24 namespace SPIRV_CROSS_NAMESPACE
25 {
CFG(Compiler & compiler_,const SPIRFunction & func_)26 CFG::CFG(Compiler &compiler_, const SPIRFunction &func_)
27 : compiler(compiler_)
28 , func(func_)
29 {
30 build_post_order_visit_order();
31 build_immediate_dominators();
32 }
33
find_common_dominator(uint32_t a,uint32_t b) const34 uint32_t CFG::find_common_dominator(uint32_t a, uint32_t b) const
35 {
36 while (a != b)
37 {
38 if (get_visit_order(a) < get_visit_order(b))
39 a = get_immediate_dominator(a);
40 else
41 b = get_immediate_dominator(b);
42 }
43 return a;
44 }
45
build_immediate_dominators()46 void CFG::build_immediate_dominators()
47 {
48 // Traverse the post-order in reverse and build up the immediate dominator tree.
49 immediate_dominators.clear();
50 immediate_dominators[func.entry_block] = func.entry_block;
51
52 for (auto i = post_order.size(); i; i--)
53 {
54 uint32_t block = post_order[i - 1];
55 auto &pred = preceding_edges[block];
56 if (pred.empty()) // This is for the entry block, but we've already set up the dominators.
57 continue;
58
59 for (auto &edge : pred)
60 {
61 if (immediate_dominators[block])
62 {
63 assert(immediate_dominators[edge]);
64 immediate_dominators[block] = find_common_dominator(immediate_dominators[block], edge);
65 }
66 else
67 immediate_dominators[block] = edge;
68 }
69 }
70 }
71
is_back_edge(uint32_t to) const72 bool CFG::is_back_edge(uint32_t to) const
73 {
74 // We have a back edge if the visit order is set with the temporary magic value 0.
75 // Crossing edges will have already been recorded with a visit order.
76 auto itr = visit_order.find(to);
77 return itr != end(visit_order) && itr->second.get() == 0;
78 }
79
has_visited_forward_edge(uint32_t to) const80 bool CFG::has_visited_forward_edge(uint32_t to) const
81 {
82 // If > 0, we have visited the edge already, and this is not a back edge branch.
83 auto itr = visit_order.find(to);
84 return itr != end(visit_order) && itr->second.get() > 0;
85 }
86
post_order_visit(uint32_t block_id)87 bool CFG::post_order_visit(uint32_t block_id)
88 {
89 // If we have already branched to this block (back edge), stop recursion.
90 // If our branches are back-edges, we do not record them.
91 // We have to record crossing edges however.
92 if (has_visited_forward_edge(block_id))
93 return true;
94 else if (is_back_edge(block_id))
95 return false;
96
97 // Block back-edges from recursively revisiting ourselves.
98 visit_order[block_id].get() = 0;
99
100 auto &block = compiler.get<SPIRBlock>(block_id);
101
102 // If this is a loop header, add an implied branch to the merge target.
103 // This is needed to avoid annoying cases with do { ... } while(false) loops often generated by inliners.
104 // To the CFG, this is linear control flow, but we risk picking the do/while scope as our dominating block.
105 // This makes sure that if we are accessing a variable outside the do/while, we choose the loop header as dominator.
106 // We could use has_visited_forward_edge, but this break code-gen where the merge block is unreachable in the CFG.
107
108 // Make a point out of visiting merge target first. This is to make sure that post visit order outside the loop
109 // is lower than inside the loop, which is going to be key for some traversal algorithms like post-dominance analysis.
110 // For selection constructs true/false blocks will end up visiting the merge block directly and it works out fine,
111 // but for loops, only the header might end up actually branching to merge block.
112 if (block.merge == SPIRBlock::MergeLoop && post_order_visit(block.merge_block))
113 add_branch(block_id, block.merge_block);
114
115 // First visit our branch targets.
116 switch (block.terminator)
117 {
118 case SPIRBlock::Direct:
119 if (post_order_visit(block.next_block))
120 add_branch(block_id, block.next_block);
121 break;
122
123 case SPIRBlock::Select:
124 if (post_order_visit(block.true_block))
125 add_branch(block_id, block.true_block);
126 if (post_order_visit(block.false_block))
127 add_branch(block_id, block.false_block);
128 break;
129
130 case SPIRBlock::MultiSelect:
131 for (auto &target : block.cases)
132 {
133 if (post_order_visit(target.block))
134 add_branch(block_id, target.block);
135 }
136 if (block.default_block && post_order_visit(block.default_block))
137 add_branch(block_id, block.default_block);
138 break;
139
140 default:
141 break;
142 }
143
144 // If this is a selection merge, add an implied branch to the merge target.
145 // This is needed to avoid cases where an inner branch dominates the outer branch.
146 // This can happen if one of the branches exit early, e.g.:
147 // if (cond) { ...; break; } else { var = 100 } use_var(var);
148 // We can use the variable without a Phi since there is only one possible parent here.
149 // However, in this case, we need to hoist out the inner variable to outside the branch.
150 // Use same strategy as loops.
151 if (block.merge == SPIRBlock::MergeSelection && post_order_visit(block.next_block))
152 {
153 // If there is only one preceding edge to the merge block and it's not ourselves, we need a fixup.
154 // Add a fake branch so any dominator in either the if (), or else () block, or a lone case statement
155 // will be hoisted out to outside the selection merge.
156 // If size > 1, the variable will be automatically hoisted, so we should not mess with it.
157 // The exception here is switch blocks, where we can have multiple edges to merge block,
158 // all coming from same scope, so be more conservative in this case.
159 // Adding fake branches unconditionally breaks parameter preservation analysis,
160 // which looks at how variables are accessed through the CFG.
161 auto pred_itr = preceding_edges.find(block.next_block);
162 if (pred_itr != end(preceding_edges))
163 {
164 auto &pred = pred_itr->second;
165 auto succ_itr = succeeding_edges.find(block_id);
166 size_t num_succeeding_edges = 0;
167 if (succ_itr != end(succeeding_edges))
168 num_succeeding_edges = succ_itr->second.size();
169
170 if (block.terminator == SPIRBlock::MultiSelect && num_succeeding_edges == 1)
171 {
172 // Multiple branches can come from the same scope due to "break;", so we need to assume that all branches
173 // come from same case scope in worst case, even if there are multiple preceding edges.
174 // If we have more than one succeeding edge from the block header, it should be impossible
175 // to have a dominator be inside the block.
176 // Only case this can go wrong is if we have 2 or more edges from block header and
177 // 2 or more edges to merge block, and still have dominator be inside a case label.
178 if (!pred.empty())
179 add_branch(block_id, block.next_block);
180 }
181 else
182 {
183 if (pred.size() == 1 && *pred.begin() != block_id)
184 add_branch(block_id, block.next_block);
185 }
186 }
187 else
188 {
189 // If the merge block does not have any preceding edges, i.e. unreachable, hallucinate it.
190 // We're going to do code-gen for it, and domination analysis requires that we have at least one preceding edge.
191 add_branch(block_id, block.next_block);
192 }
193 }
194
195 // Then visit ourselves. Start counting at one, to let 0 be a magic value for testing back vs. crossing edges.
196 visit_order[block_id].get() = ++visit_count;
197 post_order.push_back(block_id);
198 return true;
199 }
200
build_post_order_visit_order()201 void CFG::build_post_order_visit_order()
202 {
203 uint32_t block = func.entry_block;
204 visit_count = 0;
205 visit_order.clear();
206 post_order.clear();
207 post_order_visit(block);
208 }
209
add_branch(uint32_t from,uint32_t to)210 void CFG::add_branch(uint32_t from, uint32_t to)
211 {
212 const auto add_unique = [](SmallVector<uint32_t> &l, uint32_t value) {
213 auto itr = find(begin(l), end(l), value);
214 if (itr == end(l))
215 l.push_back(value);
216 };
217 add_unique(preceding_edges[to], from);
218 add_unique(succeeding_edges[from], to);
219 }
220
find_loop_dominator(uint32_t block_id) const221 uint32_t CFG::find_loop_dominator(uint32_t block_id) const
222 {
223 while (block_id != SPIRBlock::NoDominator)
224 {
225 auto itr = preceding_edges.find(block_id);
226 if (itr == end(preceding_edges))
227 return SPIRBlock::NoDominator;
228 if (itr->second.empty())
229 return SPIRBlock::NoDominator;
230
231 uint32_t pred_block_id = SPIRBlock::NoDominator;
232 bool ignore_loop_header = false;
233
234 // If we are a merge block, go directly to the header block.
235 // Only consider a loop dominator if we are branching from inside a block to a loop header.
236 // NOTE: In the CFG we forced an edge from header to merge block always to support variable scopes properly.
237 for (auto &pred : itr->second)
238 {
239 auto &pred_block = compiler.get<SPIRBlock>(pred);
240 if (pred_block.merge == SPIRBlock::MergeLoop && pred_block.merge_block == ID(block_id))
241 {
242 pred_block_id = pred;
243 ignore_loop_header = true;
244 break;
245 }
246 else if (pred_block.merge == SPIRBlock::MergeSelection && pred_block.next_block == ID(block_id))
247 {
248 pred_block_id = pred;
249 break;
250 }
251 }
252
253 // No merge block means we can just pick any edge. Loop headers dominate the inner loop, so any path we
254 // take will lead there.
255 if (pred_block_id == SPIRBlock::NoDominator)
256 pred_block_id = itr->second.front();
257
258 block_id = pred_block_id;
259
260 if (!ignore_loop_header && block_id)
261 {
262 auto &block = compiler.get<SPIRBlock>(block_id);
263 if (block.merge == SPIRBlock::MergeLoop)
264 return block_id;
265 }
266 }
267
268 return block_id;
269 }
270
node_terminates_control_flow_in_sub_graph(BlockID from,BlockID to) const271 bool CFG::node_terminates_control_flow_in_sub_graph(BlockID from, BlockID to) const
272 {
273 // Walk backwards, starting from "to" block.
274 // Only follow pred edges if they have a 1:1 relationship, or a merge relationship.
275 // If we cannot find a path to "from", we must assume that to is inside control flow in some way.
276
277 auto &from_block = compiler.get<SPIRBlock>(from);
278 BlockID ignore_block_id = 0;
279 if (from_block.merge == SPIRBlock::MergeLoop)
280 ignore_block_id = from_block.merge_block;
281
282 while (to != from)
283 {
284 auto pred_itr = preceding_edges.find(to);
285 if (pred_itr == end(preceding_edges))
286 return false;
287
288 DominatorBuilder builder(*this);
289 for (auto &edge : pred_itr->second)
290 builder.add_block(edge);
291
292 uint32_t dominator = builder.get_dominator();
293 if (dominator == 0)
294 return false;
295
296 auto &dom = compiler.get<SPIRBlock>(dominator);
297
298 bool true_path_ignore = false;
299 bool false_path_ignore = false;
300 if (ignore_block_id && dom.terminator == SPIRBlock::Select)
301 {
302 auto &true_block = compiler.get<SPIRBlock>(dom.true_block);
303 auto &false_block = compiler.get<SPIRBlock>(dom.false_block);
304 auto &ignore_block = compiler.get<SPIRBlock>(ignore_block_id);
305 true_path_ignore = compiler.execution_is_branchless(true_block, ignore_block);
306 false_path_ignore = compiler.execution_is_branchless(false_block, ignore_block);
307 }
308
309 if ((dom.merge == SPIRBlock::MergeSelection && dom.next_block == to) ||
310 (dom.merge == SPIRBlock::MergeLoop && dom.merge_block == to) ||
311 (dom.terminator == SPIRBlock::Direct && dom.next_block == to) ||
312 (dom.terminator == SPIRBlock::Select && dom.true_block == to && false_path_ignore) ||
313 (dom.terminator == SPIRBlock::Select && dom.false_block == to && true_path_ignore))
314 {
315 // Allow walking selection constructs if the other branch reaches out of a loop construct.
316 // It cannot be in-scope anymore.
317 to = dominator;
318 }
319 else
320 return false;
321 }
322
323 return true;
324 }
325
DominatorBuilder(const CFG & cfg_)326 DominatorBuilder::DominatorBuilder(const CFG &cfg_)
327 : cfg(cfg_)
328 {
329 }
330
add_block(uint32_t block)331 void DominatorBuilder::add_block(uint32_t block)
332 {
333 if (!cfg.get_immediate_dominator(block))
334 {
335 // Unreachable block via the CFG, we will never emit this code anyways.
336 return;
337 }
338
339 if (!dominator)
340 {
341 dominator = block;
342 return;
343 }
344
345 if (block != dominator)
346 dominator = cfg.find_common_dominator(block, dominator);
347 }
348
lift_continue_block_dominator()349 void DominatorBuilder::lift_continue_block_dominator()
350 {
351 // It is possible for a continue block to be the dominator of a variable is only accessed inside the while block of a do-while loop.
352 // We cannot safely declare variables inside a continue block, so move any variable declared
353 // in a continue block to the entry block to simplify.
354 // It makes very little sense for a continue block to ever be a dominator, so fall back to the simplest
355 // solution.
356
357 if (!dominator)
358 return;
359
360 auto &block = cfg.get_compiler().get<SPIRBlock>(dominator);
361 auto post_order = cfg.get_visit_order(dominator);
362
363 // If we are branching to a block with a higher post-order traversal index (continue blocks), we have a problem
364 // since we cannot create sensible GLSL code for this, fallback to entry block.
365 bool back_edge_dominator = false;
366 switch (block.terminator)
367 {
368 case SPIRBlock::Direct:
369 if (cfg.get_visit_order(block.next_block) > post_order)
370 back_edge_dominator = true;
371 break;
372
373 case SPIRBlock::Select:
374 if (cfg.get_visit_order(block.true_block) > post_order)
375 back_edge_dominator = true;
376 if (cfg.get_visit_order(block.false_block) > post_order)
377 back_edge_dominator = true;
378 break;
379
380 case SPIRBlock::MultiSelect:
381 for (auto &target : block.cases)
382 {
383 if (cfg.get_visit_order(target.block) > post_order)
384 back_edge_dominator = true;
385 }
386 if (block.default_block && cfg.get_visit_order(block.default_block) > post_order)
387 back_edge_dominator = true;
388 break;
389
390 default:
391 break;
392 }
393
394 if (back_edge_dominator)
395 dominator = cfg.get_function().entry_block;
396 }
397 } // namespace SPIRV_CROSS_NAMESPACE
398