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 return visit_continue
;
105 ir_copy_propagation_visitor::visit_enter(ir_function
*ir
)
108 return visit_continue_with_parent
;
112 * Replaces dereferences of ACP RHS variables with ACP LHS variables.
114 * This is where the actual copy propagation occurs. Note that the
115 * rewriting of ir_dereference means that the ir_dereference instance
116 * must not be shared by multiple IR operations!
119 ir_copy_propagation_visitor::visit(ir_dereference_variable
*ir
)
121 /* Ignores the LHS. Don't want to rewrite the LHS to point at some
125 this->in_lhs
= false;
126 return visit_continue
;
129 ir_variable
*var
= ir
->variable_referenced();
131 foreach_iter(exec_list_iterator
, iter
, *this->acp
) {
132 acp_entry
*entry
= (acp_entry
*)iter
.get();
134 if (var
== entry
->lhs
) {
135 ir
->var
= entry
->rhs
;
136 this->progress
= true;
141 return visit_continue
;
146 ir_copy_propagation_visitor::visit_enter(ir_call
*ir
)
150 /* Note, if we were to do copy propagation to parameters of calls, we'd
151 * have to be careful about out params.
153 return visit_continue_with_parent
;
158 ir_copy_propagation_visitor::visit_enter(ir_if
*ir
)
160 ir
->condition
->accept(this);
162 /* Do not traverse into the body of the if-statement since that is a
163 * different basic block.
165 return visit_continue_with_parent
;
169 propagate_copies(ir_instruction
*ir
, exec_list
*acp
)
171 ir_copy_propagation_visitor
v(acp
);
179 kill_invalidated_copies(ir_assignment
*ir
, exec_list
*acp
)
181 ir_variable
*var
= ir
->lhs
->variable_referenced();
184 foreach_iter(exec_list_iterator
, iter
, *acp
) {
185 acp_entry
*entry
= (acp_entry
*)iter
.get();
187 if (entry
->lhs
== var
|| entry
->rhs
== var
) {
194 * Adds an entry to the available copy list if it's a plain assignment
195 * of a variable to a variable.
198 add_copy(void *ctx
, ir_assignment
*ir
, exec_list
*acp
)
203 ir_constant
*condition
= ir
->condition
->as_constant();
204 if (!condition
|| !condition
->value
.b
[0])
208 ir_variable
*lhs_var
= ir
->lhs
->whole_variable_referenced();
209 ir_variable
*rhs_var
= ir
->rhs
->whole_variable_referenced();
211 if ((lhs_var
!= NULL
) && (rhs_var
!= NULL
)) {
212 entry
= new(ctx
) acp_entry(lhs_var
, rhs_var
);
213 acp
->push_tail(entry
);
218 copy_propagation_basic_block(ir_instruction
*first
,
219 ir_instruction
*last
,
223 /* List of avaialble_copy */
225 bool *out_progress
= (bool *)data
;
226 bool progress
= false;
228 void *ctx
= talloc(NULL
, void*);
229 for (ir
= first
;; ir
= (ir_instruction
*)ir
->next
) {
230 ir_assignment
*ir_assign
= ir
->as_assignment();
232 progress
= propagate_copies(ir
, &acp
) || progress
;
235 kill_invalidated_copies(ir_assign
, &acp
);
237 add_copy(ctx
, ir_assign
, &acp
);
242 *out_progress
= progress
;
247 * Does a copy propagation pass on the code present in the instruction stream.
250 do_copy_propagation(exec_list
*instructions
)
252 bool progress
= false;
254 call_for_basic_blocks(instructions
, copy_propagation_basic_block
, &progress
);