Subversion Repositories Kolibri OS

/*

 * Copyright © 2014 Intel Corporation

 *

 * Permission is hereby granted, free of charge, to any person obtaining a

 * copy of this software and associated documentation files (the "Software"),

 * to deal in the Software without restriction, including without limitation

 * the rights to use, copy, modify, merge, publish, distribute, sublicense,

 * and/or sell copies of the Software, and to permit persons to whom the

 * Software is furnished to do so, subject to the following conditions:

 *

 * The above copyright notice and this permission notice (including the next

 * paragraph) shall be included in all copies or substantial portions of the

 * Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL

 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS

 * IN THE SOFTWARE.

 *

 * Authors:

 *    Jason Ekstrand (jason@jlekstrand.net)

 *

 */

#include "nir.h"

/*

 * Implements Global Code Motion.  A description of GCM can be found in

 * "Global Code Motion; Global Value Numbering" by Cliff Click.

 * Unfortunately, the algorithm presented in the paper is broken in a

 * number of ways.  The algorithm used here differs substantially from the

 * one in the paper but it is, in my opinion, much easier to read and

 * verify correcness.

 */

struct gcm_block_info {

   /* Number of loops this block is inside */

   unsigned loop_depth;

   /* The last instruction inserted into this block.  This is used as we

    * traverse the instructions and insert them back into the program to

    * put them in the right order.

    */

   nir_instr *last_instr;

};

/* Flags used in the instr->pass_flags field for various instruction states */

enum {

   GCM_INSTR_PINNED =            (1 << 0),

   GCM_INSTR_SCHEDULED_EARLY =   (1 << 1),

   GCM_INSTR_SCHEDULED_LATE =    (1 << 2),

   GCM_INSTR_PLACED =            (1 << 3),

};

struct gcm_state {

   nir_function_impl *impl;

   nir_instr *instr;

   /* The list of non-pinned instructions.  As we do the late scheduling,

    * we pull non-pinned instructions out of their blocks and place them in

    * this list.  This saves us from having linked-list problems when we go

    * to put instructions back in their blocks.

    */

   struct exec_list instrs;

   struct gcm_block_info *blocks;

};

/* Recursively walks the CFG and builds the block_info structure */

static void

gcm_build_block_info(struct exec_list *cf_list, struct gcm_state *state,

                     unsigned loop_depth)

{

   foreach_list_typed(nir_cf_node, node, node, cf_list) {

      switch (node->type) {

      case nir_cf_node_block: {

         nir_block *block = nir_cf_node_as_block(node);

         state->blocks[block->index].loop_depth = loop_depth;

         break;

      }

      case nir_cf_node_if: {

         nir_if *if_stmt = nir_cf_node_as_if(node);

         gcm_build_block_info(&if_stmt->then_list, state, loop_depth);

         gcm_build_block_info(&if_stmt->else_list, state, loop_depth);

         break;

      }

      case nir_cf_node_loop: {

         nir_loop *loop = nir_cf_node_as_loop(node);

         gcm_build_block_info(&loop->body, state, loop_depth + 1);

         break;

      }

      default:

         unreachable("Invalid CF node type");

      }

   }

}

/* Walks the instruction list and marks immovable instructions as pinned

 *

 * This function also serves to initialize the instr->pass_flags field.

 * After this is completed, all instructions' pass_flags fields will be set

 * to either GCM_INSTR_PINNED or 0.

 */

static bool

gcm_pin_instructions_block(nir_block *block, void *void_state)

{

   struct gcm_state *state = void_state;

   nir_foreach_instr_safe(block, instr) {

      switch (instr->type) {

      case nir_instr_type_alu:

         switch (nir_instr_as_alu(instr)->op) {

         case nir_op_fddx:

         case nir_op_fddy:

         case nir_op_fddx_fine:

         case nir_op_fddy_fine:

         case nir_op_fddx_coarse:

         case nir_op_fddy_coarse:

            /* These can only go in uniform control flow; pin them for now */

            instr->pass_flags = GCM_INSTR_PINNED;

            break;

         default:

            instr->pass_flags = 0;

            break;

         }

         break;

      case nir_instr_type_tex:

         switch (nir_instr_as_tex(instr)->op) {

         case nir_texop_tex:

         case nir_texop_txb:

         case nir_texop_lod:

            /* These two take implicit derivatives so they need to be pinned */

            instr->pass_flags = GCM_INSTR_PINNED;

            break;

         default:

            instr->pass_flags = 0;

            break;

         }

         break;

      case nir_instr_type_load_const:

         instr->pass_flags = 0;

         break;

      case nir_instr_type_intrinsic: {

         const nir_intrinsic_info *info =

            &nir_intrinsic_infos[nir_instr_as_intrinsic(instr)->intrinsic];

         if ((info->flags & NIR_INTRINSIC_CAN_ELIMINATE) &&

             (info->flags & NIR_INTRINSIC_CAN_REORDER)) {

            instr->pass_flags = 0;

         } else {

            instr->pass_flags = GCM_INSTR_PINNED;

         }

         break;

      }

      case nir_instr_type_jump:

      case nir_instr_type_ssa_undef:

      case nir_instr_type_phi:

         instr->pass_flags = GCM_INSTR_PINNED;

         break;

      default:

         unreachable("Invalid instruction type in GCM");

      }

      if (!(instr->pass_flags & GCM_INSTR_PINNED)) {

         /* If this is an unpinned instruction, go ahead and pull it out of

          * the program and put it on the instrs list.  This has a couple

          * of benifits.  First, it makes the scheduling algorithm more

          * efficient because we can avoid walking over basic blocks and

          * pinned instructions.  Second, it keeps us from causing linked

          * list confusion when we're trying to put everything in its

          * proper place at the end of the pass.

          *

          * Note that we don't use nir_instr_remove here because that also

          * cleans up uses and defs and we want to keep that information.

          */

         exec_node_remove(&instr->node);

         exec_list_push_tail(&state->instrs, &instr->node);

      }

   }

   return true;

}

static void

gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state);

/** Update an instructions schedule for the given source

 *

 * This function is called iteratively as we walk the sources of an

 * instruction.  It ensures that the given source instruction has been

 * scheduled and then update this instruction's block if the source

 * instruction is lower down the tree.

 */

static bool

gcm_schedule_early_src(nir_src *src, void *void_state)

{

   struct gcm_state *state = void_state;

   nir_instr *instr = state->instr;

   assert(src->is_ssa);

   gcm_schedule_early_instr(src->ssa->parent_instr, void_state);

   /* While the index isn't a proper dominance depth, it does have the

    * property that if A dominates B then A->index <= B->index.  Since we

    * know that this instruction must have been dominated by all of its

    * sources at some point (even if it's gone through value-numbering),

    * all of the sources must lie on the same branch of the dominance tree.

    * Therefore, we can just go ahead and just compare indices.

    */

   if (instr->block->index < src->ssa->parent_instr->block->index)

      instr->block = src->ssa->parent_instr->block;

   /* We need to restore the state instruction because it may have been

    * changed through the gcm_schedule_early_instr call above.  Since we

    * may still be iterating through sources and future calls to

    * gcm_schedule_early_src for the same instruction will still need it.

    */

   state->instr = instr;

   return true;

}

/** Schedules an instruction early

 *

 * This function performs a recursive depth-first search starting at the

 * given instruction and proceeding through the sources to schedule

 * instructions as early as they can possibly go in the dominance tree.

 * The instructions are "scheduled" by updating their instr->block field.

 */

static void

gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state)

{

   if (instr->pass_flags & GCM_INSTR_SCHEDULED_EARLY)

      return;

   instr->pass_flags |= GCM_INSTR_SCHEDULED_EARLY;

   /* Pinned instructions are already scheduled so we don't need to do

    * anything.  Also, bailing here keeps us from ever following the

    * sources of phi nodes which can be back-edges.

    */

   if (instr->pass_flags & GCM_INSTR_PINNED)

      return;

   /* Start with the instruction at the top.  As we iterate over the

    * sources, it will get moved down as needed.

    */

   instr->block = state->impl->start_block;

   state->instr = instr;

   nir_foreach_src(instr, gcm_schedule_early_src, state);

}

static void

gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state);

/** Schedules the instruction associated with the given SSA def late

 *

 * This function works by first walking all of the uses of the given SSA

 * definition, ensuring that they are scheduled, and then computing the LCA

 * (least common ancestor) of its uses.  It then schedules this instruction

 * as close to the LCA as possible while trying to stay out of loops.

 */

static bool

gcm_schedule_late_def(nir_ssa_def *def, void *void_state)

{

   struct gcm_state *state = void_state;

   nir_block *lca = NULL;

   nir_foreach_use(def, use_src) {

      nir_instr *use_instr = use_src->parent_instr;

      gcm_schedule_late_instr(use_instr, state);

      /* Phi instructions are a bit special.  SSA definitions don't have to

       * dominate the sources of the phi nodes that use them; instead, they

       * have to dominate the predecessor block corresponding to the phi

       * source.  We handle this by looking through the sources, finding

       * any that are usingg this SSA def, and using those blocks instead

       * of the one the phi lives in.

       */

      if (use_instr->type == nir_instr_type_phi) {

         nir_phi_instr *phi = nir_instr_as_phi(use_instr);

         nir_foreach_phi_src(phi, phi_src) {

            if (phi_src->src.ssa == def)

               lca = nir_dominance_lca(lca, phi_src->pred);

         }

      } else {

         lca = nir_dominance_lca(lca, use_instr->block);

      }

   }

   nir_foreach_if_use(def, use_src) {

      nir_if *if_stmt = use_src->parent_if;

      /* For if statements, we consider the block to be the one immediately

       * preceding the if CF node.

       */

      nir_block *pred_block =

         nir_cf_node_as_block(nir_cf_node_prev(&if_stmt->cf_node));

      lca = nir_dominance_lca(lca, pred_block);

   }

   /* Some instructions may never be used.  We'll just leave them scheduled

    * early and let dead code clean them up.

    */

   if (lca == NULL)

      return true;

   /* We know have the LCA of all of the uses.  If our invariants hold,

    * this is dominated by the block that we chose when scheduling early.

    * We now walk up the dominance tree and pick the lowest block that is

    * as far outside loops as we can get.

    */

   nir_block *best = lca;

   while (lca != def->parent_instr->block) {

      assert(lca);

      if (state->blocks[lca->index].loop_depth <

          state->blocks[best->index].loop_depth)

         best = lca;

      lca = lca->imm_dom;

   }

   def->parent_instr->block = best;

   return true;

}

/** Schedules an instruction late

 *

 * This function performs a depth-first search starting at the given

 * instruction and proceeding through its uses to schedule instructions as

 * late as they can reasonably go in the dominance tree.  The instructions

 * are "scheduled" by updating their instr->block field.

 *

 * The name of this function is actually a bit of a misnomer as it doesn't

 * schedule them "as late as possible" as the paper implies.  Instead, it

 * first finds the lates possible place it can schedule the instruction and

 * then possibly schedules it earlier than that.  The actual location is as

 * far down the tree as we can go while trying to stay out of loops.

 */

static void

gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state)

{

   if (instr->pass_flags & GCM_INSTR_SCHEDULED_LATE)

      return;

   instr->pass_flags |= GCM_INSTR_SCHEDULED_LATE;

   /* Pinned instructions are already scheduled so we don't need to do

    * anything.  Also, bailing here keeps us from ever following phi nodes

    * which can be back-edges.

    */

   if (instr->pass_flags & GCM_INSTR_PINNED)

      return;

   nir_foreach_ssa_def(instr, gcm_schedule_late_def, state);

}

static void

gcm_place_instr(nir_instr *instr, struct gcm_state *state);

static bool

gcm_place_instr_def(nir_ssa_def *def, void *state)

{

   nir_foreach_use(def, use_src)

      gcm_place_instr(use_src->parent_instr, state);

   return false;

}

/** Places an instrution back into the program

 *

 * The earlier passes of GCM simply choose blocks for each instruction and

 * otherwise leave them alone.  This pass actually places the instructions

 * into their chosen blocks.

 *

 * To do so, we use a standard post-order depth-first search linearization

 * algorithm.  We walk over the uses of the given instruction and ensure

 * that they are placed and then place this instruction.  Because we are

 * working on multiple blocks at a time, we keep track of the last inserted

 * instruction per-block in the state structure's block_info array.  When

 * we insert an instruction in a block we insert it before the last

 * instruction inserted in that block rather than the last instruction

 * inserted globally.

 */

static void

gcm_place_instr(nir_instr *instr, struct gcm_state *state)

{

   if (instr->pass_flags & GCM_INSTR_PLACED)

      return;

   instr->pass_flags |= GCM_INSTR_PLACED;

   /* Phi nodes are our once source of back-edges.  Since right now we are

    * only doing scheduling within blocks, we don't need to worry about

    * them since they are always at the top.  Just skip them completely.

    */

   if (instr->type == nir_instr_type_phi) {

      assert(instr->pass_flags & GCM_INSTR_PINNED);

      return;

   }

   nir_foreach_ssa_def(instr, gcm_place_instr_def, state);

   if (instr->pass_flags & GCM_INSTR_PINNED) {

      /* Pinned instructions have an implicit dependence on the pinned

       * instructions that come after them in the block.  Since the pinned

       * instructions will naturally "chain" together, we only need to

       * explicitly visit one of them.

       */

      for (nir_instr *after = nir_instr_next(instr);

           after;

           after = nir_instr_next(after)) {

         if (after->pass_flags & GCM_INSTR_PINNED) {

            gcm_place_instr(after, state);

            break;

         }

      }

   }

   struct gcm_block_info *block_info = &state->blocks[instr->block->index];

   if (!(instr->pass_flags & GCM_INSTR_PINNED)) {

      exec_node_remove(&instr->node);

      if (block_info->last_instr) {

         exec_node_insert_node_before(&block_info->last_instr->node,

                                      &instr->node);

      } else {

         /* Schedule it at the end of the block */

         nir_instr *jump_instr = nir_block_last_instr(instr->block);

         if (jump_instr && jump_instr->type == nir_instr_type_jump) {

            exec_node_insert_node_before(&jump_instr->node, &instr->node);

         } else {

            exec_list_push_tail(&instr->block->instr_list, &instr->node);

         }

      }

   }

   block_info->last_instr = instr;

}

static void

opt_gcm_impl(nir_function_impl *impl)

{

   struct gcm_state state;

   state.impl = impl;

   state.instr = NULL;

   exec_list_make_empty(&state.instrs);

   state.blocks = rzalloc_array(NULL, struct gcm_block_info, impl->num_blocks);

   nir_metadata_require(impl, nir_metadata_block_index |

                              nir_metadata_dominance);

   gcm_build_block_info(&impl->body, &state, 0);

   nir_foreach_block(impl, gcm_pin_instructions_block, &state);

   foreach_list_typed(nir_instr, instr, node, &state.instrs)

      gcm_schedule_early_instr(instr, &state);

   foreach_list_typed(nir_instr, instr, node, &state.instrs)

      gcm_schedule_late_instr(instr, &state);

   while (!exec_list_is_empty(&state.instrs)) {

      nir_instr *instr = exec_node_data(nir_instr,

                                        state.instrs.tail_pred, node);

      gcm_place_instr(instr, &state);

   }

   ralloc_free(state.blocks);

}

void

nir_opt_gcm(nir_shader *shader)

{

   nir_foreach_overload(shader, overload) {

      if (overload->impl)

         opt_gcm_impl(overload->impl);

   }

}