workbench/libs/mesa/src/glsl/opt_constant_propagation.cpp

   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 "glsl_types.h"
  43
  44 class acp_entry : public exec_node
  45 {
  46 public:
  47    acp_entry(ir_variable *var, unsigned write_mask, ir_constant *constant)
  48    {
  49       assert(var);
  50       assert(constant);
  51       this->var = var;
  52       this->write_mask = write_mask;
  53       this->constant = constant;
  54       this->initial_values = write_mask;
  55    }
  56
  57    acp_entry(const acp_entry *src)
  58    {
  59       this->var = src->var;
  60       this->write_mask = src->write_mask;
  61       this->constant = src->constant;
  62       this->initial_values = src->initial_values;
  63    }
  64
  65    ir_variable *var;
  66    ir_constant *constant;
  67    unsigned write_mask;
  68
  69    /** Mask of values initially available in the constant. */
  70    unsigned initial_values;
  71 };
  72
  73
  74 class kill_entry : public exec_node
  75 {
  76 public:
  77    kill_entry(ir_variable *var, unsigned write_mask)
  78    {
  79       assert(var);
  80       this->var = var;
  81       this->write_mask = write_mask;
  82    }
  83
  84    ir_variable *var;
  85    unsigned write_mask;
  86 };
  87
  88 class ir_constant_propagation_visitor : public ir_rvalue_visitor {
  89 public:
  90    ir_constant_propagation_visitor()
  91    {
  92       progress = false;
  93       mem_ctx = ralloc_context(0);
  94       this->acp = new(mem_ctx) exec_list;
  95       this->kills = new(mem_ctx) exec_list;
  96    }
  97    ~ir_constant_propagation_visitor()
  98    {
  99       ralloc_free(mem_ctx);
 100    }
 101
 102    virtual ir_visitor_status visit_enter(class ir_loop *);
 103    virtual ir_visitor_status visit_enter(class ir_function_signature *);
 104    virtual ir_visitor_status visit_enter(class ir_function *);
 105    virtual ir_visitor_status visit_leave(class ir_assignment *);
 106    virtual ir_visitor_status visit_enter(class ir_call *);
 107    virtual ir_visitor_status visit_enter(class ir_if *);
 108
 109    void add_constant(ir_assignment *ir);
 110    void kill(ir_variable *ir, unsigned write_mask);
 111    void handle_if_block(exec_list *instructions);
 112    void handle_rvalue(ir_rvalue **rvalue);
 113
 114    /** List of acp_entry: The available constants to propagate */
 115    exec_list *acp;
 116
 117    /**
 118     * List of kill_entry: The masks of variables whose values were
 119     * killed in this block.
 120     */
 121    exec_list *kills;
 122
 123    bool progress;
 124
 125    bool killed_all;
 126
 127    void *mem_ctx;
 128 };
 129
 130
 131 void
 132 ir_constant_propagation_visitor::handle_rvalue(ir_rvalue **rvalue)
 133 {
 134    if (this->in_assignee || !*rvalue)
 135       return;
 136
 137    const glsl_type *type = (*rvalue)->type;
 138    if (!type->is_scalar() && !type->is_vector())
 139       return;
 140
 141    ir_swizzle *swiz = NULL;
 142    ir_dereference_variable *deref = (*rvalue)->as_dereference_variable();
 143    if (!deref) {
 144       swiz = (*rvalue)->as_swizzle();
 145       if (!swiz)
 146          return;
 147
 148       deref = swiz->val->as_dereference_variable();
 149       if (!deref)
 150          return;
 151    }
 152
 153    ir_constant_data data;
 154    memset(&data, 0, sizeof(data));
 155
 156    for (unsigned int i = 0; i < type->components(); i++) {
 157       int channel;
 158       acp_entry *found = NULL;
 159
 160       if (swiz) {
 161          switch (i) {
 162          case 0: channel = swiz->mask.x; break;
 163          case 1: channel = swiz->mask.y; break;
 164          case 2: channel = swiz->mask.z; break;
 165          case 3: channel = swiz->mask.w; break;
 166          default: assert(!"shouldn't be reached"); channel = 0; break;
 167          }
 168       } else {
 169          channel = i;
 170       }
 171
 172       foreach_iter(exec_list_iterator, iter, *this->acp) {
 173          acp_entry *entry = (acp_entry *)iter.get();
 174          if (entry->var == deref->var && entry->write_mask & (1 << channel)) {
 175             found = entry;
 176             break;
 177          }
 178       }
 179
 180       if (!found)
 181          return;
 182
 183       int rhs_channel = 0;
 184       for (int j = 0; j < 4; j++) {
 185          if (j == channel)
 186             break;
 187          if (found->initial_values & (1 << j))
 188             rhs_channel++;
 189       }
 190
 191       switch (type->base_type) {
 192       case GLSL_TYPE_FLOAT:
 193          data.f[i] = found->constant->value.f[rhs_channel];
 194          break;
 195       case GLSL_TYPE_INT:
 196          data.i[i] = found->constant->value.i[rhs_channel];
 197          break;
 198       case GLSL_TYPE_UINT:
 199          data.u[i] = found->constant->value.u[rhs_channel];
 200          break;
 201       case GLSL_TYPE_BOOL:
 202          data.b[i] = found->constant->value.b[rhs_channel];
 203          break;
 204       default:
 205          assert(!"not reached");
 206          break;
 207       }
 208    }
 209
 210    *rvalue = new(ralloc_parent(deref)) ir_constant(type, &data);
 211    this->progress = true;
 212 }
 213
 214 ir_visitor_status
 215 ir_constant_propagation_visitor::visit_enter(ir_function_signature *ir)
 216 {
 217    /* Treat entry into a function signature as a completely separate
 218     * block.  Any instructions at global scope will be shuffled into
 219     * main() at link time, so they're irrelevant to us.
 220     */
 221    exec_list *orig_acp = this->acp;
 222    exec_list *orig_kills = this->kills;
 223    bool orig_killed_all = this->killed_all;
 224
 225    this->acp = new(mem_ctx) exec_list;
 226    this->kills = new(mem_ctx) exec_list;
 227    this->killed_all = false;
 228
 229    visit_list_elements(this, &ir->body);
 230
 231    this->kills = orig_kills;
 232    this->acp = orig_acp;
 233    this->killed_all = orig_killed_all;
 234
 235    return visit_continue_with_parent;
 236 }
 237
 238 ir_visitor_status
 239 ir_constant_propagation_visitor::visit_leave(ir_assignment *ir)
 240 {
 241    if (this->in_assignee)
 242       return visit_continue;
 243
 244    kill(ir->lhs->variable_referenced(), ir->write_mask);
 245
 246    add_constant(ir);
 247
 248    return visit_continue;
 249 }
 250
 251 ir_visitor_status
 252 ir_constant_propagation_visitor::visit_enter(ir_function *ir)
 253 {
 254    (void) ir;
 255    return visit_continue;
 256 }
 257
 258 ir_visitor_status
 259 ir_constant_propagation_visitor::visit_enter(ir_call *ir)
 260 {
 261    /* Do constant propagation on call parameters, but skip any out params */
 262    exec_list_iterator sig_param_iter = ir->get_callee()->parameters.iterator();
 263    foreach_iter(exec_list_iterator, iter, ir->actual_parameters) {
 264       ir_variable *sig_param = (ir_variable *)sig_param_iter.get();
 265       ir_rvalue *param = (ir_rvalue *)iter.get();
 266       if (sig_param->mode != ir_var_out && sig_param->mode != ir_var_inout) {
 267          ir_rvalue *new_param = param;
 268          handle_rvalue(&new_param);
 269          if (new_param != param)
 270             param->replace_with(new_param);
 271          else
 272             param->accept(this);
 273       }
 274       sig_param_iter.next();
 275    }
 276
 277    /* Since we're unlinked, we don't (necssarily) know the side effects of
 278     * this call.  So kill all copies.
 279     */
 280    acp->make_empty();
 281    this->killed_all = true;
 282
 283    return visit_continue_with_parent;
 284 }
 285
 286 void
 287 ir_constant_propagation_visitor::handle_if_block(exec_list *instructions)
 288 {
 289    exec_list *orig_acp = this->acp;
 290    exec_list *orig_kills = this->kills;
 291    bool orig_killed_all = this->killed_all;
 292
 293    this->acp = new(mem_ctx) exec_list;
 294    this->kills = new(mem_ctx) exec_list;
 295    this->killed_all = false;
 296
 297    /* Populate the initial acp with a constant of the original */
 298    foreach_iter(exec_list_iterator, iter, *orig_acp) {
 299       acp_entry *a = (acp_entry *)iter.get();
 300       this->acp->push_tail(new(this->mem_ctx) acp_entry(a));
 301    }
 302
 303    visit_list_elements(this, instructions);
 304
 305    if (this->killed_all) {
 306       orig_acp->make_empty();
 307    }
 308
 309    exec_list *new_kills = this->kills;
 310    this->kills = orig_kills;
 311    this->acp = orig_acp;
 312    this->killed_all = this->killed_all || orig_killed_all;
 313
 314    foreach_iter(exec_list_iterator, iter, *new_kills) {
 315       kill_entry *k = (kill_entry *)iter.get();
 316       kill(k->var, k->write_mask);
 317    }
 318 }
 319
 320 ir_visitor_status
 321 ir_constant_propagation_visitor::visit_enter(ir_if *ir)
 322 {
 323    ir->condition->accept(this);
 324    handle_rvalue(&ir->condition);
 325
 326    handle_if_block(&ir->then_instructions);
 327    handle_if_block(&ir->else_instructions);
 328
 329    /* handle_if_block() already descended into the children. */
 330    return visit_continue_with_parent;
 331 }
 332
 333 ir_visitor_status
 334 ir_constant_propagation_visitor::visit_enter(ir_loop *ir)
 335 {
 336    exec_list *orig_acp = this->acp;
 337    exec_list *orig_kills = this->kills;
 338    bool orig_killed_all = this->killed_all;
 339
 340    /* FINISHME: For now, the initial acp for loops is totally empty.
 341     * We could go through once, then go through again with the acp
 342     * cloned minus the killed entries after the first run through.
 343     */
 344    this->acp = new(mem_ctx) exec_list;
 345    this->kills = new(mem_ctx) exec_list;
 346    this->killed_all = false;
 347
 348    visit_list_elements(this, &ir->body_instructions);
 349
 350    if (this->killed_all) {
 351       orig_acp->make_empty();
 352    }
 353
 354    exec_list *new_kills = this->kills;
 355    this->kills = orig_kills;
 356    this->acp = orig_acp;
 357    this->killed_all = this->killed_all || orig_killed_all;
 358
 359    foreach_iter(exec_list_iterator, iter, *new_kills) {
 360       kill_entry *k = (kill_entry *)iter.get();
 361       kill(k->var, k->write_mask);
 362    }
 363
 364    /* already descended into the children. */
 365    return visit_continue_with_parent;
 366 }
 367
 368 void
 369 ir_constant_propagation_visitor::kill(ir_variable *var, unsigned write_mask)
 370 {
 371    assert(var != NULL);
 372
 373    /* We don't track non-vectors. */
 374    if (!var->type->is_vector() && !var->type->is_scalar())
 375       return;
 376
 377    /* Remove any entries currently in the ACP for this kill. */
 378    foreach_iter(exec_list_iterator, iter, *this->acp) {
 379       acp_entry *entry = (acp_entry *)iter.get();
 380
 381       if (entry->var == var) {
 382          entry->write_mask &= ~write_mask;
 383          if (entry->write_mask == 0)
 384             entry->remove();
 385       }
 386    }
 387
 388    /* Add this writemask of the variable to the list of killed
 389     * variables in this block.
 390     */
 391    foreach_iter(exec_list_iterator, iter, *this->kills) {
 392       kill_entry *entry = (kill_entry *)iter.get();
 393
 394       if (entry->var == var) {
 395          entry->write_mask |= write_mask;
 396          return;
 397       }
 398    }
 399    /* Not already in the list.  Make new entry. */
 400    this->kills->push_tail(new(this->mem_ctx) kill_entry(var, write_mask));
 401 }
 402
 403 /**
 404  * Adds an entry to the available constant list if it's a plain assignment
 405  * of a variable to a variable.
 406  */
 407 void
 408 ir_constant_propagation_visitor::add_constant(ir_assignment *ir)
 409 {
 410    acp_entry *entry;
 411
 412    if (ir->condition)
 413       return;
 414
 415    if (!ir->write_mask)
 416       return;
 417
 418    ir_dereference_variable *deref = ir->lhs->as_dereference_variable();
 419    ir_constant *constant = ir->rhs->as_constant();
 420
 421    if (!deref || !constant)
 422       return;
 423
 424    /* Only do constant propagation on vectors.  Constant matrices,
 425     * arrays, or structures would require more work elsewhere.
 426     */
 427    if (!deref->var->type->is_vector() && !deref->var->type->is_scalar())
 428       return;
 429
 430    entry = new(this->mem_ctx) acp_entry(deref->var, ir->write_mask, constant);
 431    this->acp->push_tail(entry);
 432 }
 433
 434 /**
 435  * Does a constant propagation pass on the code present in the instruction stream.
 436  */
 437 bool
 438 do_constant_propagation(exec_list *instructions)
 439 {
 440    ir_constant_propagation_visitor v;
 441
 442    visit_list_elements(&v, instructions);
 443
 444    return v.progress;
 445 }