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