<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>Hello,</div><div><br></div><div>Please find my comment below:<br></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Oct 8, 2018 at 2:15 PM Daniel Schürmann <<a href="mailto:daniel.schuermann@campus.tu-berlin.de">daniel.schuermann@campus.tu-berlin.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">---<br>
 src/compiler/nir/meson.build               |   1 +<br>
 src/compiler/nir/nir.h                     |   2 +<br>
 src/compiler/nir/nir_divergence_analysis.c | 333 +++++++++++++++++++++<br>
 3 files changed, 336 insertions(+)<br>
 create mode 100644 src/compiler/nir/nir_divergence_analysis.c<br>
<br>
diff --git a/src/compiler/nir/meson.build b/src/compiler/nir/meson.build<br>
index 090aa7a628..aabfeee02c 100644<br>
--- a/src/compiler/nir/meson.build<br>
+++ b/src/compiler/nir/meson.build<br>
@@ -96,6 +96,7 @@ files_libnir = files(<br>
   'nir_control_flow_private.h',<br>
   'nir_deref.c',<br>
   'nir_deref.h',<br>
+  'nir_divergence_analysis.c',<br>
   'nir_dominance.c',<br>
   'nir_format_convert.h',<br>
   'nir_from_ssa.c',<br>
diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h<br>
index e0df95c391..374280a1cc 100644<br>
--- a/src/compiler/nir/nir.h<br>
+++ b/src/compiler/nir/nir.h<br>
@@ -3010,6 +3010,8 @@ void nir_convert_loop_to_lcssa(nir_loop *loop);<br>
  */<br>
 bool nir_convert_from_ssa(nir_shader *shader, bool phi_webs_only);<br>
<br>
+bool* nir_divergence_analysis(nir_shader *shader);<br>
+<br>
 bool nir_lower_phis_to_regs_block(nir_block *block);<br>
 bool nir_lower_ssa_defs_to_regs_block(nir_block *block);<br>
 bool nir_rematerialize_derefs_in_use_blocks_impl(nir_function_impl *impl);<br>
diff --git a/src/compiler/nir/nir_divergence_analysis.c b/src/compiler/nir/nir_divergence_analysis.c<br>
new file mode 100644<br>
index 0000000000..d91f4e55e6<br>
--- /dev/null<br>
+++ b/src/compiler/nir/nir_divergence_analysis.c<br>
@@ -0,0 +1,333 @@<br>
+/*<br>
+ * Copyright © 2018 Valve Corporation<br>
+ *<br>
+ * Permission is hereby granted, free of charge, to any person obtaining a<br>
+ * copy of this software and associated documentation files (the "Software"),<br>
+ * to deal in the Software without restriction, including without limitation<br>
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,<br>
+ * and/or sell copies of the Software, and to permit persons to whom the<br>
+ * Software is furnished to do so, subject to the following conditions:<br>
+ *<br>
+ * The above copyright notice and this permission notice (including the next<br>
+ * paragraph) shall be included in all copies or substantial portions of the<br>
+ * Software.<br>
+ *<br>
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR<br>
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,<br>
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL<br>
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER<br>
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING<br>
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS<br>
+ * IN THE SOFTWARE.<br>
+ *<br>
+ * Authors:<br>
+ *    Daniel Schürmann (<a href="mailto:daniel.schuermann@campus.tu-berlin.de" target="_blank">daniel.schuermann@campus.tu-berlin.de</a>)<br>
+ *<br>
+ */<br>
+<br>
+#include "nir.h"<br>
+#include "nir_worklist.h"<br>
+<br>
+/* This pass computes for each ssa definition if it is uniform.<br>
+ * That is, the variable has the same value for all invocations<br>
+ * of the group.<br>
+ *<br>
+ * This algorithm implements "The Simple Divergence Analysis" from<br>
+ * Diogo Sampaio, Rafael De Souza, Sylvain Collange, Fernando Magno Quintão Pereira.<br>
+ * Divergence Analysis.  ACM Transactions on Programming Languages and Systems (TOPLAS),<br>
+ * ACM, 2013, 35 (4), pp.13:1-13:36. <10.1145/2523815>. <hal-00909072v2><br>
+ */<br>
+<br>
+<br>
+static bool alu_src_is_divergent(bool *divergent, nir_alu_src src, unsigned num_input_components)<br>
+{<br>
+   /* If the alu src is swizzled and defined by a vec-instruction,<br>
+    * we can check if the originating value is non-divergent. */<br>
+   if (num_input_components == 1 &&<br>
+       src.src.ssa->num_components != 1 &&<br>
+       src.src.parent_instr->type == nir_instr_type_alu) {<br>
+      nir_alu_instr *parent = nir_instr_as_alu(src.src.parent_instr);<br>
+      switch(parent->op) {<br>
+         case nir_op_vec2:<br>
+         case nir_op_vec3:<br>
+         case nir_op_vec4: {<br>
+            if (divergent[parent->src[src.swizzle[0]].src.ssa->index])<br>
+               return true;<br>
+            return false;<br></blockquote><div><br></div><div>Could it be better to just return a value from 'divergent' array here?<br></div><div>"return divergent[parent->src[src.swizzle[0]].src.ssa->index]"</div><div>I think it is not very matter but anyway just for case if you will make v2 patch for some reason :-)<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+         }<br>
+         default:<br>
+            break;<br>
+      }<br>
+   }<br>
+   return divergent[src.src.ssa->index];<br>
+}<br>
+<br>
+static bool visit_alu(bool *divergent, nir_alu_instr *instr)<br>
+{<br>
+   if (divergent[instr->dest.dest.ssa.index])<br>
+      return false;<br>
+   unsigned num_src = nir_op_infos[instr->op].num_inputs;<br>
+   for (unsigned i = 0; i < num_src; i++) {<br>
+      if (alu_src_is_divergent(divergent, instr->src[i], nir_op_infos[instr->op].input_sizes[i])) {<br>
+         divergent[instr->dest.dest.ssa.index] = true;<br>
+         return true;<br>
+      }<br>
+   }<br>
+   divergent[instr->dest.dest.ssa.index] = false;<br>
+   return false;<br>
+}<br>
+<br>
+static bool visit_intrinsic(bool *divergent, nir_intrinsic_instr *instr)<br>
+{<br>
+   if (!nir_intrinsic_infos[instr->intrinsic].has_dest)<br>
+      return false;<br>
+   if (divergent[instr->dest.ssa.index])<br>
+      return false;<br>
+   bool is_divergent = false;<br>
+   switch (instr->intrinsic) {<br>
+   /* TODO: load_shared_var */<br>
+   /*       load_uniform etc.*/<br>
+   case nir_intrinsic_shader_clock:<br>
+   case nir_intrinsic_ballot:<br>
+   case nir_intrinsic_read_invocation:<br>
+   case nir_intrinsic_read_first_invocation:<br>
+   case nir_intrinsic_vote_any:<br>
+   case nir_intrinsic_vote_all:<br>
+   case nir_intrinsic_vote_feq:<br>
+   case nir_intrinsic_vote_ieq:<br>
+   case nir_intrinsic_reduce:<br>
+   case nir_intrinsic_load_push_constant:<br>
+   case nir_intrinsic_vulkan_resource_index:<br>
+      is_divergent = false;<br>
+      break;<br>
+   case nir_intrinsic_load_ubo:<br>
+      for (unsigned i = 0; i < nir_intrinsic_infos[instr->intrinsic].num_srcs; i++) {<br>
+         if (divergent[instr->src[i].ssa->index]) {<br>
+            is_divergent = true;<br>
+            break;<br>
+         }<br>
+      }<br>
+      break;<br>
+   case nir_intrinsic_load_interpolated_input:<br>
+   case nir_intrinsic_load_barycentric_pixel:<br>
+   default:<br>
+      is_divergent = true;<br>
+      break;<br>
+   }<br>
+   divergent[instr->dest.ssa.index] = is_divergent;<br>
+   return is_divergent;<br>
+}<br>
+<br>
+static bool visit_tex(bool *divergent, nir_tex_instr *instr)<br>
+{<br>
+   if (divergent[instr->dest.ssa.index])<br>
+      return false;<br>
+   bool is_divergent = false;<br>
+   for (unsigned i = 0; i < instr->num_srcs; i++) {<br>
+      switch (instr->src[i].src_type) {<br>
+      case nir_tex_src_coord:<br>
+         is_divergent |= divergent[instr->src[i].src.ssa->index];<br>
+         break;<br>
+      default:<br>
+         break;<br>
+      }<br>
+   }<br>
+   divergent[instr->dest.ssa.index] = is_divergent;<br>
+   return is_divergent;<br>
+}<br>
+<br>
+<br>
+/** There are 3 types of phi instructions:<br>
+ * (1) gamma: represent the joining point of different paths<br>
+ *     created by an “if-then-else” branch.<br>
+ *     The resulting value is divergent if the branch condition<br>
+ *     or any of the source values is divergent.<br>
+ *<br>
+ * (2) mu: which only exist at loop headers,<br>
+ *     merge initial and loop-carried values.<br>
+ *     The resulting value is divergent if any source value<br>
+ *     is divergent or a divergent loop continue condition<br>
+ *     is associated with a different ssa-def.<br>
+ *<br>
+ * (3) eta: represent values that leave a loop.<br>
+ *     The resulting value is divergent if any loop exit condition<br>
+ *     or source value is divergent.<br>
+ */<br>
+static bool visit_phi(bool *divergent, nir_phi_instr *instr)<br>
+{<br>
+   if (divergent[instr->dest.ssa.index])<br>
+      return false;<br>
+<br>
+   /* if any source value is divergent, the resulting value is divergent */<br>
+   nir_foreach_phi_src(src, instr) {<br>
+      if (divergent[src->src.ssa->index]) {<br>
+         divergent[instr->dest.ssa.index] = true;<br>
+         return true;<br>
+      }<br>
+   }<br>
+<br>
+   nir_cf_node *prev = nir_cf_node_prev(&instr->instr.block->cf_node);<br>
+<br>
+   /* mu: if no predecessor node exists, the phi must be at a loop header */<br>
+   if (!prev) {<br>
+      /* find the two unconditional ssa-defs (the incoming value and the back-edge) */<br>
+      nir_loop *loop = nir_cf_node_as_loop(instr->instr.block->cf_node.parent);<br>
+      prev = nir_cf_node_prev(instr->instr.block->cf_node.parent);<br>
+      unsigned unconditional[2];<br>
+      unsigned idx = 0;<br>
+      nir_foreach_phi_src(src, instr) {<br>
+         if (src->pred == nir_loop_last_block(loop) ||<br>
+             src->pred == nir_cf_node_as_block(prev))<br>
+            unconditional[idx++] = src->src.ssa->index;<br>
+      }<br>
+      assert(idx == 2);<br>
+<br>
+      /* check if the loop-carried values come from a different ssa-def<br>
+       * and the corresponding condition is divergent. */<br>
+      nir_foreach_phi_src(src, instr) {<br>
+         if (src->src.ssa->index == unconditional[0] ||<br>
+             src->src.ssa->index == unconditional[1])<br>
+            continue;<br>
+<br>
+         nir_cf_node *current = src->pred->cf_node.parent;<br>
+         /* check recursively the conditions if any is divergent */<br>
+         while (current->type != nir_cf_node_loop) {<br>
+            if (current->type == nir_cf_node_if) {<br>
+               nir_if *if_node = nir_cf_node_as_if(current);<br>
+               if (divergent[if_node->condition.ssa->index]) {<br>
+                  divergent[instr->dest.ssa.index] = true;<br>
+                  return true;<br>
+               }<br>
+            }<br>
+            current = current->parent;<br>
+         }<br>
+      }<br>
+   }<br>
+<br>
+   /* gamma: check if the condition is divergent */<br>
+   else if (prev->type == nir_cf_node_if) {<br>
+      nir_if *if_node = nir_cf_node_as_if(prev);<br>
+      if (divergent[if_node->condition.ssa->index]) {<br>
+         divergent[instr->dest.ssa.index] = true;<br>
+         return true;<br>
+      }<br>
+   }<br>
+<br>
+   /* eta: check if any loop exit condition is divergent */<br>
+   else {<br>
+      assert(prev->type == nir_cf_node_loop);<br>
+      nir_foreach_phi_src(src, instr) {<br>
+         nir_cf_node *current = src->pred->cf_node.parent;<br>
+         assert(current->type == nir_cf_node_if);<br>
+<br>
+         /* check recursively the conditions if any is divergent */<br>
+         while (current->type != nir_cf_node_loop) {<br>
+            if (current->type == nir_cf_node_if) {<br>
+               nir_if *if_node = nir_cf_node_as_if(current);<br>
+               if (divergent[if_node->condition.ssa->index]) {<br>
+                  divergent[instr->dest.ssa.index] = true;<br>
+                  return true;<br>
+               }<br>
+            }<br>
+            current = current->parent;<br>
+         }<br>
+      }<br>
+   }<br>
+   divergent[instr->dest.ssa.index] = false;<br>
+   return false;<br>
+}<br>
+<br>
+static bool visit_parallel_copy(bool *divergent, nir_parallel_copy_instr *instr)<br>
+{<br>
+   bool has_changed = false;<br>
+   nir_foreach_parallel_copy_entry(entry, instr) {<br>
+      if (divergent[entry->dest.ssa.index])<br>
+         continue;<br>
+      divergent[entry->dest.ssa.index] = divergent[entry->src.ssa->index];<br>
+      if (divergent[entry->dest.ssa.index])<br>
+         has_changed = true;<br>
+   }<br>
+   return has_changed;<br>
+}<br>
+<br>
+static bool visit_load_const(bool *divergent, nir_load_const_instr *instr)<br>
+{<br>
+   divergent[instr->def.index] = false;<br>
+   return false;<br>
+}<br>
+<br>
+static bool visit_ssa_undef(bool *divergent, nir_ssa_undef_instr *instr)<br>
+{<br>
+   divergent[instr->def.index] = false;<br>
+   return false;<br>
+}<br>
+<br>
+static bool visit_deref(bool *divergent, nir_deref_instr *instr)<br>
+{<br>
+   nir_foreach_use(src, &instr->dest.ssa)<br>
+   {<br>
+      if (src->parent_instr->type != nir_instr_type_tex) {<br>
+         divergent[instr->dest.ssa.index] = false;<br>
+         return false;<br>
+      }<br>
+   }<br>
+   bool before = divergent[instr->dest.ssa.index];<br>
+   divergent[instr->dest.ssa.index] = true;<br>
+   return !before;<br>
+}<br>
+<br>
+bool* nir_divergence_analysis(nir_shader *shader)<br>
+{<br>
+<br>
+   nir_function_impl *impl = nir_shader_get_entrypoint(shader);<br>
+   bool *t = rzalloc_array(shader, bool, impl->ssa_alloc);<br>
+   nir_block_worklist worklist;<br>
+   nir_block_worklist_init(&worklist, impl->num_blocks, NULL);<br>
+   nir_block_worklist_add_all(&worklist, impl);<br>
+<br>
+   while (!nir_block_worklist_is_empty(&worklist)) {<br>
+      nir_block *block = nir_block_worklist_pop_head(&worklist);<br>
+      bool has_changed = false;<br>
+<br>
+      nir_foreach_instr(instr, block) {<br>
+         switch (instr->type) {<br>
+         case nir_instr_type_alu:<br>
+            has_changed |= visit_alu(t, nir_instr_as_alu(instr));<br>
+            break;<br>
+         case nir_instr_type_intrinsic:<br>
+            has_changed |= visit_intrinsic(t, nir_instr_as_intrinsic(instr));<br>
+            break;<br>
+         case nir_instr_type_tex:<br>
+            has_changed |= visit_tex(t, nir_instr_as_tex(instr));<br>
+            break;<br>
+         case nir_instr_type_phi:<br>
+            has_changed |= visit_phi(t, nir_instr_as_phi(instr));<br>
+            break;<br>
+         case nir_instr_type_parallel_copy:<br>
+            has_changed |= visit_parallel_copy(t, nir_instr_as_parallel_copy(instr));<br>
+            break;<br>
+         case nir_instr_type_load_const:<br>
+            has_changed |= visit_load_const(t, nir_instr_as_load_const(instr));<br>
+            break;<br>
+         case nir_instr_type_ssa_undef:<br>
+            has_changed |= visit_ssa_undef(t, nir_instr_as_ssa_undef(instr));<br>
+            break;<br>
+         case nir_instr_type_deref:<br>
+            has_changed |= visit_deref(t, nir_instr_as_deref(instr));<br>
+            break;<br>
+         case nir_instr_type_jump:<br>
+            break;<br>
+         case nir_instr_type_call:<br>
+            assert(false);<br>
+         default:<br>
+            unreachable("Invalid instruction type");<br>
+            break;<br>
+         }<br>
+      }<br>
+      if (has_changed) {<br>
+         // FIXME: this is quite inefficient!<br>
+         nir_block_worklist_add_all(&worklist, impl);<br>
+      }<br>
+   }<br>
+   return t;<br>
+}<br>
-- <br>
2.17.1<br>
<br>
_______________________________________________<br>
mesa-dev mailing list<br>
<a href="mailto:mesa-dev@lists.freedesktop.org" target="_blank">mesa-dev@lists.freedesktop.org</a><br>
<a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a></blockquote><div><br></div><div>Regards,</div><div>Andrii.<br></div></div></div></div></div></div></div></div>