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_copy_propagation.cpp
27 * Moves usage of recently-copied variables to the previous copy of
28 * the variable within basic blocks.
30 * This should reduce the number of MOV instructions in the generated
31 * programs unless copy propagation is also done on the LIR, and may
32 * help anyway by triggering other optimizations that live in the HIR.
36 #include "ir_visitor.h"
37 #include "ir_basic_block.h"
38 #include "ir_optimization.h"
39 #include "glsl_types.h"
41 class acp_entry
: public exec_node
44 acp_entry(ir_variable
*lhs
, ir_variable
*rhs
)
56 class ir_copy_propagation_visitor
: public ir_hierarchical_visitor
{
58 ir_copy_propagation_visitor(exec_list
*acp
)
65 virtual ir_visitor_status
visit(class ir_dereference_variable
*);
66 virtual ir_visitor_status
visit_enter(class ir_loop
*);
67 virtual ir_visitor_status
visit_enter(class ir_function_signature
*);
68 virtual ir_visitor_status
visit_enter(class ir_function
*);
69 virtual ir_visitor_status
visit_enter(class ir_assignment
*);
70 virtual ir_visitor_status
visit_enter(class ir_call
*);
71 virtual ir_visitor_status
visit_enter(class ir_if
*);
73 /** List of acp_entry */
77 /** Currently in the LHS of an assignment? */
83 ir_copy_propagation_visitor::visit_enter(ir_loop
*ir
)
86 return visit_continue_with_parent
;
90 ir_copy_propagation_visitor::visit_enter(ir_function_signature
*ir
)
93 return visit_continue_with_parent
;
97 ir_copy_propagation_visitor::visit_enter(ir_assignment
*ir
)
101 /* Inline the rest of ir_assignment::accept(ir_hv *v), wrapping the
102 * LHS part with setting in_lhs so that we can avoid copy
103 * propagating into the LHS.
105 * Note that this means we won't copy propagate into the derefs of
106 * an array index. Oh well.
109 s
= ir
->lhs
->accept(this);
110 this->in_lhs
= false;
111 if (s
!= visit_continue
)
112 return (s
== visit_continue_with_parent
) ? visit_continue
: s
;
114 s
= ir
->rhs
->accept(this);
115 if (s
!= visit_continue
)
116 return (s
== visit_continue_with_parent
) ? visit_continue
: s
;
119 s
= ir
->condition
->accept(this);
121 return (s
== visit_stop
) ? s
: visit_continue_with_parent
;
125 ir_copy_propagation_visitor::visit_enter(ir_function
*ir
)
128 return visit_continue_with_parent
;
132 * Replaces dereferences of ACP RHS variables with ACP LHS variables.
134 * This is where the actual copy propagation occurs. Note that the
135 * rewriting of ir_dereference means that the ir_dereference instance
136 * must not be shared by multiple IR operations!
139 ir_copy_propagation_visitor::visit(ir_dereference_variable
*ir
)
141 /* Ignores the LHS. Don't want to rewrite the LHS to point at some
145 return visit_continue
;
148 ir_variable
*var
= ir
->variable_referenced();
150 foreach_iter(exec_list_iterator
, iter
, *this->acp
) {
151 acp_entry
*entry
= (acp_entry
*)iter
.get();
153 if (var
== entry
->lhs
) {
154 ir
->var
= entry
->rhs
;
155 this->progress
= true;
160 return visit_continue
;
165 ir_copy_propagation_visitor::visit_enter(ir_call
*ir
)
169 /* Note, if we were to do copy propagation to parameters of calls, we'd
170 * have to be careful about out params.
172 return visit_continue_with_parent
;
177 ir_copy_propagation_visitor::visit_enter(ir_if
*ir
)
179 ir
->condition
->accept(this);
181 /* Do not traverse into the body of the if-statement since that is a
182 * different basic block.
184 return visit_continue_with_parent
;
188 propagate_copies(ir_instruction
*ir
, exec_list
*acp
)
190 ir_copy_propagation_visitor
v(acp
);
198 kill_invalidated_copies(ir_assignment
*ir
, exec_list
*acp
)
200 ir_variable
*var
= ir
->lhs
->variable_referenced();
203 foreach_iter(exec_list_iterator
, iter
, *acp
) {
204 acp_entry
*entry
= (acp_entry
*)iter
.get();
206 if (entry
->lhs
== var
|| entry
->rhs
== var
) {
213 * Adds an entry to the available copy list if it's a plain assignment
214 * of a variable to a variable.
217 add_copy(void *ctx
, ir_assignment
*ir
, exec_list
*acp
)
222 ir_constant
*condition
= ir
->condition
->as_constant();
223 if (!condition
|| !condition
->value
.b
[0])
227 ir_variable
*lhs_var
= ir
->whole_variable_written();
228 ir_variable
*rhs_var
= ir
->rhs
->whole_variable_referenced();
230 if ((lhs_var
!= NULL
) && (rhs_var
!= NULL
)) {
231 if (lhs_var
== rhs_var
) {
232 /* This is a dumb assignment, but we've conveniently noticed
233 * it here. Removing it now would mess up the loop iteration
234 * calling us. Just flag it to not execute, and someone else
235 * will clean up the mess.
237 ir
->condition
= new(talloc_parent(ir
)) ir_constant(false);
240 entry
= new(ctx
) acp_entry(lhs_var
, rhs_var
);
241 acp
->push_tail(entry
);
249 copy_propagation_basic_block(ir_instruction
*first
,
250 ir_instruction
*last
,
254 /* List of avaialble_copy */
256 bool *out_progress
= (bool *)data
;
257 bool progress
= false;
259 void *ctx
= talloc_new(NULL
);
260 for (ir
= first
;; ir
= (ir_instruction
*)ir
->next
) {
261 ir_assignment
*ir_assign
= ir
->as_assignment();
263 progress
= propagate_copies(ir
, &acp
) || progress
;
266 kill_invalidated_copies(ir_assign
, &acp
);
268 progress
= add_copy(ctx
, ir_assign
, &acp
) || progress
;
273 *out_progress
= progress
;
278 * Does a copy propagation pass on the code present in the instruction stream.
281 do_copy_propagation(exec_list
*instructions
)
283 bool progress
= false;
285 call_for_basic_blocks(instructions
, copy_propagation_basic_block
, &progress
);