On Jan 24, 2015 8:18 AM, "Connor Abbott" <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> wrote: > > On Sat, Jan 24, 2015 at 1:00 AM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> 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 (<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>) > > + * > > + */ > > + > > +#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 > > +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 > > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> > > <a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a>