src/compiler/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 "compiler/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       if (in_conditional_code_or_nested_loop ||
  56           current_assignment->condition != NULL) {
  57          this->conditional_or_nested_assignment = true;
  58       }
  59
  60       if (this->first_assignment == NULL) {
  61          assert(this->num_assignments == 0);
  62
  63          this->first_assignment = current_assignment;
  64       }
  65
  66       this->num_assignments++;
  67    } else if (this->first_assignment == current_assignment) {
  68       /* This catches the case where the variable is used in the RHS of an
  69        * assignment where it is also in the LHS.
  70        */
  71       this->read_before_write = true;
  72    }
  73 }
  74
  75
  76 loop_state::loop_state()
  77 {
  78    this->ht = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
  79                                       _mesa_key_pointer_equal);
  80    this->mem_ctx = ralloc_context(NULL);
  81    this->loop_found = false;
  82 }
  83
  84
  85 loop_state::~loop_state()
  86 {
  87    _mesa_hash_table_destroy(this->ht, NULL);
  88    ralloc_free(this->mem_ctx);
  89 }
  90
  91
  92 loop_variable_state *
  93 loop_state::insert(ir_loop *ir)
  94 {
  95    loop_variable_state *ls = new(this->mem_ctx) loop_variable_state;
  96
  97    _mesa_hash_table_insert(this->ht, ir, ls);
  98    this->loop_found = true;
  99
 100    return ls;
 101 }
 102
 103
 104 loop_variable_state *
 105 loop_state::get(const ir_loop *ir)
 106 {
 107    hash_entry *entry = _mesa_hash_table_search(this->ht, ir);
 108    return entry ? (loop_variable_state *) entry->data : NULL;
 109 }
 110
 111
 112 loop_variable *
 113 loop_variable_state::get(const ir_variable *ir)
 114 {
 115    hash_entry *entry = _mesa_hash_table_search(this->var_hash, ir);
 116    return entry ? (loop_variable *) entry->data : NULL;
 117 }
 118
 119
 120 loop_variable *
 121 loop_variable_state::insert(ir_variable *var)
 122 {
 123    void *mem_ctx = ralloc_parent(this);
 124    loop_variable *lv = rzalloc(mem_ctx, loop_variable);
 125
 126    lv->var = var;
 127
 128    _mesa_hash_table_insert(this->var_hash, lv->var, lv);
 129    this->variables.push_tail(lv);
 130
 131    return lv;
 132 }
 133
 134
 135 loop_terminator *
 136 loop_variable_state::insert(ir_if *if_stmt)
 137 {
 138    void *mem_ctx = ralloc_parent(this);
 139    loop_terminator *t = new(mem_ctx) loop_terminator();
 140
 141    t->ir = if_stmt;
 142    this->terminators.push_tail(t);
 143
 144    return t;
 145 }
 146
 147
 148 /**
 149  * If the given variable already is recorded in the state for this loop,
 150  * return the corresponding loop_variable object that records information
 151  * about it.
 152  *
 153  * Otherwise, create a new loop_variable object to record information about
 154  * the variable, and set its \c read_before_write field appropriately based on
 155  * \c in_assignee.
 156  *
 157  * \arg in_assignee is true if this variable was encountered on the LHS of an
 158  * assignment.
 159  */
 160 loop_variable *
 161 loop_variable_state::get_or_insert(ir_variable *var, bool in_assignee)
 162 {
 163    loop_variable *lv = this->get(var);
 164
 165    if (lv == NULL) {
 166       lv = this->insert(var);
 167       lv->read_before_write = !in_assignee;
 168    }
 169
 170    return lv;
 171 }
 172
 173
 174 namespace {
 175
 176 class loop_analysis : public ir_hierarchical_visitor {
 177 public:
 178    loop_analysis(loop_state *loops);
 179
 180    virtual ir_visitor_status visit(ir_loop_jump *);
 181    virtual ir_visitor_status visit(ir_dereference_variable *);
 182
 183    virtual ir_visitor_status visit_enter(ir_call *);
 184
 185    virtual ir_visitor_status visit_enter(ir_loop *);
 186    virtual ir_visitor_status visit_leave(ir_loop *);
 187    virtual ir_visitor_status visit_enter(ir_assignment *);
 188    virtual ir_visitor_status visit_leave(ir_assignment *);
 189    virtual ir_visitor_status visit_enter(ir_if *);
 190    virtual ir_visitor_status visit_leave(ir_if *);
 191
 192    loop_state *loops;
 193
 194    int if_statement_depth;
 195
 196    ir_assignment *current_assignment;
 197
 198    exec_list state;
 199 };
 200
 201 } /* anonymous namespace */
 202
 203 loop_analysis::loop_analysis(loop_state *loops)
 204    : loops(loops), if_statement_depth(0), current_assignment(NULL)
 205 {
 206    /* empty */
 207 }
 208
 209
 210 ir_visitor_status
 211 loop_analysis::visit(ir_loop_jump *ir)
 212 {
 213    (void) ir;
 214
 215    assert(!this->state.is_empty());
 216
 217    loop_variable_state *const ls =
 218       (loop_variable_state *) this->state.get_head();
 219
 220    ls->num_loop_jumps++;
 221
 222    return visit_continue;
 223 }
 224
 225
 226 ir_visitor_status
 227 loop_analysis::visit_enter(ir_call *)
 228 {
 229    /* Mark every loop that we're currently analyzing as containing an ir_call
 230     * (even those at outer nesting levels).
 231     */
 232    foreach_in_list(loop_variable_state, ls, &this->state) {
 233       ls->contains_calls = true;
 234    }
 235
 236    return visit_continue_with_parent;
 237 }
 238
 239
 240 ir_visitor_status
 241 loop_analysis::visit(ir_dereference_variable *ir)
 242 {
 243    /* If we're not somewhere inside a loop, there's nothing to do.
 244     */
 245    if (this->state.is_empty())
 246       return visit_continue;
 247
 248    bool nested = false;
 249
 250    foreach_in_list(loop_variable_state, ls, &this->state) {
 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_in_list(ir_instruction, node, &ir->body_instructions) {
 291       /* Skip over declarations at the start of a loop.
 292        */
 293       if (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_in_list_safe(loop_variable, lv, &ls->variables) {
 306       /* Move variables that are already marked as being loop constant to
 307        * a separate list.  These trivially don't need to be tested.
 308        */
 309       if (lv->is_loop_constant()) {
 310          lv->remove();
 311          ls->constants.push_tail(lv);
 312       }
 313    }
 314
 315    /* Each variable assigned in the loop that isn't already marked as being loop
 316     * constant might still be loop constant.  The requirements at this point
 317     * are:
 318     *
 319     *    - Variable is written before it is read.
 320     *
 321     *    - Only one assignment to the variable.
 322     *
 323     *    - All operands on the RHS of the assignment are also loop constants.
 324     *
 325     * The last requirement is the reason for the progress loop.  A variable
 326     * marked as a loop constant on one pass may allow other variables to be
 327     * marked as loop constant on following passes.
 328     */
 329    bool progress;
 330    do {
 331       progress = false;
 332
 333       foreach_in_list_safe(loop_variable, lv, &ls->variables) {
 334          if (lv->conditional_or_nested_assignment || (lv->num_assignments > 1))
 335             continue;
 336
 337          /* Process the RHS of the assignment.  If all of the variables
 338           * accessed there are loop constants, then add this
 339           */
 340          ir_rvalue *const rhs = lv->first_assignment->rhs;
 341          if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) {
 342             lv->rhs_clean = true;
 343
 344             if (lv->is_loop_constant()) {
 345                progress = true;
 346
 347                lv->remove();
 348                ls->constants.push_tail(lv);
 349             }
 350          }
 351       }
 352    } while (progress);
 353
 354    /* The remaining variables that are not loop invariant might be loop
 355     * induction variables.
 356     */
 357    foreach_in_list_safe(loop_variable, lv, &ls->variables) {
 358       /* If there is more than one assignment to a variable, it cannot be a
 359        * loop induction variable.  This isn't strictly true, but this is a
 360        * very simple induction variable detector, and it can't handle more
 361        * complex cases.
 362        */
 363       if (lv->num_assignments > 1)
 364          continue;
 365
 366       /* All of the variables with zero assignments in the loop are loop
 367        * invariant, and they should have already been filtered out.
 368        */
 369       assert(lv->num_assignments == 1);
 370       assert(lv->first_assignment != NULL);
 371
 372       /* The assignment to the variable in the loop must be unconditional and
 373        * not inside a nested loop.
 374        */
 375       if (lv->conditional_or_nested_assignment)
 376          continue;
 377
 378       /* Basic loop induction variables have a single assignment in the loop
 379        * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a
 380        * loop invariant.
 381        */
 382       ir_rvalue *const inc =
 383          get_basic_induction_increment(lv->first_assignment, ls->var_hash);
 384       if (inc != NULL) {
 385          lv->increment = inc;
 386
 387          lv->remove();
 388          ls->induction_variables.push_tail(lv);
 389       }
 390    }
 391
 392    /* Search the loop terminating conditions for those of the form 'i < c'
 393     * where i is a loop induction variable, c is a constant, and < is any
 394     * relative operator.  From each of these we can infer an iteration count.
 395     * Also figure out which terminator (if any) produces the smallest
 396     * iteration count--this is the limiting terminator.
 397     */
 398    foreach_in_list(loop_terminator, t, &ls->terminators) {
 399       ir_if *if_stmt = t->ir;
 400
 401       /* If-statements can be either 'if (expr)' or 'if (deref)'.  We only care
 402        * about the former here.
 403        */
 404       ir_expression *cond = if_stmt->condition->as_expression();
 405       if (cond == NULL)
 406          continue;
 407
 408       switch (cond->operation) {
 409       case ir_binop_less:
 410       case ir_binop_greater:
 411       case ir_binop_lequal:
 412       case ir_binop_gequal: {
 413          /* The expressions that we care about will either be of the form
 414           * 'counter < limit' or 'limit < counter'.  Figure out which is
 415           * which.
 416           */
 417          ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
 418          ir_constant *limit = cond->operands[1]->as_constant();
 419          enum ir_expression_operation cmp = cond->operation;
 420
 421          if (limit == NULL) {
 422             counter = cond->operands[1]->as_dereference_variable();
 423             limit = cond->operands[0]->as_constant();
 424
 425             switch (cmp) {
 426             case ir_binop_less:    cmp = ir_binop_greater; break;
 427             case ir_binop_greater: cmp = ir_binop_less;    break;
 428             case ir_binop_lequal:  cmp = ir_binop_gequal;  break;
 429             case ir_binop_gequal:  cmp = ir_binop_lequal;  break;
 430             default: assert(!"Should not get here.");
 431             }
 432          }
 433
 434          if ((counter == NULL) || (limit == NULL))
 435             break;
 436
 437          ir_variable *var = counter->variable_referenced();
 438
 439          ir_rvalue *init = find_initial_value(ir, var);
 440
 441          loop_variable *lv = ls->get(var);
 442          if (lv != NULL && lv->is_induction_var()) {
 443             t->iterations = calculate_iterations(init, limit, lv->increment,
 444                                                  cmp);
 445
 446             if (t->iterations >= 0 &&
 447                 (ls->limiting_terminator == NULL ||
 448                  t->iterations < ls->limiting_terminator->iterations)) {
 449                ls->limiting_terminator = t;
 450             }
 451          }
 452          break;
 453       }
 454
 455       default:
 456          break;
 457       }
 458    }
 459
 460    return visit_continue;
 461 }
 462
 463 ir_visitor_status
 464 loop_analysis::visit_enter(ir_if *ir)
 465 {
 466    (void) ir;
 467
 468    if (!this->state.is_empty())
 469       this->if_statement_depth++;
 470
 471    return visit_continue;
 472 }
 473
 474 ir_visitor_status
 475 loop_analysis::visit_leave(ir_if *ir)
 476 {
 477    (void) ir;
 478
 479    if (!this->state.is_empty())
 480       this->if_statement_depth--;
 481
 482    return visit_continue;
 483 }
 484
 485 ir_visitor_status
 486 loop_analysis::visit_enter(ir_assignment *ir)
 487 {
 488    /* If we're not somewhere inside a loop, there's nothing to do.
 489     */
 490    if (this->state.is_empty())
 491       return visit_continue_with_parent;
 492
 493    this->current_assignment = ir;
 494
 495    return visit_continue;
 496 }
 497
 498 ir_visitor_status
 499 loop_analysis::visit_leave(ir_assignment *ir)
 500 {
 501    /* Since the visit_enter exits with visit_continue_with_parent for this
 502     * case, the loop state stack should never be empty here.
 503     */
 504    assert(!this->state.is_empty());
 505
 506    assert(this->current_assignment == ir);
 507    this->current_assignment = NULL;
 508
 509    return visit_continue;
 510 }
 511
 512
 513 class examine_rhs : public ir_hierarchical_visitor {
 514 public:
 515    examine_rhs(hash_table *loop_variables)
 516    {
 517       this->only_uses_loop_constants = true;
 518       this->loop_variables = loop_variables;
 519    }
 520
 521    virtual ir_visitor_status visit(ir_dereference_variable *ir)
 522    {
 523       hash_entry *entry = _mesa_hash_table_search(this->loop_variables,
 524                                                   ir->var);
 525       loop_variable *lv = entry ? (loop_variable *) entry->data : NULL;
 526
 527       assert(lv != NULL);
 528
 529       if (lv->is_loop_constant()) {
 530          return visit_continue;
 531       } else {
 532          this->only_uses_loop_constants = false;
 533          return visit_stop;
 534       }
 535    }
 536
 537    hash_table *loop_variables;
 538    bool only_uses_loop_constants;
 539 };
 540
 541
 542 bool
 543 all_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables)
 544 {
 545    examine_rhs v(variables);
 546
 547    ir->accept(&v);
 548
 549    return v.only_uses_loop_constants;
 550 }
 551
 552
 553 ir_rvalue *
 554 get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash)
 555 {
 556    /* The RHS must be a binary expression.
 557     */
 558    ir_expression *const rhs = ir->rhs->as_expression();
 559    if ((rhs == NULL)
 560        || ((rhs->operation != ir_binop_add)
 561            && (rhs->operation != ir_binop_sub)))
 562       return NULL;
 563
 564    /* One of the of operands of the expression must be the variable assigned.
 565     * If the operation is subtraction, the variable in question must be the
 566     * "left" operand.
 567     */
 568    ir_variable *const var = ir->lhs->variable_referenced();
 569
 570    ir_variable *const op0 = rhs->operands[0]->variable_referenced();
 571    ir_variable *const op1 = rhs->operands[1]->variable_referenced();
 572
 573    if (((op0 != var) && (op1 != var))
 574        || ((op1 == var) && (rhs->operation == ir_binop_sub)))
 575       return NULL;
 576
 577    ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0];
 578
 579    if (inc->as_constant() == NULL) {
 580       ir_variable *const inc_var = inc->variable_referenced();
 581       if (inc_var != NULL) {
 582          hash_entry *entry = _mesa_hash_table_search(var_hash, inc_var);
 583          loop_variable *lv = entry ? (loop_variable *) entry->data : NULL;
 584
 585          if (lv == NULL || !lv->is_loop_constant()) {
 586             assert(lv != NULL);
 587             inc = NULL;
 588          }
 589       } else
 590          inc = NULL;
 591    }
 592
 593    if ((inc != NULL) && (rhs->operation == ir_binop_sub)) {
 594       void *mem_ctx = ralloc_parent(ir);
 595
 596       inc = new(mem_ctx) ir_expression(ir_unop_neg,
 597                                        inc->type,
 598                                        inc->clone(mem_ctx, NULL),
 599                                        NULL);
 600    }
 601
 602    return inc;
 603 }
 604
 605
 606 /**
 607  * Detect whether an if-statement is a loop terminating condition
 608  *
 609  * Detects if-statements of the form
 610  *
 611  *  (if (expression bool ...) (break))
 612  */
 613 bool
 614 is_loop_terminator(ir_if *ir)
 615 {
 616    if (!ir->else_instructions.is_empty())
 617       return false;
 618
 619    ir_instruction *const inst =
 620       (ir_instruction *) ir->then_instructions.get_head();
 621    if (inst == NULL)
 622       return false;
 623
 624    if (inst->ir_type != ir_type_loop_jump)
 625       return false;
 626
 627    ir_loop_jump *const jump = (ir_loop_jump *) inst;
 628    if (jump->mode != ir_loop_jump::jump_break)
 629       return false;
 630
 631    return true;
 632 }
 633
 634
 635 loop_state *
 636 analyze_loop_variables(exec_list *instructions)
 637 {
 638    loop_state *loops = new loop_state;
 639    loop_analysis v(loops);
 640
 641    v.run(instructions);
 642    return v.loops;
 643 }