src/glsl/loop_analysis.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 #include "glsl_types.h"
  25 #include "loop_analysis.h"
  26 #include "ir_hierarchical_visitor.h"
  27
  28 static bool is_loop_terminator(ir_if *ir);
  29
  30 static bool all_expression_operands_are_loop_constant(ir_rvalue *,
  31                                                       hash_table *);
  32
  33 static ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *);
  34
  35
  36 loop_state::loop_state()
  37 {
  38    this->ht = hash_table_ctor(0, hash_table_pointer_hash,
  39                               hash_table_pointer_compare);
  40    this->mem_ctx = talloc_init("loop state");
  41 }
  42
  43
  44 loop_state::~loop_state()
  45 {
  46    hash_table_dtor(this->ht);
  47 }
  48
  49
  50 loop_variable_state *
  51 loop_state::insert(ir_loop *ir)
  52 {
  53    loop_variable_state *ls = new(this->mem_ctx) loop_variable_state;
  54    hash_table_insert(this->ht, ls, ir);
  55
  56    return ls;
  57 }
  58
  59
  60 loop_variable_state *
  61 loop_state::get(const ir_loop *ir)
  62 {
  63    return (loop_variable_state *) hash_table_find(this->ht, ir);
  64 }
  65
  66
  67 loop_variable *
  68 loop_variable_state::get(const ir_variable *ir)
  69 {
  70    return (loop_variable *) hash_table_find(this->var_hash, ir);
  71 }
  72
  73
  74 loop_variable *
  75 loop_variable_state::insert(ir_variable *var)
  76 {
  77    void *mem_ctx = talloc_parent(this);
  78    loop_variable *lv = talloc_zero(mem_ctx, loop_variable);
  79
  80    lv->var = var;
  81
  82    hash_table_insert(this->var_hash, lv, lv->var);
  83    this->variables.push_tail(lv);
  84
  85    return lv;
  86 }
  87
  88
  89 loop_terminator *
  90 loop_variable_state::insert(ir_if *if_stmt)
  91 {
  92    void *mem_ctx = talloc_parent(this);
  93    loop_terminator *t = talloc_zero(mem_ctx, loop_terminator);
  94
  95    t->ir = if_stmt;
  96    this->terminators.push_tail(t);
  97
  98    return t;
  99 }
 100
 101
 102 class loop_analysis : public ir_hierarchical_visitor {
 103 public:
 104    loop_analysis();
 105
 106    virtual ir_visitor_status visit(ir_dereference_variable *);
 107
 108    virtual ir_visitor_status visit_enter(ir_loop *);
 109    virtual ir_visitor_status visit_leave(ir_loop *);
 110    virtual ir_visitor_status visit_enter(ir_assignment *);
 111    virtual ir_visitor_status visit_leave(ir_assignment *);
 112    virtual ir_visitor_status visit_enter(ir_if *);
 113    virtual ir_visitor_status visit_leave(ir_if *);
 114
 115    loop_state *loops;
 116
 117    int if_statement_depth;
 118
 119    ir_assignment *current_assignment;
 120
 121    exec_list state;
 122 };
 123
 124
 125 loop_analysis::loop_analysis()
 126 {
 127    this->loops = new loop_state;
 128
 129    this->if_statement_depth = 0;
 130    this->current_assignment = NULL;
 131 }
 132
 133
 134 ir_visitor_status
 135 loop_analysis::visit(ir_dereference_variable *ir)
 136 {
 137    /* If we're not somewhere inside a loop, there's nothing to do.
 138     */
 139    if (this->state.is_empty())
 140       return visit_continue_with_parent;
 141
 142    loop_variable_state *const ls =
 143       (loop_variable_state *) this->state.get_head();
 144
 145    ir_variable *var = ir->variable_referenced();
 146    loop_variable *lv = ls->get(var);
 147
 148    if (lv == NULL) {
 149       lv = ls->insert(var);
 150       lv->read_before_write = !this->in_assignee;
 151    }
 152
 153    if (this->in_assignee) {
 154       assert(this->current_assignment != NULL);
 155
 156       lv->conditional_assignment = (this->if_statement_depth > 0)
 157          || (this->current_assignment->condition != NULL);
 158
 159       if (lv->first_assignment == NULL) {
 160          assert(lv->num_assignments == 0);
 161
 162          lv->first_assignment = this->current_assignment;
 163       }
 164
 165       lv->num_assignments++;
 166    } else if (lv->first_assignment == this->current_assignment) {
 167       /* This catches the case where the variable is used in the RHS of an
 168        * assignment where it is also in the LHS.
 169        */
 170       lv->read_before_write = true;
 171    }
 172
 173    return visit_continue;
 174 }
 175
 176 ir_visitor_status
 177 loop_analysis::visit_enter(ir_loop *ir)
 178 {
 179    loop_variable_state *ls = this->loops->insert(ir);
 180    this->state.push_head(ls);
 181
 182    return visit_continue;
 183 }
 184
 185 ir_visitor_status
 186 loop_analysis::visit_leave(ir_loop *ir)
 187 {
 188    loop_variable_state *const ls =
 189       (loop_variable_state *) this->state.pop_head();
 190
 191
 192    foreach_list(node, &ir->body_instructions) {
 193       /* Skip over declarations at the start of a loop.
 194        */
 195       if (((ir_instruction *) node)->as_variable())
 196          continue;
 197
 198       ir_if *if_stmt = ((ir_instruction *) node)->as_if();
 199
 200       if ((if_stmt != NULL) && is_loop_terminator(if_stmt))
 201          ls->insert(if_stmt);
 202       else
 203          break;
 204    }
 205
 206
 207    foreach_list_safe(node, &ls->variables) {
 208       loop_variable *lv = (loop_variable *) node;
 209
 210       /* Move variables that are already marked as being loop constant to
 211        * a separate list.  These trivially don't need to be tested.
 212        */
 213       if (lv->is_loop_constant()) {
 214          lv->remove();
 215          ls->constants.push_tail(lv);
 216       }
 217    }
 218
 219    /* Each variable assigned in the loop that isn't already marked as being loop
 220     * constant might still be loop constant.  The requirements at this point
 221     * are:
 222     *
 223     *    - Variable is written before it is read.
 224     *
 225     *    - Only one assignment to the variable.
 226     *
 227     *    - All operands on the RHS of the assignment are also loop constants.
 228     *
 229     * The last requirement is the reason for the progress loop.  A variable
 230     * marked as a loop constant on one pass may allow other variables to be
 231     * marked as loop constant on following passes.
 232     */
 233    bool progress;
 234    do {
 235       progress = false;
 236
 237       foreach_list_safe(node, &ls->variables) {
 238          loop_variable *lv = (loop_variable *) node;
 239
 240          if (lv->conditional_assignment || (lv->num_assignments > 1))
 241             continue;
 242
 243          /* Process the RHS of the assignment.  If all of the variables
 244           * accessed there are loop constants, then add this
 245           */
 246          ir_rvalue *const rhs = lv->first_assignment->rhs;
 247          if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) {
 248             lv->rhs_clean = true;
 249
 250             if (lv->is_loop_constant()) {
 251                progress = true;
 252
 253                lv->remove();
 254                ls->constants.push_tail(lv);
 255             }
 256          }
 257       }
 258    } while (progress);
 259
 260    /* The remaining variables that are not loop invariant might be loop
 261     * induction variables.
 262     */
 263    foreach_list_safe(node, &ls->variables) {
 264       loop_variable *lv = (loop_variable *) node;
 265
 266       /* If there is more than one assignment to a variable, it cannot be a
 267        * loop induction variable.  This isn't strictly true, but this is a
 268        * very simple induction variable detector, and it can't handle more
 269        * complex cases.
 270        */
 271       if (lv->num_assignments > 1)
 272          continue;
 273
 274       /* All of the variables with zero assignments in the loop are loop
 275        * invariant, and they should have already been filtered out.
 276        */
 277       assert(lv->num_assignments == 1);
 278       assert(lv->first_assignment != NULL);
 279
 280       /* The assignmnet to the variable in the loop must be unconditional.
 281        */
 282       if (lv->conditional_assignment)
 283          continue;
 284
 285       /* Basic loop induction variables have a single assignment in the loop
 286        * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a
 287        * loop invariant.
 288        */
 289       ir_rvalue *const inc =
 290          get_basic_induction_increment(lv->first_assignment, ls->var_hash);
 291       if (inc != NULL) {
 292          lv->iv_scale = NULL;
 293          lv->biv = lv->var;
 294          lv->increment = inc;
 295
 296          lv->remove();
 297          ls->induction_variables.push_tail(lv);
 298       }
 299    }
 300
 301    return visit_continue;
 302 }
 303
 304 ir_visitor_status
 305 loop_analysis::visit_enter(ir_if *ir)
 306 {
 307    (void) ir;
 308
 309    if (!this->state.is_empty())
 310       this->if_statement_depth++;
 311
 312    return visit_continue;
 313 }
 314
 315 ir_visitor_status
 316 loop_analysis::visit_leave(ir_if *ir)
 317 {
 318    (void) ir;
 319
 320    if (!this->state.is_empty())
 321       this->if_statement_depth--;
 322
 323    return visit_continue;
 324 }
 325
 326 ir_visitor_status
 327 loop_analysis::visit_enter(ir_assignment *ir)
 328 {
 329    /* If we're not somewhere inside a loop, there's nothing to do.
 330     */
 331    if (this->state.is_empty())
 332       return visit_continue_with_parent;
 333
 334    this->current_assignment = ir;
 335
 336    return visit_continue;
 337 }
 338
 339 ir_visitor_status
 340 loop_analysis::visit_leave(ir_assignment *ir)
 341 {
 342    /* Since the visit_enter exits with visit_continue_with_parent for this
 343     * case, the loop state stack should never be empty here.
 344     */
 345    assert(!this->state.is_empty());
 346
 347    assert(this->current_assignment == ir);
 348    this->current_assignment = NULL;
 349
 350    return visit_continue;
 351 }
 352
 353
 354 class examine_rhs : public ir_hierarchical_visitor {
 355 public:
 356    examine_rhs(hash_table *loop_variables)
 357    {
 358       this->only_uses_loop_constants = true;
 359       this->loop_variables = loop_variables;
 360    }
 361
 362    virtual ir_visitor_status visit(ir_dereference_variable *ir)
 363    {
 364       loop_variable *lv =
 365          (loop_variable *) hash_table_find(this->loop_variables, ir->var);
 366
 367       assert(lv != NULL);
 368
 369       if (lv->is_loop_constant()) {
 370          return visit_continue;
 371       } else {
 372          this->only_uses_loop_constants = false;
 373          return visit_stop;
 374       }
 375    }
 376
 377    hash_table *loop_variables;
 378    bool only_uses_loop_constants;
 379 };
 380
 381
 382 bool
 383 all_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables)
 384 {
 385    examine_rhs v(variables);
 386
 387    ir->accept(&v);
 388
 389    return v.only_uses_loop_constants;
 390 }
 391
 392
 393 ir_rvalue *
 394 get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash)
 395 {
 396    /* The RHS must be a binary expression.
 397     */
 398    ir_expression *const rhs = ir->rhs->as_expression();
 399    if ((rhs == NULL)
 400        || ((rhs->operation != ir_binop_add)
 401            && (rhs->operation != ir_binop_sub)))
 402       return NULL;
 403
 404    /* One of the of operands of the expression must be the variable assigned.
 405     * If the operation is subtraction, the variable in question must be the
 406     * "left" operand.
 407     */
 408    ir_variable *const var = ir->lhs->variable_referenced();
 409
 410    ir_variable *const op0 = rhs->operands[0]->variable_referenced();
 411    ir_variable *const op1 = rhs->operands[1]->variable_referenced();
 412
 413    if (((op0 != var) && (op1 != var))
 414        || ((op1 == var) && (rhs->operation == ir_binop_sub)))
 415       return NULL;
 416
 417    ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0];
 418
 419    if (inc->constant_expression_value() == NULL) {
 420       ir_variable *const inc_var = inc->variable_referenced();
 421       if (inc_var != NULL) {
 422          loop_variable *lv =
 423             (loop_variable *) hash_table_find(var_hash, inc_var);
 424
 425          if (!lv->is_loop_constant())
 426             inc = NULL;
 427       } else
 428          inc = NULL;
 429    }
 430
 431    if ((inc != NULL) && (rhs->operation == ir_binop_sub)) {
 432       void *mem_ctx = talloc_parent(ir);
 433
 434       inc = new(mem_ctx) ir_expression(ir_unop_neg,
 435                                        inc->type,
 436                                        inc->clone(mem_ctx, NULL),
 437                                        NULL);
 438    }
 439
 440    return inc;
 441 }
 442
 443
 444 /**
 445  * Detect whether an if-statement is a loop terminating condition
 446  *
 447  * Detects if-statements of the form
 448  *
 449  *  (if (expression bool ...) (break))
 450  */
 451 bool
 452 is_loop_terminator(ir_if *ir)
 453 {
 454    if (!ir->else_instructions.is_empty())
 455       return false;
 456
 457    ir_instruction *const inst =
 458       (ir_instruction *) ir->then_instructions.get_head();
 459    assert(inst != NULL);
 460
 461    if (inst->ir_type != ir_type_loop_jump)
 462       return false;
 463
 464    ir_loop_jump *const jump = (ir_loop_jump *) inst;
 465    if (jump->mode != ir_loop_jump::jump_break)
 466       return false;
 467
 468    return true;
 469 }
 470
 471
 472 loop_state *
 473 analyze_loop_variables(exec_list *instructions)
 474 {
 475    loop_analysis v;
 476
 477    v.run(instructions);
 478    return v.loops;
 479 }