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