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
);
70 ir_instruction
*base_ir
;
72 /* List of variable_entry */
73 exec_list variable_list
;
78 ir_dead_code_visitor::get_variable_entry(ir_variable
*var
)
81 foreach_iter(exec_list_iterator
, iter
, this->variable_list
) {
82 variable_entry
*entry
= (variable_entry
*)iter
.get();
83 if (entry
->var
== var
)
87 variable_entry
*entry
= new variable_entry(var
);
88 this->variable_list
.push_tail(entry
);
94 ir_dead_code_visitor::visit(ir_variable
*ir
)
96 variable_entry
*entry
= this->get_variable_entry(ir
);
98 entry
->declaration
= true;
100 return visit_continue
;
105 ir_dead_code_visitor::visit(ir_dereference_variable
*ir
)
107 ir_variable
*const var
= ir
->variable_referenced();
108 variable_entry
*entry
= this->get_variable_entry(var
);
111 entry
->referenced_count
++;
113 return visit_continue
;
118 ir_dead_code_visitor::visit_enter(ir_function
*ir
)
121 return visit_continue_with_parent
;
126 ir_dead_code_visitor::visit_leave(ir_assignment
*ir
)
128 variable_entry
*entry
;
129 entry
= this->get_variable_entry(ir
->lhs
->variable_referenced());
131 entry
->assigned_count
++;
132 if (entry
->assign
== NULL
)
136 return visit_continue
;
141 * Do a dead code pass over instructions and everything that instructions
144 * Note that this will remove assignments to globals, so it is not suitable
145 * for usage on an unlinked instruction stream.
148 do_dead_code(exec_list
*instructions
)
150 ir_dead_code_visitor v
;
151 bool progress
= false;
155 foreach_iter(exec_list_iterator
, iter
, v
.variable_list
) {
156 variable_entry
*entry
= (variable_entry
*)iter
.get();
158 /* Since each assignment is a reference, the refereneced count must be
159 * greater than or equal to the assignment count. If they are equal,
160 * then all of the references are assignments, and the variable is
163 * Note that if the variable is neither assigned nor referenced, both
164 * counts will be zero and will be caught by the equality test.
166 assert(entry
->referenced_count
>= entry
->assigned_count
);
168 if ((entry
->referenced_count
> entry
->assigned_count
)
169 || !entry
->declaration
)
173 /* Remove a single dead assignment to the variable we found.
174 * Don't do so if it's a shader output, though.
176 if (!entry
->var
->shader_out
) {
177 entry
->assign
->remove();
181 /* If there are no assignments or references to the variable left,
182 * then we can remove its declaration.
184 entry
->var
->remove();
192 * Does a dead code pass on the functions present in the instruction stream.
194 * This is suitable for use while the program is not linked, as it will
195 * ignore variable declarations (and the assignments to them) for variables
199 do_dead_code_unlinked(exec_list
*instructions
)
201 bool progress
= false;
203 foreach_iter(exec_list_iterator
, iter
, *instructions
) {
204 ir_instruction
*ir
= (ir_instruction
*)iter
.get();
205 ir_function
*f
= ir
->as_function();
207 foreach_iter(exec_list_iterator
, sigiter
, *f
) {
208 ir_function_signature
*sig
=
209 (ir_function_signature
*) sigiter
.get();
210 if (do_dead_code(&sig
->body
))