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