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