src/glsl/opt_tree_grafting.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 opt_tree_grafting.cpp
  26  *
  27  * Takes assignments to variables that are dereferenced only once and
  28  * pastes the RHS expression into where the variable is dereferenced.
  29  *
  30  * In the process of various operations like function inlining and
  31  * tertiary op handling, we'll end up with our expression trees having
  32  * been chopped up into a series of assignments of short expressions
  33  * to temps.  Other passes like ir_algebraic.cpp would prefer to see
  34  * the deepest expression trees they can to try to optimize them.
  35  *
  36  * This is a lot like copy propagaton.  In comparison, copy
  37  * propagation only acts on plain copies, not arbitrary expressions on
  38  * the RHS.  Generally, we wouldn't want to go pasting some
  39  * complicated expression everywhere it got used, though, so we don't
  40  * handle expressions in that pass.
  41  *
  42  * The hard part is making sure we don't move an expression across
  43  * some other assignments that would change the value of the
  44  * expression.  So we split this into two passes: First, find the
  45  * variables in our scope which are written to once and read once, and
  46  * then go through basic blocks seeing if we find an opportunity to
  47  * move those expressions safely.
  48  */
  49
  50 #include "ir.h"
  51 #include "ir_visitor.h"
  52 #include "ir_variable_refcount.h"
  53 #include "ir_basic_block.h"
  54 #include "ir_optimization.h"
  55 #include "glsl_types.h"
  56
  57 static bool debug = false;
  58
  59 class ir_tree_grafting_visitor : public ir_hierarchical_visitor {
  60 public:
  61    ir_tree_grafting_visitor(ir_assignment *graft_assign,
  62                             ir_variable *graft_var)
  63    {
  64       this->progress = false;
  65       this->graft_assign = graft_assign;
  66       this->graft_var = graft_var;
  67    }
  68
  69    virtual ir_visitor_status visit_leave(class ir_assignment *);
  70    virtual ir_visitor_status visit_enter(class ir_call *);
  71    virtual ir_visitor_status visit_enter(class ir_expression *);
  72    virtual ir_visitor_status visit_enter(class ir_function *);
  73    virtual ir_visitor_status visit_enter(class ir_function_signature *);
  74    virtual ir_visitor_status visit_enter(class ir_if *);
  75    virtual ir_visitor_status visit_enter(class ir_loop *);
  76    virtual ir_visitor_status visit_enter(class ir_swizzle *);
  77    virtual ir_visitor_status visit_enter(class ir_texture *);
  78
  79    ir_visitor_status check_graft(ir_instruction *ir, ir_variable *var);
  80
  81    bool do_graft(ir_rvalue **rvalue);
  82
  83    bool progress;
  84    ir_variable *graft_var;
  85    ir_assignment *graft_assign;
  86 };
  87
  88 struct find_deref_info {
  89    ir_variable *var;
  90    bool found;
  91 };
  92
  93 void
  94 dereferences_variable_callback(ir_instruction *ir, void *data)
  95 {
  96    struct find_deref_info *info = (struct find_deref_info *)data;
  97    ir_dereference_variable *deref = ir->as_dereference_variable();
  98
  99    if (deref && deref->var == info->var)
 100       info->found = true;
 101 }
 102
 103 static bool
 104 dereferences_variable(ir_instruction *ir, ir_variable *var)
 105 {
 106    struct find_deref_info info;
 107
 108    info.var = var;
 109    info.found = false;
 110
 111    visit_tree(ir, dereferences_variable_callback, &info);
 112
 113    return info.found;
 114 }
 115
 116 bool
 117 ir_tree_grafting_visitor::do_graft(ir_rvalue **rvalue)
 118 {
 119    if (!*rvalue)
 120       return false;
 121
 122    ir_dereference_variable *deref = (*rvalue)->as_dereference_variable();
 123
 124    if (!deref || deref->var != this->graft_var)
 125       return false;
 126
 127    if (debug) {
 128       printf("GRAFTING:\n");
 129       this->graft_assign->print();
 130       printf("\n");
 131       printf("TO:\n");
 132       (*rvalue)->print();
 133       printf("\n");
 134    }
 135
 136    this->graft_assign->remove();
 137    *rvalue = this->graft_assign->rhs;
 138
 139    this->progress = true;
 140    return true;
 141 }
 142
 143 ir_visitor_status
 144 ir_tree_grafting_visitor::visit_enter(ir_loop *ir)
 145 {
 146    (void)ir;
 147    /* Do not traverse into the body of the loop since that is a
 148     * different basic block.
 149     */
 150    return visit_stop;
 151 }
 152
 153 /**
 154  * Check if we can continue grafting after writing to a variable.  If the
 155  * expression we're trying to graft references the variable, we must stop.
 156  *
 157  * \param ir   An instruction that writes to a variable.
 158  * \param var  The variable being updated.
 159  */
 160 ir_visitor_status
 161 ir_tree_grafting_visitor::check_graft(ir_instruction *ir, ir_variable *var)
 162 {
 163    if (dereferences_variable(this->graft_assign->rhs, var)) {
 164       if (debug) {
 165          printf("graft killed by: ");
 166          ir->print();
 167          printf("\n");
 168       }
 169       return visit_stop;
 170    }
 171
 172    return visit_continue;
 173 }
 174
 175 ir_visitor_status
 176 ir_tree_grafting_visitor::visit_leave(ir_assignment *ir)
 177 {
 178    if (do_graft(&ir->rhs) ||
 179        do_graft(&ir->condition))
 180       return visit_stop;
 181
 182    /* If this assignment updates a variable used in the assignment
 183     * we're trying to graft, then we're done.
 184     */
 185    return check_graft(ir, ir->lhs->variable_referenced());
 186 }
 187
 188 ir_visitor_status
 189 ir_tree_grafting_visitor::visit_enter(ir_function *ir)
 190 {
 191    (void) ir;
 192    return visit_continue_with_parent;
 193 }
 194
 195 ir_visitor_status
 196 ir_tree_grafting_visitor::visit_enter(ir_function_signature *ir)
 197 {
 198    (void)ir;
 199    return visit_continue_with_parent;
 200 }
 201
 202 ir_visitor_status
 203 ir_tree_grafting_visitor::visit_enter(ir_call *ir)
 204 {
 205    exec_list_iterator sig_iter = ir->get_callee()->parameters.iterator();
 206    /* Reminder: iterating ir_call iterates its parameters. */
 207    foreach_iter(exec_list_iterator, iter, *ir) {
 208       ir_variable *sig_param = (ir_variable *)sig_iter.get();
 209       ir_rvalue *ir = (ir_rvalue *)iter.get();
 210       ir_rvalue *new_ir = ir;
 211
 212       if (sig_param->mode != ir_var_in && sig_param->mode != ir_var_const_in) {
 213          if (check_graft(ir, sig_param) == visit_stop)
 214             return visit_stop;
 215          continue;
 216       }
 217
 218       if (do_graft(&new_ir)) {
 219          ir->replace_with(new_ir);
 220          return visit_stop;
 221       }
 222       sig_iter.next();
 223    }
 224
 225    return visit_continue;
 226 }
 227
 228 ir_visitor_status
 229 ir_tree_grafting_visitor::visit_enter(ir_expression *ir)
 230 {
 231    for (unsigned int i = 0; i < ir->get_num_operands(); i++) {
 232       if (do_graft(&ir->operands[i]))
 233          return visit_stop;
 234    }
 235
 236    return visit_continue;
 237 }
 238
 239 ir_visitor_status
 240 ir_tree_grafting_visitor::visit_enter(ir_if *ir)
 241 {
 242    if (do_graft(&ir->condition))
 243       return visit_stop;
 244
 245    /* Do not traverse into the body of the if-statement since that is a
 246     * different basic block.
 247     */
 248    return visit_continue_with_parent;
 249 }
 250
 251 ir_visitor_status
 252 ir_tree_grafting_visitor::visit_enter(ir_swizzle *ir)
 253 {
 254    if (do_graft(&ir->val))
 255       return visit_stop;
 256
 257    return visit_continue;
 258 }
 259
 260 ir_visitor_status
 261 ir_tree_grafting_visitor::visit_enter(ir_texture *ir)
 262 {
 263    if (do_graft(&ir->coordinate) ||
 264        do_graft(&ir->projector) ||
 265        do_graft(&ir->offset) ||
 266        do_graft(&ir->shadow_comparitor))
 267          return visit_stop;
 268
 269    switch (ir->op) {
 270    case ir_tex:
 271       break;
 272    case ir_txb:
 273       if (do_graft(&ir->lod_info.bias))
 274          return visit_stop;
 275       break;
 276    case ir_txf:
 277    case ir_txl:
 278    case ir_txs:
 279       if (do_graft(&ir->lod_info.lod))
 280          return visit_stop;
 281       break;
 282    case ir_txd:
 283       if (do_graft(&ir->lod_info.grad.dPdx) ||
 284           do_graft(&ir->lod_info.grad.dPdy))
 285          return visit_stop;
 286       break;
 287    }
 288
 289    return visit_continue;
 290 }
 291
 292 struct tree_grafting_info {
 293    ir_variable_refcount_visitor *refs;
 294    bool progress;
 295 };
 296
 297 static bool
 298 try_tree_grafting(ir_assignment *start,
 299                   ir_variable *lhs_var,
 300                   ir_instruction *bb_last)
 301 {
 302    ir_tree_grafting_visitor v(start, lhs_var);
 303
 304    if (debug) {
 305       printf("trying to graft: ");
 306       lhs_var->print();
 307       printf("\n");
 308    }
 309
 310    for (ir_instruction *ir = (ir_instruction *)start->next;
 311         ir != bb_last->next;
 312         ir = (ir_instruction *)ir->next) {
 313
 314       if (debug) {
 315          printf("- ");
 316          ir->print();
 317          printf("\n");
 318       }
 319
 320       ir_visitor_status s = ir->accept(&v);
 321       if (s == visit_stop)
 322          return v.progress;
 323    }
 324
 325    return false;
 326 }
 327
 328 static void
 329 tree_grafting_basic_block(ir_instruction *bb_first,
 330                           ir_instruction *bb_last,
 331                           void *data)
 332 {
 333    struct tree_grafting_info *info = (struct tree_grafting_info *)data;
 334    ir_instruction *ir, *next;
 335
 336    for (ir = bb_first, next = (ir_instruction *)ir->next;
 337         ir != bb_last->next;
 338         ir = next, next = (ir_instruction *)ir->next) {
 339       ir_assignment *assign = ir->as_assignment();
 340
 341       if (!assign)
 342          continue;
 343
 344       ir_variable *lhs_var = assign->whole_variable_written();
 345       if (!lhs_var)
 346          continue;
 347
 348       if (lhs_var->mode == ir_var_out ||
 349           lhs_var->mode == ir_var_inout)
 350          continue;
 351
 352       variable_entry *entry = info->refs->get_variable_entry(lhs_var);
 353
 354       if (!entry->declaration ||
 355           entry->assigned_count != 1 ||
 356           entry->referenced_count != 2)
 357          continue;
 358
 359       assert(assign == entry->assign);
 360
 361       /* Found a possibly graftable assignment.  Now, walk through the
 362        * rest of the BB seeing if the deref is here, and if nothing interfered with
 363        * pasting its expression's values in between.
 364        */
 365       info->progress |= try_tree_grafting(assign, lhs_var, bb_last);
 366    }
 367 }
 368
 369 /**
 370  * Does a copy propagation pass on the code present in the instruction stream.
 371  */
 372 bool
 373 do_tree_grafting(exec_list *instructions)
 374 {
 375    ir_variable_refcount_visitor refs;
 376    struct tree_grafting_info info;
 377
 378    info.progress = false;
 379    info.refs = &refs;
 380
 381    visit_list_elements(info.refs, instructions);
 382
 383    call_for_basic_blocks(instructions, tree_grafting_basic_block, &info);
 384
 385    return info.progress;
 386 }