src/compiler/nir/nir_lower_returns.c

   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 appropriately 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 }