src/compiler/nir/nir_opt_trivial_continues.c

   1 /*
   2  * Copyright © 2016 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
  24 #include "nir.h"
  25
  26 static bool
  27 instr_is_continue(nir_instr *instr)
  28 {
  29    if (instr->type != nir_instr_type_jump)
  30       return false;
  31
  32    return nir_instr_as_jump(instr)->type == nir_jump_continue;
  33 }
  34
  35 static bool
  36 lower_trivial_continues_block(nir_block *block, nir_loop *loop)
  37 {
  38    bool progress = false;
  39    nir_instr *first_instr = nir_block_first_instr(block);
  40    if (!first_instr || instr_is_continue(first_instr)) {
  41       /* The block contains only a continue if anything */
  42       nir_cf_node *prev_node = nir_cf_node_prev(&block->cf_node);
  43       if (prev_node && prev_node->type == nir_cf_node_if) {
  44          nir_if *prev_if = nir_cf_node_as_if(prev_node);
  45          progress |= lower_trivial_continues_block(
  46             nir_if_last_then_block(prev_if), loop);
  47          progress |= lower_trivial_continues_block(
  48             nir_if_last_else_block(prev_if), loop);
  49       }
  50
  51       /* The lower_phis_to_regs helper is smart enough to push phi sources as
  52        * far up if-ladders as it possibly can.  In other words, the recursive
  53        * calls above shouldn't be adding instructions to this block since it
  54        * follows an if statement.
  55        */
  56       first_instr = nir_block_first_instr(block);
  57       assert(!first_instr || instr_is_continue(first_instr));
  58    }
  59
  60    nir_instr *last_instr = nir_block_last_instr(block);
  61    if (!last_instr || !instr_is_continue(last_instr))
  62       return progress;
  63
  64    /* We're at the end of a block that goes straight through to the end of the
  65     * loop and continues to the top.  We can exit normally instead of jump.
  66     */
  67    nir_lower_phis_to_regs_block(nir_loop_first_block(loop));
  68    nir_instr_remove(last_instr);
  69    return true;
  70 }
  71
  72 static bool
  73 lower_trivial_continues_list(struct exec_list *cf_list,
  74                              bool list_ends_at_loop_tail,
  75                              nir_loop *loop)
  76 {
  77    bool progress = false;
  78    foreach_list_typed(nir_cf_node, cf_node, node, cf_list) {
  79       bool at_loop_tail = list_ends_at_loop_tail &&
  80                           &cf_node->node == exec_list_get_tail(cf_list);
  81       switch (cf_node->type) {
  82       case nir_cf_node_block:
  83          break;
  84
  85       case nir_cf_node_if: {
  86          nir_if *nif = nir_cf_node_as_if(cf_node);
  87          if (lower_trivial_continues_list(&nif->then_list, at_loop_tail, loop))
  88             progress = true;
  89          if (lower_trivial_continues_list(&nif->else_list, at_loop_tail, loop))
  90             progress = true;
  91          break;
  92       }
  93
  94       case nir_cf_node_loop: {
  95          nir_loop *loop = nir_cf_node_as_loop(cf_node);
  96          if (lower_trivial_continues_list(&loop->body, true, loop))
  97             progress = true;
  98          if (lower_trivial_continues_block(nir_loop_last_block(loop), loop))
  99             progress = true;
 100          break;
 101       }
 102
 103       case nir_cf_node_function:
 104          unreachable("Invalid cf type");
 105       }
 106    }
 107
 108    return progress;
 109 }
 110
 111 /**
 112  * This simple pass gets rid of any "trivial" continues, i.e. those that are
 113  * at the tail of a loop where we can just delete the continue instruction and
 114  * control-flow will naturally and harmlessly take us back to the top of the
 115  * loop.
 116  */
 117 bool
 118 nir_opt_trivial_continues(nir_shader *shader)
 119 {
 120    bool progress = false;
 121
 122    nir_foreach_function(function, shader) {
 123       if (function->impl == NULL)
 124          continue;
 125
 126       /* First we run the simple pass to get rid of pesky continues */
 127       if (lower_trivial_continues_list(&function->impl->body, false, NULL)) {
 128          nir_metadata_preserve(function->impl, nir_metadata_none);
 129
 130          /* If that made progress, we're no longer really in SSA form. */
 131          nir_lower_regs_to_ssa_impl(function->impl);
 132          progress = true;
 133       } else {
 134          nir_metadata_preserve(function->impl, nir_metadata_all);
 135       }
 136    }
 137
 138    return progress;
 139 }