[Mesa-dev] [PATCH 110/133] nir: Add an expression matching framework
Connor Abbott
cwabbott0 at gmail.com
Mon Jan 5 21:12:54 PST 2015
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.
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.)
> 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.
>
> + 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.
> +
> + 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.
>
> + 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.
> + }
> +
> + 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.
>
> +
> + 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