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
mark_and_push(nir_instr_worklist * wl,nir_instr * instr)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
mark_live_cb(nir_src * src,void * _state)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
init_instr(nir_instr * instr,nir_instr_worklist * worklist)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
init_block(nir_block * block,nir_instr_worklist * worklist)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
nir_opt_dce_impl(nir_function_impl * impl)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
nir_opt_dce(nir_shader * shader)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 }
169