2 * Copyright © 2010 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
21 * DEALINGS IN THE SOFTWARE.
25 * \file ir_dead_code.cpp
27 * Eliminates dead assignments and variable declarations from the code.
31 #include "ir_visitor.h"
32 #include "ir_expression_flattening.h"
33 #include "glsl_types.h"
35 class variable_entry
: public exec_node
38 variable_entry(ir_variable
*var
)
47 ir_variable
*var
; /* The key: the variable's pointer. */
48 ir_assignment
*assign
; /* An assignment to the variable, if any */
50 /** Number of times the variable is referenced, including assignments. */
51 unsigned referenced_count
;
53 /** Number of times the variable is assignmened. */
54 unsigned assigned_count
;
56 bool declaration
; /* If the variable had a decl in the instruction stream */
59 class ir_dead_code_visitor
: public ir_hierarchical_visitor
{
61 virtual ir_visitor_status
visit(ir_variable
*);
62 virtual ir_visitor_status
visit(ir_dereference_variable
*);
64 virtual ir_visitor_status
visit_enter(ir_function
*);
65 virtual ir_visitor_status
visit_leave(ir_assignment
*);
67 variable_entry
*get_variable_entry(ir_variable
*var
);
69 bool (*predicate
)(ir_instruction
*ir
);
71 /* List of variable_entry */
72 exec_list variable_list
;
79 ir_dead_code_visitor::get_variable_entry(ir_variable
*var
)
82 foreach_iter(exec_list_iterator
, iter
, this->variable_list
) {
83 variable_entry
*entry
= (variable_entry
*)iter
.get();
84 if (entry
->var
== var
)
88 variable_entry
*entry
= new(mem_ctx
) variable_entry(var
);
89 this->variable_list
.push_tail(entry
);
95 ir_dead_code_visitor::visit(ir_variable
*ir
)
97 variable_entry
*entry
= this->get_variable_entry(ir
);
99 entry
->declaration
= true;
101 return visit_continue
;
106 ir_dead_code_visitor::visit(ir_dereference_variable
*ir
)
108 ir_variable
*const var
= ir
->variable_referenced();
109 variable_entry
*entry
= this->get_variable_entry(var
);
112 entry
->referenced_count
++;
114 return visit_continue
;
119 ir_dead_code_visitor::visit_enter(ir_function
*ir
)
122 return visit_continue_with_parent
;
127 ir_dead_code_visitor::visit_leave(ir_assignment
*ir
)
129 variable_entry
*entry
;
130 entry
= this->get_variable_entry(ir
->lhs
->variable_referenced());
132 entry
->assigned_count
++;
133 if (entry
->assign
== NULL
)
137 return visit_continue
;
142 * Do a dead code pass over instructions and everything that instructions
145 * Note that this will remove assignments to globals, so it is not suitable
146 * for usage on an unlinked instruction stream.
149 do_dead_code(struct _mesa_glsl_parse_state
*state
,
150 exec_list
*instructions
)
152 ir_dead_code_visitor v
;
153 bool progress
= false;
158 foreach_iter(exec_list_iterator
, iter
, v
.variable_list
) {
159 variable_entry
*entry
= (variable_entry
*)iter
.get();
161 /* Since each assignment is a reference, the refereneced count must be
162 * greater than or equal to the assignment count. If they are equal,
163 * then all of the references are assignments, and the variable is
166 * Note that if the variable is neither assigned nor referenced, both
167 * counts will be zero and will be caught by the equality test.
169 assert(entry
->referenced_count
>= entry
->assigned_count
);
171 if ((entry
->referenced_count
> entry
->assigned_count
)
172 || !entry
->declaration
)
176 /* Remove a single dead assignment to the variable we found.
177 * Don't do so if it's a shader output, though.
179 if (!entry
->var
->shader_out
) {
180 entry
->assign
->remove();
184 /* If there are no assignments or references to the variable left,
185 * then we can remove its declaration.
187 entry
->var
->remove();
195 * Does a dead code pass on the functions present in the instruction stream.
197 * This is suitable for use while the program is not linked, as it will
198 * ignore variable declarations (and the assignments to them) for variables
202 do_dead_code_unlinked(struct _mesa_glsl_parse_state
*state
,
203 exec_list
*instructions
)
205 bool progress
= false;
207 foreach_iter(exec_list_iterator
, iter
, *instructions
) {
208 ir_instruction
*ir
= (ir_instruction
*)iter
.get();
209 ir_function
*f
= ir
->as_function();
211 foreach_iter(exec_list_iterator
, sigiter
, *f
) {
212 ir_function_signature
*sig
=
213 (ir_function_signature
*) sigiter
.get();
214 if (do_dead_code(state
, &sig
->body
))