Home | History | Annotate | Download | only in glsl 
      1 /*
      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 opt_dead_code_local.cpp
     26  *
     27  * Eliminates local dead assignments from the code.
     28  *
     29  * This operates on basic blocks, tracking assignments and finding if
     30  * they're used before the variable is completely reassigned.
     31  *
     32  * Compare this to ir_dead_code.cpp, which operates globally looking
     33  * for assignments to variables that are never read.
     34  */
     35 
     36 #include "ir.h"
     37 #include "ir_basic_block.h"
     38 #include "ir_optimization.h"
     39 #include "glsl_types.h"
     40 
     41 static bool debug = false;
     42 
     43 class assignment_entry : public exec_node
     44 {
     45 public:
     46    assignment_entry(ir_variable *lhs, ir_instruction *ir)
     47    {
     48       assert(lhs);
     49       assert(ir);
     50       this->lhs = lhs;
     51       this->ir = ir;
     52    }
     53 
     54    ir_variable *lhs;
     55    ir_instruction *ir;
     56 };
     57 
     58 class kill_for_derefs_visitor : public ir_hierarchical_visitor {
     59 public:
     60    kill_for_derefs_visitor(exec_list *assignments)
     61    {
     62       this->assignments = assignments;
     63    }
     64 
     65    virtual ir_visitor_status visit(ir_dereference_variable *ir)
     66    {
     67       ir_variable *const var = ir->variable_referenced();
     68 
     69       foreach_iter(exec_list_iterator, iter, *this->assignments) {
     70 	 assignment_entry *entry = (assignment_entry *)iter.get();
     71 
     72 	 if (entry->lhs == var) {
     73 	    if (debug)
     74 	       printf("kill %s\n", entry->lhs->name);
     75 	    entry->remove();
     76 	 }
     77       }
     78 
     79       return visit_continue;
     80    }
     81 
     82 private:
     83    exec_list *assignments;
     84 };
     85 
     86 class array_index_visit : public ir_hierarchical_visitor {
     87 public:
     88    array_index_visit(ir_hierarchical_visitor *v)
     89    {
     90       this->visitor = v;
     91    }
     92 
     93    virtual ir_visitor_status visit_enter(class ir_dereference_array *ir)
     94    {
     95       ir->array_index->accept(visitor);
     96       return visit_continue;
     97    }
     98 
     99    static void run(ir_instruction *ir, ir_hierarchical_visitor *v)
    100    {
    101       array_index_visit top_visit(v);
    102       ir->accept(& top_visit);
    103    }
    104 
    105    ir_hierarchical_visitor *visitor;
    106 };
    107 
    108 
    109 /**
    110  * Adds an entry to the available copy list if it's a plain assignment
    111  * of a variable to a variable.
    112  */
    113 static bool
    114 process_assignment(void *ctx, ir_assignment *ir, exec_list *assignments)
    115 {
    116    ir_variable *var = NULL;
    117    bool progress = false;
    118    kill_for_derefs_visitor v(assignments);
    119 
    120    /* Kill assignment entries for things used to produce this assignment. */
    121    ir->rhs->accept(&v);
    122    if (ir->condition) {
    123       ir->condition->accept(&v);
    124    }
    125 
    126    /* Kill assignment enties used as array indices.
    127     */
    128    array_index_visit::run(ir->lhs, &v);
    129    var = ir->lhs->variable_referenced();
    130    assert(var);
    131 
    132    bool always_assign = true;
    133    if (ir->condition) {
    134       ir_constant *condition = ir->condition->as_constant();
    135       if (!condition || !condition->value.b[0])
    136 	 always_assign = false;
    137    }
    138 
    139    /* Now, check if we did a whole-variable assignment. */
    140    if (always_assign && (ir->whole_variable_written() != NULL)) {
    141       /* We did a whole-variable assignment.  So, any instruction in
    142        * the assignment list with the same LHS is dead.
    143        */
    144       if (debug)
    145 	 printf("looking for %s to remove\n", var->name);
    146       foreach_iter(exec_list_iterator, iter, *assignments) {
    147 	 assignment_entry *entry = (assignment_entry *)iter.get();
    148 
    149 	 if (entry->lhs == var) {
    150 	    if (debug)
    151 	       printf("removing %s\n", var->name);
    152 	    entry->ir->remove();
    153 	    entry->remove();
    154 	    progress = true;
    155 	 }
    156       }
    157    }
    158 
    159    /* Add this instruction to the assignment list available to be removed.
    160     * But not if the assignment has other side effects.
    161     */
    162    if (ir_has_call(ir))
    163       return progress;
    164 
    165    assignment_entry *entry = new(ctx) assignment_entry(var, ir);
    166    assignments->push_tail(entry);
    167 
    168    if (debug) {
    169       printf("add %s\n", var->name);
    170 
    171       printf("current entries\n");
    172       foreach_iter(exec_list_iterator, iter, *assignments) {
    173 	 assignment_entry *entry = (assignment_entry *)iter.get();
    174 
    175 	 printf("    %s\n", entry->lhs->name);
    176       }
    177    }
    178 
    179    return progress;
    180 }
    181 
    182 static void
    183 dead_code_local_basic_block(ir_instruction *first,
    184 			     ir_instruction *last,
    185 			     void *data)
    186 {
    187    ir_instruction *ir, *ir_next;
    188    /* List of avaialble_copy */
    189    exec_list assignments;
    190    bool *out_progress = (bool *)data;
    191    bool progress = false;
    192 
    193    void *ctx = hieralloc_new(NULL);
    194    /* Safe looping, since process_assignment */
    195    for (ir = first, ir_next = (ir_instruction *)first->next;;
    196 	ir = ir_next, ir_next = (ir_instruction *)ir->next) {
    197       ir_assignment *ir_assign = ir->as_assignment();
    198 
    199       if (debug) {
    200 	 ir->print();
    201 	 printf("\n");
    202       }
    203 
    204       if (ir_assign) {
    205 	 progress = process_assignment(ctx, ir_assign, &assignments) || progress;
    206       } else {
    207 	 kill_for_derefs_visitor kill(&assignments);
    208 	 ir->accept(&kill);
    209       }
    210 
    211       if (ir == last)
    212 	 break;
    213    }
    214    *out_progress = progress;
    215    hieralloc_free(ctx);
    216 }
    217 
    218 /**
    219  * Does a copy propagation pass on the code present in the instruction stream.
    220  */
    221 bool
    222 do_dead_code_local(exec_list *instructions)
    223 {
    224    bool progress = false;
    225 
    226    call_for_basic_blocks(instructions, dead_code_local_basic_block, &progress);
    227 
    228    return progress;
    229 }
    230