From 0057dfd673c62741bd9eba34759f3539940068a2 Mon Sep 17 00:00:00 2001 From: Jason Ekstrand Date: Thu, 13 Nov 2014 21:19:28 -0800 Subject: [PATCH] nir: Add an expression matching framework 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 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. Reviewed-by: Connor Abbott --- src/glsl/Makefile.sources | 2 + src/glsl/nir/nir_search.c | 364 ++++++++++++++++++++++++++++++++++++++ src/glsl/nir/nir_search.h | 80 +++++++++ 3 files changed, 446 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 12c1d8310b7..201330db269 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 00000000000..3930795a041 --- /dev/null +++ b/src/glsl/nir/nir_search.c @@ -0,0 +1,364 @@ +/* + * 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@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 const uint8_t identity_swizzle[] = { 0, 1, 2, 3 }; + +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[var->variable].src, + instr->src[src].src)) + 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 we have an explicitly sized destination, we can only handle the + * identity swizzle. While dot(vec3(a, b, c).zxy) is a valid + * expression, we don't have the information right now to propagate that + * swizzle through. We can only properly propagate swizzles if the + * instruction is vectorized. + */ + if (nir_op_infos[instr->op].output_size != 0) { + for (unsigned i = 0; i < num_components; i++) { + if (swizzle[i] != i) + return false; + } + } + + bool matched = true; + for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) { + /* If the source is an explicitly sized source, then we need to reset + * both the number of components and the swizzle. + */ + if (nir_op_infos[instr->op].input_sizes[i] != 0) { + num_components = nir_op_infos[instr->op].input_sizes[i]; + swizzle = identity_swizzle; + } + + if (!match_value(expr->srcs[i], instr, i, num_components, + swizzle, state)) { + 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); + + if (nir_op_infos[expr->opcode].output_size != 0) + num_components = nir_op_infos[expr->opcode].output_size; + + 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++) { + /* If the source is an explicitly sized source, then we need to reset + * the number of components to match. + */ + if (nir_op_infos[alu->op].input_sizes[i] != 0) + num_components = nir_op_infos[alu->op].input_sizes[i]; + + alu->src[i] = construct_value(expr->srcs[i], + nir_op_infos[alu->op].input_types[i], + num_components, + state, instr, mem_ctx); + } + + 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, 1, 2, 3 } + }; + + 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 00000000000..8ec58b07139 --- /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@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.30.2