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 namespace {
  58
  59 static bool debug = false;
  60
  61 class ir_tree_grafting_visitor : public ir_hierarchical_visitor {
  62 public:
  63    ir_tree_grafting_visitor(ir_assignment *graft_assign,
  64                             ir_variable *graft_var)
  65    {
  66       this->progress = false;
  67       this->graft_assign = graft_assign;
  68       this->graft_var = graft_var;
  69    }
  70
  71    virtual ir_visitor_status visit_leave(class ir_assignment *);
  72    virtual ir_visitor_status visit_enter(class ir_call *);
  73    virtual ir_visitor_status visit_enter(class ir_expression *);
  74    virtual ir_visitor_status visit_enter(class ir_function *);
  75    virtual ir_visitor_status visit_enter(class ir_function_signature *);
  76    virtual ir_visitor_status visit_enter(class ir_if *);
  77    virtual ir_visitor_status visit_enter(class ir_loop *);
  78    virtual ir_visitor_status visit_enter(class ir_swizzle *);
  79    virtual ir_visitor_status visit_enter(class ir_texture *);
  80
  81    ir_visitor_status check_graft(ir_instruction *ir, ir_variable *var);
  82
  83    bool do_graft(ir_rvalue **rvalue);
  84
  85    bool progress;
  86    ir_variable *graft_var;
  87    ir_assignment *graft_assign;
  88 };
  89
  90 struct find_deref_info {
  91    ir_variable *var;
  92    bool found;
  93 };
  94
  95 void
  96 dereferences_variable_callback(ir_instruction *ir, void *data)
  97 {
  98    struct find_deref_info *info = (struct find_deref_info *)data;
  99    ir_dereference_variable *deref = ir->as_dereference_variable();
 100
 101    if (deref && deref->var == info->var)
 102       info->found = true;
 103 }
 104
 105 static bool
 106 dereferences_variable(ir_instruction *ir, ir_variable *var)
 107 {
 108    struct find_deref_info info;
 109
 110    info.var = var;
 111    info.found = false;
 112
 113    visit_tree(ir, dereferences_variable_callback, &info);
 114
 115    return info.found;
 116 }
 117
 118 bool
 119 ir_tree_grafting_visitor::do_graft(ir_rvalue **rvalue)
 120 {
 121    if (!*rvalue)
 122       return false;
 123
 124    ir_dereference_variable *deref = (*rvalue)->as_dereference_variable();
 125
 126    if (!deref || deref->var != this->graft_var)
 127       return false;
 128
 129    if (debug) {
 130       printf("GRAFTING:\n");
 131       this->graft_assign->print();
 132       printf("\n");
 133       printf("TO:\n");
 134       (*rvalue)->print();
 135       printf("\n");
 136    }
 137
 138    this->graft_assign->remove();
 139    *rvalue = this->graft_assign->rhs;
 140
 141    this->progress = true;
 142    return true;
 143 }
 144
 145 ir_visitor_status
 146 ir_tree_grafting_visitor::visit_enter(ir_loop *ir)
 147 {
 148    (void)ir;
 149    /* Do not traverse into the body of the loop since that is a
 150     * different basic block.
 151     */
 152    return visit_stop;
 153 }
 154
 155 /**
 156  * Check if we can continue grafting after writing to a variable.  If the
 157  * expression we're trying to graft references the variable, we must stop.
 158  *
 159  * \param ir   An instruction that writes to a variable.
 160  * \param var  The variable being updated.
 161  */
 162 ir_visitor_status
 163 ir_tree_grafting_visitor::check_graft(ir_instruction *ir, ir_variable *var)
 164 {
 165    if (dereferences_variable(this->graft_assign->rhs, var)) {
 166       if (debug) {
 167          printf("graft killed by: ");
 168          ir->print();
 169          printf("\n");
 170       }
 171       return visit_stop;
 172    }
 173
 174    return visit_continue;
 175 }
 176
 177 ir_visitor_status
 178 ir_tree_grafting_visitor::visit_leave(ir_assignment *ir)
 179 {
 180    if (do_graft(&ir->rhs) ||
 181        do_graft(&ir->condition))
 182       return visit_stop;
 183
 184    /* If this assignment updates a variable used in the assignment
 185     * we're trying to graft, then we're done.
 186     */
 187    return check_graft(ir, ir->lhs->variable_referenced());
 188 }
 189
 190 ir_visitor_status
 191 ir_tree_grafting_visitor::visit_enter(ir_function *ir)
 192 {
 193    (void) ir;
 194    return visit_continue_with_parent;
 195 }
 196
 197 ir_visitor_status
 198 ir_tree_grafting_visitor::visit_enter(ir_function_signature *ir)
 199 {
 200    (void)ir;
 201    return visit_continue_with_parent;
 202 }
 203
 204 ir_visitor_status
 205 ir_tree_grafting_visitor::visit_enter(ir_call *ir)
 206 {
 207    exec_list_iterator sig_iter = ir->callee->parameters.iterator();
 208    /* Reminder: iterating ir_call iterates its parameters. */
 209    foreach_iter(exec_list_iterator, iter, *ir) {
 210       ir_variable *sig_param = (ir_variable *)sig_iter.get();
 211       ir_rvalue *ir = (ir_rvalue *)iter.get();
 212       ir_rvalue *new_ir = ir;
 213
 214       if (sig_param->mode != ir_var_function_in
 215           && sig_param->mode != ir_var_const_in) {
 216          if (check_graft(ir, sig_param) == visit_stop)
 217             return visit_stop;
 218          continue;
 219       }
 220
 221       if (do_graft(&new_ir)) {
 222          ir->replace_with(new_ir);
 223          return visit_stop;
 224       }
 225       sig_iter.next();
 226    }
 227
 228    if (ir->return_deref && check_graft(ir, ir->return_deref->var) == visit_stop)
 229       return visit_stop;
 230
 231    return visit_continue;
 232 }
 233
 234 ir_visitor_status
 235 ir_tree_grafting_visitor::visit_enter(ir_expression *ir)
 236 {
 237    for (unsigned int i = 0; i < ir->get_num_operands(); i++) {
 238       if (do_graft(&ir->operands[i]))
 239          return visit_stop;
 240    }
 241
 242    return visit_continue;
 243 }
 244
 245 ir_visitor_status
 246 ir_tree_grafting_visitor::visit_enter(ir_if *ir)
 247 {
 248    if (do_graft(&ir->condition))
 249       return visit_stop;
 250
 251    /* Do not traverse into the body of the if-statement since that is a
 252     * different basic block.
 253     */
 254    return visit_continue_with_parent;
 255 }
 256
 257 ir_visitor_status
 258 ir_tree_grafting_visitor::visit_enter(ir_swizzle *ir)
 259 {
 260    if (do_graft(&ir->val))
 261       return visit_stop;
 262
 263    return visit_continue;
 264 }
 265
 266 ir_visitor_status
 267 ir_tree_grafting_visitor::visit_enter(ir_texture *ir)
 268 {
 269    if (do_graft(&ir->coordinate) ||
 270        do_graft(&ir->projector) ||
 271        do_graft(&ir->offset) ||
 272        do_graft(&ir->shadow_comparitor))
 273          return visit_stop;
 274
 275    switch (ir->op) {
 276    case ir_tex:
 277    case ir_lod:
 278       break;
 279    case ir_txb:
 280       if (do_graft(&ir->lod_info.bias))
 281          return visit_stop;
 282       break;
 283    case ir_txf:
 284    case ir_txl:
 285    case ir_txs:
 286       if (do_graft(&ir->lod_info.lod))
 287          return visit_stop;
 288       break;
 289    case ir_txf_ms:
 290       if (do_graft(&ir->lod_info.sample_index))
 291          return visit_stop;
 292       break;
 293    case ir_txd:
 294       if (do_graft(&ir->lod_info.grad.dPdx) ||
 295           do_graft(&ir->lod_info.grad.dPdy))
 296          return visit_stop;
 297       break;
 298    }
 299
 300    return visit_continue;
 301 }
 302
 303 struct tree_grafting_info {
 304    ir_variable_refcount_visitor *refs;
 305    bool progress;
 306 };
 307
 308 static bool
 309 try_tree_grafting(ir_assignment *start,
 310                   ir_variable *lhs_var,
 311                   ir_instruction *bb_last)
 312 {
 313    ir_tree_grafting_visitor v(start, lhs_var);
 314
 315    if (debug) {
 316       printf("trying to graft: ");
 317       lhs_var->print();
 318       printf("\n");
 319    }
 320
 321    for (ir_instruction *ir = (ir_instruction *)start->next;
 322         ir != bb_last->next;
 323         ir = (ir_instruction *)ir->next) {
 324
 325       if (debug) {
 326          printf("- ");
 327          ir->print();
 328          printf("\n");
 329       }
 330
 331       ir_visitor_status s = ir->accept(&v);
 332       if (s == visit_stop)
 333          return v.progress;
 334    }
 335
 336    return false;
 337 }
 338
 339 static void
 340 tree_grafting_basic_block(ir_instruction *bb_first,
 341                           ir_instruction *bb_last,
 342                           void *data)
 343 {
 344    struct tree_grafting_info *info = (struct tree_grafting_info *)data;
 345    ir_instruction *ir, *next;
 346
 347    for (ir = bb_first, next = (ir_instruction *)ir->next;
 348         ir != bb_last->next;
 349         ir = next, next = (ir_instruction *)ir->next) {
 350       ir_assignment *assign = ir->as_assignment();
 351
 352       if (!assign)
 353          continue;
 354
 355       ir_variable *lhs_var = assign->whole_variable_written();
 356       if (!lhs_var)
 357          continue;
 358
 359       if (lhs_var->mode == ir_var_function_out ||
 360           lhs_var->mode == ir_var_function_inout ||
 361           lhs_var->mode == ir_var_shader_out)
 362          continue;
 363
 364       ir_variable_refcount_entry *entry = info->refs->get_variable_entry(lhs_var);
 365
 366       if (!entry->declaration ||
 367           entry->assigned_count != 1 ||
 368           entry->referenced_count != 2)
 369          continue;
 370
 371       assert(assign == entry->assign);
 372
 373       /* Found a possibly graftable assignment.  Now, walk through the
 374        * rest of the BB seeing if the deref is here, and if nothing interfered with
 375        * pasting its expression's values in between.
 376        */
 377       info->progress |= try_tree_grafting(assign, lhs_var, bb_last);
 378    }
 379 }
 380
 381 } /* unnamed namespace */
 382
 383 /**
 384  * Does a copy propagation pass on the code present in the instruction stream.
 385  */
 386 bool
 387 do_tree_grafting(exec_list *instructions)
 388 {
 389    ir_variable_refcount_visitor refs;
 390    struct tree_grafting_info info;
 391
 392    info.progress = false;
 393    info.refs = &refs;
 394
 395    visit_list_elements(info.refs, instructions);
 396
 397    call_for_basic_blocks(instructions, tree_grafting_basic_block, &info);
 398
 399    return info.progress;
 400 }