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