src/gallium/drivers/freedreno/ir3/ir3_nir_lower_if_else.c

   1 /*
   2  * Copyright © 2014 Intel Corporation
   3  * Copyright © 2015 Red Hat
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice (including the next
  13  * paragraph) shall be included in all copies or substantial portions of the
  14  * Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  22  * IN THE SOFTWARE.
  23  *
  24  * Authors:
  25  *    Jason Ekstrand (jason@jlekstrand.net)
  26  *    Rob Clark (robclark@freedesktop.org)
  27  *
  28  */
  29
  30 #include "ir3_nir.h"
  31 #include "glsl/nir/nir_builder.h"
  32
  33 /* Based on nir_opt_peephole_select, and hacked up to more aggressively
  34  * flatten anything that can be flattened
  35  *
  36  * This *might* be something that other drivers could use.  On the other
  37  * hand, I think most other hw has predicated instructions or similar
  38  * to select which side of if/else writes back result (and therefore
  39  * not having to assign unique registers to both sides of the if/else.
  40  * (And hopefully those drivers don't also have crazy scheduling reqs
  41  * and can more easily do this in their backend.)
  42  *
  43  * TODO eventually when we have proper flow control in the backend:
  44  *
  45  *  + Probably weight differently normal ALUs vs SFUs (cos/rcp/exp)
  46  *    since executing extra SFUs for the branch-not-taken path will
  47  *    generally be much more expensive.
  48  *
  49  *    Possibly what constitutes an ALU vs SFU differs between hw
  50  *    backends.. but that seems doubtful.
  51  *
  52  *  + Account for texture fetch and memory accesses (incl UBOs)
  53  *    since these will be more expensive..
  54  *
  55  *  + When if-condition is const (or uniform) or we have some way
  56  *    to know that all threads in the warp take the same branch
  57  *    then we should prefer to not flatten the if/else..
  58  */
  59
  60 struct lower_state {
  61         nir_builder b;
  62         void *mem_ctx;
  63         bool progress;
  64 };
  65
  66 static bool
  67 valid_dest(nir_block *block, nir_dest *dest)
  68 {
  69         /* It must be SSA */
  70         if (!dest->is_ssa)
  71                 return false;
  72
  73         /* We only lower blocks that do not contain other blocks
  74          * (so this is run iteratively in a loop).  Therefore if
  75          * we get this far, it should not have any if_uses:
  76          */
  77         assert(list_empty(&dest->ssa.if_uses));
  78
  79         /* The only uses of this definition must be phi's in the
  80          * successor or in the current block
  81          */
  82         nir_foreach_use(&dest->ssa, use) {
  83                 nir_instr *dest_instr = use->parent_instr;
  84                 if (dest_instr->block == block)
  85                         continue;
  86                 if ((dest_instr->type == nir_instr_type_phi) &&
  87                                 (dest_instr->block == block->successors[0]))
  88                         continue;
  89                 return false;
  90         }
  91
  92         return true;
  93 }
  94
  95 static bool
  96 block_check_for_allowed_instrs(nir_block *block)
  97 {
  98         nir_foreach_instr(block, instr) {
  99                 switch (instr->type) {
 100                 case nir_instr_type_intrinsic: {
 101                         nir_intrinsic_instr *intr = nir_instr_as_intrinsic(instr);
 102                         const nir_intrinsic_info *info =
 103                                         &nir_intrinsic_infos[intr->intrinsic];
 104
 105                         switch (intr->intrinsic) {
 106                         case nir_intrinsic_discard_if:
 107                                 /* to simplify things, we want discard_if src in ssa: */
 108                                 if (!intr->src[0].is_ssa)
 109                                         return false;
 110                                 /* fallthrough */
 111                         case nir_intrinsic_discard:
 112                                 /* discard/discard_if can be reordered, but only
 113                                  * with some special care
 114                                  */
 115                                 break;
 116                         case nir_intrinsic_store_output:
 117                                 /* TODO technically, if both if and else store
 118                                  * the same output, we can hoist that out to
 119                                  * the end of the block w/ a phi..
 120                                  * In practice, the tgsi shaders we already get
 121                                  * do this for us, so I think we don't need to
 122                                  */
 123                         default:
 124                                 if (!(info->flags & NIR_INTRINSIC_CAN_REORDER))
 125                                         return false;
 126                         }
 127
 128                         break;
 129                 }
 130
 131                 case nir_instr_type_tex: {
 132                         nir_tex_instr *tex = nir_instr_as_tex(instr);
 133                         if (!valid_dest(block, &tex->dest))
 134                                 return false;
 135                         break;
 136                 }
 137                 case nir_instr_type_phi: {
 138                         nir_phi_instr *phi = nir_instr_as_phi(instr);
 139                         if (!valid_dest(block, &phi->dest))
 140                                 return false;
 141                         break;
 142                 }
 143                 case nir_instr_type_alu: {
 144                         nir_alu_instr *alu = nir_instr_as_alu(instr);
 145                         if (!valid_dest(block, &alu->dest.dest))
 146                                 return false;
 147                         break;
 148                 }
 149
 150                 case nir_instr_type_load_const:
 151                 case nir_instr_type_ssa_undef:
 152                         break; /* always ssa dest */
 153
 154                 default:
 155                         return false;
 156                 }
 157         }
 158
 159         return true;
 160 }
 161
 162 /* flatten an then or else block: */
 163 static void
 164 flatten_block(nir_builder *bld, nir_block *if_block, nir_block *prev_block,
 165                 nir_ssa_def *condition, bool invert)
 166 {
 167         nir_foreach_instr_safe(if_block, instr) {
 168                 if (instr->type == nir_instr_type_intrinsic) {
 169                         nir_intrinsic_instr *intr = nir_instr_as_intrinsic(instr);
 170                         if ((intr->intrinsic == nir_intrinsic_discard) ||
 171                                         (intr->intrinsic == nir_intrinsic_discard_if)) {
 172                                 nir_ssa_def *discard_cond;
 173
 174                                 nir_builder_insert_after_instr(bld,
 175                                                 nir_block_last_instr(prev_block));
 176
 177                                 if (invert) {
 178                                         condition = nir_inot(bld, condition);
 179                                         invert = false;
 180                                 }
 181
 182                                 if (intr->intrinsic == nir_intrinsic_discard) {
 183                                         discard_cond = condition;
 184                                 } else {
 185                                         assert(intr->src[0].is_ssa);
 186                                         /* discard_if gets re-written w/ src and'd: */
 187                                         discard_cond = nir_iand(bld, condition, intr->src[0].ssa);
 188                                 }
 189
 190                                 nir_intrinsic_instr *discard_if =
 191                                                 nir_intrinsic_instr_create(bld->shader,
 192                                                                 nir_intrinsic_discard_if);
 193                                 discard_if->src[0] = nir_src_for_ssa(discard_cond);
 194
 195                                 nir_instr_insert_after(nir_block_last_instr(prev_block),
 196                                                 &discard_if->instr);
 197                                 nir_instr_remove(instr);
 198                                 instr = NULL;
 199                         }
 200                 }
 201                 /* if not an handled specially, just move to prev block: */
 202                 if (instr) {
 203                         /* NOTE: exec_node_remove() is safe here (vs nir_instr_remove()
 204                          * since we are re-adding the instructin back in to the prev
 205                          * block (so no dangling SSA uses)
 206                          */
 207                         exec_node_remove(&instr->node);
 208                         instr->block = prev_block;
 209                         exec_list_push_tail(&prev_block->instr_list, &instr->node);
 210                 }
 211         }
 212 }
 213
 214 static bool
 215 lower_if_else_block(nir_block *block, void *void_state)
 216 {
 217         struct lower_state *state = void_state;
 218
 219         /* If the block is empty, then it certainly doesn't have any phi nodes,
 220          * so we can skip it.  This also ensures that we do an early skip on the
 221          * end block of the function which isn't actually attached to the CFG.
 222          */
 223         if (exec_list_is_empty(&block->instr_list))
 224                 return true;
 225
 226         if (nir_cf_node_is_first(&block->cf_node))
 227                 return true;
 228
 229         nir_cf_node *prev_node = nir_cf_node_prev(&block->cf_node);
 230         if (prev_node->type != nir_cf_node_if)
 231                 return true;
 232
 233         nir_if *if_stmt = nir_cf_node_as_if(prev_node);
 234         nir_cf_node *then_node = nir_if_first_then_node(if_stmt);
 235         nir_cf_node *else_node = nir_if_first_else_node(if_stmt);
 236
 237         /* We can only have one block in each side ... */
 238         if (nir_if_last_then_node(if_stmt) != then_node ||
 239                         nir_if_last_else_node(if_stmt) != else_node)
 240                 return true;
 241
 242         nir_block *then_block = nir_cf_node_as_block(then_node);
 243         nir_block *else_block = nir_cf_node_as_block(else_node);
 244
 245         /* ... and those blocks must only contain "allowed" instructions. */
 246         if (!block_check_for_allowed_instrs(then_block) ||
 247                         !block_check_for_allowed_instrs(else_block))
 248                 return true;
 249
 250         /* condition should be ssa too, which simplifies flatten_block: */
 251         if (!if_stmt->condition.is_ssa)
 252                 return true;
 253
 254         /* At this point, we know that the previous CFG node is an if-then
 255          * statement containing only moves to phi nodes in this block.  We can
 256          * just remove that entire CF node and replace all of the phi nodes with
 257          * selects.
 258          */
 259
 260         nir_block *prev_block = nir_cf_node_as_block(nir_cf_node_prev(prev_node));
 261         assert(prev_block->cf_node.type == nir_cf_node_block);
 262
 263         /* First, we move the remaining instructions from the blocks to the
 264          * block before.  There are a few things that need handling specially
 265          * like discard/discard_if.
 266          */
 267         flatten_block(&state->b, then_block, prev_block,
 268                         if_stmt->condition.ssa, false);
 269         flatten_block(&state->b, else_block, prev_block,
 270                         if_stmt->condition.ssa, true);
 271
 272         nir_foreach_instr_safe(block, instr) {
 273                 if (instr->type != nir_instr_type_phi)
 274                         break;
 275
 276                 nir_phi_instr *phi = nir_instr_as_phi(instr);
 277                 nir_alu_instr *sel = nir_alu_instr_create(state->mem_ctx, nir_op_bcsel);
 278                 nir_src_copy(&sel->src[0].src, &if_stmt->condition, state->mem_ctx);
 279                 /* Splat the condition to all channels */
 280                 memset(sel->src[0].swizzle, 0, sizeof sel->src[0].swizzle);
 281
 282                 assert(exec_list_length(&phi->srcs) == 2);
 283                 nir_foreach_phi_src(phi, src) {
 284                         assert(src->pred == then_block || src->pred == else_block);
 285                         assert(src->src.is_ssa);
 286
 287                         unsigned idx = src->pred == then_block ? 1 : 2;
 288                         nir_src_copy(&sel->src[idx].src, &src->src, state->mem_ctx);
 289                 }
 290
 291                 nir_ssa_dest_init(&sel->instr, &sel->dest.dest,
 292                                 phi->dest.ssa.num_components, phi->dest.ssa.name);
 293                 sel->dest.write_mask = (1 << phi->dest.ssa.num_components) - 1;
 294
 295                 nir_ssa_def_rewrite_uses(&phi->dest.ssa,
 296                                 nir_src_for_ssa(&sel->dest.dest.ssa),
 297                                 state->mem_ctx);
 298
 299                 nir_instr_insert_before(&phi->instr, &sel->instr);
 300                 nir_instr_remove(&phi->instr);
 301         }
 302
 303         nir_cf_node_remove(&if_stmt->cf_node);
 304         state->progress = true;
 305
 306         return true;
 307 }
 308
 309 static bool
 310 lower_if_else_impl(nir_function_impl *impl)
 311 {
 312         struct lower_state state;
 313
 314         state.mem_ctx = ralloc_parent(impl);
 315         state.progress = false;
 316         nir_builder_init(&state.b, impl);
 317
 318         nir_foreach_block(impl, lower_if_else_block, &state);
 319
 320         if (state.progress)
 321                 nir_metadata_preserve(impl, nir_metadata_none);
 322
 323         return state.progress;
 324 }
 325
 326 bool
 327 ir3_nir_lower_if_else(nir_shader *shader)
 328 {
 329         bool progress = false;
 330
 331         nir_foreach_overload(shader, overload) {
 332                 if (overload->impl)
 333                         progress |= lower_if_else_impl(overload->impl);
 334         }
 335
 336         return progress;
 337 }