src/compiler/nir/nir_instr_set.c

   1 /*
   2  * Copyright © 2014 Connor Abbott
   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
  24 #include "nir_instr_set.h"
  25 #include "nir_vla.h"
  26 #include "util/half_float.h"
  27
  28 #define HASH(hash, data) _mesa_fnv32_1a_accumulate((hash), (data))
  29
  30 static uint32_t
  31 hash_src(uint32_t hash, const nir_src *src)
  32 {
  33    assert(src->is_ssa);
  34    hash = HASH(hash, src->ssa);
  35    return hash;
  36 }
  37
  38 static uint32_t
  39 hash_alu_src(uint32_t hash, const nir_alu_src *src, unsigned num_components)
  40 {
  41    hash = HASH(hash, src->abs);
  42    hash = HASH(hash, src->negate);
  43
  44    for (unsigned i = 0; i < num_components; i++)
  45       hash = HASH(hash, src->swizzle[i]);
  46
  47    hash = hash_src(hash, &src->src);
  48    return hash;
  49 }
  50
  51 static uint32_t
  52 hash_alu(uint32_t hash, const nir_alu_instr *instr)
  53 {
  54    hash = HASH(hash, instr->op);
  55    hash = HASH(hash, instr->dest.dest.ssa.num_components);
  56    hash = HASH(hash, instr->dest.dest.ssa.bit_size);
  57    /* We explicitly don't hash instr->dest.dest.exact */
  58
  59    if (nir_op_infos[instr->op].algebraic_properties & NIR_OP_IS_COMMUTATIVE) {
  60       assert(nir_op_infos[instr->op].num_inputs == 2);
  61       uint32_t hash0 = hash_alu_src(hash, &instr->src[0],
  62                                     nir_ssa_alu_instr_src_components(instr, 0));
  63       uint32_t hash1 = hash_alu_src(hash, &instr->src[1],
  64                                     nir_ssa_alu_instr_src_components(instr, 1));
  65       /* For commutative operations, we need some commutative way of
  66        * combining the hashes.  One option would be to XOR them but that
  67        * means that anything with two identical sources will hash to 0 and
  68        * that's common enough we probably don't want the guaranteed
  69        * collision.  Either addition or multiplication will also work.
  70        */
  71       hash = hash0 * hash1;
  72    } else {
  73       for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) {
  74          hash = hash_alu_src(hash, &instr->src[i],
  75                              nir_ssa_alu_instr_src_components(instr, i));
  76       }
  77    }
  78
  79    return hash;
  80 }
  81
  82 static uint32_t
  83 hash_deref(uint32_t hash, const nir_deref_instr *instr)
  84 {
  85    hash = HASH(hash, instr->deref_type);
  86    hash = HASH(hash, instr->mode);
  87    hash = HASH(hash, instr->type);
  88
  89    if (instr->deref_type == nir_deref_type_var)
  90       return HASH(hash, instr->var);
  91
  92    hash = hash_src(hash, &instr->parent);
  93
  94    switch (instr->deref_type) {
  95    case nir_deref_type_struct:
  96       hash = HASH(hash, instr->strct.index);
  97       break;
  98
  99    case nir_deref_type_array:
 100    case nir_deref_type_ptr_as_array:
 101       hash = hash_src(hash, &instr->arr.index);
 102       break;
 103
 104    case nir_deref_type_cast:
 105       hash = HASH(hash, instr->cast.ptr_stride);
 106       break;
 107
 108    case nir_deref_type_var:
 109    case nir_deref_type_array_wildcard:
 110       /* Nothing to do */
 111       break;
 112
 113    default:
 114       unreachable("Invalid instruction deref type");
 115    }
 116
 117    return hash;
 118 }
 119
 120 static uint32_t
 121 hash_load_const(uint32_t hash, const nir_load_const_instr *instr)
 122 {
 123    hash = HASH(hash, instr->def.num_components);
 124
 125    if (instr->def.bit_size == 1) {
 126       for (unsigned i = 0; i < instr->def.num_components; i++) {
 127          uint8_t b = instr->value.b[i];
 128          hash = HASH(hash, b);
 129       }
 130    } else {
 131       unsigned size = instr->def.num_components * (instr->def.bit_size / 8);
 132       hash = _mesa_fnv32_1a_accumulate_block(hash, instr->value.f32, size);
 133    }
 134
 135    return hash;
 136 }
 137
 138 static int
 139 cmp_phi_src(const void *data1, const void *data2)
 140 {
 141    nir_phi_src *src1 = *(nir_phi_src **)data1;
 142    nir_phi_src *src2 = *(nir_phi_src **)data2;
 143    return src1->pred - src2->pred;
 144 }
 145
 146 static uint32_t
 147 hash_phi(uint32_t hash, const nir_phi_instr *instr)
 148 {
 149    hash = HASH(hash, instr->instr.block);
 150
 151    /* sort sources by predecessor, since the order shouldn't matter */
 152    unsigned num_preds = instr->instr.block->predecessors->entries;
 153    NIR_VLA(nir_phi_src *, srcs, num_preds);
 154    unsigned i = 0;
 155    nir_foreach_phi_src(src, instr) {
 156       srcs[i++] = src;
 157    }
 158
 159    qsort(srcs, num_preds, sizeof(nir_phi_src *), cmp_phi_src);
 160
 161    for (i = 0; i < num_preds; i++) {
 162       hash = hash_src(hash, &srcs[i]->src);
 163       hash = HASH(hash, srcs[i]->pred);
 164    }
 165
 166    return hash;
 167 }
 168
 169 static uint32_t
 170 hash_intrinsic(uint32_t hash, const nir_intrinsic_instr *instr)
 171 {
 172    const nir_intrinsic_info *info = &nir_intrinsic_infos[instr->intrinsic];
 173    hash = HASH(hash, instr->intrinsic);
 174
 175    if (info->has_dest) {
 176       hash = HASH(hash, instr->dest.ssa.num_components);
 177       hash = HASH(hash, instr->dest.ssa.bit_size);
 178    }
 179
 180    hash = _mesa_fnv32_1a_accumulate_block(hash, instr->const_index,
 181                                           info->num_indices
 182                                              * sizeof(instr->const_index[0]));
 183    return hash;
 184 }
 185
 186 static uint32_t
 187 hash_tex(uint32_t hash, const nir_tex_instr *instr)
 188 {
 189    hash = HASH(hash, instr->op);
 190    hash = HASH(hash, instr->num_srcs);
 191
 192    for (unsigned i = 0; i < instr->num_srcs; i++) {
 193       hash = HASH(hash, instr->src[i].src_type);
 194       hash = hash_src(hash, &instr->src[i].src);
 195    }
 196
 197    hash = HASH(hash, instr->coord_components);
 198    hash = HASH(hash, instr->sampler_dim);
 199    hash = HASH(hash, instr->is_array);
 200    hash = HASH(hash, instr->is_shadow);
 201    hash = HASH(hash, instr->is_new_style_shadow);
 202    unsigned component = instr->component;
 203    hash = HASH(hash, component);
 204    for (unsigned i = 0; i < 4; ++i)
 205       for (unsigned j = 0; j < 2; ++j)
 206          hash = HASH(hash, instr->tg4_offsets[i][j]);
 207    hash = HASH(hash, instr->texture_index);
 208    hash = HASH(hash, instr->texture_array_size);
 209    hash = HASH(hash, instr->sampler_index);
 210
 211    return hash;
 212 }
 213
 214 /* Computes a hash of an instruction for use in a hash table. Note that this
 215  * will only work for instructions where instr_can_rewrite() returns true, and
 216  * it should return identical hashes for two instructions that are the same
 217  * according nir_instrs_equal().
 218  */
 219
 220 static uint32_t
 221 hash_instr(const void *data)
 222 {
 223    const nir_instr *instr = data;
 224    uint32_t hash = _mesa_fnv32_1a_offset_bias;
 225
 226    switch (instr->type) {
 227    case nir_instr_type_alu:
 228       hash = hash_alu(hash, nir_instr_as_alu(instr));
 229       break;
 230    case nir_instr_type_deref:
 231       hash = hash_deref(hash, nir_instr_as_deref(instr));
 232       break;
 233    case nir_instr_type_load_const:
 234       hash = hash_load_const(hash, nir_instr_as_load_const(instr));
 235       break;
 236    case nir_instr_type_phi:
 237       hash = hash_phi(hash, nir_instr_as_phi(instr));
 238       break;
 239    case nir_instr_type_intrinsic:
 240       hash = hash_intrinsic(hash, nir_instr_as_intrinsic(instr));
 241       break;
 242    case nir_instr_type_tex:
 243       hash = hash_tex(hash, nir_instr_as_tex(instr));
 244       break;
 245    default:
 246       unreachable("Invalid instruction type");
 247    }
 248
 249    return hash;
 250 }
 251
 252 bool
 253 nir_srcs_equal(nir_src src1, nir_src src2)
 254 {
 255    if (src1.is_ssa) {
 256       if (src2.is_ssa) {
 257          return src1.ssa == src2.ssa;
 258       } else {
 259          return false;
 260       }
 261    } else {
 262       if (src2.is_ssa) {
 263          return false;
 264       } else {
 265          if ((src1.reg.indirect == NULL) != (src2.reg.indirect == NULL))
 266             return false;
 267
 268          if (src1.reg.indirect) {
 269             if (!nir_srcs_equal(*src1.reg.indirect, *src2.reg.indirect))
 270                return false;
 271          }
 272
 273          return src1.reg.reg == src2.reg.reg &&
 274                 src1.reg.base_offset == src2.reg.base_offset;
 275       }
 276    }
 277 }
 278
 279 /**
 280  * If the \p s is an SSA value that was generated by a negation instruction,
 281  * that instruction is returned as a \c nir_alu_instr.  Otherwise \c NULL is
 282  * returned.
 283  */
 284 static const struct nir_alu_instr *
 285 get_neg_instr(const nir_src *s)
 286 {
 287    const struct nir_alu_instr *const alu = nir_src_as_alu_instr_const(s);
 288
 289    return alu != NULL && (alu->op == nir_op_fneg || alu->op == nir_op_ineg)
 290           ? alu : NULL;
 291 }
 292
 293 bool
 294 nir_const_value_negative_equal(const nir_const_value *c1,
 295                                const nir_const_value *c2,
 296                                unsigned components,
 297                                nir_alu_type base_type,
 298                                unsigned bits)
 299 {
 300    assert(base_type == nir_alu_type_get_base_type(base_type));
 301    assert(base_type != nir_type_invalid);
 302
 303    /* This can occur for 1-bit Boolean values. */
 304    if (bits == 1)
 305       return false;
 306
 307    switch (base_type) {
 308    case nir_type_float:
 309       switch (bits) {
 310       case 16:
 311          for (unsigned i = 0; i < components; i++) {
 312             if (_mesa_half_to_float(c1->u16[i]) !=
 313                 -_mesa_half_to_float(c2->u16[i])) {
 314                return false;
 315             }
 316          }
 317
 318          return true;
 319
 320       case 32:
 321          for (unsigned i = 0; i < components; i++) {
 322             if (c1->f32[i] != -c2->f32[i])
 323                return false;
 324          }
 325
 326          return true;
 327
 328       case 64:
 329          for (unsigned i = 0; i < components; i++) {
 330             if (c1->f64[i] != -c2->f64[i])
 331                return false;
 332          }
 333
 334          return true;
 335
 336       default:
 337          unreachable("unknown bit size");
 338       }
 339
 340       break;
 341
 342    case nir_type_int:
 343    case nir_type_uint:
 344       switch (bits) {
 345       case 8:
 346          for (unsigned i = 0; i < components; i++) {
 347             if (c1->i8[i] != -c2->i8[i])
 348                return false;
 349          }
 350
 351          return true;
 352
 353       case 16:
 354          for (unsigned i = 0; i < components; i++) {
 355             if (c1->i16[i] != -c2->i16[i])
 356                return false;
 357          }
 358
 359          return true;
 360          break;
 361
 362       case 32:
 363          for (unsigned i = 0; i < components; i++) {
 364             if (c1->i32[i] != -c2->i32[i])
 365                return false;
 366          }
 367
 368          return true;
 369
 370       case 64:
 371          for (unsigned i = 0; i < components; i++) {
 372             if (c1->i64[i] != -c2->i64[i])
 373                return false;
 374          }
 375
 376          return true;
 377
 378       default:
 379          unreachable("unknown bit size");
 380       }
 381
 382       break;
 383
 384    case nir_type_bool:
 385       return false;
 386
 387    default:
 388       break;
 389    }
 390
 391    return false;
 392 }
 393
 394 /**
 395  * Shallow compare of ALU srcs to determine if one is the negation of the other
 396  *
 397  * This function detects cases where \p alu1 is a constant and \p alu2 is a
 398  * constant that is its negation.  It will also detect cases where \p alu2 is
 399  * an SSA value that is a \c nir_op_fneg applied to \p alu1 (and vice versa).
 400  *
 401  * This function does not detect the general case when \p alu1 and \p alu2 are
 402  * SSA values that are the negations of each other (e.g., \p alu1 represents
 403  * (a * b) and \p alu2 represents (-a * b)).
 404  */
 405 bool
 406 nir_alu_srcs_negative_equal(const nir_alu_instr *alu1,
 407                             const nir_alu_instr *alu2,
 408                             unsigned src1, unsigned src2)
 409 {
 410    if (alu1->src[src1].abs != alu2->src[src2].abs)
 411       return false;
 412
 413    bool parity = alu1->src[src1].negate != alu2->src[src2].negate;
 414
 415    /* Handling load_const instructions is tricky. */
 416
 417    const nir_const_value *const const1 =
 418       nir_src_as_const_value(alu1->src[src1].src);
 419
 420    if (const1 != NULL) {
 421       /* Assume that constant folding will eliminate source mods and unary
 422        * ops.
 423        */
 424       if (parity)
 425          return false;
 426
 427       const nir_const_value *const const2 =
 428          nir_src_as_const_value(alu2->src[src2].src);
 429
 430       if (const2 == NULL)
 431          return false;
 432
 433       /* FINISHME: Apply the swizzle? */
 434       return nir_const_value_negative_equal(const1,
 435                                             const2,
 436                                             nir_ssa_alu_instr_src_components(alu1, src1),
 437                                             nir_op_infos[alu1->op].input_types[src1],
 438                                             alu1->dest.dest.ssa.bit_size);
 439    }
 440
 441    uint8_t alu1_swizzle[4] = {};
 442    nir_src alu1_actual_src;
 443    const struct nir_alu_instr *const neg1 = get_neg_instr(&alu1->src[src1].src);
 444
 445    if (neg1) {
 446       parity = !parity;
 447       alu1_actual_src = neg1->src[0].src;
 448
 449       for (unsigned i = 0; i < nir_ssa_alu_instr_src_components(neg1, 0); i++)
 450          alu1_swizzle[i] = neg1->src[0].swizzle[i];
 451    } else {
 452       alu1_actual_src = alu1->src[src1].src;
 453
 454       for (unsigned i = 0; i < nir_ssa_alu_instr_src_components(alu1, src1); i++)
 455          alu1_swizzle[i] = i;
 456    }
 457
 458    uint8_t alu2_swizzle[4] = {};
 459    nir_src alu2_actual_src;
 460    const struct nir_alu_instr *const neg2 = get_neg_instr(&alu2->src[src2].src);
 461
 462    if (neg2) {
 463       parity = !parity;
 464       alu2_actual_src = neg2->src[0].src;
 465
 466       for (unsigned i = 0; i < nir_ssa_alu_instr_src_components(neg2, 0); i++)
 467          alu2_swizzle[i] = neg2->src[0].swizzle[i];
 468    } else {
 469       alu2_actual_src = alu2->src[src2].src;
 470
 471       for (unsigned i = 0; i < nir_ssa_alu_instr_src_components(alu2, src2); i++)
 472          alu2_swizzle[i] = i;
 473    }
 474
 475    for (unsigned i = 0; i < nir_ssa_alu_instr_src_components(alu1, src1); i++) {
 476       if (alu1_swizzle[alu1->src[src1].swizzle[i]] !=
 477           alu2_swizzle[alu2->src[src2].swizzle[i]])
 478          return false;
 479    }
 480
 481    return parity && nir_srcs_equal(alu1_actual_src, alu2_actual_src);
 482 }
 483
 484 bool
 485 nir_alu_srcs_equal(const nir_alu_instr *alu1, const nir_alu_instr *alu2,
 486                    unsigned src1, unsigned src2)
 487 {
 488    if (alu1->src[src1].abs != alu2->src[src2].abs ||
 489        alu1->src[src1].negate != alu2->src[src2].negate)
 490       return false;
 491
 492    for (unsigned i = 0; i < nir_ssa_alu_instr_src_components(alu1, src1); i++) {
 493       if (alu1->src[src1].swizzle[i] != alu2->src[src2].swizzle[i])
 494          return false;
 495    }
 496
 497    return nir_srcs_equal(alu1->src[src1].src, alu2->src[src2].src);
 498 }
 499
 500 /* Returns "true" if two instructions are equal. Note that this will only
 501  * work for the subset of instructions defined by instr_can_rewrite(). Also,
 502  * it should only return "true" for instructions that hash_instr() will return
 503  * the same hash for (ignoring collisions, of course).
 504  */
 505
 506 static bool
 507 nir_instrs_equal(const nir_instr *instr1, const nir_instr *instr2)
 508 {
 509    if (instr1->type != instr2->type)
 510       return false;
 511
 512    switch (instr1->type) {
 513    case nir_instr_type_alu: {
 514       nir_alu_instr *alu1 = nir_instr_as_alu(instr1);
 515       nir_alu_instr *alu2 = nir_instr_as_alu(instr2);
 516
 517       if (alu1->op != alu2->op)
 518          return false;
 519
 520       /* TODO: We can probably acutally do something more inteligent such
 521        * as allowing different numbers and taking a maximum or something
 522        * here */
 523       if (alu1->dest.dest.ssa.num_components != alu2->dest.dest.ssa.num_components)
 524          return false;
 525
 526       if (alu1->dest.dest.ssa.bit_size != alu2->dest.dest.ssa.bit_size)
 527          return false;
 528
 529       /* We explicitly don't hash instr->dest.dest.exact */
 530
 531       if (nir_op_infos[alu1->op].algebraic_properties & NIR_OP_IS_COMMUTATIVE) {
 532          assert(nir_op_infos[alu1->op].num_inputs == 2);
 533          return (nir_alu_srcs_equal(alu1, alu2, 0, 0) &&
 534                  nir_alu_srcs_equal(alu1, alu2, 1, 1)) ||
 535                 (nir_alu_srcs_equal(alu1, alu2, 0, 1) &&
 536                  nir_alu_srcs_equal(alu1, alu2, 1, 0));
 537       } else {
 538          for (unsigned i = 0; i < nir_op_infos[alu1->op].num_inputs; i++) {
 539             if (!nir_alu_srcs_equal(alu1, alu2, i, i))
 540                return false;
 541          }
 542       }
 543       return true;
 544    }
 545    case nir_instr_type_deref: {
 546       nir_deref_instr *deref1 = nir_instr_as_deref(instr1);
 547       nir_deref_instr *deref2 = nir_instr_as_deref(instr2);
 548
 549       if (deref1->deref_type != deref2->deref_type ||
 550           deref1->mode != deref2->mode ||
 551           deref1->type != deref2->type)
 552          return false;
 553
 554       if (deref1->deref_type == nir_deref_type_var)
 555          return deref1->var == deref2->var;
 556
 557       if (!nir_srcs_equal(deref1->parent, deref2->parent))
 558          return false;
 559
 560       switch (deref1->deref_type) {
 561       case nir_deref_type_struct:
 562          if (deref1->strct.index != deref2->strct.index)
 563             return false;
 564          break;
 565
 566       case nir_deref_type_array:
 567       case nir_deref_type_ptr_as_array:
 568          if (!nir_srcs_equal(deref1->arr.index, deref2->arr.index))
 569             return false;
 570          break;
 571
 572       case nir_deref_type_cast:
 573          if (deref1->cast.ptr_stride != deref2->cast.ptr_stride)
 574             return false;
 575          break;
 576
 577       case nir_deref_type_var:
 578       case nir_deref_type_array_wildcard:
 579          /* Nothing to do */
 580          break;
 581
 582       default:
 583          unreachable("Invalid instruction deref type");
 584       }
 585       return true;
 586    }
 587    case nir_instr_type_tex: {
 588       nir_tex_instr *tex1 = nir_instr_as_tex(instr1);
 589       nir_tex_instr *tex2 = nir_instr_as_tex(instr2);
 590
 591       if (tex1->op != tex2->op)
 592          return false;
 593
 594       if (tex1->num_srcs != tex2->num_srcs)
 595          return false;
 596       for (unsigned i = 0; i < tex1->num_srcs; i++) {
 597          if (tex1->src[i].src_type != tex2->src[i].src_type ||
 598              !nir_srcs_equal(tex1->src[i].src, tex2->src[i].src)) {
 599             return false;
 600          }
 601       }
 602
 603       if (tex1->coord_components != tex2->coord_components ||
 604           tex1->sampler_dim != tex2->sampler_dim ||
 605           tex1->is_array != tex2->is_array ||
 606           tex1->is_shadow != tex2->is_shadow ||
 607           tex1->is_new_style_shadow != tex2->is_new_style_shadow ||
 608           tex1->component != tex2->component ||
 609          tex1->texture_index != tex2->texture_index ||
 610          tex1->texture_array_size != tex2->texture_array_size ||
 611          tex1->sampler_index != tex2->sampler_index) {
 612          return false;
 613       }
 614
 615       if (memcmp(tex1->tg4_offsets, tex2->tg4_offsets,
 616                  sizeof(tex1->tg4_offsets)))
 617          return false;
 618
 619       return true;
 620    }
 621    case nir_instr_type_load_const: {
 622       nir_load_const_instr *load1 = nir_instr_as_load_const(instr1);
 623       nir_load_const_instr *load2 = nir_instr_as_load_const(instr2);
 624
 625       if (load1->def.num_components != load2->def.num_components)
 626          return false;
 627
 628       if (load1->def.bit_size != load2->def.bit_size)
 629          return false;
 630
 631       if (load1->def.bit_size == 1) {
 632          unsigned size = load1->def.num_components * sizeof(bool);
 633          return memcmp(load1->value.b, load2->value.b, size) == 0;
 634       } else {
 635          unsigned size = load1->def.num_components * (load1->def.bit_size / 8);
 636          return memcmp(load1->value.f32, load2->value.f32, size) == 0;
 637       }
 638    }
 639    case nir_instr_type_phi: {
 640       nir_phi_instr *phi1 = nir_instr_as_phi(instr1);
 641       nir_phi_instr *phi2 = nir_instr_as_phi(instr2);
 642
 643       if (phi1->instr.block != phi2->instr.block)
 644          return false;
 645
 646       nir_foreach_phi_src(src1, phi1) {
 647          nir_foreach_phi_src(src2, phi2) {
 648             if (src1->pred == src2->pred) {
 649                if (!nir_srcs_equal(src1->src, src2->src))
 650                   return false;
 651
 652                break;
 653             }
 654          }
 655       }
 656
 657       return true;
 658    }
 659    case nir_instr_type_intrinsic: {
 660       nir_intrinsic_instr *intrinsic1 = nir_instr_as_intrinsic(instr1);
 661       nir_intrinsic_instr *intrinsic2 = nir_instr_as_intrinsic(instr2);
 662       const nir_intrinsic_info *info =
 663          &nir_intrinsic_infos[intrinsic1->intrinsic];
 664
 665       if (intrinsic1->intrinsic != intrinsic2->intrinsic ||
 666           intrinsic1->num_components != intrinsic2->num_components)
 667          return false;
 668
 669       if (info->has_dest && intrinsic1->dest.ssa.num_components !=
 670                             intrinsic2->dest.ssa.num_components)
 671          return false;
 672
 673       if (info->has_dest && intrinsic1->dest.ssa.bit_size !=
 674                             intrinsic2->dest.ssa.bit_size)
 675          return false;
 676
 677       for (unsigned i = 0; i < info->num_srcs; i++) {
 678          if (!nir_srcs_equal(intrinsic1->src[i], intrinsic2->src[i]))
 679             return false;
 680       }
 681
 682       for (unsigned i = 0; i < info->num_indices; i++) {
 683          if (intrinsic1->const_index[i] != intrinsic2->const_index[i])
 684             return false;
 685       }
 686
 687       return true;
 688    }
 689    case nir_instr_type_call:
 690    case nir_instr_type_jump:
 691    case nir_instr_type_ssa_undef:
 692    case nir_instr_type_parallel_copy:
 693    default:
 694       unreachable("Invalid instruction type");
 695    }
 696
 697    unreachable("All cases in the above switch should return");
 698 }
 699
 700 static bool
 701 src_is_ssa(nir_src *src, void *data)
 702 {
 703    (void) data;
 704    return src->is_ssa;
 705 }
 706
 707 static bool
 708 dest_is_ssa(nir_dest *dest, void *data)
 709 {
 710    (void) data;
 711    return dest->is_ssa;
 712 }
 713
 714 static inline bool
 715 instr_each_src_and_dest_is_ssa(nir_instr *instr)
 716 {
 717    if (!nir_foreach_dest(instr, dest_is_ssa, NULL) ||
 718        !nir_foreach_src(instr, src_is_ssa, NULL))
 719       return false;
 720
 721    return true;
 722 }
 723
 724 /* This function determines if uses of an instruction can safely be rewritten
 725  * to use another identical instruction instead. Note that this function must
 726  * be kept in sync with hash_instr() and nir_instrs_equal() -- only
 727  * instructions that pass this test will be handed on to those functions, and
 728  * conversely they must handle everything that this function returns true for.
 729  */
 730
 731 static bool
 732 instr_can_rewrite(nir_instr *instr)
 733 {
 734    /* We only handle SSA. */
 735    assert(instr_each_src_and_dest_is_ssa(instr));
 736
 737    switch (instr->type) {
 738    case nir_instr_type_alu:
 739    case nir_instr_type_deref:
 740    case nir_instr_type_tex:
 741    case nir_instr_type_load_const:
 742    case nir_instr_type_phi:
 743       return true;
 744    case nir_instr_type_intrinsic: {
 745       const nir_intrinsic_info *info =
 746          &nir_intrinsic_infos[nir_instr_as_intrinsic(instr)->intrinsic];
 747       return (info->flags & NIR_INTRINSIC_CAN_ELIMINATE) &&
 748              (info->flags & NIR_INTRINSIC_CAN_REORDER);
 749    }
 750    case nir_instr_type_call:
 751    case nir_instr_type_jump:
 752    case nir_instr_type_ssa_undef:
 753       return false;
 754    case nir_instr_type_parallel_copy:
 755    default:
 756       unreachable("Invalid instruction type");
 757    }
 758
 759    return false;
 760 }
 761
 762 static nir_ssa_def *
 763 nir_instr_get_dest_ssa_def(nir_instr *instr)
 764 {
 765    switch (instr->type) {
 766    case nir_instr_type_alu:
 767       assert(nir_instr_as_alu(instr)->dest.dest.is_ssa);
 768       return &nir_instr_as_alu(instr)->dest.dest.ssa;
 769    case nir_instr_type_deref:
 770       assert(nir_instr_as_deref(instr)->dest.is_ssa);
 771       return &nir_instr_as_deref(instr)->dest.ssa;
 772    case nir_instr_type_load_const:
 773       return &nir_instr_as_load_const(instr)->def;
 774    case nir_instr_type_phi:
 775       assert(nir_instr_as_phi(instr)->dest.is_ssa);
 776       return &nir_instr_as_phi(instr)->dest.ssa;
 777    case nir_instr_type_intrinsic:
 778       assert(nir_instr_as_intrinsic(instr)->dest.is_ssa);
 779       return &nir_instr_as_intrinsic(instr)->dest.ssa;
 780    case nir_instr_type_tex:
 781       assert(nir_instr_as_tex(instr)->dest.is_ssa);
 782       return &nir_instr_as_tex(instr)->dest.ssa;
 783    default:
 784       unreachable("We never ask for any of these");
 785    }
 786 }
 787
 788 static bool
 789 cmp_func(const void *data1, const void *data2)
 790 {
 791    return nir_instrs_equal(data1, data2);
 792 }
 793
 794 struct set *
 795 nir_instr_set_create(void *mem_ctx)
 796 {
 797    return _mesa_set_create(mem_ctx, hash_instr, cmp_func);
 798 }
 799
 800 void
 801 nir_instr_set_destroy(struct set *instr_set)
 802 {
 803    _mesa_set_destroy(instr_set, NULL);
 804 }
 805
 806 bool
 807 nir_instr_set_add_or_rewrite(struct set *instr_set, nir_instr *instr)
 808 {
 809    if (!instr_can_rewrite(instr))
 810       return false;
 811
 812    uint32_t hash = hash_instr(instr);
 813    struct set_entry *e = _mesa_set_search_pre_hashed(instr_set, hash, instr);
 814    if (e) {
 815       nir_ssa_def *def = nir_instr_get_dest_ssa_def(instr);
 816       nir_instr *match = (nir_instr *) e->key;
 817       nir_ssa_def *new_def = nir_instr_get_dest_ssa_def(match);
 818
 819       /* It's safe to replace an exact instruction with an inexact one as
 820        * long as we make it exact.  If we got here, the two instructions are
 821        * exactly identical in every other way so, once we've set the exact
 822        * bit, they are the same.
 823        */
 824       if (instr->type == nir_instr_type_alu && nir_instr_as_alu(instr)->exact)
 825          nir_instr_as_alu(match)->exact = true;
 826
 827       nir_ssa_def_rewrite_uses(def, nir_src_for_ssa(new_def));
 828       return true;
 829    }
 830
 831    _mesa_set_add_pre_hashed(instr_set, hash, instr);
 832    return false;
 833 }
 834
 835 void
 836 nir_instr_set_remove(struct set *instr_set, nir_instr *instr)
 837 {
 838    if (!instr_can_rewrite(instr))
 839       return;
 840
 841    struct set_entry *entry = _mesa_set_search(instr_set, instr);
 842    if (entry)
 843       _mesa_set_remove(instr_set, entry);
 844 }
 845