src/glsl/lower_variable_index_to_cond_assign.cpp

   1 /*
   2  * Copyright © 2010 Luca Barbieri
   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 lower_variable_index_to_cond_assign.cpp
  26  *
  27  * Turns non-constant indexing into array types to a series of
  28  * conditional moves of each element into a temporary.
  29  *
  30  * Pre-DX10 GPUs often don't have a native way to do this operation,
  31  * and this works around that.
  32  *
  33  * The lowering process proceeds as follows.  Each non-constant index
  34  * found in an r-value is converted to a canonical form \c array[i].  Each
  35  * element of the array is conditionally assigned to a temporary by comparing
  36  * \c i to a constant index.  This is done by cloning the canonical form and
  37  * replacing all occurances of \c i with a constant.  Each remaining occurance
  38  * of the canonical form in the IR is replaced with a dereference of the
  39  * temporary variable.
  40  *
  41  * L-values with non-constant indices are handled similarly.  In this case,
  42  * the RHS of the assignment is assigned to a temporary.  The non-constant
  43  * index is replace with the canonical form (just like for r-values).  The
  44  * temporary is conditionally assigned to each element of the canonical form
  45  * by comparing \c i with each index.  The same clone-and-replace scheme is
  46  * used.
  47  */
  48
  49 #include "ir.h"
  50 #include "ir_rvalue_visitor.h"
  51 #include "ir_optimization.h"
  52 #include "glsl_types.h"
  53 #include "main/macros.h"
  54
  55 static inline bool
  56 is_array_or_matrix(const ir_instruction *ir)
  57 {
  58    return (ir->type->is_array() || ir->type->is_matrix());
  59 }
  60
  61 /**
  62  * Replace a dereference of a variable with a specified r-value
  63  *
  64  * Each time a dereference of the specified value is replaced, the r-value
  65  * tree is cloned.
  66  */
  67 class deref_replacer : public ir_rvalue_visitor {
  68 public:
  69    deref_replacer(const ir_variable *variable_to_replace, ir_rvalue *value)
  70       : variable_to_replace(variable_to_replace), value(value),
  71         progress(false)
  72    {
  73       assert(this->variable_to_replace != NULL);
  74       assert(this->value != NULL);
  75    }
  76
  77    virtual void handle_rvalue(ir_rvalue **rvalue)
  78    {
  79       ir_dereference_variable *const dv = (*rvalue)->as_dereference_variable();
  80
  81       if ((dv != NULL) && (dv->var == this->variable_to_replace)) {
  82          this->progress = true;
  83          *rvalue = this->value->clone(ralloc_parent(*rvalue), NULL);
  84       }
  85    }
  86
  87    const ir_variable *variable_to_replace;
  88    ir_rvalue *value;
  89    bool progress;
  90 };
  91
  92 /**
  93  * Find a variable index dereference of an array in an rvalue tree
  94  */
  95 class find_variable_index : public ir_hierarchical_visitor {
  96 public:
  97    find_variable_index()
  98       : deref(NULL)
  99    {
 100       /* empty */
 101    }
 102
 103    virtual ir_visitor_status visit_enter(ir_dereference_array *ir)
 104    {
 105       if (is_array_or_matrix(ir->array)
 106           && (ir->array_index->as_constant() == NULL)) {
 107          this->deref = ir;
 108          return visit_stop;
 109       }
 110
 111       return visit_continue;
 112    }
 113
 114    /**
 115     * First array dereference found in the tree that has a non-constant index.
 116     */
 117    ir_dereference_array *deref;
 118 };
 119
 120 struct assignment_generator
 121 {
 122    ir_instruction* base_ir;
 123    ir_dereference *rvalue;
 124    ir_variable *old_index;
 125    bool is_write;
 126    unsigned int write_mask;
 127    ir_variable* var;
 128
 129    assignment_generator()
 130    {
 131    }
 132
 133    void generate(unsigned i, ir_rvalue* condition, exec_list *list) const
 134    {
 135       /* Just clone the rest of the deref chain when trying to get at the
 136        * underlying variable.
 137        */
 138       void *mem_ctx = ralloc_parent(base_ir);
 139
 140       /* Clone the old r-value in its entirety.  Then replace any occurances of
 141        * the old variable index with the new constant index.
 142        */
 143       ir_dereference *element = this->rvalue->clone(mem_ctx, NULL);
 144       ir_constant *const index = new(mem_ctx) ir_constant(i);
 145       deref_replacer r(this->old_index, index);
 146       element->accept(&r);
 147       assert(r.progress);
 148
 149       /* Generate a conditional assignment to (or from) the constant indexed
 150        * array dereference.
 151        */
 152       ir_rvalue *variable = new(mem_ctx) ir_dereference_variable(this->var);
 153       ir_assignment *const assignment = (is_write)
 154          ? new(mem_ctx) ir_assignment(element, variable, condition, write_mask)
 155          : new(mem_ctx) ir_assignment(variable, element, condition);
 156
 157       list->push_tail(assignment);
 158    }
 159 };
 160
 161 struct switch_generator
 162 {
 163    /* make TFunction a template parameter if you need to use other generators */
 164    typedef assignment_generator TFunction;
 165    const TFunction& generator;
 166
 167    ir_variable* index;
 168    unsigned linear_sequence_max_length;
 169    unsigned condition_components;
 170
 171    void *mem_ctx;
 172
 173    switch_generator(const TFunction& generator, ir_variable *index,
 174                     unsigned linear_sequence_max_length,
 175                     unsigned condition_components)
 176       : generator(generator), index(index),
 177         linear_sequence_max_length(linear_sequence_max_length),
 178         condition_components(condition_components)
 179    {
 180       this->mem_ctx = ralloc_parent(index);
 181    }
 182
 183    void linear_sequence(unsigned begin, unsigned end, exec_list *list)
 184    {
 185       if (begin == end)
 186          return;
 187
 188       /* If the array access is a read, read the first element of this subregion
 189        * unconditionally.  The remaining tests will possibly overwrite this
 190        * value with one of the other array elements.
 191        *
 192        * This optimization cannot be done for writes because it will cause the
 193        * first element of the subregion to be written possibly *in addition* to
 194        * one of the other elements.
 195        */
 196       unsigned first;
 197       if (!this->generator.is_write) {
 198          this->generator.generate(begin, 0, list);
 199          first = begin + 1;
 200       } else {
 201          first = begin;
 202       }
 203
 204       for (unsigned i = first; i < end; i += 4) {
 205          const unsigned comps = MIN2(condition_components, end - i);
 206
 207          ir_rvalue *broadcast_index =
 208             new(this->mem_ctx) ir_dereference_variable(index);
 209
 210          if (comps) {
 211             const ir_swizzle_mask m = { 0, 0, 0, 0, comps, false };
 212             broadcast_index = new(this->mem_ctx) ir_swizzle(broadcast_index, m);
 213          }
 214
 215          /* Compare the desired index value with the next block of four indices.
 216           */
 217          ir_constant_data test_indices_data;
 218          memset(&test_indices_data, 0, sizeof(test_indices_data));
 219          test_indices_data.i[0] = i;
 220          test_indices_data.i[1] = i + 1;
 221          test_indices_data.i[2] = i + 2;
 222          test_indices_data.i[3] = i + 3;
 223          ir_constant *const test_indices =
 224             new(this->mem_ctx) ir_constant(broadcast_index->type,
 225                                            &test_indices_data);
 226
 227          ir_rvalue *const condition_val =
 228             new(this->mem_ctx) ir_expression(ir_binop_equal,
 229                                              &glsl_type::bool_type[comps - 1],
 230                                              broadcast_index,
 231                                              test_indices);
 232
 233          ir_variable *const condition =
 234             new(this->mem_ctx) ir_variable(condition_val->type,
 235                                            "dereference_array_condition",
 236                                            ir_var_temporary);
 237          list->push_tail(condition);
 238
 239          ir_rvalue *const cond_deref =
 240             new(this->mem_ctx) ir_dereference_variable(condition);
 241          list->push_tail(new(this->mem_ctx) ir_assignment(cond_deref,
 242                                                           condition_val, 0));
 243
 244          if (comps == 1) {
 245             ir_rvalue *const cond_deref =
 246                new(this->mem_ctx) ir_dereference_variable(condition);
 247
 248             this->generator.generate(i, cond_deref, list);
 249          } else {
 250             for (unsigned j = 0; j < comps; j++) {
 251                ir_rvalue *const cond_deref =
 252                   new(this->mem_ctx) ir_dereference_variable(condition);
 253                ir_rvalue *const cond_swiz =
 254                   new(this->mem_ctx) ir_swizzle(cond_deref, j, 0, 0, 0, 1);
 255
 256                this->generator.generate(i + j, cond_swiz, list);
 257             }
 258          }
 259       }
 260    }
 261
 262    void bisect(unsigned begin, unsigned end, exec_list *list)
 263    {
 264       unsigned middle = (begin + end) >> 1;
 265
 266       assert(index->type->is_integer());
 267
 268       ir_constant *const middle_c = (index->type->base_type == GLSL_TYPE_UINT)
 269          ? new(this->mem_ctx) ir_constant((unsigned)middle)
 270          : new(this->mem_ctx) ir_constant((int)middle);
 271
 272
 273       ir_dereference_variable *deref =
 274          new(this->mem_ctx) ir_dereference_variable(this->index);
 275
 276       ir_expression *less =
 277          new(this->mem_ctx) ir_expression(ir_binop_less, glsl_type::bool_type,
 278                                           deref, middle_c);
 279
 280       ir_if *if_less = new(this->mem_ctx) ir_if(less);
 281
 282       generate(begin, middle, &if_less->then_instructions);
 283       generate(middle, end, &if_less->else_instructions);
 284
 285       list->push_tail(if_less);
 286    }
 287
 288    void generate(unsigned begin, unsigned end, exec_list *list)
 289    {
 290       unsigned length = end - begin;
 291       if (length <= this->linear_sequence_max_length)
 292          return linear_sequence(begin, end, list);
 293       else
 294          return bisect(begin, end, list);
 295    }
 296 };
 297
 298 /**
 299  * Visitor class for replacing expressions with ir_constant values.
 300  */
 301
 302 class variable_index_to_cond_assign_visitor : public ir_rvalue_visitor {
 303 public:
 304    variable_index_to_cond_assign_visitor(bool lower_input,
 305                                          bool lower_output,
 306                                          bool lower_temp,
 307                                          bool lower_uniform)
 308    {
 309       this->progress = false;
 310       this->lower_inputs = lower_input;
 311       this->lower_outputs = lower_output;
 312       this->lower_temps = lower_temp;
 313       this->lower_uniforms = lower_uniform;
 314    }
 315
 316    bool progress;
 317    bool lower_inputs;
 318    bool lower_outputs;
 319    bool lower_temps;
 320    bool lower_uniforms;
 321
 322    bool storage_type_needs_lowering(ir_dereference_array *deref) const
 323    {
 324       /* If a variable isn't eventually the target of this dereference, then
 325        * it must be a constant or some sort of anonymous temporary storage.
 326        *
 327        * FINISHME: Is this correct?  Most drivers treat arrays of constants as
 328        * FINISHME: uniforms.  It seems like this should do the same.
 329        */
 330       const ir_variable *const var = deref->array->variable_referenced();
 331       if (var == NULL)
 332          return this->lower_temps;
 333
 334       switch (var->mode) {
 335       case ir_var_auto:
 336       case ir_var_temporary:
 337          return this->lower_temps;
 338       case ir_var_uniform:
 339          return this->lower_uniforms;
 340       case ir_var_in:
 341       case ir_var_const_in:
 342          return (var->location == -1) ? this->lower_temps : this->lower_inputs;
 343       case ir_var_out:
 344          return (var->location == -1) ? this->lower_temps : this->lower_outputs;
 345       case ir_var_inout:
 346          return this->lower_temps;
 347       }
 348
 349       assert(!"Should not get here.");
 350       return false;
 351    }
 352
 353    bool needs_lowering(ir_dereference_array *deref) const
 354    {
 355       if (deref == NULL || deref->array_index->as_constant()
 356           || !is_array_or_matrix(deref->array))
 357          return false;
 358
 359       return this->storage_type_needs_lowering(deref);
 360    }
 361
 362    ir_variable *convert_dereference_array(ir_dereference_array *orig_deref,
 363                                           ir_assignment* orig_assign,
 364                                           ir_dereference *orig_base)
 365    {
 366       assert(is_array_or_matrix(orig_deref->array));
 367
 368       const unsigned length = (orig_deref->array->type->is_array())
 369          ? orig_deref->array->type->length
 370          : orig_deref->array->type->matrix_columns;
 371
 372       void *const mem_ctx = ralloc_parent(base_ir);
 373
 374       /* Temporary storage for either the result of the dereference of
 375        * the array, or the RHS that's being assigned into the
 376        * dereference of the array.
 377        */
 378       ir_variable *var;
 379
 380       if (orig_assign) {
 381          var = new(mem_ctx) ir_variable(orig_assign->rhs->type,
 382                                         "dereference_array_value",
 383                                         ir_var_temporary);
 384          base_ir->insert_before(var);
 385
 386          ir_dereference *lhs = new(mem_ctx) ir_dereference_variable(var);
 387          ir_assignment *assign = new(mem_ctx) ir_assignment(lhs,
 388                                                             orig_assign->rhs,
 389                                                             NULL);
 390
 391          base_ir->insert_before(assign);
 392       } else {
 393          var = new(mem_ctx) ir_variable(orig_deref->type,
 394                                         "dereference_array_value",
 395                                         ir_var_temporary);
 396          base_ir->insert_before(var);
 397       }
 398
 399       /* Store the index to a temporary to avoid reusing its tree. */
 400       ir_variable *index =
 401          new(mem_ctx) ir_variable(orig_deref->array_index->type,
 402                                   "dereference_array_index", ir_var_temporary);
 403       base_ir->insert_before(index);
 404
 405       ir_dereference *lhs = new(mem_ctx) ir_dereference_variable(index);
 406       ir_assignment *assign =
 407          new(mem_ctx) ir_assignment(lhs, orig_deref->array_index, NULL);
 408       base_ir->insert_before(assign);
 409
 410       orig_deref->array_index = lhs->clone(mem_ctx, NULL);
 411
 412       assignment_generator ag;
 413       ag.rvalue = orig_base;
 414       ag.base_ir = base_ir;
 415       ag.old_index = index;
 416       ag.var = var;
 417       if (orig_assign) {
 418          ag.is_write = true;
 419          ag.write_mask = orig_assign->write_mask;
 420       } else {
 421          ag.is_write = false;
 422       }
 423
 424       switch_generator sg(ag, index, 4, 4);
 425
 426       /* If the original assignment has a condition, respect that original
 427        * condition!  This is acomplished by wrapping the new conditional
 428        * assignments in an if-statement that uses the original condition.
 429        */
 430       if ((orig_assign != NULL) && (orig_assign->condition != NULL)) {
 431          /* No need to clone the condition because the IR that it hangs on is
 432           * going to be removed from the instruction sequence.
 433           */
 434          ir_if *if_stmt = new(mem_ctx) ir_if(orig_assign->condition);
 435
 436          sg.generate(0, length, &if_stmt->then_instructions);
 437          base_ir->insert_before(if_stmt);
 438       } else {
 439          exec_list list;
 440
 441          sg.generate(0, length, &list);
 442          base_ir->insert_before(&list);
 443       }
 444
 445       return var;
 446    }
 447
 448    virtual void handle_rvalue(ir_rvalue **pir)
 449    {
 450       if (this->in_assignee)
 451          return;
 452
 453       if (!*pir)
 454          return;
 455
 456       ir_dereference_array* orig_deref = (*pir)->as_dereference_array();
 457       if (needs_lowering(orig_deref)) {
 458          ir_variable *var =
 459             convert_dereference_array(orig_deref, NULL, orig_deref);
 460          assert(var);
 461          *pir = new(ralloc_parent(base_ir)) ir_dereference_variable(var);
 462          this->progress = true;
 463       }
 464    }
 465
 466    ir_visitor_status
 467    visit_leave(ir_assignment *ir)
 468    {
 469       ir_rvalue_visitor::visit_leave(ir);
 470
 471       find_variable_index f;
 472       ir->lhs->accept(&f);
 473
 474       if ((f.deref != NULL) && storage_type_needs_lowering(f.deref)) {
 475          convert_dereference_array(f.deref, ir, ir->lhs);
 476          ir->remove();
 477          this->progress = true;
 478       }
 479
 480       return visit_continue;
 481    }
 482 };
 483
 484 bool
 485 lower_variable_index_to_cond_assign(exec_list *instructions,
 486                                     bool lower_input,
 487                                     bool lower_output,
 488                                     bool lower_temp,
 489                                     bool lower_uniform)
 490 {
 491    variable_index_to_cond_assign_visitor v(lower_input,
 492                                            lower_output,
 493                                            lower_temp,
 494                                            lower_uniform);
 495
 496    /* Continue lowering until no progress is made.  If there are multiple
 497     * levels of indirection (e.g., non-constant indexing of array elements and
 498     * matrix columns of an array of matrix), each pass will only lower one
 499     * level of indirection.
 500     */
 501    bool progress_ever = false;
 502    do {
 503       v.progress = false;
 504       visit_list_elements(&v, instructions);
 505       progress_ever = v.progress || progress_ever;
 506    } while (v.progress);
 507
 508    return progress_ever;
 509 }