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 namespace {
     44 
     45 class assignment_entry : public exec_node
     46 {
     47 public:
     48    assignment_entry(ir_variable *lhs, ir_assignment *ir)
     49    {
     50       assert(lhs);
     51       assert(ir);
     52       this->lhs = lhs;
     53       this->ir = ir;
     54       this->available = ir->write_mask;
     55    }
     56 
     57    ir_variable *lhs;
     58    ir_assignment *ir;
     59 
     60    /* bitmask of xyzw channels written that haven't been used so far. */
     61    int available;
     62 };
     63 
     64 class kill_for_derefs_visitor : public ir_hierarchical_visitor {
     65 public:
     66    kill_for_derefs_visitor(exec_list *assignments)
     67    {
     68       this->assignments = assignments;
     69    }
     70 
     71    void kill_channels(ir_variable *const var, int used)
     72    {
     73       foreach_iter(exec_list_iterator, iter, *this->assignments) {
     74 	 assignment_entry *entry = (assignment_entry *)iter.get();
     75 
     76 	 if (entry->lhs == var) {
     77 	    if (var->type->is_scalar() || var->type->is_vector()) {
     78 	       if (debug)
     79 		  printf("kill %s (0x%01x - 0x%01x)\n", entry->lhs->name,
     80 			 entry->available, used);
     81 	       entry->available &= ~used;
     82 	       if (!entry->available)
     83 		  entry->remove();
     84 	    } else {
     85 	       if (debug)
     86 		  printf("kill %s\n", entry->lhs->name);
     87 	       entry->remove();
     88 	    }
     89 	 }
     90       }
     91    }
     92 
     93    virtual ir_visitor_status visit(ir_dereference_variable *ir)
     94    {
     95       kill_channels(ir->var, ~0);
     96 
     97       return visit_continue;
     98    }
     99 
    100    virtual ir_visitor_status visit(ir_swizzle *ir)
    101    {
    102       ir_dereference_variable *deref = ir->val->as_dereference_variable();
    103       if (!deref)
    104 	 return visit_continue;
    105 
    106       int used = 0;
    107       used |= 1 << ir->mask.x;
    108       used |= 1 << ir->mask.y;
    109       used |= 1 << ir->mask.z;
    110       used |= 1 << ir->mask.w;
    111 
    112       kill_channels(deref->var, used);
    113 
    114       return visit_continue_with_parent;
    115    }
    116 
    117 private:
    118    exec_list *assignments;
    119 };
    120 
    121 class array_index_visit : public ir_hierarchical_visitor {
    122 public:
    123    array_index_visit(ir_hierarchical_visitor *v)
    124    {
    125       this->visitor = v;
    126    }
    127 
    128    virtual ir_visitor_status visit_enter(class ir_dereference_array *ir)
    129    {
    130       ir->array_index->accept(visitor);
    131       return visit_continue;
    132    }
    133 
    134    static void run(ir_instruction *ir, ir_hierarchical_visitor *v)
    135    {
    136       array_index_visit top_visit(v);
    137       ir->accept(& top_visit);
    138    }
    139 
    140    ir_hierarchical_visitor *visitor;
    141 };
    142 
    143 } /* unnamed namespace */
    144 
    145 /**
    146  * Adds an entry to the available copy list if it's a plain assignment
    147  * of a variable to a variable.
    148  */
    149 static bool
    150 process_assignment(void *ctx, ir_assignment *ir, exec_list *assignments)
    151 {
    152    ir_variable *var = NULL;
    153    bool progress = false;
    154    kill_for_derefs_visitor v(assignments);
    155 
    156    /* Kill assignment entries for things used to produce this assignment. */
    157    ir->rhs->accept(&v);
    158    if (ir->condition) {
    159       ir->condition->accept(&v);
    160    }
    161 
    162    /* Kill assignment enties used as array indices.
    163     */
    164    array_index_visit::run(ir->lhs, &v);
    165    var = ir->lhs->variable_referenced();
    166    assert(var);
    167 
    168    /* Now, check if we did a whole-variable assignment. */
    169    if (!ir->condition) {
    170       ir_dereference_variable *deref_var = ir->lhs->as_dereference_variable();
    171 
    172       /* If it's a vector type, we can do per-channel elimination of
    173        * use of the RHS.
    174        */
    175       if (deref_var && (deref_var->var->type->is_scalar() ||
    176 			deref_var->var->type->is_vector())) {
    177 
    178 	 if (debug)
    179 	    printf("looking for %s.0x%01x to remove\n", var->name,
    180 		   ir->write_mask);
    181 
    182 	 foreach_iter(exec_list_iterator, iter, *assignments) {
    183 	    assignment_entry *entry = (assignment_entry *)iter.get();
    184 
    185 	    if (entry->lhs != var)
    186 	       continue;
    187 
    188 	    int remove = entry->available & ir->write_mask;
    189 	    if (debug) {
    190 	       printf("%s 0x%01x - 0x%01x = 0x%01x\n",
    191 		      var->name,
    192 		      entry->ir->write_mask,
    193 		      remove, entry->ir->write_mask & ~remove);
    194 	    }
    195 	    if (remove) {
    196 	       progress = true;
    197 
    198 	       if (debug) {
    199 		  printf("rewriting:\n  ");
    200 		  entry->ir->print();
    201 		  printf("\n");
    202 	       }
    203 
    204 	       entry->ir->write_mask &= ~remove;
    205 	       entry->available &= ~remove;
    206 	       if (entry->ir->write_mask == 0) {
    207 		  /* Delete the dead assignment. */
    208 		  entry->ir->remove();
    209 		  entry->remove();
    210 	       } else {
    211 		  void *mem_ctx = ralloc_parent(entry->ir);
    212 		  /* Reswizzle the RHS arguments according to the new
    213 		   * write_mask.
    214 		   */
    215 		  unsigned components[4];
    216 		  unsigned channels = 0;
    217 		  unsigned next = 0;
    218 
    219 		  for (int i = 0; i < 4; i++) {
    220 		     if ((entry->ir->write_mask | remove) & (1 << i)) {
    221 			if (!(remove & (1 << i)))
    222 			   components[channels++] = next;
    223 			next++;
    224 		     }
    225 		  }
    226 
    227 		  entry->ir->rhs = new(mem_ctx) ir_swizzle(entry->ir->rhs,
    228 							   components,
    229 							   channels);
    230 		  if (debug) {
    231 		     printf("to:\n  ");
    232 		     entry->ir->print();
    233 		     printf("\n");
    234 		  }
    235 	       }
    236 	    }
    237 	 }
    238       } else if (ir->whole_variable_written() != NULL) {
    239 	 /* We did a whole-variable assignment.  So, any instruction in
    240 	  * the assignment list with the same LHS is dead.
    241 	  */
    242 	 if (debug)
    243 	    printf("looking for %s to remove\n", var->name);
    244 	 foreach_iter(exec_list_iterator, iter, *assignments) {
    245 	    assignment_entry *entry = (assignment_entry *)iter.get();
    246 
    247 	    if (entry->lhs == var) {
    248 	       if (debug)
    249 		  printf("removing %s\n", var->name);
    250 	       entry->ir->remove();
    251 	       entry->remove();
    252 	       progress = true;
    253 	    }
    254 	 }
    255       }
    256    }
    257 
    258    /* Add this instruction to the assignment list available to be removed. */
    259    assignment_entry *entry = new(ctx) assignment_entry(var, ir);
    260    assignments->push_tail(entry);
    261 
    262    if (debug) {
    263       printf("add %s\n", var->name);
    264 
    265       printf("current entries\n");
    266       foreach_iter(exec_list_iterator, iter, *assignments) {
    267 	 assignment_entry *entry = (assignment_entry *)iter.get();
    268 
    269 	 printf("    %s (0x%01x)\n", entry->lhs->name, entry->available);
    270       }
    271    }
    272 
    273    return progress;
    274 }
    275 
    276 static void
    277 dead_code_local_basic_block(ir_instruction *first,
    278 			     ir_instruction *last,
    279 			     void *data)
    280 {
    281    ir_instruction *ir, *ir_next;
    282    /* List of avaialble_copy */
    283    exec_list assignments;
    284    bool *out_progress = (bool *)data;
    285    bool progress = false;
    286 
    287    void *ctx = ralloc_context(NULL);
    288    /* Safe looping, since process_assignment */
    289    for (ir = first, ir_next = (ir_instruction *)first->next;;
    290 	ir = ir_next, ir_next = (ir_instruction *)ir->next) {
    291       ir_assignment *ir_assign = ir->as_assignment();
    292 
    293       if (debug) {
    294 	 ir->print();
    295 	 printf("\n");
    296       }
    297 
    298       if (ir_assign) {
    299 	 progress = process_assignment(ctx, ir_assign, &assignments) || progress;
    300       } else {
    301 	 kill_for_derefs_visitor kill(&assignments);
    302 	 ir->accept(&kill);
    303       }
    304 
    305       if (ir == last)
    306 	 break;
    307    }
    308    *out_progress = progress;
    309    ralloc_free(ctx);
    310 }
    311 
    312 /**
    313  * Does a copy propagation pass on the code present in the instruction stream.
    314  */
    315 bool
    316 do_dead_code_local(exec_list *instructions)
    317 {
    318    bool progress = false;
    319 
    320    call_for_basic_blocks(instructions, dead_code_local_basic_block, &progress);
    321 
    322    return progress;
    323 }
    324