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