Home | History | Annotate | Download | only in nir 
      1 /*
      2  * Copyright  2015 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 #include "nir_builder.h"
     26 #include "nir_control_flow.h"
     27 
     28 struct lower_returns_state {
     29    nir_builder builder;
     30    struct exec_list *cf_list;
     31    nir_loop *loop;
     32    nir_variable *return_flag;
     33 
     34    /* This indicates that we have a return which is predicated on some form of
     35     * control-flow.  Since whether or not the return happens can only be
     36     * determined dynamically at run-time, everything that occurs afterwards
     37     * needs to be predicated on the return flag variable.
     38     */
     39    bool has_predicated_return;
     40 };
     41 
     42 static bool lower_returns_in_cf_list(struct exec_list *cf_list,
     43                                      struct lower_returns_state *state);
     44 
     45 static void
     46 predicate_following(nir_cf_node *node, struct lower_returns_state *state)
     47 {
     48    nir_builder *b = &state->builder;
     49    b->cursor = nir_after_cf_node_and_phis(node);
     50 
     51    if (nir_cursors_equal(b->cursor, nir_after_cf_list(state->cf_list)))
     52       return; /* Nothing to predicate */
     53 
     54    assert(state->return_flag);
     55 
     56    nir_if *if_stmt = nir_if_create(b->shader);
     57    if_stmt->condition = nir_src_for_ssa(nir_load_var(b, state->return_flag));
     58    nir_cf_node_insert(b->cursor, &if_stmt->cf_node);
     59 
     60    if (state->loop) {
     61       /* If we're inside of a loop, then all we need to do is insert a
     62        * conditional break.
     63        */
     64       nir_jump_instr *brk =
     65          nir_jump_instr_create(state->builder.shader, nir_jump_break);
     66       nir_instr_insert(nir_before_cf_list(&if_stmt->then_list), &brk->instr);
     67    } else {
     68       /* Otherwise, we need to actually move everything into the else case
     69        * of the if statement.
     70        */
     71       nir_cf_list list;
     72       nir_cf_extract(&list, nir_after_cf_node(&if_stmt->cf_node),
     73                             nir_after_cf_list(state->cf_list));
     74       assert(!exec_list_is_empty(&list.list));
     75       nir_cf_reinsert(&list, nir_before_cf_list(&if_stmt->else_list));
     76    }
     77 }
     78 
     79 static bool
     80 lower_returns_in_loop(nir_loop *loop, struct lower_returns_state *state)
     81 {
     82    nir_loop *parent = state->loop;
     83    state->loop = loop;
     84    bool progress = lower_returns_in_cf_list(&loop->body, state);
     85    state->loop = parent;
     86 
     87    /* If the recursive call made progress, then there were returns inside
     88     * of the loop.  These would have been lowered to breaks with the return
     89     * flag set to true.  We need to predicate everything following the loop
     90     * on the return flag.
     91     */
     92    if (progress) {
     93       predicate_following(&loop->cf_node, state);
     94       state->has_predicated_return = true;
     95    }
     96 
     97    return progress;
     98 }
     99 
    100 static bool
    101 lower_returns_in_if(nir_if *if_stmt, struct lower_returns_state *state)
    102 {
    103    bool progress, then_progress, else_progress;
    104 
    105    bool has_predicated_return = state->has_predicated_return;
    106    state->has_predicated_return = false;
    107 
    108    then_progress = lower_returns_in_cf_list(&if_stmt->then_list, state);
    109    else_progress = lower_returns_in_cf_list(&if_stmt->else_list, state);
    110    progress = then_progress || else_progress;
    111 
    112    /* If either of the recursive calls made progress, then there were
    113     * returns inside of the body of the if.  If we're in a loop, then these
    114     * were lowered to breaks which automatically skip to the end of the
    115     * loop so we don't have to do anything.  If we're not in a loop, then
    116     * all we know is that the return flag is set appropreately and that the
    117     * recursive calls ensured that nothing gets executed *inside* the if
    118     * after a return.  In order to ensure nothing outside gets executed
    119     * after a return, we need to predicate everything following on the
    120     * return flag.
    121     */
    122    if (progress && !state->loop) {
    123       if (state->has_predicated_return) {
    124          predicate_following(&if_stmt->cf_node, state);
    125       } else {
    126          /* If there are no nested returns we can just add the instructions to
    127           * the end of the branch that doesn't have the return.
    128           */
    129          nir_cf_list list;
    130          nir_cf_extract(&list, nir_after_cf_node(&if_stmt->cf_node),
    131                         nir_after_cf_list(state->cf_list));
    132 
    133          if (then_progress && else_progress) {
    134             /* Both branches return so delete instructions following the if */
    135             nir_cf_delete(&list);
    136          } else if (then_progress) {
    137             nir_cf_reinsert(&list, nir_after_cf_list(&if_stmt->else_list));
    138          } else {
    139             nir_cf_reinsert(&list, nir_after_cf_list(&if_stmt->then_list));
    140          }
    141       }
    142    }
    143 
    144    state->has_predicated_return = progress || has_predicated_return;
    145 
    146    return progress;
    147 }
    148 
    149 static bool
    150 lower_returns_in_block(nir_block *block, struct lower_returns_state *state)
    151 {
    152    if (block->predecessors->entries == 0 &&
    153        block != nir_start_block(state->builder.impl)) {
    154       /* This block is unreachable.  Delete it and everything after it. */
    155       nir_cf_list list;
    156       nir_cf_extract(&list, nir_before_cf_node(&block->cf_node),
    157                             nir_after_cf_list(state->cf_list));
    158 
    159       if (exec_list_is_empty(&list.list)) {
    160          /* There's nothing here, which also means there's nothing in this
    161           * block so we have nothing to do.
    162           */
    163          return false;
    164       } else {
    165          nir_cf_delete(&list);
    166          return true;
    167       }
    168    }
    169 
    170    nir_instr *last_instr = nir_block_last_instr(block);
    171    if (last_instr == NULL)
    172       return false;
    173 
    174    if (last_instr->type != nir_instr_type_jump)
    175       return false;
    176 
    177    nir_jump_instr *jump = nir_instr_as_jump(last_instr);
    178    if (jump->type != nir_jump_return)
    179       return false;
    180 
    181    nir_instr_remove(&jump->instr);
    182 
    183    nir_builder *b = &state->builder;
    184 
    185    /* Set the return flag */
    186    if (state->return_flag == NULL) {
    187       state->return_flag =
    188          nir_local_variable_create(b->impl, glsl_bool_type(), "return");
    189 
    190       /* Initialize the variable to 0 */
    191       b->cursor = nir_before_cf_list(&b->impl->body);
    192       nir_store_var(b, state->return_flag, nir_imm_int(b, NIR_FALSE), 1);
    193    }
    194 
    195    b->cursor = nir_after_block(block);
    196    nir_store_var(b, state->return_flag, nir_imm_int(b, NIR_TRUE), 1);
    197 
    198    if (state->loop) {
    199       /* We're in a loop;  we need to break out of it. */
    200       nir_jump(b, nir_jump_break);
    201    } else {
    202       /* Not in a loop;  we'll deal with predicating later*/
    203       assert(nir_cf_node_next(&block->cf_node) == NULL);
    204    }
    205 
    206    return true;
    207 }
    208 
    209 static bool
    210 lower_returns_in_cf_list(struct exec_list *cf_list,
    211                          struct lower_returns_state *state)
    212 {
    213    bool progress = false;
    214 
    215    struct exec_list *parent_list = state->cf_list;
    216    state->cf_list = cf_list;
    217 
    218    /* We iterate over the list backwards because any given lower call may
    219     * take everything following the given CF node and predicate it.  In
    220     * order to avoid recursion/iteration problems, we want everything after
    221     * a given node to already be lowered before this happens.
    222     */
    223    foreach_list_typed_reverse_safe(nir_cf_node, node, node, cf_list) {
    224       switch (node->type) {
    225       case nir_cf_node_block:
    226          if (lower_returns_in_block(nir_cf_node_as_block(node), state))
    227             progress = true;
    228          break;
    229 
    230       case nir_cf_node_if:
    231          if (lower_returns_in_if(nir_cf_node_as_if(node), state))
    232             progress = true;
    233          break;
    234 
    235       case nir_cf_node_loop:
    236          if (lower_returns_in_loop(nir_cf_node_as_loop(node), state))
    237             progress = true;
    238          break;
    239 
    240       default:
    241          unreachable("Invalid inner CF node type");
    242       }
    243    }
    244 
    245    state->cf_list = parent_list;
    246 
    247    return progress;
    248 }
    249 
    250 bool
    251 nir_lower_returns_impl(nir_function_impl *impl)
    252 {
    253    struct lower_returns_state state;
    254 
    255    state.cf_list = &impl->body;
    256    state.loop = NULL;
    257    state.return_flag = NULL;
    258    state.has_predicated_return = false;
    259    nir_builder_init(&state.builder, impl);
    260 
    261    bool progress = lower_returns_in_cf_list(&impl->body, &state);
    262 
    263    if (progress) {
    264       nir_metadata_preserve(impl, nir_metadata_none);
    265       nir_repair_ssa_impl(impl);
    266    }
    267 
    268    return progress;
    269 }
    270 
    271 bool
    272 nir_lower_returns(nir_shader *shader)
    273 {
    274    bool progress = false;
    275 
    276    nir_foreach_function(function, shader) {
    277       if (function->impl)
    278          progress = nir_lower_returns_impl(function->impl) || progress;
    279    }
    280 
    281    return progress;
    282 }
    283