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