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