• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright © 2010 Intel Corporation
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * constant 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, constant, 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 constantright 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 CONSTANTRIGHT 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 opt_constant_propagation.cpp
26  *
27  * Tracks assignments of constants to channels of variables, and
28  * usage of those constant channels with direct usage of the constants.
29  *
30  * This can lead to constant folding and algebraic optimizations in
31  * those later expressions, while causing no increase in instruction
32  * count (due to constants being generally free to load from a
33  * constant push buffer or as instruction immediate values) and
34  * possibly reducing register pressure.
35  */
36 
37 #include "ir.h"
38 #include "ir_visitor.h"
39 #include "ir_rvalue_visitor.h"
40 #include "ir_basic_block.h"
41 #include "ir_optimization.h"
42 #include "compiler/glsl_types.h"
43 #include "util/hash_table.h"
44 
45 namespace {
46 
47 class acp_entry : public exec_node
48 {
49 public:
50    /* override operator new from exec_node */
51    DECLARE_LINEAR_ZALLOC_CXX_OPERATORS(acp_entry)
52 
acp_entry(ir_variable * var,unsigned write_mask,ir_constant * constant)53    acp_entry(ir_variable *var, unsigned write_mask, ir_constant *constant)
54    {
55       assert(var);
56       assert(constant);
57       this->var = var;
58       this->write_mask = write_mask;
59       this->constant = constant;
60       this->initial_values = write_mask;
61    }
62 
acp_entry(const acp_entry * src)63    acp_entry(const acp_entry *src)
64    {
65       this->var = src->var;
66       this->write_mask = src->write_mask;
67       this->constant = src->constant;
68       this->initial_values = src->initial_values;
69    }
70 
71    ir_variable *var;
72    ir_constant *constant;
73    unsigned write_mask;
74 
75    /** Mask of values initially available in the constant. */
76    unsigned initial_values;
77 };
78 
79 
80 class ir_constant_propagation_visitor : public ir_rvalue_visitor {
81 public:
ir_constant_propagation_visitor()82    ir_constant_propagation_visitor()
83    {
84       progress = false;
85       killed_all = false;
86       mem_ctx = ralloc_context(0);
87       this->lin_ctx = linear_alloc_parent(this->mem_ctx, 0);
88       this->acp = new(mem_ctx) exec_list;
89       this->kills = _mesa_pointer_hash_table_create(mem_ctx);
90    }
~ir_constant_propagation_visitor()91    ~ir_constant_propagation_visitor()
92    {
93       ralloc_free(mem_ctx);
94    }
95 
96    virtual ir_visitor_status visit_enter(class ir_loop *);
97    virtual ir_visitor_status visit_enter(class ir_function_signature *);
98    virtual ir_visitor_status visit_enter(class ir_function *);
99    virtual ir_visitor_status visit_leave(class ir_assignment *);
100    virtual ir_visitor_status visit_enter(class ir_call *);
101    virtual ir_visitor_status visit_enter(class ir_if *);
102 
103    void add_constant(ir_assignment *ir);
104    void constant_folding(ir_rvalue **rvalue);
105    void constant_propagation(ir_rvalue **rvalue);
106    void kill(ir_variable *ir, unsigned write_mask);
107    void handle_if_block(exec_list *instructions, hash_table *kills, bool *killed_all);
108    void handle_loop(class ir_loop *, bool keep_acp);
109    void handle_rvalue(ir_rvalue **rvalue);
110 
111    /** List of acp_entry: The available constants to propagate */
112    exec_list *acp;
113 
114    /**
115     * Hash table of killed entries: maps variables to the mask of killed channels.
116     */
117    hash_table *kills;
118 
119    bool progress;
120 
121    bool killed_all;
122 
123    void *mem_ctx;
124    void *lin_ctx;
125 };
126 
127 
128 void
constant_folding(ir_rvalue ** rvalue)129 ir_constant_propagation_visitor::constant_folding(ir_rvalue **rvalue)
130 {
131    if (this->in_assignee || *rvalue == NULL)
132       return;
133 
134    if (ir_constant_fold(rvalue))
135       this->progress = true;
136 
137    ir_dereference_variable *var_ref = (*rvalue)->as_dereference_variable();
138    if (var_ref && !var_ref->type->is_array()) {
139       ir_constant *constant =
140          var_ref->constant_expression_value(ralloc_parent(var_ref));
141       if (constant) {
142          *rvalue = constant;
143          this->progress = true;
144       }
145    }
146 }
147 
148 void
constant_propagation(ir_rvalue ** rvalue)149 ir_constant_propagation_visitor::constant_propagation(ir_rvalue **rvalue) {
150 
151    if (this->in_assignee || !*rvalue)
152       return;
153 
154    const glsl_type *type = (*rvalue)->type;
155    if (!type->is_scalar() && !type->is_vector())
156       return;
157 
158    ir_swizzle *swiz = NULL;
159    ir_dereference_variable *deref = (*rvalue)->as_dereference_variable();
160    if (!deref) {
161       swiz = (*rvalue)->as_swizzle();
162       if (!swiz)
163 	 return;
164 
165       deref = swiz->val->as_dereference_variable();
166       if (!deref)
167 	 return;
168    }
169 
170    ir_constant_data data;
171    memset(&data, 0, sizeof(data));
172 
173    for (unsigned int i = 0; i < type->components(); i++) {
174       int channel;
175       acp_entry *found = NULL;
176 
177       if (swiz) {
178 	 switch (i) {
179 	 case 0: channel = swiz->mask.x; break;
180 	 case 1: channel = swiz->mask.y; break;
181 	 case 2: channel = swiz->mask.z; break;
182 	 case 3: channel = swiz->mask.w; break;
183 	 default: assert(!"shouldn't be reached"); channel = 0; break;
184 	 }
185       } else {
186 	 channel = i;
187       }
188 
189       foreach_in_list(acp_entry, entry, this->acp) {
190 	 if (entry->var == deref->var && entry->write_mask & (1 << channel)) {
191 	    found = entry;
192 	    break;
193 	 }
194       }
195 
196       if (!found)
197 	 return;
198 
199       int rhs_channel = 0;
200       for (int j = 0; j < 4; j++) {
201 	 if (j == channel)
202 	    break;
203 	 if (found->initial_values & (1 << j))
204 	    rhs_channel++;
205       }
206 
207       switch (type->base_type) {
208       case GLSL_TYPE_FLOAT:
209 	 data.f[i] = found->constant->value.f[rhs_channel];
210 	 break;
211       case GLSL_TYPE_FLOAT16:
212 	 data.f16[i] = found->constant->value.f16[rhs_channel];
213 	 break;
214       case GLSL_TYPE_DOUBLE:
215 	 data.d[i] = found->constant->value.d[rhs_channel];
216 	 break;
217       case GLSL_TYPE_INT:
218 	 data.i[i] = found->constant->value.i[rhs_channel];
219 	 break;
220       case GLSL_TYPE_UINT:
221 	 data.u[i] = found->constant->value.u[rhs_channel];
222 	 break;
223       case GLSL_TYPE_INT16:
224 	 data.i16[i] = found->constant->value.i16[rhs_channel];
225 	 break;
226       case GLSL_TYPE_UINT16:
227 	 data.u16[i] = found->constant->value.u16[rhs_channel];
228 	 break;
229       case GLSL_TYPE_BOOL:
230 	 data.b[i] = found->constant->value.b[rhs_channel];
231 	 break;
232       case GLSL_TYPE_UINT64:
233 	 data.u64[i] = found->constant->value.u64[rhs_channel];
234 	 break;
235       case GLSL_TYPE_INT64:
236 	 data.i64[i] = found->constant->value.i64[rhs_channel];
237 	 break;
238       default:
239 	 assert(!"not reached");
240 	 break;
241       }
242    }
243 
244    *rvalue = new(ralloc_parent(deref)) ir_constant(type, &data);
245    this->progress = true;
246 }
247 
248 void
handle_rvalue(ir_rvalue ** rvalue)249 ir_constant_propagation_visitor::handle_rvalue(ir_rvalue **rvalue)
250 {
251    constant_propagation(rvalue);
252    constant_folding(rvalue);
253 }
254 
255 ir_visitor_status
visit_enter(ir_function_signature * ir)256 ir_constant_propagation_visitor::visit_enter(ir_function_signature *ir)
257 {
258    /* Treat entry into a function signature as a completely separate
259     * block.  Any instructions at global scope will be shuffled into
260     * main() at link time, so they're irrelevant to us.
261     */
262    exec_list *orig_acp = this->acp;
263    hash_table *orig_kills = this->kills;
264    bool orig_killed_all = this->killed_all;
265 
266    this->acp = new(mem_ctx) exec_list;
267    this->kills = _mesa_pointer_hash_table_create(mem_ctx);
268    this->killed_all = false;
269 
270    visit_list_elements(this, &ir->body);
271 
272    this->kills = orig_kills;
273    this->acp = orig_acp;
274    this->killed_all = orig_killed_all;
275 
276    return visit_continue_with_parent;
277 }
278 
279 ir_visitor_status
visit_leave(ir_assignment * ir)280 ir_constant_propagation_visitor::visit_leave(ir_assignment *ir)
281 {
282   constant_folding(&ir->rhs);
283 
284    if (this->in_assignee)
285       return visit_continue;
286 
287    unsigned kill_mask = ir->write_mask;
288    if (ir->lhs->as_dereference_array()) {
289       /* The LHS of the assignment uses an array indexing operator (e.g. v[i]
290        * = ...;).  Since we only try to constant propagate vectors and
291        * scalars, this means that either (a) array indexing is being used to
292        * select a vector component, or (b) the variable in question is neither
293        * a scalar or a vector, so we don't care about it.  In the former case,
294        * we want to kill the whole vector, since in general we can't predict
295        * which vector component will be selected by array indexing.  In the
296        * latter case, it doesn't matter what we do, so go ahead and kill the
297        * whole variable anyway.
298        *
299        * Note that if the array index is constant (e.g. v[2] = ...;), we could
300        * in principle be smarter, but we don't need to, because a future
301        * optimization pass will convert it to a simple assignment with the
302        * correct mask.
303        */
304       kill_mask = ~0;
305    }
306    kill(ir->lhs->variable_referenced(), kill_mask);
307 
308    add_constant(ir);
309 
310    return visit_continue;
311 }
312 
313 ir_visitor_status
visit_enter(ir_function * ir)314 ir_constant_propagation_visitor::visit_enter(ir_function *ir)
315 {
316    (void) ir;
317    return visit_continue;
318 }
319 
320 ir_visitor_status
visit_enter(ir_call * ir)321 ir_constant_propagation_visitor::visit_enter(ir_call *ir)
322 {
323    /* Do constant propagation on call parameters, but skip any out params */
324    foreach_two_lists(formal_node, &ir->callee->parameters,
325                      actual_node, &ir->actual_parameters) {
326       ir_variable *sig_param = (ir_variable *) formal_node;
327       ir_rvalue *param = (ir_rvalue *) actual_node;
328       if (sig_param->data.mode != ir_var_function_out
329           && sig_param->data.mode != ir_var_function_inout) {
330 	 ir_rvalue *new_param = param;
331 	 handle_rvalue(&new_param);
332          if (new_param != param)
333 	    param->replace_with(new_param);
334 	 else
335 	    param->accept(this);
336       }
337    }
338 
339    /* Since we're unlinked, we don't (necssarily) know the side effects of
340     * this call.  So kill all copies.
341     */
342    acp->make_empty();
343    this->killed_all = true;
344 
345    return visit_continue_with_parent;
346 }
347 
348 void
handle_if_block(exec_list * instructions,hash_table * kills,bool * killed_all)349 ir_constant_propagation_visitor::handle_if_block(exec_list *instructions, hash_table *kills, bool *killed_all)
350 {
351    exec_list *orig_acp = this->acp;
352    hash_table *orig_kills = this->kills;
353    bool orig_killed_all = this->killed_all;
354 
355    this->acp = new(mem_ctx) exec_list;
356    this->kills = kills;
357    this->killed_all = false;
358 
359    /* Populate the initial acp with a constant of the original */
360    foreach_in_list(acp_entry, a, orig_acp) {
361       this->acp->push_tail(new(this->lin_ctx) acp_entry(a));
362    }
363 
364    visit_list_elements(this, instructions);
365 
366    *killed_all = this->killed_all;
367    this->kills = orig_kills;
368    this->acp = orig_acp;
369    this->killed_all = orig_killed_all;
370 }
371 
372 ir_visitor_status
visit_enter(ir_if * ir)373 ir_constant_propagation_visitor::visit_enter(ir_if *ir)
374 {
375    ir->condition->accept(this);
376    handle_rvalue(&ir->condition);
377 
378    hash_table *new_kills = _mesa_pointer_hash_table_create(mem_ctx);
379    bool then_killed_all = false;
380    bool else_killed_all = false;
381 
382    handle_if_block(&ir->then_instructions, new_kills, &then_killed_all);
383    handle_if_block(&ir->else_instructions, new_kills, &else_killed_all);
384 
385    if (then_killed_all || else_killed_all) {
386       acp->make_empty();
387       killed_all = true;
388    } else {
389       hash_table_foreach(new_kills, htk)
390          kill((ir_variable *) htk->key, (uintptr_t) htk->data);
391    }
392 
393    _mesa_hash_table_destroy(new_kills, NULL);
394 
395    /* handle_if_block() already descended into the children. */
396    return visit_continue_with_parent;
397 }
398 
399 void
handle_loop(ir_loop * ir,bool keep_acp)400 ir_constant_propagation_visitor::handle_loop(ir_loop *ir, bool keep_acp)
401 {
402    exec_list *orig_acp = this->acp;
403    hash_table *orig_kills = this->kills;
404    bool orig_killed_all = this->killed_all;
405 
406    this->acp = new(mem_ctx) exec_list;
407    this->kills = _mesa_pointer_hash_table_create(mem_ctx);
408    this->killed_all = false;
409 
410    if (keep_acp) {
411       foreach_in_list(acp_entry, a, orig_acp) {
412          this->acp->push_tail(new(this->lin_ctx) acp_entry(a));
413       }
414    }
415 
416    visit_list_elements(this, &ir->body_instructions);
417 
418    if (this->killed_all) {
419       orig_acp->make_empty();
420    }
421 
422    hash_table *new_kills = this->kills;
423    this->kills = orig_kills;
424    this->acp = orig_acp;
425    this->killed_all = this->killed_all || orig_killed_all;
426 
427    hash_table_foreach(new_kills, htk) {
428       kill((ir_variable *) htk->key, (uintptr_t) htk->data);
429    }
430 }
431 
432 ir_visitor_status
visit_enter(ir_loop * ir)433 ir_constant_propagation_visitor::visit_enter(ir_loop *ir)
434 {
435    /* Make a conservative first pass over the loop with an empty ACP set.
436     * This also removes any killed entries from the original ACP set.
437     */
438    handle_loop(ir, false);
439 
440    /* Then, run it again with the real ACP set, minus any killed entries.
441     * This takes care of propagating values from before the loop into it.
442     */
443    handle_loop(ir, true);
444 
445    /* already descended into the children. */
446    return visit_continue_with_parent;
447 }
448 
449 void
kill(ir_variable * var,unsigned write_mask)450 ir_constant_propagation_visitor::kill(ir_variable *var, unsigned write_mask)
451 {
452    assert(var != NULL);
453 
454    /* We don't track non-vectors. */
455    if (!var->type->is_vector() && !var->type->is_scalar())
456       return;
457 
458    /* Remove any entries currently in the ACP for this kill. */
459    foreach_in_list_safe(acp_entry, entry, this->acp) {
460       if (entry->var == var) {
461 	 entry->write_mask &= ~write_mask;
462 	 if (entry->write_mask == 0)
463 	    entry->remove();
464       }
465    }
466 
467    /* Add this writemask of the variable to the hash table of killed
468     * variables in this block.
469     */
470    hash_entry *kill_hash_entry = _mesa_hash_table_search(this->kills, var);
471    if (kill_hash_entry) {
472       uintptr_t new_write_mask = ((uintptr_t) kill_hash_entry->data) | write_mask;
473       kill_hash_entry->data = (void *) new_write_mask;
474       return;
475    }
476    /* Not already in the hash table.  Make new entry. */
477    _mesa_hash_table_insert(this->kills, var, (void *) uintptr_t(write_mask));
478 }
479 
480 /**
481  * Adds an entry to the available constant list if it's a plain assignment
482  * of a variable to a variable.
483  */
484 void
add_constant(ir_assignment * ir)485 ir_constant_propagation_visitor::add_constant(ir_assignment *ir)
486 {
487    acp_entry *entry;
488 
489    if (ir->condition)
490       return;
491 
492    if (!ir->write_mask)
493       return;
494 
495    ir_dereference_variable *deref = ir->lhs->as_dereference_variable();
496    ir_constant *constant = ir->rhs->as_constant();
497 
498    if (!deref || !constant)
499       return;
500 
501    /* Only do constant propagation on vectors.  Constant matrices,
502     * arrays, or structures would require more work elsewhere.
503     */
504    if (!deref->var->type->is_vector() && !deref->var->type->is_scalar())
505       return;
506 
507    /* We can't do copy propagation on buffer variables, since the underlying
508     * memory storage is shared across multiple threads we can't be sure that
509     * the variable value isn't modified between this assignment and the next
510     * instruction where its value is read.
511     */
512    if (deref->var->data.mode == ir_var_shader_storage ||
513        deref->var->data.mode == ir_var_shader_shared)
514       return;
515 
516    entry = new(this->lin_ctx) acp_entry(deref->var, ir->write_mask, constant);
517    this->acp->push_tail(entry);
518 }
519 
520 } /* unnamed namespace */
521 
522 /**
523  * Does a constant propagation pass on the code present in the instruction stream.
524  */
525 bool
do_constant_propagation(exec_list * instructions)526 do_constant_propagation(exec_list *instructions)
527 {
528    ir_constant_propagation_visitor v;
529 
530    visit_list_elements(&v, instructions);
531 
532    return v.progress;
533 }
534