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