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