/*
* 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"),
/* 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));
}
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));
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));
/* 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);
}
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.
}
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;
}
{
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);
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:
}
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);
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 {
+ nir_metadata_preserve(function->impl, nir_metadata_all);
+ }
+ }
ralloc_free(state);
+ return progress;
}
+
projects / mesa.git / blobdiff