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 ([email protected])
25 *
26 */
27
28 #include "nir.h"
29
30 static bool
is_def_live(const nir_def * def,BITSET_WORD * defs_live)31 is_def_live(const nir_def *def, BITSET_WORD *defs_live)
32 {
33 return BITSET_TEST(defs_live, def->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 (!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_def_live(&alu->def, defs_live);
64 }
65 case nir_instr_type_deref: {
66 nir_deref_instr *deref = nir_instr_as_deref(instr);
67 return is_def_live(&deref->def, 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_def_live(&intrin->def, defs_live));
74 }
75 case nir_instr_type_tex: {
76 nir_tex_instr *tex = nir_instr_as_tex(instr);
77 return is_def_live(&tex->def, defs_live);
78 }
79 case nir_instr_type_phi: {
80 nir_phi_instr *phi = nir_instr_as_phi(instr);
81 return is_def_live(&phi->def, defs_live);
82 }
83 case nir_instr_type_load_const: {
84 nir_load_const_instr *lc = nir_instr_as_load_const(instr);
85 return is_def_live(&lc->def, defs_live);
86 }
87 case nir_instr_type_undef: {
88 nir_undef_instr *undef = nir_instr_as_undef(instr);
89 return is_def_live(&undef->def, defs_live);
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 (entry->dest_is_reg || is_def_live(&entry->dest.def, defs_live))
95 return true;
96 }
97 return false;
98 }
99 case nir_instr_type_debug_info: {
100 nir_debug_info_instr *di = nir_instr_as_debug_info(instr);
101 if (di->type == nir_debug_info_src_loc) {
102 nir_instr *next = nir_instr_next(instr);
103 return !next || next->type != nir_instr_type_debug_info;
104 } else if (di->type == nir_debug_info_string) {
105 return is_def_live(&di->def, defs_live);
106 }
107 return true;
108 }
109 default:
110 unreachable("unexpected instr type");
111 }
112 }
113
114 struct loop_state {
115 bool header_phis_changed;
116 nir_block *preheader;
117 };
118
119 static bool
dce_block(nir_block * block,BITSET_WORD * defs_live,struct loop_state * loop,struct exec_list * dead_instrs)120 dce_block(nir_block *block, BITSET_WORD *defs_live, struct loop_state *loop,
121 struct exec_list *dead_instrs)
122 {
123 bool progress = false;
124 bool phis_changed = false;
125 nir_foreach_instr_reverse_safe(instr, block) {
126 bool live = is_live(defs_live, instr);
127 if (live) {
128 if (instr->type == nir_instr_type_phi) {
129 nir_foreach_phi_src(src, nir_instr_as_phi(instr)) {
130 phis_changed |= mark_src_live(&src->src, defs_live) &&
131 src->pred != loop->preheader;
132 }
133 } else {
134 nir_foreach_src(instr, mark_live_cb, defs_live);
135 }
136 }
137
138 /* If we're not in a loop, remove it now if it's dead. If we are in a
139 * loop, leave instructions to be removed later if they're still dead.
140 */
141 if (loop->preheader) {
142 instr->pass_flags = live;
143 } else if (!live) {
144 nir_instr_remove(instr);
145 exec_list_push_tail(dead_instrs, &instr->node);
146 progress = true;
147 }
148 }
149
150 /* Because blocks are visited in reverse and this stomps header_phis_changed,
151 * we don't have to check whether the current block is a loop header before
152 * setting header_phis_changed.
153 */
154 loop->header_phis_changed = phis_changed;
155
156 return progress;
157 }
158
159 static bool
dce_cf_list(struct exec_list * cf_list,BITSET_WORD * defs_live,struct loop_state * parent_loop,struct exec_list * dead_instrs)160 dce_cf_list(struct exec_list *cf_list, BITSET_WORD *defs_live,
161 struct loop_state *parent_loop, struct exec_list *dead_instrs)
162 {
163 bool progress = false;
164 foreach_list_typed_reverse(nir_cf_node, cf_node, node, cf_list) {
165 switch (cf_node->type) {
166 case nir_cf_node_block: {
167 nir_block *block = nir_cf_node_as_block(cf_node);
168 progress |= dce_block(block, defs_live, parent_loop, dead_instrs);
169 break;
170 }
171 case nir_cf_node_if: {
172 nir_if *nif = nir_cf_node_as_if(cf_node);
173 progress |= dce_cf_list(&nif->else_list, defs_live, parent_loop, dead_instrs);
174 progress |= dce_cf_list(&nif->then_list, defs_live, parent_loop, dead_instrs);
175 mark_src_live(&nif->condition, defs_live);
176 break;
177 }
178 case nir_cf_node_loop: {
179 nir_loop *loop = nir_cf_node_as_loop(cf_node);
180 assert(!nir_loop_has_continue_construct(loop));
181
182 struct loop_state inner_state;
183 inner_state.preheader = nir_cf_node_as_block(nir_cf_node_prev(cf_node));
184 inner_state.header_phis_changed = false;
185
186 /* Fast path if the loop has no continues: we can remove instructions
187 * as we mark the others live.
188 */
189 struct set *predecessors = nir_loop_first_block(loop)->predecessors;
190 if (predecessors->entries == 1 &&
191 _mesa_set_next_entry(predecessors, NULL)->key == inner_state.preheader) {
192 progress |= dce_cf_list(&loop->body, defs_live, parent_loop, dead_instrs);
193 break;
194 }
195
196 /* Mark instructions as live until there is no more progress. */
197 do {
198 /* dce_cf_list() resets inner_state.header_phis_changed itself, so
199 * it doesn't have to be done here.
200 */
201 dce_cf_list(&loop->body, defs_live, &inner_state, dead_instrs);
202 } while (inner_state.header_phis_changed);
203
204 /* We don't know how many times mark_cf_list() will repeat, so
205 * remove instructions separately.
206 *
207 * By checking parent_loop->preheader, we ensure that we only do this
208 * walk for the outer-most loops so it only happens once.
209 */
210 if (!parent_loop->preheader) {
211 nir_foreach_block_in_cf_node(block, cf_node) {
212 nir_foreach_instr_safe(instr, block) {
213 if (!instr->pass_flags) {
214 nir_instr_remove(instr);
215 exec_list_push_tail(dead_instrs, &instr->node);
216 progress = true;
217 }
218 }
219 }
220 }
221 break;
222 }
223 case nir_cf_node_function:
224 unreachable("Invalid cf type");
225 }
226 }
227
228 return progress;
229 }
230
231 static bool
nir_opt_dce_impl(nir_function_impl * impl)232 nir_opt_dce_impl(nir_function_impl *impl)
233 {
234 assert(impl->structured);
235
236 BITSET_WORD *defs_live = rzalloc_array(NULL, BITSET_WORD,
237 BITSET_WORDS(impl->ssa_alloc));
238
239 struct exec_list dead_instrs;
240 exec_list_make_empty(&dead_instrs);
241
242 struct loop_state loop;
243 loop.preheader = NULL;
244 bool progress = dce_cf_list(&impl->body, defs_live, &loop, &dead_instrs);
245
246 ralloc_free(defs_live);
247
248 nir_instr_free_list(&dead_instrs);
249
250 if (progress) {
251 nir_metadata_preserve(impl, nir_metadata_control_flow);
252 } else {
253 nir_metadata_preserve(impl, nir_metadata_all);
254 }
255
256 return progress;
257 }
258
259 bool
nir_opt_dce(nir_shader * shader)260 nir_opt_dce(nir_shader *shader)
261 {
262 bool progress = false;
263 nir_foreach_function_impl(impl, shader) {
264 if (nir_opt_dce_impl(impl))
265 progress = true;
266 }
267
268 return progress;
269 }
270