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    void simple_unroll(ir_loop *ir, int iterations);
  41    void complex_unroll(ir_loop *ir, int iterations,
  42                        bool continue_from_then_branch);
  43    void splice_post_if_instructions(ir_if *ir_if, exec_list *splice_dest);
  44
  45    loop_state *state;
  46
  47    bool progress;
  48    unsigned max_iterations;
  49 };
  50
  51 } /* anonymous namespace */
  52
  53 static bool
  54 is_break(ir_instruction *ir)
  55 {
  56    return ir != NULL && ir->ir_type == ir_type_loop_jump
  57                      && ((ir_loop_jump *) ir)->is_break();
  58 }
  59
  60 class loop_unroll_count : public ir_hierarchical_visitor {
  61 public:
  62    int nodes;
  63    bool fail;
  64
  65    loop_unroll_count(exec_list *list)
  66    {
  67       nodes = 0;
  68       fail = false;
  69
  70       run(list);
  71    }
  72
  73    virtual ir_visitor_status visit_enter(ir_assignment *ir)
  74    {
  75       nodes++;
  76       return visit_continue;
  77    }
  78
  79    virtual ir_visitor_status visit_enter(ir_expression *ir)
  80    {
  81       nodes++;
  82       return visit_continue;
  83    }
  84
  85    virtual ir_visitor_status visit_enter(ir_loop *ir)
  86    {
  87       fail = true;
  88       return visit_continue;
  89    }
  90 };
  91
  92
  93 /**
  94  * Unroll a loop which does not contain any jumps.  For example, if the input
  95  * is:
  96  *
  97  *     (loop (...) ...instrs...)
  98  *
  99  * And the iteration count is 3, the output will be:
 100  *
 101  *     ...instrs... ...instrs... ...instrs...
 102  */
 103 void
 104 loop_unroll_visitor::simple_unroll(ir_loop *ir, int iterations)
 105 {
 106    void *const mem_ctx = ralloc_parent(ir);
 107
 108    for (int i = 0; i < iterations; i++) {
 109       exec_list copy_list;
 110
 111       copy_list.make_empty();
 112       clone_ir_list(mem_ctx, &copy_list, &ir->body_instructions);
 113
 114       ir->insert_before(&copy_list);
 115    }
 116
 117    /* The loop has been replaced by the unrolled copies.  Remove the original
 118     * loop from the IR sequence.
 119     */
 120    ir->remove();
 121
 122    this->progress = true;
 123 }
 124
 125
 126 /**
 127  * Unroll a loop whose last statement is an ir_if.  If \c
 128  * continue_from_then_branch is true, the loop is repeated only when the
 129  * "then" branch of the if is taken; otherwise it is repeated only when the
 130  * "else" branch of the if is taken.
 131  *
 132  * For example, if the input is:
 133  *
 134  *     (loop (...)
 135  *      ...body...
 136  *      (if (cond)
 137  *          (...then_instrs...)
 138  *        (...else_instrs...)))
 139  *
 140  * And the iteration count is 3, and \c continue_from_then_branch is true,
 141  * then the output will be:
 142  *
 143  *     ...body...
 144  *     (if (cond)
 145  *         (...then_instrs...
 146  *          ...body...
 147  *          (if (cond)
 148  *              (...then_instrs...
 149  *               ...body...
 150  *               (if (cond)
 151  *                   (...then_instrs...)
 152  *                 (...else_instrs...)))
 153  *            (...else_instrs...)))
 154  *       (...else_instrs))
 155  */
 156 void
 157 loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations,
 158                                     bool continue_from_then_branch)
 159 {
 160    void *const mem_ctx = ralloc_parent(ir);
 161    ir_instruction *ir_to_replace = ir;
 162
 163    for (int i = 0; i < iterations; i++) {
 164       exec_list copy_list;
 165
 166       copy_list.make_empty();
 167       clone_ir_list(mem_ctx, &copy_list, &ir->body_instructions);
 168
 169       ir_if *ir_if = ((ir_instruction *) copy_list.get_tail())->as_if();
 170       assert(ir_if != NULL);
 171
 172       ir_to_replace->insert_before(&copy_list);
 173       ir_to_replace->remove();
 174
 175       /* placeholder that will be removed in the next iteration */
 176       ir_to_replace =
 177          new(mem_ctx) ir_loop_jump(ir_loop_jump::jump_continue);
 178
 179       exec_list *const list = (continue_from_then_branch)
 180          ? &ir_if->then_instructions : &ir_if->else_instructions;
 181
 182       list->push_tail(ir_to_replace);
 183    }
 184
 185    ir_to_replace->remove();
 186
 187    this->progress = true;
 188 }
 189
 190
 191 /**
 192  * Move all of the instructions which follow \c ir_if to the end of
 193  * \c splice_dest.
 194  *
 195  * For example, in the code snippet:
 196  *
 197  *     (if (cond)
 198  *         (...then_instructions...
 199  *          break)
 200  *       (...else_instructions...))
 201  *     ...post_if_instructions...
 202  *
 203  * If \c ir_if points to the "if" instruction, and \c splice_dest points to
 204  * (...else_instructions...), the code snippet is transformed into:
 205  *
 206  *     (if (cond)
 207  *         (...then_instructions...
 208  *          break)
 209  *       (...else_instructions...
 210  *        ...post_if_instructions...))
 211  */
 212 void
 213 loop_unroll_visitor::splice_post_if_instructions(ir_if *ir_if,
 214                                                  exec_list *splice_dest)
 215 {
 216    while (!ir_if->get_next()->is_tail_sentinel()) {
 217       ir_instruction *move_ir = (ir_instruction *) ir_if->get_next();
 218
 219       move_ir->remove();
 220       splice_dest->push_tail(move_ir);
 221    }
 222 }
 223
 224
 225 ir_visitor_status
 226 loop_unroll_visitor::visit_leave(ir_loop *ir)
 227 {
 228    loop_variable_state *const ls = this->state->get(ir);
 229    int iterations;
 230
 231    /* If we've entered a loop that hasn't been analyzed, something really,
 232     * really bad has happened.
 233     */
 234    if (ls == NULL) {
 235       assert(ls != NULL);
 236       return visit_continue;
 237    }
 238
 239    /* Don't try to unroll loops where the number of iterations is not known
 240     * at compile-time.
 241     */
 242    if (ls->limiting_terminator == NULL)
 243       return visit_continue;
 244
 245    iterations = ls->limiting_terminator->iterations;
 246
 247    /* Don't try to unroll loops that have zillions of iterations either.
 248     */
 249    if (iterations > (int) max_iterations)
 250       return visit_continue;
 251
 252    /* Don't try to unroll nested loops and loops with a huge body.
 253     */
 254    loop_unroll_count count(&ir->body_instructions);
 255
 256    if (count.fail || count.nodes * iterations > (int)max_iterations * 5)
 257       return visit_continue;
 258
 259    /* Note: the limiting terminator contributes 1 to ls->num_loop_jumps.
 260     * We'll be removing the limiting terminator before we unroll.
 261     */
 262    assert(ls->num_loop_jumps > 0);
 263    unsigned predicted_num_loop_jumps = ls->num_loop_jumps - 1;
 264
 265    if (predicted_num_loop_jumps > 1)
 266       return visit_continue;
 267
 268    if (predicted_num_loop_jumps == 0) {
 269       ls->limiting_terminator->ir->remove();
 270       simple_unroll(ir, iterations);
 271       return visit_continue;
 272    }
 273
 274    ir_instruction *last_ir = (ir_instruction *) ir->body_instructions.get_tail();
 275    assert(last_ir != NULL);
 276
 277    if (is_break(last_ir)) {
 278       /* If the only loop-jump is a break at the end of the loop, the loop
 279        * will execute exactly once.  Remove the break and use the simple
 280        * unroller with an iteration count of 1.
 281        */
 282       last_ir->remove();
 283
 284       ls->limiting_terminator->ir->remove();
 285       simple_unroll(ir, 1);
 286       return visit_continue;
 287    }
 288
 289    foreach_list(node, &ir->body_instructions) {
 290       /* recognize loops in the form produced by ir_lower_jumps */
 291       ir_instruction *cur_ir = (ir_instruction *) node;
 292
 293       /* Skip the limiting terminator, since it will go away when we
 294        * unroll.
 295        */
 296       if (cur_ir == ls->limiting_terminator->ir)
 297          continue;
 298
 299       ir_if *ir_if = cur_ir->as_if();
 300       if (ir_if != NULL) {
 301          /* Determine which if-statement branch, if any, ends with a
 302           * break.  The branch that did *not* have the break will get a
 303           * temporary continue inserted in each iteration of the loop
 304           * unroll.
 305           *
 306           * Note that since ls->num_loop_jumps is <= 1, it is impossible
 307           * for both branches to end with a break.
 308           */
 309          ir_instruction *ir_if_last =
 310             (ir_instruction *) ir_if->then_instructions.get_tail();
 311
 312          if (is_break(ir_if_last)) {
 313             ls->limiting_terminator->ir->remove();
 314             splice_post_if_instructions(ir_if, &ir_if->else_instructions);
 315             ir_if_last->remove();
 316             complex_unroll(ir, iterations, false);
 317             return visit_continue;
 318          } else {
 319             ir_if_last =
 320                (ir_instruction *) ir_if->else_instructions.get_tail();
 321
 322             if (is_break(ir_if_last)) {
 323                ls->limiting_terminator->ir->remove();
 324                splice_post_if_instructions(ir_if, &ir_if->then_instructions);
 325                ir_if_last->remove();
 326                complex_unroll(ir, iterations, true);
 327                return visit_continue;
 328             }
 329          }
 330       }
 331    }
 332
 333    /* Did not find the break statement.  It must be in a complex if-nesting,
 334     * so don't try to unroll.
 335     */
 336    return visit_continue;
 337 }
 338
 339
 340 bool
 341 unroll_loops(exec_list *instructions, loop_state *ls, unsigned max_iterations)
 342 {
 343    loop_unroll_visitor v(ls, max_iterations);
 344
 345    v.run(instructions);
 346
 347    return v.progress;
 348 }