ir_copy_propagation.cpp

   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 ir_copy_propagation.cpp
  26  *
  27  * Moves usage of recently-copied variables to the previous copy of
  28  * the variable within basic blocks.
  29  *
  30  * This should reduce the number of MOV instructions in the generated
  31  * programs unless copy propagation is also done on the LIR, and may
  32  * help anyway by triggering other optimizations that live in the HIR.
  33  */
  34
  35 #include <stdio.h>
  36 #include "ir.h"
  37 #include "ir_visitor.h"
  38 #include "ir_print_visitor.h"
  39 #include "ir_basic_block.h"
  40 #include "ir_optimization.h"
  41 #include "glsl_types.h"
  42
  43 class acp_entry : public exec_node
  44 {
  45 public:
  46    acp_entry(ir_variable *lhs, ir_variable *rhs)
  47    {
  48       assert(lhs);
  49       assert(rhs);
  50       this->lhs = lhs;
  51       this->rhs = rhs;
  52    }
  53
  54    ir_variable *lhs;
  55    ir_variable *rhs;
  56 };
  57
  58 class ir_copy_propagation_visitor : public ir_visitor {
  59 public:
  60    ir_copy_propagation_visitor(exec_list *acp)
  61    {
  62       progress = false;
  63       this->acp = acp;
  64    }
  65
  66    /**
  67     * \name Visit methods
  68     *
  69     * As typical for the visitor pattern, there must be one \c visit method for
  70     * each concrete subclass of \c ir_instruction.  Virtual base classes within
  71     * the hierarchy should not have \c visit methods.
  72     */
  73    /*@{*/
  74    virtual void visit(ir_variable *);
  75    virtual void visit(ir_loop *);
  76    virtual void visit(ir_loop_jump *);
  77    virtual void visit(ir_function_signature *);
  78    virtual void visit(ir_function *);
  79    virtual void visit(ir_expression *);
  80    virtual void visit(ir_swizzle *);
  81    virtual void visit(ir_dereference *);
  82    virtual void visit(ir_assignment *);
  83    virtual void visit(ir_constant *);
  84    virtual void visit(ir_call *);
  85    virtual void visit(ir_return *);
  86    virtual void visit(ir_if *);
  87    /*@}*/
  88
  89    /** List of acp_entry */
  90    exec_list *acp;
  91    bool progress;
  92 };
  93
  94
  95 void
  96 ir_copy_propagation_visitor::visit(ir_variable *ir)
  97 {
  98    (void)ir;
  99 }
 100
 101
 102 void
 103 ir_copy_propagation_visitor::visit(ir_loop *ir)
 104 {
 105    (void)ir;
 106 }
 107
 108 void
 109 ir_copy_propagation_visitor::visit(ir_loop_jump *ir)
 110 {
 111    (void) ir;
 112 }
 113
 114
 115 void
 116 ir_copy_propagation_visitor::visit(ir_function_signature *ir)
 117 {
 118    (void)ir;
 119 }
 120
 121 void
 122 ir_copy_propagation_visitor::visit(ir_function *ir)
 123 {
 124    (void) ir;
 125 }
 126
 127 void
 128 ir_copy_propagation_visitor::visit(ir_expression *ir)
 129 {
 130    unsigned int operand;
 131
 132    for (operand = 0; operand < ir->get_num_operands(); operand++) {
 133       ir->operands[operand]->accept(this);
 134    }
 135 }
 136
 137
 138 void
 139 ir_copy_propagation_visitor::visit(ir_swizzle *ir)
 140 {
 141    ir->val->accept(this);
 142 }
 143
 144 /**
 145  * Replaces dereferences of ACP RHS variables with ACP LHS variables.
 146  *
 147  * This is where the actual copy propagation occurs.  Note that the
 148  * rewriting of ir_dereference means that the ir_dereference instance
 149  * must not be shared by multiple IR operations!
 150  */
 151 void
 152 ir_copy_propagation_visitor::visit(ir_dereference *ir)
 153 {
 154    ir_variable *var;
 155
 156    if (ir->mode == ir_dereference::ir_reference_array) {
 157       ir->selector.array_index->accept(this);
 158    }
 159
 160    var = ir->var->as_variable();
 161    if (var) {
 162       foreach_iter(exec_list_iterator, iter, *this->acp) {
 163          acp_entry *entry = (acp_entry *)iter.get();
 164
 165          if (var == entry->lhs) {
 166             ir->var = entry->rhs;
 167             this->progress = true;
 168             break;
 169          }
 170       }
 171    } else {
 172       ir->var->accept(this);
 173    }
 174 }
 175
 176 void
 177 ir_copy_propagation_visitor::visit(ir_assignment *ir)
 178 {
 179    if (ir->condition)
 180       ir->condition->accept(this);
 181
 182    /* Ignores the LHS.  Don't want to rewrite the LHS to point at some
 183     * other storage!
 184     */
 185
 186    ir->rhs->accept(this);
 187 }
 188
 189
 190 void
 191 ir_copy_propagation_visitor::visit(ir_constant *ir)
 192 {
 193    (void) ir;
 194 }
 195
 196
 197 void
 198 ir_copy_propagation_visitor::visit(ir_call *ir)
 199 {
 200    (void)ir;
 201
 202    /* Note, if we were to do copy propagation to parameters of calls, we'd
 203     * have to be careful about out params.
 204     */
 205 }
 206
 207
 208 void
 209 ir_copy_propagation_visitor::visit(ir_return *ir)
 210 {
 211    ir_rvalue *val = ir->get_value();
 212
 213    if (val)
 214       val->accept(this);
 215 }
 216
 217
 218 void
 219 ir_copy_propagation_visitor::visit(ir_if *ir)
 220 {
 221    ir->condition->accept(this);
 222 }
 223
 224 static bool
 225 propagate_copies(ir_instruction *ir, exec_list *acp)
 226 {
 227    ir_copy_propagation_visitor v(acp);
 228
 229    ir->accept(&v);
 230
 231    return v.progress;
 232 }
 233
 234 static void
 235 kill_invalidated_copies(ir_assignment *ir, exec_list *acp)
 236 {
 237    ir_instruction *current = ir->lhs;
 238
 239    /* Walk down the dereference chain to find the variable at the end
 240     * of it that we're actually modifying.
 241     */
 242    while (current != NULL) {
 243       ir_swizzle *swiz;
 244       ir_dereference *deref;
 245
 246       if ((swiz = current->as_swizzle())) {
 247          current = swiz->val;
 248       } else if ((deref = current->as_dereference())) {
 249          current = deref->var;
 250       } else {
 251          ir_variable *var = current->as_variable();
 252          assert(var);
 253
 254          foreach_iter(exec_list_iterator, iter, *acp) {
 255             acp_entry *entry = (acp_entry *)iter.get();
 256
 257             if (entry->lhs == var || entry->rhs == var) {
 258                entry->remove();
 259             }
 260          }
 261          current = NULL;
 262          break;
 263       }
 264    }
 265 }
 266
 267 /**
 268  * Adds an entry to the available copy list if it's a plain assignment
 269  * of a variable to a variable.
 270  */
 271 static void
 272 add_copy(ir_assignment *ir, exec_list *acp)
 273 {
 274    acp_entry *entry;
 275
 276    if (ir->condition) {
 277       ir_constant *condition = ir->condition->as_constant();
 278       if (!condition || !condition->value.b[0])
 279          return;
 280    }
 281
 282    ir_dereference *lhs_deref = ir->lhs->as_dereference();
 283    if (!lhs_deref || lhs_deref->mode != ir_dereference::ir_reference_variable)
 284       return;
 285    ir_variable *lhs_var = lhs_deref->var->as_variable();
 286
 287    ir_dereference *rhs_deref = ir->rhs->as_dereference();
 288    if (!rhs_deref || rhs_deref->mode != ir_dereference::ir_reference_variable)
 289       return;
 290    ir_variable *rhs_var = rhs_deref->var->as_variable();
 291
 292    entry = new acp_entry(lhs_var, rhs_var);
 293    acp->push_tail(entry);
 294 }
 295
 296 static void
 297 copy_propagation_basic_block(ir_instruction *first,
 298                              ir_instruction *last,
 299                              void *data)
 300 {
 301    ir_instruction *ir;
 302    /* List of avaialble_copy */
 303    exec_list acp;
 304    bool *out_progress = (bool *)data;
 305    bool progress = false;
 306
 307    for (ir = first;; ir = (ir_instruction *)ir->next) {
 308       ir_assignment *ir_assign = ir->as_assignment();
 309
 310       progress = propagate_copies(ir, &acp) || progress;
 311
 312       if (ir_assign) {
 313          kill_invalidated_copies(ir_assign, &acp);
 314
 315          add_copy(ir_assign, &acp);
 316       }
 317       if (ir == last)
 318          break;
 319    }
 320    *out_progress = progress;
 321 }
 322
 323 /**
 324  * Does a copy propagation pass on the code present in the instruction stream.
 325  */
 326 bool
 327 do_copy_propagation(exec_list *instructions)
 328 {
 329    bool progress = false;
 330
 331    call_for_basic_blocks(instructions, copy_propagation_basic_block, &progress);
 332
 333    return progress;
 334 }