src/compiler/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 "compiler/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       fprintf(stderr, "GRAFTING:\n");
 131       this->graft_assign->fprint(stderr);
 132       fprintf(stderr, "\n");
 133       fprintf(stderr, "TO:\n");
 134       (*rvalue)->fprint(stderr);
 135       fprintf(stderr, "\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          fprintf(stderr, "graft killed by: ");
 168          ir->fprint(stderr);
 169          fprintf(stderr, "\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    foreach_two_lists(formal_node, &ir->callee->parameters,
 208                      actual_node, &ir->actual_parameters) {
 209       ir_variable *sig_param = (ir_variable *) formal_node;
 210       ir_rvalue *ir = (ir_rvalue *) actual_node;
 211       ir_rvalue *new_ir = ir;
 212
 213       if (sig_param->data.mode != ir_var_function_in
 214           && sig_param->data.mode != ir_var_const_in) {
 215          if (check_graft(ir, sig_param) == visit_stop)
 216             return visit_stop;
 217          continue;
 218       }
 219
 220       if (do_graft(&new_ir)) {
 221          ir->replace_with(new_ir);
 222          return visit_stop;
 223       }
 224    }
 225
 226    if (ir->return_deref && check_graft(ir, ir->return_deref->var) == visit_stop)
 227       return visit_stop;
 228
 229    return visit_continue;
 230 }
 231
 232 ir_visitor_status
 233 ir_tree_grafting_visitor::visit_enter(ir_expression *ir)
 234 {
 235    for (unsigned int i = 0; i < ir->num_operands; i++) {
 236       if (do_graft(&ir->operands[i]))
 237          return visit_stop;
 238    }
 239
 240    return visit_continue;
 241 }
 242
 243 ir_visitor_status
 244 ir_tree_grafting_visitor::visit_enter(ir_if *ir)
 245 {
 246    if (do_graft(&ir->condition))
 247       return visit_stop;
 248
 249    /* Do not traverse into the body of the if-statement since that is a
 250     * different basic block.
 251     */
 252    return visit_continue_with_parent;
 253 }
 254
 255 ir_visitor_status
 256 ir_tree_grafting_visitor::visit_enter(ir_swizzle *ir)
 257 {
 258    if (do_graft(&ir->val))
 259       return visit_stop;
 260
 261    return visit_continue;
 262 }
 263
 264 ir_visitor_status
 265 ir_tree_grafting_visitor::visit_enter(ir_texture *ir)
 266 {
 267    if (do_graft(&ir->coordinate) ||
 268        do_graft(&ir->projector) ||
 269        do_graft(&ir->offset) ||
 270        do_graft(&ir->shadow_comparator))
 271          return visit_stop;
 272
 273    switch (ir->op) {
 274    case ir_tex:
 275    case ir_lod:
 276    case ir_query_levels:
 277    case ir_texture_samples:
 278    case ir_samples_identical:
 279       break;
 280    case ir_txb:
 281       if (do_graft(&ir->lod_info.bias))
 282          return visit_stop;
 283       break;
 284    case ir_txf:
 285    case ir_txl:
 286    case ir_txs:
 287       if (do_graft(&ir->lod_info.lod))
 288          return visit_stop;
 289       break;
 290    case ir_txf_ms:
 291       if (do_graft(&ir->lod_info.sample_index))
 292          return visit_stop;
 293       break;
 294    case ir_txd:
 295       if (do_graft(&ir->lod_info.grad.dPdx) ||
 296           do_graft(&ir->lod_info.grad.dPdy))
 297          return visit_stop;
 298       break;
 299    case ir_tg4:
 300       if (do_graft(&ir->lod_info.component))
 301          return visit_stop;
 302       break;
 303    }
 304
 305    return visit_continue;
 306 }
 307
 308 struct tree_grafting_info {
 309    ir_variable_refcount_visitor *refs;
 310    bool progress;
 311 };
 312
 313 static bool
 314 try_tree_grafting(ir_assignment *start,
 315                   ir_variable *lhs_var,
 316                   ir_instruction *bb_last)
 317 {
 318    ir_tree_grafting_visitor v(start, lhs_var);
 319
 320    if (debug) {
 321       fprintf(stderr, "trying to graft: ");
 322       lhs_var->fprint(stderr);
 323       fprintf(stderr, "\n");
 324    }
 325
 326    for (ir_instruction *ir = (ir_instruction *)start->next;
 327         ir != bb_last->next;
 328         ir = (ir_instruction *)ir->next) {
 329
 330       if (debug) {
 331          fprintf(stderr, "- ");
 332          ir->fprint(stderr);
 333          fprintf(stderr, "\n");
 334       }
 335
 336       ir_visitor_status s = ir->accept(&v);
 337       if (s == visit_stop)
 338          return v.progress;
 339    }
 340
 341    return false;
 342 }
 343
 344 static void
 345 tree_grafting_basic_block(ir_instruction *bb_first,
 346                           ir_instruction *bb_last,
 347                           void *data)
 348 {
 349    struct tree_grafting_info *info = (struct tree_grafting_info *)data;
 350    ir_instruction *ir, *next;
 351
 352    for (ir = bb_first, next = (ir_instruction *)ir->next;
 353         ir != bb_last->next;
 354         ir = next, next = (ir_instruction *)ir->next) {
 355       ir_assignment *assign = ir->as_assignment();
 356
 357       if (!assign)
 358          continue;
 359
 360       ir_variable *lhs_var = assign->whole_variable_written();
 361       if (!lhs_var)
 362          continue;
 363
 364       if (lhs_var->data.mode == ir_var_function_out ||
 365           lhs_var->data.mode == ir_var_function_inout ||
 366           lhs_var->data.mode == ir_var_shader_out ||
 367           lhs_var->data.mode == ir_var_shader_storage ||
 368           lhs_var->data.mode == ir_var_shader_shared)
 369          continue;
 370
 371       if (lhs_var->data.precise)
 372          continue;
 373
 374       /* Do not graft sampler and image variables. This is a workaround to
 375        * st/glsl_to_tgsi being unable to handle expression parameters to image
 376        * intrinsics.
 377        *
 378        * Note that if this is ever fixed, we still need to skip grafting when
 379        * any image layout qualifiers (including the image format) are set,
 380        * since we must not lose those.
 381        */
 382       if (lhs_var->type->is_sampler() || lhs_var->type->is_image())
 383          continue;
 384
 385       ir_variable_refcount_entry *entry = info->refs->get_variable_entry(lhs_var);
 386
 387       if (!entry->declaration ||
 388           entry->assigned_count != 1 ||
 389           entry->referenced_count != 2)
 390          continue;
 391
 392       /* Found a possibly graftable assignment.  Now, walk through the
 393        * rest of the BB seeing if the deref is here, and if nothing interfered with
 394        * pasting its expression's values in between.
 395        */
 396       info->progress |= try_tree_grafting(assign, lhs_var, bb_last);
 397    }
 398 }
 399
 400 } /* unnamed namespace */
 401
 402 /**
 403  * Does a copy propagation pass on the code present in the instruction stream.
 404  */
 405 bool
 406 do_tree_grafting(exec_list *instructions)
 407 {
 408    ir_variable_refcount_visitor refs;
 409    struct tree_grafting_info info;
 410
 411    info.progress = false;
 412    info.refs = &refs;
 413
 414    visit_list_elements(info.refs, instructions);
 415
 416    call_for_basic_blocks(instructions, tree_grafting_basic_block, &info);
 417
 418    return info.progress;
 419 }