1 /*
2 * Copyright © 2021 Valve Corporation
3 *
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:
10 *
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
13 * Software.
14 *
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
21 * IN THE SOFTWARE.
22 *
23 */
24
25 #include "nir.h"
26 #include "nir_builder.h"
27 #include "nir_control_flow.h"
28
29 static bool
lower_loop_continue_block(nir_builder * b,nir_loop * loop,bool * repair_ssa)30 lower_loop_continue_block(nir_builder *b, nir_loop *loop, bool *repair_ssa)
31 {
32 if (!nir_loop_has_continue_construct(loop))
33 return false;
34
35 nir_block *header = nir_loop_first_block(loop);
36 nir_block *cont = nir_loop_first_continue_block(loop);
37
38 /* count continue statements excluding unreachable ones */
39 unsigned num_continue = 0;
40 nir_block *single_predecessor = NULL;
41 set_foreach(cont->predecessors, entry) {
42 nir_block *pred = (nir_block *)entry->key;
43 /* If the continue block has no predecessors, it is unreachable. */
44 if (pred->predecessors->entries == 0)
45 continue;
46
47 single_predecessor = pred;
48 if (num_continue++)
49 break;
50 }
51
52 nir_lower_phis_to_regs_block(header);
53
54 if (num_continue == 0) {
55 /* this loop doesn't continue at all. delete the continue construct */
56 nir_cf_list extracted;
57 nir_cf_list_extract(&extracted, &loop->continue_list);
58 nir_cf_delete(&extracted);
59 } else if (num_continue == 1) {
60 /* inline the continue construct */
61 assert(single_predecessor->successors[0] == cont);
62 assert(single_predecessor->successors[1] == NULL);
63
64 nir_cf_list extracted;
65 nir_cf_list_extract(&extracted, &loop->continue_list);
66 nir_cf_reinsert(&extracted,
67 nir_after_block_before_jump(single_predecessor));
68 } else {
69 nir_lower_phis_to_regs_block(cont);
70 *repair_ssa = true;
71
72 /* As control flow has to re-converge before executing the continue
73 * construct, we insert it at the beginning of the loop with a flag
74 * to ensure that it doesn't get executed in the first iteration:
75 *
76 * loop {
77 * if (i != 0) {
78 * continue construct
79 * }
80 * loop body
81 * }
82 */
83
84 nir_variable *do_cont =
85 nir_local_variable_create(b->impl, glsl_bool_type(), "cont");
86
87 b->cursor = nir_before_cf_node(&loop->cf_node);
88 nir_store_var(b, do_cont, nir_imm_false(b), 1);
89 b->cursor = nir_before_block(header);
90 nir_if *cont_if = nir_push_if(b, nir_load_var(b, do_cont));
91 {
92 nir_cf_list extracted;
93 nir_cf_list_extract(&extracted, &loop->continue_list);
94 nir_cf_reinsert(&extracted, nir_before_cf_list(&cont_if->then_list));
95 }
96 nir_pop_if(b, cont_if);
97 nir_store_var(b, do_cont, nir_imm_true(b), 1);
98 }
99
100 nir_loop_remove_continue_construct(loop);
101 return true;
102 }
103
104 static bool
visit_cf_list(nir_builder * b,struct exec_list * list,bool * repair_ssa)105 visit_cf_list(nir_builder *b, struct exec_list *list, bool *repair_ssa)
106 {
107 bool progress = false;
108
109 foreach_list_typed(nir_cf_node, node, node, list) {
110 switch (node->type) {
111 case nir_cf_node_block:
112 continue;
113 case nir_cf_node_if: {
114 nir_if *nif = nir_cf_node_as_if(node);
115 progress |= visit_cf_list(b, &nif->then_list, repair_ssa);
116 progress |= visit_cf_list(b, &nif->else_list, repair_ssa);
117 break;
118 }
119 case nir_cf_node_loop: {
120 nir_loop *loop = nir_cf_node_as_loop(node);
121 progress |= visit_cf_list(b, &loop->body, repair_ssa);
122 progress |= visit_cf_list(b, &loop->continue_list, repair_ssa);
123 progress |= lower_loop_continue_block(b, loop, repair_ssa);
124 break;
125 }
126 case nir_cf_node_function:
127 unreachable("Unsupported cf_node type.");
128 }
129 }
130
131 return progress;
132 }
133
134 static bool
lower_continue_constructs_impl(nir_function_impl * impl)135 lower_continue_constructs_impl(nir_function_impl *impl)
136 {
137 nir_builder b = nir_builder_create(impl);
138 bool repair_ssa = false;
139 bool progress = visit_cf_list(&b, &impl->body, &repair_ssa);
140
141 if (progress) {
142 nir_metadata_preserve(impl, nir_metadata_none);
143
144 /* Merge the Phis from Header and Continue Target */
145 nir_lower_reg_intrinsics_to_ssa_impl(impl);
146
147 /* Re-inserting the Continue Target at the beginning of the loop
148 * violates the dominance property if instructions in the continue
149 * use SSA defs from the loop body.
150 */
151 if (repair_ssa)
152 nir_repair_ssa_impl(impl);
153 } else {
154 nir_metadata_preserve(impl, nir_metadata_all);
155 }
156
157 return progress;
158 }
159
160 bool
nir_lower_continue_constructs(nir_shader * shader)161 nir_lower_continue_constructs(nir_shader *shader)
162 {
163 bool progress = false;
164
165 nir_foreach_function_impl(impl, shader) {
166 if (lower_continue_constructs_impl(impl))
167 progress = true;
168 }
169
170 return progress;
171 }
172