src/glsl/opt_cse.cpp

   1 /*
   2  * Copyright © 2013 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_cse.cpp
  26  *
  27  * constant subexpression elimination at the GLSL IR level.
  28  *
  29  * Compare to brw_fs_cse.cpp for a more complete CSE implementation.  This one
  30  * is generic and handles texture operations, but it's rather simple currently
  31  * and doesn't support modification of variables in the available expressions
  32  * list, so it can't do variables other than uniforms or shader inputs.
  33  */
  34
  35 #include "ir.h"
  36 #include "ir_visitor.h"
  37 #include "ir_rvalue_visitor.h"
  38 #include "ir_basic_block.h"
  39 #include "ir_optimization.h"
  40 #include "ir_builder.h"
  41 #include "glsl_types.h"
  42
  43 using namespace ir_builder;
  44
  45 static bool debug = false;
  46
  47 namespace {
  48
  49 /**
  50  * This is the record of an available expression for common subexpression
  51  * elimination.
  52  */
  53 class ae_entry : public exec_node
  54 {
  55 public:
  56    ae_entry(ir_instruction *base_ir, ir_rvalue **val)
  57       : val(val), base_ir(base_ir)
  58    {
  59       assert(val);
  60       assert(*val);
  61       assert(base_ir);
  62
  63       var = NULL;
  64    }
  65
  66    /**
  67     * The pointer to the expression that we might be able to reuse
  68     *
  69     * Note the double pointer -- this is the place in the base_ir expression
  70     * tree that we would rewrite to move the expression out to a new variable
  71     * assignment.
  72     */
  73    ir_rvalue **val;
  74
  75    /**
  76     * Root instruction in the basic block where the expression appeared.
  77     *
  78     * This is used so that we can insert the new variable declaration into the
  79     * instruction stream (since *val is just somewhere in base_ir's expression
  80     * tree).
  81     */
  82    ir_instruction *base_ir;
  83
  84    /**
  85     * The variable that the expression has been stored in, if it's been CSEd
  86     * once already.
  87     */
  88    ir_variable *var;
  89 };
  90
  91 class cse_visitor : public ir_rvalue_visitor {
  92 public:
  93    cse_visitor(exec_list *validate_instructions)
  94       : validate_instructions(validate_instructions)
  95    {
  96       progress = false;
  97       mem_ctx = ralloc_context(NULL);
  98       this->ae = new(mem_ctx) exec_list;
  99    }
 100    ~cse_visitor()
 101    {
 102       ralloc_free(mem_ctx);
 103    }
 104
 105    virtual ir_visitor_status visit_enter(ir_function_signature *ir);
 106    virtual ir_visitor_status visit_enter(ir_loop *ir);
 107    virtual ir_visitor_status visit_enter(ir_if *ir);
 108    virtual ir_visitor_status visit_enter(ir_call *ir);
 109    virtual void handle_rvalue(ir_rvalue **rvalue);
 110
 111    bool progress;
 112
 113 private:
 114    void *mem_ctx;
 115
 116    ir_rvalue *try_cse(ir_rvalue *rvalue);
 117    void add_to_ae(ir_rvalue **rvalue);
 118
 119    /** List of ae_entry: The available expressions to reuse */
 120    exec_list *ae;
 121
 122    /**
 123     * The whole shader, so that we can validate_ir_tree in debug mode.
 124     *
 125     * This proved quite useful when trying to get the tree manipulation
 126     * right.
 127     */
 128    exec_list *validate_instructions;
 129 };
 130
 131 /**
 132  * Visitor to walk an expression tree to check that all variables referenced
 133  * are constants.
 134  */
 135 class is_cse_candidate_visitor : public ir_hierarchical_visitor
 136 {
 137 public:
 138
 139    is_cse_candidate_visitor()
 140       : ok(true)
 141    {
 142    }
 143
 144    virtual ir_visitor_status visit(ir_dereference_variable *ir);
 145
 146    bool ok;
 147 };
 148
 149
 150 class contains_rvalue_visitor : public ir_rvalue_visitor
 151 {
 152 public:
 153
 154    contains_rvalue_visitor(ir_rvalue *val)
 155       : val(val)
 156    {
 157       found = false;
 158    }
 159
 160    virtual void handle_rvalue(ir_rvalue **rvalue);
 161
 162    bool found;
 163
 164 private:
 165    ir_rvalue *val;
 166 };
 167
 168 } /* unnamed namespace */
 169
 170 static void
 171 dump_ae(exec_list *ae)
 172 {
 173    int i = 0;
 174
 175    printf("CSE: AE contents:\n");
 176    foreach_in_list(ae_entry, entry, ae) {
 177       printf("CSE:   AE %2d (%p): ", i, entry);
 178       (*entry->val)->print();
 179       printf("\n");
 180
 181       if (entry->var)
 182          printf("CSE:     in var %p:\n", entry->var);
 183
 184       i++;
 185    }
 186 }
 187
 188 ir_visitor_status
 189 is_cse_candidate_visitor::visit(ir_dereference_variable *ir)
 190 {
 191    /* Currently, since we don't handle kills of the ae based on variables
 192     * getting assigned, we can only handle constant variables.
 193     */
 194    if (ir->var->data.read_only) {
 195       return visit_continue;
 196    } else {
 197       ok = false;
 198       return visit_stop;
 199    }
 200 }
 201
 202 void
 203 contains_rvalue_visitor::handle_rvalue(ir_rvalue **rvalue)
 204 {
 205    if (*rvalue == val)
 206       found = true;
 207 }
 208
 209 static bool
 210 contains_rvalue(ir_rvalue *haystack, ir_rvalue *needle)
 211 {
 212    contains_rvalue_visitor v(needle);
 213    haystack->accept(&v);
 214    return v.found;
 215 }
 216
 217 static bool
 218 is_cse_candidate(ir_rvalue *ir)
 219 {
 220    /* Our temporary variable assignment generation isn't ready to handle
 221     * anything bigger than a vector.
 222     */
 223    if (!ir->type->is_vector() && !ir->type->is_scalar())
 224       return false;
 225
 226    /* Only handle expressions and textures currently.  We may want to extend
 227     * to variable-index array dereferences at some point.
 228     */
 229    switch (ir->ir_type) {
 230    case ir_type_expression:
 231    case ir_type_texture:
 232       break;
 233    default:
 234       return false;
 235    }
 236
 237    is_cse_candidate_visitor v;
 238
 239    ir->accept(&v);
 240
 241    return v.ok;
 242 }
 243
 244 /**
 245  * Tries to find and return a reference to a previous computation of a given
 246  * expression.
 247  *
 248  * Walk the list of available expressions checking if any of them match the
 249  * rvalue, and if so, move the previous copy of the expression to a temporary
 250  * and return a reference of the temporary.
 251  */
 252 ir_rvalue *
 253 cse_visitor::try_cse(ir_rvalue *rvalue)
 254 {
 255    foreach_in_list(ae_entry, entry, ae) {
 256       if (debug) {
 257          printf("Comparing to AE %p: ", entry);
 258          (*entry->val)->print();
 259          printf("\n");
 260       }
 261
 262       if (!rvalue->equals(*entry->val))
 263          continue;
 264
 265       if (debug) {
 266          printf("CSE: Replacing: ");
 267          (*entry->val)->print();
 268          printf("\n");
 269          printf("CSE:      with: ");
 270          rvalue->print();
 271          printf("\n");
 272       }
 273
 274       if (!entry->var) {
 275          ir_instruction *base_ir = entry->base_ir;
 276
 277          ir_variable *var = new(rvalue) ir_variable(rvalue->type,
 278                                                     "cse",
 279                                                     ir_var_temporary);
 280
 281          /* Write the previous expression result into a new variable. */
 282          base_ir->insert_before(var);
 283          ir_assignment *assignment = assign(var, *entry->val);
 284          base_ir->insert_before(assignment);
 285
 286          /* Replace the expression in the original tree with a deref of the
 287           * variable, but keep tracking the expression for further reuse.
 288           */
 289          *entry->val = new(rvalue) ir_dereference_variable(var);
 290          entry->val = &assignment->rhs;
 291
 292          entry->var = var;
 293
 294          /* Update the base_irs in the AE list.  We have to be sure that
 295           * they're correct -- expressions from our base_ir that weren't moved
 296           * need to stay in this base_ir (so that later consumption of them
 297           * puts new variables between our new variable and our base_ir), but
 298           * expressions from our base_ir that we *did* move need base_ir
 299           * updated so that any further elimination from inside gets its new
 300           * assignments put before our new assignment.
 301           */
 302          foreach_in_list(ae_entry, fixup_entry, ae) {
 303             if (contains_rvalue(assignment->rhs, *fixup_entry->val))
 304                fixup_entry->base_ir = assignment;
 305          }
 306
 307          if (debug)
 308             dump_ae(ae);
 309       }
 310
 311       /* Replace the expression in our current tree with the variable. */
 312       return new(rvalue) ir_dereference_variable(entry->var);
 313    }
 314
 315    return NULL;
 316 }
 317
 318 /** Add the rvalue to the list of available expressions for CSE. */
 319 void
 320 cse_visitor::add_to_ae(ir_rvalue **rvalue)
 321 {
 322    if (debug) {
 323       printf("CSE: Add to AE: ");
 324       (*rvalue)->print();
 325       printf("\n");
 326    }
 327
 328    ae->push_tail(new(mem_ctx) ae_entry(base_ir, rvalue));
 329
 330    if (debug)
 331       dump_ae(ae);
 332 }
 333
 334 void
 335 cse_visitor::handle_rvalue(ir_rvalue **rvalue)
 336 {
 337    if (!*rvalue)
 338       return;
 339
 340    if (debug) {
 341       printf("CSE: handle_rvalue ");
 342       (*rvalue)->print();
 343       printf("\n");
 344    }
 345
 346    if (!is_cse_candidate(*rvalue))
 347       return;
 348
 349    ir_rvalue *new_rvalue = try_cse(*rvalue);
 350    if (new_rvalue) {
 351       *rvalue = new_rvalue;
 352       progress = true;
 353
 354       if (debug)
 355          validate_ir_tree(validate_instructions);
 356    } else {
 357       add_to_ae(rvalue);
 358    }
 359 }
 360
 361 ir_visitor_status
 362 cse_visitor::visit_enter(ir_if *ir)
 363 {
 364    handle_rvalue(&ir->condition);
 365
 366    ae->make_empty();
 367    visit_list_elements(this, &ir->then_instructions);
 368
 369    ae->make_empty();
 370    visit_list_elements(this, &ir->else_instructions);
 371
 372    ae->make_empty();
 373    return visit_continue_with_parent;
 374 }
 375
 376 ir_visitor_status
 377 cse_visitor::visit_enter(ir_function_signature *ir)
 378 {
 379    ae->make_empty();
 380    visit_list_elements(this, &ir->body);
 381
 382    ae->make_empty();
 383    return visit_continue_with_parent;
 384 }
 385
 386 ir_visitor_status
 387 cse_visitor::visit_enter(ir_loop *ir)
 388 {
 389    ae->make_empty();
 390    visit_list_elements(this, &ir->body_instructions);
 391
 392    ae->make_empty();
 393    return visit_continue_with_parent;
 394 }
 395
 396 ir_visitor_status
 397 cse_visitor::visit_enter(ir_call *)
 398 {
 399    /* Because call is an exec_list of ir_rvalues, handle_rvalue gets passed a
 400     * pointer to the (ir_rvalue *) on the stack.  Since we save those pointers
 401     * in the AE list, we can't let handle_rvalue get called.
 402     */
 403    return visit_continue_with_parent;
 404 }
 405
 406 /**
 407  * Does a (uniform-value) constant subexpression elimination pass on the code
 408  * present in the instruction stream.
 409  */
 410 bool
 411 do_cse(exec_list *instructions)
 412 {
 413    cse_visitor v(instructions);
 414
 415    visit_list_elements(&v, instructions);
 416
 417    return v.progress;
 418 }