src/compiler/nir/nir_lower_vars_to_ssa.c

   1 /*
   2  * Copyright © 2014 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  * Authors:
  24  *    Jason Ekstrand (jason@jlekstrand.net)
  25  *
  26  */
  27
  28 #include "nir.h"
  29 #include "nir_builder.h"
  30 #include "nir_phi_builder.h"
  31 #include "nir_vla.h"
  32
  33
  34 struct deref_node {
  35    struct deref_node *parent;
  36    const struct glsl_type *type;
  37
  38    bool lower_to_ssa;
  39
  40    /* Only valid for things that end up in the direct list.
  41     * Note that multiple nir_deref_vars may correspond to this node, but they
  42     * will all be equivalent, so any is as good as the other.
  43     */
  44    nir_deref_var *deref;
  45    struct exec_node direct_derefs_link;
  46
  47    struct set *loads;
  48    struct set *stores;
  49    struct set *copies;
  50
  51    struct nir_phi_builder_value *pb_value;
  52
  53    struct deref_node *wildcard;
  54    struct deref_node *indirect;
  55    struct deref_node *children[0];
  56 };
  57
  58 struct lower_variables_state {
  59    nir_shader *shader;
  60    void *dead_ctx;
  61    nir_function_impl *impl;
  62
  63    /* A hash table mapping variables to deref_node data */
  64    struct hash_table *deref_var_nodes;
  65
  66    /* A hash table mapping fully-qualified direct dereferences, i.e.
  67     * dereferences with no indirect or wildcard array dereferences, to
  68     * deref_node data.
  69     *
  70     * At the moment, we only lower loads, stores, and copies that can be
  71     * trivially lowered to loads and stores, i.e. copies with no indirects
  72     * and no wildcards.  If a part of a variable that is being loaded from
  73     * and/or stored into is also involved in a copy operation with
  74     * wildcards, then we lower that copy operation to loads and stores, but
  75     * otherwise we leave copies with wildcards alone. Since the only derefs
  76     * used in these loads, stores, and trivial copies are ones with no
  77     * wildcards and no indirects, these are precisely the derefs that we
  78     * can actually consider lowering.
  79     */
  80    struct exec_list direct_deref_nodes;
  81
  82    /* Controls whether get_deref_node will add variables to the
  83     * direct_deref_nodes table.  This is turned on when we are initially
  84     * scanning for load/store instructions.  It is then turned off so we
  85     * don't accidentally change the direct_deref_nodes table while we're
  86     * iterating throug it.
  87     */
  88    bool add_to_direct_deref_nodes;
  89
  90    struct nir_phi_builder *phi_builder;
  91 };
  92
  93 static struct deref_node *
  94 deref_node_create(struct deref_node *parent,
  95                   const struct glsl_type *type, nir_shader *shader)
  96 {
  97    size_t size = sizeof(struct deref_node) +
  98                  glsl_get_length(type) * sizeof(struct deref_node *);
  99
 100    struct deref_node *node = rzalloc_size(shader, size);
 101    node->type = type;
 102    node->parent = parent;
 103    node->deref = NULL;
 104    exec_node_init(&node->direct_derefs_link);
 105
 106    return node;
 107 }
 108
 109 /* Returns the deref node associated with the given variable.  This will be
 110  * the root of the tree representing all of the derefs of the given variable.
 111  */
 112 static struct deref_node *
 113 get_deref_node_for_var(nir_variable *var, struct lower_variables_state *state)
 114 {
 115    struct deref_node *node;
 116
 117    struct hash_entry *var_entry =
 118       _mesa_hash_table_search(state->deref_var_nodes, var);
 119
 120    if (var_entry) {
 121       return var_entry->data;
 122    } else {
 123       node = deref_node_create(NULL, var->type, state->dead_ctx);
 124       _mesa_hash_table_insert(state->deref_var_nodes, var, node);
 125       return node;
 126    }
 127 }
 128
 129 /* Gets the deref_node for the given deref chain and creates it if it
 130  * doesn't yet exist.  If the deref is fully-qualified and direct and
 131  * state->add_to_direct_deref_nodes is true, it will be added to the hash
 132  * table of of fully-qualified direct derefs.
 133  */
 134 static struct deref_node *
 135 get_deref_node(nir_deref_var *deref, struct lower_variables_state *state)
 136 {
 137    bool is_direct = true;
 138
 139    /* Start at the base of the chain. */
 140    struct deref_node *node = get_deref_node_for_var(deref->var, state);
 141    assert(deref->deref.type == node->type);
 142
 143    for (nir_deref *tail = deref->deref.child; tail; tail = tail->child) {
 144       switch (tail->deref_type) {
 145       case nir_deref_type_struct: {
 146          nir_deref_struct *deref_struct = nir_deref_as_struct(tail);
 147
 148          assert(deref_struct->index < glsl_get_length(node->type));
 149
 150          if (node->children[deref_struct->index] == NULL)
 151             node->children[deref_struct->index] =
 152                deref_node_create(node, tail->type, state->dead_ctx);
 153
 154          node = node->children[deref_struct->index];
 155          break;
 156       }
 157
 158       case nir_deref_type_array: {
 159          nir_deref_array *arr = nir_deref_as_array(tail);
 160
 161          switch (arr->deref_array_type) {
 162          case nir_deref_array_type_direct:
 163             /* This is possible if a loop unrolls and generates an
 164              * out-of-bounds offset.  We need to handle this at least
 165              * somewhat gracefully.
 166              */
 167             if (arr->base_offset >= glsl_get_length(node->type))
 168                return NULL;
 169
 170             if (node->children[arr->base_offset] == NULL)
 171                node->children[arr->base_offset] =
 172                   deref_node_create(node, tail->type, state->dead_ctx);
 173
 174             node = node->children[arr->base_offset];
 175             break;
 176
 177          case nir_deref_array_type_indirect:
 178             if (node->indirect == NULL)
 179                node->indirect = deref_node_create(node, tail->type,
 180                                                   state->dead_ctx);
 181
 182             node = node->indirect;
 183             is_direct = false;
 184             break;
 185
 186          case nir_deref_array_type_wildcard:
 187             if (node->wildcard == NULL)
 188                node->wildcard = deref_node_create(node, tail->type,
 189                                                   state->dead_ctx);
 190
 191             node = node->wildcard;
 192             is_direct = false;
 193             break;
 194
 195          default:
 196             unreachable("Invalid array deref type");
 197          }
 198          break;
 199       }
 200       default:
 201          unreachable("Invalid deref type");
 202       }
 203    }
 204
 205    assert(node);
 206
 207    /* Only insert if it isn't already in the list. */
 208    if (is_direct && state->add_to_direct_deref_nodes &&
 209        node->direct_derefs_link.next == NULL) {
 210       node->deref = deref;
 211       assert(deref->var != NULL);
 212       exec_list_push_tail(&state->direct_deref_nodes,
 213                           &node->direct_derefs_link);
 214    }
 215
 216    return node;
 217 }
 218
 219 /* \sa foreach_deref_node_match */
 220 static bool
 221 foreach_deref_node_worker(struct deref_node *node, nir_deref *deref,
 222                           bool (* cb)(struct deref_node *node,
 223                                       struct lower_variables_state *state),
 224                           struct lower_variables_state *state)
 225 {
 226    if (deref->child == NULL) {
 227       return cb(node, state);
 228    } else {
 229       switch (deref->child->deref_type) {
 230       case nir_deref_type_array: {
 231          nir_deref_array *arr = nir_deref_as_array(deref->child);
 232          assert(arr->deref_array_type == nir_deref_array_type_direct);
 233          if (node->children[arr->base_offset] &&
 234              !foreach_deref_node_worker(node->children[arr->base_offset],
 235                                         deref->child, cb, state))
 236             return false;
 237
 238          if (node->wildcard &&
 239              !foreach_deref_node_worker(node->wildcard,
 240                                         deref->child, cb, state))
 241             return false;
 242
 243          return true;
 244       }
 245
 246       case nir_deref_type_struct: {
 247          nir_deref_struct *str = nir_deref_as_struct(deref->child);
 248          return foreach_deref_node_worker(node->children[str->index],
 249                                           deref->child, cb, state);
 250       }
 251
 252       default:
 253          unreachable("Invalid deref child type");
 254       }
 255    }
 256 }
 257
 258 /* Walks over every "matching" deref_node and calls the callback.  A node
 259  * is considered to "match" if either refers to that deref or matches up t
 260  * a wildcard.  In other words, the following would match a[6].foo[3].bar:
 261  *
 262  * a[6].foo[3].bar
 263  * a[*].foo[3].bar
 264  * a[6].foo[*].bar
 265  * a[*].foo[*].bar
 266  *
 267  * The given deref must be a full-length and fully qualified (no wildcards
 268  * or indirects) deref chain.
 269  */
 270 static bool
 271 foreach_deref_node_match(nir_deref_var *deref,
 272                          bool (* cb)(struct deref_node *node,
 273                                      struct lower_variables_state *state),
 274                          struct lower_variables_state *state)
 275 {
 276    nir_deref_var var_deref = *deref;
 277    var_deref.deref.child = NULL;
 278    struct deref_node *node = get_deref_node(&var_deref, state);
 279
 280    if (node == NULL)
 281       return false;
 282
 283    return foreach_deref_node_worker(node, &deref->deref, cb, state);
 284 }
 285
 286 /* \sa deref_may_be_aliased */
 287 static bool
 288 deref_may_be_aliased_node(struct deref_node *node, nir_deref *deref,
 289                           struct lower_variables_state *state)
 290 {
 291    if (deref->child == NULL) {
 292       return false;
 293    } else {
 294       switch (deref->child->deref_type) {
 295       case nir_deref_type_array: {
 296          nir_deref_array *arr = nir_deref_as_array(deref->child);
 297          if (arr->deref_array_type == nir_deref_array_type_indirect)
 298             return true;
 299
 300          /* If there is an indirect at this level, we're aliased. */
 301          if (node->indirect)
 302             return true;
 303
 304          assert(arr->deref_array_type == nir_deref_array_type_direct);
 305
 306          if (node->children[arr->base_offset] &&
 307              deref_may_be_aliased_node(node->children[arr->base_offset],
 308                                        deref->child, state))
 309             return true;
 310
 311          if (node->wildcard &&
 312              deref_may_be_aliased_node(node->wildcard, deref->child, state))
 313             return true;
 314
 315          return false;
 316       }
 317
 318       case nir_deref_type_struct: {
 319          nir_deref_struct *str = nir_deref_as_struct(deref->child);
 320          if (node->children[str->index]) {
 321              return deref_may_be_aliased_node(node->children[str->index],
 322                                               deref->child, state);
 323          } else {
 324             return false;
 325          }
 326       }
 327
 328       default:
 329          unreachable("Invalid nir_deref child type");
 330       }
 331    }
 332 }
 333
 334 /* Returns true if there are no indirects that can ever touch this deref.
 335  *
 336  * For example, if the given deref is a[6].foo, then any uses of a[i].foo
 337  * would cause this to return false, but a[i].bar would not affect it
 338  * because it's a different structure member.  A var_copy involving of
 339  * a[*].bar also doesn't affect it because that can be lowered to entirely
 340  * direct load/stores.
 341  *
 342  * We only support asking this question about fully-qualified derefs.
 343  * Obviously, it's pointless to ask this about indirects, but we also
 344  * rule-out wildcards.  Handling Wildcard dereferences would involve
 345  * checking each array index to make sure that there aren't any indirect
 346  * references.
 347  */
 348 static bool
 349 deref_may_be_aliased(nir_deref_var *deref,
 350                      struct lower_variables_state *state)
 351 {
 352    return deref_may_be_aliased_node(get_deref_node_for_var(deref->var, state),
 353                                     &deref->deref, state);
 354 }
 355
 356 static void
 357 register_load_instr(nir_intrinsic_instr *load_instr,
 358                     struct lower_variables_state *state)
 359 {
 360    struct deref_node *node = get_deref_node(load_instr->variables[0], state);
 361    if (node == NULL)
 362       return;
 363
 364    if (node->loads == NULL)
 365       node->loads = _mesa_set_create(state->dead_ctx, _mesa_hash_pointer,
 366                                      _mesa_key_pointer_equal);
 367
 368    _mesa_set_add(node->loads, load_instr);
 369 }
 370
 371 static void
 372 register_store_instr(nir_intrinsic_instr *store_instr,
 373                      struct lower_variables_state *state)
 374 {
 375    struct deref_node *node = get_deref_node(store_instr->variables[0], state);
 376    if (node == NULL)
 377       return;
 378
 379    if (node->stores == NULL)
 380       node->stores = _mesa_set_create(state->dead_ctx, _mesa_hash_pointer,
 381                                      _mesa_key_pointer_equal);
 382
 383    _mesa_set_add(node->stores, store_instr);
 384 }
 385
 386 static void
 387 register_copy_instr(nir_intrinsic_instr *copy_instr,
 388                     struct lower_variables_state *state)
 389 {
 390    for (unsigned idx = 0; idx < 2; idx++) {
 391       struct deref_node *node =
 392          get_deref_node(copy_instr->variables[idx], state);
 393
 394       if (node == NULL)
 395          continue;
 396
 397       if (node->copies == NULL)
 398          node->copies = _mesa_set_create(state->dead_ctx, _mesa_hash_pointer,
 399                                          _mesa_key_pointer_equal);
 400
 401       _mesa_set_add(node->copies, copy_instr);
 402    }
 403 }
 404
 405 /* Registers all variable uses in the given block. */
 406 static bool
 407 register_variable_uses_block(nir_block *block,
 408                              struct lower_variables_state *state)
 409 {
 410    nir_foreach_instr_safe(instr, block) {
 411       if (instr->type != nir_instr_type_intrinsic)
 412          continue;
 413
 414       nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
 415
 416       switch (intrin->intrinsic) {
 417       case nir_intrinsic_load_var:
 418          register_load_instr(intrin, state);
 419          break;
 420
 421       case nir_intrinsic_store_var:
 422          register_store_instr(intrin, state);
 423          break;
 424
 425       case nir_intrinsic_copy_var:
 426          register_copy_instr(intrin, state);
 427          break;
 428
 429       default:
 430          continue;
 431       }
 432    }
 433
 434    return true;
 435 }
 436
 437 /* Walks over all of the copy instructions to or from the given deref_node
 438  * and lowers them to load/store intrinsics.
 439  */
 440 static bool
 441 lower_copies_to_load_store(struct deref_node *node,
 442                            struct lower_variables_state *state)
 443 {
 444    if (!node->copies)
 445       return true;
 446
 447    struct set_entry *copy_entry;
 448    set_foreach(node->copies, copy_entry) {
 449       nir_intrinsic_instr *copy = (void *)copy_entry->key;
 450
 451       nir_lower_var_copy_instr(copy, state->shader);
 452
 453       for (unsigned i = 0; i < 2; ++i) {
 454          struct deref_node *arg_node =
 455             get_deref_node(copy->variables[i], state);
 456
 457          /* Only bother removing copy entries for other nodes */
 458          if (arg_node == NULL || arg_node == node)
 459             continue;
 460
 461          struct set_entry *arg_entry = _mesa_set_search(arg_node->copies, copy);
 462          assert(arg_entry);
 463          _mesa_set_remove(node->copies, arg_entry);
 464       }
 465
 466       nir_instr_remove(&copy->instr);
 467    }
 468
 469    node->copies = NULL;
 470
 471    return true;
 472 }
 473
 474 /* Performs variable renaming by doing a DFS of the dominance tree
 475  *
 476  * This algorithm is very similar to the one outlined in "Efficiently
 477  * Computing Static Single Assignment Form and the Control Dependence
 478  * Graph" by Cytron et. al.  The primary difference is that we only put one
 479  * SSA def on the stack per block.
 480  */
 481 static bool
 482 rename_variables_block(nir_block *block, struct lower_variables_state *state)
 483 {
 484    nir_builder b;
 485    nir_builder_init(&b, state->impl);
 486
 487    nir_foreach_instr_safe(instr, block) {
 488       if (instr->type != nir_instr_type_intrinsic)
 489          continue;
 490
 491       nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
 492
 493       switch (intrin->intrinsic) {
 494       case nir_intrinsic_load_var: {
 495          struct deref_node *node =
 496             get_deref_node(intrin->variables[0], state);
 497
 498          if (node == NULL) {
 499             /* If we hit this path then we are referencing an invalid
 500              * value.  Most likely, we unrolled something and are
 501              * reading past the end of some array.  In any case, this
 502              * should result in an undefined value.
 503              */
 504             nir_ssa_undef_instr *undef =
 505                nir_ssa_undef_instr_create(state->shader,
 506                                           intrin->num_components,
 507                                           intrin->dest.ssa.bit_size);
 508
 509             nir_instr_insert_before(&intrin->instr, &undef->instr);
 510             nir_instr_remove(&intrin->instr);
 511
 512             nir_ssa_def_rewrite_uses(&intrin->dest.ssa,
 513                                      nir_src_for_ssa(&undef->def));
 514             continue;
 515          }
 516
 517          if (!node->lower_to_ssa)
 518             continue;
 519
 520          nir_alu_instr *mov = nir_alu_instr_create(state->shader,
 521                                                    nir_op_imov);
 522          mov->src[0].src = nir_src_for_ssa(
 523             nir_phi_builder_value_get_block_def(node->pb_value, block));
 524          for (unsigned i = intrin->num_components; i < 4; i++)
 525             mov->src[0].swizzle[i] = 0;
 526
 527          assert(intrin->dest.is_ssa);
 528
 529          mov->dest.write_mask = (1 << intrin->num_components) - 1;
 530          nir_ssa_dest_init(&mov->instr, &mov->dest.dest,
 531                            intrin->num_components,
 532                            intrin->dest.ssa.bit_size, NULL);
 533
 534          nir_instr_insert_before(&intrin->instr, &mov->instr);
 535          nir_instr_remove(&intrin->instr);
 536
 537          nir_ssa_def_rewrite_uses(&intrin->dest.ssa,
 538                                   nir_src_for_ssa(&mov->dest.dest.ssa));
 539          break;
 540       }
 541
 542       case nir_intrinsic_store_var: {
 543          struct deref_node *node =
 544             get_deref_node(intrin->variables[0], state);
 545
 546          if (node == NULL) {
 547             /* Probably an out-of-bounds array store.  That should be a
 548              * no-op. */
 549             nir_instr_remove(&intrin->instr);
 550             continue;
 551          }
 552
 553          if (!node->lower_to_ssa)
 554             continue;
 555
 556          assert(intrin->num_components ==
 557                 glsl_get_vector_elements(node->type));
 558
 559          assert(intrin->src[0].is_ssa);
 560
 561          nir_ssa_def *new_def;
 562          b.cursor = nir_before_instr(&intrin->instr);
 563
 564          unsigned wrmask = nir_intrinsic_write_mask(intrin);
 565          if (wrmask == (1 << intrin->num_components) - 1) {
 566             /* Whole variable store - just copy the source.  Note that
 567              * intrin->num_components and intrin->src[0].ssa->num_components
 568              * may differ.
 569              */
 570             unsigned swiz[4];
 571             for (unsigned i = 0; i < 4; i++)
 572                swiz[i] = i < intrin->num_components ? i : 0;
 573
 574             new_def = nir_swizzle(&b, intrin->src[0].ssa, swiz,
 575                                   intrin->num_components, false);
 576          } else {
 577             nir_ssa_def *old_def =
 578                nir_phi_builder_value_get_block_def(node->pb_value, block);
 579             /* For writemasked store_var intrinsics, we combine the newly
 580              * written values with the existing contents of unwritten
 581              * channels, creating a new SSA value for the whole vector.
 582              */
 583             nir_ssa_def *srcs[4];
 584             for (unsigned i = 0; i < intrin->num_components; i++) {
 585                if (wrmask & (1 << i)) {
 586                   srcs[i] = nir_channel(&b, intrin->src[0].ssa, i);
 587                } else {
 588                   srcs[i] = nir_channel(&b, old_def, i);
 589                }
 590             }
 591             new_def = nir_vec(&b, srcs, intrin->num_components);
 592          }
 593
 594          assert(new_def->num_components == intrin->num_components);
 595
 596          nir_phi_builder_value_set_block_def(node->pb_value, block, new_def);
 597          nir_instr_remove(&intrin->instr);
 598          break;
 599       }
 600
 601       default:
 602          break;
 603       }
 604    }
 605
 606    for (unsigned i = 0; i < block->num_dom_children; ++i)
 607       rename_variables_block(block->dom_children[i], state);
 608
 609    return true;
 610 }
 611
 612 /** Implements a pass to lower variable uses to SSA values
 613  *
 614  * This path walks the list of instructions and tries to lower as many
 615  * local variable load/store operations to SSA defs and uses as it can.
 616  * The process involves four passes:
 617  *
 618  *  1) Iterate over all of the instructions and mark where each local
 619  *     variable deref is used in a load, store, or copy.  While we're at
 620  *     it, we keep track of all of the fully-qualified (no wildcards) and
 621  *     fully-direct references we see and store them in the
 622  *     direct_deref_nodes hash table.
 623  *
 624  *  2) Walk over the the list of fully-qualified direct derefs generated in
 625  *     the previous pass.  For each deref, we determine if it can ever be
 626  *     aliased, i.e. if there is an indirect reference anywhere that may
 627  *     refer to it.  If it cannot be aliased, we mark it for lowering to an
 628  *     SSA value.  At this point, we lower any var_copy instructions that
 629  *     use the given deref to load/store operations and, if the deref has a
 630  *     constant initializer, we go ahead and add a load_const value at the
 631  *     beginning of the function with the initialized value.
 632  *
 633  *  3) Walk over the list of derefs we plan to lower to SSA values and
 634  *     insert phi nodes as needed.
 635  *
 636  *  4) Perform "variable renaming" by replacing the load/store instructions
 637  *     with SSA definitions and SSA uses.
 638  */
 639 static bool
 640 nir_lower_vars_to_ssa_impl(nir_function_impl *impl)
 641 {
 642    struct lower_variables_state state;
 643
 644    state.shader = impl->function->shader;
 645    state.dead_ctx = ralloc_context(state.shader);
 646    state.impl = impl;
 647
 648    state.deref_var_nodes = _mesa_hash_table_create(state.dead_ctx,
 649                                                    _mesa_hash_pointer,
 650                                                    _mesa_key_pointer_equal);
 651    exec_list_make_empty(&state.direct_deref_nodes);
 652
 653    /* Build the initial deref structures and direct_deref_nodes table */
 654    state.add_to_direct_deref_nodes = true;
 655
 656    nir_foreach_block(block, impl) {
 657       register_variable_uses_block(block, &state);
 658    }
 659
 660    bool progress = false;
 661
 662    nir_metadata_require(impl, nir_metadata_block_index);
 663
 664    /* We're about to iterate through direct_deref_nodes.  Don't modify it. */
 665    state.add_to_direct_deref_nodes = false;
 666
 667    foreach_list_typed_safe(struct deref_node, node, direct_derefs_link,
 668                            &state.direct_deref_nodes) {
 669       nir_deref_var *deref = node->deref;
 670
 671       if (deref->var->data.mode != nir_var_local) {
 672          exec_node_remove(&node->direct_derefs_link);
 673          continue;
 674       }
 675
 676       if (deref_may_be_aliased(deref, &state)) {
 677          exec_node_remove(&node->direct_derefs_link);
 678          continue;
 679       }
 680
 681       node->lower_to_ssa = true;
 682       progress = true;
 683
 684       foreach_deref_node_match(deref, lower_copies_to_load_store, &state);
 685    }
 686
 687    if (!progress)
 688       return false;
 689
 690    nir_metadata_require(impl, nir_metadata_dominance);
 691
 692    /* We may have lowered some copy instructions to load/store
 693     * instructions.  The uses from the copy instructions hav already been
 694     * removed but we need to rescan to ensure that the uses from the newly
 695     * added load/store instructions are registered.  We need this
 696     * information for phi node insertion below.
 697     */
 698    nir_foreach_block(block, impl) {
 699       register_variable_uses_block(block, &state);
 700    }
 701
 702    state.phi_builder = nir_phi_builder_create(state.impl);
 703
 704    NIR_VLA(BITSET_WORD, store_blocks, BITSET_WORDS(state.impl->num_blocks));
 705    foreach_list_typed(struct deref_node, node, direct_derefs_link,
 706                       &state.direct_deref_nodes) {
 707       if (!node->lower_to_ssa)
 708          continue;
 709
 710       memset(store_blocks, 0,
 711              BITSET_WORDS(state.impl->num_blocks) * sizeof(*store_blocks));
 712
 713       if (node->stores) {
 714          struct set_entry *store_entry;
 715          set_foreach(node->stores, store_entry) {
 716             nir_intrinsic_instr *store =
 717                (nir_intrinsic_instr *)store_entry->key;
 718             BITSET_SET(store_blocks, store->instr.block->index);
 719          }
 720       }
 721
 722       if (node->deref->var->constant_initializer)
 723          BITSET_SET(store_blocks, 0);
 724
 725       node->pb_value =
 726          nir_phi_builder_add_value(state.phi_builder,
 727                                    glsl_get_vector_elements(node->type),
 728                                    glsl_get_bit_size(node->type),
 729                                    store_blocks);
 730
 731       if (node->deref->var->constant_initializer) {
 732          nir_load_const_instr *load =
 733             nir_deref_get_const_initializer_load(state.shader, node->deref);
 734          nir_instr_insert_before_cf_list(&impl->body, &load->instr);
 735          nir_phi_builder_value_set_block_def(node->pb_value,
 736                                              nir_start_block(impl), &load->def);
 737       }
 738    }
 739
 740    rename_variables_block(nir_start_block(impl), &state);
 741
 742    nir_phi_builder_finish(state.phi_builder);
 743
 744    nir_metadata_preserve(impl, nir_metadata_block_index |
 745                                nir_metadata_dominance);
 746
 747    ralloc_free(state.dead_ctx);
 748
 749    return progress;
 750 }
 751
 752 void
 753 nir_lower_vars_to_ssa(nir_shader *shader)
 754 {
 755    nir_foreach_function(function, shader) {
 756       if (function->impl)
 757          nir_lower_vars_to_ssa_impl(function->impl);
 758    }
 759 }