nir/algebraic: trivially enable existing 32-bit patterns for all bit sizes
[mesa.git] / src / compiler / nir / nir_divergence_analysis.c
index 402a2b00a54dbda241144068788d3d46414f18b0..85663c83615ee7b4b8cc7a5a9fd9a43769e71223 100644 (file)
 struct divergence_state {
    const nir_divergence_options options;
    const gl_shader_stage stage;
+
+   /** current control flow state */
+   /* True if some loop-active invocations might take a different control-flow path.
+    * A divergent break does not cause subsequent control-flow to be considered
+    * divergent because those invocations are no longer active in the loop.
+    * For a divergent if, both sides are considered divergent flow because
+    * the other side is still loop-active. */
+   bool divergent_loop_cf;
+   /* True if a divergent continue happened since the loop header */
+   bool divergent_loop_continue;
+   /* True if a divergent break happened since the loop header */
+   bool divergent_loop_break;
+
+   /* True if we visit the block for the fist time */
+   bool first_visit;
 };
 
 static bool
@@ -130,6 +145,16 @@ visit_intrinsic(nir_intrinsic_instr *instr, struct divergence_state *state)
       else
          is_divergent = true;
       break;
+   case nir_intrinsic_load_per_vertex_input:
+      is_divergent = instr->src[0].ssa->divergent ||
+                     instr->src[1].ssa->divergent;
+      if (stage == MESA_SHADER_TESS_CTRL)
+         is_divergent |= !(options & nir_divergence_single_patch_per_tcs_subgroup);
+      if (stage == MESA_SHADER_TESS_EVAL)
+         is_divergent |= !(options & nir_divergence_single_patch_per_tes_subgroup);
+      else
+         is_divergent = true;
+      break;
    case nir_intrinsic_load_input_vertex:
       is_divergent = instr->src[1].ssa->divergent;
       assert(stage == MESA_SHADER_FRAGMENT);
@@ -143,6 +168,12 @@ visit_intrinsic(nir_intrinsic_instr *instr, struct divergence_state *state)
       else
          is_divergent = true;
       break;
+   case nir_intrinsic_load_per_vertex_output:
+      assert(stage == MESA_SHADER_TESS_CTRL);
+      is_divergent = instr->src[0].ssa->divergent ||
+                     instr->src[1].ssa->divergent ||
+                     !(options & nir_divergence_single_patch_per_tcs_subgroup);
+      break;
    case nir_intrinsic_load_layer_id:
    case nir_intrinsic_load_front_face:
       assert(stage == MESA_SHADER_FRAGMENT);
@@ -224,6 +255,7 @@ visit_intrinsic(nir_intrinsic_instr *instr, struct divergence_state *state)
    case nir_intrinsic_load_ssbo:
    case nir_intrinsic_load_shared:
    case nir_intrinsic_load_global:
+   case nir_intrinsic_load_global_constant:
    case nir_intrinsic_load_uniform:
    case nir_intrinsic_load_push_constant:
    case nir_intrinsic_load_constant:
@@ -283,12 +315,11 @@ visit_intrinsic(nir_intrinsic_instr *instr, struct divergence_state *state)
    case nir_intrinsic_interp_deref_at_vertex:
    case nir_intrinsic_load_tess_coord:
    case nir_intrinsic_load_point_coord:
+   case nir_intrinsic_load_line_coord:
    case nir_intrinsic_load_frag_coord:
    case nir_intrinsic_load_sample_pos:
    case nir_intrinsic_load_vertex_id_zero_base:
    case nir_intrinsic_load_vertex_id:
-   case nir_intrinsic_load_per_vertex_input:
-   case nir_intrinsic_load_per_vertex_output:
    case nir_intrinsic_load_instance_id:
    case nir_intrinsic_load_invocation_id:
    case nir_intrinsic_load_local_invocation_id:
@@ -465,169 +496,6 @@ visit_tex(nir_tex_instr *instr)
    return is_divergent;
 }
 
-static bool
-visit_phi(nir_phi_instr *instr)
-{
-   /* There are 3 types of phi instructions:
-    * (1) gamma: represent the joining point of different paths
-    *     created by an “if-then-else” branch.
-    *     The resulting value is divergent if the branch condition
-    *     or any of the source values is divergent.
-    *
-    * (2) mu: which only exist at loop headers,
-    *     merge initial and loop-carried values.
-    *     The resulting value is divergent if any source value
-    *     is divergent or a divergent loop continue condition
-    *     is associated with a different ssa-def.
-    *
-    * (3) eta: represent values that leave a loop.
-    *     The resulting value is divergent if the source value is divergent
-    *     or any loop exit condition is divergent for a value which is
-    *     not loop-invariant.
-    *     (note: there should be no phi for loop-invariant variables.)
-    */
-
-   if (instr->dest.ssa.divergent)
-      return false;
-
-   nir_foreach_phi_src(src, instr) {
-      /* if any source value is divergent, the resulting value is divergent */
-      if (src->src.ssa->divergent) {
-         instr->dest.ssa.divergent = true;
-         return true;
-      }
-   }
-
-   nir_cf_node *prev = nir_cf_node_prev(&instr->instr.block->cf_node);
-
-   if (!prev) {
-      /* mu: if no predecessor node exists, the phi must be at a loop header */
-      nir_loop *loop = nir_cf_node_as_loop(instr->instr.block->cf_node.parent);
-      prev = nir_cf_node_prev(&loop->cf_node);
-      nir_ssa_def* same = NULL;
-      bool all_same = true;
-
-      /* first, check if all loop-carried values are from the same ssa-def */
-      nir_foreach_phi_src(src, instr) {
-         if (src->pred == nir_cf_node_as_block(prev))
-            continue;
-         if (src->src.ssa->parent_instr->type == nir_instr_type_ssa_undef)
-            continue;
-         if (!same)
-            same = src->src.ssa;
-         else if (same != src->src.ssa)
-            all_same = false;
-      }
-
-      /* if all loop-carried values are the same, the resulting value is uniform */
-      if (all_same)
-         return false;
-
-      /* check if the loop-carried values come from different ssa-defs
-       * and the corresponding condition is divergent. */
-      nir_foreach_phi_src(src, instr) {
-         /* skip the loop preheader */
-         if (src->pred == nir_cf_node_as_block(prev))
-            continue;
-
-         /* skip the unconditional back-edge */
-         if (src->pred == nir_loop_last_block(loop))
-            continue;
-
-         /* if the value is undef, we don't need to check the condition */
-         if (src->src.ssa->parent_instr->type == nir_instr_type_ssa_undef)
-            continue;
-
-         nir_cf_node *current = src->pred->cf_node.parent;
-         /* check recursively the conditions if any is divergent */
-         while (current->type != nir_cf_node_loop) {
-            assert (current->type == nir_cf_node_if);
-            nir_if *if_node = nir_cf_node_as_if(current);
-            if (if_node->condition.ssa->divergent) {
-               instr->dest.ssa.divergent = true;
-               return true;
-            }
-            current = current->parent;
-         }
-         assert(current == &loop->cf_node);
-      }
-
-   } else if (prev->type == nir_cf_node_if) {
-      /* if only one of the incoming values is defined, the resulting value is uniform */
-      unsigned defined_srcs = 0;
-      nir_foreach_phi_src(src, instr) {
-         if (src->src.ssa->parent_instr->type != nir_instr_type_ssa_undef)
-            defined_srcs++;
-      }
-      if (defined_srcs <= 1)
-         return false;
-
-      /* gamma: check if the condition is divergent */
-      nir_if *if_node = nir_cf_node_as_if(prev);
-      if (if_node->condition.ssa->divergent) {
-         instr->dest.ssa.divergent = true;
-         return true;
-      }
-
-   } else {
-      /* eta: the predecessor must be a loop */
-      assert(prev->type == nir_cf_node_loop);
-
-      /* Check if any loop exit condition is divergent:
-       * That is any break happens under divergent condition or
-       * a break is preceeded by a divergent continue
-       */
-      nir_foreach_phi_src(src, instr) {
-         nir_cf_node *current = src->pred->cf_node.parent;
-
-         /* check recursively the conditions if any is divergent */
-         while (current->type != nir_cf_node_loop) {
-            assert(current->type == nir_cf_node_if);
-            nir_if *if_node = nir_cf_node_as_if(current);
-            if (if_node->condition.ssa->divergent) {
-               instr->dest.ssa.divergent = true;
-               return true;
-            }
-            current = current->parent;
-         }
-         assert(current == prev);
-
-         /* check if any divergent continue happened before the break */
-         nir_foreach_block_in_cf_node(block, prev) {
-            if (block == src->pred)
-               break;
-            if (!nir_block_ends_in_jump(block))
-               continue;
-
-            nir_jump_instr *jump = nir_instr_as_jump(nir_block_last_instr(block));
-            if (jump->type != nir_jump_continue)
-               continue;
-
-            current = block->cf_node.parent;
-            bool is_divergent = false;
-            while (current != prev) {
-               /* the continue belongs to an inner loop */
-               if (current->type == nir_cf_node_loop) {
-                  is_divergent = false;
-                  break;
-               }
-               assert(current->type == nir_cf_node_if);
-               nir_if *if_node = nir_cf_node_as_if(current);
-               is_divergent |= if_node->condition.ssa->divergent;
-               current = current->parent;
-            }
-
-            if (is_divergent) {
-               instr->dest.ssa.divergent = true;
-               return true;
-            }
-         }
-      }
-   }
-
-   return false;
-}
-
 static bool
 visit_load_const(nir_load_const_instr *instr)
 {
@@ -708,12 +576,53 @@ visit_deref(nir_deref_instr *deref, struct divergence_state *state)
    return is_divergent;
 }
 
+static bool
+visit_jump(nir_jump_instr *jump, struct divergence_state *state)
+{
+   switch (jump->type) {
+   case nir_jump_continue:
+      if (state->divergent_loop_continue)
+         return false;
+      if (state->divergent_loop_cf)
+         state->divergent_loop_continue = true;
+      return state->divergent_loop_continue;
+   case nir_jump_break:
+      if (state->divergent_loop_break)
+         return false;
+      if (state->divergent_loop_cf)
+         state->divergent_loop_break = true;
+      return state->divergent_loop_break;
+   case nir_jump_return:
+      unreachable("NIR divergence analysis: Unsupported return instruction.");
+      break;
+   case nir_jump_goto:
+   case nir_jump_goto_if:
+      unreachable("NIR divergence analysis: Unsupported goto_if instruction.");
+      break;
+   }
+   return false;
+}
+
+static bool
+set_ssa_def_not_divergent(nir_ssa_def *def, UNUSED void *_state)
+{
+   def->divergent = false;
+   return true;
+}
+
 static bool
 visit_block(nir_block *block, struct divergence_state *state)
 {
    bool has_changed = false;
 
    nir_foreach_instr(instr, block) {
+      /* phis are handled when processing the branches */
+      if (instr->type == nir_instr_type_phi)
+         continue;
+
+      if (state->first_visit)
+         nir_foreach_ssa_def(instr, set_ssa_def_not_divergent, NULL);
+
       switch (instr->type) {
       case nir_instr_type_alu:
          has_changed |= visit_alu(nir_instr_as_alu(instr));
@@ -724,9 +633,6 @@ visit_block(nir_block *block, struct divergence_state *state)
       case nir_instr_type_tex:
          has_changed |= visit_tex(nir_instr_as_tex(instr));
          break;
-      case nir_instr_type_phi:
-         has_changed |= visit_phi(nir_instr_as_phi(instr));
-         break;
       case nir_instr_type_load_const:
          has_changed |= visit_load_const(nir_instr_as_load_const(instr));
          break;
@@ -737,7 +643,9 @@ visit_block(nir_block *block, struct divergence_state *state)
          has_changed |= visit_deref(nir_instr_as_deref(instr), state);
          break;
       case nir_instr_type_jump:
+         has_changed |= visit_jump(nir_instr_as_jump(instr), state);
          break;
+      case nir_instr_type_phi:
       case nir_instr_type_call:
       case nir_instr_type_parallel_copy:
          unreachable("NIR divergence analysis: Unsupported instruction type.");
@@ -747,26 +655,209 @@ visit_block(nir_block *block, struct divergence_state *state)
    return has_changed;
 }
 
+/* There are 3 types of phi instructions:
+ * (1) gamma: represent the joining point of different paths
+ *     created by an “if-then-else” branch.
+ *     The resulting value is divergent if the branch condition
+ *     or any of the source values is divergent. */
+static bool
+visit_if_merge_phi(nir_phi_instr *phi, bool if_cond_divergent)
+{
+   if (phi->dest.ssa.divergent)
+      return false;
+
+   unsigned defined_srcs = 0;
+   nir_foreach_phi_src(src, phi) {
+      /* if any source value is divergent, the resulting value is divergent */
+      if (src->src.ssa->divergent) {
+         phi->dest.ssa.divergent = true;
+         return true;
+      }
+      if (src->src.ssa->parent_instr->type != nir_instr_type_ssa_undef) {
+         defined_srcs++;
+      }
+   }
+
+   /* if the condition is divergent and two sources defined, the definition is divergent */
+   if (defined_srcs > 1 && if_cond_divergent) {
+      phi->dest.ssa.divergent = true;
+      return true;
+   }
+
+   return false;
+}
+
+/* There are 3 types of phi instructions:
+ * (2) mu: which only exist at loop headers,
+ *     merge initial and loop-carried values.
+ *     The resulting value is divergent if any source value
+ *     is divergent or a divergent loop continue condition
+ *     is associated with a different ssa-def. */
+static bool
+visit_loop_header_phi(nir_phi_instr *phi, nir_block *preheader, bool divergent_continue)
+{
+   if (phi->dest.ssa.divergent)
+      return false;
+
+   nir_ssa_def* same = NULL;
+   nir_foreach_phi_src(src, phi) {
+      /* if any source value is divergent, the resulting value is divergent */
+      if (src->src.ssa->divergent) {
+         phi->dest.ssa.divergent = true;
+         return true;
+      }
+      /* if this loop is uniform, we're done here */
+      if (!divergent_continue)
+         continue;
+      /* skip the loop preheader */
+      if (src->pred == preheader)
+         continue;
+      /* skip undef values */
+      if (src->src.ssa->parent_instr->type == nir_instr_type_ssa_undef)
+         continue;
+
+      /* check if all loop-carried values are from the same ssa-def */
+      if (!same)
+         same = src->src.ssa;
+      else if (same != src->src.ssa) {
+         phi->dest.ssa.divergent = true;
+         return true;
+      }
+   }
+
+   return false;
+}
+
+/* There are 3 types of phi instructions:
+ * (3) eta: represent values that leave a loop.
+ *     The resulting value is divergent if the source value is divergent
+ *     or any loop exit condition is divergent for a value which is
+ *     not loop-invariant.
+ *     (note: there should be no phi for loop-invariant variables.) */
+static bool
+visit_loop_exit_phi(nir_phi_instr *phi, bool divergent_break)
+{
+   if (phi->dest.ssa.divergent)
+      return false;
+
+   if (divergent_break) {
+      phi->dest.ssa.divergent = true;
+      return true;
+   }
+
+   /* if any source value is divergent, the resulting value is divergent */
+   nir_foreach_phi_src(src, phi) {
+      if (src->src.ssa->divergent) {
+         phi->dest.ssa.divergent = true;
+         return true;
+      }
+   }
+
+   return false;
+}
+
 static bool
 visit_if(nir_if *if_stmt, struct divergence_state *state)
 {
-   return visit_cf_list(&if_stmt->then_list, state) |
-          visit_cf_list(&if_stmt->else_list, state);
+   bool progress = false;
+
+   struct divergence_state then_state = *state;
+   then_state.divergent_loop_cf |= if_stmt->condition.ssa->divergent;
+   progress |= visit_cf_list(&if_stmt->then_list, &then_state);
+
+   struct divergence_state else_state = *state;
+   else_state.divergent_loop_cf |= if_stmt->condition.ssa->divergent;
+   progress |= visit_cf_list(&if_stmt->else_list, &else_state);
+
+   /* handle phis after the IF */
+   nir_foreach_instr(instr, nir_cf_node_cf_tree_next(&if_stmt->cf_node)) {
+      if (instr->type != nir_instr_type_phi)
+         break;
+
+      if (state->first_visit)
+         nir_instr_as_phi(instr)->dest.ssa.divergent = false;
+      progress |= visit_if_merge_phi(nir_instr_as_phi(instr),
+                                     if_stmt->condition.ssa->divergent);
+   }
+
+   /* join loop divergence information from both branch legs */
+   state->divergent_loop_continue |= then_state.divergent_loop_continue ||
+                                     else_state.divergent_loop_continue;
+   state->divergent_loop_break |= then_state.divergent_loop_break ||
+                                  else_state.divergent_loop_break;
+
+   /* A divergent continue makes succeeding loop CF divergent:
+    * not all loop-active invocations participate in the remaining loop-body
+    * which means that a following break might be taken by some invocations, only */
+   state->divergent_loop_cf |= state->divergent_loop_continue;
+
+   return progress;
 }
 
 static bool
 visit_loop(nir_loop *loop, struct divergence_state *state)
 {
-   bool has_changed = false;
-   bool repeat = true;
+   bool progress = false;
+   nir_block *loop_header = nir_loop_first_block(loop);
+   nir_block *loop_preheader = nir_block_cf_tree_prev(loop_header);
+
+   /* handle loop header phis first: we have no knowledge yet about
+    * the loop's control flow or any loop-carried sources. */
+   nir_foreach_instr(instr, loop_header) {
+      if (instr->type != nir_instr_type_phi)
+         break;
 
-   /* TODO: restructure this and the phi handling more efficiently */
-   while (repeat) {
-      repeat = visit_cf_list(&loop->body, state);
-      has_changed |= repeat;
+      nir_phi_instr *phi = nir_instr_as_phi(instr);
+      if (!state->first_visit && phi->dest.ssa.divergent)
+         continue;
+
+      nir_foreach_phi_src(src, phi) {
+         if (src->pred == loop_preheader) {
+            phi->dest.ssa.divergent = src->src.ssa->divergent;
+            break;
+         }
+      }
+      progress |= phi->dest.ssa.divergent;
    }
 
-   return has_changed;
+   /* setup loop state */
+   struct divergence_state loop_state = *state;
+   loop_state.divergent_loop_cf = false;
+   loop_state.divergent_loop_continue = false;
+   loop_state.divergent_loop_break = false;
+
+   /* process loop body until no further changes are made */
+   bool repeat;
+   do {
+      progress |= visit_cf_list(&loop->body, &loop_state);
+      repeat = false;
+
+      /* revisit loop header phis to see if something has changed */
+      nir_foreach_instr(instr, loop_header) {
+         if (instr->type != nir_instr_type_phi)
+            break;
+
+         repeat |= visit_loop_header_phi(nir_instr_as_phi(instr),
+                                         loop_preheader,
+                                         loop_state.divergent_loop_continue);
+      }
+
+      loop_state.divergent_loop_cf = false;
+      loop_state.first_visit = false;
+   } while (repeat);
+
+   /* handle phis after the loop */
+   nir_foreach_instr(instr, nir_cf_node_cf_tree_next(&loop->cf_node)) {
+      if (instr->type != nir_instr_type_phi)
+         break;
+
+      if (state->first_visit)
+         nir_instr_as_phi(instr)->dest.ssa.divergent = false;
+      progress |= visit_loop_exit_phi(nir_instr_as_phi(instr),
+                                      loop_state.divergent_loop_break);
+   }
+
+   return progress;
 }
 
 static bool
@@ -793,29 +884,18 @@ visit_cf_list(struct exec_list *list, struct divergence_state *state)
    return has_changed;
 }
 
-static bool
-set_ssa_def_not_divergent(nir_ssa_def *def, UNUSED void *_state)
-{
-   def->divergent = false;
-   return true;
-}
-
 void
 nir_divergence_analysis(nir_shader *shader, nir_divergence_options options)
 {
-   nir_function_impl *impl = nir_shader_get_entrypoint(shader);
-
-   /* Set all SSA defs to non-divergent to start off */
-   nir_foreach_block(block, impl) {
-      nir_foreach_instr(instr, block)
-         nir_foreach_ssa_def(instr, set_ssa_def_not_divergent, NULL);
-   }
-
    struct divergence_state state = {
       .options = options,
       .stage = shader->info.stage,
+      .divergent_loop_cf = false,
+      .divergent_loop_continue = false,
+      .divergent_loop_break = false,
+      .first_visit = true,
    };
 
-   visit_cf_list(&impl->body, &state);
+   visit_cf_list(&nir_shader_get_entrypoint(shader)->body, &state);
 }