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
);
42 instr
->pass_flags
= 1;
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
->pass_flags
) {
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
;
73 /* We use the pass_flags to store the live/dead information. In DCE, we
74 * just treat it as a zero/non-zero boolean for whether or not the
75 * instruction is live.
77 instr
->pass_flags
= 0;
79 switch (instr
->type
) {
80 case nir_instr_type_call
:
81 case nir_instr_type_jump
:
82 worklist_push(worklist
, instr
);
85 case nir_instr_type_alu
:
86 alu_instr
= nir_instr_as_alu(instr
);
87 if (!alu_instr
->dest
.dest
.is_ssa
)
88 worklist_push(worklist
, instr
);
91 case nir_instr_type_intrinsic
:
92 intrin_instr
= nir_instr_as_intrinsic(instr
);
93 if (nir_intrinsic_infos
[intrin_instr
->intrinsic
].flags
&
94 NIR_INTRINSIC_CAN_ELIMINATE
) {
95 if (nir_intrinsic_infos
[intrin_instr
->intrinsic
].has_dest
&&
96 !intrin_instr
->dest
.is_ssa
) {
97 worklist_push(worklist
, instr
);
100 worklist_push(worklist
, instr
);
104 case nir_instr_type_tex
:
105 tex_instr
= nir_instr_as_tex(instr
);
106 if (!tex_instr
->dest
.is_ssa
)
107 worklist_push(worklist
, instr
);
116 init_block(nir_block
*block
, struct exec_list
*worklist
)
118 nir_foreach_instr(instr
, block
)
119 init_instr(instr
, worklist
);
121 nir_if
*following_if
= nir_block_get_following_if(block
);
123 if (following_if
->condition
.is_ssa
&&
124 !following_if
->condition
.ssa
->parent_instr
->pass_flags
)
125 worklist_push(worklist
, following_if
->condition
.ssa
->parent_instr
);
132 nir_opt_dce_impl(nir_function_impl
*impl
)
134 struct exec_list
*worklist
= rzalloc(NULL
, struct exec_list
);
135 exec_list_make_empty(worklist
);
137 nir_foreach_block(block
, impl
) {
138 init_block(block
, worklist
);
141 while (!exec_list_is_empty(worklist
)) {
142 nir_instr
*instr
= worklist_pop(worklist
);
143 nir_foreach_src(instr
, mark_live_cb
, worklist
);
146 ralloc_free(worklist
);
148 bool progress
= false;
150 nir_foreach_block(block
, impl
) {
151 nir_foreach_instr_safe(instr
, block
) {
152 if (!instr
->pass_flags
) {
153 nir_instr_remove(instr
);
160 nir_metadata_preserve(impl
, nir_metadata_block_index
|
161 nir_metadata_dominance
);
167 nir_opt_dce(nir_shader
*shader
)
169 bool progress
= false;
170 nir_foreach_function(function
, shader
) {
171 if (function
->impl
&& nir_opt_dce_impl(function
->impl
))