"Fossies" - the Fresh Open Source Software Archive

Member "mesa-20.1.8/src/compiler/glsl/lower_jumps.cpp" (16 Sep 2020, 39712 Bytes) of package /linux/misc/mesa-20.1.8.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "lower_jumps.cpp" see the Fossies "Dox" file reference documentation.

    1 /*
    2  * Copyright © 2010 Luca Barbieri
    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 lower_jumps.cpp
   26  *
   27  * This pass lowers jumps (break, continue, and return) to if/else structures.
   28  *
   29  * It can be asked to:
   30  * 1. Pull jumps out of ifs where possible
   31  * 2. Remove all "continue"s, replacing them with an "execute flag"
   32  * 3. Replace all "break" with a single conditional one at the end of the loop
   33  * 4. Replace all "return"s with a single return at the end of the function,
   34  *    for the main function and/or other functions
   35  *
   36  * Applying this pass gives several benefits:
   37  * 1. All functions can be inlined.
   38  * 2. nv40 and other pre-DX10 chips without "continue" can be supported
   39  * 3. nv30 and other pre-DX10 chips with no control flow at all are better
   40  *    supported
   41  *
   42  * Continues are lowered by adding a per-loop "execute flag", initialized to
   43  * true, that when cleared inhibits all execution until the end of the loop.
   44  *
   45  * Breaks are lowered to continues, plus setting a "break flag" that is checked
   46  * at the end of the loop, and trigger the unique "break".
   47  *
   48  * Returns are lowered to breaks/continues, plus adding a "return flag" that
   49  * causes loops to break again out of their enclosing loops until all the
   50  * loops are exited: then the "execute flag" logic will ignore everything
   51  * until the end of the function.
   52  *
   53  * Note that "continue" and "return" can also be implemented by adding
   54  * a dummy loop and using break.
   55  * However, this is bad for hardware with limited nesting depth, and
   56  * prevents further optimization, and thus is not currently performed.
   57  */
   58 
   59 #include "compiler/glsl_types.h"
   60 #include <string.h>
   61 #include "ir.h"
   62 
   63 /**
   64  * Enum recording the result of analyzing how control flow might exit
   65  * an IR node.
   66  *
   67  * Each possible value of jump_strength indicates a strictly stronger
   68  * guarantee on control flow than the previous value.
   69  *
   70  * The ordering of strengths roughly reflects the way jumps are
   71  * lowered: jumps with higher strength tend to be lowered to jumps of
   72  * lower strength.  Accordingly, strength is used as a heuristic to
   73  * determine which lowering to perform first.
   74  *
   75  * This enum is also used by get_jump_strength() to categorize
   76  * instructions as either break, continue, return, or other.  When
   77  * used in this fashion, strength_always_clears_execute_flag is not
   78  * used.
   79  *
   80  * The control flow analysis made by this optimization pass makes two
   81  * simplifying assumptions:
   82  *
   83  * - It ignores discard instructions, since they are lowered by a
   84  *   separate pass (lower_discard.cpp).
   85  *
   86  * - It assumes it is always possible for control to flow from a loop
   87  *   to the instruction immediately following it.  Technically, this
   88  *   is not true (since all execution paths through the loop might
   89  *   jump back to the top, or return from the function).
   90  *
   91  * Both of these simplifying assumtions are safe, since they can never
   92  * cause reachable code to be incorrectly classified as unreachable;
   93  * they can only do the opposite.
   94  */
   95 enum jump_strength
   96 {
   97    /**
   98     * Analysis has produced no guarantee on how control flow might
   99     * exit this IR node.  It might fall out the bottom (with or
  100     * without clearing the execute flag, if present), or it might
  101     * continue to the top of the innermost enclosing loop, break out
  102     * of it, or return from the function.
  103     */
  104    strength_none,
  105 
  106    /**
  107     * The only way control can fall out the bottom of this node is
  108     * through a code path that clears the execute flag.  It might also
  109     * continue to the top of the innermost enclosing loop, break out
  110     * of it, or return from the function.
  111     */
  112    strength_always_clears_execute_flag,
  113 
  114    /**
  115     * Control cannot fall out the bottom of this node.  It might
  116     * continue to the top of the innermost enclosing loop, break out
  117     * of it, or return from the function.
  118     */
  119    strength_continue,
  120 
  121    /**
  122     * Control cannot fall out the bottom of this node, or continue the
  123     * top of the innermost enclosing loop.  It can only break out of
  124     * it or return from the function.
  125     */
  126    strength_break,
  127 
  128    /**
  129     * Control cannot fall out the bottom of this node, continue to the
  130     * top of the innermost enclosing loop, or break out of it.  It can
  131     * only return from the function.
  132     */
  133    strength_return
  134 };
  135 
  136 namespace {
  137 
  138 struct block_record
  139 {
  140    /* minimum jump strength (of lowered IR, not pre-lowering IR)
  141     *
  142     * If the block ends with a jump, must be the strength of the jump.
  143     * Otherwise, the jump would be dead and have been deleted before)
  144     *
  145     * If the block doesn't end with a jump, it can be different than strength_none if all paths before it lead to some jump
  146     * (e.g. an if with a return in one branch, and a break in the other, while not lowering them)
  147     * Note that identical jumps are usually unified though.
  148     */
  149    jump_strength min_strength;
  150 
  151    /* can anything clear the execute flag? */
  152    bool may_clear_execute_flag;
  153 
  154    block_record()
  155    {
  156       this->min_strength = strength_none;
  157       this->may_clear_execute_flag = false;
  158    }
  159 };
  160 
  161 struct loop_record
  162 {
  163    ir_function_signature* signature;
  164    ir_loop* loop;
  165 
  166    /* used to avoid lowering the break used to represent lowered breaks */
  167    unsigned nesting_depth;
  168    bool in_if_at_the_end_of_the_loop;
  169 
  170    bool may_set_return_flag;
  171 
  172    ir_variable* break_flag;
  173    ir_variable* execute_flag; /* cleared to emulate continue */
  174 
  175    loop_record(ir_function_signature* p_signature = 0, ir_loop* p_loop = 0)
  176    {
  177       this->signature = p_signature;
  178       this->loop = p_loop;
  179       this->nesting_depth = 0;
  180       this->in_if_at_the_end_of_the_loop = false;
  181       this->may_set_return_flag = false;
  182       this->break_flag = 0;
  183       this->execute_flag = 0;
  184    }
  185 
  186    ir_variable* get_execute_flag()
  187    {
  188       /* also supported for the "function loop" */
  189       if(!this->execute_flag) {
  190          exec_list& list = this->loop ? this->loop->body_instructions : signature->body;
  191          this->execute_flag = new(this->signature) ir_variable(glsl_type::bool_type, "execute_flag", ir_var_temporary);
  192          list.push_head(new(this->signature) ir_assignment(new(this->signature) ir_dereference_variable(execute_flag), new(this->signature) ir_constant(true)));
  193          list.push_head(this->execute_flag);
  194       }
  195       return this->execute_flag;
  196    }
  197 
  198    ir_variable* get_break_flag()
  199    {
  200       assert(this->loop);
  201       if(!this->break_flag) {
  202          this->break_flag = new(this->signature) ir_variable(glsl_type::bool_type, "break_flag", ir_var_temporary);
  203          this->loop->insert_before(this->break_flag);
  204          this->loop->insert_before(new(this->signature) ir_assignment(new(this->signature) ir_dereference_variable(break_flag), new(this->signature) ir_constant(false)));
  205       }
  206       return this->break_flag;
  207    }
  208 };
  209 
  210 struct function_record
  211 {
  212    ir_function_signature* signature;
  213    ir_variable* return_flag; /* used to break out of all loops and then jump to the return instruction */
  214    ir_variable* return_value;
  215    bool lower_return;
  216    unsigned nesting_depth;
  217 
  218    function_record(ir_function_signature* p_signature = 0,
  219                    bool lower_return = false)
  220    {
  221       this->signature = p_signature;
  222       this->return_flag = 0;
  223       this->return_value = 0;
  224       this->nesting_depth = 0;
  225       this->lower_return = lower_return;
  226    }
  227 
  228    ir_variable* get_return_flag()
  229    {
  230       if(!this->return_flag) {
  231          this->return_flag = new(this->signature) ir_variable(glsl_type::bool_type, "return_flag", ir_var_temporary);
  232          this->signature->body.push_head(new(this->signature) ir_assignment(new(this->signature) ir_dereference_variable(return_flag), new(this->signature) ir_constant(false)));
  233          this->signature->body.push_head(this->return_flag);
  234       }
  235       return this->return_flag;
  236    }
  237 
  238    ir_variable* get_return_value()
  239    {
  240       if(!this->return_value) {
  241          assert(!this->signature->return_type->is_void());
  242          return_value = new(this->signature) ir_variable(this->signature->return_type, "return_value", ir_var_temporary);
  243          this->signature->body.push_head(this->return_value);
  244       }
  245       return this->return_value;
  246    }
  247 };
  248 
  249 struct ir_lower_jumps_visitor : public ir_control_flow_visitor {
  250    /* Postconditions: on exit of any visit() function:
  251     *
  252     * ANALYSIS: this->block.min_strength,
  253     * this->block.may_clear_execute_flag, and
  254     * this->loop.may_set_return_flag are updated to reflect the
  255     * characteristics of the visited statement.
  256     *
  257     * DEAD_CODE_ELIMINATION: If this->block.min_strength is not
  258     * strength_none, the visited node is at the end of its exec_list.
  259     * In other words, any unreachable statements that follow the
  260     * visited statement in its exec_list have been removed.
  261     *
  262     * CONTAINED_JUMPS_LOWERED: If the visited statement contains other
  263     * statements, then should_lower_jump() is false for all of the
  264     * return, break, or continue statements it contains.
  265     *
  266     * Note that visiting a jump does not lower it.  That is the
  267     * responsibility of the statement (or function signature) that
  268     * contains the jump.
  269     */
  270 
  271    using ir_control_flow_visitor::visit;
  272 
  273    bool progress;
  274 
  275    struct function_record function;
  276    struct loop_record loop;
  277    struct block_record block;
  278 
  279    bool pull_out_jumps;
  280    bool lower_continue;
  281    bool lower_break;
  282    bool lower_sub_return;
  283    bool lower_main_return;
  284 
  285    ir_lower_jumps_visitor()
  286       : progress(false),
  287         pull_out_jumps(false),
  288         lower_continue(false),
  289         lower_break(false),
  290         lower_sub_return(false),
  291         lower_main_return(false)
  292    {
  293    }
  294 
  295    void truncate_after_instruction(exec_node *ir)
  296    {
  297       if (!ir)
  298          return;
  299 
  300       while (!ir->get_next()->is_tail_sentinel()) {
  301          ((ir_instruction *)ir->get_next())->remove();
  302          this->progress = true;
  303       }
  304    }
  305 
  306    void move_outer_block_inside(ir_instruction *ir, exec_list *inner_block)
  307    {
  308       while (!ir->get_next()->is_tail_sentinel()) {
  309          ir_instruction *move_ir = (ir_instruction *)ir->get_next();
  310 
  311          move_ir->remove();
  312          inner_block->push_tail(move_ir);
  313       }
  314    }
  315 
  316    /**
  317     * Insert the instructions necessary to lower a return statement,
  318     * before the given return instruction.
  319     */
  320    void insert_lowered_return(ir_return *ir)
  321    {
  322       ir_variable* return_flag = this->function.get_return_flag();
  323       if(!this->function.signature->return_type->is_void()) {
  324          ir_variable* return_value = this->function.get_return_value();
  325          ir->insert_before(
  326             new(ir) ir_assignment(
  327                new (ir) ir_dereference_variable(return_value),
  328                ir->value));
  329       }
  330       ir->insert_before(
  331          new(ir) ir_assignment(
  332             new (ir) ir_dereference_variable(return_flag),
  333             new (ir) ir_constant(true)));
  334       this->loop.may_set_return_flag = true;
  335    }
  336 
  337    /**
  338     * If the given instruction is a return, lower it to instructions
  339     * that store the return value (if there is one), set the return
  340     * flag, and then break.
  341     *
  342     * It is safe to pass NULL to this function.
  343     */
  344    void lower_return_unconditionally(ir_instruction *ir)
  345    {
  346       if (get_jump_strength(ir) != strength_return) {
  347          return;
  348       }
  349       insert_lowered_return((ir_return*)ir);
  350       ir->replace_with(new(ir) ir_loop_jump(ir_loop_jump::jump_break));
  351    }
  352 
  353    /**
  354     * Create the necessary instruction to replace a break instruction.
  355     */
  356    ir_instruction *create_lowered_break()
  357    {
  358       void *ctx = this->function.signature;
  359       return new(ctx) ir_assignment(
  360           new(ctx) ir_dereference_variable(this->loop.get_break_flag()),
  361           new(ctx) ir_constant(true));
  362    }
  363 
  364    /**
  365     * If the given instruction is a break, lower it to an instruction
  366     * that sets the break flag, without consulting
  367     * should_lower_jump().
  368     *
  369     * It is safe to pass NULL to this function.
  370     */
  371    void lower_break_unconditionally(ir_instruction *ir)
  372    {
  373       if (get_jump_strength(ir) != strength_break) {
  374          return;
  375       }
  376       ir->replace_with(create_lowered_break());
  377    }
  378 
  379    /**
  380     * If the block ends in a conditional or unconditional break, lower
  381     * it, even though should_lower_jump() says it needn't be lowered.
  382     */
  383    void lower_final_breaks(exec_list *block)
  384    {
  385       ir_instruction *ir = (ir_instruction *) block->get_tail();
  386       lower_break_unconditionally(ir);
  387       ir_if *ir_if = ir->as_if();
  388       if (ir_if) {
  389           lower_break_unconditionally(
  390               (ir_instruction *) ir_if->then_instructions.get_tail());
  391           lower_break_unconditionally(
  392               (ir_instruction *) ir_if->else_instructions.get_tail());
  393       }
  394    }
  395 
  396    virtual void visit(class ir_loop_jump * ir)
  397    {
  398       /* Eliminate all instructions after each one, since they are
  399        * unreachable.  This satisfies the DEAD_CODE_ELIMINATION
  400        * postcondition.
  401        */
  402       truncate_after_instruction(ir);
  403 
  404       /* Set this->block.min_strength based on this instruction.  This
  405        * satisfies the ANALYSIS postcondition.  It is not necessary to
  406        * update this->block.may_clear_execute_flag or
  407        * this->loop.may_set_return_flag, because an unlowered jump
  408        * instruction can't change any flags.
  409        */
  410       this->block.min_strength = ir->is_break() ? strength_break : strength_continue;
  411 
  412       /* The CONTAINED_JUMPS_LOWERED postcondition is already
  413        * satisfied, because jump statements can't contain other
  414        * statements.
  415        */
  416    }
  417 
  418    virtual void visit(class ir_return * ir)
  419    {
  420       /* Eliminate all instructions after each one, since they are
  421        * unreachable.  This satisfies the DEAD_CODE_ELIMINATION
  422        * postcondition.
  423        */
  424       truncate_after_instruction(ir);
  425 
  426       /* Set this->block.min_strength based on this instruction.  This
  427        * satisfies the ANALYSIS postcondition.  It is not necessary to
  428        * update this->block.may_clear_execute_flag or
  429        * this->loop.may_set_return_flag, because an unlowered return
  430        * instruction can't change any flags.
  431        */
  432       this->block.min_strength = strength_return;
  433 
  434       /* The CONTAINED_JUMPS_LOWERED postcondition is already
  435        * satisfied, because jump statements can't contain other
  436        * statements.
  437        */
  438    }
  439 
  440    virtual void visit(class ir_discard * ir)
  441    {
  442       /* Nothing needs to be done.  The ANALYSIS and
  443        * DEAD_CODE_ELIMINATION postconditions are already satisfied,
  444        * because discard statements are ignored by this optimization
  445        * pass.  The CONTAINED_JUMPS_LOWERED postcondition is already
  446        * satisfied, because discard statements can't contain other
  447        * statements.
  448        */
  449       (void) ir;
  450    }
  451 
  452    enum jump_strength get_jump_strength(ir_instruction* ir)
  453    {
  454       if(!ir)
  455          return strength_none;
  456       else if(ir->ir_type == ir_type_loop_jump) {
  457          if(((ir_loop_jump*)ir)->is_break())
  458             return strength_break;
  459          else
  460             return strength_continue;
  461       } else if(ir->ir_type == ir_type_return)
  462          return strength_return;
  463       else
  464          return strength_none;
  465    }
  466 
  467    bool should_lower_jump(ir_jump* ir)
  468    {
  469       unsigned strength = get_jump_strength(ir);
  470       bool lower;
  471       switch(strength)
  472       {
  473       case strength_none:
  474          lower = false; /* don't change this, code relies on it */
  475          break;
  476       case strength_continue:
  477          lower = lower_continue;
  478          break;
  479       case strength_break:
  480          assert(this->loop.loop);
  481          /* never lower "canonical break" */
  482          if(ir->get_next()->is_tail_sentinel() && (this->loop.nesting_depth == 0
  483                || (this->loop.nesting_depth == 1 && this->loop.in_if_at_the_end_of_the_loop)))
  484             lower = false;
  485          else
  486             lower = lower_break;
  487          break;
  488       case strength_return:
  489          /* never lower return at the end of a this->function */
  490          if(this->function.nesting_depth == 0 && ir->get_next()->is_tail_sentinel())
  491             lower = false;
  492          else
  493             lower = this->function.lower_return;
  494          break;
  495       }
  496       return lower;
  497    }
  498 
  499    block_record visit_block(exec_list* list)
  500    {
  501       /* Note: since visiting a node may change that node's next
  502        * pointer, we can't use visit_exec_list(), because
  503        * visit_exec_list() caches the node's next pointer before
  504        * visiting it.  So we use foreach_in_list() instead.
  505        *
  506        * foreach_in_list() isn't safe if the node being visited gets
  507        * removed, but fortunately this visitor doesn't do that.
  508        */
  509 
  510       block_record saved_block = this->block;
  511       this->block = block_record();
  512       foreach_in_list(ir_instruction, node, list) {
  513          node->accept(this);
  514       }
  515       block_record ret = this->block;
  516       this->block = saved_block;
  517       return ret;
  518    }
  519 
  520    virtual void visit(ir_if *ir)
  521    {
  522       if(this->loop.nesting_depth == 0 && ir->get_next()->is_tail_sentinel())
  523          this->loop.in_if_at_the_end_of_the_loop = true;
  524 
  525       ++this->function.nesting_depth;
  526       ++this->loop.nesting_depth;
  527 
  528       block_record block_records[2];
  529       ir_jump* jumps[2];
  530 
  531       /* Recursively lower nested jumps.  This satisfies the
  532        * CONTAINED_JUMPS_LOWERED postcondition, except in the case of
  533        * unconditional jumps at the end of ir->then_instructions and
  534        * ir->else_instructions, which are handled below.
  535        */
  536       block_records[0] = visit_block(&ir->then_instructions);
  537       block_records[1] = visit_block(&ir->else_instructions);
  538 
  539 retry: /* we get here if we put code after the if inside a branch */
  540 
  541       /* Determine which of ir->then_instructions and
  542        * ir->else_instructions end with an unconditional jump.
  543        */
  544       for(unsigned i = 0; i < 2; ++i) {
  545          exec_list& list = i ? ir->else_instructions : ir->then_instructions;
  546          jumps[i] = 0;
  547          if(!list.is_empty() && get_jump_strength((ir_instruction*)list.get_tail()))
  548             jumps[i] = (ir_jump*)list.get_tail();
  549       }
  550 
  551       /* Loop until we have satisfied the CONTAINED_JUMPS_LOWERED
  552        * postcondition by lowering jumps in both then_instructions and
  553        * else_instructions.
  554        */
  555       for(;;) {
  556          /* Determine the types of the jumps that terminate
  557           * ir->then_instructions and ir->else_instructions.
  558           */
  559          jump_strength jump_strengths[2];
  560 
  561          for(unsigned i = 0; i < 2; ++i) {
  562             if(jumps[i]) {
  563                jump_strengths[i] = block_records[i].min_strength;
  564                assert(jump_strengths[i] == get_jump_strength(jumps[i]));
  565             } else
  566                jump_strengths[i] = strength_none;
  567          }
  568 
  569          /* If both code paths end in a jump, and the jumps are the
  570           * same, and we are pulling out jumps, replace them with a
  571           * single jump that comes after the if instruction.  The new
  572           * jump will be visited next, and it will be lowered if
  573           * necessary by the loop or conditional that encloses it.
  574           */
  575          if(pull_out_jumps && jump_strengths[0] == jump_strengths[1]) {
  576             bool unify = true;
  577             if(jump_strengths[0] == strength_continue)
  578                ir->insert_after(new(ir) ir_loop_jump(ir_loop_jump::jump_continue));
  579             else if(jump_strengths[0] == strength_break)
  580                ir->insert_after(new(ir) ir_loop_jump(ir_loop_jump::jump_break));
  581             /* FINISHME: unify returns with identical expressions */
  582             else if(jump_strengths[0] == strength_return && this->function.signature->return_type->is_void())
  583                ir->insert_after(new(ir) ir_return(NULL));
  584         else
  585            unify = false;
  586 
  587             if(unify) {
  588                jumps[0]->remove();
  589                jumps[1]->remove();
  590                this->progress = true;
  591 
  592                /* Update jumps[] to reflect the fact that the jumps
  593                 * are gone, and update block_records[] to reflect the
  594                 * fact that control can now flow to the next
  595                 * instruction.
  596                 */
  597                jumps[0] = 0;
  598                jumps[1] = 0;
  599                block_records[0].min_strength = strength_none;
  600                block_records[1].min_strength = strength_none;
  601 
  602                /* The CONTAINED_JUMPS_LOWERED postcondition is now
  603                 * satisfied, so we can break out of the loop.
  604                 */
  605                break;
  606             }
  607          }
  608 
  609          /* lower a jump: if both need to lowered, start with the strongest one, so that
  610           * we might later unify the lowered version with the other one
  611           */
  612          bool should_lower[2];
  613          for(unsigned i = 0; i < 2; ++i)
  614             should_lower[i] = should_lower_jump(jumps[i]);
  615 
  616          int lower;
  617          if(should_lower[1] && should_lower[0])
  618             lower = jump_strengths[1] > jump_strengths[0];
  619          else if(should_lower[0])
  620             lower = 0;
  621          else if(should_lower[1])
  622             lower = 1;
  623          else
  624             /* Neither code path ends in a jump that needs to be
  625              * lowered, so the CONTAINED_JUMPS_LOWERED postcondition
  626              * is satisfied and we can break out of the loop.
  627              */
  628             break;
  629 
  630          if(jump_strengths[lower] == strength_return) {
  631             /* To lower a return, we create a return flag (if the
  632              * function doesn't have one already) and add instructions
  633              * that: 1. store the return value (if this function has a
  634              * non-void return) and 2. set the return flag
  635              */
  636             insert_lowered_return((ir_return*)jumps[lower]);
  637             if(this->loop.loop) {
  638                /* If we are in a loop, replace the return instruction
  639                 * with a break instruction, and then loop so that the
  640                 * break instruction can be lowered if necessary.
  641                 */
  642                ir_loop_jump* lowered = 0;
  643                lowered = new(ir) ir_loop_jump(ir_loop_jump::jump_break);
  644                /* Note: we must update block_records and jumps to
  645                 * reflect the fact that the control path has been
  646                 * altered from a return to a break.
  647                 */
  648                block_records[lower].min_strength = strength_break;
  649                jumps[lower]->replace_with(lowered);
  650                jumps[lower] = lowered;
  651             } else {
  652                /* If we are not in a loop, we then proceed as we would
  653                 * for a continue statement (set the execute flag to
  654                 * false to prevent the rest of the function from
  655                 * executing).
  656                 */
  657                goto lower_continue;
  658             }
  659             this->progress = true;
  660          } else if(jump_strengths[lower] == strength_break) {
  661             /* To lower a break, we create a break flag (if the loop
  662              * doesn't have one already) and add an instruction that
  663              * sets it.
  664              *
  665              * Then we proceed as we would for a continue statement
  666              * (set the execute flag to false to prevent the rest of
  667              * the loop body from executing).
  668              *
  669              * The visit() function for the loop will ensure that the
  670              * break flag is checked after executing the loop body.
  671              */
  672             jumps[lower]->insert_before(create_lowered_break());
  673             goto lower_continue;
  674          } else if(jump_strengths[lower] == strength_continue) {
  675 lower_continue:
  676             /* To lower a continue, we create an execute flag (if the
  677              * loop doesn't have one already) and replace the continue
  678              * with an instruction that clears it.
  679              *
  680              * Note that this code path gets exercised when lowering
  681              * return statements that are not inside a loop, so
  682              * this->loop must be initialized even outside of loops.
  683              */
  684             ir_variable* execute_flag = this->loop.get_execute_flag();
  685             jumps[lower]->replace_with(new(ir) ir_assignment(new (ir) ir_dereference_variable(execute_flag), new (ir) ir_constant(false)));
  686             /* Note: we must update block_records and jumps to reflect
  687              * the fact that the control path has been altered to an
  688              * instruction that clears the execute flag.
  689              */
  690             jumps[lower] = 0;
  691             block_records[lower].min_strength = strength_always_clears_execute_flag;
  692             block_records[lower].may_clear_execute_flag = true;
  693             this->progress = true;
  694 
  695             /* Let the loop run again, in case the other branch of the
  696              * if needs to be lowered too.
  697              */
  698          }
  699       }
  700 
  701       /* move out a jump out if possible */
  702       if(pull_out_jumps) {
  703          /* If one of the branches ends in a jump, and control cannot
  704           * fall out the bottom of the other branch, then we can move
  705           * the jump after the if.
  706           *
  707           * Set move_out to the branch we are moving a jump out of.
  708           */
  709          int move_out = -1;
  710          if(jumps[0] && block_records[1].min_strength >= strength_continue)
  711             move_out = 0;
  712          else if(jumps[1] && block_records[0].min_strength >= strength_continue)
  713             move_out = 1;
  714 
  715          if(move_out >= 0)
  716          {
  717             jumps[move_out]->remove();
  718             ir->insert_after(jumps[move_out]);
  719             /* Note: we must update block_records and jumps to reflect
  720              * the fact that the jump has been moved out of the if.
  721              */
  722             jumps[move_out] = 0;
  723             block_records[move_out].min_strength = strength_none;
  724             this->progress = true;
  725          }
  726       }
  727 
  728       /* Now satisfy the ANALYSIS postcondition by setting
  729        * this->block.min_strength and
  730        * this->block.may_clear_execute_flag based on the
  731        * characteristics of the two branches.
  732        */
  733       if(block_records[0].min_strength < block_records[1].min_strength)
  734          this->block.min_strength = block_records[0].min_strength;
  735       else
  736          this->block.min_strength = block_records[1].min_strength;
  737       this->block.may_clear_execute_flag = this->block.may_clear_execute_flag || block_records[0].may_clear_execute_flag || block_records[1].may_clear_execute_flag;
  738 
  739       /* Now we need to clean up the instructions that follow the
  740        * if.
  741        *
  742        * If those instructions are unreachable, then satisfy the
  743        * DEAD_CODE_ELIMINATION postcondition by eliminating them.
  744        * Otherwise that postcondition is already satisfied.
  745        */
  746       if(this->block.min_strength)
  747          truncate_after_instruction(ir);
  748       else if(this->block.may_clear_execute_flag)
  749       {
  750          /* If the "if" instruction might clear the execute flag, then
  751           * we need to guard any instructions that follow so that they
  752           * are only executed if the execute flag is set.
  753           *
  754           * If one of the branches of the "if" always clears the
  755           * execute flag, and the other branch never clears it, then
  756           * this is easy: just move all the instructions following the
  757           * "if" into the branch that never clears it.
  758           */
  759          int move_into = -1;
  760          if(block_records[0].min_strength && !block_records[1].may_clear_execute_flag)
  761             move_into = 1;
  762          else if(block_records[1].min_strength && !block_records[0].may_clear_execute_flag)
  763             move_into = 0;
  764 
  765          if(move_into >= 0) {
  766             assert(!block_records[move_into].min_strength && !block_records[move_into].may_clear_execute_flag); /* otherwise, we just truncated */
  767 
  768             exec_list* list = move_into ? &ir->else_instructions : &ir->then_instructions;
  769             exec_node* next = ir->get_next();
  770             if(!next->is_tail_sentinel()) {
  771                move_outer_block_inside(ir, list);
  772 
  773                /* If any instructions moved, then we need to visit
  774                 * them (since they are now inside the "if").  Since
  775                 * block_records[move_into] is in its default state
  776                 * (see assertion above), we can safely replace
  777                 * block_records[move_into] with the result of this
  778                 * analysis.
  779                 */
  780                exec_list list;
  781                list.head_sentinel.next = next;
  782                block_records[move_into] = visit_block(&list);
  783 
  784                /*
  785                 * Then we need to re-start our jump lowering, since one
  786                 * of the instructions we moved might be a jump that
  787                 * needs to be lowered.
  788                 */
  789                this->progress = true;
  790                goto retry;
  791             }
  792          } else {
  793             /* If we get here, then the simple case didn't apply; we
  794              * need to actually guard the instructions that follow.
  795              *
  796              * To avoid creating unnecessarily-deep nesting, first
  797              * look through the instructions that follow and unwrap
  798              * any instructions that that are already wrapped in the
  799              * appropriate guard.
  800              */
  801             ir_instruction* ir_after;
  802             for(ir_after = (ir_instruction*)ir->get_next(); !ir_after->is_tail_sentinel();)
  803             {
  804                ir_if* ir_if = ir_after->as_if();
  805                if(ir_if && ir_if->else_instructions.is_empty()) {
  806                   ir_dereference_variable* ir_if_cond_deref = ir_if->condition->as_dereference_variable();
  807                   if(ir_if_cond_deref && ir_if_cond_deref->var == this->loop.execute_flag) {
  808                      ir_instruction* ir_next = (ir_instruction*)ir_after->get_next();
  809                      ir_after->insert_before(&ir_if->then_instructions);
  810                      ir_after->remove();
  811                      ir_after = ir_next;
  812                      continue;
  813                   }
  814                }
  815                ir_after = (ir_instruction*)ir_after->get_next();
  816 
  817                /* only set this if we find any unprotected instruction */
  818                this->progress = true;
  819             }
  820 
  821             /* Then, wrap all the instructions that follow in a single
  822              * guard.
  823              */
  824             if(!ir->get_next()->is_tail_sentinel()) {
  825                assert(this->loop.execute_flag);
  826                ir_if* if_execute = new(ir) ir_if(new(ir) ir_dereference_variable(this->loop.execute_flag));
  827                move_outer_block_inside(ir, &if_execute->then_instructions);
  828                ir->insert_after(if_execute);
  829             }
  830          }
  831       }
  832       --this->loop.nesting_depth;
  833       --this->function.nesting_depth;
  834    }
  835 
  836    virtual void visit(ir_loop *ir)
  837    {
  838       /* Visit the body of the loop, with a fresh data structure in
  839        * this->loop so that the analysis we do here won't bleed into
  840        * enclosing loops.
  841        *
  842        * We assume that all code after a loop is reachable from the
  843        * loop (see comments on enum jump_strength), so the
  844        * DEAD_CODE_ELIMINATION postcondition is automatically
  845        * satisfied, as is the block.min_strength portion of the
  846        * ANALYSIS postcondition.
  847        *
  848        * The block.may_clear_execute_flag portion of the ANALYSIS
  849        * postcondition is automatically satisfied because execute
  850        * flags do not propagate outside of loops.
  851        *
  852        * The loop.may_set_return_flag portion of the ANALYSIS
  853        * postcondition is handled below.
  854        */
  855       ++this->function.nesting_depth;
  856       loop_record saved_loop = this->loop;
  857       this->loop = loop_record(this->function.signature, ir);
  858 
  859       /* Recursively lower nested jumps.  This satisfies the
  860        * CONTAINED_JUMPS_LOWERED postcondition, except in the case of
  861        * an unconditional continue or return at the bottom of the
  862        * loop, which are handled below.
  863        */
  864       block_record body = visit_block(&ir->body_instructions);
  865 
  866       /* If the loop ends in an unconditional continue, eliminate it
  867        * because it is redundant.
  868        */
  869       ir_instruction *ir_last
  870          = (ir_instruction *) ir->body_instructions.get_tail();
  871       if (get_jump_strength(ir_last) == strength_continue) {
  872          ir_last->remove();
  873       }
  874 
  875       /* If the loop ends in an unconditional return, and we are
  876        * lowering returns, lower it.
  877        */
  878       if (this->function.lower_return)
  879          lower_return_unconditionally(ir_last);
  880 
  881       if(body.min_strength >= strength_break) {
  882          /* FINISHME: If the min_strength of the loop body is
  883           * strength_break or strength_return, that means that it
  884           * isn't a loop at all, since control flow always leaves the
  885           * body of the loop via break or return.  In principle the
  886           * loop could be eliminated in this case.  This optimization
  887           * is not implemented yet.
  888           */
  889       }
  890 
  891       if(this->loop.break_flag) {
  892          /* We only get here if we are lowering breaks */
  893          assert (lower_break);
  894 
  895          /* If a break flag was generated while visiting the body of
  896           * the loop, then at least one break was lowered, so we need
  897           * to generate an if statement at the end of the loop that
  898           * does a "break" if the break flag is set.  The break we
  899           * generate won't violate the CONTAINED_JUMPS_LOWERED
  900           * postcondition, because should_lower_jump() always returns
  901           * false for a break that happens at the end of a loop.
  902           *
  903           * However, if the loop already ends in a conditional or
  904           * unconditional break, then we need to lower that break,
  905           * because it won't be at the end of the loop anymore.
  906           */
  907          lower_final_breaks(&ir->body_instructions);
  908 
  909          ir_if* break_if = new(ir) ir_if(new(ir) ir_dereference_variable(this->loop.break_flag));
  910          break_if->then_instructions.push_tail(new(ir) ir_loop_jump(ir_loop_jump::jump_break));
  911          ir->body_instructions.push_tail(break_if);
  912       }
  913 
  914       /* If the body of the loop may set the return flag, then at
  915        * least one return was lowered to a break, so we need to ensure
  916        * that the return flag is checked after the body of the loop is
  917        * executed.
  918        */
  919       if(this->loop.may_set_return_flag) {
  920          assert(this->function.return_flag);
  921          /* Generate the if statement to check the return flag */
  922          ir_if* return_if = new(ir) ir_if(new(ir) ir_dereference_variable(this->function.return_flag));
  923          /* Note: we also need to propagate the knowledge that the
  924           * return flag may get set to the outer context.  This
  925           * satisfies the loop.may_set_return_flag part of the
  926           * ANALYSIS postcondition.
  927           */
  928          saved_loop.may_set_return_flag = true;
  929          if(saved_loop.loop)
  930             /* If this loop is nested inside another one, then the if
  931              * statement that we generated should break out of that
  932              * loop if the return flag is set.  Caller will lower that
  933              * break statement if necessary.
  934              */
  935             return_if->then_instructions.push_tail(new(ir) ir_loop_jump(ir_loop_jump::jump_break));
  936          else {
  937             /* Otherwise, ensure that the instructions that follow are only
  938              * executed if the return flag is clear.  We can do that by moving
  939              * those instructions into the else clause of the generated if
  940              * statement.
  941              */
  942             move_outer_block_inside(ir, &return_if->else_instructions);
  943 
  944             /* In case the loop is embedded inside an if add a new return to
  945              * the return flag then branch and let a future pass tidy it up.
  946              */
  947             if (this->function.signature->return_type->is_void())
  948                return_if->then_instructions.push_tail(new(ir) ir_return(NULL));
  949             else {
  950                assert(this->function.return_value);
  951                ir_variable* return_value = this->function.return_value;
  952                return_if->then_instructions.push_tail(
  953                   new(ir) ir_return(new(ir) ir_dereference_variable(return_value)));
  954             }
  955          }
  956 
  957          ir->insert_after(return_if);
  958       }
  959 
  960       this->loop = saved_loop;
  961       --this->function.nesting_depth;
  962    }
  963 
  964    virtual void visit(ir_function_signature *ir)
  965    {
  966       /* these are not strictly necessary */
  967       assert(!this->function.signature);
  968       assert(!this->loop.loop);
  969 
  970       bool lower_return;
  971       if (strcmp(ir->function_name(), "main") == 0)
  972          lower_return = lower_main_return;
  973       else
  974          lower_return = lower_sub_return;
  975 
  976       function_record saved_function = this->function;
  977       loop_record saved_loop = this->loop;
  978       this->function = function_record(ir, lower_return);
  979       this->loop = loop_record(ir);
  980 
  981       assert(!this->loop.loop);
  982 
  983       /* Visit the body of the function to lower any jumps that occur
  984        * in it, except possibly an unconditional return statement at
  985        * the end of it.
  986        */
  987       visit_block(&ir->body);
  988 
  989       /* If the body ended in an unconditional return of non-void,
  990        * then we don't need to lower it because it's the one canonical
  991        * return.
  992        *
  993        * If the body ended in a return of void, eliminate it because
  994        * it is redundant.
  995        */
  996       if (ir->return_type->is_void() &&
  997           get_jump_strength((ir_instruction *) ir->body.get_tail())) {
  998          ir_jump *jump = (ir_jump *) ir->body.get_tail();
  999          assert (jump->ir_type == ir_type_return);
 1000          jump->remove();
 1001       }
 1002 
 1003       if(this->function.return_value)
 1004          ir->body.push_tail(new(ir) ir_return(new (ir) ir_dereference_variable(this->function.return_value)));
 1005 
 1006       this->loop = saved_loop;
 1007       this->function = saved_function;
 1008    }
 1009 
 1010    virtual void visit(class ir_function * ir)
 1011    {
 1012       visit_block(&ir->signatures);
 1013    }
 1014 };
 1015 
 1016 } /* anonymous namespace */
 1017 
 1018 bool
 1019 do_lower_jumps(exec_list *instructions, bool pull_out_jumps, bool lower_sub_return, bool lower_main_return, bool lower_continue, bool lower_break)
 1020 {
 1021    ir_lower_jumps_visitor v;
 1022    v.pull_out_jumps = pull_out_jumps;
 1023    v.lower_continue = lower_continue;
 1024    v.lower_break = lower_break;
 1025    v.lower_sub_return = lower_sub_return;
 1026    v.lower_main_return = lower_main_return;
 1027 
 1028    bool progress_ever = false;
 1029    do {
 1030       v.progress = false;
 1031       visit_exec_list(instructions, &v);
 1032       progress_ever = v.progress || progress_ever;
 1033    } while (v.progress);
 1034 
 1035    return progress_ever;
 1036 }