src/compiler/nir/nir_opt_copy_prop_vars.c

   1 /*
   2  * Copyright © 2016 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
  28 #include "util/bitscan.h"
  29 #include "util/u_dynarray.h"
  30
  31 static const bool debug = false;
  32
  33 /**
  34  * Variable-based copy propagation
  35  *
  36  * Normally, NIR trusts in SSA form for most of its copy-propagation needs.
  37  * However, there are cases, especially when dealing with indirects, where SSA
  38  * won't help you.  This pass is for those times.  Specifically, it handles
  39  * the following things that the rest of NIR can't:
  40  *
  41  *  1) Copy-propagation on variables that have indirect access.  This includes
  42  *     propagating from indirect stores into indirect loads.
  43  *
  44  *  2) Removal of redundant load_deref intrinsics.  We can't trust regular CSE
  45  *     to do this because it isn't aware of variable writes that may alias the
  46  *     value and make the former load invalid.
  47  *
  48  * This pass uses an intermediate solution between being local / "per-block"
  49  * and a complete data-flow analysis.  It follows the control flow graph, and
  50  * propagate the available copy information forward, invalidating data at each
  51  * cf_node.
  52  *
  53  * Removal of dead writes to variables is handled by another pass.
  54  */
  55
  56 struct vars_written {
  57    nir_variable_mode modes;
  58
  59    /* Key is deref and value is the uintptr_t with the write mask. */
  60    struct hash_table *derefs;
  61 };
  62
  63 struct value {
  64    bool is_ssa;
  65    union {
  66       struct {
  67          nir_ssa_def *def[NIR_MAX_VEC_COMPONENTS];
  68          uint8_t component[NIR_MAX_VEC_COMPONENTS];
  69       } ssa;
  70       nir_deref_instr *deref;
  71    };
  72 };
  73
  74 static void
  75 value_set_ssa_components(struct value *value, nir_ssa_def *def,
  76                          unsigned num_components)
  77 {
  78    if (!value->is_ssa)
  79       memset(&value->ssa, 0, sizeof(value->ssa));
  80    value->is_ssa = true;
  81    for (unsigned i = 0; i < num_components; i++) {
  82       value->ssa.def[i] = def;
  83       value->ssa.component[i] = i;
  84    }
  85 }
  86
  87 struct copy_entry {
  88    struct value src;
  89
  90    nir_deref_instr *dst;
  91 };
  92
  93 struct copy_prop_var_state {
  94    nir_function_impl *impl;
  95
  96    void *mem_ctx;
  97    void *lin_ctx;
  98
  99    /* Maps nodes to vars_written.  Used to invalidate copy entries when
 100     * visiting each node.
 101     */
 102    struct hash_table *vars_written_map;
 103
 104    bool progress;
 105 };
 106
 107 static bool
 108 value_equals_store_src(struct value *value, nir_intrinsic_instr *intrin)
 109 {
 110    assert(intrin->intrinsic == nir_intrinsic_store_deref);
 111    uintptr_t write_mask = nir_intrinsic_write_mask(intrin);
 112
 113    for (unsigned i = 0; i < intrin->num_components; i++) {
 114       if ((write_mask & (1 << i)) &&
 115           (value->ssa.def[i] != intrin->src[1].ssa ||
 116            value->ssa.component[i] != i))
 117          return false;
 118    }
 119
 120    return true;
 121 }
 122
 123 static struct vars_written *
 124 create_vars_written(struct copy_prop_var_state *state)
 125 {
 126    struct vars_written *written =
 127       linear_zalloc_child(state->lin_ctx, sizeof(struct vars_written));
 128    written->derefs = _mesa_pointer_hash_table_create(state->mem_ctx);
 129    return written;
 130 }
 131
 132 static void
 133 gather_vars_written(struct copy_prop_var_state *state,
 134                     struct vars_written *written,
 135                     nir_cf_node *cf_node)
 136 {
 137    struct vars_written *new_written = NULL;
 138
 139    switch (cf_node->type) {
 140    case nir_cf_node_function: {
 141       nir_function_impl *impl = nir_cf_node_as_function(cf_node);
 142       foreach_list_typed_safe(nir_cf_node, cf_node, node, &impl->body)
 143          gather_vars_written(state, NULL, cf_node);
 144       break;
 145    }
 146
 147    case nir_cf_node_block: {
 148       if (!written)
 149          break;
 150
 151       nir_block *block = nir_cf_node_as_block(cf_node);
 152       nir_foreach_instr(instr, block) {
 153          if (instr->type == nir_instr_type_call) {
 154             written->modes |= nir_var_shader_out |
 155                               nir_var_shader_temp |
 156                               nir_var_function_temp |
 157                               nir_var_mem_ssbo |
 158                               nir_var_mem_shared |
 159                               nir_var_mem_global;
 160             continue;
 161          }
 162
 163          if (instr->type != nir_instr_type_intrinsic)
 164             continue;
 165
 166          nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
 167          switch (intrin->intrinsic) {
 168          case nir_intrinsic_control_barrier:
 169          case nir_intrinsic_group_memory_barrier:
 170          case nir_intrinsic_memory_barrier:
 171             written->modes |= nir_var_shader_out |
 172                               nir_var_mem_ssbo |
 173                               nir_var_mem_shared |
 174                               nir_var_mem_global;
 175             break;
 176
 177          case nir_intrinsic_scoped_barrier:
 178             if (nir_intrinsic_memory_semantics(intrin) & NIR_MEMORY_ACQUIRE)
 179                written->modes |= nir_intrinsic_memory_modes(intrin);
 180             break;
 181
 182          case nir_intrinsic_emit_vertex:
 183          case nir_intrinsic_emit_vertex_with_counter:
 184             written->modes = nir_var_shader_out;
 185             break;
 186
 187          case nir_intrinsic_deref_atomic_add:
 188          case nir_intrinsic_deref_atomic_imin:
 189          case nir_intrinsic_deref_atomic_umin:
 190          case nir_intrinsic_deref_atomic_imax:
 191          case nir_intrinsic_deref_atomic_umax:
 192          case nir_intrinsic_deref_atomic_and:
 193          case nir_intrinsic_deref_atomic_or:
 194          case nir_intrinsic_deref_atomic_xor:
 195          case nir_intrinsic_deref_atomic_exchange:
 196          case nir_intrinsic_deref_atomic_comp_swap:
 197          case nir_intrinsic_store_deref:
 198          case nir_intrinsic_copy_deref: {
 199             /* Destination in all of store_deref, copy_deref and the atomics is src[0]. */
 200             nir_deref_instr *dst = nir_src_as_deref(intrin->src[0]);
 201
 202             uintptr_t mask = intrin->intrinsic == nir_intrinsic_store_deref ?
 203                nir_intrinsic_write_mask(intrin) : (1 << glsl_get_vector_elements(dst->type)) - 1;
 204
 205             struct hash_entry *ht_entry = _mesa_hash_table_search(written->derefs, dst);
 206             if (ht_entry)
 207                ht_entry->data = (void *)(mask | (uintptr_t)ht_entry->data);
 208             else
 209                _mesa_hash_table_insert(written->derefs, dst, (void *)mask);
 210
 211             break;
 212          }
 213
 214          default:
 215             break;
 216          }
 217       }
 218
 219       break;
 220    }
 221
 222    case nir_cf_node_if: {
 223       nir_if *if_stmt = nir_cf_node_as_if(cf_node);
 224
 225       new_written = create_vars_written(state);
 226
 227       foreach_list_typed_safe(nir_cf_node, cf_node, node, &if_stmt->then_list)
 228          gather_vars_written(state, new_written, cf_node);
 229
 230       foreach_list_typed_safe(nir_cf_node, cf_node, node, &if_stmt->else_list)
 231          gather_vars_written(state, new_written, cf_node);
 232
 233       break;
 234    }
 235
 236    case nir_cf_node_loop: {
 237       nir_loop *loop = nir_cf_node_as_loop(cf_node);
 238
 239       new_written = create_vars_written(state);
 240
 241       foreach_list_typed_safe(nir_cf_node, cf_node, node, &loop->body)
 242          gather_vars_written(state, new_written, cf_node);
 243
 244       break;
 245    }
 246
 247    default:
 248       unreachable("Invalid CF node type");
 249    }
 250
 251    if (new_written) {
 252       /* Merge new information to the parent control flow node. */
 253       if (written) {
 254          written->modes |= new_written->modes;
 255          hash_table_foreach(new_written->derefs, new_entry) {
 256             struct hash_entry *old_entry =
 257                _mesa_hash_table_search_pre_hashed(written->derefs, new_entry->hash,
 258                                                   new_entry->key);
 259             if (old_entry) {
 260                nir_component_mask_t merged = (uintptr_t) new_entry->data |
 261                                              (uintptr_t) old_entry->data;
 262                old_entry->data = (void *) ((uintptr_t) merged);
 263             } else {
 264                _mesa_hash_table_insert_pre_hashed(written->derefs, new_entry->hash,
 265                                                   new_entry->key, new_entry->data);
 266             }
 267          }
 268       }
 269       _mesa_hash_table_insert(state->vars_written_map, cf_node, new_written);
 270    }
 271 }
 272
 273 static struct copy_entry *
 274 copy_entry_create(struct util_dynarray *copies,
 275                   nir_deref_instr *dst_deref)
 276 {
 277    struct copy_entry new_entry = {
 278       .dst = dst_deref,
 279    };
 280    util_dynarray_append(copies, struct copy_entry, new_entry);
 281    return util_dynarray_top_ptr(copies, struct copy_entry);
 282 }
 283
 284 /* Remove copy entry by swapping it with the last element and reducing the
 285  * size.  If used inside an iteration on copies, it must be a reverse
 286  * (backwards) iteration.  It is safe to use in those cases because the swap
 287  * will not affect the rest of the iteration.
 288  */
 289 static void
 290 copy_entry_remove(struct util_dynarray *copies,
 291                   struct copy_entry *entry)
 292 {
 293    const struct copy_entry *src =
 294       util_dynarray_pop_ptr(copies, struct copy_entry);
 295    if (src != entry)
 296       *entry = *src;
 297 }
 298
 299 static bool
 300 is_array_deref_of_vector(nir_deref_instr *deref)
 301 {
 302    if (deref->deref_type != nir_deref_type_array)
 303       return false;
 304    nir_deref_instr *parent = nir_deref_instr_parent(deref);
 305    return glsl_type_is_vector(parent->type);
 306 }
 307
 308 static struct copy_entry *
 309 lookup_entry_for_deref(struct util_dynarray *copies,
 310                        nir_deref_instr *deref,
 311                        nir_deref_compare_result allowed_comparisons)
 312 {
 313    struct copy_entry *entry = NULL;
 314    util_dynarray_foreach(copies, struct copy_entry, iter) {
 315       nir_deref_compare_result result = nir_compare_derefs(iter->dst, deref);
 316       if (result & allowed_comparisons) {
 317          entry = iter;
 318          if (result & nir_derefs_equal_bit)
 319             break;
 320          /* Keep looking in case we have an equal match later in the array. */
 321       }
 322    }
 323    return entry;
 324 }
 325
 326 static struct copy_entry *
 327 lookup_entry_and_kill_aliases(struct util_dynarray *copies,
 328                               nir_deref_instr *deref,
 329                               unsigned write_mask)
 330 {
 331    /* TODO: Take into account the write_mask. */
 332
 333    nir_deref_instr *dst_match = NULL;
 334    util_dynarray_foreach_reverse(copies, struct copy_entry, iter) {
 335       if (!iter->src.is_ssa) {
 336          /* If this write aliases the source of some entry, get rid of it */
 337          if (nir_compare_derefs(iter->src.deref, deref) & nir_derefs_may_alias_bit) {
 338             copy_entry_remove(copies, iter);
 339             continue;
 340          }
 341       }
 342
 343       nir_deref_compare_result comp = nir_compare_derefs(iter->dst, deref);
 344
 345       if (comp & nir_derefs_equal_bit) {
 346          /* Removing entries invalidate previous iter pointers, so we'll
 347           * collect the matching entry later.  Just make sure it is unique.
 348           */
 349          assert(!dst_match);
 350          dst_match = iter->dst;
 351       } else if (comp & nir_derefs_may_alias_bit) {
 352          copy_entry_remove(copies, iter);
 353       }
 354    }
 355
 356    struct copy_entry *entry = NULL;
 357    if (dst_match) {
 358       util_dynarray_foreach(copies, struct copy_entry, iter) {
 359          if (iter->dst == dst_match) {
 360             entry = iter;
 361             break;
 362          }
 363       }
 364       assert(entry);
 365    }
 366    return entry;
 367 }
 368
 369 static void
 370 kill_aliases(struct util_dynarray *copies,
 371              nir_deref_instr *deref,
 372              unsigned write_mask)
 373 {
 374    /* TODO: Take into account the write_mask. */
 375
 376    struct copy_entry *entry =
 377       lookup_entry_and_kill_aliases(copies, deref, write_mask);
 378    if (entry)
 379       copy_entry_remove(copies, entry);
 380 }
 381
 382 static struct copy_entry *
 383 get_entry_and_kill_aliases(struct util_dynarray *copies,
 384                            nir_deref_instr *deref,
 385                            unsigned write_mask)
 386 {
 387    /* TODO: Take into account the write_mask. */
 388
 389    struct copy_entry *entry =
 390       lookup_entry_and_kill_aliases(copies, deref, write_mask);
 391
 392    if (entry == NULL)
 393       entry = copy_entry_create(copies, deref);
 394
 395    return entry;
 396 }
 397
 398 static void
 399 apply_barrier_for_modes(struct util_dynarray *copies,
 400                         nir_variable_mode modes)
 401 {
 402    util_dynarray_foreach_reverse(copies, struct copy_entry, iter) {
 403       if ((iter->dst->mode & modes) ||
 404           (!iter->src.is_ssa && (iter->src.deref->mode & modes)))
 405          copy_entry_remove(copies, iter);
 406    }
 407 }
 408
 409 static void
 410 value_set_from_value(struct value *value, const struct value *from,
 411                      unsigned base_index, unsigned write_mask)
 412 {
 413    /* We can't have non-zero indexes with non-trivial write masks */
 414    assert(base_index == 0 || write_mask == 1);
 415
 416    if (from->is_ssa) {
 417       /* Clear value if it was being used as non-SSA. */
 418       if (!value->is_ssa)
 419          memset(&value->ssa, 0, sizeof(value->ssa));
 420       value->is_ssa = true;
 421       /* Only overwrite the written components */
 422       for (unsigned i = 0; i < NIR_MAX_VEC_COMPONENTS; i++) {
 423          if (write_mask & (1 << i)) {
 424             value->ssa.def[base_index + i] = from->ssa.def[i];
 425             value->ssa.component[base_index + i] = from->ssa.component[i];
 426          }
 427       }
 428    } else {
 429       /* Non-ssa stores always write everything */
 430       value->is_ssa = false;
 431       value->deref = from->deref;
 432    }
 433 }
 434
 435 /* Try to load a single element of a vector from the copy_entry.  If the data
 436  * isn't available, just let the original intrinsic do the work.
 437  */
 438 static bool
 439 load_element_from_ssa_entry_value(struct copy_prop_var_state *state,
 440                                   struct copy_entry *entry,
 441                                   nir_builder *b, nir_intrinsic_instr *intrin,
 442                                   struct value *value, unsigned index)
 443 {
 444    assert(index < glsl_get_vector_elements(entry->dst->type));
 445
 446    /* We don't have the element available, so let the instruction do the work. */
 447    if (!entry->src.ssa.def[index])
 448       return false;
 449
 450    b->cursor = nir_instr_remove(&intrin->instr);
 451    intrin->instr.block = NULL;
 452
 453    assert(entry->src.ssa.component[index] <
 454           entry->src.ssa.def[index]->num_components);
 455    nir_ssa_def *def = nir_channel(b, entry->src.ssa.def[index],
 456                                      entry->src.ssa.component[index]);
 457
 458    *value = (struct value) {
 459       .is_ssa = true,
 460       {
 461         .ssa = {
 462           .def = { def },
 463           .component = { 0 },
 464         },
 465       }
 466    };
 467
 468    return true;
 469 }
 470
 471 /* Do a "load" from an SSA-based entry return it in "value" as a value with a
 472  * single SSA def.  Because an entry could reference multiple different SSA
 473  * defs, a vecN operation may be inserted to combine them into a single SSA
 474  * def before handing it back to the caller.  If the load instruction is no
 475  * longer needed, it is removed and nir_instr::block is set to NULL.  (It is
 476  * possible, in some cases, for the load to be used in the vecN operation in
 477  * which case it isn't deleted.)
 478  */
 479 static bool
 480 load_from_ssa_entry_value(struct copy_prop_var_state *state,
 481                           struct copy_entry *entry,
 482                           nir_builder *b, nir_intrinsic_instr *intrin,
 483                           nir_deref_instr *src, struct value *value)
 484 {
 485    if (is_array_deref_of_vector(src)) {
 486       if (nir_src_is_const(src->arr.index)) {
 487          return load_element_from_ssa_entry_value(state, entry, b, intrin, value,
 488                                                   nir_src_as_uint(src->arr.index));
 489       }
 490
 491       /* An SSA copy_entry for the vector won't help indirect load. */
 492       if (glsl_type_is_vector(entry->dst->type)) {
 493          assert(entry->dst->type == nir_deref_instr_parent(src)->type);
 494          /* TODO: If all SSA entries are there, try an if-ladder. */
 495          return false;
 496       }
 497    }
 498
 499    *value = entry->src;
 500    assert(value->is_ssa);
 501
 502    const struct glsl_type *type = entry->dst->type;
 503    unsigned num_components = glsl_get_vector_elements(type);
 504
 505    nir_component_mask_t available = 0;
 506    bool all_same = true;
 507    for (unsigned i = 0; i < num_components; i++) {
 508       if (value->ssa.def[i])
 509          available |= (1 << i);
 510
 511       if (value->ssa.def[i] != value->ssa.def[0])
 512          all_same = false;
 513
 514       if (value->ssa.component[i] != i)
 515          all_same = false;
 516    }
 517
 518    if (all_same) {
 519       /* Our work here is done */
 520       b->cursor = nir_instr_remove(&intrin->instr);
 521       intrin->instr.block = NULL;
 522       return true;
 523    }
 524
 525    if (available != (1 << num_components) - 1 &&
 526        intrin->intrinsic == nir_intrinsic_load_deref &&
 527        (available & nir_ssa_def_components_read(&intrin->dest.ssa)) == 0) {
 528       /* If none of the components read are available as SSA values, then we
 529        * should just bail.  Otherwise, we would end up replacing the uses of
 530        * the load_deref a vecN() that just gathers up its components.
 531        */
 532       return false;
 533    }
 534
 535    b->cursor = nir_after_instr(&intrin->instr);
 536
 537    nir_ssa_def *load_def =
 538       intrin->intrinsic == nir_intrinsic_load_deref ? &intrin->dest.ssa : NULL;
 539
 540    bool keep_intrin = false;
 541    nir_ssa_def *comps[NIR_MAX_VEC_COMPONENTS];
 542    for (unsigned i = 0; i < num_components; i++) {
 543       if (value->ssa.def[i]) {
 544          comps[i] = nir_channel(b, value->ssa.def[i], value->ssa.component[i]);
 545       } else {
 546          /* We don't have anything for this component in our
 547           * list.  Just re-use a channel from the load.
 548           */
 549          if (load_def == NULL)
 550             load_def = nir_load_deref(b, entry->dst);
 551
 552          if (load_def->parent_instr == &intrin->instr)
 553             keep_intrin = true;
 554
 555          comps[i] = nir_channel(b, load_def, i);
 556       }
 557    }
 558
 559    nir_ssa_def *vec = nir_vec(b, comps, num_components);
 560    value_set_ssa_components(value, vec, num_components);
 561
 562    if (!keep_intrin) {
 563       /* Removing this instruction should not touch the cursor because we
 564        * created the cursor after the intrinsic and have added at least one
 565        * instruction (the vec) since then.
 566        */
 567       assert(b->cursor.instr != &intrin->instr);
 568       nir_instr_remove(&intrin->instr);
 569       intrin->instr.block = NULL;
 570    }
 571
 572    return true;
 573 }
 574
 575 /**
 576  * Specialize the wildcards in a deref chain
 577  *
 578  * This function returns a deref chain identical to \param deref except that
 579  * some of its wildcards are replaced with indices from \param specific.  The
 580  * process is guided by \param guide which references the same type as \param
 581  * specific but has the same wildcard array lengths as \param deref.
 582  */
 583 static nir_deref_instr *
 584 specialize_wildcards(nir_builder *b,
 585                      nir_deref_path *deref,
 586                      nir_deref_path *guide,
 587                      nir_deref_path *specific)
 588 {
 589    nir_deref_instr **deref_p = &deref->path[1];
 590    nir_deref_instr **guide_p = &guide->path[1];
 591    nir_deref_instr **spec_p = &specific->path[1];
 592    nir_deref_instr *ret_tail = deref->path[0];
 593    for (; *deref_p; deref_p++) {
 594       if ((*deref_p)->deref_type == nir_deref_type_array_wildcard) {
 595          /* This is where things get tricky.  We have to search through
 596           * the entry deref to find its corresponding wildcard and fill
 597           * this slot in with the value from the src.
 598           */
 599          while (*guide_p &&
 600                 (*guide_p)->deref_type != nir_deref_type_array_wildcard) {
 601             guide_p++;
 602             spec_p++;
 603          }
 604          assert(*guide_p && *spec_p);
 605
 606          ret_tail = nir_build_deref_follower(b, ret_tail, *spec_p);
 607
 608          guide_p++;
 609          spec_p++;
 610       } else {
 611          ret_tail = nir_build_deref_follower(b, ret_tail, *deref_p);
 612       }
 613    }
 614
 615    return ret_tail;
 616 }
 617
 618 /* Do a "load" from an deref-based entry return it in "value" as a value.  The
 619  * deref returned in "value" will always be a fresh copy so the caller can
 620  * steal it and assign it to the instruction directly without copying it
 621  * again.
 622  */
 623 static bool
 624 load_from_deref_entry_value(struct copy_prop_var_state *state,
 625                             struct copy_entry *entry,
 626                             nir_builder *b, nir_intrinsic_instr *intrin,
 627                             nir_deref_instr *src, struct value *value)
 628 {
 629    *value = entry->src;
 630
 631    b->cursor = nir_instr_remove(&intrin->instr);
 632
 633    nir_deref_path entry_dst_path, src_path;
 634    nir_deref_path_init(&entry_dst_path, entry->dst, state->mem_ctx);
 635    nir_deref_path_init(&src_path, src, state->mem_ctx);
 636
 637    bool need_to_specialize_wildcards = false;
 638    nir_deref_instr **entry_p = &entry_dst_path.path[1];
 639    nir_deref_instr **src_p = &src_path.path[1];
 640    while (*entry_p && *src_p) {
 641       nir_deref_instr *entry_tail = *entry_p++;
 642       nir_deref_instr *src_tail = *src_p++;
 643
 644       if (src_tail->deref_type == nir_deref_type_array &&
 645           entry_tail->deref_type == nir_deref_type_array_wildcard)
 646          need_to_specialize_wildcards = true;
 647    }
 648
 649    /* If the entry deref is longer than the source deref then it refers to a
 650     * smaller type and we can't source from it.
 651     */
 652    assert(*entry_p == NULL);
 653
 654    if (need_to_specialize_wildcards) {
 655       /* The entry has some wildcards that are not in src.  This means we need
 656        * to construct a new deref based on the entry but using the wildcards
 657        * from the source and guided by the entry dst.  Oof.
 658        */
 659       nir_deref_path entry_src_path;
 660       nir_deref_path_init(&entry_src_path, entry->src.deref, state->mem_ctx);
 661       value->deref = specialize_wildcards(b, &entry_src_path,
 662                                           &entry_dst_path, &src_path);
 663       nir_deref_path_finish(&entry_src_path);
 664    }
 665
 666    /* If our source deref is longer than the entry deref, that's ok because
 667     * it just means the entry deref needs to be extended a bit.
 668     */
 669    while (*src_p) {
 670       nir_deref_instr *src_tail = *src_p++;
 671       value->deref = nir_build_deref_follower(b, value->deref, src_tail);
 672    }
 673
 674    nir_deref_path_finish(&entry_dst_path);
 675    nir_deref_path_finish(&src_path);
 676
 677    return true;
 678 }
 679
 680 static bool
 681 try_load_from_entry(struct copy_prop_var_state *state, struct copy_entry *entry,
 682                     nir_builder *b, nir_intrinsic_instr *intrin,
 683                     nir_deref_instr *src, struct value *value)
 684 {
 685    if (entry == NULL)
 686       return false;
 687
 688    if (entry->src.is_ssa) {
 689       return load_from_ssa_entry_value(state, entry, b, intrin, src, value);
 690    } else {
 691       return load_from_deref_entry_value(state, entry, b, intrin, src, value);
 692    }
 693 }
 694
 695 static void
 696 invalidate_copies_for_cf_node(struct copy_prop_var_state *state,
 697                               struct util_dynarray *copies,
 698                               nir_cf_node *cf_node)
 699 {
 700    struct hash_entry *ht_entry = _mesa_hash_table_search(state->vars_written_map, cf_node);
 701    assert(ht_entry);
 702
 703    struct vars_written *written = ht_entry->data;
 704    if (written->modes) {
 705       util_dynarray_foreach_reverse(copies, struct copy_entry, entry) {
 706          if (entry->dst->mode & written->modes)
 707             copy_entry_remove(copies, entry);
 708       }
 709    }
 710
 711    hash_table_foreach (written->derefs, entry) {
 712       nir_deref_instr *deref_written = (nir_deref_instr *)entry->key;
 713       kill_aliases(copies, deref_written, (uintptr_t)entry->data);
 714    }
 715 }
 716
 717 static void
 718 print_value(struct value *value, unsigned num_components)
 719 {
 720    if (!value->is_ssa) {
 721       printf(" %s ", glsl_get_type_name(value->deref->type));
 722       nir_print_deref(value->deref, stdout);
 723       return;
 724    }
 725
 726    bool same_ssa = true;
 727    for (unsigned i = 0; i < num_components; i++) {
 728       if (value->ssa.component[i] != i ||
 729           (i > 0 && value->ssa.def[i - 1] != value->ssa.def[i])) {
 730          same_ssa = false;
 731          break;
 732       }
 733    }
 734    if (same_ssa) {
 735       printf(" ssa_%d", value->ssa.def[0]->index);
 736    } else {
 737       for (int i = 0; i < num_components; i++) {
 738          if (value->ssa.def[i])
 739             printf(" ssa_%d[%u]", value->ssa.def[i]->index, value->ssa.component[i]);
 740          else
 741             printf(" _");
 742       }
 743    }
 744 }
 745
 746 static void
 747 print_copy_entry(struct copy_entry *entry)
 748 {
 749    printf("    %s ", glsl_get_type_name(entry->dst->type));
 750    nir_print_deref(entry->dst, stdout);
 751    printf(":\t");
 752
 753    unsigned num_components = glsl_get_vector_elements(entry->dst->type);
 754    print_value(&entry->src, num_components);
 755    printf("\n");
 756 }
 757
 758 static void
 759 dump_instr(nir_instr *instr)
 760 {
 761    printf("  ");
 762    nir_print_instr(instr, stdout);
 763    printf("\n");
 764 }
 765
 766 static void
 767 dump_copy_entries(struct util_dynarray *copies)
 768 {
 769    util_dynarray_foreach(copies, struct copy_entry, iter)
 770       print_copy_entry(iter);
 771    printf("\n");
 772 }
 773
 774 static void
 775 copy_prop_vars_block(struct copy_prop_var_state *state,
 776                      nir_builder *b, nir_block *block,
 777                      struct util_dynarray *copies)
 778 {
 779    if (debug) {
 780       printf("# block%d\n", block->index);
 781       dump_copy_entries(copies);
 782    }
 783
 784    nir_foreach_instr_safe(instr, block) {
 785       if (debug && instr->type == nir_instr_type_deref)
 786          dump_instr(instr);
 787
 788       if (instr->type == nir_instr_type_call) {
 789          if (debug) dump_instr(instr);
 790          apply_barrier_for_modes(copies, nir_var_shader_out |
 791                                          nir_var_shader_temp |
 792                                          nir_var_function_temp |
 793                                          nir_var_mem_ssbo |
 794                                          nir_var_mem_shared |
 795                                          nir_var_mem_global);
 796          if (debug) dump_copy_entries(copies);
 797          continue;
 798       }
 799
 800       if (instr->type != nir_instr_type_intrinsic)
 801          continue;
 802
 803       nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
 804       switch (intrin->intrinsic) {
 805       case nir_intrinsic_control_barrier:
 806       case nir_intrinsic_memory_barrier:
 807          if (debug) dump_instr(instr);
 808
 809          apply_barrier_for_modes(copies, nir_var_shader_out |
 810                                          nir_var_mem_ssbo |
 811                                          nir_var_mem_shared |
 812                                          nir_var_mem_global);
 813          break;
 814
 815       case nir_intrinsic_memory_barrier_buffer:
 816          if (debug) dump_instr(instr);
 817
 818          apply_barrier_for_modes(copies, nir_var_mem_ssbo |
 819                                          nir_var_mem_global);
 820          break;
 821
 822       case nir_intrinsic_memory_barrier_shared:
 823          if (debug) dump_instr(instr);
 824
 825          apply_barrier_for_modes(copies, nir_var_mem_shared);
 826          break;
 827
 828       case nir_intrinsic_memory_barrier_tcs_patch:
 829          if (debug) dump_instr(instr);
 830
 831          apply_barrier_for_modes(copies, nir_var_shader_out);
 832          break;
 833
 834       case nir_intrinsic_scoped_barrier:
 835          if (debug) dump_instr(instr);
 836
 837          if (nir_intrinsic_memory_semantics(intrin) & NIR_MEMORY_ACQUIRE)
 838             apply_barrier_for_modes(copies, nir_intrinsic_memory_modes(intrin));
 839          break;
 840
 841       case nir_intrinsic_emit_vertex:
 842       case nir_intrinsic_emit_vertex_with_counter:
 843          if (debug) dump_instr(instr);
 844
 845          apply_barrier_for_modes(copies, nir_var_shader_out);
 846          break;
 847
 848       case nir_intrinsic_load_deref: {
 849          if (debug) dump_instr(instr);
 850
 851          if (nir_intrinsic_access(intrin) & ACCESS_VOLATILE)
 852             break;
 853
 854          nir_deref_instr *src = nir_src_as_deref(intrin->src[0]);
 855
 856          /* Direct array_derefs of vectors operate on the vectors (the parent
 857           * deref).  Indirects will be handled like other derefs.
 858           */
 859          int vec_index = 0;
 860          nir_deref_instr *vec_src = src;
 861          if (is_array_deref_of_vector(src) && nir_src_is_const(src->arr.index)) {
 862             vec_src = nir_deref_instr_parent(src);
 863             unsigned vec_comps = glsl_get_vector_elements(vec_src->type);
 864             vec_index = nir_src_as_uint(src->arr.index);
 865
 866             /* Loading from an invalid index yields an undef */
 867             if (vec_index >= vec_comps) {
 868                b->cursor = nir_instr_remove(instr);
 869                nir_ssa_def *u = nir_ssa_undef(b, 1, intrin->dest.ssa.bit_size);
 870                nir_ssa_def_rewrite_uses(&intrin->dest.ssa, nir_src_for_ssa(u));
 871                state->progress = true;
 872                break;
 873             }
 874          }
 875
 876          struct copy_entry *src_entry =
 877             lookup_entry_for_deref(copies, src, nir_derefs_a_contains_b_bit);
 878          struct value value = {0};
 879          if (try_load_from_entry(state, src_entry, b, intrin, src, &value)) {
 880             if (value.is_ssa) {
 881                /* lookup_load has already ensured that we get a single SSA
 882                 * value that has all of the channels.  We just have to do the
 883                 * rewrite operation.  Note for array derefs of vectors, the
 884                 * channel 0 is used.
 885                 */
 886                if (intrin->instr.block) {
 887                   /* The lookup left our instruction in-place.  This means it
 888                    * must have used it to vec up a bunch of different sources.
 889                    * We need to be careful when rewriting uses so we don't
 890                    * rewrite the vecN itself.
 891                    */
 892                   nir_ssa_def_rewrite_uses_after(&intrin->dest.ssa,
 893                                                  nir_src_for_ssa(value.ssa.def[0]),
 894                                                  value.ssa.def[0]->parent_instr);
 895                } else {
 896                   nir_ssa_def_rewrite_uses(&intrin->dest.ssa,
 897                                            nir_src_for_ssa(value.ssa.def[0]));
 898                }
 899             } else {
 900                /* We're turning it into a load of a different variable */
 901                intrin->src[0] = nir_src_for_ssa(&value.deref->dest.ssa);
 902
 903                /* Put it back in again. */
 904                nir_builder_instr_insert(b, instr);
 905                value_set_ssa_components(&value, &intrin->dest.ssa,
 906                                         intrin->num_components);
 907             }
 908             state->progress = true;
 909          } else {
 910             value_set_ssa_components(&value, &intrin->dest.ssa,
 911                                      intrin->num_components);
 912          }
 913
 914          /* Now that we have a value, we're going to store it back so that we
 915           * have the right value next time we come looking for it.  In order
 916           * to do this, we need an exact match, not just something that
 917           * contains what we're looking for.
 918           */
 919          struct copy_entry *entry =
 920             lookup_entry_for_deref(copies, vec_src, nir_derefs_equal_bit);
 921          if (!entry)
 922             entry = copy_entry_create(copies, vec_src);
 923
 924          /* Update the entry with the value of the load.  This way
 925           * we can potentially remove subsequent loads.
 926           */
 927          value_set_from_value(&entry->src, &value, vec_index,
 928                               (1 << intrin->num_components) - 1);
 929          break;
 930       }
 931
 932       case nir_intrinsic_store_deref: {
 933          if (debug) dump_instr(instr);
 934
 935          nir_deref_instr *dst = nir_src_as_deref(intrin->src[0]);
 936          assert(glsl_type_is_vector_or_scalar(dst->type));
 937
 938          /* Direct array_derefs of vectors operate on the vectors (the parent
 939           * deref).  Indirects will be handled like other derefs.
 940           */
 941          int vec_index = 0;
 942          nir_deref_instr *vec_dst = dst;
 943          if (is_array_deref_of_vector(dst) && nir_src_is_const(dst->arr.index)) {
 944             vec_dst = nir_deref_instr_parent(dst);
 945             unsigned vec_comps = glsl_get_vector_elements(vec_dst->type);
 946
 947             vec_index = nir_src_as_uint(dst->arr.index);
 948
 949             /* Storing to an invalid index is a no-op. */
 950             if (vec_index >= vec_comps) {
 951                nir_instr_remove(instr);
 952                state->progress = true;
 953                break;
 954             }
 955          }
 956
 957          if (nir_intrinsic_access(intrin) & ACCESS_VOLATILE) {
 958             unsigned wrmask = nir_intrinsic_write_mask(intrin);
 959             kill_aliases(copies, dst, wrmask);
 960             break;
 961          }
 962
 963          struct copy_entry *entry =
 964             lookup_entry_for_deref(copies, dst, nir_derefs_equal_bit);
 965          if (entry && value_equals_store_src(&entry->src, intrin)) {
 966             /* If we are storing the value from a load of the same var the
 967              * store is redundant so remove it.
 968              */
 969             nir_instr_remove(instr);
 970             state->progress = true;
 971          } else {
 972             struct value value = {0};
 973             value_set_ssa_components(&value, intrin->src[1].ssa,
 974                                      intrin->num_components);
 975             unsigned wrmask = nir_intrinsic_write_mask(intrin);
 976             struct copy_entry *entry =
 977                get_entry_and_kill_aliases(copies, vec_dst, wrmask);
 978             value_set_from_value(&entry->src, &value, vec_index, wrmask);
 979          }
 980
 981          break;
 982       }
 983
 984       case nir_intrinsic_copy_deref: {
 985          if (debug) dump_instr(instr);
 986
 987          nir_deref_instr *dst = nir_src_as_deref(intrin->src[0]);
 988          nir_deref_instr *src = nir_src_as_deref(intrin->src[1]);
 989
 990          /* The copy_deref intrinsic doesn't keep track of num_components, so
 991           * get it ourselves.
 992           */
 993          unsigned num_components = glsl_get_vector_elements(dst->type);
 994          unsigned full_mask = (1 << num_components) - 1;
 995
 996          if ((nir_intrinsic_src_access(intrin) & ACCESS_VOLATILE) ||
 997              (nir_intrinsic_dst_access(intrin) & ACCESS_VOLATILE)) {
 998             kill_aliases(copies, dst, full_mask);
 999             break;
1000          }
1001
1002          if (nir_compare_derefs(src, dst) & nir_derefs_equal_bit) {
1003             /* This is a no-op self-copy.  Get rid of it */
1004             nir_instr_remove(instr);
1005             state->progress = true;
1006             continue;
1007          }
1008
1009          /* Copy of direct array derefs of vectors are not handled.  Just
1010           * invalidate what's written and bail.
1011           */
1012          if ((is_array_deref_of_vector(src) && nir_src_is_const(src->arr.index)) ||
1013              (is_array_deref_of_vector(dst) && nir_src_is_const(dst->arr.index))) {
1014             kill_aliases(copies, dst, full_mask);
1015             break;
1016          }
1017
1018          struct copy_entry *src_entry =
1019             lookup_entry_for_deref(copies, src, nir_derefs_a_contains_b_bit);
1020          struct value value;
1021          if (try_load_from_entry(state, src_entry, b, intrin, src, &value)) {
1022             /* If load works, intrin (the copy_deref) is removed. */
1023             if (value.is_ssa) {
1024                nir_store_deref(b, dst, value.ssa.def[0], full_mask);
1025             } else {
1026                /* If this would be a no-op self-copy, don't bother. */
1027                if (nir_compare_derefs(value.deref, dst) & nir_derefs_equal_bit)
1028                   continue;
1029
1030                /* Just turn it into a copy of a different deref */
1031                intrin->src[1] = nir_src_for_ssa(&value.deref->dest.ssa);
1032
1033                /* Put it back in again. */
1034                nir_builder_instr_insert(b, instr);
1035             }
1036
1037             state->progress = true;
1038          } else {
1039             value = (struct value) {
1040                .is_ssa = false,
1041                { .deref = src },
1042             };
1043          }
1044
1045          nir_variable *src_var = nir_deref_instr_get_variable(src);
1046          if (src_var && src_var->data.cannot_coalesce) {
1047             /* The source cannot be coaleseced, which means we can't propagate
1048              * this copy.
1049              */
1050             break;
1051          }
1052
1053          struct copy_entry *dst_entry =
1054             get_entry_and_kill_aliases(copies, dst, full_mask);
1055          value_set_from_value(&dst_entry->src, &value, 0, full_mask);
1056          break;
1057       }
1058
1059       case nir_intrinsic_deref_atomic_add:
1060       case nir_intrinsic_deref_atomic_imin:
1061       case nir_intrinsic_deref_atomic_umin:
1062       case nir_intrinsic_deref_atomic_imax:
1063       case nir_intrinsic_deref_atomic_umax:
1064       case nir_intrinsic_deref_atomic_and:
1065       case nir_intrinsic_deref_atomic_or:
1066       case nir_intrinsic_deref_atomic_xor:
1067       case nir_intrinsic_deref_atomic_exchange:
1068       case nir_intrinsic_deref_atomic_comp_swap:
1069          if (debug) dump_instr(instr);
1070
1071          nir_deref_instr *dst = nir_src_as_deref(intrin->src[0]);
1072          unsigned num_components = glsl_get_vector_elements(dst->type);
1073          unsigned full_mask = (1 << num_components) - 1;
1074          kill_aliases(copies, dst, full_mask);
1075          break;
1076
1077       default:
1078          continue; /* To skip the debug below. */
1079       }
1080
1081       if (debug) dump_copy_entries(copies);
1082    }
1083 }
1084
1085 static void
1086 copy_prop_vars_cf_node(struct copy_prop_var_state *state,
1087                        struct util_dynarray *copies,
1088                        nir_cf_node *cf_node)
1089 {
1090    switch (cf_node->type) {
1091    case nir_cf_node_function: {
1092       nir_function_impl *impl = nir_cf_node_as_function(cf_node);
1093
1094       struct util_dynarray impl_copies;
1095       util_dynarray_init(&impl_copies, state->mem_ctx);
1096
1097       foreach_list_typed_safe(nir_cf_node, cf_node, node, &impl->body)
1098          copy_prop_vars_cf_node(state, &impl_copies, cf_node);
1099
1100       break;
1101    }
1102
1103    case nir_cf_node_block: {
1104       nir_block *block = nir_cf_node_as_block(cf_node);
1105       nir_builder b;
1106       nir_builder_init(&b, state->impl);
1107       copy_prop_vars_block(state, &b, block, copies);
1108       break;
1109    }
1110
1111    case nir_cf_node_if: {
1112       nir_if *if_stmt = nir_cf_node_as_if(cf_node);
1113
1114       /* Clone the copies for each branch of the if statement.  The idea is
1115        * that they both see the same state of available copies, but do not
1116        * interfere to each other.
1117        */
1118
1119       struct util_dynarray then_copies;
1120       util_dynarray_clone(&then_copies, state->mem_ctx, copies);
1121
1122       struct util_dynarray else_copies;
1123       util_dynarray_clone(&else_copies, state->mem_ctx, copies);
1124
1125       foreach_list_typed_safe(nir_cf_node, cf_node, node, &if_stmt->then_list)
1126          copy_prop_vars_cf_node(state, &then_copies, cf_node);
1127
1128       foreach_list_typed_safe(nir_cf_node, cf_node, node, &if_stmt->else_list)
1129          copy_prop_vars_cf_node(state, &else_copies, cf_node);
1130
1131       /* Both branches copies can be ignored, since the effect of running both
1132        * branches was captured in the first pass that collects vars_written.
1133        */
1134
1135       invalidate_copies_for_cf_node(state, copies, cf_node);
1136
1137       break;
1138    }
1139
1140    case nir_cf_node_loop: {
1141       nir_loop *loop = nir_cf_node_as_loop(cf_node);
1142
1143       /* Invalidate before cloning the copies for the loop, since the loop
1144        * body can be executed more than once.
1145        */
1146
1147       invalidate_copies_for_cf_node(state, copies, cf_node);
1148
1149       struct util_dynarray loop_copies;
1150       util_dynarray_clone(&loop_copies, state->mem_ctx, copies);
1151
1152       foreach_list_typed_safe(nir_cf_node, cf_node, node, &loop->body)
1153          copy_prop_vars_cf_node(state, &loop_copies, cf_node);
1154
1155       break;
1156    }
1157
1158    default:
1159       unreachable("Invalid CF node type");
1160    }
1161 }
1162
1163 static bool
1164 nir_copy_prop_vars_impl(nir_function_impl *impl)
1165 {
1166    void *mem_ctx = ralloc_context(NULL);
1167
1168    if (debug) {
1169       nir_metadata_require(impl, nir_metadata_block_index);
1170       printf("## nir_copy_prop_vars_impl for %s\n", impl->function->name);
1171    }
1172
1173    struct copy_prop_var_state state = {
1174       .impl = impl,
1175       .mem_ctx = mem_ctx,
1176       .lin_ctx = linear_zalloc_parent(mem_ctx, 0),
1177
1178       .vars_written_map = _mesa_pointer_hash_table_create(mem_ctx),
1179    };
1180
1181    gather_vars_written(&state, NULL, &impl->cf_node);
1182
1183    copy_prop_vars_cf_node(&state, NULL, &impl->cf_node);
1184
1185    if (state.progress) {
1186       nir_metadata_preserve(impl, nir_metadata_block_index |
1187                                   nir_metadata_dominance);
1188    } else {
1189       nir_metadata_preserve(impl, nir_metadata_all);
1190    }
1191
1192    ralloc_free(mem_ctx);
1193    return state.progress;
1194 }
1195
1196 bool
1197 nir_opt_copy_prop_vars(nir_shader *shader)
1198 {
1199    bool progress = false;
1200
1201    nir_foreach_function(function, shader) {
1202       if (!function->impl)
1203          continue;
1204       progress |= nir_copy_prop_vars_impl(function->impl);
1205    }
1206
1207    return progress;
1208 }