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