1 /*
2 * Copyright © 2015 Intel 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 * Authors:
24 * Jason Ekstrand (jason@jlekstrand.net)
25 *
26 */
27
28 #include "nir.h"
29
30 /*
31 * Implements a pass that lowers vector phi nodes to scalar phi nodes when
32 * we don't think it will hurt anything.
33 */
34
35 struct lower_phis_to_scalar_state {
36 void *mem_ctx;
37 void *dead_ctx;
38
39 /* Hash table marking which phi nodes are scalarizable. The key is
40 * pointers to phi instructions and the entry is either NULL for not
41 * scalarizable or non-null for scalarizable.
42 */
43 struct hash_table *phi_table;
44 };
45
46 static bool
47 should_lower_phi(nir_phi_instr *phi, struct lower_phis_to_scalar_state *state);
48
49 static bool
is_phi_src_scalarizable(nir_phi_src * src,struct lower_phis_to_scalar_state * state)50 is_phi_src_scalarizable(nir_phi_src *src,
51 struct lower_phis_to_scalar_state *state)
52 {
53 /* Don't know what to do with non-ssa sources */
54 if (!src->src.is_ssa)
55 return false;
56
57 nir_instr *src_instr = src->src.ssa->parent_instr;
58 switch (src_instr->type) {
59 case nir_instr_type_alu: {
60 nir_alu_instr *src_alu = nir_instr_as_alu(src_instr);
61
62 /* ALU operations with output_size == 0 should be scalarized. We
63 * will also see a bunch of vecN operations from scalarizing ALU
64 * operations and, since they can easily be copy-propagated, they
65 * are ok too.
66 */
67 return nir_op_infos[src_alu->op].output_size == 0 ||
68 nir_op_is_vec(src_alu->op);
69 }
70
71 case nir_instr_type_phi:
72 /* A phi is scalarizable if we're going to lower it */
73 return should_lower_phi(nir_instr_as_phi(src_instr), state);
74
75 case nir_instr_type_load_const:
76 /* These are trivially scalarizable */
77 return true;
78
79 case nir_instr_type_ssa_undef:
80 /* The caller of this function is going to OR the results and we don't
81 * want undefs to count so we return false.
82 */
83 return false;
84
85 case nir_instr_type_intrinsic: {
86 nir_intrinsic_instr *src_intrin = nir_instr_as_intrinsic(src_instr);
87
88 switch (src_intrin->intrinsic) {
89 case nir_intrinsic_load_deref: {
90 /* Don't scalarize if we see a load of a local variable because it
91 * might turn into one of the things we can't scalarize.
92 */
93 nir_deref_instr *deref = nir_src_as_deref(src_intrin->src[0]);
94 return !nir_deref_mode_may_be(deref, nir_var_function_temp |
95 nir_var_shader_temp);
96 }
97
98 case nir_intrinsic_interp_deref_at_centroid:
99 case nir_intrinsic_interp_deref_at_sample:
100 case nir_intrinsic_interp_deref_at_offset:
101 case nir_intrinsic_interp_deref_at_vertex:
102 case nir_intrinsic_load_uniform:
103 case nir_intrinsic_load_ubo:
104 case nir_intrinsic_load_ssbo:
105 case nir_intrinsic_load_global:
106 case nir_intrinsic_load_global_constant:
107 case nir_intrinsic_load_input:
108 return true;
109 default:
110 break;
111 }
112 }
113 /* fallthrough */
114
115 default:
116 /* We can't scalarize this type of instruction */
117 return false;
118 }
119 }
120
121 /**
122 * Determines if the given phi node should be lowered. The only phi nodes
123 * we will scalarize at the moment are those where all of the sources are
124 * scalarizable.
125 *
126 * The reason for this comes down to coalescing. Since phi sources can't
127 * swizzle, swizzles on phis have to be resolved by inserting a mov right
128 * before the phi. The choice then becomes between movs to pick off
129 * components for a scalar phi or potentially movs to recombine components
130 * for a vector phi. The problem is that the movs generated to pick off
131 * the components are almost uncoalescable. We can't coalesce them in NIR
132 * because we need them to pick off components and we can't coalesce them
133 * in the backend because the source register is a vector and the
134 * destination is a scalar that may be used at other places in the program.
135 * On the other hand, if we have a bunch of scalars going into a vector
136 * phi, the situation is much better. In this case, if the SSA def is
137 * generated in the predecessor block to the corresponding phi source, the
138 * backend code will be an ALU op into a temporary and then a mov into the
139 * given vector component; this move can almost certainly be coalesced
140 * away.
141 */
142 static bool
should_lower_phi(nir_phi_instr * phi,struct lower_phis_to_scalar_state * state)143 should_lower_phi(nir_phi_instr *phi, struct lower_phis_to_scalar_state *state)
144 {
145 /* Already scalar */
146 if (phi->dest.ssa.num_components == 1)
147 return false;
148
149 struct hash_entry *entry = _mesa_hash_table_search(state->phi_table, phi);
150 if (entry)
151 return entry->data != NULL;
152
153 /* Insert an entry and mark it as scalarizable for now. That way
154 * we don't recurse forever and a cycle in the dependence graph
155 * won't automatically make us fail to scalarize.
156 */
157 entry = _mesa_hash_table_insert(state->phi_table, phi, (void *)(intptr_t)1);
158
159 bool scalarizable = false;
160
161 nir_foreach_phi_src(src, phi) {
162 /* This loop ignores srcs that are not scalarizable because its likely
163 * still worth copying to temps if another phi source is scalarizable.
164 * This reduces register spilling by a huge amount in the i965 driver for
165 * Deus Ex: MD.
166 */
167 scalarizable = is_phi_src_scalarizable(src, state);
168 if (scalarizable)
169 break;
170 }
171
172 /* The hash table entry for 'phi' may have changed while recursing the
173 * dependence graph, so we need to reset it */
174 entry = _mesa_hash_table_search(state->phi_table, phi);
175 assert(entry);
176
177 entry->data = (void *)(intptr_t)scalarizable;
178
179 return scalarizable;
180 }
181
182 static bool
lower_phis_to_scalar_block(nir_block * block,struct lower_phis_to_scalar_state * state)183 lower_phis_to_scalar_block(nir_block *block,
184 struct lower_phis_to_scalar_state *state)
185 {
186 bool progress = false;
187
188 /* Find the last phi node in the block */
189 nir_phi_instr *last_phi = NULL;
190 nir_foreach_instr(instr, block) {
191 if (instr->type != nir_instr_type_phi)
192 break;
193
194 last_phi = nir_instr_as_phi(instr);
195 }
196
197 /* We have to handle the phi nodes in their own pass due to the way
198 * we're modifying the linked list of instructions.
199 */
200 nir_foreach_instr_safe(instr, block) {
201 if (instr->type != nir_instr_type_phi)
202 break;
203
204 nir_phi_instr *phi = nir_instr_as_phi(instr);
205
206 if (!should_lower_phi(phi, state))
207 continue;
208
209 unsigned bit_size = phi->dest.ssa.bit_size;
210
211 /* Create a vecN operation to combine the results. Most of these
212 * will be redundant, but copy propagation should clean them up for
213 * us. No need to add the complexity here.
214 */
215 nir_op vec_op = nir_op_vec(phi->dest.ssa.num_components);
216
217 nir_alu_instr *vec = nir_alu_instr_create(state->mem_ctx, vec_op);
218 nir_ssa_dest_init(&vec->instr, &vec->dest.dest,
219 phi->dest.ssa.num_components,
220 bit_size, NULL);
221 vec->dest.write_mask = (1 << phi->dest.ssa.num_components) - 1;
222
223 for (unsigned i = 0; i < phi->dest.ssa.num_components; i++) {
224 nir_phi_instr *new_phi = nir_phi_instr_create(state->mem_ctx);
225 nir_ssa_dest_init(&new_phi->instr, &new_phi->dest, 1,
226 phi->dest.ssa.bit_size, NULL);
227
228 vec->src[i].src = nir_src_for_ssa(&new_phi->dest.ssa);
229
230 nir_foreach_phi_src(src, phi) {
231 /* We need to insert a mov to grab the i'th component of src */
232 nir_alu_instr *mov = nir_alu_instr_create(state->mem_ctx,
233 nir_op_mov);
234 nir_ssa_dest_init(&mov->instr, &mov->dest.dest, 1, bit_size, NULL);
235 mov->dest.write_mask = 1;
236 nir_src_copy(&mov->src[0].src, &src->src, state->mem_ctx);
237 mov->src[0].swizzle[0] = i;
238
239 /* Insert at the end of the predecessor but before the jump */
240 nir_instr *pred_last_instr = nir_block_last_instr(src->pred);
241 if (pred_last_instr && pred_last_instr->type == nir_instr_type_jump)
242 nir_instr_insert_before(pred_last_instr, &mov->instr);
243 else
244 nir_instr_insert_after_block(src->pred, &mov->instr);
245
246 nir_phi_src *new_src = ralloc(new_phi, nir_phi_src);
247 new_src->pred = src->pred;
248 new_src->src = nir_src_for_ssa(&mov->dest.dest.ssa);
249
250 exec_list_push_tail(&new_phi->srcs, &new_src->node);
251 }
252
253 nir_instr_insert_before(&phi->instr, &new_phi->instr);
254 }
255
256 nir_instr_insert_after(&last_phi->instr, &vec->instr);
257
258 nir_ssa_def_rewrite_uses(&phi->dest.ssa,
259 nir_src_for_ssa(&vec->dest.dest.ssa));
260
261 ralloc_steal(state->dead_ctx, phi);
262 nir_instr_remove(&phi->instr);
263
264 progress = true;
265
266 /* We're using the safe iterator and inserting all the newly
267 * scalarized phi nodes before their non-scalarized version so that's
268 * ok. However, we are also inserting vec operations after all of
269 * the last phi node so once we get here, we can't trust even the
270 * safe iterator to stop properly. We have to break manually.
271 */
272 if (instr == &last_phi->instr)
273 break;
274 }
275
276 return progress;
277 }
278
279 static bool
lower_phis_to_scalar_impl(nir_function_impl * impl)280 lower_phis_to_scalar_impl(nir_function_impl *impl)
281 {
282 struct lower_phis_to_scalar_state state;
283 bool progress = false;
284
285 state.mem_ctx = ralloc_parent(impl);
286 state.dead_ctx = ralloc_context(NULL);
287 state.phi_table = _mesa_pointer_hash_table_create(state.dead_ctx);
288
289 nir_foreach_block(block, impl) {
290 progress = lower_phis_to_scalar_block(block, &state) || progress;
291 }
292
293 nir_metadata_preserve(impl, nir_metadata_block_index |
294 nir_metadata_dominance);
295
296 ralloc_free(state.dead_ctx);
297 return progress;
298 }
299
300 /** A pass that lowers vector phi nodes to scalar
301 *
302 * This pass loops through the blocks and lowers looks for vector phi nodes
303 * it can lower to scalar phi nodes. Not all phi nodes are lowered. For
304 * instance, if one of the sources is a non-scalarizable vector, then we
305 * don't bother lowering because that would generate hard-to-coalesce movs.
306 */
307 bool
nir_lower_phis_to_scalar(nir_shader * shader)308 nir_lower_phis_to_scalar(nir_shader *shader)
309 {
310 bool progress = false;
311
312 nir_foreach_function(function, shader) {
313 if (function->impl)
314 progress = lower_phis_to_scalar_impl(function->impl) || progress;
315 }
316
317 return progress;
318 }
319