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