X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fcompiler%2Fnir%2Fnir_to_lcssa.c;h=e5b760c706f6f010c69221ce72796c19849fb83f;hb=60097cc840e33af8506d7d4d621fefdca1a77695;hp=0f62fc39400dac596a1f3209bd38119bede7f909;hpb=976046a8d8f9bed8f805d09ac5aebe63b81a71d9;p=mesa.git

diff --git a/src/compiler/nir/nir_to_lcssa.c b/src/compiler/nir/nir_to_lcssa.c
index 0f62fc39400..e5b760c706f 100644
--- a/src/compiler/nir/nir_to_lcssa.c
+++ b/src/compiler/nir/nir_to_lcssa.c
@@ -1,5 +1,6 @@
 /*
  * Copyright © 2015 Thomas Helland
+ * Copyright © 2019 Valve Corporation
  *
  * Permission is hereby granted, free of charge, to any person obtaining a
  * copy of this software and associated documentation files (the "Software"),
@@ -45,10 +46,15 @@ typedef struct {
    /* The loop we store information for */
    nir_loop *loop;
 
+   /* Whether to skip loop invariant variables */
+   bool skip_invariants;
+   bool skip_bool_invariants;
+
+   bool progress;
 } lcssa_state;
 
 static bool
-is_if_use_inside_loop(nir_src *use, nir_loop* loop)
+is_if_use_inside_loop(nir_src *use, nir_loop *loop)
 {
    nir_block *block_before_loop =
       nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
@@ -66,7 +72,7 @@ is_if_use_inside_loop(nir_src *use, nir_loop* loop)
 }
 
 static bool
-is_use_inside_loop(nir_src *use, nir_loop* loop)
+is_use_inside_loop(nir_src *use, nir_loop *loop)
 {
    nir_block *block_before_loop =
       nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
@@ -81,12 +87,120 @@ is_use_inside_loop(nir_src *use, nir_loop* loop)
    return true;
 }
 
+static bool
+is_defined_before_loop(nir_ssa_def *def, nir_loop *loop)
+{
+   nir_instr *instr = def->parent_instr;
+   nir_block *block_before_loop =
+      nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
+
+   return instr->block->index <= block_before_loop->index;
+}
+
+typedef enum instr_invariance {
+   undefined = 0,
+   invariant,
+   not_invariant,
+} instr_invariance;
+
+static instr_invariance
+instr_is_invariant(nir_instr *instr, nir_loop *loop);
+
+static bool
+def_is_invariant(nir_ssa_def *def, nir_loop *loop)
+{
+   if (is_defined_before_loop(def, loop))
+      return invariant;
+
+   if (def->parent_instr->pass_flags == undefined)
+      def->parent_instr->pass_flags = instr_is_invariant(def->parent_instr, loop);
+
+   return def->parent_instr->pass_flags == invariant;
+}
+
+static bool
+src_is_invariant(nir_src *src, void *state)
+{
+   assert(src->is_ssa);
+   return def_is_invariant(src->ssa, (nir_loop *)state);
+}
+
+static instr_invariance
+phi_is_invariant(nir_phi_instr *instr, nir_loop *loop)
+{
+   /* Base case: it's a phi at the loop header
+    * Loop-header phis are updated in each loop iteration with
+    * the loop-carried value, and thus control-flow dependent
+    * on the loop itself.
+    */
+   if (instr->instr.block == nir_loop_first_block(loop))
+      return not_invariant;
+
+   nir_foreach_phi_src(src, instr) {
+      if (!src_is_invariant(&src->src, loop))
+         return not_invariant;
+   }
+
+   /* All loop header- and LCSSA-phis should be handled by this point. */
+   nir_cf_node *prev = nir_cf_node_prev(&instr->instr.block->cf_node);
+   assert(prev && prev->type == nir_cf_node_if);
+
+   /* Invariance of phis after if-nodes also depends on the invariance
+    * of the branch condition.
+    */
+   nir_if *if_node = nir_cf_node_as_if(prev);
+   if (!def_is_invariant(if_node->condition.ssa, loop))
+      return not_invariant;
+
+   return invariant;
+}
+
+
+/* An instruction is said to be loop-invariant if it
+ * - has no sideeffects and
+ * - solely depends on variables defined outside of the loop or
+ *   by other invariant instructions
+ */
+static instr_invariance
+instr_is_invariant(nir_instr *instr, nir_loop *loop)
+{
+   assert(instr->pass_flags == undefined);
+
+   switch (instr->type) {
+   case nir_instr_type_load_const:
+   case nir_instr_type_ssa_undef:
+      return invariant;
+   case nir_instr_type_call:
+      return not_invariant;
+   case nir_instr_type_phi:
+      return phi_is_invariant(nir_instr_as_phi(instr), loop);
+   case nir_instr_type_intrinsic: {
+      nir_intrinsic_instr *intrinsic = nir_instr_as_intrinsic(instr);
+      if (!(nir_intrinsic_infos[intrinsic->intrinsic].flags & NIR_INTRINSIC_CAN_REORDER))
+         return not_invariant;
+      /* fallthrough */
+   }
+   default:
+      return nir_foreach_src(instr, src_is_invariant, loop) ? invariant : not_invariant;
+   }
+
+   return invariant;
+}
+
 static bool
 convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state)
 {
    lcssa_state *state = void_state;
    bool all_uses_inside_loop = true;
 
+   /* Don't create LCSSA-Phis for loop-invariant variables */
+   if (state->skip_invariants &&
+       (def->bit_size != 1 || state->skip_bool_invariants)) {
+      assert(def->parent_instr->pass_flags != undefined);
+      if (def->parent_instr->pass_flags == invariant)
+         return true;
+   }
+
    nir_block *block_after_loop =
       nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node));
 
@@ -111,9 +225,6 @@ convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state)
    if (all_uses_inside_loop)
       return true;
 
-   /* We don't want derefs ending up in phi sources */
-   assert(def->parent_instr->type != nir_instr_type_deref);
-
    /* Initialize a phi-instruction */
    nir_phi_instr *phi = nir_phi_instr_create(state->shader);
    nir_ssa_dest_init(&phi->instr, &phi->dest,
@@ -122,7 +233,6 @@ convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state)
    /* Create a phi node with as many sources pointing to the same ssa_def as
     * the block has predecessors.
     */
-   struct set_entry *entry;
    set_foreach(block_after_loop->predecessors, entry) {
       nir_phi_src *phi_src = ralloc(phi, nir_phi_src);
       phi_src->src = nir_src_for_ssa(def);
@@ -132,6 +242,25 @@ convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state)
    }
 
    nir_instr_insert_before_block(block_after_loop, &phi->instr);
+   nir_ssa_def *dest = &phi->dest.ssa;
+
+   /* deref instructions need a cast after the phi */
+   if (def->parent_instr->type == nir_instr_type_deref) {
+      nir_deref_instr *cast =
+         nir_deref_instr_create(state->shader, nir_deref_type_cast);
+
+      nir_deref_instr *instr = nir_instr_as_deref(def->parent_instr);
+      cast->mode = instr->mode;
+      cast->type = instr->type;
+      cast->parent = nir_src_for_ssa(&phi->dest.ssa);
+      cast->cast.ptr_stride = nir_deref_instr_ptr_as_array_stride(instr);
+
+      nir_ssa_dest_init(&cast->instr, &cast->dest,
+                        phi->dest.ssa.num_components,
+                        phi->dest.ssa.bit_size, NULL);
+      nir_instr_insert(nir_after_phis(block_after_loop), &cast->instr);
+      dest = &cast->dest.ssa;
+   }
 
    /* Run through all uses and rewrite those outside the loop to point to
     * the phi instead of pointing to the ssa-def.
@@ -143,18 +272,17 @@ convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state)
       }
 
       if (!is_use_inside_loop(use, state->loop)) {
-         nir_instr_rewrite_src(use->parent_instr, use,
-                               nir_src_for_ssa(&phi->dest.ssa));
+         nir_instr_rewrite_src(use->parent_instr, use, nir_src_for_ssa(dest));
       }
    }
 
    nir_foreach_if_use_safe(use, def) {
       if (!is_if_use_inside_loop(use, state->loop)) {
-         nir_if_rewrite_condition(use->parent_if,
-                                  nir_src_for_ssa(&phi->dest.ssa));
+         nir_if_rewrite_condition(use->parent_if, nir_src_for_ssa(dest));
       }
    }
 
+   state->progress = true;
    return true;
 }
 
@@ -163,8 +291,6 @@ convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state)
 {
    switch (cf_node->type) {
    case nir_cf_node_block:
-      nir_foreach_instr(instr, nir_cf_node_as_block(cf_node))
-         nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state);
       return;
    case nir_cf_node_if: {
       nir_if *if_stmt = nir_cf_node_as_if(cf_node);
@@ -175,13 +301,50 @@ convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state)
       return;
    }
    case nir_cf_node_loop: {
-      nir_loop *parent_loop = state->loop;
-      state->loop = nir_cf_node_as_loop(cf_node);
+      if (state->skip_invariants) {
+         nir_foreach_block_in_cf_node(block, cf_node) {
+            nir_foreach_instr(instr, block)
+               instr->pass_flags = undefined;
+         }
+      }
 
-      foreach_list_typed(nir_cf_node, nested_node, node, &state->loop->body)
+      /* first, convert inner loops */
+      nir_loop *loop = nir_cf_node_as_loop(cf_node);
+      foreach_list_typed(nir_cf_node, nested_node, node, &loop->body)
          convert_to_lcssa(nested_node, state);
 
-      state->loop = parent_loop;
+      /* mark loop-invariant instructions */
+      if (state->skip_invariants) {
+         nir_foreach_block_in_cf_node(block, cf_node) {
+            nir_foreach_instr(instr, block) {
+               if (instr->pass_flags == undefined)
+                  instr->pass_flags = instr_is_invariant(instr, nir_cf_node_as_loop(cf_node));
+            }
+         }
+      }
+
+      state->loop = loop;
+      nir_foreach_block_in_cf_node(block, cf_node) {
+         nir_foreach_instr(instr, block) {
+            nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state);
+
+            /* for outer loops, invariant instructions can be variant */
+            if (state->skip_invariants && instr->pass_flags == invariant)
+               instr->pass_flags = undefined;
+         }
+      }
+
+      /* For outer loops, the LCSSA-phi should be considered not invariant */
+      if (state->skip_invariants) {
+         nir_block *block_after_loop =
+            nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node));
+         nir_foreach_instr(instr, block_after_loop) {
+            if (instr->type == nir_instr_type_phi)
+               instr->pass_flags = not_invariant;
+            else
+               break;
+         }
+      }
       return;
    }
    default:
@@ -190,7 +353,8 @@ convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state)
 }
 
 void
-nir_convert_loop_to_lcssa(nir_loop *loop) {
+nir_convert_loop_to_lcssa(nir_loop *loop)
+{
    nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node);
 
    nir_metadata_require(impl, nir_metadata_block_index);
@@ -198,9 +362,48 @@ nir_convert_loop_to_lcssa(nir_loop *loop) {
    lcssa_state *state = rzalloc(NULL, lcssa_state);
    state->loop = loop;
    state->shader = impl->function->shader;
+   state->skip_invariants = false;
+   state->skip_bool_invariants = false;
 
-   foreach_list_typed(nir_cf_node, node, node, &state->loop->body)
-      convert_to_lcssa(node, state);
+   nir_foreach_block_in_cf_node (block, &loop->cf_node) {
+      nir_foreach_instr(instr, block)
+         nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state);
+   }
 
    ralloc_free(state);
 }
+
+bool
+nir_convert_to_lcssa(nir_shader *shader, bool skip_invariants, bool skip_bool_invariants)
+{
+   bool progress = false;
+   lcssa_state *state = rzalloc(NULL, lcssa_state);
+   state->shader = shader;
+   state->skip_invariants = skip_invariants;
+   state->skip_bool_invariants = skip_bool_invariants;
+
+   nir_foreach_function(function, shader) {
+      if (function->impl == NULL)
+         continue;
+
+      state->progress = false;
+      nir_metadata_require(function->impl, nir_metadata_block_index);
+
+      foreach_list_typed(nir_cf_node, node, node, &function->impl->body)
+         convert_to_lcssa(node, state);
+
+      if (state->progress) {
+         progress = true;
+         nir_metadata_preserve(function->impl, nir_metadata_block_index |
+                                               nir_metadata_dominance);
+      } else {
+#ifndef NDEBUG
+         function->impl->valid_metadata &= ~nir_metadata_not_properly_reset;
+#endif
+      }
+   }
+
+   ralloc_free(state);
+   return progress;
+}
+