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.
32 #include "ir_visitor.h"
33 #include "ir_expression_flattening.h"
34 #include "glsl_types.h"
36 class variable_entry
: public exec_node
39 variable_entry(ir_variable
*var
)
48 ir_variable
*var
; /* The key: the variable's pointer. */
49 ir_assignment
*assign
; /* An assignment to the variable, if any */
51 /** Number of times the variable is referenced, including assignments. */
52 unsigned referenced_count
;
54 /** Number of times the variable is assignmened. */
55 unsigned assigned_count
;
57 bool declaration
; /* If the variable had a decl in the instruction stream */
60 class ir_dead_code_visitor
: public ir_hierarchical_visitor
{
62 virtual ir_visitor_status
visit(ir_variable
*);
63 virtual ir_visitor_status
visit(ir_dereference_variable
*);
65 virtual ir_visitor_status
visit_enter(ir_function
*);
66 virtual ir_visitor_status
visit_leave(ir_assignment
*);
68 variable_entry
*get_variable_entry(ir_variable
*var
);
70 bool (*predicate
)(ir_instruction
*ir
);
71 ir_instruction
*base_ir
;
73 /* List of variable_entry */
74 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 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(exec_list
*instructions
)
151 ir_dead_code_visitor v
;
152 bool progress
= false;
156 foreach_iter(exec_list_iterator
, iter
, v
.variable_list
) {
157 variable_entry
*entry
= (variable_entry
*)iter
.get();
159 /* Since each assignment is a reference, the refereneced count must be
160 * greater than or equal to the assignment count. If they are equal,
161 * then all of the references are assignments, and the variable is
164 * Note that if the variable is neither assigned nor referenced, both
165 * counts will be zero and will be caught by the equality test.
167 assert(entry
->referenced_count
>= entry
->assigned_count
);
169 if ((entry
->referenced_count
> entry
->assigned_count
)
170 || !entry
->declaration
)
174 /* Remove a single dead assignment to the variable we found.
175 * Don't do so if it's a shader output, though.
177 if (!entry
->var
->shader_out
) {
178 entry
->assign
->remove();
182 /* If there are no assignments or references to the variable left,
183 * then we can remove its declaration.
185 entry
->var
->remove();
193 * Does a dead code pass on the functions present in the instruction stream.
195 * This is suitable for use while the program is not linked, as it will
196 * ignore variable declarations (and the assignments to them) for variables
200 do_dead_code_unlinked(exec_list
*instructions
)
202 bool progress
= false;
204 foreach_iter(exec_list_iterator
, iter
, *instructions
) {
205 ir_instruction
*ir
= (ir_instruction
*)iter
.get();
206 ir_function
*f
= ir
->as_function();
208 foreach_iter(exec_list_iterator
, sigiter
, *f
) {
209 ir_function_signature
*sig
=
210 (ir_function_signature
*) sigiter
.get();
211 if (do_dead_code(&sig
->body
))