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 unsigned
 125 nir_deref_instr_ptr_as_array_stride(nir_deref_instr *deref)
 126 {
 127    assert(deref->deref_type == nir_deref_type_ptr_as_array);
 128    nir_deref_instr *parent = nir_deref_instr_parent(deref);
 129    switch (parent->deref_type) {
 130    case nir_deref_type_array:
 131       return glsl_get_explicit_stride(nir_deref_instr_parent(parent)->type);
 132    case nir_deref_type_ptr_as_array:
 133       return nir_deref_instr_ptr_as_array_stride(parent);
 134    case nir_deref_type_cast:
 135       return parent->cast.ptr_stride;
 136    default:
 137       unreachable("Invalid parent for ptr_as_array deref");
 138    }
 139 }
 140
 141 static unsigned
 142 type_get_array_stride(const struct glsl_type *elem_type,
 143                       glsl_type_size_align_func size_align)
 144 {
 145    unsigned elem_size, elem_align;
 146    size_align(elem_type, &elem_size, &elem_align);
 147    return ALIGN_POT(elem_size, elem_align);
 148 }
 149
 150 static unsigned
 151 struct_type_get_field_offset(const struct glsl_type *struct_type,
 152                              glsl_type_size_align_func size_align,
 153                              unsigned field_idx)
 154 {
 155    assert(glsl_type_is_struct(struct_type));
 156    unsigned offset = 0;
 157    for (unsigned i = 0; i <= field_idx; i++) {
 158       unsigned elem_size, elem_align;
 159       size_align(glsl_get_struct_field(struct_type, i), &elem_size, &elem_align);
 160       offset = ALIGN_POT(offset, elem_align);
 161       if (i < field_idx)
 162          offset += elem_size;
 163    }
 164    return offset;
 165 }
 166
 167 unsigned
 168 nir_deref_instr_get_const_offset(nir_deref_instr *deref,
 169                                  glsl_type_size_align_func size_align)
 170 {
 171    nir_deref_path path;
 172    nir_deref_path_init(&path, deref, NULL);
 173
 174    assert(path.path[0]->deref_type == nir_deref_type_var);
 175
 176    unsigned offset = 0;
 177    for (nir_deref_instr **p = &path.path[1]; *p; p++) {
 178       if ((*p)->deref_type == nir_deref_type_array) {
 179          offset += nir_src_as_uint((*p)->arr.index) *
 180                    type_get_array_stride((*p)->type, size_align);
 181       } else if ((*p)->deref_type == nir_deref_type_struct) {
 182          /* p starts at path[1], so this is safe */
 183          nir_deref_instr *parent = *(p - 1);
 184          offset += struct_type_get_field_offset(parent->type, size_align,
 185                                                 (*p)->strct.index);
 186       } else {
 187          unreachable("Unsupported deref type");
 188       }
 189    }
 190
 191    nir_deref_path_finish(&path);
 192
 193    return offset;
 194 }
 195
 196 nir_ssa_def *
 197 nir_build_deref_offset(nir_builder *b, nir_deref_instr *deref,
 198                        glsl_type_size_align_func size_align)
 199 {
 200    nir_deref_path path;
 201    nir_deref_path_init(&path, deref, NULL);
 202
 203    assert(path.path[0]->deref_type == nir_deref_type_var);
 204
 205    nir_ssa_def *offset = nir_imm_int(b, 0);
 206    for (nir_deref_instr **p = &path.path[1]; *p; p++) {
 207       if ((*p)->deref_type == nir_deref_type_array) {
 208          nir_ssa_def *index = nir_ssa_for_src(b, (*p)->arr.index, 1);
 209          nir_ssa_def *stride =
 210             nir_imm_int(b, type_get_array_stride((*p)->type, size_align));
 211          offset = nir_iadd(b, offset, nir_imul(b, index, stride));
 212       } else if ((*p)->deref_type == nir_deref_type_struct) {
 213          /* p starts at path[1], so this is safe */
 214          nir_deref_instr *parent = *(p - 1);
 215          unsigned field_offset =
 216             struct_type_get_field_offset(parent->type, size_align,
 217                                          (*p)->strct.index);
 218          nir_iadd(b, offset, nir_imm_int(b, field_offset));
 219       } else {
 220          unreachable("Unsupported deref type");
 221       }
 222    }
 223
 224    nir_deref_path_finish(&path);
 225
 226    return offset;
 227 }
 228
 229 bool
 230 nir_remove_dead_derefs_impl(nir_function_impl *impl)
 231 {
 232    bool progress = false;
 233
 234    nir_foreach_block(block, impl) {
 235       nir_foreach_instr_safe(instr, block) {
 236          if (instr->type == nir_instr_type_deref &&
 237              nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr)))
 238             progress = true;
 239       }
 240    }
 241
 242    if (progress)
 243       nir_metadata_preserve(impl, nir_metadata_block_index |
 244                                   nir_metadata_dominance);
 245
 246    return progress;
 247 }
 248
 249 bool
 250 nir_remove_dead_derefs(nir_shader *shader)
 251 {
 252    bool progress = false;
 253    nir_foreach_function(function, shader) {
 254       if (function->impl && nir_remove_dead_derefs_impl(function->impl))
 255          progress = true;
 256    }
 257
 258    return progress;
 259 }
 260
 261 void
 262 nir_fixup_deref_modes(nir_shader *shader)
 263 {
 264    nir_foreach_function(function, shader) {
 265       if (!function->impl)
 266          continue;
 267
 268       nir_foreach_block(block, function->impl) {
 269          nir_foreach_instr(instr, block) {
 270             if (instr->type != nir_instr_type_deref)
 271                continue;
 272
 273             nir_deref_instr *deref = nir_instr_as_deref(instr);
 274             if (deref->deref_type == nir_deref_type_cast)
 275                continue;
 276
 277             nir_variable_mode parent_mode;
 278             if (deref->deref_type == nir_deref_type_var) {
 279                parent_mode = deref->var->data.mode;
 280             } else {
 281                assert(deref->parent.is_ssa);
 282                nir_deref_instr *parent =
 283                   nir_instr_as_deref(deref->parent.ssa->parent_instr);
 284                parent_mode = parent->mode;
 285             }
 286
 287             deref->mode = parent_mode;
 288          }
 289       }
 290    }
 291 }
 292
 293 static bool
 294 modes_may_alias(nir_variable_mode a, nir_variable_mode b)
 295 {
 296    /* Generic pointers can alias with SSBOs */
 297    if ((a == nir_var_mem_ssbo || a == nir_var_mem_global) &&
 298        (b == nir_var_mem_ssbo || b == nir_var_mem_global))
 299       return true;
 300
 301    /* In the general case, pointers can only alias if they have the same mode.
 302     *
 303     * NOTE: In future, with things like OpenCL generic pointers, this may not
 304     * be true and will have to be re-evaluated.  However, with graphics only,
 305     * it should be safe.
 306     */
 307    return a == b;
 308 }
 309
 310 nir_deref_compare_result
 311 nir_compare_deref_paths(nir_deref_path *a_path,
 312                         nir_deref_path *b_path)
 313 {
 314    if (!modes_may_alias(b_path->path[0]->mode, a_path->path[0]->mode))
 315       return nir_derefs_do_not_alias;
 316
 317    if (a_path->path[0]->deref_type != b_path->path[0]->deref_type)
 318       return nir_derefs_may_alias_bit;
 319
 320    if (a_path->path[0]->deref_type == nir_deref_type_var) {
 321       /* If we can chase the deref all the way back to the variable and
 322        * they're not the same variable, we know they can't possibly alias.
 323        */
 324       if (a_path->path[0]->var != b_path->path[0]->var)
 325          return nir_derefs_do_not_alias;
 326    } else {
 327       assert(a_path->path[0]->deref_type == nir_deref_type_cast);
 328       /* If they're not exactly the same cast, it's hard to compare them so we
 329        * just assume they alias.  Comparing casts is tricky as there are lots
 330        * of things such as mode, type, etc. to make sure work out; for now, we
 331        * just assume nit_opt_deref will combine them and compare the deref
 332        * instructions.
 333        *
 334        * TODO: At some point in the future, we could be clever and understand
 335        * that a float[] and int[] have the same layout and aliasing structure
 336        * but double[] and vec3[] do not and we could potentially be a bit
 337        * smarter here.
 338        */
 339       if (a_path->path[0] != b_path->path[0])
 340          return nir_derefs_may_alias_bit;
 341    }
 342
 343    /* Start off assuming they fully compare.  We ignore equality for now.  In
 344     * the end, we'll determine that by containment.
 345     */
 346    nir_deref_compare_result result = nir_derefs_may_alias_bit |
 347                                      nir_derefs_a_contains_b_bit |
 348                                      nir_derefs_b_contains_a_bit;
 349
 350    nir_deref_instr **a_p = &a_path->path[1];
 351    nir_deref_instr **b_p = &b_path->path[1];
 352    while (*a_p != NULL && *a_p == *b_p) {
 353       a_p++;
 354       b_p++;
 355    }
 356
 357    /* We're at either the tail or the divergence point between the two deref
 358     * paths.  Look to see if either contains a ptr_as_array deref.  It it
 359     * does we don't know how to safely make any inferences.  Hopefully,
 360     * nir_opt_deref will clean most of these up and we can start inferring
 361     * things again.
 362     *
 363     * In theory, we could do a bit better.  For instance, we could detect the
 364     * case where we have exactly one ptr_as_array deref in the chain after the
 365     * divergence point and it's matched in both chains and the two chains have
 366     * different constant indices.
 367     */
 368    for (nir_deref_instr **t_p = a_p; *t_p; t_p++) {
 369       if ((*t_p)->deref_type == nir_deref_type_ptr_as_array)
 370          return nir_derefs_may_alias_bit;
 371    }
 372    for (nir_deref_instr **t_p = b_p; *t_p; t_p++) {
 373       if ((*t_p)->deref_type == nir_deref_type_ptr_as_array)
 374          return nir_derefs_may_alias_bit;
 375    }
 376
 377    while (*a_p != NULL && *b_p != NULL) {
 378       nir_deref_instr *a_tail = *(a_p++);
 379       nir_deref_instr *b_tail = *(b_p++);
 380
 381       switch (a_tail->deref_type) {
 382       case nir_deref_type_array:
 383       case nir_deref_type_array_wildcard: {
 384          assert(b_tail->deref_type == nir_deref_type_array ||
 385                 b_tail->deref_type == nir_deref_type_array_wildcard);
 386
 387          if (a_tail->deref_type == nir_deref_type_array_wildcard) {
 388             if (b_tail->deref_type != nir_deref_type_array_wildcard)
 389                result &= ~nir_derefs_b_contains_a_bit;
 390          } else if (b_tail->deref_type == nir_deref_type_array_wildcard) {
 391             if (a_tail->deref_type != nir_deref_type_array_wildcard)
 392                result &= ~nir_derefs_a_contains_b_bit;
 393          } else {
 394             assert(a_tail->deref_type == nir_deref_type_array &&
 395                    b_tail->deref_type == nir_deref_type_array);
 396             assert(a_tail->arr.index.is_ssa && b_tail->arr.index.is_ssa);
 397
 398             if (nir_src_is_const(a_tail->arr.index) &&
 399                 nir_src_is_const(b_tail->arr.index)) {
 400                /* If they're both direct and have different offsets, they
 401                 * don't even alias much less anything else.
 402                 */
 403                if (nir_src_as_uint(a_tail->arr.index) !=
 404                    nir_src_as_uint(b_tail->arr.index))
 405                   return nir_derefs_do_not_alias;
 406             } else if (a_tail->arr.index.ssa == b_tail->arr.index.ssa) {
 407                /* They're the same indirect, continue on */
 408             } else {
 409                /* They're not the same index so we can't prove anything about
 410                 * containment.
 411                 */
 412                result &= ~(nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit);
 413             }
 414          }
 415          break;
 416       }
 417
 418       case nir_deref_type_struct: {
 419          /* If they're different struct members, they don't even alias */
 420          if (a_tail->strct.index != b_tail->strct.index)
 421             return nir_derefs_do_not_alias;
 422          break;
 423       }
 424
 425       default:
 426          unreachable("Invalid deref type");
 427       }
 428    }
 429
 430    /* If a is longer than b, then it can't contain b */
 431    if (*a_p != NULL)
 432       result &= ~nir_derefs_a_contains_b_bit;
 433    if (*b_p != NULL)
 434       result &= ~nir_derefs_b_contains_a_bit;
 435
 436    /* If a contains b and b contains a they must be equal. */
 437    if ((result & nir_derefs_a_contains_b_bit) && (result & nir_derefs_b_contains_a_bit))
 438       result |= nir_derefs_equal_bit;
 439
 440    return result;
 441 }
 442
 443 nir_deref_compare_result
 444 nir_compare_derefs(nir_deref_instr *a, nir_deref_instr *b)
 445 {
 446    if (a == b) {
 447       return nir_derefs_equal_bit | nir_derefs_may_alias_bit |
 448              nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit;
 449    }
 450
 451    nir_deref_path a_path, b_path;
 452    nir_deref_path_init(&a_path, a, NULL);
 453    nir_deref_path_init(&b_path, b, NULL);
 454    assert(a_path.path[0]->deref_type == nir_deref_type_var ||
 455           a_path.path[0]->deref_type == nir_deref_type_cast);
 456    assert(b_path.path[0]->deref_type == nir_deref_type_var ||
 457           b_path.path[0]->deref_type == nir_deref_type_cast);
 458
 459    nir_deref_compare_result result = nir_compare_deref_paths(&a_path, &b_path);
 460
 461    nir_deref_path_finish(&a_path);
 462    nir_deref_path_finish(&b_path);
 463
 464    return result;
 465 }
 466
 467 struct rematerialize_deref_state {
 468    bool progress;
 469    nir_builder builder;
 470    nir_block *block;
 471    struct hash_table *cache;
 472 };
 473
 474 static nir_deref_instr *
 475 rematerialize_deref_in_block(nir_deref_instr *deref,
 476                              struct rematerialize_deref_state *state)
 477 {
 478    if (deref->instr.block == state->block)
 479       return deref;
 480
 481    if (!state->cache) {
 482       state->cache = _mesa_pointer_hash_table_create(NULL);
 483    }
 484
 485    struct hash_entry *cached = _mesa_hash_table_search(state->cache, deref);
 486    if (cached)
 487       return cached->data;
 488
 489    nir_builder *b = &state->builder;
 490    nir_deref_instr *new_deref =
 491       nir_deref_instr_create(b->shader, deref->deref_type);
 492    new_deref->mode = deref->mode;
 493    new_deref->type = deref->type;
 494
 495    if (deref->deref_type == nir_deref_type_var) {
 496       new_deref->var = deref->var;
 497    } else {
 498       nir_deref_instr *parent = nir_src_as_deref(deref->parent);
 499       if (parent) {
 500          parent = rematerialize_deref_in_block(parent, state);
 501          new_deref->parent = nir_src_for_ssa(&parent->dest.ssa);
 502       } else {
 503          nir_src_copy(&new_deref->parent, &deref->parent, new_deref);
 504       }
 505    }
 506
 507    switch (deref->deref_type) {
 508    case nir_deref_type_var:
 509    case nir_deref_type_array_wildcard:
 510    case nir_deref_type_cast:
 511       /* Nothing more to do */
 512       break;
 513
 514    case nir_deref_type_array:
 515       assert(!nir_src_as_deref(deref->arr.index));
 516       nir_src_copy(&new_deref->arr.index, &deref->arr.index, new_deref);
 517       break;
 518
 519    case nir_deref_type_struct:
 520       new_deref->strct.index = deref->strct.index;
 521       break;
 522
 523    default:
 524       unreachable("Invalid deref instruction type");
 525    }
 526
 527    nir_ssa_dest_init(&new_deref->instr, &new_deref->dest,
 528                      deref->dest.ssa.num_components,
 529                      deref->dest.ssa.bit_size,
 530                      deref->dest.ssa.name);
 531    nir_builder_instr_insert(b, &new_deref->instr);
 532
 533    return new_deref;
 534 }
 535
 536 static bool
 537 rematerialize_deref_src(nir_src *src, void *_state)
 538 {
 539    struct rematerialize_deref_state *state = _state;
 540
 541    nir_deref_instr *deref = nir_src_as_deref(*src);
 542    if (!deref)
 543       return true;
 544
 545    nir_deref_instr *block_deref = rematerialize_deref_in_block(deref, state);
 546    if (block_deref != deref) {
 547       nir_instr_rewrite_src(src->parent_instr, src,
 548                             nir_src_for_ssa(&block_deref->dest.ssa));
 549       nir_deref_instr_remove_if_unused(deref);
 550       state->progress = true;
 551    }
 552
 553    return true;
 554 }
 555
 556 /** Re-materialize derefs in every block
 557  *
 558  * This pass re-materializes deref instructions in every block in which it is
 559  * used.  After this pass has been run, every use of a deref will be of a
 560  * deref in the same block as the use.  Also, all unused derefs will be
 561  * deleted as a side-effect.
 562  */
 563 bool
 564 nir_rematerialize_derefs_in_use_blocks_impl(nir_function_impl *impl)
 565 {
 566    struct rematerialize_deref_state state = { 0 };
 567    nir_builder_init(&state.builder, impl);
 568
 569    nir_foreach_block(block, impl) {
 570       state.block = block;
 571
 572       /* Start each block with a fresh cache */
 573       if (state.cache)
 574          _mesa_hash_table_clear(state.cache, NULL);
 575
 576       nir_foreach_instr_safe(instr, block) {
 577          if (instr->type == nir_instr_type_deref) {
 578             nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr));
 579             continue;
 580          }
 581
 582          state.builder.cursor = nir_before_instr(instr);
 583          nir_foreach_src(instr, rematerialize_deref_src, &state);
 584       }
 585
 586 #ifndef NDEBUG
 587       nir_if *following_if = nir_block_get_following_if(block);
 588       if (following_if)
 589          assert(!nir_src_as_deref(following_if->condition));
 590 #endif
 591    }
 592
 593    _mesa_hash_table_destroy(state.cache, NULL);
 594
 595    return state.progress;
 596 }
 597
 598 static bool
 599 is_trivial_deref_cast(nir_deref_instr *cast)
 600 {
 601    nir_deref_instr *parent = nir_src_as_deref(cast->parent);
 602    if (!parent)
 603       return false;
 604
 605    return cast->mode == parent->mode &&
 606           cast->type == parent->type &&
 607           cast->dest.ssa.num_components == parent->dest.ssa.num_components &&
 608           cast->dest.ssa.bit_size == parent->dest.ssa.bit_size;
 609 }
 610
 611 static bool
 612 is_trivial_array_deref_cast(nir_deref_instr *cast)
 613 {
 614    assert(is_trivial_deref_cast(cast));
 615
 616    nir_deref_instr *parent = nir_src_as_deref(cast->parent);
 617
 618    if (parent->deref_type == nir_deref_type_array) {
 619       return cast->cast.ptr_stride ==
 620              glsl_get_explicit_stride(nir_deref_instr_parent(parent)->type);
 621    } else if (parent->deref_type == nir_deref_type_ptr_as_array) {
 622       return cast->cast.ptr_stride ==
 623              nir_deref_instr_ptr_as_array_stride(parent);
 624    } else {
 625       return false;
 626    }
 627 }
 628
 629 static bool
 630 is_deref_ptr_as_array(nir_instr *instr)
 631 {
 632    return instr->type == nir_instr_type_deref &&
 633           nir_instr_as_deref(instr)->deref_type == nir_deref_type_ptr_as_array;
 634 }
 635
 636 static bool
 637 opt_deref_cast(nir_deref_instr *cast)
 638 {
 639    if (!is_trivial_deref_cast(cast))
 640       return false;
 641
 642    bool trivial_array_cast = is_trivial_array_deref_cast(cast);
 643
 644    assert(cast->dest.is_ssa);
 645    assert(cast->parent.is_ssa);
 646
 647    bool progress = false;
 648    nir_foreach_use_safe(use_src, &cast->dest.ssa) {
 649       /* If this isn't a trivial array cast, we can't propagate into
 650        * ptr_as_array derefs.
 651        */
 652       if (is_deref_ptr_as_array(use_src->parent_instr) &&
 653           !trivial_array_cast)
 654          continue;
 655
 656       nir_instr_rewrite_src(use_src->parent_instr, use_src, cast->parent);
 657       progress = true;
 658    }
 659
 660    /* If uses would be a bit crazy */
 661    assert(list_empty(&cast->dest.ssa.if_uses));
 662
 663    nir_deref_instr_remove_if_unused(cast);
 664    return progress;
 665 }
 666
 667 static bool
 668 opt_deref_ptr_as_array(nir_builder *b, nir_deref_instr *deref)
 669 {
 670    assert(deref->deref_type == nir_deref_type_ptr_as_array);
 671
 672    nir_deref_instr *parent = nir_deref_instr_parent(deref);
 673    if (parent->deref_type != nir_deref_type_array &&
 674        parent->deref_type != nir_deref_type_ptr_as_array)
 675       return false;
 676
 677    assert(parent->parent.is_ssa);
 678    assert(parent->arr.index.is_ssa);
 679    assert(deref->arr.index.is_ssa);
 680
 681    nir_ssa_def *new_idx = nir_iadd(b, parent->arr.index.ssa,
 682                                       deref->arr.index.ssa);
 683
 684    deref->deref_type = parent->deref_type;
 685    nir_instr_rewrite_src(&deref->instr, &deref->parent, parent->parent);
 686    nir_instr_rewrite_src(&deref->instr, &deref->arr.index,
 687                          nir_src_for_ssa(new_idx));
 688    return true;
 689 }
 690
 691 static bool
 692 nir_opt_deref_impl(nir_function_impl *impl)
 693 {
 694    bool progress = false;
 695
 696    nir_builder b;
 697    nir_builder_init(&b, impl);
 698
 699    nir_foreach_block(block, impl) {
 700       nir_foreach_instr_safe(instr, block) {
 701          if (instr->type != nir_instr_type_deref)
 702             continue;
 703
 704          b.cursor = nir_before_instr(instr);
 705
 706          nir_deref_instr *deref = nir_instr_as_deref(instr);
 707          switch (deref->deref_type) {
 708          case nir_deref_type_ptr_as_array:
 709             if (opt_deref_ptr_as_array(&b, deref))
 710                progress = true;
 711             break;
 712
 713          case nir_deref_type_cast:
 714             if (opt_deref_cast(deref))
 715                progress = true;
 716             break;
 717
 718          default:
 719             /* Do nothing */
 720             break;
 721          }
 722       }
 723    }
 724
 725    if (progress) {
 726       nir_metadata_preserve(impl, nir_metadata_block_index |
 727                                   nir_metadata_dominance);
 728    } else {
 729 #ifndef NDEBUG
 730       impl->valid_metadata &= ~nir_metadata_not_properly_reset;
 731 #endif
 732    }
 733
 734    return progress;
 735 }
 736
 737 bool
 738 nir_opt_deref(nir_shader *shader)
 739 {
 740    bool progress = false;
 741
 742    nir_foreach_function(func, shader) {
 743       if (func->impl && nir_opt_deref_impl(func->impl))
 744          progress = true;
 745    }
 746
 747    return progress;
 748 }