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