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 (robdclark@gmail.com>
26 * Daniel Schürmann (daniel.schuermann@campus.tu-berlin.de)
27 * Rhys Perry (pendingchaos02@gmail.com)
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 if (nir_op_is_vec_or_mov(alu->op) || alu->op == nir_op_b2i32)
74 return options & nir_move_copies;
75 if (nir_alu_instr_is_comparison(alu))
76 return options & nir_move_comparisons;
77
78 /* Assuming that constants do not contribute to register pressure, it is
79 * beneficial to sink ALU instructions where all non constant sources
80 * are the same.
81 */
82 if (!(options & nir_move_alu))
83 return false;
84
85 unsigned inputs = nir_op_infos[alu->op].num_inputs;
86 int non_const = -1;
87
88 for (unsigned i = 0; i < inputs; ++i) {
89 if (is_constant_like(&alu->src[i].src))
90 continue;
91 else if (non_const < 0)
92 non_const = i;
93 else if (!nir_alu_srcs_equal(alu, alu, non_const, i))
94 return false;
95 }
96
97 return true;
98 }
99 case nir_instr_type_intrinsic: {
100 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
101 switch (intrin->intrinsic) {
102 case nir_intrinsic_load_ubo:
103 case nir_intrinsic_load_ubo_vec4:
104 *can_mov_out_of_loop = false;
105 return options & nir_move_load_ubo;
106 case nir_intrinsic_load_ssbo:
107 *can_mov_out_of_loop = false;
108 return (options & nir_move_load_ssbo) && nir_intrinsic_can_reorder(intrin);
109 case nir_intrinsic_load_input:
110 case nir_intrinsic_load_per_primitive_input:
111 case nir_intrinsic_load_interpolated_input:
112 case nir_intrinsic_load_per_vertex_input:
113 case nir_intrinsic_load_frag_coord:
114 case nir_intrinsic_load_frag_coord_zw:
115 case nir_intrinsic_load_frag_coord_zw_pan:
116 case nir_intrinsic_load_pixel_coord:
117 case nir_intrinsic_load_attribute_pan:
118 return options & nir_move_load_input;
119 case nir_intrinsic_load_uniform:
120 case nir_intrinsic_load_kernel_input:
121 return options & nir_move_load_uniform;
122 case nir_intrinsic_inverse_ballot:
123 case nir_intrinsic_is_subgroup_invocation_lt_amd:
124 *can_mov_out_of_loop = false;
125 return options & nir_move_copies;
126 case nir_intrinsic_load_constant_agx:
127 case nir_intrinsic_load_local_pixel_agx:
128 return true;
129 default:
130 return false;
131 }
132 }
133 default:
134 return false;
135 }
136 }
137
138 bool
nir_can_move_instr(nir_instr * instr,nir_move_options options)139 nir_can_move_instr(nir_instr *instr, nir_move_options options)
140 {
141 bool out_of_loop;
142 return can_sink_instr(instr, options, &out_of_loop);
143 }
144
145 static nir_loop *
get_innermost_loop(nir_cf_node * node)146 get_innermost_loop(nir_cf_node *node)
147 {
148 for (; node != NULL; node = node->parent) {
149 if (node->type == nir_cf_node_loop) {
150 nir_loop *loop = nir_cf_node_as_loop(node);
151 if (nir_loop_first_block(loop)->predecessors->entries > 1)
152 return loop;
153 }
154 }
155 return NULL;
156 }
157
158 static bool
loop_contains_block(nir_loop * loop,nir_block * block)159 loop_contains_block(nir_loop *loop, nir_block *block)
160 {
161 assert(!nir_loop_has_continue_construct(loop));
162 nir_block *before = nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
163 nir_block *after = nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node));
164
165 return block->index > before->index && block->index < after->index;
166 }
167
168 /* Given the LCA of all uses and the definition, find a block on the path
169 * between them in the dominance tree that is outside of as many loops as
170 * possible. If "sink_out_of_loops" is false, then we disallow sinking the
171 * definition outside of the loop it's defined in (if any).
172 */
173
174 static nir_block *
adjust_block_for_loops(nir_block * use_block,nir_block * def_block,bool sink_out_of_loops)175 adjust_block_for_loops(nir_block *use_block, nir_block *def_block,
176 bool sink_out_of_loops)
177 {
178 nir_loop *def_loop = NULL;
179 if (!sink_out_of_loops)
180 def_loop = get_innermost_loop(&def_block->cf_node);
181
182 for (nir_block *cur_block = use_block; cur_block != def_block->imm_dom;
183 cur_block = cur_block->imm_dom) {
184 if (!sink_out_of_loops && def_loop &&
185 !loop_contains_block(def_loop, use_block)) {
186 use_block = cur_block;
187 continue;
188 }
189
190 nir_cf_node *next = nir_cf_node_next(&cur_block->cf_node);
191 if (next && next->type == nir_cf_node_loop &&
192 nir_block_cf_tree_next(cur_block)->predecessors->entries > 1) {
193 nir_loop *following_loop = nir_cf_node_as_loop(next);
194 if (loop_contains_block(following_loop, use_block)) {
195 use_block = cur_block;
196 continue;
197 }
198 }
199 }
200
201 return use_block;
202 }
203
204 /* iterate a ssa def's use's and try to find a more optimal block to
205 * move it to, using the dominance tree. In short, if all of the uses
206 * are contained in a single block, the load will be moved there,
207 * otherwise it will be move to the least common ancestor block of all
208 * the uses
209 */
210 static nir_block *
get_preferred_block(nir_def * def,bool sink_out_of_loops)211 get_preferred_block(nir_def *def, bool sink_out_of_loops)
212 {
213 nir_block *lca = NULL;
214
215 nir_foreach_use_including_if(use, def) {
216 lca = nir_dominance_lca(lca, nir_src_get_block(use));
217 }
218
219 /* return in case, we didn't find a reachable user */
220 if (!lca)
221 return NULL;
222
223 /* We don't sink any instructions into loops to avoid repeated executions
224 * This might occasionally increase register pressure, but seems overall
225 * the better choice.
226 */
227 lca = adjust_block_for_loops(lca, def->parent_instr->block,
228 sink_out_of_loops);
229 assert(nir_block_dominates(def->parent_instr->block, lca));
230
231 return lca;
232 }
233
234 bool
nir_opt_sink(nir_shader * shader,nir_move_options options)235 nir_opt_sink(nir_shader *shader, nir_move_options options)
236 {
237 bool progress = false;
238
239 nir_foreach_function_impl(impl, shader) {
240 nir_metadata_require(impl,
241 nir_metadata_control_flow);
242
243 nir_foreach_block_reverse(block, impl) {
244 nir_foreach_instr_reverse_safe(instr, block) {
245 bool sink_out_of_loops;
246 if (!can_sink_instr(instr, options, &sink_out_of_loops))
247 continue;
248
249 nir_def *def = nir_instr_def(instr);
250
251 nir_block *use_block =
252 get_preferred_block(def, sink_out_of_loops);
253
254 if (!use_block || use_block == instr->block)
255 continue;
256
257 nir_instr_remove(instr);
258 nir_instr_insert(nir_after_phis(use_block), instr);
259
260 progress = true;
261 }
262 }
263
264 nir_metadata_preserve(impl,
265 nir_metadata_control_flow);
266 }
267
268 return progress;
269 }
270