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