src/glsl/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 *parent_cf_list;
  31    struct exec_list *cf_list;
  32    nir_loop *loop;
  33    nir_if *if_stmt;
  34    nir_variable *return_flag;
  35 };
  36
  37 static bool lower_returns_in_cf_list(struct exec_list *cf_list,
  38                                      struct lower_returns_state *state);
  39
  40 static bool
  41 lower_returns_in_loop(nir_loop *loop, struct lower_returns_state *state)
  42 {
  43    nir_loop *parent = state->loop;
  44    state->loop = loop;
  45    bool progress = lower_returns_in_cf_list(&loop->body, state);
  46    state->loop = parent;
  47
  48    /* Nothing interesting */
  49    if (!progress)
  50       return false;
  51
  52    /* In this case, there was a return somewhere inside of the loop.  That
  53     * return would have been turned into a write to the return_flag
  54     * variable and a break.  We need to insert a predicated return right
  55     * after the loop ends.
  56     */
  57
  58    assert(state->return_flag);
  59
  60    nir_intrinsic_instr *load =
  61       nir_intrinsic_instr_create(state->builder.shader, nir_intrinsic_load_var);
  62    load->num_components = 1;
  63    load->variables[0] = nir_deref_var_create(load, state->return_flag);
  64    nir_ssa_dest_init(&load->instr, &load->dest, 1, "return");
  65    nir_instr_insert(nir_after_cf_node(&loop->cf_node), &load->instr);
  66
  67    nir_if *if_stmt = nir_if_create(state->builder.shader);
  68    if_stmt->condition = nir_src_for_ssa(&load->dest.ssa);
  69    nir_cf_node_insert(nir_after_instr(&load->instr), &if_stmt->cf_node);
  70
  71    nir_jump_instr *ret =
  72       nir_jump_instr_create(state->builder.shader, nir_jump_return);
  73    nir_instr_insert(nir_before_cf_list(&if_stmt->then_list), &ret->instr);
  74
  75    return true;
  76 }
  77
  78 static bool
  79 lower_returns_in_if(nir_if *if_stmt, struct lower_returns_state *state)
  80 {
  81    bool progress;
  82
  83    nir_if *parent = state->if_stmt;
  84    state->if_stmt = if_stmt;
  85    progress = lower_returns_in_cf_list(&if_stmt->then_list, state);
  86    progress = lower_returns_in_cf_list(&if_stmt->else_list, state) || progress;
  87    state->if_stmt = parent;
  88
  89    return progress;
  90 }
  91
  92 static bool
  93 lower_returns_in_block(nir_block *block, struct lower_returns_state *state)
  94 {
  95    if (block->predecessors->entries == 0 &&
  96        block != nir_start_block(state->builder.impl)) {
  97       /* This block is unreachable.  Delete it and everything after it. */
  98       nir_cf_list list;
  99       nir_cf_extract(&list, nir_before_cf_node(&block->cf_node),
 100                             nir_after_cf_list(state->cf_list));
 101
 102       if (exec_list_is_empty(&list.list)) {
 103          /* There's nothing here, which also means there's nothing in this
 104           * block so we have nothing to do.
 105           */
 106          return false;
 107       } else {
 108          nir_cf_delete(&list);
 109          return true;
 110       }
 111    }
 112
 113    nir_instr *last_instr = nir_block_last_instr(block);
 114    if (last_instr == NULL)
 115       return false;
 116
 117    if (last_instr->type != nir_instr_type_jump)
 118       return false;
 119
 120    nir_jump_instr *jump = nir_instr_as_jump(last_instr);
 121    if (jump->type != nir_jump_return)
 122       return false;
 123
 124    if (state->loop) {
 125       /* We're in a loop.  Just set the return flag to true and break.
 126        * lower_returns_in_loop will do the rest.
 127        */
 128       nir_builder *b = &state->builder;
 129       b->cursor = nir_before_instr(&jump->instr);
 130
 131       if (state->return_flag == NULL) {
 132          state->return_flag =
 133             nir_local_variable_create(b->impl, glsl_bool_type(), "return");
 134
 135          /* Set a default value of false */
 136          state->return_flag->constant_initializer =
 137             rzalloc(state->return_flag, nir_constant);
 138       }
 139
 140       nir_store_var(b, state->return_flag, nir_imm_int(b, NIR_TRUE));
 141       jump->type = nir_jump_return;
 142    } else if (state->if_stmt) {
 143       /* If we're not in a loop but in an if, just move the rest of the CF
 144        * list into the the other case of the if.
 145        */
 146       nir_cf_list list;
 147       nir_cf_extract(&list, nir_after_cf_node(&state->if_stmt->cf_node),
 148                             nir_after_cf_list(state->parent_cf_list));
 149
 150       nir_instr_remove(&jump->instr);
 151
 152       if (state->cf_list == &state->if_stmt->then_list) {
 153          nir_cf_reinsert(&list,
 154                          nir_after_cf_list(&state->if_stmt->else_list));
 155       } else if (state->cf_list == &state->if_stmt->else_list) {
 156          nir_cf_reinsert(&list,
 157                          nir_after_cf_list(&state->if_stmt->then_list));
 158       } else {
 159          unreachable("Invalid CF list");
 160       }
 161    } else {
 162       nir_instr_remove(&jump->instr);
 163
 164       /* No if, no nothing.  Just delete the return and whatever follows. */
 165       nir_cf_list list;
 166       nir_cf_extract(&list, nir_after_cf_node(&block->cf_node),
 167                             nir_after_cf_list(state->parent_cf_list));
 168       nir_cf_delete(&list);
 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 *prev_parent_list = state->parent_cf_list;
 181    state->parent_cf_list = state->cf_list;
 182    state->cf_list = cf_list;
 183
 184    foreach_list_typed_reverse_safe(nir_cf_node, node, node, cf_list) {
 185       switch (node->type) {
 186       case nir_cf_node_block:
 187          if (lower_returns_in_block(nir_cf_node_as_block(node), state))
 188             progress = true;
 189          break;
 190
 191       case nir_cf_node_if:
 192          if (lower_returns_in_if(nir_cf_node_as_if(node), state))
 193             progress = true;
 194          break;
 195
 196       case nir_cf_node_loop:
 197          if (lower_returns_in_loop(nir_cf_node_as_loop(node), state))
 198             progress = true;
 199          break;
 200
 201       default:
 202          unreachable("Invalid inner CF node type");
 203       }
 204    }
 205
 206    state->cf_list = state->parent_cf_list;
 207    state->parent_cf_list = prev_parent_list;
 208
 209    return progress;
 210 }
 211
 212 bool
 213 nir_lower_returns_impl(nir_function_impl *impl)
 214 {
 215    struct lower_returns_state state;
 216
 217    state.parent_cf_list = NULL;
 218    state.cf_list = &impl->body;
 219    state.loop = NULL;
 220    state.if_stmt = NULL;
 221    state.return_flag = NULL;
 222    nir_builder_init(&state.builder, impl);
 223
 224    bool progress = lower_returns_in_cf_list(&impl->body, &state);
 225
 226    if (progress)
 227       nir_metadata_preserve(impl, nir_metadata_none);
 228
 229    return progress;
 230 }
 231
 232 bool
 233 nir_lower_returns(nir_shader *shader)
 234 {
 235    bool progress = false;
 236
 237    nir_foreach_overload(shader, overload) {
 238       if (overload->impl)
 239          progress = nir_lower_returns_impl(overload->impl) || progress;
 240    }
 241
 242    return progress;
 243 }