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