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