src/compiler/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 #include "nir_worklist.h"
  30
  31 /* SSA-based mark-and-sweep dead code elimination */
  32
  33 static void
  34 mark_and_push(nir_instr_worklist *wl, nir_instr *instr)
  35 {
  36    nir_instr_worklist_push_tail(wl, instr);
  37    instr->pass_flags = 1;
  38 }
  39
  40 static bool
  41 mark_live_cb(nir_src *src, void *_state)
  42 {
  43    nir_instr_worklist *worklist = (nir_instr_worklist *) _state;
  44
  45    if (src->is_ssa && !src->ssa->parent_instr->pass_flags)
  46       mark_and_push(worklist, src->ssa->parent_instr);
  47
  48    return true;
  49 }
  50
  51 static void
  52 init_instr(nir_instr *instr, nir_instr_worklist *worklist)
  53 {
  54    nir_alu_instr *alu_instr;
  55    nir_deref_instr *deref_instr;
  56    nir_intrinsic_instr *intrin_instr;
  57    nir_tex_instr *tex_instr;
  58
  59    /* We use the pass_flags to store the live/dead information.  In DCE, we
  60     * just treat it as a zero/non-zero boolean for whether or not the
  61     * instruction is live.
  62     */
  63    instr->pass_flags = 0;
  64
  65    switch (instr->type) {
  66    case nir_instr_type_call:
  67    case nir_instr_type_jump:
  68       mark_and_push(worklist, instr);
  69       break;
  70
  71    case nir_instr_type_alu:
  72       alu_instr = nir_instr_as_alu(instr);
  73       if (!alu_instr->dest.dest.is_ssa)
  74          mark_and_push(worklist, instr);
  75       break;
  76
  77    case nir_instr_type_deref:
  78       deref_instr = nir_instr_as_deref(instr);
  79       if (!deref_instr->dest.is_ssa)
  80          mark_and_push(worklist, instr);
  81       break;
  82
  83    case nir_instr_type_intrinsic:
  84       intrin_instr = nir_instr_as_intrinsic(instr);
  85       if (nir_intrinsic_infos[intrin_instr->intrinsic].flags &
  86           NIR_INTRINSIC_CAN_ELIMINATE) {
  87          if (nir_intrinsic_infos[intrin_instr->intrinsic].has_dest &&
  88              !intrin_instr->dest.is_ssa) {
  89             mark_and_push(worklist, instr);
  90          }
  91       } else {
  92          mark_and_push(worklist, instr);
  93       }
  94       break;
  95
  96    case nir_instr_type_tex:
  97       tex_instr = nir_instr_as_tex(instr);
  98       if (!tex_instr->dest.is_ssa)
  99          mark_and_push(worklist, instr);
 100       break;
 101
 102    default:
 103       break;
 104    }
 105 }
 106
 107 static bool
 108 init_block(nir_block *block, nir_instr_worklist *worklist)
 109 {
 110    nir_foreach_instr(instr, block)
 111       init_instr(instr, worklist);
 112
 113    nir_if *following_if = nir_block_get_following_if(block);
 114    if (following_if) {
 115       if (following_if->condition.is_ssa &&
 116           !following_if->condition.ssa->parent_instr->pass_flags)
 117          mark_and_push(worklist, following_if->condition.ssa->parent_instr);
 118    }
 119
 120    return true;
 121 }
 122
 123 static bool
 124 nir_opt_dce_impl(nir_function_impl *impl)
 125 {
 126    nir_instr_worklist *worklist = nir_instr_worklist_create();
 127
 128    nir_foreach_block(block, impl) {
 129       init_block(block, worklist);
 130    }
 131
 132    nir_foreach_instr_in_worklist(instr, worklist)
 133       nir_foreach_src(instr, mark_live_cb, worklist);
 134
 135    nir_instr_worklist_destroy(worklist);
 136
 137    bool progress = false;
 138
 139    nir_foreach_block(block, impl) {
 140       nir_foreach_instr_safe(instr, block) {
 141          if (!instr->pass_flags) {
 142             nir_instr_remove(instr);
 143             progress = true;
 144          }
 145       }
 146    }
 147
 148    if (progress) {
 149       nir_metadata_preserve(impl, nir_metadata_block_index |
 150                                   nir_metadata_dominance);
 151    } else {
 152       nir_metadata_preserve(impl, nir_metadata_all);
 153    }
 154
 155    return progress;
 156 }
 157
 158 bool
 159 nir_opt_dce(nir_shader *shader)
 160 {
 161    bool progress = false;
 162    nir_foreach_function(function, shader) {
 163       if (function->impl && nir_opt_dce_impl(function->impl))
 164          progress = true;
 165    }
 166
 167    return progress;
 168 }