2 * Copyright © 2014 Intel Corporation
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:
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
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
24 * Connor Abbott (cwabbott0@gmail.com)
30 /* SSA-based mark-and-sweep dead code elimination */
33 struct exec_node node
;
38 worklist_push(struct exec_list
*worklist
, nir_instr
*instr
)
40 worklist_elem
*elem
= ralloc(worklist
, worklist_elem
);
43 exec_list_push_tail(worklist
, &elem
->node
);
47 worklist_pop(struct exec_list
*worklist
)
49 struct exec_node
*node
= exec_list_pop_head(worklist
);
50 worklist_elem
*elem
= exec_node_data(worklist_elem
, node
, node
);
55 mark_live_cb(nir_src
*src
, void *_state
)
57 struct exec_list
*worklist
= (struct exec_list
*) _state
;
59 if (src
->is_ssa
&& !src
->ssa
->parent_instr
->live
) {
60 worklist_push(worklist
, src
->ssa
->parent_instr
);
67 init_instr(nir_instr
*instr
, struct exec_list
*worklist
)
69 nir_alu_instr
*alu_instr
;
70 nir_intrinsic_instr
*intrin_instr
;
71 nir_tex_instr
*tex_instr
;
72 nir_load_const_instr
*load_const_instr
;
76 switch (instr
->type
) {
77 case nir_instr_type_call
:
78 case nir_instr_type_jump
:
79 worklist_push(worklist
, instr
);
82 case nir_instr_type_alu
:
83 alu_instr
= nir_instr_as_alu(instr
);
84 if (!alu_instr
->dest
.dest
.is_ssa
)
85 worklist_push(worklist
, instr
);
88 case nir_instr_type_intrinsic
:
89 intrin_instr
= nir_instr_as_intrinsic(instr
);
90 if (nir_intrinsic_infos
[intrin_instr
->intrinsic
].flags
&
91 NIR_INTRINSIC_CAN_ELIMINATE
) {
92 if (nir_intrinsic_infos
[intrin_instr
->intrinsic
].has_dest
&&
93 !intrin_instr
->dest
.is_ssa
) {
94 worklist_push(worklist
, instr
);
97 worklist_push(worklist
, instr
);
101 case nir_instr_type_texture
:
102 tex_instr
= nir_instr_as_texture(instr
);
103 if (!tex_instr
->dest
.is_ssa
)
104 worklist_push(worklist
, instr
);
107 case nir_instr_type_load_const
:
108 load_const_instr
= nir_instr_as_load_const(instr
);
109 if (!load_const_instr
->dest
.is_ssa
)
110 worklist_push(worklist
, instr
);
119 init_block_cb(nir_block
*block
, void *_state
)
121 struct exec_list
*worklist
= (struct exec_list
*) _state
;
123 nir_foreach_instr(block
, instr
)
124 init_instr(instr
, worklist
);
126 nir_if
*following_if
= nir_block_following_if(block
);
128 if (following_if
->condition
.is_ssa
&&
129 !following_if
->condition
.ssa
->parent_instr
->live
)
130 worklist_push(worklist
, following_if
->condition
.ssa
->parent_instr
);
137 delete_block_cb(nir_block
*block
, void *_state
)
139 bool *progress
= (bool *) _state
;
141 nir_foreach_instr_safe(block
, instr
) {
143 nir_instr_remove(instr
);
152 nir_opt_dce_impl(nir_function_impl
*impl
)
154 struct exec_list
*worklist
= ralloc(NULL
, struct exec_list
);
155 exec_list_make_empty(worklist
);
157 nir_foreach_block(impl
, init_block_cb
, worklist
);
159 while (!exec_list_is_empty(worklist
)) {
160 nir_instr
*instr
= worklist_pop(worklist
);
161 nir_foreach_src(instr
, mark_live_cb
, worklist
);
164 ralloc_free(worklist
);
166 bool progress
= false;
167 nir_foreach_block(impl
, delete_block_cb
, &progress
);
173 nir_opt_dce(nir_shader
*shader
)
175 bool progress
= false;
176 nir_foreach_overload(shader
, overload
) {
177 if (overload
->impl
&& nir_opt_dce_impl(overload
->impl
))