1 /*
2 * Copyright © 2018 Red Hat
3 * Copyright © 2019 Valve Corporation
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 * IN THE SOFTWARE.
23 *
24 * Authors:
25 * Rob Clark ([email protected]>
26 * Daniel Schürmann ([email protected])
27 * Rhys Perry ([email protected])
28 *
29 */
30
31 #include "nir.h"
32
33 /*
34 * A simple pass that moves some instructions into the least common
35 * anscestor of consuming instructions.
36 */
37
38 /*
39 * Detect whether a source is like a constant for the purposes of register
40 * pressure calculations (e.g. can be remat anywhere effectively for free).
41 */
42 static bool
is_constant_like(nir_src * src)43 is_constant_like(nir_src *src)
44 {
45 /* Constants are constants */
46 if (nir_src_is_const(*src))
47 return true;
48
49 /* Otherwise, look for constant-like intrinsics */
50 nir_instr *parent = src->ssa->parent_instr;
51 if (parent->type != nir_instr_type_intrinsic)
52 return false;
53
54 return (nir_instr_as_intrinsic(parent)->intrinsic ==
55 nir_intrinsic_load_preamble);
56 }
57
58 static bool
can_sink_instr(nir_instr * instr,nir_move_options options,bool * can_mov_out_of_loop)59 can_sink_instr(nir_instr *instr, nir_move_options options, bool *can_mov_out_of_loop)
60 {
61 /* Some intrinsic might require uniform sources and
62 * moving out of loops can add divergence.
63 */
64 *can_mov_out_of_loop = true;
65 switch (instr->type) {
66 case nir_instr_type_load_const:
67 case nir_instr_type_undef: {
68 return options & nir_move_const_undef;
69 }
70 case nir_instr_type_alu: {
71 nir_alu_instr *alu = nir_instr_as_alu(instr);
72
73 /* Derivatives cannot be moved into non-uniform control flow, including
74 * past a discard_if in the same block. Even if they could, sinking
75 * derivatives extends the lifetime of helper invocations which may be
76 * worse than the register pressure decrease. Bail on derivatives.
77 */
78 if (nir_op_is_derivative(alu->op))
79 return false;
80
81 if (nir_op_is_vec_or_mov(alu->op) || alu->op == nir_op_b2i32)
82 return options & nir_move_copies;
83 if (nir_alu_instr_is_comparison(alu))
84 return options & nir_move_comparisons;
85
86 /* Assuming that constants do not contribute to register pressure, it is
87 * beneficial to sink ALU instructions where all but one source is
88 * constant. Detect that case last.
89 */
90 if (!(options & nir_move_alu))
91 return false;
92
93 unsigned inputs = nir_op_infos[alu->op].num_inputs;
94 unsigned constant_inputs = 0;
95
96 for (unsigned i = 0; i < inputs; ++i) {
97 if (is_constant_like(&alu->src[i].src))
98 constant_inputs++;
99 }
100
101 return (constant_inputs + 1 >= inputs);
102 }
103 case nir_instr_type_intrinsic: {
104 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
105 switch (intrin->intrinsic) {
106 case nir_intrinsic_load_ubo:
107 case nir_intrinsic_load_ubo_vec4:
108 *can_mov_out_of_loop = false;
109 return options & nir_move_load_ubo;
110 case nir_intrinsic_load_ssbo:
111 *can_mov_out_of_loop = false;
112 return (options & nir_move_load_ssbo) && nir_intrinsic_can_reorder(intrin);
113 case nir_intrinsic_load_input:
114 case nir_intrinsic_load_per_primitive_input:
115 case nir_intrinsic_load_interpolated_input:
116 case nir_intrinsic_load_per_vertex_input:
117 case nir_intrinsic_load_frag_coord:
118 case nir_intrinsic_load_frag_coord_zw:
119 case nir_intrinsic_load_pixel_coord:
120 return options & nir_move_load_input;
121 case nir_intrinsic_load_uniform:
122 case nir_intrinsic_load_kernel_input:
123 return options & nir_move_load_uniform;
124 case nir_intrinsic_inverse_ballot:
125 *can_mov_out_of_loop = false;
126 return options & nir_move_copies;
127 case nir_intrinsic_load_constant_agx:
128 case nir_intrinsic_load_local_pixel_agx:
129 return true;
130 default:
131 return false;
132 }
133 }
134 default:
135 return false;
136 }
137 }
138
139 bool
nir_can_move_instr(nir_instr * instr,nir_move_options options)140 nir_can_move_instr(nir_instr *instr, nir_move_options options)
141 {
142 bool out_of_loop;
143 return can_sink_instr(instr, options, &out_of_loop);
144 }
145
146 static nir_loop *
get_innermost_loop(nir_cf_node * node)147 get_innermost_loop(nir_cf_node *node)
148 {
149 for (; node != NULL; node = node->parent) {
150 if (node->type == nir_cf_node_loop) {
151 nir_loop *loop = nir_cf_node_as_loop(node);
152 if (nir_loop_first_block(loop)->predecessors->entries > 1)
153 return loop;
154 }
155 }
156 return NULL;
157 }
158
159 static bool
loop_contains_block(nir_loop * loop,nir_block * block)160 loop_contains_block(nir_loop *loop, nir_block *block)
161 {
162 assert(!nir_loop_has_continue_construct(loop));
163 nir_block *before = nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
164 nir_block *after = nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node));
165
166 return block->index > before->index && block->index < after->index;
167 }
168
169 /* Given the LCA of all uses and the definition, find a block on the path
170 * between them in the dominance tree that is outside of as many loops as
171 * possible. If "sink_out_of_loops" is false, then we disallow sinking the
172 * definition outside of the loop it's defined in (if any).
173 */
174
175 static nir_block *
adjust_block_for_loops(nir_block * use_block,nir_block * def_block,bool sink_out_of_loops)176 adjust_block_for_loops(nir_block *use_block, nir_block *def_block,
177 bool sink_out_of_loops)
178 {
179 nir_loop *def_loop = NULL;
180 if (!sink_out_of_loops)
181 def_loop = get_innermost_loop(&def_block->cf_node);
182
183 for (nir_block *cur_block = use_block; cur_block != def_block->imm_dom;
184 cur_block = cur_block->imm_dom) {
185 if (!sink_out_of_loops && def_loop &&
186 !loop_contains_block(def_loop, use_block)) {
187 use_block = cur_block;
188 continue;
189 }
190
191 nir_cf_node *next = nir_cf_node_next(&cur_block->cf_node);
192 if (next && next->type == nir_cf_node_loop &&
193 nir_block_cf_tree_next(cur_block)->predecessors->entries > 1) {
194 nir_loop *following_loop = nir_cf_node_as_loop(next);
195 if (loop_contains_block(following_loop, use_block)) {
196 use_block = cur_block;
197 continue;
198 }
199 }
200 }
201
202 return use_block;
203 }
204
205 /* iterate a ssa def's use's and try to find a more optimal block to
206 * move it to, using the dominance tree. In short, if all of the uses
207 * are contained in a single block, the load will be moved there,
208 * otherwise it will be move to the least common ancestor block of all
209 * the uses
210 */
211 static nir_block *
get_preferred_block(nir_def * def,bool sink_out_of_loops)212 get_preferred_block(nir_def *def, bool sink_out_of_loops)
213 {
214 nir_block *lca = NULL;
215
216 nir_foreach_use_including_if(use, def) {
217 lca = nir_dominance_lca(lca, nir_src_get_block(use));
218 }
219
220 /* return in case, we didn't find a reachable user */
221 if (!lca)
222 return NULL;
223
224 /* We don't sink any instructions into loops to avoid repeated executions
225 * This might occasionally increase register pressure, but seems overall
226 * the better choice.
227 */
228 lca = adjust_block_for_loops(lca, def->parent_instr->block,
229 sink_out_of_loops);
230 assert(nir_block_dominates(def->parent_instr->block, lca));
231
232 return lca;
233 }
234
235 bool
nir_opt_sink(nir_shader * shader,nir_move_options options)236 nir_opt_sink(nir_shader *shader, nir_move_options options)
237 {
238 bool progress = false;
239
240 nir_foreach_function_impl(impl, shader) {
241 nir_metadata_require(impl,
242 nir_metadata_control_flow);
243
244 nir_foreach_block_reverse(block, impl) {
245 nir_foreach_instr_reverse_safe(instr, block) {
246 bool sink_out_of_loops;
247 if (!can_sink_instr(instr, options, &sink_out_of_loops))
248 continue;
249
250 nir_def *def = nir_instr_def(instr);
251
252 nir_block *use_block =
253 get_preferred_block(def, sink_out_of_loops);
254
255 if (!use_block || use_block == instr->block)
256 continue;
257
258 nir_instr_remove(instr);
259 nir_instr_insert(nir_after_phis(use_block), instr);
260
261 progress = true;
262 }
263 }
264
265 nir_metadata_preserve(impl,
266 nir_metadata_control_flow);
267 }
268
269 return progress;
270 }
271