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
  34 #include "ir.h"
  35 #include "ir_rvalue_visitor.h"
  36 #include "ir_optimization.h"
  37 #include "glsl_types.h"
  38 #include "main/macros.h"
  39
  40 struct assignment_generator
  41 {
  42    ir_instruction* base_ir;
  43    ir_rvalue* array;
  44    bool is_write;
  45    ir_variable* var;
  46
  47    assignment_generator()
  48    {
  49    }
  50
  51    void generate(unsigned i, ir_rvalue* condition, exec_list *list) const
  52    {
  53       /* Just clone the rest of the deref chain when trying to get at the
  54        * underlying variable.
  55        */
  56       void *mem_ctx = talloc_parent(base_ir);
  57       ir_rvalue *element =
  58          new(mem_ctx) ir_dereference_array(this->array->clone(mem_ctx, NULL),
  59                                            new(mem_ctx) ir_constant(i));
  60       ir_rvalue *variable = new(mem_ctx) ir_dereference_variable(this->var);
  61
  62       ir_assignment *assignment = (is_write)
  63          ? new(mem_ctx) ir_assignment(element, variable, condition)
  64          : new(mem_ctx) ir_assignment(variable, element, condition);
  65
  66       list->push_tail(assignment);
  67    }
  68 };
  69
  70 struct switch_generator
  71 {
  72    /* make TFunction a template parameter if you need to use other generators */
  73    typedef assignment_generator TFunction;
  74    const TFunction& generator;
  75
  76    ir_variable* index;
  77    unsigned linear_sequence_max_length;
  78    unsigned condition_components;
  79
  80    void *mem_ctx;
  81
  82    switch_generator(const TFunction& generator, ir_variable *index,
  83                     unsigned linear_sequence_max_length,
  84                     unsigned condition_components)
  85       : generator(generator), index(index),
  86         linear_sequence_max_length(linear_sequence_max_length),
  87         condition_components(condition_components)
  88    {
  89       this->mem_ctx = talloc_parent(index);
  90    }
  91
  92    void linear_sequence(unsigned begin, unsigned end, exec_list *list)
  93    {
  94       if (begin == end)
  95          return;
  96
  97       /* If the array access is a read, read the first element of this subregion
  98        * unconditionally.  The remaining tests will possibly overwrite this
  99        * value with one of the other array elements.
 100        *
 101        * This optimization cannot be done for writes because it will cause the
 102        * first element of the subregion to be written possibly *in addition* to
 103        * one of the other elements.
 104        */
 105       unsigned first;
 106       if (!this->generator.is_write) {
 107          this->generator.generate(begin, 0, list);
 108          first = begin + 1;
 109       } else {
 110          first = begin;
 111       }
 112
 113       for (unsigned i = first; i < end; i += 4) {
 114          const unsigned comps = MIN2(condition_components, end - i);
 115
 116          ir_rvalue *broadcast_index =
 117             new(this->mem_ctx) ir_dereference_variable(index);
 118
 119          if (comps) {
 120             const ir_swizzle_mask m = { 0, 0, 0, 0, comps, false };
 121             broadcast_index = new(this->mem_ctx) ir_swizzle(broadcast_index, m);
 122          }
 123
 124          /* Compare the desired index value with the next block of four indices.
 125           */
 126          ir_constant_data test_indices_data;
 127          memset(&test_indices_data, 0, sizeof(test_indices_data));
 128          test_indices_data.i[0] = i;
 129          test_indices_data.i[1] = i + 1;
 130          test_indices_data.i[2] = i + 2;
 131          test_indices_data.i[3] = i + 3;
 132          ir_constant *const test_indices =
 133             new(this->mem_ctx) ir_constant(broadcast_index->type,
 134                                            &test_indices_data);
 135
 136          ir_rvalue *const condition_val =
 137             new(this->mem_ctx) ir_expression(ir_binop_equal,
 138                                              &glsl_type::bool_type[comps - 1],
 139                                              broadcast_index,
 140                                              test_indices);
 141
 142          ir_variable *const condition =
 143             new(this->mem_ctx) ir_variable(condition_val->type,
 144                                            "dereference_array_condition",
 145                                            ir_var_temporary);
 146          list->push_tail(condition);
 147
 148          ir_rvalue *const cond_deref =
 149             new(this->mem_ctx) ir_dereference_variable(condition);
 150          list->push_tail(new(this->mem_ctx) ir_assignment(cond_deref,
 151                                                           condition_val, 0));
 152
 153          if (comps == 1) {
 154             ir_rvalue *const cond_deref =
 155                new(this->mem_ctx) ir_dereference_variable(condition);
 156
 157             this->generator.generate(i, cond_deref, list);
 158          } else {
 159             for (unsigned j = 0; j < comps; j++) {
 160                ir_rvalue *const cond_deref =
 161                   new(this->mem_ctx) ir_dereference_variable(condition);
 162                ir_rvalue *const cond_swiz =
 163                   new(this->mem_ctx) ir_swizzle(cond_deref, j, 0, 0, 0, 1);
 164
 165                this->generator.generate(i + j, cond_swiz, list);
 166             }
 167          }
 168       }
 169    }
 170
 171    void bisect(unsigned begin, unsigned end, exec_list *list)
 172    {
 173       unsigned middle = (begin + end) >> 1;
 174
 175       assert(index->type->is_integer());
 176
 177       ir_constant *const middle_c = (index->type->base_type == GLSL_TYPE_UINT)
 178          ? new(this->mem_ctx) ir_constant((unsigned)middle)
 179          : new(this->mem_ctx) ir_constant((int)middle);
 180
 181
 182       ir_dereference_variable *deref =
 183          new(this->mem_ctx) ir_dereference_variable(this->index);
 184
 185       ir_expression *less =
 186          new(this->mem_ctx) ir_expression(ir_binop_less, glsl_type::bool_type,
 187                                           deref, middle_c);
 188
 189       ir_if *if_less = new(this->mem_ctx) ir_if(less);
 190
 191       generate(begin, middle, &if_less->then_instructions);
 192       generate(middle, end, &if_less->else_instructions);
 193
 194       list->push_tail(if_less);
 195    }
 196
 197    void generate(unsigned begin, unsigned end, exec_list *list)
 198    {
 199       unsigned length = end - begin;
 200       if (length <= this->linear_sequence_max_length)
 201          return linear_sequence(begin, end, list);
 202       else
 203          return bisect(begin, end, list);
 204    }
 205 };
 206
 207 /**
 208  * Visitor class for replacing expressions with ir_constant values.
 209  */
 210
 211 class variable_index_to_cond_assign_visitor : public ir_rvalue_visitor {
 212 public:
 213    variable_index_to_cond_assign_visitor(bool lower_input,
 214                                          bool lower_output,
 215                                          bool lower_temp,
 216                                          bool lower_uniform)
 217    {
 218       this->progress = false;
 219       this->lower_inputs = lower_input;
 220       this->lower_outputs = lower_output;
 221       this->lower_temps = lower_temp;
 222       this->lower_uniforms = lower_uniform;
 223    }
 224
 225    bool progress;
 226    bool lower_inputs;
 227    bool lower_outputs;
 228    bool lower_temps;
 229    bool lower_uniforms;
 230
 231    bool is_array_or_matrix(const ir_instruction *ir) const
 232    {
 233       return (ir->type->is_array() || ir->type->is_matrix());
 234    }
 235
 236    bool needs_lowering(ir_dereference_array *deref) const
 237    {
 238       if (deref == NULL || deref->array_index->as_constant()
 239           || !is_array_or_matrix(deref->array))
 240          return false;
 241
 242       if (deref->array->ir_type == ir_type_constant)
 243          return this->lower_temps;
 244
 245       const ir_variable *const var = deref->array->variable_referenced();
 246       switch (var->mode) {
 247       case ir_var_auto:
 248       case ir_var_temporary:
 249          return this->lower_temps;
 250       case ir_var_uniform:
 251          return this->lower_uniforms;
 252       case ir_var_in:
 253          return (var->location == -1) ? this->lower_temps : this->lower_inputs;
 254       case ir_var_out:
 255          return (var->location == -1) ? this->lower_temps : this->lower_outputs;
 256       case ir_var_inout:
 257          return this->lower_temps;
 258       }
 259
 260       assert(!"Should not get here.");
 261       return false;
 262    }
 263
 264    ir_variable *convert_dereference_array(ir_dereference_array *orig_deref,
 265                                           ir_rvalue* value)
 266    {
 267       assert(is_array_or_matrix(orig_deref->array));
 268
 269       const unsigned length = (orig_deref->array->type->is_array())
 270          ? orig_deref->array->type->length
 271          : orig_deref->array->type->matrix_columns;
 272
 273       void *const mem_ctx = talloc_parent(base_ir);
 274       ir_variable *var =
 275          new(mem_ctx) ir_variable(orig_deref->type, "dereference_array_value",
 276                                   ir_var_temporary);
 277       base_ir->insert_before(var);
 278
 279       if (value) {
 280          ir_dereference *lhs = new(mem_ctx) ir_dereference_variable(var);
 281          ir_assignment *assign = new(mem_ctx) ir_assignment(lhs, value, NULL);
 282
 283          base_ir->insert_before(assign);
 284       }
 285
 286       /* Store the index to a temporary to avoid reusing its tree. */
 287       ir_variable *index =
 288          new(mem_ctx) ir_variable(orig_deref->array_index->type,
 289                                   "dereference_array_index", ir_var_temporary);
 290       base_ir->insert_before(index);
 291
 292       ir_dereference *lhs = new(mem_ctx) ir_dereference_variable(index);
 293       ir_assignment *assign =
 294          new(mem_ctx) ir_assignment(lhs, orig_deref->array_index, NULL);
 295       base_ir->insert_before(assign);
 296
 297       assignment_generator ag;
 298       ag.array = orig_deref->array;
 299       ag.base_ir = base_ir;
 300       ag.var = var;
 301       ag.is_write = !!value;
 302
 303       switch_generator sg(ag, index, 4, 4);
 304
 305       exec_list list;
 306       sg.generate(0, length, &list);
 307       base_ir->insert_before(&list);
 308
 309       return var;
 310    }
 311
 312    virtual void handle_rvalue(ir_rvalue **pir)
 313    {
 314       if (!*pir)
 315          return;
 316
 317       ir_dereference_array* orig_deref = (*pir)->as_dereference_array();
 318       if (needs_lowering(orig_deref)) {
 319          ir_variable* var = convert_dereference_array(orig_deref, 0);
 320          assert(var);
 321          *pir = new(talloc_parent(base_ir)) ir_dereference_variable(var);
 322          this->progress = true;
 323       }
 324    }
 325
 326    ir_visitor_status
 327    visit_leave(ir_assignment *ir)
 328    {
 329       ir_rvalue_visitor::visit_leave(ir);
 330
 331       ir_dereference_array *orig_deref = ir->lhs->as_dereference_array();
 332
 333       if (needs_lowering(orig_deref)) {
 334          convert_dereference_array(orig_deref, ir->rhs);
 335          ir->remove();
 336          this->progress = true;
 337       }
 338
 339       return visit_continue;
 340    }
 341 };
 342
 343 bool
 344 lower_variable_index_to_cond_assign(exec_list *instructions,
 345                                     bool lower_input,
 346                                     bool lower_output,
 347                                     bool lower_temp,
 348                                     bool lower_uniform)
 349 {
 350    variable_index_to_cond_assign_visitor v(lower_input,
 351                                            lower_output,
 352                                            lower_temp,
 353                                            lower_uniform);
 354
 355    visit_list_elements(&v, instructions);
 356
 357    return v.progress;
 358 }