On Sat, Jan 24, 2015 at 12:22 PM, Jason Ekstrand <ja...@jlekstrand.net> wrote:
>
> On Jan 24, 2015 8:18 AM, "Connor Abbott" <cwabbo...@gmail.com> wrote:
>>
>> On Sat, Jan 24, 2015 at 1:00 AM, Jason Ekstrand <ja...@jlekstrand.net>
>> wrote:
>> > ---
>> > src/glsl/Makefile.sources | 1 +
>> > src/glsl/nir/nir.h | 2 +
>> > src/glsl/nir/nir_lower_phis_to_scalar.c | 238
>> > ++++++++++++++++++++++++++++++++
>> > 3 files changed, 241 insertions(+)
>> > create mode 100644 src/glsl/nir/nir_lower_phis_to_scalar.c
>> >
>> > diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
>> > index 96c4ec5..02d0780 100644
>> > --- a/src/glsl/Makefile.sources
>> > +++ b/src/glsl/Makefile.sources
>> > @@ -28,6 +28,7 @@ NIR_FILES = \
>> > nir/nir_lower_global_vars_to_local.c \
>> > nir/nir_lower_locals_to_regs.c \
>> > nir/nir_lower_io.c \
>> > + nir/nir_lower_phis_to_scalar.c \
>> > nir/nir_lower_samplers.cpp \
>> > nir/nir_lower_system_values.c \
>> > nir/nir_lower_to_source_mods.c \
>> > diff --git a/src/glsl/nir/nir.h b/src/glsl/nir/nir.h
>> > index 119ca01..cda14aa 100644
>> > --- a/src/glsl/nir/nir.h
>> > +++ b/src/glsl/nir/nir.h
>> > @@ -1523,6 +1523,8 @@ void nir_remove_dead_variables(nir_shader
>> > *shader);
>> > void nir_lower_vec_to_movs(nir_shader *shader);
>> > void nir_lower_alu_to_scalar(nir_shader *shader);
>> >
>> > +void nir_lower_phis_to_scalar(nir_shader *shader);
>> > +
>> > void nir_lower_samplers(nir_shader *shader,
>> > struct gl_shader_program *shader_program,
>> > struct gl_program *prog);
>> > diff --git a/src/glsl/nir/nir_lower_phis_to_scalar.c
>> > b/src/glsl/nir/nir_lower_phis_to_scalar.c
>> > new file mode 100644
>> > index 0000000..9f901d6
>> > --- /dev/null
>> > +++ b/src/glsl/nir/nir_lower_phis_to_scalar.c
>> > @@ -0,0 +1,238 @@
>> > +/*
>> > + * Copyright © 2014 Intel Corporation
>> > + *
>> > + * Permission is hereby granted, free of charge, to any person
>> > obtaining a
>> > + * copy of this software and associated documentation files (the
>> > "Software"),
>> > + * to deal in the Software without restriction, including without
>> > limitation
>> > + * the rights to use, copy, modify, merge, publish, distribute,
>> > sublicense,
>> > + * and/or sell copies of the Software, and to permit persons to whom
>> > the
>> > + * Software is furnished to do so, subject to the following conditions:
>> > + *
>> > + * The above copyright notice and this permission notice (including the
>> > next
>> > + * paragraph) shall be included in all copies or substantial portions
>> > of the
>> > + * Software.
>> > + *
>> > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
>> > EXPRESS OR
>> > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
>> > MERCHANTABILITY,
>> > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
>> > SHALL
>> > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
>> > OTHER
>> > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
>> > ARISING
>> > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
>> > DEALINGS
>> > + * IN THE SOFTWARE.
>> > + *
>> > + * Authors:
>> > + * Jason Ekstrand (ja...@jlekstrand.net)
>> > + *
>> > + */
>> > +
>> > +#include "nir.h"
>> > +
>> > +/*
>> > + * Implements common subexpression elimination
>> > + */
>>
>> Whoops...
>
> Yeah, I'll fix that.
>
>>
>> > +
>> > +struct lower_phis_to_scalar_state {
>> > + void *mem_ctx;
>> > + void *dead_ctx;
>> > +
>> > + /* Hash table marking which phi nodes are scalarizable. The key is
>> > + * pointers to phi instructions and the entry is either NULL for not
>> > + * scalarizable or non-null for scalarizable.
>> > + */
>> > + struct hash_table *phi_table;
>> > +};
>> > +
>> > +/* Determines if the given phi node should be lowered. The only phi
>> > nodes
>> > + * we will scalarize at the moment are those where all of the sources
>> > are
>> > + * scalarizable.
>> > + */
>> > +static bool
>> > +should_lower_phi(nir_phi_instr *phi, struct lower_phis_to_scalar_state
>> > *state)
>> > +{
>> > + /* Already scalar */
>> > + if (phi->dest.ssa.num_components == 1)
>> > + return false;
>> > +
>> > + struct hash_entry *entry = _mesa_hash_table_search(state->phi_table,
>> > phi);
>> > + if (entry)
>> > + return entry->data != NULL;
>> > +
>> > + nir_foreach_phi_src(phi, src) {
>> > + /* Don't know what to do with non-ssa sources */
>> > + if (!src->src.is_ssa)
>> > + return false;
>> > +
>> > + nir_instr *src_instr = src->src.ssa->parent_instr;
>> > + switch (src_instr->type) {
>> > + case nir_instr_type_alu: {
>> > + nir_alu_instr *src_alu = nir_instr_as_alu(src_instr);
>> > +
>> > + /* ALU operations with output_size == 0 should be scalarized.
>> > We
>> > + * will also see a bunch of vecN operations from scalarizing
>> > ALU
>> > + * operations and, since they can easily be copy-propagated,
>> > they
>> > + * are ok too.
>> > + */
>> > + return nir_op_infos[src_alu->op].output_size == 0 ||
>> > + src_alu->op != nir_op_vec2 ||
>> > + src_alu->op != nir_op_vec3 ||
>> > + src_alu->op != nir_op_vec4;
>> > + }
>> > +
>> > + case nir_instr_type_phi: {
>> > + nir_phi_instr *src_phi = nir_instr_as_phi(src_instr);
>> > +
>> > + /* Insert an entry and mark it as scalarizable for now. That
>> > way
>> > + * we don't recurse forever and a cycle in the depencence
>> > graph
>> > + * won't automatically make us fail to scalarize.
>> > + */
>> > + entry = _mesa_hash_table_insert(state->phi_table, src_phi,
>> > (void *)1);
>> > + bool scalarizable = should_lower_phi(src_phi, state);
>> > + entry->data = (void *)scalarizable;
>> > +
>> > + return scalarizable;
>> > + }
>> > +
>> > + default:
>> > + /* We can't scalarize this type of instruction */
>> > + return false;
>> > + }
>> > + }
>> > +
>> > + return true;
>> > +}
>> > +
>> > +static bool
>> > +lower_phis_to_scalar_block(nir_block *block, void *void_state)
>> > +{
>> > + struct lower_phis_to_scalar_state *state = void_state;
>> > +
>> > + /* Find the last phi node in the block */
>> > + nir_phi_instr *last_phi = NULL;
>> > + nir_foreach_instr(block, instr) {
>> > + if (instr->type != nir_instr_type_phi)
>> > + break;
>> > +
>> > + last_phi = nir_instr_as_phi(instr);
>> > + }
>> > +
>> > + /* We have to handle the phi nodes in their own pass due to the way
>> > + * we're modifying the linked list of instructions.
>> > + */
>> > + nir_foreach_instr_safe(block, instr) {
>> > + if (instr->type != nir_instr_type_phi)
>> > + break;
>> > +
>> > + nir_phi_instr *phi = nir_instr_as_phi(instr);
>> > +
>> > + if (!should_lower_phi(phi, state))
>> > + continue;
>> > +
>> > + /* Create a vecN operation to combine the results. Most of these
>> > + * will be redundant, but copy propagation should clean them up
>> > for
>> > + * us. No need to add the complexity here.
>> > + */
>> > + nir_op vec_op;
>> > + switch (phi->dest.ssa.num_components) {
>> > + case 2: vec_op = nir_op_vec2; break;
>> > + case 3: vec_op = nir_op_vec3; break;
>> > + case 4: vec_op = nir_op_vec4; break;
>> > + default: unreachable("Invalid number of components");
>> > + }
>> > +
>> > + nir_alu_instr *vec = nir_alu_instr_create(state->mem_ctx,
>> > vec_op);
>> > + vec->dest.dest.is_ssa = true;
>> > + nir_ssa_def_init(&vec->instr, &vec->dest.dest.ssa,
>> > + phi->dest.ssa.num_components, NULL);
>> > + vec->dest.write_mask = (1 << phi->dest.ssa.num_components) - 1;
>> > +
>> > + for (unsigned i = 0; i < phi->dest.ssa.num_components; i++) {
>> > + nir_phi_instr *new_phi = nir_phi_instr_create(state->mem_ctx);
>> > + new_phi->dest.is_ssa = true;
>> > + nir_ssa_def_init(&new_phi->instr, &new_phi->dest.ssa, 1,
>> > NULL);
>> > +
>> > + vec->src[i].src.is_ssa = true;
>> > + vec->src[i].src.ssa = &new_phi->dest.ssa;
>> > +
>> > + nir_foreach_phi_src(phi, src) {
>> > + /* We need to insert a mov to grab the i'th component of
>> > src */
>> > + nir_alu_instr *mov = nir_alu_instr_create(state->mem_ctx,
>> > + nir_op_imov);
>> > + mov->dest.dest.is_ssa = true;
>> > + nir_ssa_def_init(&mov->instr, &mov->dest.dest.ssa, 1,
>> > NULL);
>> > + mov->dest.write_mask = 1;
>> > + mov->src[0].src = nir_src_copy(src->src, state->mem_ctx);
>> > + mov->src[0].swizzle[0] = i;
>> > +
>> > + /* Insert at the end of the predecessor but before the jump
>> > */
>> > + nir_instr *pred_last_instr =
>> > nir_block_last_instr(src->pred);
>> > + if (pred_last_instr && pred_last_instr->type ==
>> > nir_instr_type_jump)
>> > + nir_instr_insert_before(pred_last_instr, &mov->instr);
>> > + else
>> > + nir_instr_insert_after_block(src->pred, &mov->instr);
>> > +
>> > + nir_phi_src *new_src = ralloc(state->mem_ctx, nir_phi_src);
>> > + new_src->pred = src->pred;
>> > + new_src->src.is_ssa = true;
>> > + new_src->src.ssa = &mov->dest.dest.ssa;
>> > +
>> > + exec_list_push_tail(&new_phi->srcs, &new_src->node);
>> > + }
>> > +
>> > + nir_instr_insert_before(&phi->instr, &new_phi->instr);
>> > + }
>> > +
>> > + nir_instr_insert_after(&last_phi->instr, &vec->instr);
>> > +
>> > + nir_ssa_def_rewrite_uses(&phi->dest.ssa,
>> > + nir_src_for_ssa(&vec->dest.dest.ssa),
>> > + state->mem_ctx);
>> > +
>> > + ralloc_steal(state->dead_ctx, phi);
>> > + nir_instr_remove(&phi->instr);
>> > +
>> > + /* We're using the safe iterator and inserting all the newly
>> > + * scalarized phi nodes before their non-scalarized version so
>> > that's
>> > + * ok. However, we are also inserting vec operations after all
>> > of
>>
>> *all of the phi nodes (or "after the last phi node")
>>
>> > + * the last phi node so once we get here, we can't trust even the
>> > + * safe iterator to stop properly. We have to break manually.
>> > + */
>>
>> I think there's something I'm not getting here. If we're on the last
>> phi instruction, and we insert a vec instruction after it, isn't this
>> still ok because the safe iterator will just skip over the vec
>> instruction and go to the next instruction (or the end of the block)
>> and we'll just break out of the loop?
>
> Yeah, that probably works. This is kind of a remnant of an old bug that I'm
> not even 100% sure was caused by this. I'll see if we can get rid of it.
>
>>
>> > + if (instr == &last_phi->instr)
>> > + break;
>> > + }
>> > +
>> > + return true;
>> > +}
>> > +
>> > +static void
>> > +lower_phis_to_scalar_impl(nir_function_impl *impl)
>> > +{
>> > + struct lower_phis_to_scalar_state state;
>> > +
>> > + state.mem_ctx = ralloc_parent(impl);
>> > + state.dead_ctx = ralloc_context(NULL);
>> > + state.phi_table = _mesa_hash_table_create(state.dead_ctx,
>> > _mesa_hash_pointer,
>> > + _mesa_key_pointer_equal);
>> > +
>> > + nir_foreach_block(impl, lower_phis_to_scalar_block, &state);
>> > +
>> > + nir_metadata_preserve(impl, nir_metadata_block_index |
>> > + nir_metadata_dominance);
>> > +
>> > + ralloc_free(state.dead_ctx);
>> > +}
>> > +
>> > +/** A pass that lowers vector phi nodes to scalar
>> > + *
>> > + * This pass loops through the blocks and lowers looks for vector phi
>> > nodes
>> > + * it can lower to scalar phi nodes. Not all phi nodes are lowered.
>> > For
>> > + * instance, if one of the sources is a non-scalarizable vector, then
>> > we
>> > + * don't bother lowering because that would generate hard-to-coalesce
>> > movs.
>> > + */
>>
>> Just wondering... what's the advantage to not scalarizing all the phi
>> nodes? This is supposed to be used for scalar targets, so they
>> potentially might even want all the phi nodes to be scalar, so the
>> only non-scalar things are load and store instructions (we don't care
>> that much right now though). Woudn't splitting everything just save us
>> some of the work of splitting up mov instructions later on?
>
> That's a valid question and it has a (hopefully equally valid) answer. It
> comes down to coalescing. Since phi sources can't swizzle, swizzles on phis
> have to be resolved by inserting a mov right before the phi. If the source
> of the phi can't be vectorized, then that leaves us with an uncoalescable
> pile of moves just to pick off single components. If we leave the phi in
> vector form, it makes it the responsibility of the sources to put things
> back together into a vector.
>
> This also matters a lot for the backend register allocation and register
> coalescing. I think this will be a lot better if we combine things into
> vectors on the source side rather than the destination. In the case where
> the ssa def going into the phi is generated in the predecessor block, we can
> almost certainly coalesce the mov away. In this case, we have an
> instruction that writes to a temporary register and then a mov into a
> component of the vector. The intermediate register can very easily be
> coalesced into the vector. On the other hand, if we have to recombine on
> the destination side, the movs will be very hard to get rid of because the
> source will be the register corresponding to the phi-web and will be
> assigned in several different basic blocks. Therefore, if we have to
> reassemble into a vector on one side or the other, source-side is better.
>
> But what if we don't care that it's a vector? That's a valid question. My
> first heuristic was to scalarize a phi node if and only if everything
> consuming that value was scalarizable. However, without swizzles on phi
> sources, this leads to the component picking problem I mentioned above. If
> we added swizzles to phis, this other heuristic is probably better. (Side
> note: The thought has also ocurred to me to just let phis have ALU src and
> dest. We are lowering them to ALU mov's after all.)
>
> Hope that helps,
> --Jason Ekstrand
Ok, I think that makes sense. Maybe it would be good to go into a
little more detail in the comment here about how scalarizing phi nodes
with sources that can't be vectorized creates these moves that can't
be coalesced away easily.
>
>> > +void
>> > +nir_lower_phis_to_scalar(nir_shader *shader)
>> > +{
>> > + nir_foreach_overload(shader, overload) {
>> > + if (overload->impl)
>> > + lower_phis_to_scalar_impl(overload->impl);
>> > + }
>> > +}
>> > --
>> > 2.2.1
>> >
>> > _______________________________________________
>> > mesa-dev mailing list
>> > mesa-dev@lists.freedesktop.org
>> > http://lists.freedesktop.org/mailman/listinfo/mesa-dev
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
