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