src/glsl/nir/nir_opt_dce.c

   1 /*
   2  * Copyright © 2014 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  * Authors:
  24  *    Connor Abbott (cwabbott0@gmail.com)
  25  *
  26  */
  27
  28 #include "nir.h"
  29
  30 /* SSA-based mark-and-sweep dead code elimination */
  31
  32 typedef struct {
  33    struct exec_node node;
  34    nir_instr *instr;
  35 } worklist_elem;
  36
  37 static void
  38 worklist_push(struct exec_list *worklist, nir_instr *instr)
  39 {
  40    worklist_elem *elem = ralloc(worklist, worklist_elem);
  41    elem->instr = instr;
  42    instr->live = true;
  43    exec_list_push_tail(worklist, &elem->node);
  44 }
  45
  46 static nir_instr *
  47 worklist_pop(struct exec_list *worklist)
  48 {
  49    struct exec_node *node = exec_list_pop_head(worklist);
  50    worklist_elem *elem = exec_node_data(worklist_elem, node, node);
  51    return elem->instr;
  52 }
  53
  54 static bool
  55 mark_live_cb(nir_src *src, void *_state)
  56 {
  57    struct exec_list *worklist = (struct exec_list *) _state;
  58
  59    if (src->is_ssa && !src->ssa->parent_instr->live) {
  60       worklist_push(worklist, src->ssa->parent_instr);
  61    }
  62
  63    return true;
  64 }
  65
  66 static void
  67 init_instr(nir_instr *instr, struct exec_list *worklist)
  68 {
  69    nir_alu_instr *alu_instr;
  70    nir_intrinsic_instr *intrin_instr;
  71    nir_tex_instr *tex_instr;
  72    nir_load_const_instr *load_const_instr;
  73
  74    instr->live = false;
  75
  76    switch (instr->type) {
  77    case nir_instr_type_call:
  78    case nir_instr_type_jump:
  79       worklist_push(worklist, instr);
  80       break;
  81
  82    case nir_instr_type_alu:
  83       alu_instr = nir_instr_as_alu(instr);
  84       if (!alu_instr->dest.dest.is_ssa)
  85          worklist_push(worklist, instr);
  86       break;
  87
  88    case nir_instr_type_intrinsic:
  89       intrin_instr = nir_instr_as_intrinsic(instr);
  90       if (nir_intrinsic_infos[intrin_instr->intrinsic].flags &
  91           NIR_INTRINSIC_CAN_ELIMINATE) {
  92          if (nir_intrinsic_infos[intrin_instr->intrinsic].has_dest &&
  93              !intrin_instr->dest.is_ssa) {
  94             worklist_push(worklist, instr);
  95          }
  96       } else {
  97          worklist_push(worklist, instr);
  98       }
  99       break;
 100
 101    case nir_instr_type_texture:
 102       tex_instr = nir_instr_as_texture(instr);
 103       if (!tex_instr->dest.is_ssa)
 104          worklist_push(worklist, instr);
 105       break;
 106
 107    case nir_instr_type_load_const:
 108       load_const_instr = nir_instr_as_load_const(instr);
 109       if (!load_const_instr->dest.is_ssa)
 110          worklist_push(worklist, instr);
 111       break;
 112
 113    default:
 114       break;
 115    }
 116 }
 117
 118 static bool
 119 init_block_cb(nir_block *block, void *_state)
 120 {
 121    struct exec_list *worklist = (struct exec_list *) _state;
 122
 123    nir_foreach_instr(block, instr)
 124       init_instr(instr, worklist);
 125
 126    if (block->cf_node.node.next != NULL && /* check that we aren't the end node */
 127        !nir_cf_node_is_last(&block->cf_node) &&
 128        nir_cf_node_next(&block->cf_node)->type == nir_cf_node_if) {
 129       nir_if *if_stmt = nir_cf_node_as_if(nir_cf_node_next(&block->cf_node));
 130       if (if_stmt->condition.is_ssa &&
 131           !if_stmt->condition.ssa->parent_instr->live)
 132          worklist_push(worklist, if_stmt->condition.ssa->parent_instr);
 133    }
 134
 135    return true;
 136 }
 137
 138 static bool
 139 delete_block_cb(nir_block *block, void *_state)
 140 {
 141    bool *progress = (bool *) _state;
 142
 143    nir_foreach_instr_safe(block, instr) {
 144       if (!instr->live) {
 145          nir_instr_remove(instr);
 146          *progress = true;
 147       }
 148    }
 149
 150    return true;
 151 }
 152
 153 bool
 154 nir_opt_dce_impl(nir_function_impl *impl)
 155 {
 156    struct exec_list *worklist = ralloc(NULL, struct exec_list);
 157    exec_list_make_empty(worklist);
 158
 159    nir_foreach_block(impl, init_block_cb, worklist);
 160
 161    while (!exec_list_is_empty(worklist)) {
 162       nir_instr *instr = worklist_pop(worklist);
 163       nir_foreach_src(instr, mark_live_cb, worklist);
 164    }
 165
 166    ralloc_free(worklist);
 167
 168    bool progress = false;
 169    nir_foreach_block(impl, delete_block_cb, &progress);
 170
 171    return progress;
 172 }
 173
 174 bool
 175 nir_opt_dce(nir_shader *shader)
 176 {
 177    bool progress = false;
 178    nir_foreach_overload(shader, overload) {
 179       if (overload->impl && nir_opt_dce_impl(overload->impl))
 180          progress = true;
 181    }
 182
 183    return progress;
 184 }