nir: Fix divergence analysis for tessellation input/outputs
[mesa.git] / src / compiler / nir / nir_divergence_analysis.c
1 /*
2 * Copyright © 2018 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
27 /* This pass computes for each ssa definition if it is uniform.
28 * That is, the variable has the same value for all invocations
29 * of the group.
30 *
31 * This divergence analysis pass expects the shader to be in LCSSA-form.
32 *
33 * This algorithm implements "The Simple Divergence Analysis" from
34 * Diogo Sampaio, Rafael De Souza, Sylvain Collange, Fernando Magno Quintão Pereira.
35 * Divergence Analysis. ACM Transactions on Programming Languages and Systems (TOPLAS),
36 * ACM, 2013, 35 (4), pp.13:1-13:36. <10.1145/2523815>. <hal-00909072v2>
37 */
38
39 struct divergence_state {
40 const nir_divergence_options options;
41 const gl_shader_stage stage;
42
43 /** current control flow state */
44 /* True if some loop-active invocations might take a different control-flow path.
45 * A divergent break does not cause subsequent control-flow to be considered
46 * divergent because those invocations are no longer active in the loop.
47 * For a divergent if, both sides are considered divergent flow because
48 * the other side is still loop-active. */
49 bool divergent_loop_cf;
50 /* True if a divergent continue happened since the loop header */
51 bool divergent_loop_continue;
52 /* True if a divergent break happened since the loop header */
53 bool divergent_loop_break;
54
55 /* True if we visit the block for the fist time */
56 bool first_visit;
57 };
58
59 static bool
60 visit_cf_list(struct exec_list *list, struct divergence_state *state);
61
62 static bool
63 visit_alu(nir_alu_instr *instr)
64 {
65 if (instr->dest.dest.ssa.divergent)
66 return false;
67
68 unsigned num_src = nir_op_infos[instr->op].num_inputs;
69
70 for (unsigned i = 0; i < num_src; i++) {
71 if (instr->src[i].src.ssa->divergent) {
72 instr->dest.dest.ssa.divergent = true;
73 return true;
74 }
75 }
76
77 return false;
78 }
79
80 static bool
81 visit_intrinsic(nir_intrinsic_instr *instr, struct divergence_state *state)
82 {
83 if (!nir_intrinsic_infos[instr->intrinsic].has_dest)
84 return false;
85
86 if (instr->dest.ssa.divergent)
87 return false;
88
89 nir_divergence_options options = state->options;
90 gl_shader_stage stage = state->stage;
91 bool is_divergent = false;
92 switch (instr->intrinsic) {
93 /* Intrinsics which are always uniform */
94 case nir_intrinsic_shader_clock:
95 case nir_intrinsic_ballot:
96 case nir_intrinsic_read_invocation:
97 case nir_intrinsic_read_first_invocation:
98 case nir_intrinsic_vote_any:
99 case nir_intrinsic_vote_all:
100 case nir_intrinsic_vote_feq:
101 case nir_intrinsic_vote_ieq:
102 case nir_intrinsic_load_work_dim:
103 case nir_intrinsic_load_work_group_id:
104 case nir_intrinsic_load_num_work_groups:
105 case nir_intrinsic_load_local_group_size:
106 case nir_intrinsic_load_subgroup_id:
107 case nir_intrinsic_load_num_subgroups:
108 case nir_intrinsic_load_subgroup_size:
109 case nir_intrinsic_load_subgroup_eq_mask:
110 case nir_intrinsic_load_subgroup_ge_mask:
111 case nir_intrinsic_load_subgroup_gt_mask:
112 case nir_intrinsic_load_subgroup_le_mask:
113 case nir_intrinsic_load_subgroup_lt_mask:
114 case nir_intrinsic_first_invocation:
115 case nir_intrinsic_load_base_instance:
116 case nir_intrinsic_load_base_vertex:
117 case nir_intrinsic_load_first_vertex:
118 case nir_intrinsic_load_draw_id:
119 case nir_intrinsic_load_is_indexed_draw:
120 case nir_intrinsic_load_viewport_scale:
121 case nir_intrinsic_load_alpha_ref_float:
122 case nir_intrinsic_load_user_clip_plane:
123 case nir_intrinsic_load_viewport_x_scale:
124 case nir_intrinsic_load_viewport_y_scale:
125 case nir_intrinsic_load_viewport_z_scale:
126 case nir_intrinsic_load_viewport_offset:
127 case nir_intrinsic_load_viewport_z_offset:
128 case nir_intrinsic_load_blend_const_color_a_float:
129 case nir_intrinsic_load_blend_const_color_b_float:
130 case nir_intrinsic_load_blend_const_color_g_float:
131 case nir_intrinsic_load_blend_const_color_r_float:
132 case nir_intrinsic_load_blend_const_color_rgba:
133 case nir_intrinsic_load_blend_const_color_aaaa8888_unorm:
134 case nir_intrinsic_load_blend_const_color_rgba8888_unorm:
135 is_divergent = false;
136 break;
137
138 /* Intrinsics with divergence depending on shader stage and hardware */
139 case nir_intrinsic_load_input:
140 is_divergent = instr->src[0].ssa->divergent;
141 if (stage == MESA_SHADER_FRAGMENT)
142 is_divergent |= !(options & nir_divergence_single_prim_per_subgroup);
143 else if (stage == MESA_SHADER_TESS_EVAL)
144 is_divergent |= !(options & nir_divergence_single_patch_per_tes_subgroup);
145 else
146 is_divergent = true;
147 break;
148 case nir_intrinsic_load_per_vertex_input:
149 is_divergent = instr->src[0].ssa->divergent ||
150 instr->src[1].ssa->divergent;
151 if (stage == MESA_SHADER_TESS_CTRL)
152 is_divergent |= !(options & nir_divergence_single_patch_per_tcs_subgroup);
153 if (stage == MESA_SHADER_TESS_EVAL)
154 is_divergent |= !(options & nir_divergence_single_patch_per_tes_subgroup);
155 else
156 is_divergent = true;
157 break;
158 case nir_intrinsic_load_input_vertex:
159 is_divergent = instr->src[1].ssa->divergent;
160 assert(stage == MESA_SHADER_FRAGMENT);
161 is_divergent |= !(options & nir_divergence_single_prim_per_subgroup);
162 break;
163 case nir_intrinsic_load_output:
164 assert(stage == MESA_SHADER_TESS_CTRL || stage == MESA_SHADER_FRAGMENT);
165 is_divergent = instr->src[0].ssa->divergent;
166 if (stage == MESA_SHADER_TESS_CTRL)
167 is_divergent |= !(options & nir_divergence_single_patch_per_tcs_subgroup);
168 else
169 is_divergent = true;
170 break;
171 case nir_intrinsic_load_per_vertex_output:
172 assert(stage == MESA_SHADER_TESS_CTRL);
173 is_divergent = instr->src[0].ssa->divergent ||
174 instr->src[1].ssa->divergent ||
175 !(options & nir_divergence_single_patch_per_tcs_subgroup);
176 break;
177 case nir_intrinsic_load_layer_id:
178 case nir_intrinsic_load_front_face:
179 assert(stage == MESA_SHADER_FRAGMENT);
180 is_divergent = !(options & nir_divergence_single_prim_per_subgroup);
181 break;
182 case nir_intrinsic_load_view_index:
183 assert(stage != MESA_SHADER_COMPUTE && stage != MESA_SHADER_KERNEL);
184 if (options & nir_divergence_view_index_uniform)
185 is_divergent = false;
186 else if (stage == MESA_SHADER_FRAGMENT)
187 is_divergent = !(options & nir_divergence_single_prim_per_subgroup);
188 break;
189 case nir_intrinsic_load_fs_input_interp_deltas:
190 assert(stage == MESA_SHADER_FRAGMENT);
191 is_divergent = instr->src[0].ssa->divergent;
192 is_divergent |= !(options & nir_divergence_single_prim_per_subgroup);
193 break;
194 case nir_intrinsic_load_primitive_id:
195 if (stage == MESA_SHADER_FRAGMENT)
196 is_divergent = !(options & nir_divergence_single_prim_per_subgroup);
197 else if (stage == MESA_SHADER_TESS_CTRL)
198 is_divergent = !(options & nir_divergence_single_patch_per_tcs_subgroup);
199 else if (stage == MESA_SHADER_TESS_EVAL)
200 is_divergent = !(options & nir_divergence_single_patch_per_tes_subgroup);
201 else if (stage == MESA_SHADER_GEOMETRY)
202 is_divergent = true;
203 else
204 unreachable("Invalid stage for load_primitive_id");
205 break;
206 case nir_intrinsic_load_tess_level_inner:
207 case nir_intrinsic_load_tess_level_outer:
208 if (stage == MESA_SHADER_TESS_CTRL)
209 is_divergent = !(options & nir_divergence_single_patch_per_tcs_subgroup);
210 else if (stage == MESA_SHADER_TESS_EVAL)
211 is_divergent = !(options & nir_divergence_single_patch_per_tes_subgroup);
212 else
213 unreachable("Invalid stage for load_primitive_tess_level_*");
214 break;
215 case nir_intrinsic_load_patch_vertices_in:
216 if (stage == MESA_SHADER_TESS_EVAL)
217 is_divergent = !(options & nir_divergence_single_patch_per_tes_subgroup);
218 else
219 assert(stage == MESA_SHADER_TESS_CTRL);
220 break;
221
222 /* Clustered reductions are uniform if cluster_size == subgroup_size or
223 * the source is uniform and the operation is invariant.
224 * Inclusive scans are uniform if
225 * the source is uniform and the operation is invariant
226 */
227 case nir_intrinsic_reduce:
228 if (nir_intrinsic_cluster_size(instr) == 0)
229 return false;
230 /* fallthrough */
231 case nir_intrinsic_inclusive_scan: {
232 nir_op op = nir_intrinsic_reduction_op(instr);
233 is_divergent = instr->src[0].ssa->divergent;
234 if (op != nir_op_umin && op != nir_op_imin && op != nir_op_fmin &&
235 op != nir_op_umax && op != nir_op_imax && op != nir_op_fmax &&
236 op != nir_op_iand && op != nir_op_ior)
237 is_divergent = true;
238 break;
239 }
240
241 /* Intrinsics with divergence depending on sources */
242 case nir_intrinsic_ballot_bitfield_extract:
243 case nir_intrinsic_ballot_find_lsb:
244 case nir_intrinsic_ballot_find_msb:
245 case nir_intrinsic_ballot_bit_count_reduce:
246 case nir_intrinsic_shuffle_xor:
247 case nir_intrinsic_shuffle_up:
248 case nir_intrinsic_shuffle_down:
249 case nir_intrinsic_quad_broadcast:
250 case nir_intrinsic_quad_swap_horizontal:
251 case nir_intrinsic_quad_swap_vertical:
252 case nir_intrinsic_quad_swap_diagonal:
253 case nir_intrinsic_load_deref:
254 case nir_intrinsic_load_ubo:
255 case nir_intrinsic_load_ssbo:
256 case nir_intrinsic_load_shared:
257 case nir_intrinsic_load_global:
258 case nir_intrinsic_load_uniform:
259 case nir_intrinsic_load_push_constant:
260 case nir_intrinsic_load_constant:
261 case nir_intrinsic_load_sample_pos_from_id:
262 case nir_intrinsic_load_kernel_input:
263 case nir_intrinsic_image_load:
264 case nir_intrinsic_image_deref_load:
265 case nir_intrinsic_bindless_image_load:
266 case nir_intrinsic_image_samples:
267 case nir_intrinsic_image_deref_samples:
268 case nir_intrinsic_bindless_image_samples:
269 case nir_intrinsic_get_buffer_size:
270 case nir_intrinsic_image_size:
271 case nir_intrinsic_image_deref_size:
272 case nir_intrinsic_bindless_image_size:
273 case nir_intrinsic_copy_deref:
274 case nir_intrinsic_deref_buffer_array_length:
275 case nir_intrinsic_vulkan_resource_index:
276 case nir_intrinsic_vulkan_resource_reindex:
277 case nir_intrinsic_load_vulkan_descriptor:
278 case nir_intrinsic_atomic_counter_read:
279 case nir_intrinsic_atomic_counter_read_deref:
280 case nir_intrinsic_quad_swizzle_amd:
281 case nir_intrinsic_masked_swizzle_amd: {
282 unsigned num_srcs = nir_intrinsic_infos[instr->intrinsic].num_srcs;
283 for (unsigned i = 0; i < num_srcs; i++) {
284 if (instr->src[i].ssa->divergent) {
285 is_divergent = true;
286 break;
287 }
288 }
289 break;
290 }
291
292 case nir_intrinsic_shuffle:
293 is_divergent = instr->src[0].ssa->divergent &&
294 instr->src[1].ssa->divergent;
295 break;
296
297 /* Intrinsics which are always divergent */
298 case nir_intrinsic_load_color0:
299 case nir_intrinsic_load_color1:
300 case nir_intrinsic_load_param:
301 case nir_intrinsic_load_sample_id:
302 case nir_intrinsic_load_sample_id_no_per_sample:
303 case nir_intrinsic_load_sample_mask_in:
304 case nir_intrinsic_load_interpolated_input:
305 case nir_intrinsic_load_barycentric_pixel:
306 case nir_intrinsic_load_barycentric_centroid:
307 case nir_intrinsic_load_barycentric_sample:
308 case nir_intrinsic_load_barycentric_model:
309 case nir_intrinsic_load_barycentric_at_sample:
310 case nir_intrinsic_load_barycentric_at_offset:
311 case nir_intrinsic_interp_deref_at_offset:
312 case nir_intrinsic_interp_deref_at_sample:
313 case nir_intrinsic_interp_deref_at_centroid:
314 case nir_intrinsic_interp_deref_at_vertex:
315 case nir_intrinsic_load_tess_coord:
316 case nir_intrinsic_load_point_coord:
317 case nir_intrinsic_load_frag_coord:
318 case nir_intrinsic_load_sample_pos:
319 case nir_intrinsic_load_vertex_id_zero_base:
320 case nir_intrinsic_load_vertex_id:
321 case nir_intrinsic_load_instance_id:
322 case nir_intrinsic_load_invocation_id:
323 case nir_intrinsic_load_local_invocation_id:
324 case nir_intrinsic_load_local_invocation_index:
325 case nir_intrinsic_load_global_invocation_id:
326 case nir_intrinsic_load_global_invocation_index:
327 case nir_intrinsic_load_subgroup_invocation:
328 case nir_intrinsic_load_helper_invocation:
329 case nir_intrinsic_is_helper_invocation:
330 case nir_intrinsic_load_scratch:
331 case nir_intrinsic_deref_atomic_add:
332 case nir_intrinsic_deref_atomic_imin:
333 case nir_intrinsic_deref_atomic_umin:
334 case nir_intrinsic_deref_atomic_imax:
335 case nir_intrinsic_deref_atomic_umax:
336 case nir_intrinsic_deref_atomic_and:
337 case nir_intrinsic_deref_atomic_or:
338 case nir_intrinsic_deref_atomic_xor:
339 case nir_intrinsic_deref_atomic_exchange:
340 case nir_intrinsic_deref_atomic_comp_swap:
341 case nir_intrinsic_deref_atomic_fadd:
342 case nir_intrinsic_deref_atomic_fmin:
343 case nir_intrinsic_deref_atomic_fmax:
344 case nir_intrinsic_deref_atomic_fcomp_swap:
345 case nir_intrinsic_ssbo_atomic_add:
346 case nir_intrinsic_ssbo_atomic_imin:
347 case nir_intrinsic_ssbo_atomic_umin:
348 case nir_intrinsic_ssbo_atomic_imax:
349 case nir_intrinsic_ssbo_atomic_umax:
350 case nir_intrinsic_ssbo_atomic_and:
351 case nir_intrinsic_ssbo_atomic_or:
352 case nir_intrinsic_ssbo_atomic_xor:
353 case nir_intrinsic_ssbo_atomic_exchange:
354 case nir_intrinsic_ssbo_atomic_comp_swap:
355 case nir_intrinsic_ssbo_atomic_fadd:
356 case nir_intrinsic_ssbo_atomic_fmax:
357 case nir_intrinsic_ssbo_atomic_fmin:
358 case nir_intrinsic_ssbo_atomic_fcomp_swap:
359 case nir_intrinsic_image_deref_atomic_add:
360 case nir_intrinsic_image_deref_atomic_imin:
361 case nir_intrinsic_image_deref_atomic_umin:
362 case nir_intrinsic_image_deref_atomic_imax:
363 case nir_intrinsic_image_deref_atomic_umax:
364 case nir_intrinsic_image_deref_atomic_and:
365 case nir_intrinsic_image_deref_atomic_or:
366 case nir_intrinsic_image_deref_atomic_xor:
367 case nir_intrinsic_image_deref_atomic_exchange:
368 case nir_intrinsic_image_deref_atomic_comp_swap:
369 case nir_intrinsic_image_deref_atomic_fadd:
370 case nir_intrinsic_image_atomic_add:
371 case nir_intrinsic_image_atomic_imin:
372 case nir_intrinsic_image_atomic_umin:
373 case nir_intrinsic_image_atomic_imax:
374 case nir_intrinsic_image_atomic_umax:
375 case nir_intrinsic_image_atomic_and:
376 case nir_intrinsic_image_atomic_or:
377 case nir_intrinsic_image_atomic_xor:
378 case nir_intrinsic_image_atomic_exchange:
379 case nir_intrinsic_image_atomic_comp_swap:
380 case nir_intrinsic_image_atomic_fadd:
381 case nir_intrinsic_bindless_image_atomic_add:
382 case nir_intrinsic_bindless_image_atomic_imin:
383 case nir_intrinsic_bindless_image_atomic_umin:
384 case nir_intrinsic_bindless_image_atomic_imax:
385 case nir_intrinsic_bindless_image_atomic_umax:
386 case nir_intrinsic_bindless_image_atomic_and:
387 case nir_intrinsic_bindless_image_atomic_or:
388 case nir_intrinsic_bindless_image_atomic_xor:
389 case nir_intrinsic_bindless_image_atomic_exchange:
390 case nir_intrinsic_bindless_image_atomic_comp_swap:
391 case nir_intrinsic_bindless_image_atomic_fadd:
392 case nir_intrinsic_shared_atomic_add:
393 case nir_intrinsic_shared_atomic_imin:
394 case nir_intrinsic_shared_atomic_umin:
395 case nir_intrinsic_shared_atomic_imax:
396 case nir_intrinsic_shared_atomic_umax:
397 case nir_intrinsic_shared_atomic_and:
398 case nir_intrinsic_shared_atomic_or:
399 case nir_intrinsic_shared_atomic_xor:
400 case nir_intrinsic_shared_atomic_exchange:
401 case nir_intrinsic_shared_atomic_comp_swap:
402 case nir_intrinsic_shared_atomic_fadd:
403 case nir_intrinsic_shared_atomic_fmin:
404 case nir_intrinsic_shared_atomic_fmax:
405 case nir_intrinsic_shared_atomic_fcomp_swap:
406 case nir_intrinsic_global_atomic_add:
407 case nir_intrinsic_global_atomic_imin:
408 case nir_intrinsic_global_atomic_umin:
409 case nir_intrinsic_global_atomic_imax:
410 case nir_intrinsic_global_atomic_umax:
411 case nir_intrinsic_global_atomic_and:
412 case nir_intrinsic_global_atomic_or:
413 case nir_intrinsic_global_atomic_xor:
414 case nir_intrinsic_global_atomic_exchange:
415 case nir_intrinsic_global_atomic_comp_swap:
416 case nir_intrinsic_global_atomic_fadd:
417 case nir_intrinsic_global_atomic_fmin:
418 case nir_intrinsic_global_atomic_fmax:
419 case nir_intrinsic_global_atomic_fcomp_swap:
420 case nir_intrinsic_atomic_counter_add:
421 case nir_intrinsic_atomic_counter_min:
422 case nir_intrinsic_atomic_counter_max:
423 case nir_intrinsic_atomic_counter_and:
424 case nir_intrinsic_atomic_counter_or:
425 case nir_intrinsic_atomic_counter_xor:
426 case nir_intrinsic_atomic_counter_inc:
427 case nir_intrinsic_atomic_counter_pre_dec:
428 case nir_intrinsic_atomic_counter_post_dec:
429 case nir_intrinsic_atomic_counter_exchange:
430 case nir_intrinsic_atomic_counter_comp_swap:
431 case nir_intrinsic_atomic_counter_add_deref:
432 case nir_intrinsic_atomic_counter_min_deref:
433 case nir_intrinsic_atomic_counter_max_deref:
434 case nir_intrinsic_atomic_counter_and_deref:
435 case nir_intrinsic_atomic_counter_or_deref:
436 case nir_intrinsic_atomic_counter_xor_deref:
437 case nir_intrinsic_atomic_counter_inc_deref:
438 case nir_intrinsic_atomic_counter_pre_dec_deref:
439 case nir_intrinsic_atomic_counter_post_dec_deref:
440 case nir_intrinsic_atomic_counter_exchange_deref:
441 case nir_intrinsic_atomic_counter_comp_swap_deref:
442 case nir_intrinsic_exclusive_scan:
443 case nir_intrinsic_ballot_bit_count_exclusive:
444 case nir_intrinsic_ballot_bit_count_inclusive:
445 case nir_intrinsic_write_invocation_amd:
446 case nir_intrinsic_mbcnt_amd:
447 case nir_intrinsic_elect:
448 is_divergent = true;
449 break;
450
451 default:
452 #ifdef NDEBUG
453 is_divergent = true;
454 break;
455 #else
456 nir_print_instr(&instr->instr, stderr);
457 unreachable("\nNIR divergence analysis: Unhandled intrinsic.");
458 #endif
459 }
460
461 instr->dest.ssa.divergent = is_divergent;
462 return is_divergent;
463 }
464
465 static bool
466 visit_tex(nir_tex_instr *instr)
467 {
468 if (instr->dest.ssa.divergent)
469 return false;
470
471 bool is_divergent = false;
472
473 for (unsigned i = 0; i < instr->num_srcs; i++) {
474 switch (instr->src[i].src_type) {
475 case nir_tex_src_sampler_deref:
476 case nir_tex_src_sampler_handle:
477 case nir_tex_src_sampler_offset:
478 is_divergent |= instr->src[i].src.ssa->divergent &&
479 instr->sampler_non_uniform;
480 break;
481 case nir_tex_src_texture_deref:
482 case nir_tex_src_texture_handle:
483 case nir_tex_src_texture_offset:
484 is_divergent |= instr->src[i].src.ssa->divergent &&
485 instr->texture_non_uniform;
486 break;
487 default:
488 is_divergent |= instr->src[i].src.ssa->divergent;
489 break;
490 }
491 }
492
493 instr->dest.ssa.divergent = is_divergent;
494 return is_divergent;
495 }
496
497 static bool
498 visit_load_const(nir_load_const_instr *instr)
499 {
500 return false;
501 }
502
503 static bool
504 visit_ssa_undef(nir_ssa_undef_instr *instr)
505 {
506 return false;
507 }
508
509 static bool
510 nir_variable_mode_is_uniform(nir_variable_mode mode) {
511 switch (mode) {
512 case nir_var_uniform:
513 case nir_var_mem_ubo:
514 case nir_var_mem_ssbo:
515 case nir_var_mem_shared:
516 case nir_var_mem_global:
517 return true;
518 default:
519 return false;
520 }
521 }
522
523 static bool
524 nir_variable_is_uniform(nir_variable *var, struct divergence_state *state)
525 {
526 if (nir_variable_mode_is_uniform(var->data.mode))
527 return true;
528
529 if (state->stage == MESA_SHADER_FRAGMENT &&
530 (state->options & nir_divergence_single_prim_per_subgroup) &&
531 var->data.mode == nir_var_shader_in &&
532 var->data.interpolation == INTERP_MODE_FLAT)
533 return true;
534
535 if (state->stage == MESA_SHADER_TESS_CTRL &&
536 (state->options & nir_divergence_single_patch_per_tcs_subgroup) &&
537 var->data.mode == nir_var_shader_out && var->data.patch)
538 return true;
539
540 if (state->stage == MESA_SHADER_TESS_EVAL &&
541 (state->options & nir_divergence_single_patch_per_tes_subgroup) &&
542 var->data.mode == nir_var_shader_in && var->data.patch)
543 return true;
544
545 return false;
546 }
547
548 static bool
549 visit_deref(nir_deref_instr *deref, struct divergence_state *state)
550 {
551 if (deref->dest.ssa.divergent)
552 return false;
553
554 bool is_divergent = false;
555 switch (deref->deref_type) {
556 case nir_deref_type_var:
557 is_divergent = !nir_variable_is_uniform(deref->var, state);
558 break;
559 case nir_deref_type_array:
560 case nir_deref_type_ptr_as_array:
561 is_divergent = deref->arr.index.ssa->divergent;
562 /* fallthrough */
563 case nir_deref_type_struct:
564 case nir_deref_type_array_wildcard:
565 is_divergent |= deref->parent.ssa->divergent;
566 break;
567 case nir_deref_type_cast:
568 is_divergent = !nir_variable_mode_is_uniform(deref->var->data.mode) ||
569 deref->parent.ssa->divergent;
570 break;
571 }
572
573 deref->dest.ssa.divergent = is_divergent;
574 return is_divergent;
575 }
576
577 static bool
578 visit_jump(nir_jump_instr *jump, struct divergence_state *state)
579 {
580 switch (jump->type) {
581 case nir_jump_continue:
582 if (state->divergent_loop_continue)
583 return false;
584 if (state->divergent_loop_cf)
585 state->divergent_loop_continue = true;
586 return state->divergent_loop_continue;
587 case nir_jump_break:
588 if (state->divergent_loop_break)
589 return false;
590 if (state->divergent_loop_cf)
591 state->divergent_loop_break = true;
592 return state->divergent_loop_break;
593 case nir_jump_return:
594 unreachable("NIR divergence analysis: Unsupported return instruction.");
595 }
596 return false;
597 }
598
599 static bool
600 set_ssa_def_not_divergent(nir_ssa_def *def, UNUSED void *_state)
601 {
602 def->divergent = false;
603 return true;
604 }
605
606 static bool
607 visit_block(nir_block *block, struct divergence_state *state)
608 {
609 bool has_changed = false;
610
611 nir_foreach_instr(instr, block) {
612 /* phis are handled when processing the branches */
613 if (instr->type == nir_instr_type_phi)
614 continue;
615
616 if (state->first_visit)
617 nir_foreach_ssa_def(instr, set_ssa_def_not_divergent, NULL);
618
619 switch (instr->type) {
620 case nir_instr_type_alu:
621 has_changed |= visit_alu(nir_instr_as_alu(instr));
622 break;
623 case nir_instr_type_intrinsic:
624 has_changed |= visit_intrinsic(nir_instr_as_intrinsic(instr), state);
625 break;
626 case nir_instr_type_tex:
627 has_changed |= visit_tex(nir_instr_as_tex(instr));
628 break;
629 case nir_instr_type_load_const:
630 has_changed |= visit_load_const(nir_instr_as_load_const(instr));
631 break;
632 case nir_instr_type_ssa_undef:
633 has_changed |= visit_ssa_undef(nir_instr_as_ssa_undef(instr));
634 break;
635 case nir_instr_type_deref:
636 has_changed |= visit_deref(nir_instr_as_deref(instr), state);
637 break;
638 case nir_instr_type_jump:
639 has_changed |= visit_jump(nir_instr_as_jump(instr), state);
640 break;
641 case nir_instr_type_phi:
642 case nir_instr_type_call:
643 case nir_instr_type_parallel_copy:
644 unreachable("NIR divergence analysis: Unsupported instruction type.");
645 }
646 }
647
648 return has_changed;
649 }
650
651 /* There are 3 types of phi instructions:
652 * (1) gamma: represent the joining point of different paths
653 * created by an “if-then-else” branch.
654 * The resulting value is divergent if the branch condition
655 * or any of the source values is divergent. */
656 static bool
657 visit_if_merge_phi(nir_phi_instr *phi, bool if_cond_divergent)
658 {
659 if (phi->dest.ssa.divergent)
660 return false;
661
662 unsigned defined_srcs = 0;
663 nir_foreach_phi_src(src, phi) {
664 /* if any source value is divergent, the resulting value is divergent */
665 if (src->src.ssa->divergent) {
666 phi->dest.ssa.divergent = true;
667 return true;
668 }
669 if (src->src.ssa->parent_instr->type != nir_instr_type_ssa_undef) {
670 defined_srcs++;
671 }
672 }
673
674 /* if the condition is divergent and two sources defined, the definition is divergent */
675 if (defined_srcs > 1 && if_cond_divergent) {
676 phi->dest.ssa.divergent = true;
677 return true;
678 }
679
680 return false;
681 }
682
683 /* There are 3 types of phi instructions:
684 * (2) mu: which only exist at loop headers,
685 * merge initial and loop-carried values.
686 * The resulting value is divergent if any source value
687 * is divergent or a divergent loop continue condition
688 * is associated with a different ssa-def. */
689 static bool
690 visit_loop_header_phi(nir_phi_instr *phi, nir_block *preheader, bool divergent_continue)
691 {
692 if (phi->dest.ssa.divergent)
693 return false;
694
695 nir_ssa_def* same = NULL;
696 nir_foreach_phi_src(src, phi) {
697 /* if any source value is divergent, the resulting value is divergent */
698 if (src->src.ssa->divergent) {
699 phi->dest.ssa.divergent = true;
700 return true;
701 }
702 /* if this loop is uniform, we're done here */
703 if (!divergent_continue)
704 continue;
705 /* skip the loop preheader */
706 if (src->pred == preheader)
707 continue;
708 /* skip undef values */
709 if (src->src.ssa->parent_instr->type == nir_instr_type_ssa_undef)
710 continue;
711
712 /* check if all loop-carried values are from the same ssa-def */
713 if (!same)
714 same = src->src.ssa;
715 else if (same != src->src.ssa) {
716 phi->dest.ssa.divergent = true;
717 return true;
718 }
719 }
720
721 return false;
722 }
723
724 /* There are 3 types of phi instructions:
725 * (3) eta: represent values that leave a loop.
726 * The resulting value is divergent if the source value is divergent
727 * or any loop exit condition is divergent for a value which is
728 * not loop-invariant.
729 * (note: there should be no phi for loop-invariant variables.) */
730 static bool
731 visit_loop_exit_phi(nir_phi_instr *phi, bool divergent_break)
732 {
733 if (phi->dest.ssa.divergent)
734 return false;
735
736 if (divergent_break) {
737 phi->dest.ssa.divergent = true;
738 return true;
739 }
740
741 /* if any source value is divergent, the resulting value is divergent */
742 nir_foreach_phi_src(src, phi) {
743 if (src->src.ssa->divergent) {
744 phi->dest.ssa.divergent = true;
745 return true;
746 }
747 }
748
749 return false;
750 }
751
752 static bool
753 visit_if(nir_if *if_stmt, struct divergence_state *state)
754 {
755 bool progress = false;
756
757 struct divergence_state then_state = *state;
758 then_state.divergent_loop_cf |= if_stmt->condition.ssa->divergent;
759 progress |= visit_cf_list(&if_stmt->then_list, &then_state);
760
761 struct divergence_state else_state = *state;
762 else_state.divergent_loop_cf |= if_stmt->condition.ssa->divergent;
763 progress |= visit_cf_list(&if_stmt->else_list, &else_state);
764
765 /* handle phis after the IF */
766 nir_foreach_instr(instr, nir_cf_node_cf_tree_next(&if_stmt->cf_node)) {
767 if (instr->type != nir_instr_type_phi)
768 break;
769
770 if (state->first_visit)
771 nir_instr_as_phi(instr)->dest.ssa.divergent = false;
772 progress |= visit_if_merge_phi(nir_instr_as_phi(instr),
773 if_stmt->condition.ssa->divergent);
774 }
775
776 /* join loop divergence information from both branch legs */
777 state->divergent_loop_continue |= then_state.divergent_loop_continue ||
778 else_state.divergent_loop_continue;
779 state->divergent_loop_break |= then_state.divergent_loop_break ||
780 else_state.divergent_loop_break;
781
782 /* A divergent continue makes succeeding loop CF divergent:
783 * not all loop-active invocations participate in the remaining loop-body
784 * which means that a following break might be taken by some invocations, only */
785 state->divergent_loop_cf |= state->divergent_loop_continue;
786
787 return progress;
788 }
789
790 static bool
791 visit_loop(nir_loop *loop, struct divergence_state *state)
792 {
793 bool progress = false;
794 nir_block *loop_header = nir_loop_first_block(loop);
795 nir_block *loop_preheader = nir_block_cf_tree_prev(loop_header);
796
797 /* handle loop header phis first: we have no knowledge yet about
798 * the loop's control flow or any loop-carried sources. */
799 nir_foreach_instr(instr, loop_header) {
800 if (instr->type != nir_instr_type_phi)
801 break;
802
803 nir_phi_instr *phi = nir_instr_as_phi(instr);
804 if (!state->first_visit && phi->dest.ssa.divergent)
805 continue;
806
807 nir_foreach_phi_src(src, phi) {
808 if (src->pred == loop_preheader) {
809 phi->dest.ssa.divergent = src->src.ssa->divergent;
810 break;
811 }
812 }
813 progress |= phi->dest.ssa.divergent;
814 }
815
816 /* setup loop state */
817 struct divergence_state loop_state = *state;
818 loop_state.divergent_loop_cf = false;
819 loop_state.divergent_loop_continue = false;
820 loop_state.divergent_loop_break = false;
821
822 /* process loop body until no further changes are made */
823 bool repeat;
824 do {
825 progress |= visit_cf_list(&loop->body, &loop_state);
826 repeat = false;
827
828 /* revisit loop header phis to see if something has changed */
829 nir_foreach_instr(instr, loop_header) {
830 if (instr->type != nir_instr_type_phi)
831 break;
832
833 repeat |= visit_loop_header_phi(nir_instr_as_phi(instr),
834 loop_preheader,
835 loop_state.divergent_loop_continue);
836 }
837
838 loop_state.divergent_loop_cf = false;
839 loop_state.first_visit = false;
840 } while (repeat);
841
842 /* handle phis after the loop */
843 nir_foreach_instr(instr, nir_cf_node_cf_tree_next(&loop->cf_node)) {
844 if (instr->type != nir_instr_type_phi)
845 break;
846
847 if (state->first_visit)
848 nir_instr_as_phi(instr)->dest.ssa.divergent = false;
849 progress |= visit_loop_exit_phi(nir_instr_as_phi(instr),
850 loop_state.divergent_loop_break);
851 }
852
853 return progress;
854 }
855
856 static bool
857 visit_cf_list(struct exec_list *list, struct divergence_state *state)
858 {
859 bool has_changed = false;
860
861 foreach_list_typed(nir_cf_node, node, node, list) {
862 switch (node->type) {
863 case nir_cf_node_block:
864 has_changed |= visit_block(nir_cf_node_as_block(node), state);
865 break;
866 case nir_cf_node_if:
867 has_changed |= visit_if(nir_cf_node_as_if(node), state);
868 break;
869 case nir_cf_node_loop:
870 has_changed |= visit_loop(nir_cf_node_as_loop(node), state);
871 break;
872 case nir_cf_node_function:
873 unreachable("NIR divergence analysis: Unsupported cf_node type.");
874 }
875 }
876
877 return has_changed;
878 }
879
880 void
881 nir_divergence_analysis(nir_shader *shader, nir_divergence_options options)
882 {
883 struct divergence_state state = {
884 .options = options,
885 .stage = shader->info.stage,
886 .divergent_loop_cf = false,
887 .divergent_loop_continue = false,
888 .divergent_loop_break = false,
889 .first_visit = true,
890 };
891
892 visit_cf_list(&nir_shader_get_entrypoint(shader)->body, &state);
893 }
894