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((*head)->deref_type == nir_deref_type_var);
  74    assert(*tail == NULL);
  75 }
  76
  77 void
  78 nir_deref_path_finish(nir_deref_path *path)
  79 {
  80    if (path->path < &path->_short_path[0] ||
  81        path->path > &path->_short_path[ARRAY_SIZE(path->_short_path) - 1])
  82       ralloc_free(path->path);
  83 }
  84
  85 /**
  86  * Recursively removes unused deref instructions
  87  */
  88 bool
  89 nir_deref_instr_remove_if_unused(nir_deref_instr *instr)
  90 {
  91    bool progress = false;
  92
  93    for (nir_deref_instr *d = instr; d; d = nir_deref_instr_parent(d)) {
  94       /* If anyone is using this deref, leave it alone */
  95       assert(d->dest.is_ssa);
  96       if (!list_empty(&d->dest.ssa.uses))
  97          break;
  98
  99       nir_instr_remove(&d->instr);
 100       progress = true;
 101    }
 102
 103    return progress;
 104 }
 105
 106 bool
 107 nir_deref_instr_has_indirect(nir_deref_instr *instr)
 108 {
 109    while (instr->deref_type != nir_deref_type_var) {
 110       /* Consider casts to be indirects */
 111       if (instr->deref_type == nir_deref_type_cast)
 112          return true;
 113
 114       if (instr->deref_type == nir_deref_type_array &&
 115           !nir_src_as_const_value(instr->arr.index))
 116          return true;
 117
 118       instr = nir_deref_instr_parent(instr);
 119    }
 120
 121    return false;
 122 }
 123
 124 static unsigned
 125 type_get_array_stride(const struct glsl_type *elem_type,
 126                       glsl_type_size_align_func size_align)
 127 {
 128    unsigned elem_size, elem_align;
 129    glsl_get_natural_size_align_bytes(elem_type, &elem_size, &elem_align);
 130    return ALIGN_POT(elem_size, elem_align);
 131 }
 132
 133 static unsigned
 134 struct_type_get_field_offset(const struct glsl_type *struct_type,
 135                              glsl_type_size_align_func size_align,
 136                              unsigned field_idx)
 137 {
 138    assert(glsl_type_is_struct(struct_type));
 139    unsigned offset = 0;
 140    for (unsigned i = 0; i <= field_idx; i++) {
 141       unsigned elem_size, elem_align;
 142       glsl_get_natural_size_align_bytes(glsl_get_struct_field(struct_type, i),
 143                                         &elem_size, &elem_align);
 144       offset = ALIGN_POT(offset, elem_align);
 145       if (i < field_idx)
 146          offset += elem_size;
 147    }
 148    return offset;
 149 }
 150
 151 unsigned
 152 nir_deref_instr_get_const_offset(nir_deref_instr *deref,
 153                                  glsl_type_size_align_func size_align)
 154 {
 155    nir_deref_path path;
 156    nir_deref_path_init(&path, deref, NULL);
 157
 158    assert(path.path[0]->deref_type == nir_deref_type_var);
 159
 160    unsigned offset = 0;
 161    for (nir_deref_instr **p = &path.path[1]; *p; p++) {
 162       if ((*p)->deref_type == nir_deref_type_array) {
 163          offset += nir_src_as_const_value((*p)->arr.index)->u32[0] *
 164                    type_get_array_stride((*p)->type, size_align);
 165       } else if ((*p)->deref_type == nir_deref_type_struct) {
 166          /* p starts at path[1], so this is safe */
 167          nir_deref_instr *parent = *(p - 1);
 168          offset += struct_type_get_field_offset(parent->type, size_align,
 169                                                 (*p)->strct.index);
 170       } else {
 171          unreachable("Unsupported deref type");
 172       }
 173    }
 174
 175    nir_deref_path_finish(&path);
 176
 177    return offset;
 178 }
 179
 180 nir_ssa_def *
 181 nir_build_deref_offset(nir_builder *b, nir_deref_instr *deref,
 182                        glsl_type_size_align_func size_align)
 183 {
 184    nir_deref_path path;
 185    nir_deref_path_init(&path, deref, NULL);
 186
 187    assert(path.path[0]->deref_type == nir_deref_type_var);
 188
 189    nir_ssa_def *offset = nir_imm_int(b, 0);
 190    for (nir_deref_instr **p = &path.path[1]; *p; p++) {
 191       if ((*p)->deref_type == nir_deref_type_array) {
 192          nir_ssa_def *index = nir_ssa_for_src(b, (*p)->arr.index, 1);
 193          nir_ssa_def *stride =
 194             nir_imm_int(b, type_get_array_stride((*p)->type, size_align));
 195          offset = nir_iadd(b, offset, nir_imul(b, index, stride));
 196       } else if ((*p)->deref_type == nir_deref_type_struct) {
 197          /* p starts at path[1], so this is safe */
 198          nir_deref_instr *parent = *(p - 1);
 199          unsigned field_offset =
 200             struct_type_get_field_offset(parent->type, size_align,
 201                                          (*p)->strct.index);
 202          nir_iadd(b, offset, nir_imm_int(b, field_offset));
 203       } else {
 204          unreachable("Unsupported deref type");
 205       }
 206    }
 207
 208    nir_deref_path_finish(&path);
 209
 210    return offset;
 211 }
 212
 213 bool
 214 nir_remove_dead_derefs_impl(nir_function_impl *impl)
 215 {
 216    bool progress = false;
 217
 218    nir_foreach_block(block, impl) {
 219       nir_foreach_instr_safe(instr, block) {
 220          if (instr->type == nir_instr_type_deref &&
 221              nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr)))
 222             progress = true;
 223       }
 224    }
 225
 226    if (progress)
 227       nir_metadata_preserve(impl, nir_metadata_block_index |
 228                                   nir_metadata_dominance);
 229
 230    return progress;
 231 }
 232
 233 bool
 234 nir_remove_dead_derefs(nir_shader *shader)
 235 {
 236    bool progress = false;
 237    nir_foreach_function(function, shader) {
 238       if (function->impl && nir_remove_dead_derefs_impl(function->impl))
 239          progress = true;
 240    }
 241
 242    return progress;
 243 }
 244
 245 void
 246 nir_fixup_deref_modes(nir_shader *shader)
 247 {
 248    nir_foreach_function(function, shader) {
 249       if (!function->impl)
 250          continue;
 251
 252       nir_foreach_block(block, function->impl) {
 253          nir_foreach_instr(instr, block) {
 254             if (instr->type != nir_instr_type_deref)
 255                continue;
 256
 257             nir_deref_instr *deref = nir_instr_as_deref(instr);
 258
 259             nir_variable_mode parent_mode;
 260             if (deref->deref_type == nir_deref_type_var) {
 261                parent_mode = deref->var->data.mode;
 262             } else {
 263                assert(deref->parent.is_ssa);
 264                nir_deref_instr *parent =
 265                   nir_instr_as_deref(deref->parent.ssa->parent_instr);
 266                parent_mode = parent->mode;
 267             }
 268
 269             deref->mode = parent_mode;
 270          }
 271       }
 272    }
 273 }
 274
 275 nir_deref_compare_result
 276 nir_compare_deref_paths(nir_deref_path *a_path,
 277                         nir_deref_path *b_path)
 278 {
 279    if (a_path->path[0]->var != b_path->path[0]->var)
 280       return 0;
 281
 282    /* Start off assuming they fully compare.  We ignore equality for now.  In
 283     * the end, we'll determine that by containment.
 284     */
 285    nir_deref_compare_result result = nir_derefs_may_alias_bit |
 286                                      nir_derefs_a_contains_b_bit |
 287                                      nir_derefs_b_contains_a_bit;
 288
 289    nir_deref_instr **a_p = &a_path->path[1];
 290    nir_deref_instr **b_p = &b_path->path[1];
 291    while (*a_p != NULL && *b_p != NULL) {
 292       nir_deref_instr *a_tail = *(a_p++);
 293       nir_deref_instr *b_tail = *(b_p++);
 294
 295       if (a_tail == b_tail)
 296          continue;
 297
 298       switch (a_tail->deref_type) {
 299       case nir_deref_type_array:
 300       case nir_deref_type_array_wildcard: {
 301          assert(b_tail->deref_type == nir_deref_type_array ||
 302                 b_tail->deref_type == nir_deref_type_array_wildcard);
 303
 304          if (a_tail->deref_type == nir_deref_type_array_wildcard) {
 305             if (b_tail->deref_type != nir_deref_type_array_wildcard)
 306                result &= ~nir_derefs_b_contains_a_bit;
 307          } else if (b_tail->deref_type == nir_deref_type_array_wildcard) {
 308             if (a_tail->deref_type != nir_deref_type_array_wildcard)
 309                result &= ~nir_derefs_a_contains_b_bit;
 310          } else {
 311             assert(a_tail->deref_type == nir_deref_type_array &&
 312                    b_tail->deref_type == nir_deref_type_array);
 313             assert(a_tail->arr.index.is_ssa && b_tail->arr.index.is_ssa);
 314
 315             nir_const_value *a_index_const =
 316                nir_src_as_const_value(a_tail->arr.index);
 317             nir_const_value *b_index_const =
 318                nir_src_as_const_value(b_tail->arr.index);
 319             if (a_index_const && b_index_const) {
 320                /* If they're both direct and have different offsets, they
 321                 * don't even alias much less anything else.
 322                 */
 323                if (a_index_const->u32[0] != b_index_const->u32[0])
 324                   return 0;
 325             } else if (a_tail->arr.index.ssa == b_tail->arr.index.ssa) {
 326                /* They're the same indirect, continue on */
 327             } else {
 328                /* They're not the same index so we can't prove anything about
 329                 * containment.
 330                 */
 331                result &= ~(nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit);
 332             }
 333          }
 334          break;
 335       }
 336
 337       case nir_deref_type_struct: {
 338          /* If they're different struct members, they don't even alias */
 339          if (a_tail->strct.index != b_tail->strct.index)
 340             return 0;
 341          break;
 342       }
 343
 344       default:
 345          unreachable("Invalid deref type");
 346       }
 347    }
 348
 349    /* If a is longer than b, then it can't contain b */
 350    if (*a_p != NULL)
 351       result &= ~nir_derefs_a_contains_b_bit;
 352    if (*b_p != NULL)
 353       result &= ~nir_derefs_b_contains_a_bit;
 354
 355    /* If a contains b and b contains a they must be equal. */
 356    if ((result & nir_derefs_a_contains_b_bit) && (result & nir_derefs_b_contains_a_bit))
 357       result |= nir_derefs_equal_bit;
 358
 359    return result;
 360 }
 361
 362 nir_deref_compare_result
 363 nir_compare_derefs(nir_deref_instr *a, nir_deref_instr *b)
 364 {
 365    if (a == b) {
 366       return nir_derefs_equal_bit | nir_derefs_may_alias_bit |
 367              nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit;
 368    }
 369
 370    nir_deref_path a_path, b_path;
 371    nir_deref_path_init(&a_path, a, NULL);
 372    nir_deref_path_init(&b_path, b, NULL);
 373    assert(a_path.path[0]->deref_type == nir_deref_type_var);
 374    assert(b_path.path[0]->deref_type == nir_deref_type_var);
 375
 376    nir_deref_compare_result result = nir_compare_deref_paths(&a_path, &b_path);
 377
 378    nir_deref_path_finish(&a_path);
 379    nir_deref_path_finish(&b_path);
 380
 381    return result;
 382 }
 383
 384 struct rematerialize_deref_state {
 385    bool progress;
 386    nir_builder builder;
 387    nir_block *block;
 388    struct hash_table *cache;
 389 };
 390
 391 static nir_deref_instr *
 392 rematerialize_deref_in_block(nir_deref_instr *deref,
 393                              struct rematerialize_deref_state *state)
 394 {
 395    if (deref->instr.block == state->block)
 396       return deref;
 397
 398    if (!state->cache) {
 399       state->cache = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
 400                                              _mesa_key_pointer_equal);
 401    }
 402
 403    struct hash_entry *cached = _mesa_hash_table_search(state->cache, deref);
 404    if (cached)
 405       return cached->data;
 406
 407    nir_builder *b = &state->builder;
 408    nir_deref_instr *new_deref =
 409       nir_deref_instr_create(b->shader, deref->deref_type);
 410    new_deref->mode = deref->mode;
 411    new_deref->type = deref->type;
 412
 413    if (deref->deref_type == nir_deref_type_var) {
 414       new_deref->var = deref->var;
 415    } else {
 416       nir_deref_instr *parent = nir_src_as_deref(deref->parent);
 417       if (parent) {
 418          parent = rematerialize_deref_in_block(parent, state);
 419          new_deref->parent = nir_src_for_ssa(&parent->dest.ssa);
 420       } else {
 421          nir_src_copy(&new_deref->parent, &deref->parent, new_deref);
 422       }
 423    }
 424
 425    switch (deref->deref_type) {
 426    case nir_deref_type_var:
 427    case nir_deref_type_array_wildcard:
 428    case nir_deref_type_cast:
 429       /* Nothing more to do */
 430       break;
 431
 432    case nir_deref_type_array:
 433       assert(!nir_src_as_deref(deref->arr.index));
 434       nir_src_copy(&new_deref->arr.index, &deref->arr.index, new_deref);
 435       break;
 436
 437    case nir_deref_type_struct:
 438       new_deref->strct.index = deref->strct.index;
 439       break;
 440
 441    default:
 442       unreachable("Invalid deref instruction type");
 443    }
 444
 445    nir_ssa_dest_init(&new_deref->instr, &new_deref->dest,
 446                      deref->dest.ssa.num_components,
 447                      deref->dest.ssa.bit_size,
 448                      deref->dest.ssa.name);
 449    nir_builder_instr_insert(b, &new_deref->instr);
 450
 451    return new_deref;
 452 }
 453
 454 static bool
 455 rematerialize_deref_src(nir_src *src, void *_state)
 456 {
 457    struct rematerialize_deref_state *state = _state;
 458
 459    nir_deref_instr *deref = nir_src_as_deref(*src);
 460    if (!deref)
 461       return true;
 462
 463    nir_deref_instr *block_deref = rematerialize_deref_in_block(deref, state);
 464    if (block_deref != deref) {
 465       nir_instr_rewrite_src(src->parent_instr, src,
 466                             nir_src_for_ssa(&block_deref->dest.ssa));
 467       nir_deref_instr_remove_if_unused(deref);
 468       state->progress = true;
 469    }
 470
 471    return true;
 472 }
 473
 474 /** Re-materialize derefs in every block
 475  *
 476  * This pass re-materializes deref instructions in every block in which it is
 477  * used.  After this pass has been run, every use of a deref will be of a
 478  * deref in the same block as the use.  Also, all unused derefs will be
 479  * deleted as a side-effect.
 480  */
 481 bool
 482 nir_rematerialize_derefs_in_use_blocks_impl(nir_function_impl *impl)
 483 {
 484    struct rematerialize_deref_state state = { };
 485    nir_builder_init(&state.builder, impl);
 486
 487    nir_foreach_block(block, impl) {
 488       state.block = block;
 489
 490       /* Start each block with a fresh cache */
 491       if (state.cache)
 492          _mesa_hash_table_clear(state.cache, NULL);
 493
 494       nir_foreach_instr_safe(instr, block) {
 495          if (instr->type == nir_instr_type_deref) {
 496             nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr));
 497             continue;
 498          }
 499
 500          state.builder.cursor = nir_before_instr(instr);
 501          nir_foreach_src(instr, rematerialize_deref_src, &state);
 502       }
 503
 504 #ifndef NDEBUG
 505       nir_if *following_if = nir_block_get_following_if(block);
 506       if (following_if)
 507          assert(!nir_src_as_deref(following_if->condition));
 508 #endif
 509    }
 510
 511    _mesa_hash_table_destroy(state.cache, NULL);
 512
 513    return state.progress;
 514 }