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 static bool
is_dest_live(const nir_dest * dest,BITSET_WORD * defs_live)31 is_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
36 static bool
mark_src_live(const nir_src * src,BITSET_WORD * defs_live)37 mark_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
47 static bool
mark_live_cb(nir_src * src,void * defs_live)48 mark_live_cb(nir_src *src, void *defs_live)
49 {
50 mark_src_live(src, defs_live);
51 return true;
52 }
53
54 static bool
is_live(BITSET_WORD * defs_live,nir_instr * instr)55 is_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
104 struct loop_state {
105 bool header_phis_changed;
106 nir_block *preheader;
107 };
108
109 static bool
dce_block(nir_block * block,BITSET_WORD * defs_live,struct loop_state * loop)110 dce_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
147 static bool
dce_cf_list(struct exec_list * cf_list,BITSET_WORD * defs_live,struct loop_state * parent_loop)148 dce_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
217 static bool
nir_opt_dce_impl(nir_function_impl * impl)218 nir_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
241 bool
nir_opt_dce(nir_shader * shader)242 nir_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