src/compiler/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 <inttypes.h>
  29 #include "nir_search.h"
  30
  31 struct match_state {
  32    bool inexact_match;
  33    bool has_exact_alu;
  34    unsigned variables_seen;
  35    nir_alu_src variables[NIR_SEARCH_MAX_VARIABLES];
  36 };
  37
  38 static bool
  39 match_expression(const nir_search_expression *expr, nir_alu_instr *instr,
  40                  unsigned num_components, const uint8_t *swizzle,
  41                  struct match_state *state);
  42
  43 static const uint8_t identity_swizzle[] = { 0, 1, 2, 3 };
  44
  45 static bool alu_instr_is_bool(nir_alu_instr *instr);
  46
  47 static bool
  48 src_is_bool(nir_src src)
  49 {
  50    if (!src.is_ssa)
  51       return false;
  52    if (src.ssa->parent_instr->type != nir_instr_type_alu)
  53       return false;
  54    return alu_instr_is_bool(nir_instr_as_alu(src.ssa->parent_instr));
  55 }
  56
  57 static bool
  58 alu_instr_is_bool(nir_alu_instr *instr)
  59 {
  60    switch (instr->op) {
  61    case nir_op_iand:
  62    case nir_op_ior:
  63    case nir_op_ixor:
  64       return src_is_bool(instr->src[0].src) && src_is_bool(instr->src[1].src);
  65    case nir_op_inot:
  66       return src_is_bool(instr->src[0].src);
  67    default:
  68       return (nir_alu_type_get_base_type(nir_op_infos[instr->op].output_type)
  69              == nir_type_bool);
  70    }
  71 }
  72
  73 /**
  74  * Check if a source produces a value of the given type.
  75  *
  76  * Used for satisfying 'a@type' constraints.
  77  */
  78 static bool
  79 src_is_type(nir_src src, nir_alu_type type)
  80 {
  81    assert(type != nir_type_invalid);
  82
  83    if (!src.is_ssa)
  84       return false;
  85
  86    if (src.ssa->parent_instr->type == nir_instr_type_alu) {
  87       nir_alu_instr *src_alu = nir_instr_as_alu(src.ssa->parent_instr);
  88       nir_alu_type output_type = nir_op_infos[src_alu->op].output_type;
  89
  90       return nir_alu_type_get_base_type(output_type) == type ||
  91              (nir_alu_type_get_base_type(type) == nir_type_bool &&
  92               alu_instr_is_bool(src_alu));
  93    }
  94
  95    /* don't know */
  96    return false;
  97 }
  98
  99 static bool
 100 match_value(const nir_search_value *value, nir_alu_instr *instr, unsigned src,
 101             unsigned num_components, const uint8_t *swizzle,
 102             struct match_state *state)
 103 {
 104    uint8_t new_swizzle[4];
 105
 106    /* If the source is an explicitly sized source, then we need to reset
 107     * both the number of components and the swizzle.
 108     */
 109    if (nir_op_infos[instr->op].input_sizes[src] != 0) {
 110       num_components = nir_op_infos[instr->op].input_sizes[src];
 111       swizzle = identity_swizzle;
 112    }
 113
 114    for (unsigned i = 0; i < num_components; ++i)
 115       new_swizzle[i] = instr->src[src].swizzle[swizzle[i]];
 116
 117    /* If the value has a specific bit size and it doesn't match, bail */
 118    if (value->bit_size &&
 119        nir_src_bit_size(instr->src[src].src) != value->bit_size)
 120       return false;
 121
 122    switch (value->type) {
 123    case nir_search_value_expression:
 124       if (!instr->src[src].src.is_ssa)
 125          return false;
 126
 127       if (instr->src[src].src.ssa->parent_instr->type != nir_instr_type_alu)
 128          return false;
 129
 130       return match_expression(nir_search_value_as_expression(value),
 131                               nir_instr_as_alu(instr->src[src].src.ssa->parent_instr),
 132                               num_components, new_swizzle, state);
 133
 134    case nir_search_value_variable: {
 135       nir_search_variable *var = nir_search_value_as_variable(value);
 136       assert(var->variable < NIR_SEARCH_MAX_VARIABLES);
 137
 138       if (state->variables_seen & (1 << var->variable)) {
 139          if (!nir_srcs_equal(state->variables[var->variable].src,
 140                              instr->src[src].src))
 141             return false;
 142
 143          assert(!instr->src[src].abs && !instr->src[src].negate);
 144
 145          for (unsigned i = 0; i < num_components; ++i) {
 146             if (state->variables[var->variable].swizzle[i] != new_swizzle[i])
 147                return false;
 148          }
 149
 150          return true;
 151       } else {
 152          if (var->is_constant &&
 153              instr->src[src].src.ssa->parent_instr->type != nir_instr_type_load_const)
 154             return false;
 155
 156          if (var->cond && !var->cond(instr, src, num_components, new_swizzle))
 157             return false;
 158
 159          if (var->type != nir_type_invalid &&
 160              !src_is_type(instr->src[src].src, var->type))
 161             return false;
 162
 163          state->variables_seen |= (1 << var->variable);
 164          state->variables[var->variable].src = instr->src[src].src;
 165          state->variables[var->variable].abs = false;
 166          state->variables[var->variable].negate = false;
 167
 168          for (unsigned i = 0; i < 4; ++i) {
 169             if (i < num_components)
 170                state->variables[var->variable].swizzle[i] = new_swizzle[i];
 171             else
 172                state->variables[var->variable].swizzle[i] = 0;
 173          }
 174
 175          return true;
 176       }
 177    }
 178
 179    case nir_search_value_constant: {
 180       nir_search_constant *const_val = nir_search_value_as_constant(value);
 181
 182       if (!instr->src[src].src.is_ssa)
 183          return false;
 184
 185       if (instr->src[src].src.ssa->parent_instr->type != nir_instr_type_load_const)
 186          return false;
 187
 188       nir_load_const_instr *load =
 189          nir_instr_as_load_const(instr->src[src].src.ssa->parent_instr);
 190
 191       switch (const_val->type) {
 192       case nir_type_float:
 193          for (unsigned i = 0; i < num_components; ++i) {
 194             double val;
 195             switch (load->def.bit_size) {
 196             case 32:
 197                val = load->value.f32[new_swizzle[i]];
 198                break;
 199             case 64:
 200                val = load->value.f64[new_swizzle[i]];
 201                break;
 202             default:
 203                unreachable("unknown bit size");
 204             }
 205
 206             if (val != const_val->data.d)
 207                return false;
 208          }
 209          return true;
 210
 211       case nir_type_int:
 212          for (unsigned i = 0; i < num_components; ++i) {
 213             int64_t val;
 214             switch (load->def.bit_size) {
 215             case 32:
 216                val = load->value.i32[new_swizzle[i]];
 217                break;
 218             case 64:
 219                val = load->value.i64[new_swizzle[i]];
 220                break;
 221             default:
 222                unreachable("unknown bit size");
 223             }
 224
 225             if (val != const_val->data.i)
 226                return false;
 227          }
 228          return true;
 229
 230       case nir_type_uint:
 231       case nir_type_bool32:
 232          for (unsigned i = 0; i < num_components; ++i) {
 233             uint64_t val;
 234             switch (load->def.bit_size) {
 235             case 32:
 236                val = load->value.u32[new_swizzle[i]];
 237                break;
 238             case 64:
 239                val = load->value.u64[new_swizzle[i]];
 240                break;
 241             default:
 242                unreachable("unknown bit size");
 243             }
 244
 245             if (val != const_val->data.u)
 246                return false;
 247          }
 248          return true;
 249
 250       default:
 251          unreachable("Invalid alu source type");
 252       }
 253    }
 254
 255    default:
 256       unreachable("Invalid search value type");
 257    }
 258 }
 259
 260 static bool
 261 match_expression(const nir_search_expression *expr, nir_alu_instr *instr,
 262                  unsigned num_components, const uint8_t *swizzle,
 263                  struct match_state *state)
 264 {
 265    if (instr->op != expr->opcode)
 266       return false;
 267
 268    assert(instr->dest.dest.is_ssa);
 269
 270    if (expr->value.bit_size &&
 271        instr->dest.dest.ssa.bit_size != expr->value.bit_size)
 272       return false;
 273
 274    state->inexact_match = expr->inexact || state->inexact_match;
 275    state->has_exact_alu = instr->exact || state->has_exact_alu;
 276    if (state->inexact_match && state->has_exact_alu)
 277       return false;
 278
 279    assert(!instr->dest.saturate);
 280    assert(nir_op_infos[instr->op].num_inputs > 0);
 281
 282    /* If we have an explicitly sized destination, we can only handle the
 283     * identity swizzle.  While dot(vec3(a, b, c).zxy) is a valid
 284     * expression, we don't have the information right now to propagate that
 285     * swizzle through.  We can only properly propagate swizzles if the
 286     * instruction is vectorized.
 287     */
 288    if (nir_op_infos[instr->op].output_size != 0) {
 289       for (unsigned i = 0; i < num_components; i++) {
 290          if (swizzle[i] != i)
 291             return false;
 292       }
 293    }
 294
 295    /* Stash off the current variables_seen bitmask.  This way we can
 296     * restore it prior to matching in the commutative case below.
 297     */
 298    unsigned variables_seen_stash = state->variables_seen;
 299
 300    bool matched = true;
 301    for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) {
 302       if (!match_value(expr->srcs[i], instr, i, num_components,
 303                        swizzle, state)) {
 304          matched = false;
 305          break;
 306       }
 307    }
 308
 309    if (matched)
 310       return true;
 311
 312    if (nir_op_infos[instr->op].algebraic_properties & NIR_OP_IS_COMMUTATIVE) {
 313       assert(nir_op_infos[instr->op].num_inputs == 2);
 314
 315       /* Restore the variables_seen bitmask.  If we don't do this, then we
 316        * could end up with an erroneous failure due to variables found in the
 317        * first match attempt above not matching those in the second.
 318        */
 319       state->variables_seen = variables_seen_stash;
 320
 321       if (!match_value(expr->srcs[0], instr, 1, num_components,
 322                        swizzle, state))
 323          return false;
 324
 325       return match_value(expr->srcs[1], instr, 0, num_components,
 326                          swizzle, state);
 327    } else {
 328       return false;
 329    }
 330 }
 331
 332 typedef struct bitsize_tree {
 333    unsigned num_srcs;
 334    struct bitsize_tree *srcs[4];
 335
 336    unsigned common_size;
 337    bool is_src_sized[4];
 338    bool is_dest_sized;
 339
 340    unsigned dest_size;
 341    unsigned src_size[4];
 342 } bitsize_tree;
 343
 344 static bitsize_tree *
 345 build_bitsize_tree(void *mem_ctx, struct match_state *state,
 346                    const nir_search_value *value)
 347 {
 348    bitsize_tree *tree = ralloc(mem_ctx, bitsize_tree);
 349
 350    switch (value->type) {
 351    case nir_search_value_expression: {
 352       nir_search_expression *expr = nir_search_value_as_expression(value);
 353       nir_op_info info = nir_op_infos[expr->opcode];
 354       tree->num_srcs = info.num_inputs;
 355       tree->common_size = 0;
 356       for (unsigned i = 0; i < info.num_inputs; i++) {
 357          tree->is_src_sized[i] = !!nir_alu_type_get_type_size(info.input_types[i]);
 358          if (tree->is_src_sized[i])
 359             tree->src_size[i] = nir_alu_type_get_type_size(info.input_types[i]);
 360          tree->srcs[i] = build_bitsize_tree(mem_ctx, state, expr->srcs[i]);
 361       }
 362       tree->is_dest_sized = !!nir_alu_type_get_type_size(info.output_type);
 363       if (tree->is_dest_sized)
 364          tree->dest_size = nir_alu_type_get_type_size(info.output_type);
 365       break;
 366    }
 367
 368    case nir_search_value_variable: {
 369       nir_search_variable *var = nir_search_value_as_variable(value);
 370       tree->num_srcs = 0;
 371       tree->is_dest_sized = true;
 372       tree->dest_size = nir_src_bit_size(state->variables[var->variable].src);
 373       break;
 374    }
 375
 376    case nir_search_value_constant: {
 377       tree->num_srcs = 0;
 378       tree->is_dest_sized = false;
 379       tree->common_size = 0;
 380       break;
 381    }
 382    }
 383
 384    if (value->bit_size) {
 385       assert(!tree->is_dest_sized || tree->dest_size == value->bit_size);
 386       tree->common_size = value->bit_size;
 387    }
 388
 389    return tree;
 390 }
 391
 392 static unsigned
 393 bitsize_tree_filter_up(bitsize_tree *tree)
 394 {
 395    for (unsigned i = 0; i < tree->num_srcs; i++) {
 396       unsigned src_size = bitsize_tree_filter_up(tree->srcs[i]);
 397       if (src_size == 0)
 398          continue;
 399
 400       if (tree->is_src_sized[i]) {
 401          assert(src_size == tree->src_size[i]);
 402       } else if (tree->common_size != 0) {
 403          assert(src_size == tree->common_size);
 404          tree->src_size[i] = src_size;
 405       } else {
 406          tree->common_size = src_size;
 407          tree->src_size[i] = src_size;
 408       }
 409    }
 410
 411    if (tree->num_srcs && tree->common_size) {
 412       if (tree->dest_size == 0)
 413          tree->dest_size = tree->common_size;
 414       else if (!tree->is_dest_sized)
 415          assert(tree->dest_size == tree->common_size);
 416
 417       for (unsigned i = 0; i < tree->num_srcs; i++) {
 418          if (!tree->src_size[i])
 419             tree->src_size[i] = tree->common_size;
 420       }
 421    }
 422
 423    return tree->dest_size;
 424 }
 425
 426 static void
 427 bitsize_tree_filter_down(bitsize_tree *tree, unsigned size)
 428 {
 429    if (tree->dest_size)
 430       assert(tree->dest_size == size);
 431    else
 432       tree->dest_size = size;
 433
 434    if (!tree->is_dest_sized) {
 435       if (tree->common_size)
 436          assert(tree->common_size == size);
 437       else
 438          tree->common_size = size;
 439    }
 440
 441    for (unsigned i = 0; i < tree->num_srcs; i++) {
 442       if (!tree->src_size[i]) {
 443          assert(tree->common_size);
 444          tree->src_size[i] = tree->common_size;
 445       }
 446       bitsize_tree_filter_down(tree->srcs[i], tree->src_size[i]);
 447    }
 448 }
 449
 450 static nir_alu_src
 451 construct_value(const nir_search_value *value,
 452                 unsigned num_components, bitsize_tree *bitsize,
 453                 struct match_state *state,
 454                 nir_instr *instr, void *mem_ctx)
 455 {
 456    switch (value->type) {
 457    case nir_search_value_expression: {
 458       const nir_search_expression *expr = nir_search_value_as_expression(value);
 459
 460       if (nir_op_infos[expr->opcode].output_size != 0)
 461          num_components = nir_op_infos[expr->opcode].output_size;
 462
 463       nir_alu_instr *alu = nir_alu_instr_create(mem_ctx, expr->opcode);
 464       nir_ssa_dest_init(&alu->instr, &alu->dest.dest, num_components,
 465                         bitsize->dest_size, NULL);
 466       alu->dest.write_mask = (1 << num_components) - 1;
 467       alu->dest.saturate = false;
 468
 469       /* We have no way of knowing what values in a given search expression
 470        * map to a particular replacement value.  Therefore, if the
 471        * expression we are replacing has any exact values, the entire
 472        * replacement should be exact.
 473        */
 474       alu->exact = state->has_exact_alu;
 475
 476       for (unsigned i = 0; i < nir_op_infos[expr->opcode].num_inputs; i++) {
 477          /* If the source is an explicitly sized source, then we need to reset
 478           * the number of components to match.
 479           */
 480          if (nir_op_infos[alu->op].input_sizes[i] != 0)
 481             num_components = nir_op_infos[alu->op].input_sizes[i];
 482
 483          alu->src[i] = construct_value(expr->srcs[i],
 484                                        num_components, bitsize->srcs[i],
 485                                        state, instr, mem_ctx);
 486       }
 487
 488       nir_instr_insert_before(instr, &alu->instr);
 489
 490       nir_alu_src val;
 491       val.src = nir_src_for_ssa(&alu->dest.dest.ssa);
 492       val.negate = false;
 493       val.abs = false,
 494       memcpy(val.swizzle, identity_swizzle, sizeof val.swizzle);
 495
 496       return val;
 497    }
 498
 499    case nir_search_value_variable: {
 500       const nir_search_variable *var = nir_search_value_as_variable(value);
 501       assert(state->variables_seen & (1 << var->variable));
 502
 503       nir_alu_src val = { NIR_SRC_INIT };
 504       nir_alu_src_copy(&val, &state->variables[var->variable], mem_ctx);
 505
 506       assert(!var->is_constant);
 507
 508       return val;
 509    }
 510
 511    case nir_search_value_constant: {
 512       const nir_search_constant *c = nir_search_value_as_constant(value);
 513       nir_load_const_instr *load =
 514          nir_load_const_instr_create(mem_ctx, 1, bitsize->dest_size);
 515
 516       switch (c->type) {
 517       case nir_type_float:
 518          load->def.name = ralloc_asprintf(load, "%f", c->data.d);
 519          switch (bitsize->dest_size) {
 520          case 32:
 521             load->value.f32[0] = c->data.d;
 522             break;
 523          case 64:
 524             load->value.f64[0] = c->data.d;
 525             break;
 526          default:
 527             unreachable("unknown bit size");
 528          }
 529          break;
 530
 531       case nir_type_int:
 532          load->def.name = ralloc_asprintf(load, "%" PRIi64, c->data.i);
 533          switch (bitsize->dest_size) {
 534          case 32:
 535             load->value.i32[0] = c->data.i;
 536             break;
 537          case 64:
 538             load->value.i64[0] = c->data.i;
 539             break;
 540          default:
 541             unreachable("unknown bit size");
 542          }
 543          break;
 544
 545       case nir_type_uint:
 546          load->def.name = ralloc_asprintf(load, "%" PRIu64, c->data.u);
 547          switch (bitsize->dest_size) {
 548          case 32:
 549             load->value.u32[0] = c->data.u;
 550             break;
 551          case 64:
 552             load->value.u64[0] = c->data.u;
 553             break;
 554          default:
 555             unreachable("unknown bit size");
 556          }
 557          break;
 558
 559       case nir_type_bool32:
 560          load->value.u32[0] = c->data.u;
 561          break;
 562       default:
 563          unreachable("Invalid alu source type");
 564       }
 565
 566       nir_instr_insert_before(instr, &load->instr);
 567
 568       nir_alu_src val;
 569       val.src = nir_src_for_ssa(&load->def);
 570       val.negate = false;
 571       val.abs = false,
 572       memset(val.swizzle, 0, sizeof val.swizzle);
 573
 574       return val;
 575    }
 576
 577    default:
 578       unreachable("Invalid search value type");
 579    }
 580 }
 581
 582 nir_alu_instr *
 583 nir_replace_instr(nir_alu_instr *instr, const nir_search_expression *search,
 584                   const nir_search_value *replace, void *mem_ctx)
 585 {
 586    uint8_t swizzle[4] = { 0, 0, 0, 0 };
 587
 588    for (unsigned i = 0; i < instr->dest.dest.ssa.num_components; ++i)
 589       swizzle[i] = i;
 590
 591    assert(instr->dest.dest.is_ssa);
 592
 593    struct match_state state;
 594    state.inexact_match = false;
 595    state.has_exact_alu = false;
 596    state.variables_seen = 0;
 597
 598    if (!match_expression(search, instr, instr->dest.dest.ssa.num_components,
 599                          swizzle, &state))
 600       return NULL;
 601
 602    void *bitsize_ctx = ralloc_context(NULL);
 603    bitsize_tree *tree = build_bitsize_tree(bitsize_ctx, &state, replace);
 604    bitsize_tree_filter_up(tree);
 605    bitsize_tree_filter_down(tree, instr->dest.dest.ssa.bit_size);
 606
 607    /* Inserting a mov may be unnecessary.  However, it's much easier to
 608     * simply let copy propagation clean this up than to try to go through
 609     * and rewrite swizzles ourselves.
 610     */
 611    nir_alu_instr *mov = nir_alu_instr_create(mem_ctx, nir_op_imov);
 612    mov->dest.write_mask = instr->dest.write_mask;
 613    nir_ssa_dest_init(&mov->instr, &mov->dest.dest,
 614                      instr->dest.dest.ssa.num_components,
 615                      instr->dest.dest.ssa.bit_size, NULL);
 616
 617    mov->src[0] = construct_value(replace,
 618                                  instr->dest.dest.ssa.num_components, tree,
 619                                  &state, &instr->instr, mem_ctx);
 620    nir_instr_insert_before(&instr->instr, &mov->instr);
 621
 622    nir_ssa_def_rewrite_uses(&instr->dest.dest.ssa,
 623                             nir_src_for_ssa(&mov->dest.dest.ssa));
 624
 625    /* We know this one has no more uses because we just rewrote them all,
 626     * so we can remove it.  The rest of the matched expression, however, we
 627     * don't know so much about.  We'll just let dead code clean them up.
 628     */
 629    nir_instr_remove(&instr->instr);
 630
 631    ralloc_free(bitsize_ctx);
 632
 633    return mov;
 634 }