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