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