src/compiler/nir/nir_deref.c

   1 /*
   2  * Copyright © 2018 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
  24 #include "nir.h"
  25 #include "nir_builder.h"
  26 #include "nir_deref.h"
  27 #include "util/hash_table.h"
  28
  29 static bool
  30 is_trivial_deref_cast(nir_deref_instr *cast)
  31 {
  32    nir_deref_instr *parent = nir_src_as_deref(cast->parent);
  33    if (!parent)
  34       return false;
  35
  36    return cast->mode == parent->mode &&
  37           cast->type == parent->type &&
  38           cast->dest.ssa.num_components == parent->dest.ssa.num_components &&
  39           cast->dest.ssa.bit_size == parent->dest.ssa.bit_size;
  40 }
  41
  42 void
  43 nir_deref_path_init(nir_deref_path *path,
  44                     nir_deref_instr *deref, void *mem_ctx)
  45 {
  46    assert(deref != NULL);
  47
  48    /* The length of the short path is at most ARRAY_SIZE - 1 because we need
  49     * room for the NULL terminator.
  50     */
  51    static const int max_short_path_len = ARRAY_SIZE(path->_short_path) - 1;
  52
  53    int count = 0;
  54
  55    nir_deref_instr **tail = &path->_short_path[max_short_path_len];
  56    nir_deref_instr **head = tail;
  57
  58    *tail = NULL;
  59    for (nir_deref_instr *d = deref; d; d = nir_deref_instr_parent(d)) {
  60       if (d->deref_type == nir_deref_type_cast && is_trivial_deref_cast(d))
  61          continue;
  62       count++;
  63       if (count <= max_short_path_len)
  64          *(--head) = d;
  65    }
  66
  67    if (count <= max_short_path_len) {
  68       /* If we're under max_short_path_len, just use the short path. */
  69       path->path = head;
  70       goto done;
  71    }
  72
  73 #ifndef NDEBUG
  74    /* Just in case someone uses short_path by accident */
  75    for (unsigned i = 0; i < ARRAY_SIZE(path->_short_path); i++)
  76       path->_short_path[i] = (void *)(uintptr_t)0xdeadbeef;
  77 #endif
  78
  79    path->path = ralloc_array(mem_ctx, nir_deref_instr *, count + 1);
  80    head = tail = path->path + count;
  81    *tail = NULL;
  82    for (nir_deref_instr *d = deref; d; d = nir_deref_instr_parent(d)) {
  83       if (d->deref_type == nir_deref_type_cast && is_trivial_deref_cast(d))
  84          continue;
  85       *(--head) = d;
  86    }
  87
  88 done:
  89    assert(head == path->path);
  90    assert(tail == head + count);
  91    assert(*tail == NULL);
  92 }
  93
  94 void
  95 nir_deref_path_finish(nir_deref_path *path)
  96 {
  97    if (path->path < &path->_short_path[0] ||
  98        path->path > &path->_short_path[ARRAY_SIZE(path->_short_path) - 1])
  99       ralloc_free(path->path);
 100 }
 101
 102 /**
 103  * Recursively removes unused deref instructions
 104  */
 105 bool
 106 nir_deref_instr_remove_if_unused(nir_deref_instr *instr)
 107 {
 108    bool progress = false;
 109
 110    for (nir_deref_instr *d = instr; d; d = nir_deref_instr_parent(d)) {
 111       /* If anyone is using this deref, leave it alone */
 112       assert(d->dest.is_ssa);
 113       if (!list_is_empty(&d->dest.ssa.uses))
 114          break;
 115
 116       nir_instr_remove(&d->instr);
 117       progress = true;
 118    }
 119
 120    return progress;
 121 }
 122
 123 bool
 124 nir_deref_instr_has_indirect(nir_deref_instr *instr)
 125 {
 126    while (instr->deref_type != nir_deref_type_var) {
 127       /* Consider casts to be indirects */
 128       if (instr->deref_type == nir_deref_type_cast)
 129          return true;
 130
 131       if ((instr->deref_type == nir_deref_type_array ||
 132            instr->deref_type == nir_deref_type_ptr_as_array) &&
 133           !nir_src_is_const(instr->arr.index))
 134          return true;
 135
 136       instr = nir_deref_instr_parent(instr);
 137    }
 138
 139    return false;
 140 }
 141
 142 bool
 143 nir_deref_instr_is_known_out_of_bounds(nir_deref_instr *instr)
 144 {
 145    for (; instr; instr = nir_deref_instr_parent(instr)) {
 146       if (instr->deref_type == nir_deref_type_array &&
 147           nir_src_is_const(instr->arr.index) &&
 148            nir_src_as_uint(instr->arr.index) >=
 149            glsl_get_length(nir_deref_instr_parent(instr)->type))
 150          return true;
 151    }
 152
 153    return false;
 154 }
 155
 156 bool
 157 nir_deref_instr_has_complex_use(nir_deref_instr *deref)
 158 {
 159    nir_foreach_use(use_src, &deref->dest.ssa) {
 160       nir_instr *use_instr = use_src->parent_instr;
 161
 162       switch (use_instr->type) {
 163       case nir_instr_type_deref: {
 164          nir_deref_instr *use_deref = nir_instr_as_deref(use_instr);
 165
 166          /* A var deref has no sources */
 167          assert(use_deref->deref_type != nir_deref_type_var);
 168
 169          /* If a deref shows up in an array index or something like that, it's
 170           * a complex use.
 171           */
 172          if (use_src != &use_deref->parent)
 173             return true;
 174
 175          /* Anything that isn't a basic struct or array deref is considered to
 176           * be a "complex" use.  In particular, we don't allow ptr_as_array
 177           * because we assume that opt_deref will turn any non-complex
 178           * ptr_as_array derefs into regular array derefs eventually so passes
 179           * which only want to handle simple derefs will pick them up in a
 180           * later pass.
 181           */
 182          if (use_deref->deref_type != nir_deref_type_struct &&
 183              use_deref->deref_type != nir_deref_type_array_wildcard &&
 184              use_deref->deref_type != nir_deref_type_array)
 185             return true;
 186
 187          if (nir_deref_instr_has_complex_use(use_deref))
 188             return true;
 189
 190          continue;
 191       }
 192
 193       case nir_instr_type_intrinsic: {
 194          nir_intrinsic_instr *use_intrin = nir_instr_as_intrinsic(use_instr);
 195          switch (use_intrin->intrinsic) {
 196          case nir_intrinsic_load_deref:
 197             assert(use_src == &use_intrin->src[0]);
 198             continue;
 199
 200          case nir_intrinsic_copy_deref:
 201             assert(use_src == &use_intrin->src[0] ||
 202                    use_src == &use_intrin->src[1]);
 203             continue;
 204
 205          case nir_intrinsic_store_deref:
 206             /* A use in src[1] of a store means we're taking that pointer and
 207              * writing it to a variable.  Because we have no idea who will
 208              * read that variable and what they will do with the pointer, it's
 209              * considered a "complex" use.  A use in src[0], on the other
 210              * hand, is a simple use because we're just going to dereference
 211              * it and write a value there.
 212              */
 213             if (use_src == &use_intrin->src[0])
 214                continue;
 215             return true;
 216
 217          default:
 218             return true;
 219          }
 220          unreachable("Switch default failed");
 221       }
 222
 223       default:
 224          return true;
 225       }
 226    }
 227
 228    nir_foreach_if_use(use, &deref->dest.ssa)
 229       return true;
 230
 231    return false;
 232 }
 233
 234 unsigned
 235 nir_deref_instr_ptr_as_array_stride(nir_deref_instr *deref)
 236 {
 237    switch (deref->deref_type) {
 238    case nir_deref_type_array:
 239       return glsl_get_explicit_stride(nir_deref_instr_parent(deref)->type);
 240    case nir_deref_type_ptr_as_array:
 241       return nir_deref_instr_ptr_as_array_stride(nir_deref_instr_parent(deref));
 242    case nir_deref_type_cast:
 243       return deref->cast.ptr_stride;
 244    default:
 245       return 0;
 246    }
 247 }
 248
 249 static unsigned
 250 type_get_array_stride(const struct glsl_type *elem_type,
 251                       glsl_type_size_align_func size_align)
 252 {
 253    unsigned elem_size, elem_align;
 254    size_align(elem_type, &elem_size, &elem_align);
 255    return ALIGN_POT(elem_size, elem_align);
 256 }
 257
 258 static unsigned
 259 struct_type_get_field_offset(const struct glsl_type *struct_type,
 260                              glsl_type_size_align_func size_align,
 261                              unsigned field_idx)
 262 {
 263    assert(glsl_type_is_struct_or_ifc(struct_type));
 264    unsigned offset = 0;
 265    for (unsigned i = 0; i <= field_idx; i++) {
 266       unsigned elem_size, elem_align;
 267       size_align(glsl_get_struct_field(struct_type, i), &elem_size, &elem_align);
 268       offset = ALIGN_POT(offset, elem_align);
 269       if (i < field_idx)
 270          offset += elem_size;
 271    }
 272    return offset;
 273 }
 274
 275 unsigned
 276 nir_deref_instr_get_const_offset(nir_deref_instr *deref,
 277                                  glsl_type_size_align_func size_align)
 278 {
 279    nir_deref_path path;
 280    nir_deref_path_init(&path, deref, NULL);
 281
 282    assert(path.path[0]->deref_type == nir_deref_type_var);
 283
 284    unsigned offset = 0;
 285    for (nir_deref_instr **p = &path.path[1]; *p; p++) {
 286       if ((*p)->deref_type == nir_deref_type_array) {
 287          offset += nir_src_as_uint((*p)->arr.index) *
 288                    type_get_array_stride((*p)->type, size_align);
 289       } else if ((*p)->deref_type == nir_deref_type_struct) {
 290          /* p starts at path[1], so this is safe */
 291          nir_deref_instr *parent = *(p - 1);
 292          offset += struct_type_get_field_offset(parent->type, size_align,
 293                                                 (*p)->strct.index);
 294       } else {
 295          unreachable("Unsupported deref type");
 296       }
 297    }
 298
 299    nir_deref_path_finish(&path);
 300
 301    return offset;
 302 }
 303
 304 nir_ssa_def *
 305 nir_build_deref_offset(nir_builder *b, nir_deref_instr *deref,
 306                        glsl_type_size_align_func size_align)
 307 {
 308    nir_deref_path path;
 309    nir_deref_path_init(&path, deref, NULL);
 310
 311    assert(path.path[0]->deref_type == nir_deref_type_var);
 312
 313    nir_ssa_def *offset = nir_imm_intN_t(b, 0, deref->dest.ssa.bit_size);
 314    for (nir_deref_instr **p = &path.path[1]; *p; p++) {
 315       if ((*p)->deref_type == nir_deref_type_array) {
 316          nir_ssa_def *index = nir_ssa_for_src(b, (*p)->arr.index, 1);
 317          int stride = type_get_array_stride((*p)->type, size_align);
 318          offset = nir_iadd(b, offset, nir_amul_imm(b, index, stride));
 319       } else if ((*p)->deref_type == nir_deref_type_struct) {
 320          /* p starts at path[1], so this is safe */
 321          nir_deref_instr *parent = *(p - 1);
 322          unsigned field_offset =
 323             struct_type_get_field_offset(parent->type, size_align,
 324                                          (*p)->strct.index);
 325          offset = nir_iadd_imm(b, offset, field_offset);
 326       } else {
 327          unreachable("Unsupported deref type");
 328       }
 329    }
 330
 331    nir_deref_path_finish(&path);
 332
 333    return offset;
 334 }
 335
 336 bool
 337 nir_remove_dead_derefs_impl(nir_function_impl *impl)
 338 {
 339    bool progress = false;
 340
 341    nir_foreach_block(block, impl) {
 342       nir_foreach_instr_safe(instr, block) {
 343          if (instr->type == nir_instr_type_deref &&
 344              nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr)))
 345             progress = true;
 346       }
 347    }
 348
 349    if (progress)
 350       nir_metadata_preserve(impl, nir_metadata_block_index |
 351                                   nir_metadata_dominance);
 352
 353    return progress;
 354 }
 355
 356 bool
 357 nir_remove_dead_derefs(nir_shader *shader)
 358 {
 359    bool progress = false;
 360    nir_foreach_function(function, shader) {
 361       if (function->impl && nir_remove_dead_derefs_impl(function->impl))
 362          progress = true;
 363    }
 364
 365    return progress;
 366 }
 367
 368 void
 369 nir_fixup_deref_modes(nir_shader *shader)
 370 {
 371    nir_foreach_function(function, shader) {
 372       if (!function->impl)
 373          continue;
 374
 375       nir_foreach_block(block, function->impl) {
 376          nir_foreach_instr(instr, block) {
 377             if (instr->type != nir_instr_type_deref)
 378                continue;
 379
 380             nir_deref_instr *deref = nir_instr_as_deref(instr);
 381             if (deref->deref_type == nir_deref_type_cast)
 382                continue;
 383
 384             nir_variable_mode parent_mode;
 385             if (deref->deref_type == nir_deref_type_var) {
 386                parent_mode = deref->var->data.mode;
 387             } else {
 388                assert(deref->parent.is_ssa);
 389                nir_deref_instr *parent =
 390                   nir_instr_as_deref(deref->parent.ssa->parent_instr);
 391                parent_mode = parent->mode;
 392             }
 393
 394             deref->mode = parent_mode;
 395          }
 396       }
 397    }
 398 }
 399
 400 static bool
 401 modes_may_alias(nir_variable_mode a, nir_variable_mode b)
 402 {
 403    /* Generic pointers can alias with SSBOs */
 404    if ((a == nir_var_mem_ssbo || a == nir_var_mem_global) &&
 405        (b == nir_var_mem_ssbo || b == nir_var_mem_global))
 406       return true;
 407
 408    /* In the general case, pointers can only alias if they have the same mode.
 409     *
 410     * NOTE: In future, with things like OpenCL generic pointers, this may not
 411     * be true and will have to be re-evaluated.  However, with graphics only,
 412     * it should be safe.
 413     */
 414    return a == b;
 415 }
 416
 417 static bool
 418 deref_path_contains_coherent_decoration(nir_deref_path *path)
 419 {
 420    assert(path->path[0]->deref_type == nir_deref_type_var);
 421
 422    if (path->path[0]->var->data.access & ACCESS_COHERENT)
 423       return true;
 424
 425    for (nir_deref_instr **p = &path->path[1]; *p; p++) {
 426       if ((*p)->deref_type != nir_deref_type_struct)
 427          continue;
 428
 429       const struct glsl_type *struct_type = (*(p - 1))->type;
 430       const struct glsl_struct_field *field =
 431          glsl_get_struct_field_data(struct_type, (*p)->strct.index);
 432       if (field->memory_coherent)
 433          return true;
 434    }
 435
 436    return false;
 437 }
 438
 439 nir_deref_compare_result
 440 nir_compare_deref_paths(nir_deref_path *a_path,
 441                         nir_deref_path *b_path)
 442 {
 443    if (!modes_may_alias(b_path->path[0]->mode, a_path->path[0]->mode))
 444       return nir_derefs_do_not_alias;
 445
 446    if (a_path->path[0]->deref_type != b_path->path[0]->deref_type)
 447       return nir_derefs_may_alias_bit;
 448
 449    if (a_path->path[0]->deref_type == nir_deref_type_var) {
 450       if (a_path->path[0]->var != b_path->path[0]->var) {
 451          /* Shader and function temporaries aren't backed by memory so two
 452           * distinct variables never alias.
 453           */
 454          static const nir_variable_mode temp_var_modes =
 455             nir_var_shader_temp | nir_var_function_temp;
 456          if ((a_path->path[0]->mode & temp_var_modes) ||
 457              (b_path->path[0]->mode & temp_var_modes))
 458             return nir_derefs_do_not_alias;
 459
 460          /* If they are both declared coherent or have coherent somewhere in
 461           * their path (due to a member of an interface being declared
 462           * coherent), we have to assume we that we could have any kind of
 463           * aliasing.  Otherwise, they could still alias but the client didn't
 464           * tell us and that's their fault.
 465           */
 466          if (deref_path_contains_coherent_decoration(a_path) &&
 467              deref_path_contains_coherent_decoration(b_path))
 468             return nir_derefs_may_alias_bit;
 469
 470          /* If we can chase the deref all the way back to the variable and
 471           * they're not the same variable and at least one is not declared
 472           * coherent, we know they can't possibly alias.
 473           */
 474          return nir_derefs_do_not_alias;
 475       }
 476    } else {
 477       assert(a_path->path[0]->deref_type == nir_deref_type_cast);
 478       /* If they're not exactly the same cast, it's hard to compare them so we
 479        * just assume they alias.  Comparing casts is tricky as there are lots
 480        * of things such as mode, type, etc. to make sure work out; for now, we
 481        * just assume nit_opt_deref will combine them and compare the deref
 482        * instructions.
 483        *
 484        * TODO: At some point in the future, we could be clever and understand
 485        * that a float[] and int[] have the same layout and aliasing structure
 486        * but double[] and vec3[] do not and we could potentially be a bit
 487        * smarter here.
 488        */
 489       if (a_path->path[0] != b_path->path[0])
 490          return nir_derefs_may_alias_bit;
 491    }
 492
 493    /* Start off assuming they fully compare.  We ignore equality for now.  In
 494     * the end, we'll determine that by containment.
 495     */
 496    nir_deref_compare_result result = nir_derefs_may_alias_bit |
 497                                      nir_derefs_a_contains_b_bit |
 498                                      nir_derefs_b_contains_a_bit;
 499
 500    nir_deref_instr **a_p = &a_path->path[1];
 501    nir_deref_instr **b_p = &b_path->path[1];
 502    while (*a_p != NULL && *a_p == *b_p) {
 503       a_p++;
 504       b_p++;
 505    }
 506
 507    /* We're at either the tail or the divergence point between the two deref
 508     * paths.  Look to see if either contains a ptr_as_array deref.  It it
 509     * does we don't know how to safely make any inferences.  Hopefully,
 510     * nir_opt_deref will clean most of these up and we can start inferring
 511     * things again.
 512     *
 513     * In theory, we could do a bit better.  For instance, we could detect the
 514     * case where we have exactly one ptr_as_array deref in the chain after the
 515     * divergence point and it's matched in both chains and the two chains have
 516     * different constant indices.
 517     */
 518    for (nir_deref_instr **t_p = a_p; *t_p; t_p++) {
 519       if ((*t_p)->deref_type == nir_deref_type_ptr_as_array)
 520          return nir_derefs_may_alias_bit;
 521    }
 522    for (nir_deref_instr **t_p = b_p; *t_p; t_p++) {
 523       if ((*t_p)->deref_type == nir_deref_type_ptr_as_array)
 524          return nir_derefs_may_alias_bit;
 525    }
 526
 527    while (*a_p != NULL && *b_p != NULL) {
 528       nir_deref_instr *a_tail = *(a_p++);
 529       nir_deref_instr *b_tail = *(b_p++);
 530
 531       switch (a_tail->deref_type) {
 532       case nir_deref_type_array:
 533       case nir_deref_type_array_wildcard: {
 534          assert(b_tail->deref_type == nir_deref_type_array ||
 535                 b_tail->deref_type == nir_deref_type_array_wildcard);
 536
 537          if (a_tail->deref_type == nir_deref_type_array_wildcard) {
 538             if (b_tail->deref_type != nir_deref_type_array_wildcard)
 539                result &= ~nir_derefs_b_contains_a_bit;
 540          } else if (b_tail->deref_type == nir_deref_type_array_wildcard) {
 541             if (a_tail->deref_type != nir_deref_type_array_wildcard)
 542                result &= ~nir_derefs_a_contains_b_bit;
 543          } else {
 544             assert(a_tail->deref_type == nir_deref_type_array &&
 545                    b_tail->deref_type == nir_deref_type_array);
 546             assert(a_tail->arr.index.is_ssa && b_tail->arr.index.is_ssa);
 547
 548             if (nir_src_is_const(a_tail->arr.index) &&
 549                 nir_src_is_const(b_tail->arr.index)) {
 550                /* If they're both direct and have different offsets, they
 551                 * don't even alias much less anything else.
 552                 */
 553                if (nir_src_as_uint(a_tail->arr.index) !=
 554                    nir_src_as_uint(b_tail->arr.index))
 555                   return nir_derefs_do_not_alias;
 556             } else if (a_tail->arr.index.ssa == b_tail->arr.index.ssa) {
 557                /* They're the same indirect, continue on */
 558             } else {
 559                /* They're not the same index so we can't prove anything about
 560                 * containment.
 561                 */
 562                result &= ~(nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit);
 563             }
 564          }
 565          break;
 566       }
 567
 568       case nir_deref_type_struct: {
 569          /* If they're different struct members, they don't even alias */
 570          if (a_tail->strct.index != b_tail->strct.index)
 571             return nir_derefs_do_not_alias;
 572          break;
 573       }
 574
 575       default:
 576          unreachable("Invalid deref type");
 577       }
 578    }
 579
 580    /* If a is longer than b, then it can't contain b */
 581    if (*a_p != NULL)
 582       result &= ~nir_derefs_a_contains_b_bit;
 583    if (*b_p != NULL)
 584       result &= ~nir_derefs_b_contains_a_bit;
 585
 586    /* If a contains b and b contains a they must be equal. */
 587    if ((result & nir_derefs_a_contains_b_bit) && (result & nir_derefs_b_contains_a_bit))
 588       result |= nir_derefs_equal_bit;
 589
 590    return result;
 591 }
 592
 593 nir_deref_compare_result
 594 nir_compare_derefs(nir_deref_instr *a, nir_deref_instr *b)
 595 {
 596    if (a == b) {
 597       return nir_derefs_equal_bit | nir_derefs_may_alias_bit |
 598              nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit;
 599    }
 600
 601    nir_deref_path a_path, b_path;
 602    nir_deref_path_init(&a_path, a, NULL);
 603    nir_deref_path_init(&b_path, b, NULL);
 604    assert(a_path.path[0]->deref_type == nir_deref_type_var ||
 605           a_path.path[0]->deref_type == nir_deref_type_cast);
 606    assert(b_path.path[0]->deref_type == nir_deref_type_var ||
 607           b_path.path[0]->deref_type == nir_deref_type_cast);
 608
 609    nir_deref_compare_result result = nir_compare_deref_paths(&a_path, &b_path);
 610
 611    nir_deref_path_finish(&a_path);
 612    nir_deref_path_finish(&b_path);
 613
 614    return result;
 615 }
 616
 617 struct rematerialize_deref_state {
 618    bool progress;
 619    nir_builder builder;
 620    nir_block *block;
 621    struct hash_table *cache;
 622 };
 623
 624 static nir_deref_instr *
 625 rematerialize_deref_in_block(nir_deref_instr *deref,
 626                              struct rematerialize_deref_state *state)
 627 {
 628    if (deref->instr.block == state->block)
 629       return deref;
 630
 631    if (!state->cache) {
 632       state->cache = _mesa_pointer_hash_table_create(NULL);
 633    }
 634
 635    struct hash_entry *cached = _mesa_hash_table_search(state->cache, deref);
 636    if (cached)
 637       return cached->data;
 638
 639    nir_builder *b = &state->builder;
 640    nir_deref_instr *new_deref =
 641       nir_deref_instr_create(b->shader, deref->deref_type);
 642    new_deref->mode = deref->mode;
 643    new_deref->type = deref->type;
 644
 645    if (deref->deref_type == nir_deref_type_var) {
 646       new_deref->var = deref->var;
 647    } else {
 648       nir_deref_instr *parent = nir_src_as_deref(deref->parent);
 649       if (parent) {
 650          parent = rematerialize_deref_in_block(parent, state);
 651          new_deref->parent = nir_src_for_ssa(&parent->dest.ssa);
 652       } else {
 653          nir_src_copy(&new_deref->parent, &deref->parent, new_deref);
 654       }
 655    }
 656
 657    switch (deref->deref_type) {
 658    case nir_deref_type_var:
 659    case nir_deref_type_array_wildcard:
 660       /* Nothing more to do */
 661       break;
 662
 663    case nir_deref_type_cast:
 664       new_deref->cast.ptr_stride = deref->cast.ptr_stride;
 665       break;
 666
 667    case nir_deref_type_array:
 668    case nir_deref_type_ptr_as_array:
 669       assert(!nir_src_as_deref(deref->arr.index));
 670       nir_src_copy(&new_deref->arr.index, &deref->arr.index, new_deref);
 671       break;
 672
 673    case nir_deref_type_struct:
 674       new_deref->strct.index = deref->strct.index;
 675       break;
 676
 677    default:
 678       unreachable("Invalid deref instruction type");
 679    }
 680
 681    nir_ssa_dest_init(&new_deref->instr, &new_deref->dest,
 682                      deref->dest.ssa.num_components,
 683                      deref->dest.ssa.bit_size,
 684                      deref->dest.ssa.name);
 685    nir_builder_instr_insert(b, &new_deref->instr);
 686
 687    return new_deref;
 688 }
 689
 690 static bool
 691 rematerialize_deref_src(nir_src *src, void *_state)
 692 {
 693    struct rematerialize_deref_state *state = _state;
 694
 695    nir_deref_instr *deref = nir_src_as_deref(*src);
 696    if (!deref)
 697       return true;
 698
 699    nir_deref_instr *block_deref = rematerialize_deref_in_block(deref, state);
 700    if (block_deref != deref) {
 701       nir_instr_rewrite_src(src->parent_instr, src,
 702                             nir_src_for_ssa(&block_deref->dest.ssa));
 703       nir_deref_instr_remove_if_unused(deref);
 704       state->progress = true;
 705    }
 706
 707    return true;
 708 }
 709
 710 /** Re-materialize derefs in every block
 711  *
 712  * This pass re-materializes deref instructions in every block in which it is
 713  * used.  After this pass has been run, every use of a deref will be of a
 714  * deref in the same block as the use.  Also, all unused derefs will be
 715  * deleted as a side-effect.
 716  *
 717  * Derefs used as sources of phi instructions are not rematerialized.
 718  */
 719 bool
 720 nir_rematerialize_derefs_in_use_blocks_impl(nir_function_impl *impl)
 721 {
 722    struct rematerialize_deref_state state = { 0 };
 723    nir_builder_init(&state.builder, impl);
 724
 725    nir_foreach_block(block, impl) {
 726       state.block = block;
 727
 728       /* Start each block with a fresh cache */
 729       if (state.cache)
 730          _mesa_hash_table_clear(state.cache, NULL);
 731
 732       nir_foreach_instr_safe(instr, block) {
 733          if (instr->type == nir_instr_type_deref &&
 734              nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr)))
 735             continue;
 736
 737          /* If a deref is used in a phi, we can't rematerialize it, as the new
 738           * derefs would appear before the phi, which is not valid.
 739           */
 740          if (instr->type == nir_instr_type_phi)
 741             continue;
 742
 743          state.builder.cursor = nir_before_instr(instr);
 744          nir_foreach_src(instr, rematerialize_deref_src, &state);
 745       }
 746
 747 #ifndef NDEBUG
 748       nir_if *following_if = nir_block_get_following_if(block);
 749       if (following_if)
 750          assert(!nir_src_as_deref(following_if->condition));
 751 #endif
 752    }
 753
 754    _mesa_hash_table_destroy(state.cache, NULL);
 755
 756    return state.progress;
 757 }
 758
 759 static void
 760 nir_deref_instr_fixup_child_types(nir_deref_instr *parent)
 761 {
 762    nir_foreach_use(use, &parent->dest.ssa) {
 763       if (use->parent_instr->type != nir_instr_type_deref)
 764          continue;
 765
 766       nir_deref_instr *child = nir_instr_as_deref(use->parent_instr);
 767       switch (child->deref_type) {
 768       case nir_deref_type_var:
 769          unreachable("nir_deref_type_var cannot be a child");
 770
 771       case nir_deref_type_array:
 772       case nir_deref_type_array_wildcard:
 773          child->type = glsl_get_array_element(parent->type);
 774          break;
 775
 776       case nir_deref_type_ptr_as_array:
 777          child->type = parent->type;
 778          break;
 779
 780       case nir_deref_type_struct:
 781          child->type = glsl_get_struct_field(parent->type,
 782                                              child->strct.index);
 783          break;
 784
 785       case nir_deref_type_cast:
 786          /* We stop the recursion here */
 787          continue;
 788       }
 789
 790       /* Recurse into children */
 791       nir_deref_instr_fixup_child_types(child);
 792    }
 793 }
 794
 795 static bool
 796 is_trivial_array_deref_cast(nir_deref_instr *cast)
 797 {
 798    assert(is_trivial_deref_cast(cast));
 799
 800    nir_deref_instr *parent = nir_src_as_deref(cast->parent);
 801
 802    if (parent->deref_type == nir_deref_type_array) {
 803       return cast->cast.ptr_stride ==
 804              glsl_get_explicit_stride(nir_deref_instr_parent(parent)->type);
 805    } else if (parent->deref_type == nir_deref_type_ptr_as_array) {
 806       return cast->cast.ptr_stride ==
 807              nir_deref_instr_ptr_as_array_stride(parent);
 808    } else {
 809       return false;
 810    }
 811 }
 812
 813 static bool
 814 is_deref_ptr_as_array(nir_instr *instr)
 815 {
 816    return instr->type == nir_instr_type_deref &&
 817           nir_instr_as_deref(instr)->deref_type == nir_deref_type_ptr_as_array;
 818 }
 819
 820 /**
 821  * Remove casts that just wrap other casts.
 822  */
 823 static bool
 824 opt_remove_cast_cast(nir_deref_instr *cast)
 825 {
 826    nir_deref_instr *first_cast = cast;
 827
 828    while (true) {
 829       nir_deref_instr *parent = nir_deref_instr_parent(first_cast);
 830       if (parent == NULL || parent->deref_type != nir_deref_type_cast)
 831          break;
 832       first_cast = parent;
 833    }
 834    if (cast == first_cast)
 835       return false;
 836
 837    nir_instr_rewrite_src(&cast->instr, &cast->parent,
 838                          nir_src_for_ssa(first_cast->parent.ssa));
 839    return true;
 840 }
 841
 842 static bool
 843 opt_remove_sampler_cast(nir_deref_instr *cast)
 844 {
 845    assert(cast->deref_type == nir_deref_type_cast);
 846    nir_deref_instr *parent = nir_src_as_deref(cast->parent);
 847    if (parent == NULL)
 848       return false;
 849
 850    /* Strip both types down to their non-array type and bail if there are any
 851     * discrepancies in array lengths.
 852     */
 853    const struct glsl_type *parent_type = parent->type;
 854    const struct glsl_type *cast_type = cast->type;
 855    while (glsl_type_is_array(parent_type) && glsl_type_is_array(cast_type)) {
 856       if (glsl_get_length(parent_type) != glsl_get_length(cast_type))
 857          return false;
 858       parent_type = glsl_get_array_element(parent_type);
 859       cast_type = glsl_get_array_element(cast_type);
 860    }
 861
 862    if (glsl_type_is_array(parent_type) || glsl_type_is_array(cast_type))
 863       return false;
 864
 865    if (!glsl_type_is_sampler(parent_type) ||
 866        cast_type != glsl_bare_sampler_type())
 867       return false;
 868
 869    /* We're a cast from a more detailed sampler type to a bare sampler */
 870    nir_ssa_def_rewrite_uses(&cast->dest.ssa,
 871                             nir_src_for_ssa(&parent->dest.ssa));
 872    nir_instr_remove(&cast->instr);
 873
 874    /* Recursively crawl the deref tree and clean up types */
 875    nir_deref_instr_fixup_child_types(parent);
 876
 877    return true;
 878 }
 879
 880 /**
 881  * Is this casting a struct to a contained struct.
 882  * struct a { struct b field0 };
 883  * ssa_5 is structa;
 884  * deref_cast (structb *)ssa_5 (function_temp structb);
 885  * converts to
 886  * deref_struct &ssa_5->field0 (function_temp structb);
 887  * This allows subsequent copy propagation to work.
 888  */
 889 static bool
 890 opt_replace_struct_wrapper_cast(nir_builder *b, nir_deref_instr *cast)
 891 {
 892    nir_deref_instr *parent = nir_src_as_deref(cast->parent);
 893    if (!parent)
 894       return false;
 895
 896    if (!glsl_type_is_struct(parent->type))
 897       return false;
 898
 899    if (glsl_get_struct_field_offset(parent->type, 0) != 0)
 900       return false;
 901
 902    if (cast->type != glsl_get_struct_field(parent->type, 0))
 903       return false;
 904
 905    nir_deref_instr *replace = nir_build_deref_struct(b, parent, 0);
 906    nir_ssa_def_rewrite_uses(&cast->dest.ssa, nir_src_for_ssa(&replace->dest.ssa));
 907    nir_deref_instr_remove_if_unused(cast);
 908    return true;
 909 }
 910
 911 static bool
 912 opt_deref_cast(nir_builder *b, nir_deref_instr *cast)
 913 {
 914    bool progress;
 915
 916    if (opt_replace_struct_wrapper_cast(b, cast))
 917       return true;
 918
 919    if (opt_remove_sampler_cast(cast))
 920       return true;
 921
 922    progress = opt_remove_cast_cast(cast);
 923    if (!is_trivial_deref_cast(cast))
 924       return progress;
 925
 926    bool trivial_array_cast = is_trivial_array_deref_cast(cast);
 927
 928    assert(cast->dest.is_ssa);
 929    assert(cast->parent.is_ssa);
 930
 931    nir_foreach_use_safe(use_src, &cast->dest.ssa) {
 932       /* If this isn't a trivial array cast, we can't propagate into
 933        * ptr_as_array derefs.
 934        */
 935       if (is_deref_ptr_as_array(use_src->parent_instr) &&
 936           !trivial_array_cast)
 937          continue;
 938
 939       nir_instr_rewrite_src(use_src->parent_instr, use_src, cast->parent);
 940       progress = true;
 941    }
 942
 943    /* If uses would be a bit crazy */
 944    assert(list_is_empty(&cast->dest.ssa.if_uses));
 945
 946    if (nir_deref_instr_remove_if_unused(cast))
 947       progress = true;
 948
 949    return progress;
 950 }
 951
 952 static bool
 953 opt_deref_ptr_as_array(nir_builder *b, nir_deref_instr *deref)
 954 {
 955    assert(deref->deref_type == nir_deref_type_ptr_as_array);
 956
 957    nir_deref_instr *parent = nir_deref_instr_parent(deref);
 958
 959    if (nir_src_is_const(deref->arr.index) &&
 960        nir_src_as_int(deref->arr.index) == 0) {
 961       /* If it's a ptr_as_array deref with an index of 0, it does nothing
 962        * and we can just replace its uses with its parent.
 963        *
 964        * The source of a ptr_as_array deref always has a deref_type of
 965        * nir_deref_type_array or nir_deref_type_cast.  If it's a cast, it
 966        * may be trivial and we may be able to get rid of that too.  Any
 967        * trivial cast of trivial cast cases should be handled already by
 968        * opt_deref_cast() above.
 969        */
 970       if (parent->deref_type == nir_deref_type_cast &&
 971           is_trivial_deref_cast(parent))
 972          parent = nir_deref_instr_parent(parent);
 973       nir_ssa_def_rewrite_uses(&deref->dest.ssa,
 974                                nir_src_for_ssa(&parent->dest.ssa));
 975       nir_instr_remove(&deref->instr);
 976       return true;
 977    }
 978
 979    if (parent->deref_type != nir_deref_type_array &&
 980        parent->deref_type != nir_deref_type_ptr_as_array)
 981       return false;
 982
 983    assert(parent->parent.is_ssa);
 984    assert(parent->arr.index.is_ssa);
 985    assert(deref->arr.index.is_ssa);
 986
 987    nir_ssa_def *new_idx = nir_iadd(b, parent->arr.index.ssa,
 988                                       deref->arr.index.ssa);
 989
 990    deref->deref_type = parent->deref_type;
 991    nir_instr_rewrite_src(&deref->instr, &deref->parent, parent->parent);
 992    nir_instr_rewrite_src(&deref->instr, &deref->arr.index,
 993                          nir_src_for_ssa(new_idx));
 994    return true;
 995 }
 996
 997 bool
 998 nir_opt_deref_impl(nir_function_impl *impl)
 999 {
1000    bool progress = false;
1001
1002    nir_builder b;
1003    nir_builder_init(&b, impl);
1004
1005    nir_foreach_block(block, impl) {
1006       nir_foreach_instr_safe(instr, block) {
1007          if (instr->type != nir_instr_type_deref)
1008             continue;
1009
1010          b.cursor = nir_before_instr(instr);
1011
1012          nir_deref_instr *deref = nir_instr_as_deref(instr);
1013          switch (deref->deref_type) {
1014          case nir_deref_type_ptr_as_array:
1015             if (opt_deref_ptr_as_array(&b, deref))
1016                progress = true;
1017             break;
1018
1019          case nir_deref_type_cast:
1020             if (opt_deref_cast(&b, deref))
1021                progress = true;
1022             break;
1023
1024          default:
1025             /* Do nothing */
1026             break;
1027          }
1028       }
1029    }
1030
1031    if (progress) {
1032       nir_metadata_preserve(impl, nir_metadata_block_index |
1033                                   nir_metadata_dominance);
1034    } else {
1035       nir_metadata_preserve(impl, nir_metadata_all);
1036    }
1037
1038    return progress;
1039 }
1040
1041 bool
1042 nir_opt_deref(nir_shader *shader)
1043 {
1044    bool progress = false;
1045
1046    nir_foreach_function(func, shader) {
1047       if (func->impl && nir_opt_deref_impl(func->impl))
1048          progress = true;
1049    }
1050
1051    return progress;
1052 }