2
* Copyright © 2020 Julian Winkler
4
* Permission is hereby granted, free of charge, to any person obtaining a
5
* copy of this software and associated documentation files (the "Software"),
6
* to deal in the Software without restriction, including without limitation
7
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
8
* and/or sell copies of the Software, and to permit persons to whom the
9
* Software is furnished to do so, subject to the following conditions:
11
* The above copyright notice and this permission notice (including the next
12
* paragraph) shall be included in all copies or substantial portions of the
15
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
25
#include "nir_builder.h"
28
#define NIR_LOWER_GOTO_IFS_DEBUG 0
31
/** Set of blocks which this path represents
33
* It's "reachable" not in the sense that these are all the nodes reachable
34
* through this path but in the sense that, when you see one of these
35
* blocks, you know you've reached this path.
37
struct set *reachable;
39
/** Fork in the path, if reachable->entries > 1 */
40
struct path_fork *fork;
46
nir_variable *path_var;
47
nir_ssa_def *path_ssa;
56
struct routes *loop_backup;
60
struct list_head link;
62
/** Set of blocks at the current level */
65
/** Path for the next level */
68
/** Reach set from inside_outside if irreducable */
71
/** True if a skip region starts with this level */
74
/** True if a skip region ends with this level */
77
/** True if this level is irreducable */
82
nir_block_ptr_cmp(const void *_a, const void *_b)
84
const nir_block *const *a = _a;
85
const nir_block *const *b = _b;
86
return (int)(*a)->index - (int)(*b)->index;
90
print_block_set(const struct set *set)
95
set_foreach(set, entry) {
98
printf("%u", ((nir_block *)entry->key)->index);
104
/** Return a sorted array of blocks for a set
106
* Hash set ordering is non-deterministic. We hash based on pointers and so,
107
* if any pointer ever changes from one run to another, the order of the set
108
* may change. Any time we're going to make decisions which may affect the
109
* final structure which may depend on ordering, we should first sort the
113
sorted_block_arr_for_set(const struct set *block_set, void *mem_ctx)
115
const unsigned num_blocks = block_set->entries;
116
nir_block **block_arr = ralloc_array(mem_ctx, nir_block *, num_blocks);
118
set_foreach(block_set, entry)
119
block_arr[i++] = (nir_block *)entry->key;
120
assert(i == num_blocks);
121
qsort(block_arr, num_blocks, sizeof(*block_arr), nir_block_ptr_cmp);
126
block_for_singular_set(const struct set *block_set)
128
assert(block_set->entries == 1);
129
return (nir_block *)_mesa_set_next_entry(block_set, NULL)->key;
133
* Sets all path variables to reach the target block via a fork
136
set_path_vars(nir_builder *b, struct path_fork *fork, nir_block *target)
139
for (int i = 0; i < 2; i++) {
140
if (_mesa_set_search(fork->paths[i].reachable, target)) {
142
nir_store_var(b, fork->path_var, nir_imm_bool(b, i), 1);
144
assert(fork->path_ssa == NULL);
145
fork->path_ssa = nir_imm_bool(b, i);
147
fork = fork->paths[i].fork;
155
* Sets all path variables to reach the both target blocks via a fork.
156
* If the blocks are in different fork paths, the condition will be used.
157
* As the fork is already created, the then and else blocks may be swapped,
158
* in this case the condition is inverted
161
set_path_vars_cond(nir_builder *b, struct path_fork *fork, nir_src condition,
162
nir_block *then_block, nir_block *else_block)
166
for (i = 0; i < 2; i++) {
167
if (_mesa_set_search(fork->paths[i].reachable, then_block)) {
168
if (_mesa_set_search(fork->paths[i].reachable, else_block)) {
170
nir_store_var(b, fork->path_var, nir_imm_bool(b, i), 1);
172
assert(fork->path_ssa == NULL);
173
fork->path_ssa = nir_imm_bool(b, i);
175
fork = fork->paths[i].fork;
179
assert(condition.is_ssa);
180
nir_ssa_def *ssa_def = condition.ssa;
181
assert(ssa_def->bit_size == 1);
182
assert(ssa_def->num_components == 1);
184
ssa_def = nir_inot(b, ssa_def);
186
nir_store_var(b, fork->path_var, ssa_def, 1);
188
assert(fork->path_ssa == NULL);
189
fork->path_ssa = ssa_def;
191
set_path_vars(b, fork->paths[i].fork, then_block);
192
set_path_vars(b, fork->paths[!i].fork, else_block);
202
* Sets all path variables and places the right jump instruction to reach the
206
route_to(nir_builder *b, struct routes *routing, nir_block *target)
208
if (_mesa_set_search(routing->regular.reachable, target)) {
209
set_path_vars(b, routing->regular.fork, target);
211
else if (_mesa_set_search(routing->brk.reachable, target)) {
212
set_path_vars(b, routing->brk.fork, target);
213
nir_jump(b, nir_jump_break);
215
else if (_mesa_set_search(routing->cont.reachable, target)) {
216
set_path_vars(b, routing->cont.fork, target);
217
nir_jump(b, nir_jump_continue);
220
assert(!target->successors[0]); /* target is endblock */
221
nir_jump(b, nir_jump_return);
226
* Sets path vars and places the right jump instr to reach one of the two
227
* target blocks based on the condition. If the targets need different jump
228
* istructions, they will be placed into an if else statement.
229
* This can happen if one target is the loop head
237
route_to_cond(nir_builder *b, struct routes *routing, nir_src condition,
238
nir_block *then_block, nir_block *else_block)
240
if (_mesa_set_search(routing->regular.reachable, then_block)) {
241
if (_mesa_set_search(routing->regular.reachable, else_block)) {
242
set_path_vars_cond(b, routing->regular.fork, condition,
243
then_block, else_block);
246
} else if (_mesa_set_search(routing->brk.reachable, then_block)) {
247
if (_mesa_set_search(routing->brk.reachable, else_block)) {
248
set_path_vars_cond(b, routing->brk.fork, condition,
249
then_block, else_block);
250
nir_jump(b, nir_jump_break);
253
} else if (_mesa_set_search(routing->cont.reachable, then_block)) {
254
if (_mesa_set_search(routing->cont.reachable, else_block)) {
255
set_path_vars_cond(b, routing->cont.fork, condition,
256
then_block, else_block);
257
nir_jump(b, nir_jump_continue);
262
/* then and else blocks are in different routes */
263
nir_push_if_src(b, condition);
264
route_to(b, routing, then_block);
265
nir_push_else(b, NULL);
266
route_to(b, routing, else_block);
271
* Merges the reachable sets of both fork subpaths into the forks entire
275
fork_reachable(struct path_fork *fork)
277
struct set *reachable = _mesa_set_clone(fork->paths[0].reachable, fork);
278
set_foreach(fork->paths[1].reachable, entry)
279
_mesa_set_add_pre_hashed(reachable, entry->hash, entry->key);
284
* Modifies the routing to be the routing inside a loop. The old regular path
285
* becomes the new break path. The loop in path becomes the new regular and
287
* The lost routing information is stacked into the loop_backup stack.
288
* Also creates helper vars for multilevel loop jumping if needed.
289
* Also calls the nir builder to build the loop
292
loop_routing_start(struct routes *routing, nir_builder *b,
293
struct path loop_path, struct set *reach,
296
if (NIR_LOWER_GOTO_IFS_DEBUG) {
297
printf("loop_routing_start:\n");
299
print_block_set(reach);
300
printf(" loop_path.reachable = ");
301
print_block_set(loop_path.reachable);
302
printf(" routing->regular.reachable = ");
303
print_block_set(routing->regular.reachable);
304
printf(" routing->brk.reachable = ");
305
print_block_set(routing->brk.reachable);
306
printf(" routing->cont.reachable = ");
307
print_block_set(routing->cont.reachable);
311
struct routes *routing_backup = rzalloc(mem_ctx, struct routes);
312
*routing_backup = *routing;
313
bool break_needed = false;
314
bool continue_needed = false;
316
set_foreach(reach, entry) {
317
if (_mesa_set_search(loop_path.reachable, entry->key))
319
if (_mesa_set_search(routing->regular.reachable, entry->key))
321
if (_mesa_set_search(routing->brk.reachable, entry->key)) {
325
assert(_mesa_set_search(routing->cont.reachable, entry->key));
326
continue_needed = true;
329
routing->brk = routing_backup->regular;
330
routing->cont = loop_path;
331
routing->regular = loop_path;
332
routing->loop_backup = routing_backup;
335
struct path_fork *fork = rzalloc(mem_ctx, struct path_fork);
337
fork->path_var = nir_local_variable_create(b->impl, glsl_bool_type(),
339
fork->paths[0] = routing->brk;
340
fork->paths[1] = routing_backup->brk;
341
routing->brk.fork = fork;
342
routing->brk.reachable = fork_reachable(fork);
344
if (continue_needed) {
345
struct path_fork *fork = rzalloc(mem_ctx, struct path_fork);
347
fork->path_var = nir_local_variable_create(b->impl, glsl_bool_type(),
349
fork->paths[0] = routing->brk;
350
fork->paths[1] = routing_backup->cont;
351
routing->brk.fork = fork;
352
routing->brk.reachable = fork_reachable(fork);
358
* Gets a forks condition as ssa def if the condition is inside a helper var,
359
* the variable will be read into an ssa def
362
fork_condition(nir_builder *b, struct path_fork *fork)
366
ret = nir_load_var(b, fork->path_var);
369
ret = fork->path_ssa;
374
* Restores the routing after leaving a loop based on the loop_backup stack.
375
* Also handles multi level jump helper vars if existing and calls the nir
376
* builder to pop the nir loop
379
loop_routing_end(struct routes *routing, nir_builder *b)
381
struct routes *routing_backup = routing->loop_backup;
382
assert(routing->cont.fork == routing->regular.fork);
383
assert(routing->cont.reachable == routing->regular.reachable);
384
nir_pop_loop(b, NULL);
385
if (routing->brk.fork && routing->brk.fork->paths[1].reachable ==
386
routing_backup->cont.reachable) {
387
assert(!(routing->brk.fork->is_var &&
388
strcmp(routing->brk.fork->path_var->name, "path_continue")));
389
nir_push_if_src(b, nir_src_for_ssa(
390
fork_condition(b, routing->brk.fork)));
391
nir_jump(b, nir_jump_continue);
393
routing->brk = routing->brk.fork->paths[0];
395
if (routing->brk.fork && routing->brk.fork->paths[1].reachable ==
396
routing_backup->brk.reachable) {
397
assert(!(routing->brk.fork->is_var &&
398
strcmp(routing->brk.fork->path_var->name, "path_break")));
399
nir_push_if_src(b, nir_src_for_ssa(
400
fork_condition(b, routing->brk.fork)));
401
nir_jump(b, nir_jump_break);
403
routing->brk = routing->brk.fork->paths[0];
405
assert(routing->brk.fork == routing_backup->regular.fork);
406
assert(routing->brk.reachable == routing_backup->regular.reachable);
407
*routing = *routing_backup;
408
ralloc_free(routing_backup);
412
* generates a list of all blocks dominated by the loop header, but the
413
* control flow can't go back to the loop header from the block.
414
* also generates a list of all blocks that can be reached from within the
422
* here B and C are directly dominated by A but only C can reach back to the
423
* loop head A. B will be added to the outside set and to the reach set.
424
* \param loop_heads set of loop heads. All blocks inside the loop will be
426
* \param outside all blocks directly outside the loop will be added
427
* \param reach all blocks reachable from the loop will be added
430
inside_outside(nir_block *block, struct set *loop_heads, struct set *outside,
431
struct set *reach, struct set *brk_reachable, void *mem_ctx)
433
assert(_mesa_set_search(loop_heads, block));
434
struct set *remaining = _mesa_pointer_set_create(mem_ctx);
435
for (int i = 0; i < block->num_dom_children; i++) {
436
if (!_mesa_set_search(brk_reachable, block->dom_children[i]))
437
_mesa_set_add(remaining, block->dom_children[i]);
441
if (NIR_LOWER_GOTO_IFS_DEBUG) {
442
printf("inside_outside(%u):\n", block->index);
443
printf(" loop_heads = ");
444
print_block_set(loop_heads);
446
print_block_set(reach);
447
printf(" brk_reach = ");
448
print_block_set(brk_reachable);
449
printf(" remaining = ");
450
print_block_set(remaining);
454
bool progress = true;
455
while (remaining->entries && progress) {
457
set_foreach(remaining, child_entry) {
458
nir_block *dom_child = (nir_block *) child_entry->key;
459
bool can_jump_back = false;
460
set_foreach(dom_child->dom_frontier, entry) {
461
if (entry->key == dom_child)
463
if (_mesa_set_search_pre_hashed(remaining, entry->hash,
465
can_jump_back = true;
468
if (_mesa_set_search_pre_hashed(loop_heads, entry->hash,
470
can_jump_back = true;
474
if (!can_jump_back) {
475
_mesa_set_add_pre_hashed(outside, child_entry->hash,
477
_mesa_set_remove(remaining, child_entry);
483
/* Add everything remaining to loop_heads */
484
set_foreach(remaining, entry)
485
_mesa_set_add_pre_hashed(loop_heads, entry->hash, entry->key);
487
/* Recurse for each remaining */
488
set_foreach(remaining, entry) {
489
inside_outside((nir_block *) entry->key, loop_heads, outside, reach,
490
brk_reachable, mem_ctx);
493
for (int i = 0; i < 2; i++) {
494
if (block->successors[i] && block->successors[i]->successors[0] &&
495
!_mesa_set_search(loop_heads, block->successors[i])) {
496
_mesa_set_add(reach, block->successors[i]);
500
if (NIR_LOWER_GOTO_IFS_DEBUG) {
501
printf("outside(%u) = ", block->index);
502
print_block_set(outside);
503
printf("reach(%u) = ", block->index);
504
print_block_set(reach);
508
static struct path_fork *
509
select_fork_recur(struct nir_block **blocks, unsigned start, unsigned end,
510
nir_function_impl *impl, bool need_var, void *mem_ctx)
512
if (start == end - 1)
515
struct path_fork *fork = rzalloc(mem_ctx, struct path_fork);
516
fork->is_var = need_var;
518
fork->path_var = nir_local_variable_create(impl, glsl_bool_type(),
521
unsigned mid = start + (end - start) / 2;
523
fork->paths[0].reachable = _mesa_pointer_set_create(fork);
524
for (unsigned i = start; i < mid; i++)
525
_mesa_set_add(fork->paths[0].reachable, blocks[i]);
526
fork->paths[0].fork =
527
select_fork_recur(blocks, start, mid, impl, need_var, mem_ctx);
529
fork->paths[1].reachable = _mesa_pointer_set_create(fork);
530
for (unsigned i = mid; i < end; i++)
531
_mesa_set_add(fork->paths[1].reachable, blocks[i]);
532
fork->paths[1].fork =
533
select_fork_recur(blocks, mid, end, impl, need_var, mem_ctx);
539
* Gets a set of blocks organized into the same level by the organize_levels
540
* function and creates enough forks to be able to route to them.
541
* If the set only contains one block, the function has nothing to do.
542
* The set should almost never contain more than two blocks, but if so,
543
* then the function calls itself recursively
545
static struct path_fork *
546
select_fork(struct set *reachable, nir_function_impl *impl, bool need_var,
549
assert(reachable->entries > 0);
550
if (reachable->entries <= 1)
553
/* Hash set ordering is non-deterministic. We're about to turn a set into
554
* a tree so we really want things to be in a deterministic ordering.
556
return select_fork_recur(sorted_block_arr_for_set(reachable, mem_ctx),
557
0, reachable->entries, impl, need_var, mem_ctx);
561
* gets called when the organize_levels functions fails to find blocks that
562
* can't be reached by the other remaining blocks. This means, at least two
563
* dominance sibling blocks can reach each other. So we have a multi entry
564
* loop. This function tries to find the smallest possible set of blocks that
565
* must be part of the multi entry loop.
572
* The function choses a random block as candidate. for example C
573
* The function checks which remaining blocks can reach C, in this case A.
574
* So A becomes the new candidate and C is removed from the result set.
576
* So B becomes the new candidate and A is removed from the set.
578
* A was an old candidate. So it is added to the set containing B.
579
* No other remaining blocks can reach A or B.
580
* So only A and B must be part of the multi entry loop.
583
handle_irreducible(struct set *remaining, struct strct_lvl *curr_level,
584
struct set *brk_reachable, void *mem_ctx)
586
nir_block *candidate = (nir_block *)
587
_mesa_set_next_entry(remaining, NULL)->key;
588
struct set *old_candidates = _mesa_pointer_set_create(mem_ctx);
590
_mesa_set_add(old_candidates, candidate);
592
/* Start with just the candidate block */
593
_mesa_set_clear(curr_level->blocks, NULL);
594
_mesa_set_add(curr_level->blocks, candidate);
597
set_foreach(remaining, entry) {
598
nir_block *remaining_block = (nir_block *) entry->key;
599
if (!_mesa_set_search(curr_level->blocks, remaining_block) &&
600
_mesa_set_intersects(remaining_block->dom_frontier,
601
curr_level->blocks)) {
602
if (_mesa_set_search(old_candidates, remaining_block)) {
603
_mesa_set_add(curr_level->blocks, remaining_block);
605
candidate = remaining_block;
611
_mesa_set_destroy(old_candidates, NULL);
612
old_candidates = NULL;
614
struct set *loop_heads = _mesa_set_clone(curr_level->blocks, curr_level);
615
curr_level->reach = _mesa_pointer_set_create(curr_level);
616
set_foreach(curr_level->blocks, entry) {
617
_mesa_set_remove_key(remaining, entry->key);
618
inside_outside((nir_block *) entry->key, loop_heads, remaining,
619
curr_level->reach, brk_reachable, mem_ctx);
621
_mesa_set_destroy(loop_heads, NULL);
625
* organize a set of blocks into a list of levels. Where every level contains
626
* one or more blocks. So that every block is before all blocks it can reach.
627
* Also creates all path variables needed, for the control flow between the
629
* For example if the control flow looks like this:
637
* B, C, E and F are dominance children of A
638
* The level list should look like this:
639
* blocks irreducible conditional
640
* level 0 B, C false false
641
* level 1 E false true
642
* level 2 F false false
643
* The final structure should look like this:
650
* if (path_conditional) {
655
* \param levels uninitialized list
656
* \param is_dominated if true, no helper variables will be created for the
660
organize_levels(struct list_head *levels, struct set *remaining,
661
struct set *reach, struct routes *routing,
662
nir_function_impl *impl, bool is_domminated, void *mem_ctx)
664
if (NIR_LOWER_GOTO_IFS_DEBUG) {
665
printf("organize_levels:\n");
667
print_block_set(reach);
670
/* blocks that can be reached by the remaining blocks */
671
struct set *remaining_frontier = _mesa_pointer_set_create(mem_ctx);
673
/* targets of active skip path */
674
struct set *skip_targets = _mesa_pointer_set_create(mem_ctx);
676
list_inithead(levels);
677
while (remaining->entries) {
678
_mesa_set_clear(remaining_frontier, NULL);
679
set_foreach(remaining, entry) {
680
nir_block *remain_block = (nir_block *) entry->key;
681
set_foreach(remain_block->dom_frontier, frontier_entry) {
682
nir_block *frontier = (nir_block *) frontier_entry->key;
683
if (frontier != remain_block) {
684
_mesa_set_add(remaining_frontier, frontier);
689
struct strct_lvl *curr_level = rzalloc(mem_ctx, struct strct_lvl);
690
curr_level->blocks = _mesa_pointer_set_create(curr_level);
691
set_foreach(remaining, entry) {
692
nir_block *candidate = (nir_block *) entry->key;
693
if (!_mesa_set_search(remaining_frontier, candidate)) {
694
_mesa_set_add(curr_level->blocks, candidate);
695
_mesa_set_remove_key(remaining, candidate);
699
curr_level->irreducible = !curr_level->blocks->entries;
700
if (curr_level->irreducible) {
701
handle_irreducible(remaining, curr_level,
702
routing->brk.reachable, mem_ctx);
704
assert(curr_level->blocks->entries);
706
struct strct_lvl *prev_level = NULL;
707
if (!list_is_empty(levels))
708
prev_level = list_last_entry(levels, struct strct_lvl, link);
710
set_foreach(skip_targets, entry) {
711
if (_mesa_set_search_pre_hashed(curr_level->blocks,
712
entry->hash, entry->key)) {
713
_mesa_set_remove(skip_targets, entry);
714
prev_level->skip_end = 1;
717
curr_level->skip_start = skip_targets->entries != 0;
719
struct set *prev_frontier = NULL;
721
prev_frontier = _mesa_set_clone(reach, curr_level);
722
} else if (prev_level->irreducible) {
723
prev_frontier = _mesa_set_clone(prev_level->reach, curr_level);
726
set_foreach(curr_level->blocks, blocks_entry) {
727
nir_block *level_block = (nir_block *) blocks_entry->key;
728
if (prev_frontier == NULL) {
730
_mesa_set_clone(level_block->dom_frontier, curr_level);
732
set_foreach(level_block->dom_frontier, entry)
733
_mesa_set_add_pre_hashed(prev_frontier, entry->hash,
738
bool is_in_skip = skip_targets->entries != 0;
739
set_foreach(prev_frontier, entry) {
740
if (_mesa_set_search(remaining, entry->key) ||
741
(_mesa_set_search(routing->regular.reachable, entry->key) &&
742
!_mesa_set_search(routing->brk.reachable, entry->key) &&
743
!_mesa_set_search(routing->cont.reachable, entry->key))) {
744
_mesa_set_add_pre_hashed(skip_targets, entry->hash, entry->key);
746
prev_level->skip_end = 1;
747
curr_level->skip_start = 1;
751
curr_level->skip_end = 0;
752
list_addtail(&curr_level->link, levels);
755
if (NIR_LOWER_GOTO_IFS_DEBUG) {
756
printf(" levels:\n");
757
list_for_each_entry(struct strct_lvl, level, levels, link) {
759
print_block_set(level->blocks);
764
if (skip_targets->entries)
765
list_last_entry(levels, struct strct_lvl, link)->skip_end = 1;
767
/* Iterate throught all levels reverse and create all the paths and forks */
768
struct path path_after_skip;
770
list_for_each_entry_rev(struct strct_lvl, level, levels, link) {
771
bool need_var = !(is_domminated && level->link.prev == levels);
772
level->out_path = routing->regular;
773
if (level->skip_end) {
774
path_after_skip = routing->regular;
776
routing->regular.reachable = level->blocks;
777
routing->regular.fork = select_fork(routing->regular.reachable, impl,
779
if (level->skip_start) {
780
struct path_fork *fork = rzalloc(mem_ctx, struct path_fork);
781
fork->is_var = need_var;
783
fork->path_var = nir_local_variable_create(impl, glsl_bool_type(),
785
fork->paths[0] = path_after_skip;
786
fork->paths[1] = routing->regular;
787
routing->regular.fork = fork;
788
routing->regular.reachable = fork_reachable(fork);
794
nir_structurize(struct routes *routing, nir_builder *b,
795
nir_block *block, void *mem_ctx);
798
* Places all the if else statements to select between all blocks in a select
802
select_blocks(struct routes *routing, nir_builder *b,
803
struct path in_path, void *mem_ctx)
806
nir_block *block = block_for_singular_set(in_path.reachable);
807
nir_structurize(routing, b, block, mem_ctx);
809
assert(!(in_path.fork->is_var &&
810
strcmp(in_path.fork->path_var->name, "path_select")));
811
nir_push_if_src(b, nir_src_for_ssa(fork_condition(b, in_path.fork)));
812
select_blocks(routing, b, in_path.fork->paths[1], mem_ctx);
813
nir_push_else(b, NULL);
814
select_blocks(routing, b, in_path.fork->paths[0], mem_ctx);
820
* Builds the structurized nir code by the final level list.
823
plant_levels(struct list_head *levels, struct routes *routing,
824
nir_builder *b, void *mem_ctx)
826
/* Place all dominated blocks and build the path forks */
827
list_for_each_entry(struct strct_lvl, level, levels, link) {
828
if (level->skip_start) {
829
assert(routing->regular.fork);
830
assert(!(routing->regular.fork->is_var && strcmp(
831
routing->regular.fork->path_var->name, "path_conditional")));
832
nir_push_if_src(b, nir_src_for_ssa(
833
fork_condition(b, routing->regular.fork)));
834
routing->regular = routing->regular.fork->paths[1];
836
struct path in_path = routing->regular;
837
routing->regular = level->out_path;
838
if (level->irreducible)
839
loop_routing_start(routing, b, in_path, level->reach, mem_ctx);
840
select_blocks(routing, b, in_path, mem_ctx);
841
if (level->irreducible)
842
loop_routing_end(routing, b);
849
* builds the control flow of a block and all its dominance children
850
* \param routing the routing after the block and all dominated blocks
853
nir_structurize(struct routes *routing, nir_builder *b, nir_block *block,
856
struct set *remaining = _mesa_pointer_set_create(mem_ctx);
857
for (int i = 0; i < block->num_dom_children; i++) {
858
if (!_mesa_set_search(routing->brk.reachable, block->dom_children[i]))
859
_mesa_set_add(remaining, block->dom_children[i]);
862
/* If the block can reach back to itself, it is a loop head */
863
int is_looped = _mesa_set_search(block->dom_frontier, block) != NULL;
864
struct list_head outside_levels;
866
struct set *loop_heads = _mesa_pointer_set_create(mem_ctx);
867
_mesa_set_add(loop_heads, block);
869
struct set *outside = _mesa_pointer_set_create(mem_ctx);
870
struct set *reach = _mesa_pointer_set_create(mem_ctx);
871
inside_outside(block, loop_heads, outside, reach,
872
routing->brk.reachable, mem_ctx);
874
set_foreach(outside, entry)
875
_mesa_set_remove_key(remaining, entry->key);
877
organize_levels(&outside_levels, outside, reach, routing, b->impl,
880
struct path loop_path = {
881
.reachable = _mesa_pointer_set_create(mem_ctx),
884
_mesa_set_add(loop_path.reachable, block);
886
loop_routing_start(routing, b, loop_path, reach, mem_ctx);
889
struct set *reach = _mesa_pointer_set_create(mem_ctx);
890
if (block->successors[0]->successors[0]) /* it is not the end_block */
891
_mesa_set_add(reach, block->successors[0]);
892
if (block->successors[1] && block->successors[1]->successors[0])
893
_mesa_set_add(reach, block->successors[1]);
895
struct list_head levels;
896
organize_levels(&levels, remaining, reach, routing, b->impl, true, mem_ctx);
898
/* Push all instructions of this block, without the jump instr */
899
nir_jump_instr *jump_instr = NULL;
900
nir_foreach_instr_safe(instr, block) {
901
if (instr->type == nir_instr_type_jump) {
902
jump_instr = nir_instr_as_jump(instr);
905
nir_instr_remove(instr);
906
nir_builder_instr_insert(b, instr);
909
/* Find path to the successor blocks */
910
if (jump_instr->type == nir_jump_goto_if) {
911
route_to_cond(b, routing, jump_instr->condition,
912
jump_instr->target, jump_instr->else_target);
914
route_to(b, routing, block->successors[0]);
917
plant_levels(&levels, routing, b, mem_ctx);
919
loop_routing_end(routing, b);
920
plant_levels(&outside_levels, routing, b, mem_ctx);
925
nir_lower_goto_ifs_impl(nir_function_impl *impl)
927
if (impl->structured) {
928
nir_metadata_preserve(impl, nir_metadata_all);
932
nir_metadata_require(impl, nir_metadata_dominance);
934
/* We're going to re-arrange blocks like crazy. This is much easier to do
935
* if we don't have any phi nodes to fix up.
937
nir_foreach_block_unstructured(block, impl)
938
nir_lower_phis_to_regs_block(block);
941
nir_cf_extract(&cf_list, nir_before_cf_list(&impl->body),
942
nir_after_cf_list(&impl->body));
944
/* From this point on, it's structured */
945
impl->structured = true;
948
nir_builder_init(&b, impl);
949
b.cursor = nir_before_block(nir_start_block(impl));
951
void *mem_ctx = ralloc_context(b.shader);
953
struct set *end_set = _mesa_pointer_set_create(mem_ctx);
954
_mesa_set_add(end_set, impl->end_block);
955
struct set *empty_set = _mesa_pointer_set_create(mem_ctx);
957
nir_cf_node *start_node =
958
exec_node_data(nir_cf_node, exec_list_get_head(&cf_list.list), node);
959
nir_block *start_block = nir_cf_node_as_block(start_node);
961
struct routes *routing = rzalloc(mem_ctx, struct routes);
962
*routing = (struct routes) {
963
.regular.reachable = end_set,
964
.brk.reachable = empty_set,
965
.cont.reachable = empty_set,
967
nir_structurize(routing, &b, start_block, mem_ctx);
968
assert(routing->regular.fork == NULL);
969
assert(routing->brk.fork == NULL);
970
assert(routing->cont.fork == NULL);
971
assert(routing->brk.reachable == empty_set);
972
assert(routing->cont.reachable == empty_set);
974
ralloc_free(mem_ctx);
975
nir_cf_delete(&cf_list);
977
nir_metadata_preserve(impl, nir_metadata_none);
979
nir_repair_ssa_impl(impl);
980
nir_lower_regs_to_ssa_impl(impl);
986
nir_lower_goto_ifs(nir_shader *shader)
988
bool progress = true;
990
nir_foreach_function(function, shader) {
991
if (function->impl && nir_lower_goto_ifs_impl(function->impl))
added
removed
src/compiler/nir/nir_lower_goto_ifs.c
