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

source code of qtshadertools/src/3rdparty/SPIRV-Cross/spirv_cfg.cpp