src/glsl/nir/nir_search.c

   1 /*
   2  * Copyright © 2014 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  *
  23  * Authors:
  24  *    Jason Ekstrand (jason@jlekstrand.net)
  25  *
  26  */
  27
  28 #include "nir_search.h"
  29
  30 struct match_state {
  31    unsigned variables_seen;
  32    nir_alu_src variables[NIR_SEARCH_MAX_VARIABLES];
  33 };
  34
  35 static bool
  36 is_commutative_binop(nir_op op)
  37 {
  38    switch (op) {
  39    case nir_op_fadd:
  40    case nir_op_iadd:
  41    case nir_op_fmul:
  42    case nir_op_imul:
  43    case nir_op_imul_high:
  44    case nir_op_umul_high:
  45    case nir_op_feq:
  46    case nir_op_fne:
  47    case nir_op_ieq:
  48    case nir_op_ine:
  49    case nir_op_fand:
  50    case nir_op_for:
  51    case nir_op_fxor:
  52    case nir_op_iand:
  53    case nir_op_ior:
  54    case nir_op_ixor:
  55    case nir_op_fmin:
  56    case nir_op_fmax:
  57    case nir_op_imin:
  58    case nir_op_imax:
  59    case nir_op_umin:
  60    case nir_op_umax:
  61       return true;
  62    default:
  63       return false;
  64    }
  65 }
  66
  67 static bool
  68 match_expression(const nir_search_expression *expr, nir_alu_instr *instr,
  69                  unsigned num_components, const uint8_t *swizzle,
  70                  struct match_state *state);
  71
  72 static const uint8_t identity_swizzle[] = { 0, 1, 2, 3 };
  73
  74 static bool
  75 match_value(const nir_search_value *value, nir_alu_instr *instr, unsigned src,
  76             unsigned num_components, const uint8_t *swizzle,
  77             struct match_state *state)
  78 {
  79    uint8_t new_swizzle[4];
  80
  81    for (int i = 0; i < num_components; ++i)
  82       new_swizzle[i] = instr->src[src].swizzle[swizzle[i]];
  83
  84    switch (value->type) {
  85    case nir_search_value_expression:
  86       if (!instr->src[src].src.is_ssa)
  87          return false;
  88
  89       if (instr->src[src].src.ssa->parent_instr->type != nir_instr_type_alu)
  90          return false;
  91
  92       return match_expression(nir_search_value_as_expression(value),
  93                               nir_instr_as_alu(instr->src[src].src.ssa->parent_instr),
  94                               num_components, new_swizzle, state);
  95
  96    case nir_search_value_variable: {
  97       nir_search_variable *var = nir_search_value_as_variable(value);
  98
  99       if (state->variables_seen & (1 << var->variable)) {
 100          if (!nir_srcs_equal(state->variables[var->variable].src,
 101                              instr->src[src].src))
 102             return false;
 103
 104          assert(!instr->src[src].abs && !instr->src[src].negate);
 105
 106          for (int i = 0; i < num_components; ++i) {
 107             if (state->variables[var->variable].swizzle[i] != new_swizzle[i])
 108                return false;
 109          }
 110
 111          return true;
 112       } else {
 113          state->variables_seen |= (1 << var->variable);
 114          state->variables[var->variable].src = instr->src[src].src;
 115          state->variables[var->variable].abs = false;
 116          state->variables[var->variable].negate = false;
 117
 118          for (int i = 0; i < 4; ++i) {
 119             if (i < num_components)
 120                state->variables[var->variable].swizzle[i] = new_swizzle[i];
 121             else
 122                state->variables[var->variable].swizzle[i] = 0;
 123          }
 124
 125          return true;
 126       }
 127    }
 128
 129    case nir_search_value_constant: {
 130       nir_search_constant *const_val = nir_search_value_as_constant(value);
 131
 132       if (!instr->src[src].src.is_ssa)
 133          return false;
 134
 135       if (instr->src[src].src.ssa->parent_instr->type != nir_instr_type_load_const)
 136          return false;
 137
 138       nir_load_const_instr *load =
 139          nir_instr_as_load_const(instr->src[src].src.ssa->parent_instr);
 140
 141       switch (nir_op_infos[instr->op].input_types[src]) {
 142       case nir_type_float:
 143          for (unsigned i = 0; i < num_components; ++i) {
 144             if (load->value.f[new_swizzle[i]] != const_val->data.f)
 145                return false;
 146          }
 147          return true;
 148       case nir_type_int:
 149       case nir_type_unsigned:
 150       case nir_type_bool:
 151          for (unsigned i = 0; i < num_components; ++i) {
 152             if (load->value.i[new_swizzle[i]] != const_val->data.i)
 153                return false;
 154          }
 155          return true;
 156       default:
 157          unreachable("Invalid alu source type");
 158       }
 159    }
 160
 161    default:
 162       unreachable("Invalid search value type");
 163    }
 164 }
 165
 166 static bool
 167 match_expression(const nir_search_expression *expr, nir_alu_instr *instr,
 168                  unsigned num_components, const uint8_t *swizzle,
 169                  struct match_state *state)
 170 {
 171    if (instr->op != expr->opcode)
 172       return false;
 173
 174    assert(!instr->dest.saturate);
 175    assert(nir_op_infos[instr->op].num_inputs > 0);
 176
 177    /* If we have an explicitly sized destination, we can only handle the
 178     * identity swizzle.  While dot(vec3(a, b, c).zxy) is a valid
 179     * expression, we don't have the information right now to propagate that
 180     * swizzle through.  We can only properly propagate swizzles if the
 181     * instruction is vectorized.
 182     */
 183    if (nir_op_infos[instr->op].output_size != 0) {
 184       for (unsigned i = 0; i < num_components; i++) {
 185          if (swizzle[i] != i)
 186             return false;
 187       }
 188    }
 189
 190    bool matched = true;
 191    for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) {
 192       /* If the source is an explicitly sized source, then we need to reset
 193        * both the number of components and the swizzle.
 194        */
 195       if (nir_op_infos[instr->op].input_sizes[i] != 0) {
 196          num_components = nir_op_infos[instr->op].input_sizes[i];
 197          swizzle = identity_swizzle;
 198       }
 199
 200       if (!match_value(expr->srcs[i], instr, i, num_components,
 201                        swizzle, state)) {
 202          matched = false;
 203          break;
 204       }
 205    }
 206
 207    if (matched)
 208       return true;
 209
 210    if (is_commutative_binop(instr->op)) {
 211       if (!match_value(expr->srcs[0], instr, 1, num_components,
 212                        swizzle, state))
 213          return false;
 214
 215       return match_value(expr->srcs[1], instr, 0, num_components,
 216                          swizzle, state);
 217    } else {
 218       return false;
 219    }
 220 }
 221
 222 static nir_alu_src
 223 construct_value(const nir_search_value *value, nir_alu_type type,
 224                 unsigned num_components, struct match_state *state,
 225                 nir_instr *instr, void *mem_ctx)
 226 {
 227    switch (value->type) {
 228    case nir_search_value_expression: {
 229       const nir_search_expression *expr = nir_search_value_as_expression(value);
 230
 231       if (nir_op_infos[expr->opcode].output_size != 0)
 232          num_components = nir_op_infos[expr->opcode].output_size;
 233
 234       nir_alu_instr *alu = nir_alu_instr_create(mem_ctx, expr->opcode);
 235       alu->dest.dest.is_ssa = true;
 236       nir_ssa_def_init(&alu->instr, &alu->dest.dest.ssa, num_components, NULL);
 237       alu->dest.write_mask = (1 << num_components) - 1;
 238       alu->dest.saturate = false;
 239
 240       for (unsigned i = 0; i < nir_op_infos[expr->opcode].num_inputs; i++) {
 241          /* If the source is an explicitly sized source, then we need to reset
 242           * the number of components to match.
 243           */
 244          if (nir_op_infos[alu->op].input_sizes[i] != 0)
 245             num_components = nir_op_infos[alu->op].input_sizes[i];
 246
 247          alu->src[i] = construct_value(expr->srcs[i],
 248                                        nir_op_infos[alu->op].input_types[i],
 249                                        num_components,
 250                                        state, instr, mem_ctx);
 251       }
 252
 253       nir_instr_insert_before(instr, &alu->instr);
 254
 255       nir_alu_src val = {
 256          .src.is_ssa = true,
 257          .src.ssa = &alu->dest.dest.ssa,
 258          .negate = false,
 259          .abs = false,
 260          .swizzle = { 0, 1, 2, 3 }
 261       };
 262
 263       return val;
 264    }
 265
 266    case nir_search_value_variable: {
 267       const nir_search_variable *var = nir_search_value_as_variable(value);
 268       assert(state->variables_seen & (1 << var->variable));
 269
 270       nir_alu_src val = state->variables[var->variable];
 271       val.src = nir_src_copy(val.src, mem_ctx);
 272
 273       return val;
 274    }
 275
 276    case nir_search_value_constant: {
 277       const nir_search_constant *c = nir_search_value_as_constant(value);
 278       nir_load_const_instr *load = nir_load_const_instr_create(mem_ctx, 1);
 279
 280       switch (type) {
 281       case nir_type_float:
 282          load->def.name = ralloc_asprintf(mem_ctx, "%f", c->data.f);
 283          load->value.f[0] = c->data.f;
 284          break;
 285       case nir_type_int:
 286          load->def.name = ralloc_asprintf(mem_ctx, "%d", c->data.i);
 287          load->value.i[0] = c->data.i;
 288          break;
 289       case nir_type_unsigned:
 290       case nir_type_bool:
 291          load->value.u[0] = c->data.u;
 292          break;
 293       default:
 294          unreachable("Invalid alu source type");
 295       }
 296
 297       nir_instr_insert_before(instr, &load->instr);
 298
 299       nir_alu_src val = {
 300          .src.is_ssa = true,
 301          .src.ssa = &load->def,
 302          .negate = false,
 303          .abs = false,
 304          .swizzle = { 0, 0, 0, 0 } /* Splatted scalar */
 305       };
 306
 307       return val;
 308    }
 309
 310    default:
 311       unreachable("Invalid search value type");
 312    }
 313 }
 314
 315 nir_alu_instr *
 316 nir_replace_instr(nir_alu_instr *instr, const nir_search_expression *search,
 317                   const nir_search_value *replace, void *mem_ctx)
 318 {
 319    uint8_t swizzle[4] = { 0, 0, 0, 0 };
 320
 321    for (unsigned i = 0; i < instr->dest.dest.ssa.num_components; ++i)
 322       swizzle[i] = i;
 323
 324    assert(instr->dest.dest.is_ssa);
 325
 326    struct match_state state;
 327    state.variables_seen = 0;
 328
 329    if (!match_expression(search, instr, instr->dest.dest.ssa.num_components,
 330                          swizzle, &state))
 331       return NULL;
 332
 333    /* Inserting a mov may be unnecessary.  However, it's much easier to
 334     * simply let copy propagation clean this up than to try to go through
 335     * and rewrite swizzles ourselves.
 336     */
 337    nir_alu_instr *mov = nir_alu_instr_create(mem_ctx, nir_op_imov);
 338    mov->dest.write_mask = instr->dest.write_mask;
 339    mov->dest.dest.is_ssa = true;
 340    nir_ssa_def_init(&mov->instr, &mov->dest.dest.ssa,
 341                     instr->dest.dest.ssa.num_components, NULL);
 342
 343    mov->src[0] = construct_value(replace, nir_op_infos[instr->op].output_type,
 344                                  instr->dest.dest.ssa.num_components, &state,
 345                                  &instr->instr, mem_ctx);
 346    nir_instr_insert_before(&instr->instr, &mov->instr);
 347
 348    nir_src replace_src = {
 349       .is_ssa = true,
 350       .ssa = &mov->dest.dest.ssa,
 351    };
 352
 353    nir_ssa_def_rewrite_uses(&instr->dest.dest.ssa, replace_src, mem_ctx);
 354
 355    /* We know this one has no more uses because we just rewrote them all,
 356     * so we can remove it.  The rest of the matched expression, however, we
 357     * don't know so much about.  We'll just let dead code clean them up.
 358     */
 359    nir_instr_remove(&instr->instr);
 360
 361    return mov;
 362 }