2 * Copyright © 2013 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.
27 * constant subexpression elimination at the GLSL IR level.
29 * Compare to brw_fs_cse.cpp for a more complete CSE implementation. This one
30 * is generic and handles texture operations, but it's rather simple currently
31 * and doesn't support modification of variables in the available expressions
32 * list, so it can't do variables other than uniforms or shader inputs.
36 #include "ir_visitor.h"
37 #include "ir_rvalue_visitor.h"
38 #include "ir_basic_block.h"
39 #include "ir_optimization.h"
40 #include "ir_builder.h"
41 #include "glsl_types.h"
43 using namespace ir_builder
;
45 static bool debug
= false;
50 * This is the record of an available expression for common subexpression
53 class ae_entry
: public exec_node
56 ae_entry(ir_instruction
*base_ir
, ir_rvalue
**val
)
57 : val(val
), base_ir(base_ir
)
67 * The pointer to the expression that we might be able to reuse
69 * Note the double pointer -- this is the place in the base_ir expression
70 * tree that we would rewrite to move the expression out to a new variable
76 * Root instruction in the basic block where the expression appeared.
78 * This is used so that we can insert the new variable declaration into the
79 * instruction stream (since *val is just somewhere in base_ir's expression
82 ir_instruction
*base_ir
;
85 * The variable that the expression has been stored in, if it's been CSEd
91 class cse_visitor
: public ir_rvalue_visitor
{
93 cse_visitor(exec_list
*validate_instructions
)
94 : validate_instructions(validate_instructions
)
97 mem_ctx
= ralloc_context(NULL
);
98 this->ae
= new(mem_ctx
) exec_list
;
102 ralloc_free(mem_ctx
);
105 virtual ir_visitor_status
visit_enter(ir_function_signature
*ir
);
106 virtual ir_visitor_status
visit_enter(ir_loop
*ir
);
107 virtual ir_visitor_status
visit_enter(ir_if
*ir
);
108 virtual ir_visitor_status
visit_enter(ir_call
*ir
);
109 virtual void handle_rvalue(ir_rvalue
**rvalue
);
116 ir_rvalue
*try_cse(ir_rvalue
*rvalue
);
117 void add_to_ae(ir_rvalue
**rvalue
);
119 /** List of ae_entry: The available expressions to reuse */
123 * The whole shader, so that we can validate_ir_tree in debug mode.
125 * This proved quite useful when trying to get the tree manipulation
128 exec_list
*validate_instructions
;
132 * Visitor to walk an expression tree to check that all variables referenced
135 class is_cse_candidate_visitor
: public ir_hierarchical_visitor
139 is_cse_candidate_visitor()
144 virtual ir_visitor_status
visit(ir_dereference_variable
*ir
);
150 class contains_rvalue_visitor
: public ir_rvalue_visitor
154 contains_rvalue_visitor(ir_rvalue
*val
)
160 virtual void handle_rvalue(ir_rvalue
**rvalue
);
168 } /* unnamed namespace */
171 dump_ae(exec_list
*ae
)
175 printf("CSE: AE contents:\n");
176 foreach_list(node
, ae
) {
177 ae_entry
*entry
= (ae_entry
*)node
;
179 printf("CSE: AE %2d (%p): ", i
, entry
);
180 (*entry
->val
)->print();
184 printf("CSE: in var %p:\n", entry
->var
);
191 is_cse_candidate_visitor::visit(ir_dereference_variable
*ir
)
193 /* Currently, since we don't handle kills of the ae based on variables
194 * getting assigned, we can only handle constant variables.
196 if (ir
->var
->data
.read_only
) {
197 return visit_continue
;
205 contains_rvalue_visitor::handle_rvalue(ir_rvalue
**rvalue
)
212 contains_rvalue(ir_rvalue
*haystack
, ir_rvalue
*needle
)
214 contains_rvalue_visitor
v(needle
);
215 haystack
->accept(&v
);
220 is_cse_candidate(ir_rvalue
*ir
)
222 /* Our temporary variable assignment generation isn't ready to handle
223 * anything bigger than a vector.
225 if (!ir
->type
->is_vector() && !ir
->type
->is_scalar())
228 /* Only handle expressions and textures currently. We may want to extend
229 * to variable-index array dereferences at some point.
231 switch (ir
->ir_type
) {
232 case ir_type_expression
:
233 case ir_type_texture
:
239 is_cse_candidate_visitor v
;
247 * Tries to find and return a reference to a previous computation of a given
250 * Walk the list of available expressions checking if any of them match the
251 * rvalue, and if so, move the previous copy of the expression to a temporary
252 * and return a reference of the temporary.
255 cse_visitor::try_cse(ir_rvalue
*rvalue
)
257 foreach_list(node
, ae
) {
258 ae_entry
*entry
= (ae_entry
*)node
;
261 printf("Comparing to AE %p: ", entry
);
262 (*entry
->val
)->print();
266 if (!rvalue
->equals(*entry
->val
))
270 printf("CSE: Replacing: ");
271 (*entry
->val
)->print();
273 printf("CSE: with: ");
279 ir_instruction
*base_ir
= entry
->base_ir
;
281 ir_variable
*var
= new(rvalue
) ir_variable(rvalue
->type
,
285 /* Write the previous expression result into a new variable. */
286 base_ir
->insert_before(var
);
287 ir_assignment
*assignment
= assign(var
, *entry
->val
);
288 base_ir
->insert_before(assignment
);
290 /* Replace the expression in the original tree with a deref of the
291 * variable, but keep tracking the expression for further reuse.
293 *entry
->val
= new(rvalue
) ir_dereference_variable(var
);
294 entry
->val
= &assignment
->rhs
;
298 /* Update the base_irs in the AE list. We have to be sure that
299 * they're correct -- expressions from our base_ir that weren't moved
300 * need to stay in this base_ir (so that later consumption of them
301 * puts new variables between our new variable and our base_ir), but
302 * expressions from our base_ir that we *did* move need base_ir
303 * updated so that any further elimination from inside gets its new
304 * assignments put before our new assignment.
306 foreach_list(fixup_node
, ae
) {
307 ae_entry
*fixup_entry
= (ae_entry
*)fixup_node
;
308 if (contains_rvalue(assignment
->rhs
, *fixup_entry
->val
))
309 fixup_entry
->base_ir
= assignment
;
316 /* Replace the expression in our current tree with the variable. */
317 return new(rvalue
) ir_dereference_variable(entry
->var
);
323 /** Add the rvalue to the list of available expressions for CSE. */
325 cse_visitor::add_to_ae(ir_rvalue
**rvalue
)
328 printf("CSE: Add to AE: ");
333 ae
->push_tail(new(mem_ctx
) ae_entry(base_ir
, rvalue
));
340 cse_visitor::handle_rvalue(ir_rvalue
**rvalue
)
346 printf("CSE: handle_rvalue ");
351 if (!is_cse_candidate(*rvalue
))
354 ir_rvalue
*new_rvalue
= try_cse(*rvalue
);
356 *rvalue
= new_rvalue
;
360 validate_ir_tree(validate_instructions
);
367 cse_visitor::visit_enter(ir_if
*ir
)
369 handle_rvalue(&ir
->condition
);
372 visit_list_elements(this, &ir
->then_instructions
);
375 visit_list_elements(this, &ir
->else_instructions
);
378 return visit_continue_with_parent
;
382 cse_visitor::visit_enter(ir_function_signature
*ir
)
385 visit_list_elements(this, &ir
->body
);
388 return visit_continue_with_parent
;
392 cse_visitor::visit_enter(ir_loop
*ir
)
395 visit_list_elements(this, &ir
->body_instructions
);
398 return visit_continue_with_parent
;
402 cse_visitor::visit_enter(ir_call
*ir
)
404 /* Because call is an exec_list of ir_rvalues, handle_rvalue gets passed a
405 * pointer to the (ir_rvalue *) on the stack. Since we save those pointers
406 * in the AE list, we can't let handle_rvalue get called.
408 return visit_continue_with_parent
;
412 * Does a (uniform-value) constant subexpression elimination pass on the code
413 * present in the instruction stream.
416 do_cse(exec_list
*instructions
)
418 cse_visitor
v(instructions
);
420 visit_list_elements(&v
, instructions
);