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
30static bool
31is_dest_live(const nir_dest *dest, BITSET_WORD *defs_live)
32{
33   return !dest->is_ssa || BITSET_TEST(defs_live, dest->ssa.index);
34}
35
36static bool
37mark_src_live(const nir_src *src, BITSET_WORD *defs_live)
38{
39   if (src->is_ssa && !BITSET_TEST(defs_live, src->ssa->index)) {
40      BITSET_SET(defs_live, src->ssa->index);
41      return true;
42   } else {
43      return false;
44   }
45}
46
47static bool
48mark_live_cb(nir_src *src, void *defs_live)
49{
50   mark_src_live(src, defs_live);
51   return true;
52}
53
54static bool
55is_live(BITSET_WORD *defs_live, nir_instr *instr)
56{
57   switch (instr->type) {
58   case nir_instr_type_call:
59   case nir_instr_type_jump:
60      return true;
61   case nir_instr_type_alu: {
62      nir_alu_instr *alu = nir_instr_as_alu(instr);
63      return is_dest_live(&alu->dest.dest, defs_live);
64   }
65   case nir_instr_type_deref: {
66      nir_deref_instr *deref = nir_instr_as_deref(instr);
67      return is_dest_live(&deref->dest, defs_live);
68   }
69   case nir_instr_type_intrinsic: {
70      nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
71      const nir_intrinsic_info *info = &nir_intrinsic_infos[intrin->intrinsic];
72      return !(info->flags & NIR_INTRINSIC_CAN_ELIMINATE) ||
73             (info->has_dest && is_dest_live(&intrin->dest, defs_live));
74   }
75   case nir_instr_type_tex: {
76      nir_tex_instr *tex = nir_instr_as_tex(instr);
77      return is_dest_live(&tex->dest, defs_live);
78   }
79   case nir_instr_type_phi: {
80      nir_phi_instr *phi = nir_instr_as_phi(instr);
81      return is_dest_live(&phi->dest, defs_live);
82   }
83   case nir_instr_type_load_const: {
84      nir_load_const_instr *lc = nir_instr_as_load_const(instr);
85      return BITSET_TEST(defs_live, lc->def.index);
86   }
87   case nir_instr_type_ssa_undef: {
88      nir_ssa_undef_instr *undef = nir_instr_as_ssa_undef(instr);
89      return BITSET_TEST(defs_live, undef->def.index);
90   }
91   case nir_instr_type_parallel_copy: {
92      nir_parallel_copy_instr *pc = nir_instr_as_parallel_copy(instr);
93      nir_foreach_parallel_copy_entry(entry, pc) {
94         if (is_dest_live(&entry->dest, defs_live))
95            return true;
96      }
97      return false;
98   }
99   default:
100      unreachable("unexpected instr type");
101   }
102}
103
104struct loop_state {
105   bool header_phis_changed;
106   nir_block *preheader;
107};
108
109static bool
110dce_block(nir_block *block, BITSET_WORD *defs_live, struct loop_state *loop)
111{
112   bool progress = false;
113   bool phis_changed = false;
114   nir_foreach_instr_reverse_safe(instr, block) {
115      bool live = is_live(defs_live, instr);
116      if (live) {
117         if (instr->type == nir_instr_type_phi) {
118            nir_foreach_phi_src(src, nir_instr_as_phi(instr)) {
119               phis_changed |= mark_src_live(&src->src, defs_live) &&
120                               src->pred != loop->preheader;
121            }
122         } else {
123            nir_foreach_src(instr, mark_live_cb, defs_live);
124         }
125      }
126
127      /* If we're not in a loop, remove it now if it's dead. If we are in a
128       * loop, leave instructions to be removed later if they're still dead.
129       */
130      if (loop->preheader) {
131         instr->pass_flags = live;
132      } else if (!live) {
133         nir_instr_remove(instr);
134         progress = true;
135      }
136   }
137
138   /* Because blocks are visited in reverse and this stomps header_phis_changed,
139    * we don't have to check whether the current block is a loop header before
140    * setting header_phis_changed.
141    */
142   loop->header_phis_changed = phis_changed;
143
144   return progress;
145}
146
147static bool
148dce_cf_list(struct exec_list *cf_list, BITSET_WORD *defs_live,
149            struct loop_state *parent_loop)
150{
151   bool progress = false;
152   foreach_list_typed_reverse(nir_cf_node, cf_node, node, cf_list) {
153      switch (cf_node->type) {
154      case nir_cf_node_block: {
155         nir_block *block = nir_cf_node_as_block(cf_node);
156         progress |= dce_block(block, defs_live, parent_loop);
157         break;
158      }
159      case nir_cf_node_if: {
160         nir_if *nif = nir_cf_node_as_if(cf_node);
161         progress |= dce_cf_list(&nif->else_list, defs_live, parent_loop);
162         progress |= dce_cf_list(&nif->then_list, defs_live, parent_loop);
163         mark_src_live(&nif->condition, defs_live);
164         break;
165      }
166      case nir_cf_node_loop: {
167         nir_loop *loop = nir_cf_node_as_loop(cf_node);
168
169         struct loop_state inner_state;
170         inner_state.preheader = nir_cf_node_as_block(nir_cf_node_prev(cf_node));
171         inner_state.header_phis_changed = false;
172
173         /* Fast path if the loop has no continues: we can remove instructions
174          * as we mark the others live.
175          */
176         struct set *predecessors = nir_loop_first_block(loop)->predecessors;
177         if (predecessors->entries == 1 &&
178             _mesa_set_next_entry(predecessors, NULL)->key == inner_state.preheader) {
179            progress |= dce_cf_list(&loop->body, defs_live, parent_loop);
180            break;
181         }
182
183         /* Mark instructions as live until there is no more progress. */
184         do {
185            /* dce_cf_list() resets inner_state.header_phis_changed itself, so
186             * it doesn't have to be done here.
187             */
188            dce_cf_list(&loop->body, defs_live, &inner_state);
189         } while (inner_state.header_phis_changed);
190
191         /* We don't know how many times mark_cf_list() will repeat, so
192          * remove instructions separately.
193          *
194          * By checking parent_loop->preheader, we ensure that we only do this
195          * walk for the outer-most loops so it only happens once.
196          */
197         if (!parent_loop->preheader) {
198            nir_foreach_block_in_cf_node(block, cf_node) {
199               nir_foreach_instr_safe(instr, block) {
200                  if (!instr->pass_flags) {
201                     nir_instr_remove(instr);
202                     progress = true;
203                  }
204               }
205            }
206         }
207         break;
208      }
209      case nir_cf_node_function:
210         unreachable("Invalid cf type");
211      }
212   }
213
214   return progress;
215}
216
217static bool
218nir_opt_dce_impl(nir_function_impl *impl)
219{
220   assert(impl->structured);
221
222   BITSET_WORD *defs_live = rzalloc_array(NULL, BITSET_WORD,
223                                          BITSET_WORDS(impl->ssa_alloc));
224
225   struct loop_state loop;
226   loop.preheader = NULL;
227   bool progress = dce_cf_list(&impl->body, defs_live, &loop);
228
229   ralloc_free(defs_live);
230
231   if (progress) {
232      nir_metadata_preserve(impl, nir_metadata_block_index |
233                                  nir_metadata_dominance);
234   } else {
235      nir_metadata_preserve(impl, nir_metadata_all);
236   }
237
238   return progress;
239}
240
241bool
242nir_opt_dce(nir_shader *shader)
243{
244   bool progress = false;
245   nir_foreach_function(function, shader) {
246      if (function->impl && nir_opt_dce_impl(function->impl))
247         progress = true;
248   }
249
250   return progress;
251}
252