Home | History | Annotate | Download | only in nir 
      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       }
    134    }
    135 
    136    return progress;
    137 }
    138