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 /* Flags used in the instr->pass_flags field for various instruction states */
  52 enum {
  53    GCM_INSTR_PINNED =            (1 << 0),
  54    GCM_INSTR_SCHEDULED_EARLY =   (1 << 1),
  55    GCM_INSTR_SCHEDULED_LATE =    (1 << 2),
  56    GCM_INSTR_PLACED =            (1 << 3),
  57 };
  58
  59 struct gcm_state {
  60    nir_function_impl *impl;
  61    nir_instr *instr;
  62
  63    /* The list of non-pinned instructions.  As we do the late scheduling,
  64     * we pull non-pinned instructions out of their blocks and place them in
  65     * this list.  This saves us from having linked-list problems when we go
  66     * to put instructions back in their blocks.
  67     */
  68    struct exec_list instrs;
  69
  70    struct gcm_block_info *blocks;
  71 };
  72
  73 /* Recursively walks the CFG and builds the block_info structure */
  74 static void
  75 gcm_build_block_info(struct exec_list *cf_list, struct gcm_state *state,
  76                      unsigned loop_depth)
  77 {
  78    foreach_list_typed(nir_cf_node, node, node, cf_list) {
  79       switch (node->type) {
  80       case nir_cf_node_block: {
  81          nir_block *block = nir_cf_node_as_block(node);
  82          state->blocks[block->index].loop_depth = loop_depth;
  83          break;
  84       }
  85       case nir_cf_node_if: {
  86          nir_if *if_stmt = nir_cf_node_as_if(node);
  87          gcm_build_block_info(&if_stmt->then_list, state, loop_depth);
  88          gcm_build_block_info(&if_stmt->else_list, state, loop_depth);
  89          break;
  90       }
  91       case nir_cf_node_loop: {
  92          nir_loop *loop = nir_cf_node_as_loop(node);
  93          gcm_build_block_info(&loop->body, state, loop_depth + 1);
  94          break;
  95       }
  96       default:
  97          unreachable("Invalid CF node type");
  98       }
  99    }
 100 }
 101
 102 /* Walks the instruction list and marks immovable instructions as pinned
 103  *
 104  * This function also serves to initialize the instr->pass_flags field.
 105  * After this is completed, all instructions' pass_flags fields will be set
 106  * to either GCM_INSTR_PINNED or 0.
 107  */
 108 static bool
 109 gcm_pin_instructions_block(nir_block *block, struct gcm_state *state)
 110 {
 111    nir_foreach_instr_safe(instr, block) {
 112       switch (instr->type) {
 113       case nir_instr_type_alu:
 114          switch (nir_instr_as_alu(instr)->op) {
 115          case nir_op_fddx:
 116          case nir_op_fddy:
 117          case nir_op_fddx_fine:
 118          case nir_op_fddy_fine:
 119          case nir_op_fddx_coarse:
 120          case nir_op_fddy_coarse:
 121             /* These can only go in uniform control flow; pin them for now */
 122             instr->pass_flags = GCM_INSTR_PINNED;
 123             break;
 124
 125          default:
 126             instr->pass_flags = 0;
 127             break;
 128          }
 129          break;
 130
 131       case nir_instr_type_deref:
 132          instr->pass_flags = 0;
 133          break;
 134
 135       case nir_instr_type_tex:
 136          switch (nir_instr_as_tex(instr)->op) {
 137          case nir_texop_tex:
 138          case nir_texop_txb:
 139          case nir_texop_lod:
 140             /* These two take implicit derivatives so they need to be pinned */
 141             instr->pass_flags = GCM_INSTR_PINNED;
 142             break;
 143
 144          default:
 145             instr->pass_flags = 0;
 146             break;
 147          }
 148          break;
 149
 150       case nir_instr_type_load_const:
 151          instr->pass_flags = 0;
 152          break;
 153
 154       case nir_instr_type_intrinsic: {
 155          const nir_intrinsic_info *info =
 156             &nir_intrinsic_infos[nir_instr_as_intrinsic(instr)->intrinsic];
 157
 158          if ((info->flags & NIR_INTRINSIC_CAN_ELIMINATE) &&
 159              (info->flags & NIR_INTRINSIC_CAN_REORDER)) {
 160             instr->pass_flags = 0;
 161          } else {
 162             instr->pass_flags = GCM_INSTR_PINNED;
 163          }
 164          break;
 165       }
 166
 167       case nir_instr_type_jump:
 168       case nir_instr_type_ssa_undef:
 169       case nir_instr_type_phi:
 170          instr->pass_flags = GCM_INSTR_PINNED;
 171          break;
 172
 173       default:
 174          unreachable("Invalid instruction type in GCM");
 175       }
 176
 177       if (!(instr->pass_flags & GCM_INSTR_PINNED)) {
 178          /* If this is an unpinned instruction, go ahead and pull it out of
 179           * the program and put it on the instrs list.  This has a couple
 180           * of benifits.  First, it makes the scheduling algorithm more
 181           * efficient because we can avoid walking over basic blocks and
 182           * pinned instructions.  Second, it keeps us from causing linked
 183           * list confusion when we're trying to put everything in its
 184           * proper place at the end of the pass.
 185           *
 186           * Note that we don't use nir_instr_remove here because that also
 187           * cleans up uses and defs and we want to keep that information.
 188           */
 189          exec_node_remove(&instr->node);
 190          exec_list_push_tail(&state->instrs, &instr->node);
 191       }
 192    }
 193
 194    return true;
 195 }
 196
 197 static void
 198 gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state);
 199
 200 /** Update an instructions schedule for the given source
 201  *
 202  * This function is called iteratively as we walk the sources of an
 203  * instruction.  It ensures that the given source instruction has been
 204  * scheduled and then update this instruction's block if the source
 205  * instruction is lower down the tree.
 206  */
 207 static bool
 208 gcm_schedule_early_src(nir_src *src, void *void_state)
 209 {
 210    struct gcm_state *state = void_state;
 211    nir_instr *instr = state->instr;
 212
 213    assert(src->is_ssa);
 214
 215    gcm_schedule_early_instr(src->ssa->parent_instr, void_state);
 216
 217    /* While the index isn't a proper dominance depth, it does have the
 218     * property that if A dominates B then A->index <= B->index.  Since we
 219     * know that this instruction must have been dominated by all of its
 220     * sources at some point (even if it's gone through value-numbering),
 221     * all of the sources must lie on the same branch of the dominance tree.
 222     * Therefore, we can just go ahead and just compare indices.
 223     */
 224    if (instr->block->index < src->ssa->parent_instr->block->index)
 225       instr->block = src->ssa->parent_instr->block;
 226
 227    /* We need to restore the state instruction because it may have been
 228     * changed through the gcm_schedule_early_instr call above.  Since we
 229     * may still be iterating through sources and future calls to
 230     * gcm_schedule_early_src for the same instruction will still need it.
 231     */
 232    state->instr = instr;
 233
 234    return true;
 235 }
 236
 237 /** Schedules an instruction early
 238  *
 239  * This function performs a recursive depth-first search starting at the
 240  * given instruction and proceeding through the sources to schedule
 241  * instructions as early as they can possibly go in the dominance tree.
 242  * The instructions are "scheduled" by updating their instr->block field.
 243  */
 244 static void
 245 gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state)
 246 {
 247    if (instr->pass_flags & GCM_INSTR_SCHEDULED_EARLY)
 248       return;
 249
 250    instr->pass_flags |= GCM_INSTR_SCHEDULED_EARLY;
 251
 252    /* Pinned instructions are already scheduled so we don't need to do
 253     * anything.  Also, bailing here keeps us from ever following the
 254     * sources of phi nodes which can be back-edges.
 255     */
 256    if (instr->pass_flags & GCM_INSTR_PINNED)
 257       return;
 258
 259    /* Start with the instruction at the top.  As we iterate over the
 260     * sources, it will get moved down as needed.
 261     */
 262    instr->block = nir_start_block(state->impl);
 263    state->instr = instr;
 264
 265    nir_foreach_src(instr, gcm_schedule_early_src, state);
 266 }
 267
 268 static void
 269 gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state);
 270
 271 /** Schedules the instruction associated with the given SSA def late
 272  *
 273  * This function works by first walking all of the uses of the given SSA
 274  * definition, ensuring that they are scheduled, and then computing the LCA
 275  * (least common ancestor) of its uses.  It then schedules this instruction
 276  * as close to the LCA as possible while trying to stay out of loops.
 277  */
 278 static bool
 279 gcm_schedule_late_def(nir_ssa_def *def, void *void_state)
 280 {
 281    struct gcm_state *state = void_state;
 282
 283    nir_block *lca = NULL;
 284
 285    nir_foreach_use(use_src, def) {
 286       nir_instr *use_instr = use_src->parent_instr;
 287
 288       gcm_schedule_late_instr(use_instr, state);
 289
 290       /* Phi instructions are a bit special.  SSA definitions don't have to
 291        * dominate the sources of the phi nodes that use them; instead, they
 292        * have to dominate the predecessor block corresponding to the phi
 293        * source.  We handle this by looking through the sources, finding
 294        * any that are usingg this SSA def, and using those blocks instead
 295        * of the one the phi lives in.
 296        */
 297       if (use_instr->type == nir_instr_type_phi) {
 298          nir_phi_instr *phi = nir_instr_as_phi(use_instr);
 299
 300          nir_foreach_phi_src(phi_src, phi) {
 301             if (phi_src->src.ssa == def)
 302                lca = nir_dominance_lca(lca, phi_src->pred);
 303          }
 304       } else {
 305          lca = nir_dominance_lca(lca, use_instr->block);
 306       }
 307    }
 308
 309    nir_foreach_if_use(use_src, def) {
 310       nir_if *if_stmt = use_src->parent_if;
 311
 312       /* For if statements, we consider the block to be the one immediately
 313        * preceding the if CF node.
 314        */
 315       nir_block *pred_block =
 316          nir_cf_node_as_block(nir_cf_node_prev(&if_stmt->cf_node));
 317
 318       lca = nir_dominance_lca(lca, pred_block);
 319    }
 320
 321    /* Some instructions may never be used.  We'll just leave them scheduled
 322     * early and let dead code clean them up.
 323     */
 324    if (lca == NULL)
 325       return true;
 326
 327    /* We now have the LCA of all of the uses.  If our invariants hold,
 328     * this is dominated by the block that we chose when scheduling early.
 329     * We now walk up the dominance tree and pick the lowest block that is
 330     * as far outside loops as we can get.
 331     */
 332    nir_block *best = lca;
 333    for (nir_block *block = lca; block != NULL; block = block->imm_dom) {
 334       if (state->blocks[block->index].loop_depth <
 335           state->blocks[best->index].loop_depth)
 336          best = block;
 337
 338       if (block == def->parent_instr->block)
 339          break;
 340    }
 341    def->parent_instr->block = best;
 342
 343    return true;
 344 }
 345
 346 /** Schedules an instruction late
 347  *
 348  * This function performs a depth-first search starting at the given
 349  * instruction and proceeding through its uses to schedule instructions as
 350  * late as they can reasonably go in the dominance tree.  The instructions
 351  * are "scheduled" by updating their instr->block field.
 352  *
 353  * The name of this function is actually a bit of a misnomer as it doesn't
 354  * schedule them "as late as possible" as the paper implies.  Instead, it
 355  * first finds the lates possible place it can schedule the instruction and
 356  * then possibly schedules it earlier than that.  The actual location is as
 357  * far down the tree as we can go while trying to stay out of loops.
 358  */
 359 static void
 360 gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state)
 361 {
 362    if (instr->pass_flags & GCM_INSTR_SCHEDULED_LATE)
 363       return;
 364
 365    instr->pass_flags |= GCM_INSTR_SCHEDULED_LATE;
 366
 367    /* Pinned instructions are already scheduled so we don't need to do
 368     * anything.  Also, bailing here keeps us from ever following phi nodes
 369     * which can be back-edges.
 370     */
 371    if (instr->pass_flags & GCM_INSTR_PINNED)
 372       return;
 373
 374    nir_foreach_ssa_def(instr, gcm_schedule_late_def, state);
 375 }
 376
 377 static void
 378 gcm_place_instr(nir_instr *instr, struct gcm_state *state);
 379
 380 static bool
 381 gcm_place_instr_def(nir_ssa_def *def, void *state)
 382 {
 383    nir_foreach_use(use_src, def)
 384       gcm_place_instr(use_src->parent_instr, state);
 385
 386    return false;
 387 }
 388
 389 /** Places an instrution back into the program
 390  *
 391  * The earlier passes of GCM simply choose blocks for each instruction and
 392  * otherwise leave them alone.  This pass actually places the instructions
 393  * into their chosen blocks.
 394  *
 395  * To do so, we use a standard post-order depth-first search linearization
 396  * algorithm.  We walk over the uses of the given instruction and ensure
 397  * that they are placed and then place this instruction.  Because we are
 398  * working on multiple blocks at a time, we keep track of the last inserted
 399  * instruction per-block in the state structure's block_info array.  When
 400  * we insert an instruction in a block we insert it before the last
 401  * instruction inserted in that block rather than the last instruction
 402  * inserted globally.
 403  */
 404 static void
 405 gcm_place_instr(nir_instr *instr, struct gcm_state *state)
 406 {
 407    if (instr->pass_flags & GCM_INSTR_PLACED)
 408       return;
 409
 410    instr->pass_flags |= GCM_INSTR_PLACED;
 411
 412    /* Phi nodes are our once source of back-edges.  Since right now we are
 413     * only doing scheduling within blocks, we don't need to worry about
 414     * them since they are always at the top.  Just skip them completely.
 415     */
 416    if (instr->type == nir_instr_type_phi) {
 417       assert(instr->pass_flags & GCM_INSTR_PINNED);
 418       return;
 419    }
 420
 421    nir_foreach_ssa_def(instr, gcm_place_instr_def, state);
 422
 423    if (instr->pass_flags & GCM_INSTR_PINNED) {
 424       /* Pinned instructions have an implicit dependence on the pinned
 425        * instructions that come after them in the block.  Since the pinned
 426        * instructions will naturally "chain" together, we only need to
 427        * explicitly visit one of them.
 428        */
 429       for (nir_instr *after = nir_instr_next(instr);
 430            after;
 431            after = nir_instr_next(after)) {
 432          if (after->pass_flags & GCM_INSTR_PINNED) {
 433             gcm_place_instr(after, state);
 434             break;
 435          }
 436       }
 437    }
 438
 439    struct gcm_block_info *block_info = &state->blocks[instr->block->index];
 440    if (!(instr->pass_flags & GCM_INSTR_PINNED)) {
 441       exec_node_remove(&instr->node);
 442
 443       if (block_info->last_instr) {
 444          exec_node_insert_node_before(&block_info->last_instr->node,
 445                                       &instr->node);
 446       } else {
 447          /* Schedule it at the end of the block */
 448          nir_instr *jump_instr = nir_block_last_instr(instr->block);
 449          if (jump_instr && jump_instr->type == nir_instr_type_jump) {
 450             exec_node_insert_node_before(&jump_instr->node, &instr->node);
 451          } else {
 452             exec_list_push_tail(&instr->block->instr_list, &instr->node);
 453          }
 454       }
 455    }
 456
 457    block_info->last_instr = instr;
 458 }
 459
 460 static bool
 461 opt_gcm_impl(nir_function_impl *impl, bool value_number)
 462 {
 463    nir_metadata_require(impl, nir_metadata_block_index |
 464                               nir_metadata_dominance);
 465
 466    struct gcm_state state;
 467
 468    state.impl = impl;
 469    state.instr = NULL;
 470    exec_list_make_empty(&state.instrs);
 471    state.blocks = rzalloc_array(NULL, struct gcm_block_info, impl->num_blocks);
 472
 473    gcm_build_block_info(&impl->body, &state, 0);
 474
 475    nir_foreach_block(block, impl) {
 476       gcm_pin_instructions_block(block, &state);
 477    }
 478
 479    bool progress = false;
 480    if (value_number) {
 481       struct set *gvn_set = nir_instr_set_create(NULL);
 482       foreach_list_typed_safe(nir_instr, instr, node, &state.instrs) {
 483          if (nir_instr_set_add_or_rewrite(gvn_set, instr)) {
 484             nir_instr_remove(instr);
 485             progress = true;
 486          }
 487       }
 488       nir_instr_set_destroy(gvn_set);
 489    }
 490
 491    foreach_list_typed(nir_instr, instr, node, &state.instrs)
 492       gcm_schedule_early_instr(instr, &state);
 493
 494    foreach_list_typed(nir_instr, instr, node, &state.instrs)
 495       gcm_schedule_late_instr(instr, &state);
 496
 497    while (!exec_list_is_empty(&state.instrs)) {
 498       nir_instr *instr = exec_node_data(nir_instr,
 499                                         state.instrs.tail_sentinel.prev, node);
 500       gcm_place_instr(instr, &state);
 501    }
 502
 503    ralloc_free(state.blocks);
 504
 505    nir_metadata_preserve(impl, nir_metadata_block_index |
 506                                nir_metadata_dominance);
 507
 508    return progress;
 509 }
 510
 511 bool
 512 nir_opt_gcm(nir_shader *shader, bool value_number)
 513 {
 514    bool progress = false;
 515
 516    nir_foreach_function(function, shader) {
 517       if (function->impl)
 518          progress |= opt_gcm_impl(function->impl, value_number);
 519    }
 520
 521    return progress;
 522 }