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