src/glsl/loop_unroll.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 namespace {
  29
  30 class loop_unroll_visitor : public ir_hierarchical_visitor {
  31 public:
  32    loop_unroll_visitor(loop_state *state, unsigned max_iterations)
  33    {
  34       this->state = state;
  35       this->progress = false;
  36       this->max_iterations = max_iterations;
  37    }
  38
  39    virtual ir_visitor_status visit_leave(ir_loop *ir);
  40
  41    loop_state *state;
  42
  43    bool progress;
  44    unsigned max_iterations;
  45 };
  46
  47 } /* anonymous namespace */
  48
  49 static bool
  50 is_break(ir_instruction *ir)
  51 {
  52    return ir != NULL && ir->ir_type == ir_type_loop_jump
  53                      && ((ir_loop_jump *) ir)->is_break();
  54 }
  55
  56 class loop_unroll_count : public ir_hierarchical_visitor {
  57 public:
  58    int nodes;
  59    bool fail;
  60
  61    loop_unroll_count(exec_list *list)
  62    {
  63       nodes = 0;
  64       fail = false;
  65
  66       run(list);
  67    }
  68
  69    virtual ir_visitor_status visit_enter(ir_assignment *ir)
  70    {
  71       nodes++;
  72       return visit_continue;
  73    }
  74
  75    virtual ir_visitor_status visit_enter(ir_expression *ir)
  76    {
  77       nodes++;
  78       return visit_continue;
  79    }
  80
  81    virtual ir_visitor_status visit_enter(ir_loop *ir)
  82    {
  83       fail = true;
  84       return visit_continue;
  85    }
  86 };
  87
  88
  89 ir_visitor_status
  90 loop_unroll_visitor::visit_leave(ir_loop *ir)
  91 {
  92    loop_variable_state *const ls = this->state->get(ir);
  93    int iterations;
  94
  95    /* If we've entered a loop that hasn't been analyzed, something really,
  96     * really bad has happened.
  97     */
  98    if (ls == NULL) {
  99       assert(ls != NULL);
 100       return visit_continue;
 101    }
 102
 103    iterations = ls->max_iterations;
 104
 105    /* Don't try to unroll loops where the number of iterations is not known
 106     * at compile-time.
 107     */
 108    if (iterations < 0)
 109       return visit_continue;
 110
 111    /* Don't try to unroll loops that have zillions of iterations either.
 112     */
 113    if (iterations > (int) max_iterations)
 114       return visit_continue;
 115
 116    /* Don't try to unroll nested loops and loops with a huge body.
 117     */
 118    loop_unroll_count count(&ir->body_instructions);
 119
 120    if (count.fail || count.nodes * iterations > (int)max_iterations * 5)
 121       return visit_continue;
 122
 123    if (ls->num_loop_jumps > 1)
 124       return visit_continue;
 125    else if (ls->num_loop_jumps) {
 126       ir_instruction *last_ir = (ir_instruction *) ir->body_instructions.get_tail();
 127       assert(last_ir != NULL);
 128
 129       if (is_break(last_ir)) {
 130          /* If the only loop-jump is a break at the end of the loop, the loop
 131           * will execute exactly once.  Remove the break, set the iteration
 132           * count, and fall through to the normal unroller.
 133           */
 134          last_ir->remove();
 135          iterations = 1;
 136
 137          this->progress = true;
 138       } else {
 139          ir_if *ir_if = NULL;
 140          ir_instruction *break_ir = NULL;
 141          bool continue_from_then_branch = false;
 142
 143          foreach_list(node, &ir->body_instructions) {
 144             /* recognize loops in the form produced by ir_lower_jumps */
 145             ir_instruction *cur_ir = (ir_instruction *) node;
 146
 147             ir_if = cur_ir->as_if();
 148             if (ir_if != NULL) {
 149                /* Determine which if-statement branch, if any, ends with a
 150                 * break.  The branch that did *not* have the break will get a
 151                 * temporary continue inserted in each iteration of the loop
 152                 * unroll.
 153                 *
 154                 * Note that since ls->num_loop_jumps is <= 1, it is impossible
 155                 * for both branches to end with a break.
 156                 */
 157                ir_instruction *ir_if_last =
 158                   (ir_instruction *) ir_if->then_instructions.get_tail();
 159
 160                if (is_break(ir_if_last)) {
 161                   continue_from_then_branch = false;
 162                   break_ir = ir_if_last;
 163                   break;
 164                } else {
 165                   ir_if_last =
 166                      (ir_instruction *) ir_if->else_instructions.get_tail();
 167
 168                   if (is_break(ir_if_last)) {
 169                      break_ir = ir_if_last;
 170                      continue_from_then_branch = true;
 171                      break;
 172                   }
 173                }
 174             }
 175          }
 176
 177          if (break_ir == NULL)
 178             return visit_continue;
 179
 180          /* move instructions after then if in the continue branch */
 181          while (!ir_if->get_next()->is_tail_sentinel()) {
 182             ir_instruction *move_ir = (ir_instruction *) ir_if->get_next();
 183
 184             move_ir->remove();
 185             if (continue_from_then_branch)
 186                ir_if->then_instructions.push_tail(move_ir);
 187             else
 188                ir_if->else_instructions.push_tail(move_ir);
 189          }
 190
 191          /* Remove the break from the if-statement.
 192           */
 193          break_ir->remove();
 194
 195          void *const mem_ctx = ralloc_parent(ir);
 196          ir_instruction *ir_to_replace = ir;
 197
 198          for (int i = 0; i < iterations; i++) {
 199             exec_list copy_list;
 200
 201             copy_list.make_empty();
 202             clone_ir_list(mem_ctx, &copy_list, &ir->body_instructions);
 203
 204             ir_if = ((ir_instruction *) copy_list.get_tail())->as_if();
 205             assert(ir_if != NULL);
 206
 207             ir_to_replace->insert_before(&copy_list);
 208             ir_to_replace->remove();
 209
 210             /* placeholder that will be removed in the next iteration */
 211             ir_to_replace =
 212                new(mem_ctx) ir_loop_jump(ir_loop_jump::jump_continue);
 213
 214             exec_list *const list = (continue_from_then_branch)
 215                ? &ir_if->then_instructions : &ir_if->else_instructions;
 216
 217             list->push_tail(ir_to_replace);
 218          }
 219
 220          ir_to_replace->remove();
 221
 222          this->progress = true;
 223          return visit_continue;
 224       }
 225    }
 226
 227    void *const mem_ctx = ralloc_parent(ir);
 228
 229    for (int i = 0; i < iterations; i++) {
 230       exec_list copy_list;
 231
 232       copy_list.make_empty();
 233       clone_ir_list(mem_ctx, &copy_list, &ir->body_instructions);
 234
 235       ir->insert_before(&copy_list);
 236    }
 237
 238    /* The loop has been replaced by the unrolled copies.  Remove the original
 239     * loop from the IR sequence.
 240     */
 241    ir->remove();
 242
 243    this->progress = true;
 244    return visit_continue;
 245 }
 246
 247
 248 bool
 249 unroll_loops(exec_list *instructions, loop_state *ls, unsigned max_iterations)
 250 {
 251    loop_unroll_visitor v(ls, max_iterations);
 252
 253    v.run(instructions);
 254
 255    return v.progress;
 256 }