blob: aa8ebf8ad106745e3aa1deec3d217b2a32caa77a [file] [log] [blame]
Eric Anholt7d211042010-04-16 16:43:47 -07001/*
2 * Copyright © 2010 Intel Corporation
3 *
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:
10 *
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
13 * Software.
14 *
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.
22 */
23
24/**
25 * \file ir_dead_code.cpp
26 *
27 * Eliminates dead assignments and variable declarations from the code.
28 */
29
30#define NULL 0
31#include "ir.h"
32#include "ir_visitor.h"
33#include "ir_expression_flattening.h"
34#include "glsl_types.h"
35
36class variable_entry : public exec_node
37{
38public:
39 variable_entry(ir_variable *var)
40 {
41 this->var = var;
42 assign = NULL;
Ian Romanickb5a7cf92010-05-14 12:41:22 -070043 referenced_count = 0;
44 assigned_count = 0;
Eric Anholt7d211042010-04-16 16:43:47 -070045 declaration = false;
46 }
47
48 ir_variable *var; /* The key: the variable's pointer. */
49 ir_assignment *assign; /* An assignment to the variable, if any */
Ian Romanickb5a7cf92010-05-14 12:41:22 -070050
51 /** Number of times the variable is referenced, including assignments. */
52 unsigned referenced_count;
53
54 /** Number of times the variable is assignmened. */
55 unsigned assigned_count;
56
Eric Anholt7d211042010-04-16 16:43:47 -070057 bool declaration; /* If the variable had a decl in the instruction stream */
58};
59
Ian Romanickb5a7cf92010-05-14 12:41:22 -070060class ir_dead_code_visitor : public ir_hierarchical_visitor {
Eric Anholt7d211042010-04-16 16:43:47 -070061public:
Ian Romanickb5a7cf92010-05-14 12:41:22 -070062 virtual ir_visitor_status visit(ir_variable *);
Eric Anholt7d211042010-04-16 16:43:47 -070063
Ian Romanickb5a7cf92010-05-14 12:41:22 -070064 virtual ir_visitor_status visit_enter(ir_function *);
65 virtual ir_visitor_status visit_enter(ir_dereference *);
66 virtual ir_visitor_status visit_leave(ir_dereference *);
67 virtual ir_visitor_status visit_leave(ir_assignment *);
68
69 ir_dead_code_visitor(void);
Eric Anholt7d211042010-04-16 16:43:47 -070070
71 variable_entry *get_variable_entry(ir_variable *var);
72
73 bool (*predicate)(ir_instruction *ir);
74 ir_instruction *base_ir;
75
76 /* List of variable_entry */
77 exec_list variable_list;
Ian Romanickb5a7cf92010-05-14 12:41:22 -070078
79 /* Depth of derefernce stack. */
80 int in_dereference;
Eric Anholt7d211042010-04-16 16:43:47 -070081};
82
Ian Romanickb5a7cf92010-05-14 12:41:22 -070083ir_dead_code_visitor::ir_dead_code_visitor(void)
84{
85 this->in_dereference = 0;
86}
87
88
Eric Anholt7d211042010-04-16 16:43:47 -070089variable_entry *
90ir_dead_code_visitor::get_variable_entry(ir_variable *var)
91{
92 assert(var);
93 foreach_iter(exec_list_iterator, iter, this->variable_list) {
94 variable_entry *entry = (variable_entry *)iter.get();
95 if (entry->var == var)
96 return entry;
97 }
98
99 variable_entry *entry = new variable_entry(var);
100 this->variable_list.push_tail(entry);
101 return entry;
102}
103
Eric Anholt7d211042010-04-16 16:43:47 -0700104
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700105ir_visitor_status
Eric Anholt7d211042010-04-16 16:43:47 -0700106ir_dead_code_visitor::visit(ir_variable *ir)
107{
108 variable_entry *entry = this->get_variable_entry(ir);
109 if (entry) {
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700110 if (this->in_dereference)
111 entry->referenced_count++;
112 else
113 entry->declaration = true;
Eric Anholt7d211042010-04-16 16:43:47 -0700114 }
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700115
116 return visit_continue;
Eric Anholt7d211042010-04-16 16:43:47 -0700117}
118
119
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700120ir_visitor_status
121ir_dead_code_visitor::visit_enter(ir_function *ir)
Eric Anholt7d211042010-04-16 16:43:47 -0700122{
123 (void) ir;
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700124 return visit_continue_with_parent;
Eric Anholt7d211042010-04-16 16:43:47 -0700125}
126
127
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700128ir_visitor_status
129ir_dead_code_visitor::visit_enter(ir_dereference *ir)
Eric Anholt7d211042010-04-16 16:43:47 -0700130{
131 (void) ir;
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700132 this->in_dereference++;
133 return visit_continue;
Eric Anholt7d211042010-04-16 16:43:47 -0700134}
135
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700136
137ir_visitor_status
138ir_dead_code_visitor::visit_leave(ir_dereference *ir)
Eric Anholt7d211042010-04-16 16:43:47 -0700139{
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700140 (void) ir;
141 this->in_dereference--;
142 return visit_continue;
Eric Anholt7d211042010-04-16 16:43:47 -0700143}
144
145
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700146ir_visitor_status
147ir_dead_code_visitor::visit_leave(ir_assignment *ir)
Eric Anholt7d211042010-04-16 16:43:47 -0700148{
Eric Anholt7d211042010-04-16 16:43:47 -0700149 variable_entry *entry;
Ian Romanick461c2942010-05-18 13:53:20 +0200150 entry = this->get_variable_entry(ir->lhs->variable_referenced());
Eric Anholt7d211042010-04-16 16:43:47 -0700151 if (entry) {
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700152 entry->assigned_count++;
Eric Anholt7d211042010-04-16 16:43:47 -0700153 if (entry->assign == NULL)
154 entry->assign = ir;
155 }
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700156
157 return visit_continue;
Eric Anholt7d211042010-04-16 16:43:47 -0700158}
159
160
Eric Anholt7d211042010-04-16 16:43:47 -0700161/**
162 * Do a dead code pass over instructions and everything that instructions
163 * references.
164 *
165 * Note that this will remove assignments to globals, so it is not suitable
166 * for usage on an unlinked instruction stream.
167 */
168bool
169do_dead_code(exec_list *instructions)
170{
171 ir_dead_code_visitor v;
172 bool progress = false;
173
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700174 v.run(instructions);
Eric Anholt7d211042010-04-16 16:43:47 -0700175
176 foreach_iter(exec_list_iterator, iter, v.variable_list) {
177 variable_entry *entry = (variable_entry *)iter.get();
178
Ian Romanickb5a7cf92010-05-14 12:41:22 -0700179 /* Since each assignment is a reference, the refereneced count must be
180 * greater than or equal to the assignment count. If they are equal,
181 * then all of the references are assignments, and the variable is
182 * dead.
183 *
184 * Note that if the variable is neither assigned nor referenced, both
185 * counts will be zero and will be caught by the equality test.
186 */
187 assert(entry->referenced_count >= entry->assigned_count);
188
189 if ((entry->referenced_count > entry->assigned_count)
190 || !entry->declaration)
Eric Anholt7d211042010-04-16 16:43:47 -0700191 continue;
192
193 if (entry->assign) {
194 /* Remove a single dead assignment to the variable we found.
195 * Don't do so if it's a shader output, though.
196 */
197 if (!entry->var->shader_out) {
198 entry->assign->remove();
199 progress = true;
200 }
201 } else {
202 /* If there are no assignments or references to the variable left,
203 * then we can remove its declaration.
204 */
205 entry->var->remove();
206 progress = true;
207 }
208 }
209 return progress;
210}
211
212/**
213 * Does a dead code pass on the functions present in the instruction stream.
214 *
215 * This is suitable for use while the program is not linked, as it will
216 * ignore variable declarations (and the assignments to them) for variables
217 * with global scope.
218 */
219bool
220do_dead_code_unlinked(exec_list *instructions)
221{
222 bool progress = false;
223
224 foreach_iter(exec_list_iterator, iter, *instructions) {
225 ir_instruction *ir = (ir_instruction *)iter.get();
Kenneth Graunke6202cbf2010-04-21 16:02:15 -0700226 ir_function *f = ir->as_function();
227 if (f) {
228 foreach_iter(exec_list_iterator, sigiter, *f) {
229 ir_function_signature *sig =
230 (ir_function_signature *) sigiter.get();
231 if (do_dead_code(&sig->body))
232 progress = true;
233 }
Eric Anholt7d211042010-04-16 16:43:47 -0700234 }
235 }
236
237 return progress;
238}