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_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 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,struct exec_list * dead_instrs)110 dce_block(nir_block *block, BITSET_WORD *defs_live, struct loop_state *loop,
111 struct exec_list *dead_instrs)
112 {
113 bool progress = false;
114 bool phis_changed = false;
115 nir_foreach_instr_reverse_safe(instr, block) {
116 bool live = is_live(defs_live, instr);
117 if (live) {
118 if (instr->type == nir_instr_type_phi) {
119 nir_foreach_phi_src(src, nir_instr_as_phi(instr)) {
120 phis_changed |= mark_src_live(&src->src, defs_live) &&
121 src->pred != loop->preheader;
122 }
123 } else {
124 nir_foreach_src(instr, mark_live_cb, defs_live);
125 }
126 }
127
128 /* If we're not in a loop, remove it now if it's dead. If we are in a
129 * loop, leave instructions to be removed later if they're still dead.
130 */
131 if (loop->preheader) {
132 instr->pass_flags = live;
133 } else if (!live) {
134 nir_instr_remove(instr);
135 exec_list_push_tail(dead_instrs, &instr->node);
136 progress = true;
137 }
138 }
139
140 /* Because blocks are visited in reverse and this stomps header_phis_changed,
141 * we don't have to check whether the current block is a loop header before
142 * setting header_phis_changed.
143 */
144 loop->header_phis_changed = phis_changed;
145
146 return progress;
147 }
148
149 static bool
dce_cf_list(struct exec_list * cf_list,BITSET_WORD * defs_live,struct loop_state * parent_loop,struct exec_list * dead_instrs)150 dce_cf_list(struct exec_list *cf_list, BITSET_WORD *defs_live,
151 struct loop_state *parent_loop, struct exec_list *dead_instrs)
152 {
153 bool progress = false;
154 foreach_list_typed_reverse(nir_cf_node, cf_node, node, cf_list) {
155 switch (cf_node->type) {
156 case nir_cf_node_block: {
157 nir_block *block = nir_cf_node_as_block(cf_node);
158 progress |= dce_block(block, defs_live, parent_loop, dead_instrs);
159 break;
160 }
161 case nir_cf_node_if: {
162 nir_if *nif = nir_cf_node_as_if(cf_node);
163 progress |= dce_cf_list(&nif->else_list, defs_live, parent_loop, dead_instrs);
164 progress |= dce_cf_list(&nif->then_list, defs_live, parent_loop, dead_instrs);
165 mark_src_live(&nif->condition, defs_live);
166 break;
167 }
168 case nir_cf_node_loop: {
169 nir_loop *loop = nir_cf_node_as_loop(cf_node);
170 assert(!nir_loop_has_continue_construct(loop));
171
172 struct loop_state inner_state;
173 inner_state.preheader = nir_cf_node_as_block(nir_cf_node_prev(cf_node));
174 inner_state.header_phis_changed = false;
175
176 /* Fast path if the loop has no continues: we can remove instructions
177 * as we mark the others live.
178 */
179 struct set *predecessors = nir_loop_first_block(loop)->predecessors;
180 if (predecessors->entries == 1 &&
181 _mesa_set_next_entry(predecessors, NULL)->key == inner_state.preheader) {
182 progress |= dce_cf_list(&loop->body, defs_live, parent_loop, dead_instrs);
183 break;
184 }
185
186 /* Mark instructions as live until there is no more progress. */
187 do {
188 /* dce_cf_list() resets inner_state.header_phis_changed itself, so
189 * it doesn't have to be done here.
190 */
191 dce_cf_list(&loop->body, defs_live, &inner_state, dead_instrs);
192 } while (inner_state.header_phis_changed);
193
194 /* We don't know how many times mark_cf_list() will repeat, so
195 * remove instructions separately.
196 *
197 * By checking parent_loop->preheader, we ensure that we only do this
198 * walk for the outer-most loops so it only happens once.
199 */
200 if (!parent_loop->preheader) {
201 nir_foreach_block_in_cf_node(block, cf_node) {
202 nir_foreach_instr_safe(instr, block) {
203 if (!instr->pass_flags) {
204 nir_instr_remove(instr);
205 exec_list_push_tail(dead_instrs, &instr->node);
206 progress = true;
207 }
208 }
209 }
210 }
211 break;
212 }
213 case nir_cf_node_function:
214 unreachable("Invalid cf type");
215 }
216 }
217
218 return progress;
219 }
220
221 static bool
nir_opt_dce_impl(nir_function_impl * impl)222 nir_opt_dce_impl(nir_function_impl *impl)
223 {
224 assert(impl->structured);
225
226 BITSET_WORD *defs_live = rzalloc_array(NULL, BITSET_WORD,
227 BITSET_WORDS(impl->ssa_alloc));
228
229 struct exec_list dead_instrs;
230 exec_list_make_empty(&dead_instrs);
231
232 struct loop_state loop;
233 loop.preheader = NULL;
234 bool progress = dce_cf_list(&impl->body, defs_live, &loop, &dead_instrs);
235
236 ralloc_free(defs_live);
237
238 nir_instr_free_list(&dead_instrs);
239
240 if (progress) {
241 nir_metadata_preserve(impl, nir_metadata_block_index |
242 nir_metadata_dominance);
243 } else {
244 nir_metadata_preserve(impl, nir_metadata_all);
245 }
246
247 return progress;
248 }
249
250 bool
nir_opt_dce(nir_shader * shader)251 nir_opt_dce(nir_shader *shader)
252 {
253 bool progress = false;
254 nir_foreach_function_impl(impl, shader) {
255 if (nir_opt_dce_impl(impl))
256 progress = true;
257 }
258
259 return progress;
260 }
261