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 /**
  37  * Record the fact that the given loop variable was referenced inside the loop.
  38  *
  39  * \arg in_assignee is true if the reference was on the LHS of an assignment.
  40  *
  41  * \arg in_conditional_code_or_nested_loop is true if the reference occurred
  42  * inside an if statement or a nested loop.
  43  *
  44  * \arg current_assignment is the ir_assignment node that the loop variable is
  45  * on the LHS of, if any (ignored if \c in_assignee is false).
  46  */
  47 void
  48 loop_variable::record_reference(bool in_assignee,
  49                                 bool in_conditional_code_or_nested_loop,
  50                                 ir_assignment *current_assignment)
  51 {
  52    if (in_assignee) {
  53       assert(current_assignment != NULL);
  54
  55       this->conditional_or_nested_assignment =
  56          in_conditional_code_or_nested_loop
  57          || current_assignment->condition != NULL;
  58
  59       if (this->first_assignment == NULL) {
  60          assert(this->num_assignments == 0);
  61
  62          this->first_assignment = current_assignment;
  63       }
  64
  65       this->num_assignments++;
  66    } else if (this->first_assignment == current_assignment) {
  67       /* This catches the case where the variable is used in the RHS of an
  68        * assignment where it is also in the LHS.
  69        */
  70       this->read_before_write = true;
  71    }
  72 }
  73
  74
  75 loop_state::loop_state()
  76 {
  77    this->ht = hash_table_ctor(0, hash_table_pointer_hash,
  78                               hash_table_pointer_compare);
  79    this->mem_ctx = ralloc_context(NULL);
  80    this->loop_found = false;
  81 }
  82
  83
  84 loop_state::~loop_state()
  85 {
  86    hash_table_dtor(this->ht);
  87    ralloc_free(this->mem_ctx);
  88 }
  89
  90
  91 loop_variable_state *
  92 loop_state::insert(ir_loop *ir)
  93 {
  94    loop_variable_state *ls = new(this->mem_ctx) loop_variable_state;
  95
  96    hash_table_insert(this->ht, ls, ir);
  97    this->loop_found = true;
  98
  99    return ls;
 100 }
 101
 102
 103 loop_variable_state *
 104 loop_state::get(const ir_loop *ir)
 105 {
 106    return (loop_variable_state *) hash_table_find(this->ht, ir);
 107 }
 108
 109
 110 loop_variable *
 111 loop_variable_state::get(const ir_variable *ir)
 112 {
 113    return (loop_variable *) hash_table_find(this->var_hash, ir);
 114 }
 115
 116
 117 loop_variable *
 118 loop_variable_state::insert(ir_variable *var)
 119 {
 120    void *mem_ctx = ralloc_parent(this);
 121    loop_variable *lv = rzalloc(mem_ctx, loop_variable);
 122
 123    lv->var = var;
 124
 125    hash_table_insert(this->var_hash, lv, lv->var);
 126    this->variables.push_tail(lv);
 127
 128    return lv;
 129 }
 130
 131
 132 loop_terminator *
 133 loop_variable_state::insert(ir_if *if_stmt)
 134 {
 135    void *mem_ctx = ralloc_parent(this);
 136    loop_terminator *t = rzalloc(mem_ctx, loop_terminator);
 137
 138    t->ir = if_stmt;
 139    this->terminators.push_tail(t);
 140
 141    return t;
 142 }
 143
 144
 145 /**
 146  * If the given variable already is recorded in the state for this loop,
 147  * return the corresponding loop_variable object that records information
 148  * about it.
 149  *
 150  * Otherwise, create a new loop_variable object to record information about
 151  * the variable, and set its \c read_before_write field appropriately based on
 152  * \c in_assignee.
 153  *
 154  * \arg in_assignee is true if this variable was encountered on the LHS of an
 155  * assignment.
 156  */
 157 loop_variable *
 158 loop_variable_state::get_or_insert(ir_variable *var, bool in_assignee)
 159 {
 160    loop_variable *lv = this->get(var);
 161
 162    if (lv == NULL) {
 163       lv = this->insert(var);
 164       lv->read_before_write = !in_assignee;
 165    }
 166
 167    return lv;
 168 }
 169
 170
 171 namespace {
 172
 173 class loop_analysis : public ir_hierarchical_visitor {
 174 public:
 175    loop_analysis(loop_state *loops);
 176
 177    virtual ir_visitor_status visit(ir_loop_jump *);
 178    virtual ir_visitor_status visit(ir_dereference_variable *);
 179
 180    virtual ir_visitor_status visit_enter(ir_call *);
 181
 182    virtual ir_visitor_status visit_enter(ir_loop *);
 183    virtual ir_visitor_status visit_leave(ir_loop *);
 184    virtual ir_visitor_status visit_enter(ir_assignment *);
 185    virtual ir_visitor_status visit_leave(ir_assignment *);
 186    virtual ir_visitor_status visit_enter(ir_if *);
 187    virtual ir_visitor_status visit_leave(ir_if *);
 188
 189    loop_state *loops;
 190
 191    int if_statement_depth;
 192
 193    ir_assignment *current_assignment;
 194
 195    exec_list state;
 196 };
 197
 198 } /* anonymous namespace */
 199
 200 loop_analysis::loop_analysis(loop_state *loops)
 201    : loops(loops), if_statement_depth(0), current_assignment(NULL)
 202 {
 203    /* empty */
 204 }
 205
 206
 207 ir_visitor_status
 208 loop_analysis::visit(ir_loop_jump *ir)
 209 {
 210    (void) ir;
 211
 212    assert(!this->state.is_empty());
 213
 214    loop_variable_state *const ls =
 215       (loop_variable_state *) this->state.get_head();
 216
 217    ls->num_loop_jumps++;
 218
 219    return visit_continue;
 220 }
 221
 222
 223 ir_visitor_status
 224 loop_analysis::visit_enter(ir_call *ir)
 225 {
 226    /* Mark every loop that we're currently analyzing as containing an ir_call
 227     * (even those at outer nesting levels).
 228     */
 229    foreach_list(node, &this->state) {
 230       loop_variable_state *const ls = (loop_variable_state *) node;
 231       ls->contains_calls = true;
 232    }
 233
 234    return visit_continue_with_parent;
 235 }
 236
 237
 238 ir_visitor_status
 239 loop_analysis::visit(ir_dereference_variable *ir)
 240 {
 241    /* If we're not somewhere inside a loop, there's nothing to do.
 242     */
 243    if (this->state.is_empty())
 244       return visit_continue;
 245
 246    bool nested = false;
 247
 248    foreach_list(node, &this->state) {
 249       loop_variable_state *const ls = (loop_variable_state *) node;
 250
 251       ir_variable *var = ir->variable_referenced();
 252       loop_variable *lv = ls->get_or_insert(var, this->in_assignee);
 253
 254       lv->record_reference(this->in_assignee,
 255                            nested || this->if_statement_depth > 0,
 256                            this->current_assignment);
 257       nested = true;
 258    }
 259
 260    return visit_continue;
 261 }
 262
 263 ir_visitor_status
 264 loop_analysis::visit_enter(ir_loop *ir)
 265 {
 266    loop_variable_state *ls = this->loops->insert(ir);
 267    this->state.push_head(ls);
 268
 269    return visit_continue;
 270 }
 271
 272 ir_visitor_status
 273 loop_analysis::visit_leave(ir_loop *ir)
 274 {
 275    loop_variable_state *const ls =
 276       (loop_variable_state *) this->state.pop_head();
 277
 278    /* Function calls may contain side effects.  These could alter any of our
 279     * variables in ways that cannot be known, and may even terminate shader
 280     * execution (say, calling discard in the fragment shader).  So we can't
 281     * rely on any of our analysis about assignments to variables.
 282     *
 283     * We could perform some conservative analysis (prove there's no statically
 284     * possible assignment, etc.) but it isn't worth it for now; function
 285     * inlining will allow us to unroll loops anyway.
 286     */
 287    if (ls->contains_calls)
 288       return visit_continue;
 289
 290    foreach_list(node, &ir->body_instructions) {
 291       /* Skip over declarations at the start of a loop.
 292        */
 293       if (((ir_instruction *) node)->as_variable())
 294          continue;
 295
 296       ir_if *if_stmt = ((ir_instruction *) node)->as_if();
 297
 298       if ((if_stmt != NULL) && is_loop_terminator(if_stmt))
 299          ls->insert(if_stmt);
 300       else
 301          break;
 302    }
 303
 304
 305    foreach_list_safe(node, &ls->variables) {
 306       loop_variable *lv = (loop_variable *) node;
 307
 308       /* Move variables that are already marked as being loop constant to
 309        * a separate list.  These trivially don't need to be tested.
 310        */
 311       if (lv->is_loop_constant()) {
 312          lv->remove();
 313          ls->constants.push_tail(lv);
 314       }
 315    }
 316
 317    /* Each variable assigned in the loop that isn't already marked as being loop
 318     * constant might still be loop constant.  The requirements at this point
 319     * are:
 320     *
 321     *    - Variable is written before it is read.
 322     *
 323     *    - Only one assignment to the variable.
 324     *
 325     *    - All operands on the RHS of the assignment are also loop constants.
 326     *
 327     * The last requirement is the reason for the progress loop.  A variable
 328     * marked as a loop constant on one pass may allow other variables to be
 329     * marked as loop constant on following passes.
 330     */
 331    bool progress;
 332    do {
 333       progress = false;
 334
 335       foreach_list_safe(node, &ls->variables) {
 336          loop_variable *lv = (loop_variable *) node;
 337
 338          if (lv->conditional_or_nested_assignment || (lv->num_assignments > 1))
 339             continue;
 340
 341          /* Process the RHS of the assignment.  If all of the variables
 342           * accessed there are loop constants, then add this
 343           */
 344          ir_rvalue *const rhs = lv->first_assignment->rhs;
 345          if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) {
 346             lv->rhs_clean = true;
 347
 348             if (lv->is_loop_constant()) {
 349                progress = true;
 350
 351                lv->remove();
 352                ls->constants.push_tail(lv);
 353             }
 354          }
 355       }
 356    } while (progress);
 357
 358    /* The remaining variables that are not loop invariant might be loop
 359     * induction variables.
 360     */
 361    foreach_list_safe(node, &ls->variables) {
 362       loop_variable *lv = (loop_variable *) node;
 363
 364       /* If there is more than one assignment to a variable, it cannot be a
 365        * loop induction variable.  This isn't strictly true, but this is a
 366        * very simple induction variable detector, and it can't handle more
 367        * complex cases.
 368        */
 369       if (lv->num_assignments > 1)
 370          continue;
 371
 372       /* All of the variables with zero assignments in the loop are loop
 373        * invariant, and they should have already been filtered out.
 374        */
 375       assert(lv->num_assignments == 1);
 376       assert(lv->first_assignment != NULL);
 377
 378       /* The assignment to the variable in the loop must be unconditional and
 379        * not inside a nested loop.
 380        */
 381       if (lv->conditional_or_nested_assignment)
 382          continue;
 383
 384       /* Basic loop induction variables have a single assignment in the loop
 385        * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a
 386        * loop invariant.
 387        */
 388       ir_rvalue *const inc =
 389          get_basic_induction_increment(lv->first_assignment, ls->var_hash);
 390       if (inc != NULL) {
 391          lv->iv_scale = NULL;
 392          lv->biv = lv->var;
 393          lv->increment = inc;
 394
 395          lv->remove();
 396          ls->induction_variables.push_tail(lv);
 397       }
 398    }
 399
 400    return visit_continue;
 401 }
 402
 403 ir_visitor_status
 404 loop_analysis::visit_enter(ir_if *ir)
 405 {
 406    (void) ir;
 407
 408    if (!this->state.is_empty())
 409       this->if_statement_depth++;
 410
 411    return visit_continue;
 412 }
 413
 414 ir_visitor_status
 415 loop_analysis::visit_leave(ir_if *ir)
 416 {
 417    (void) ir;
 418
 419    if (!this->state.is_empty())
 420       this->if_statement_depth--;
 421
 422    return visit_continue;
 423 }
 424
 425 ir_visitor_status
 426 loop_analysis::visit_enter(ir_assignment *ir)
 427 {
 428    /* If we're not somewhere inside a loop, there's nothing to do.
 429     */
 430    if (this->state.is_empty())
 431       return visit_continue_with_parent;
 432
 433    this->current_assignment = ir;
 434
 435    return visit_continue;
 436 }
 437
 438 ir_visitor_status
 439 loop_analysis::visit_leave(ir_assignment *ir)
 440 {
 441    /* Since the visit_enter exits with visit_continue_with_parent for this
 442     * case, the loop state stack should never be empty here.
 443     */
 444    assert(!this->state.is_empty());
 445
 446    assert(this->current_assignment == ir);
 447    this->current_assignment = NULL;
 448
 449    return visit_continue;
 450 }
 451
 452
 453 class examine_rhs : public ir_hierarchical_visitor {
 454 public:
 455    examine_rhs(hash_table *loop_variables)
 456    {
 457       this->only_uses_loop_constants = true;
 458       this->loop_variables = loop_variables;
 459    }
 460
 461    virtual ir_visitor_status visit(ir_dereference_variable *ir)
 462    {
 463       loop_variable *lv =
 464          (loop_variable *) hash_table_find(this->loop_variables, ir->var);
 465
 466       assert(lv != NULL);
 467
 468       if (lv->is_loop_constant()) {
 469          return visit_continue;
 470       } else {
 471          this->only_uses_loop_constants = false;
 472          return visit_stop;
 473       }
 474    }
 475
 476    hash_table *loop_variables;
 477    bool only_uses_loop_constants;
 478 };
 479
 480
 481 bool
 482 all_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables)
 483 {
 484    examine_rhs v(variables);
 485
 486    ir->accept(&v);
 487
 488    return v.only_uses_loop_constants;
 489 }
 490
 491
 492 ir_rvalue *
 493 get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash)
 494 {
 495    /* The RHS must be a binary expression.
 496     */
 497    ir_expression *const rhs = ir->rhs->as_expression();
 498    if ((rhs == NULL)
 499        || ((rhs->operation != ir_binop_add)
 500            && (rhs->operation != ir_binop_sub)))
 501       return NULL;
 502
 503    /* One of the of operands of the expression must be the variable assigned.
 504     * If the operation is subtraction, the variable in question must be the
 505     * "left" operand.
 506     */
 507    ir_variable *const var = ir->lhs->variable_referenced();
 508
 509    ir_variable *const op0 = rhs->operands[0]->variable_referenced();
 510    ir_variable *const op1 = rhs->operands[1]->variable_referenced();
 511
 512    if (((op0 != var) && (op1 != var))
 513        || ((op1 == var) && (rhs->operation == ir_binop_sub)))
 514       return NULL;
 515
 516    ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0];
 517
 518    if (inc->as_constant() == NULL) {
 519       ir_variable *const inc_var = inc->variable_referenced();
 520       if (inc_var != NULL) {
 521          loop_variable *lv =
 522             (loop_variable *) hash_table_find(var_hash, inc_var);
 523
 524          if (!lv->is_loop_constant())
 525             inc = NULL;
 526       } else
 527          inc = NULL;
 528    }
 529
 530    if ((inc != NULL) && (rhs->operation == ir_binop_sub)) {
 531       void *mem_ctx = ralloc_parent(ir);
 532
 533       inc = new(mem_ctx) ir_expression(ir_unop_neg,
 534                                        inc->type,
 535                                        inc->clone(mem_ctx, NULL),
 536                                        NULL);
 537    }
 538
 539    return inc;
 540 }
 541
 542
 543 /**
 544  * Detect whether an if-statement is a loop terminating condition
 545  *
 546  * Detects if-statements of the form
 547  *
 548  *  (if (expression bool ...) (break))
 549  */
 550 bool
 551 is_loop_terminator(ir_if *ir)
 552 {
 553    if (!ir->else_instructions.is_empty())
 554       return false;
 555
 556    ir_instruction *const inst =
 557       (ir_instruction *) ir->then_instructions.get_head();
 558    if (inst == NULL)
 559       return false;
 560
 561    if (inst->ir_type != ir_type_loop_jump)
 562       return false;
 563
 564    ir_loop_jump *const jump = (ir_loop_jump *) inst;
 565    if (jump->mode != ir_loop_jump::jump_break)
 566       return false;
 567
 568    return true;
 569 }
 570
 571
 572 loop_state *
 573 analyze_loop_variables(exec_list *instructions)
 574 {
 575    loop_state *loops = new loop_state;
 576    loop_analysis v(loops);
 577
 578    v.run(instructions);
 579    return v.loops;
 580 }