[Mesa-dev] [PATCH 110/133] nir: Add an expression matching framework
Connor Abbott
cwabbott0 at gmail.com
Sun Jan 11 19:08:41 PST 2015
On Tue, Jan 6, 2015 at 5:21 PM, Jason Ekstrand <jason at jlekstrand.net> wrote:
>
>
> On Mon, Jan 5, 2015 at 10:00 PM, Jason Ekstrand <jason at jlekstrand.net>
> wrote:
>>
>>
>>
>> On Mon, Jan 5, 2015 at 9:12 PM, Connor Abbott <cwabbott0 at gmail.com> 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 <jason at jlekstrand.net>
>>> 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 (jason at jlekstrand.net)
>>> > + *
>>> > + */
>>> > +
>>> > +#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.
On second thought, I think you're right. We only need to bail on a
non-trivial swizzle.
>
>>
>>
>>>
>>> > +
>>> > + 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->dest.ssa.name = ralloc_asprintf(mem_ctx, "%f",
>>> > c->data.f);
>>> > + load->value.f[0] = c->data.f;
>>> > + break;
>>> > + case nir_type_int:
>>> > + load->dest.ssa.name = 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 (jason at jlekstrand.net)
>>> > + *
>>> > + */
>>> > +
>>> > +#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
>>> > mesa-dev at lists.freedesktop.org
>>> > http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>>
>>
>
More information about the mesa-dev
mailing list