<div dir="ltr"> <div class="gmail_extra"> <div class="gmail_quote">On Sun, Jan 11, 2015 at 7:08 PM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com" target="_blank">cwabbott0@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div class="h5">On Tue, Jan 6, 2015 at 5:21 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> wrote: > > > On Mon, Jan 5, 2015 at 10:00 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> > wrote: >> >> >> >> On Mon, Jan 5, 2015 at 9:12 PM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> wrote: >>> >>> Hi, >>> >>> Was it your intention to not support non-per-component things like dot >>> product at all? I've made a few inline comments about how to do it, >>> and it doesn't seem like it's that hard. >> >> >> No, It was just never tested on them. All your comments seem valid >> enough. I'll try and incorperate them. >> >>> >>> >>> On Tue, Dec 16, 2014 at 1:12 AM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> >>> wrote: >>> > >>> > This framework provides a simple way to do simple search-and-replace >>> > operations on NIR code. The nir_search.h header provides four simple >>> > data >>> > structures for representing expressions: nir_value and four subtypes: >>> > nir_variable, nir_constant, and nir_expression. An expression tree can >>> >>> Make these be the actual names (nir_search_value, nir_search_variable, >>> etc.) >> >> >> Yeah, no problem. >> >>> >>> >>> > then be represented by nesting these data structures as needed. The >>> > nir_replace_instr function takes an instruction, an expression, and a >>> > value; if the instruction matches the expression, it is replaced with a >>> > new >>> > chain of instructions to generate the given replacement value. The >>> > framework keeps track of swizzles on sources and automatically >>> > generates >>> > the currect swizzles for the replacement value. >>> > --- >>> > src/glsl/Makefile.sources | 2 + >>> > src/glsl/nir/nir_search.c | 337 >>> > ++++++++++++++++++++++++++++++++++++++++++++++ >>> > src/glsl/nir/nir_search.h | 80 +++++++++++ >>> > 3 files changed, 419 insertions(+) >>> > create mode 100644 src/glsl/nir/nir_search.c >>> > create mode 100644 src/glsl/nir/nir_search.h >>> > >>> > diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources >>> > index 12c1d83..201330d 100644 >>> > --- a/src/glsl/Makefile.sources >>> > +++ b/src/glsl/Makefile.sources >>> > @@ -41,6 +41,8 @@ NIR_FILES = \ >>> > $(GLSL_SRCDIR)/nir/nir_opt_peephole_select.c \ >>> > $(GLSL_SRCDIR)/nir/nir_print.c \ >>> > $(GLSL_SRCDIR)/nir/nir_remove_dead_variables.c \ >>> > + $(GLSL_SRCDIR)/nir/nir_search.c \ >>> > + $(GLSL_SRCDIR)/nir/nir_search.h \ >>> > $(GLSL_SRCDIR)/nir/nir_split_var_copies.c \ >>> > $(GLSL_SRCDIR)/nir/nir_to_ssa.c \ >>> > $(GLSL_SRCDIR)/nir/nir_validate.c \ >>> > diff --git a/src/glsl/nir/nir_search.c b/src/glsl/nir/nir_search.c >>> > new file mode 100644 >>> > index 0000000..257a53b >>> > --- /dev/null >>> > +++ b/src/glsl/nir/nir_search.c >>> > @@ -0,0 +1,337 @@ >>> > +/* >>> > + * 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_search.h" >>> > + >>> > +struct match_state { >>> > + unsigned variables_seen; >>> > + nir_alu_src variables[NIR_SEARCH_MAX_VARIABLES]; >>> > +}; >>> > + >>> > +static bool >>> > +is_commutative_binop(nir_op op) >>> > +{ >>> > + switch (op) { >>> > + case nir_op_fadd: >>> > + case nir_op_iadd: >>> > + case nir_op_fmul: >>> > + case nir_op_imul: >>> > + case nir_op_imul_high: >>> > + case nir_op_umul_high: >>> > + case nir_op_feq: >>> > + case nir_op_fne: >>> > + case nir_op_ieq: >>> > + case nir_op_ine: >>> > + case nir_op_fand: >>> > + case nir_op_for: >>> > + case nir_op_fxor: >>> > + case nir_op_iand: >>> > + case nir_op_ior: >>> > + case nir_op_ixor: >>> > + case nir_op_fmin: >>> > + case nir_op_fmax: >>> > + case nir_op_imin: >>> > + case nir_op_imax: >>> > + case nir_op_umin: >>> > + case nir_op_umax: >>> > + return true; >>> > + default: >>> > + return false; >>> > + } >>> > +} >>> > + >>> > +static bool >>> > +match_expression(const nir_search_expression *expr, nir_alu_instr >>> > *instr, >>> > + unsigned num_components, const uint8_t *swizzle, >>> > + struct match_state *state); >>> > + >>> > +static bool >>> > +match_value(const nir_search_value *value, nir_alu_instr *instr, >>> > unsigned src, >>> > + unsigned num_components, const uint8_t *swizzle, >>> > + struct match_state *state) >>> > +{ >>> > + uint8_t new_swizzle[4]; >>> > + >>> > + for (int i = 0; i < num_components; ++i) >>> > + new_swizzle[i] = instr->src[src].swizzle[swizzle[i]]; >>> > + >>> > + switch (value->type) { >>> > + case nir_search_value_expression: >>> > + if (!instr->src[src].src.is_ssa) >>> > + return false; >>> > + >>> > + if (instr->src[src].src.ssa->parent_instr->type != >>> > nir_instr_type_alu) >>> > + return false; >>> > + >>> > + return match_expression(nir_search_value_as_expression(value), >>> > + >>> > nir_instr_as_alu(instr->src[src].src.ssa->parent_instr), >>> > + num_components, new_swizzle, state); >>> > + >>> > + case nir_search_value_variable: { >>> > + nir_search_variable *var = nir_search_value_as_variable(value); >>> > + >>> > + if (state->variables_seen & (1 << var->variable)) { >>> > + if (!nir_srcs_equal(state->variables[0].src, >>> > instr->src[src].src)) >>> >>> I think you meant state->variables[var->variable].src here. >> >> >> Yes, I think you're right. Kind of curious that this worked... >> >>> >>> >>> > >>> > + return false; >>> > >>> > + >>> > + assert(!instr->src[src].abs && !instr->src[src].negate); >>> > + >>> > + for (int i = 0; i < num_components; ++i) { >>> > + if (state->variables[var->variable].swizzle[i] != >>> > new_swizzle[i]) >>> > + return false; >>> > + } >>> > + >>> > + return true; >>> > + } else { >>> > + state->variables_seen |= (1 << var->variable); >>> > + state->variables[var->variable].src = instr->src[src].src; >>> > + state->variables[var->variable].abs = false; >>> > + state->variables[var->variable].negate = false; >>> > + >>> > + for (int i = 0; i < 4; ++i) { >>> > + if (i < num_components) >>> > + state->variables[var->variable].swizzle[i] = >>> > new_swizzle[i]; >>> > + else >>> > + state->variables[var->variable].swizzle[i] = 0; >>> > + } >>> > + >>> > + return true; >>> > + } >>> > + } >>> > + >>> > + case nir_search_value_constant: { >>> > + nir_search_constant *const_val = >>> > nir_search_value_as_constant(value); >>> > + >>> > + if (!instr->src[src].src.is_ssa) >>> > + return false; >>> > + >>> > + if (instr->src[src].src.ssa->parent_instr->type != >>> > nir_instr_type_load_const) >>> > + return false; >>> > + >>> > + nir_load_const_instr *load = >>> > + >>> > nir_instr_as_load_const(instr->src[src].src.ssa->parent_instr); >>> > + >>> > + switch (nir_op_infos[instr->op].input_types[src]) { >>> > + case nir_type_float: >>> > + for (unsigned i = 0; i < num_components; ++i) { >>> > + if (load->value.f[new_swizzle[i]] != const_val->data.f) >>> > + return false; >>> > + } >>> > + return true; >>> > + case nir_type_int: >>> > + case nir_type_unsigned: >>> > + case nir_type_bool: >>> > + for (unsigned i = 0; i < num_components; ++i) { >>> > + if (load->value.i[new_swizzle[i]] != const_val->data.i) >>> > + return false; >>> > + } >>> > + return true; >>> > + default: >>> > + unreachable("Invalid alu source type"); >>> > + } >>> > + } >>> > + >>> > + default: >>> > + unreachable("Invalid search value type"); >>> > + } >>> > +} >>> > + >>> > +static bool >>> > +match_expression(const nir_search_expression *expr, nir_alu_instr >>> > *instr, >>> > + unsigned num_components, const uint8_t *swizzle, >>> > + struct match_state *state) >>> > +{ >>> > + if (instr->op != expr->opcode) >>> > + return false; >>> > + >>> > + assert(!instr->dest.saturate); >>> > + assert(nir_op_infos[instr->op].num_inputs > 0); >>> >>> >>> If the instruction has a sized destination, we ought to bail out if >>> the swizzle isn't the identity or num_components isn't equal to the >>> identity for those components. Alternately, we could assert that the >>> only instructions with non-per-component destinations are at the root, >>> since it doesn't seem like there are that many optimizations with a >>> non-per-component instruction like "dot" or "any" that's not at the >>> root of the tree. >> >> >> Good point. > > > Yes, we do need to bail on a non-trivial swizzle. However, I think not > using all the components is probably fine. The validator will ensure that > it doesn't use more components and not using all of them shouldn't be a > problem. </div></div>On second thought, I think you're right. We only need to bail on a non-trivial swizzle. </blockquote><div> </div><div>FYI: I did make all those changes. They're sigging in my repo: <a href="http://cgit.freedesktop.org/~jekstrand/mesa/tree/src/glsl/nir/nir_search.c?h=review/nir-v1">http://cgit.freedesktop.org/~jekstrand/mesa/tree/src/glsl/nir/nir_search.c?h=review/nir-v1</a> </div><div>If you want me to resend, I can. Or you can review it there </div><div>--Jason </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"> > >> >> >>> <div class=""><div class="h5">>>> > + >>> > + bool matched = true; >>> > + for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) { >>> > + if (!match_value(expr->srcs[i], instr, i, num_components, >>> > + swizzle, state)) { >>> >>> >>> I think we need to pass in the correct number of components if the >>> source isn't per-component, since if we don't any optimizations >>> involving dot products will be totally broken. Similarly, I think we >>> need to reset the swizzle to the identity here for non-per-component >>> inputs. >> >> >> Right >> >>> >>> >>> > >>> > + matched = false; >>> > + break; >>> > + } >>> > + } >>> > + >>> > + if (matched) >>> > + return true; >>> > + >>> > + if (is_commutative_binop(instr->op)) { >>> > + if (!match_value(expr->srcs[0], instr, 1, num_components, >>> > + swizzle, state)) >>> > + return false; >>> > + >>> > + return match_value(expr->srcs[1], instr, 0, num_components, >>> > + swizzle, state); >>> > + } else { >>> > + return false; >>> > + } >>> > +} >>> > + >>> > +static nir_alu_src >>> > +construct_value(const nir_search_value *value, nir_alu_type type, >>> > + unsigned num_components, struct match_state *state, >>> > + nir_instr *instr, void *mem_ctx) >>> > +{ >>> > + switch (value->type) { >>> > + case nir_search_value_expression: { >>> > + const nir_search_expression *expr = >>> > nir_search_value_as_expression(value); >>> > + >>> > + nir_alu_instr *alu = nir_alu_instr_create(mem_ctx, >>> > expr->opcode); >>> > + alu->dest.dest.is_ssa = true; >>> > + nir_ssa_def_init(&alu->instr, &alu->dest.dest.ssa, >>> > num_components, NULL); >>> > + alu->dest.write_mask = (1 << num_components) - 1; >>> > + alu->dest.saturate = false; >>> > + >>> > + for (unsigned i = 0; i < nir_op_infos[expr->opcode].num_inputs; >>> > i++) { >>> > + alu->src[i] = construct_value(expr->srcs[i], >>> > + >>> > nir_op_infos[alu->op].input_types[i], >>> > + num_components, >>> > + state, instr, mem_ctx); >>> >>> Similarly to my earlier comment, we need to set num_components >>> correctly here if the source is not per-component. >> >> >> Yup >> >>> >>> >>> > + } >>> > + >>> > + nir_instr_insert_before(instr, &alu->instr); >>> > + >>> > + nir_alu_src val = { >>> > + .src.is_ssa = true, >>> > + .src.ssa = &alu->dest.dest.ssa, >>> > + .negate = false, >>> > + .abs = false, >>> > + .swizzle = { 0, 0, 0, 0 } >>> > + }; >>> > + >>> > + /* No swizzling, but we can't have a swizzle value higher than >>> > + * num_components or the validator will get cranky. >>> > + */ >>> > + for (unsigned i = 0; i < num_components; ++i) >>> > + val.swizzle[i] = i; >>> >>> >>> The validator only checks swizzle values that are actually being used, >>> so we can just do >>> >>> .swizzle = {0, 1, 2, 3} >>> >>> here and it should be fine. >> >> >> Yeah, that should be ok. >> >>> >>> >>> > >>> > + >>> > + return val; >>> > + } >>> > + >>> > + case nir_search_value_variable: { >>> > + const nir_search_variable *var = >>> > nir_search_value_as_variable(value); >>> > + assert(state->variables_seen & (1 << var->variable)); >>> > + >>> > + nir_alu_src val = state->variables[var->variable]; >>> > + val.src = nir_src_copy(val.src, mem_ctx); >>> > + >>> > + return val; >>> > + } >>> > + >>> > + case nir_search_value_constant: { >>> > + const nir_search_constant *c = >>> > nir_search_value_as_constant(value); >>> > + nir_load_const_instr *load = >>> > nir_load_const_instr_create(mem_ctx); >>> > + load->dest.is_ssa = true; >>> > + nir_ssa_def_init(&load->instr, &load->dest.ssa, 1, NULL); >>> > + >>> > + switch (type) { >>> > + case nir_type_float: >>> > + load-><a href="http://dest.ssa.name" target="_blank">dest.ssa.name</a> = ralloc_asprintf(mem_ctx, "%f", >>> > c->data.f); >>> > + load->value.f[0] = c->data.f; >>> > + break; >>> > + case nir_type_int: >>> > + load-><a href="http://dest.ssa.name" target="_blank">dest.ssa.name</a> = ralloc_asprintf(mem_ctx, "%d", >>> > c->data.i); >>> > + load->value.i[0] = c->data.i; >>> > + break; >>> > + case nir_type_unsigned: >>> > + case nir_type_bool: >>> > + load->value.u[0] = c->data.u; >>> > + break; >>> > + default: >>> > + unreachable("Invalid alu source type"); >>> > + } >>> > + >>> > + nir_instr_insert_before(instr, &load->instr); >>> > + >>> > + nir_alu_src val = { >>> > + .src.is_ssa = true, >>> > + .src.ssa = &load->dest.ssa, >>> > + .negate = false, >>> > + .abs = false, >>> > + .swizzle = { 0, 0, 0, 0 } /* Splatted scalar */ >>> > + }; >>> > + >>> > + return val; >>> > + } >>> > + >>> > + default: >>> > + unreachable("Invalid search value type"); >>> > + } >>> > +} >>> > + >>> > +nir_alu_instr * >>> > +nir_replace_instr(nir_alu_instr *instr, const nir_search_expression >>> > *search, >>> > + const nir_search_value *replace, void *mem_ctx) >>> > +{ >>> > + uint8_t swizzle[4] = { 0, 0, 0, 0 }; >>> > + >>> > + for (unsigned i = 0; i < instr->dest.dest.ssa.num_components; ++i) >>> > + swizzle[i] = i; >>> > + >>> > + assert(instr->dest.dest.is_ssa); >>> > + >>> > + struct match_state state; >>> > + state.variables_seen = 0; >>> > + >>> > + if (!match_expression(search, instr, >>> > instr->dest.dest.ssa.num_components, >>> > + swizzle, &state)) >>> > + return NULL; >>> > + >>> > + /* Inserting a mov may be unnecessary. However, it's much easier >>> > to >>> > + * simply let copy propagation clean this up than to try to go >>> > through >>> > + * and rewrite swizzles ourselves. >>> > + */ >>> > + nir_alu_instr *mov = nir_alu_instr_create(mem_ctx, nir_op_imov); >>> > + mov->dest.write_mask = instr->dest.write_mask; >>> > + mov->dest.dest.is_ssa = true; >>> > + nir_ssa_def_init(&mov->instr, &mov->dest.dest.ssa, >>> > + instr->dest.dest.ssa.num_components, NULL); >>> > + >>> > + mov->src[0] = construct_value(replace, >>> > nir_op_infos[instr->op].output_type, >>> > + instr->dest.dest.ssa.num_components, >>> > &state, >>> > + &instr->instr, mem_ctx); >>> > + nir_instr_insert_before(&instr->instr, &mov->instr); >>> > + >>> > + nir_src replace_src = { >>> > + .is_ssa = true, >>> > + .ssa = &mov->dest.dest.ssa, >>> > + }; >>> > + >>> > + nir_ssa_def_rewrite_uses(&instr->dest.dest.ssa, replace_src, >>> > mem_ctx); >>> > + >>> > + /* We know this one has no more uses because we just rewrote them >>> > all, >>> > + * so we can remove it. The rest of the matched expression, >>> > however, we >>> > + * don't know so much about. We'll just let dead code clean them >>> > up. >>> > + */ >>> > + nir_instr_remove(&instr->instr); >>> > + >>> > + return mov; >>> > +} >>> > diff --git a/src/glsl/nir/nir_search.h b/src/glsl/nir/nir_search.h >>> > new file mode 100644 >>> > index 0000000..8ec58b0 >>> > --- /dev/null >>> > +++ b/src/glsl/nir/nir_search.h >>> > @@ -0,0 +1,80 @@ >>> > +/* >>> > + * 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>) >>> > + * >>> > + */ >>> > + >>> > +#ifndef _NIR_SEARCH_ >>> > +#define _NIR_SEARCH_ >>> > + >>> > +#include "nir.h" >>> > + >>> > +#define NIR_SEARCH_MAX_VARIABLES 16 >>> > + >>> > +typedef enum { >>> > + nir_search_value_expression, >>> > + nir_search_value_variable, >>> > + nir_search_value_constant, >>> > +} nir_search_value_type; >>> > + >>> > +typedef struct { >>> > + nir_search_value_type type; >>> > +} nir_search_value; >>> > + >>> > +typedef struct { >>> > + nir_search_value value; >>> > + >>> > + /** The variable index; Must be less than NIR_SEARCH_MAX_VARIABLES >>> > */ >>> > + unsigned variable; >>> > +} nir_search_variable; >>> > + >>> > +typedef struct { >>> > + nir_search_value value; >>> > + >>> > + union { >>> > + uint32_t u; >>> > + int32_t i; >>> > + float f; >>> > + } data; >>> > +} nir_search_constant; >>> > + >>> > +typedef struct { >>> > + nir_search_value value; >>> > + >>> > + nir_op opcode; >>> > + const nir_search_value *srcs[4]; >>> > +} nir_search_expression; >>> > + >>> > +NIR_DEFINE_CAST(nir_search_value_as_variable, nir_search_value, >>> > + nir_search_variable, value) >>> > +NIR_DEFINE_CAST(nir_search_value_as_constant, nir_search_value, >>> > + nir_search_constant, value) >>> > +NIR_DEFINE_CAST(nir_search_value_as_expression, nir_search_value, >>> > + nir_search_expression, value) >>> > + >>> > +nir_alu_instr * >>> > +nir_replace_instr(nir_alu_instr *instr, const nir_search_expression >>> > *search, >>> > + const nir_search_value *replace, void *mem_ctx); >>> > + >>> > +#endif /* _NIR_SEARCH_ */ >>> > -- >>> > 2.2.0 >>> > >>> > _______________________________________________ >>> > 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" target="_blank">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> >> >> > </div></div></blockquote></div> </div></div>