src/compiler/nir/nir_opt_gcm.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_instr_set.h"
  30
  31 /*
  32  * Implements Global Code Motion.  A description of GCM can be found in
  33  * "Global Code Motion; Global Value Numbering" by Cliff Click.
  34  * Unfortunately, the algorithm presented in the paper is broken in a
  35  * number of ways.  The algorithm used here differs substantially from the
  36  * one in the paper but it is, in my opinion, much easier to read and
  37  * verify correcness.
  38  */
  39
  40 struct gcm_block_info {
  41    /* Number of loops this block is inside */
  42    unsigned loop_depth;
  43
  44    /* The last instruction inserted into this block.  This is used as we
  45     * traverse the instructions and insert them back into the program to
  46     * put them in the right order.
  47     */
  48    nir_instr *last_instr;
  49 };
  50
  51 struct gcm_instr_info {
  52    nir_block *early_block;
  53 };
  54
  55 /* Flags used in the instr->pass_flags field for various instruction states */
  56 enum {
  57    GCM_INSTR_PINNED =                (1 << 0),
  58    GCM_INSTR_SCHEDULE_EARLIER_ONLY = (1 << 1),
  59    GCM_INSTR_SCHEDULED_EARLY =       (1 << 2),
  60    GCM_INSTR_SCHEDULED_LATE =        (1 << 3),
  61    GCM_INSTR_PLACED =                (1 << 4),
  62 };
  63
  64 struct gcm_state {
  65    nir_function_impl *impl;
  66    nir_instr *instr;
  67
  68    bool progress;
  69
  70    /* The list of non-pinned instructions.  As we do the late scheduling,
  71     * we pull non-pinned instructions out of their blocks and place them in
  72     * this list.  This saves us from having linked-list problems when we go
  73     * to put instructions back in their blocks.
  74     */
  75    struct exec_list instrs;
  76
  77    struct gcm_block_info *blocks;
  78
  79    unsigned num_instrs;
  80    struct gcm_instr_info *instr_infos;
  81 };
  82
  83 /* Recursively walks the CFG and builds the block_info structure */
  84 static void
  85 gcm_build_block_info(struct exec_list *cf_list, struct gcm_state *state,
  86                      unsigned loop_depth)
  87 {
  88    foreach_list_typed(nir_cf_node, node, node, cf_list) {
  89       switch (node->type) {
  90       case nir_cf_node_block: {
  91          nir_block *block = nir_cf_node_as_block(node);
  92          state->blocks[block->index].loop_depth = loop_depth;
  93          break;
  94       }
  95       case nir_cf_node_if: {
  96          nir_if *if_stmt = nir_cf_node_as_if(node);
  97          gcm_build_block_info(&if_stmt->then_list, state, loop_depth);
  98          gcm_build_block_info(&if_stmt->else_list, state, loop_depth);
  99          break;
 100       }
 101       case nir_cf_node_loop: {
 102          nir_loop *loop = nir_cf_node_as_loop(node);
 103          gcm_build_block_info(&loop->body, state, loop_depth + 1);
 104          break;
 105       }
 106       default:
 107          unreachable("Invalid CF node type");
 108       }
 109    }
 110 }
 111
 112 static bool
 113 is_src_scalarizable(nir_src *src)
 114 {
 115    assert(src->is_ssa);
 116
 117    nir_instr *src_instr = src->ssa->parent_instr;
 118    switch (src_instr->type) {
 119    case nir_instr_type_alu: {
 120       nir_alu_instr *src_alu = nir_instr_as_alu(src_instr);
 121
 122       /* ALU operations with output_size == 0 should be scalarized.  We
 123        * will also see a bunch of vecN operations from scalarizing ALU
 124        * operations and, since they can easily be copy-propagated, they
 125        * are ok too.
 126        */
 127       return nir_op_infos[src_alu->op].output_size == 0 ||
 128              src_alu->op == nir_op_vec2 ||
 129              src_alu->op == nir_op_vec3 ||
 130              src_alu->op == nir_op_vec4;
 131    }
 132
 133    case nir_instr_type_load_const:
 134       /* These are trivially scalarizable */
 135       return true;
 136
 137    case nir_instr_type_ssa_undef:
 138       return true;
 139
 140    case nir_instr_type_intrinsic: {
 141       nir_intrinsic_instr *src_intrin = nir_instr_as_intrinsic(src_instr);
 142
 143       switch (src_intrin->intrinsic) {
 144       case nir_intrinsic_load_deref: {
 145          nir_deref_instr *deref = nir_src_as_deref(src_intrin->src[0]);
 146          return deref->mode == nir_var_shader_in ||
 147                 deref->mode == nir_var_uniform ||
 148                 deref->mode == nir_var_mem_ubo ||
 149                 deref->mode == nir_var_mem_ssbo ||
 150                 deref->mode == nir_var_mem_global;
 151       }
 152
 153       case nir_intrinsic_interp_deref_at_centroid:
 154       case nir_intrinsic_interp_deref_at_sample:
 155       case nir_intrinsic_interp_deref_at_offset:
 156       case nir_intrinsic_load_uniform:
 157       case nir_intrinsic_load_ubo:
 158       case nir_intrinsic_load_ssbo:
 159       case nir_intrinsic_load_global:
 160       case nir_intrinsic_load_input:
 161          return true;
 162       default:
 163          break;
 164       }
 165
 166       return false;
 167    }
 168
 169    default:
 170       /* We can't scalarize this type of instruction */
 171       return false;
 172    }
 173 }
 174
 175 /* Walks the instruction list and marks immovable instructions as pinned
 176  *
 177  * This function also serves to initialize the instr->pass_flags field.
 178  * After this is completed, all instructions' pass_flags fields will be set
 179  * to either GCM_INSTR_PINNED or 0.
 180  */
 181 static void
 182 gcm_pin_instructions(nir_function_impl *impl, struct gcm_state *state)
 183 {
 184    state->num_instrs = 0;
 185
 186    nir_foreach_block(block, impl) {
 187       nir_foreach_instr_safe(instr, block) {
 188          /* Index the instructions for use in gcm_state::instrs */
 189          instr->index = state->num_instrs++;
 190
 191          switch (instr->type) {
 192          case nir_instr_type_alu:
 193             switch (nir_instr_as_alu(instr)->op) {
 194             case nir_op_fddx:
 195             case nir_op_fddy:
 196             case nir_op_fddx_fine:
 197             case nir_op_fddy_fine:
 198             case nir_op_fddx_coarse:
 199             case nir_op_fddy_coarse:
 200                /* These can only go in uniform control flow */
 201                instr->pass_flags = GCM_INSTR_SCHEDULE_EARLIER_ONLY;
 202                break;
 203
 204             case nir_op_mov:
 205                if (!is_src_scalarizable(&(nir_instr_as_alu(instr)->src[0].src))) {
 206                   instr->pass_flags = GCM_INSTR_PINNED;
 207                   break;
 208                }
 209                /* fallthrough */
 210
 211             default:
 212                instr->pass_flags = 0;
 213                break;
 214             }
 215             break;
 216
 217          case nir_instr_type_tex:
 218             if (nir_tex_instr_has_implicit_derivative(nir_instr_as_tex(instr)))
 219                instr->pass_flags = GCM_INSTR_SCHEDULE_EARLIER_ONLY;
 220             break;
 221
 222          case nir_instr_type_deref:
 223          case nir_instr_type_load_const:
 224             instr->pass_flags = 0;
 225             break;
 226
 227          case nir_instr_type_intrinsic: {
 228             if (nir_intrinsic_can_reorder(nir_instr_as_intrinsic(instr))) {
 229                instr->pass_flags = 0;
 230             } else {
 231                instr->pass_flags = GCM_INSTR_PINNED;
 232             }
 233             break;
 234          }
 235
 236          case nir_instr_type_jump:
 237          case nir_instr_type_ssa_undef:
 238          case nir_instr_type_phi:
 239             instr->pass_flags = GCM_INSTR_PINNED;
 240             break;
 241
 242          default:
 243             unreachable("Invalid instruction type in GCM");
 244          }
 245
 246          if (!(instr->pass_flags & GCM_INSTR_PINNED)) {
 247             /* If this is an unpinned instruction, go ahead and pull it out of
 248              * the program and put it on the instrs list.  This has a couple
 249              * of benifits.  First, it makes the scheduling algorithm more
 250              * efficient because we can avoid walking over basic blocks and
 251              * pinned instructions.  Second, it keeps us from causing linked
 252              * list confusion when we're trying to put everything in its
 253              * proper place at the end of the pass.
 254              *
 255              * Note that we don't use nir_instr_remove here because that also
 256              * cleans up uses and defs and we want to keep that information.
 257              */
 258             exec_node_remove(&instr->node);
 259             exec_list_push_tail(&state->instrs, &instr->node);
 260          }
 261       }
 262    }
 263 }
 264
 265 static void
 266 gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state);
 267
 268 /** Update an instructions schedule for the given source
 269  *
 270  * This function is called iteratively as we walk the sources of an
 271  * instruction.  It ensures that the given source instruction has been
 272  * scheduled and then update this instruction's block if the source
 273  * instruction is lower down the tree.
 274  */
 275 static bool
 276 gcm_schedule_early_src(nir_src *src, void *void_state)
 277 {
 278    struct gcm_state *state = void_state;
 279    nir_instr *instr = state->instr;
 280
 281    assert(src->is_ssa);
 282
 283    gcm_schedule_early_instr(src->ssa->parent_instr, void_state);
 284
 285    /* While the index isn't a proper dominance depth, it does have the
 286     * property that if A dominates B then A->index <= B->index.  Since we
 287     * know that this instruction must have been dominated by all of its
 288     * sources at some point (even if it's gone through value-numbering),
 289     * all of the sources must lie on the same branch of the dominance tree.
 290     * Therefore, we can just go ahead and just compare indices.
 291     */
 292    struct gcm_instr_info *src_info =
 293       &state->instr_infos[src->ssa->parent_instr->index];
 294    struct gcm_instr_info *info = &state->instr_infos[instr->index];
 295    if (info->early_block->index < src_info->early_block->index)
 296       info->early_block = src_info->early_block;
 297
 298    /* We need to restore the state instruction because it may have been
 299     * changed through the gcm_schedule_early_instr call above.  Since we
 300     * may still be iterating through sources and future calls to
 301     * gcm_schedule_early_src for the same instruction will still need it.
 302     */
 303    state->instr = instr;
 304
 305    return true;
 306 }
 307
 308 /** Schedules an instruction early
 309  *
 310  * This function performs a recursive depth-first search starting at the
 311  * given instruction and proceeding through the sources to schedule
 312  * instructions as early as they can possibly go in the dominance tree.
 313  * The instructions are "scheduled" by updating the early_block field of
 314  * the corresponding gcm_instr_state entry.
 315  */
 316 static void
 317 gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state)
 318 {
 319    if (instr->pass_flags & GCM_INSTR_SCHEDULED_EARLY)
 320       return;
 321
 322    instr->pass_flags |= GCM_INSTR_SCHEDULED_EARLY;
 323
 324    /* Pinned instructions always get scheduled in their original block so we
 325     * don't need to do anything.  Also, bailing here keeps us from ever
 326     * following the sources of phi nodes which can be back-edges.
 327     */
 328    if (instr->pass_flags & GCM_INSTR_PINNED) {
 329       state->instr_infos[instr->index].early_block = instr->block;
 330       return;
 331    }
 332
 333    /* Start with the instruction at the top.  As we iterate over the
 334     * sources, it will get moved down as needed.
 335     */
 336    state->instr_infos[instr->index].early_block = nir_start_block(state->impl);
 337    state->instr = instr;
 338
 339    nir_foreach_src(instr, gcm_schedule_early_src, state);
 340 }
 341
 342 static nir_block *
 343 gcm_choose_block_for_instr(nir_instr *instr, nir_block *early_block,
 344                            nir_block *late_block, struct gcm_state *state)
 345 {
 346    assert(nir_block_dominates(early_block, late_block));
 347
 348    nir_block *best = late_block;
 349    for (nir_block *block = late_block; block != NULL; block = block->imm_dom) {
 350       /* Being too aggressive with how we pull instructions out of loops can
 351        * result in extra register pressure and spilling. For example its fairly
 352        * common for loops in compute shaders to calculate SSBO offsets using
 353        * the workgroup id, subgroup id and subgroup invocation, pulling all
 354        * these calculations outside the loop causes register pressure.
 355        *
 356        * To work around these issues for now we only allow constant and texture
 357        * instructions to be moved outside their original loops.
 358        *
 359        * TODO: figure out some heuristics to allow more to be moved out of loops.
 360        */
 361       if (state->blocks[block->index].loop_depth <
 362           state->blocks[best->index].loop_depth &&
 363           (nir_block_dominates(instr->block, block) ||
 364            instr->type == nir_instr_type_load_const ||
 365            instr->type == nir_instr_type_tex))
 366          best = block;
 367       else if (block == instr->block)
 368          best = block;
 369
 370       if (block == early_block)
 371          break;
 372    }
 373
 374    return best;
 375 }
 376
 377 static void
 378 gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state);
 379
 380 /** Schedules the instruction associated with the given SSA def late
 381  *
 382  * This function works by first walking all of the uses of the given SSA
 383  * definition, ensuring that they are scheduled, and then computing the LCA
 384  * (least common ancestor) of its uses.  It then schedules this instruction
 385  * as close to the LCA as possible while trying to stay out of loops.
 386  */
 387 static bool
 388 gcm_schedule_late_def(nir_ssa_def *def, void *void_state)
 389 {
 390    struct gcm_state *state = void_state;
 391
 392    nir_block *lca = NULL;
 393
 394    nir_foreach_use(use_src, def) {
 395       nir_instr *use_instr = use_src->parent_instr;
 396
 397       gcm_schedule_late_instr(use_instr, state);
 398
 399       /* Phi instructions are a bit special.  SSA definitions don't have to
 400        * dominate the sources of the phi nodes that use them; instead, they
 401        * have to dominate the predecessor block corresponding to the phi
 402        * source.  We handle this by looking through the sources, finding
 403        * any that are usingg this SSA def, and using those blocks instead
 404        * of the one the phi lives in.
 405        */
 406       if (use_instr->type == nir_instr_type_phi) {
 407          nir_phi_instr *phi = nir_instr_as_phi(use_instr);
 408
 409          nir_foreach_phi_src(phi_src, phi) {
 410             if (phi_src->src.ssa == def)
 411                lca = nir_dominance_lca(lca, phi_src->pred);
 412          }
 413       } else {
 414          lca = nir_dominance_lca(lca, use_instr->block);
 415       }
 416    }
 417
 418    nir_foreach_if_use(use_src, def) {
 419       nir_if *if_stmt = use_src->parent_if;
 420
 421       /* For if statements, we consider the block to be the one immediately
 422        * preceding the if CF node.
 423        */
 424       nir_block *pred_block =
 425          nir_cf_node_as_block(nir_cf_node_prev(&if_stmt->cf_node));
 426
 427       lca = nir_dominance_lca(lca, pred_block);
 428    }
 429
 430    nir_block *early_block =
 431       state->instr_infos[def->parent_instr->index].early_block;
 432
 433    /* Some instructions may never be used.  Flag them and the instruction
 434     * placement code will get rid of them for us.
 435     */
 436    if (lca == NULL) {
 437       def->parent_instr->block = NULL;
 438       return true;
 439    }
 440
 441    if (def->parent_instr->pass_flags & GCM_INSTR_SCHEDULE_EARLIER_ONLY &&
 442        lca != def->parent_instr->block &&
 443        nir_block_dominates(def->parent_instr->block, lca)) {
 444       lca = def->parent_instr->block;
 445    }
 446
 447    /* We now have the LCA of all of the uses.  If our invariants hold,
 448     * this is dominated by the block that we chose when scheduling early.
 449     * We now walk up the dominance tree and pick the lowest block that is
 450     * as far outside loops as we can get.
 451     */
 452    nir_block *best_block =
 453       gcm_choose_block_for_instr(def->parent_instr, early_block, lca, state);
 454
 455    if (def->parent_instr->block != best_block)
 456       state->progress = true;
 457
 458    def->parent_instr->block = best_block;
 459
 460    return true;
 461 }
 462
 463 /** Schedules an instruction late
 464  *
 465  * This function performs a depth-first search starting at the given
 466  * instruction and proceeding through its uses to schedule instructions as
 467  * late as they can reasonably go in the dominance tree.  The instructions
 468  * are "scheduled" by updating their instr->block field.
 469  *
 470  * The name of this function is actually a bit of a misnomer as it doesn't
 471  * schedule them "as late as possible" as the paper implies.  Instead, it
 472  * first finds the lates possible place it can schedule the instruction and
 473  * then possibly schedules it earlier than that.  The actual location is as
 474  * far down the tree as we can go while trying to stay out of loops.
 475  */
 476 static void
 477 gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state)
 478 {
 479    if (instr->pass_flags & GCM_INSTR_SCHEDULED_LATE)
 480       return;
 481
 482    instr->pass_flags |= GCM_INSTR_SCHEDULED_LATE;
 483
 484    /* Pinned instructions are already scheduled so we don't need to do
 485     * anything.  Also, bailing here keeps us from ever following phi nodes
 486     * which can be back-edges.
 487     */
 488    if (instr->pass_flags & GCM_INSTR_PINNED)
 489       return;
 490
 491    nir_foreach_ssa_def(instr, gcm_schedule_late_def, state);
 492 }
 493
 494 static void
 495 gcm_place_instr(nir_instr *instr, struct gcm_state *state);
 496
 497 static bool
 498 gcm_place_instr_def(nir_ssa_def *def, void *state)
 499 {
 500    nir_foreach_use(use_src, def)
 501       gcm_place_instr(use_src->parent_instr, state);
 502
 503    return false;
 504 }
 505
 506 static bool
 507 gcm_replace_def_with_undef(nir_ssa_def *def, void *void_state)
 508 {
 509    struct gcm_state *state = void_state;
 510
 511    if (list_is_empty(&def->uses) && list_is_empty(&def->if_uses))
 512       return true;
 513
 514    nir_ssa_undef_instr *undef =
 515       nir_ssa_undef_instr_create(state->impl->function->shader,
 516                                  def->num_components, def->bit_size);
 517    nir_instr_insert(nir_before_cf_list(&state->impl->body), &undef->instr);
 518    nir_ssa_def_rewrite_uses(def, nir_src_for_ssa(&undef->def));
 519
 520    return true;
 521 }
 522
 523 /** Places an instrution back into the program
 524  *
 525  * The earlier passes of GCM simply choose blocks for each instruction and
 526  * otherwise leave them alone.  This pass actually places the instructions
 527  * into their chosen blocks.
 528  *
 529  * To do so, we use a standard post-order depth-first search linearization
 530  * algorithm.  We walk over the uses of the given instruction and ensure
 531  * that they are placed and then place this instruction.  Because we are
 532  * working on multiple blocks at a time, we keep track of the last inserted
 533  * instruction per-block in the state structure's block_info array.  When
 534  * we insert an instruction in a block we insert it before the last
 535  * instruction inserted in that block rather than the last instruction
 536  * inserted globally.
 537  */
 538 static void
 539 gcm_place_instr(nir_instr *instr, struct gcm_state *state)
 540 {
 541    if (instr->pass_flags & GCM_INSTR_PLACED)
 542       return;
 543
 544    instr->pass_flags |= GCM_INSTR_PLACED;
 545
 546    if (instr->block == NULL) {
 547       nir_foreach_ssa_def(instr, gcm_replace_def_with_undef, state);
 548       nir_instr_remove(instr);
 549       return;
 550    }
 551
 552    /* Phi nodes are our once source of back-edges.  Since right now we are
 553     * only doing scheduling within blocks, we don't need to worry about
 554     * them since they are always at the top.  Just skip them completely.
 555     */
 556    if (instr->type == nir_instr_type_phi) {
 557       assert(instr->pass_flags & GCM_INSTR_PINNED);
 558       return;
 559    }
 560
 561    nir_foreach_ssa_def(instr, gcm_place_instr_def, state);
 562
 563    if (instr->pass_flags & GCM_INSTR_PINNED) {
 564       /* Pinned instructions have an implicit dependence on the pinned
 565        * instructions that come after them in the block.  Since the pinned
 566        * instructions will naturally "chain" together, we only need to
 567        * explicitly visit one of them.
 568        */
 569       for (nir_instr *after = nir_instr_next(instr);
 570            after;
 571            after = nir_instr_next(after)) {
 572          if (after->pass_flags & GCM_INSTR_PINNED) {
 573             gcm_place_instr(after, state);
 574             break;
 575          }
 576       }
 577    }
 578
 579    struct gcm_block_info *block_info = &state->blocks[instr->block->index];
 580    if (!(instr->pass_flags & GCM_INSTR_PINNED)) {
 581       exec_node_remove(&instr->node);
 582
 583       if (block_info->last_instr) {
 584          exec_node_insert_node_before(&block_info->last_instr->node,
 585                                       &instr->node);
 586       } else {
 587          /* Schedule it at the end of the block */
 588          nir_instr *jump_instr = nir_block_last_instr(instr->block);
 589          if (jump_instr && jump_instr->type == nir_instr_type_jump) {
 590             exec_node_insert_node_before(&jump_instr->node, &instr->node);
 591          } else {
 592             exec_list_push_tail(&instr->block->instr_list, &instr->node);
 593          }
 594       }
 595    }
 596
 597    block_info->last_instr = instr;
 598 }
 599
 600 static bool
 601 opt_gcm_impl(nir_function_impl *impl, bool value_number)
 602 {
 603    nir_metadata_require(impl, nir_metadata_block_index |
 604                               nir_metadata_dominance);
 605
 606    struct gcm_state state;
 607
 608    state.impl = impl;
 609    state.instr = NULL;
 610    state.progress = false;
 611    exec_list_make_empty(&state.instrs);
 612    state.blocks = rzalloc_array(NULL, struct gcm_block_info, impl->num_blocks);
 613
 614    gcm_build_block_info(&impl->body, &state, 0);
 615
 616    gcm_pin_instructions(impl, &state);
 617
 618    state.instr_infos =
 619       rzalloc_array(NULL, struct gcm_instr_info, state.num_instrs);
 620
 621    if (value_number) {
 622       struct set *gvn_set = nir_instr_set_create(NULL);
 623       foreach_list_typed_safe(nir_instr, instr, node, &state.instrs) {
 624          if (nir_instr_set_add_or_rewrite(gvn_set, instr)) {
 625             nir_instr_remove(instr);
 626             state.progress = true;
 627          }
 628       }
 629       nir_instr_set_destroy(gvn_set);
 630    }
 631
 632    foreach_list_typed(nir_instr, instr, node, &state.instrs)
 633       gcm_schedule_early_instr(instr, &state);
 634
 635    foreach_list_typed(nir_instr, instr, node, &state.instrs)
 636       gcm_schedule_late_instr(instr, &state);
 637
 638    while (!exec_list_is_empty(&state.instrs)) {
 639       nir_instr *instr = exec_node_data(nir_instr,
 640                                         state.instrs.tail_sentinel.prev, node);
 641       gcm_place_instr(instr, &state);
 642    }
 643
 644    ralloc_free(state.blocks);
 645    ralloc_free(state.instr_infos);
 646
 647    nir_metadata_preserve(impl, nir_metadata_block_index |
 648                                nir_metadata_dominance);
 649
 650    return state.progress;
 651 }
 652
 653 bool
 654 nir_opt_gcm(nir_shader *shader, bool value_number)
 655 {
 656    bool progress = false;
 657
 658    nir_foreach_function(function, shader) {
 659       if (function->impl)
 660          progress |= opt_gcm_impl(function->impl, value_number);
 661    }
 662
 663    return progress;
 664 }