src/glsl/ir_if_return.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 /**
  25  * \file ir_if_return.cpp
  26  *
  27  * This pass tries to normalize functions to always return from one
  28  * place by moving around blocks of code in if statements.
  29  *
  30  * This helps on hardware with no branching support, and may even be a
  31  * useful transform on hardware supporting control flow by turning
  32  * masked returns into normal returns.
  33  */
  34
  35 #include <string.h>
  36 #include "glsl_types.h"
  37 #include "ir.h"
  38
  39 class ir_if_return_visitor : public ir_hierarchical_visitor {
  40 public:
  41    ir_if_return_visitor()
  42    {
  43       this->progress = false;
  44    }
  45
  46    ir_visitor_status visit_enter(ir_function_signature *);
  47    ir_visitor_status visit_leave(ir_if *);
  48
  49    ir_visitor_status move_outer_block_inside(ir_instruction *ir,
  50                                              exec_list *inner_block);
  51    void move_returns_after_block(ir_instruction *ir,
  52                                  ir_return *then_return,
  53                                  ir_return *else_return);
  54    bool progress;
  55 };
  56
  57 bool
  58 do_if_return(exec_list *instructions)
  59 {
  60    ir_if_return_visitor v;
  61
  62    do {
  63       v.progress = false;
  64       visit_list_elements(&v, instructions);
  65    } while (v.progress);
  66
  67    return v.progress;
  68 }
  69
  70 /**
  71  * Removes any instructions after a (unconditional) return, since they will
  72  * never be executed.
  73  */
  74 static void
  75 truncate_after_instruction(ir_instruction *ir)
  76 {
  77    if (!ir)
  78       return;
  79
  80    while (!ir->get_next()->is_tail_sentinel())
  81       ((ir_instruction *)ir->get_next())->remove();
  82 }
  83
  84 /**
  85  * Returns an ir_instruction of the first ir_return in the exec_list, or NULL.
  86  */
  87 static ir_return *
  88 find_return_in_block(exec_list *instructions)
  89 {
  90    foreach_iter(exec_list_iterator, iter, *instructions) {
  91       ir_instruction *ir = (ir_instruction *)iter.get();
  92       if (ir->ir_type == ir_type_return)
  93          return (ir_return *)ir;
  94    }
  95
  96    return NULL;
  97 }
  98
  99 void
 100 ir_if_return_visitor::move_returns_after_block(ir_instruction *ir,
 101                                                ir_return *then_return,
 102                                                ir_return *else_return)
 103 {
 104
 105    if (!then_return->value) {
 106       then_return->remove();
 107       else_return->remove();
 108       ir->insert_after(new(ir) ir_return(NULL));
 109    } else {
 110       ir_assignment *assign;
 111       ir_variable *new_var = new(ir) ir_variable(then_return->value->type,
 112                                                  "if_return_tmp",
 113                                                  ir_var_temporary);
 114       ir->insert_before(new_var);
 115
 116       assign = new(ir) ir_assignment(new(ir) ir_dereference_variable(new_var),
 117                                      then_return->value, NULL);
 118       then_return->replace_with(assign);
 119
 120       assign = new(ir) ir_assignment(new(ir) ir_dereference_variable(new_var),
 121                                      else_return->value, NULL);
 122       else_return->replace_with(assign);
 123
 124       ir_dereference_variable *deref = new(ir) ir_dereference_variable(new_var);
 125       ir->insert_after(new(ir) ir_return(deref));
 126    }
 127    this->progress = true;
 128 }
 129
 130 ir_visitor_status
 131 ir_if_return_visitor::move_outer_block_inside(ir_instruction *ir,
 132                                               exec_list *inner_block)
 133 {
 134    if (!ir->get_next()->is_tail_sentinel()) {
 135       while (!ir->get_next()->is_tail_sentinel()) {
 136          ir_instruction *move_ir = (ir_instruction *)ir->get_next();
 137
 138          move_ir->remove();
 139          inner_block->push_tail(move_ir);
 140       }
 141
 142       /* If we move the instructions following ir inside the block, it
 143        * will confuse the exec_list iteration in the parent that visited
 144        * us.  So stop the visit at this point.
 145        */
 146       return visit_stop;
 147    } else {
 148       return visit_continue;
 149    }
 150 }
 151
 152 /* Normalize a function to always have a return statement at the end.
 153  *
 154  * This avoids the ir_if handler needing to know whether it is at the
 155  * top level of the function to know if there's an implicit return at
 156  * the end of the outer block.
 157  */
 158 ir_visitor_status
 159 ir_if_return_visitor::visit_enter(ir_function_signature *ir)
 160 {
 161    ir_return *ret;
 162
 163    if (!ir->is_defined)
 164       return visit_continue_with_parent;
 165    if (strcmp(ir->function_name(), "main") == 0)
 166       return visit_continue_with_parent;
 167
 168    ret = find_return_in_block(&ir->body);
 169
 170    if (ret) {
 171       truncate_after_instruction(ret);
 172    } else {
 173       if (ir->return_type->is_void()) {
 174          ir->body.push_tail(new(ir) ir_return(NULL));
 175       } else {
 176          /* Probably, if we've got a function with a return value
 177           * hitting this point, it's something like:
 178           *
 179           * float reduce_below_half(float val)
 180           * {
 181           *         while () {
 182           *                 if (val >= 0.5)
 183           *                         val /= 2.0;
 184           *                 else
 185           *                         return val;
 186           *         }
 187           * }
 188           *
 189           * So we gain a junk return statement of an undefined value
 190           * at the end that never gets executed.  However, a backend
 191           * using this pass is probably desperate to get rid of
 192           * function calls, so go ahead and do it for their sake in
 193           * case it fixes apps.
 194           */
 195          ir_variable *undef = new(ir) ir_variable(ir->return_type,
 196                                                   "if_return_undef",
 197                                                   ir_var_temporary);
 198          ir->body.push_tail(undef);
 199
 200          ir_dereference_variable *deref = new(ir) ir_dereference_variable(undef);
 201          ir->body.push_tail(new(ir) ir_return(deref));
 202       }
 203    }
 204
 205    return visit_continue;
 206 }
 207
 208 ir_visitor_status
 209 ir_if_return_visitor::visit_leave(ir_if *ir)
 210 {
 211    ir_return *then_return;
 212    ir_return *else_return;
 213
 214    then_return = find_return_in_block(&ir->then_instructions);
 215    else_return = find_return_in_block(&ir->else_instructions);
 216    if (!then_return && !else_return)
 217       return visit_continue;
 218
 219    /* Trim off any trailing instructions after the return statements
 220     * on both sides.
 221     */
 222    truncate_after_instruction(then_return);
 223    truncate_after_instruction(else_return);
 224
 225    /* If both sides return, then we can move the returns to a single
 226     * one outside the if statement.
 227     */
 228    if (then_return && else_return) {
 229       move_returns_after_block(ir, then_return, else_return);
 230       return visit_continue;
 231    }
 232
 233    /* If only one side returns, then the block of code after the "if"
 234     * is only executed by the other side, so those instructions don't
 235     * need to be anywhere but that other side.
 236     *
 237     * This will usually pull a return statement up into the other
 238     * side, so we'll trigger the above case on the next pass.
 239     */
 240    if (then_return) {
 241       return move_outer_block_inside(ir, &ir->else_instructions);
 242    } else {
 243       assert(else_return);
 244       return move_outer_block_inside(ir, &ir->then_instructions);
 245    }
 246 }