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