Home | History | Annotate | Download | only in i965 
      1 /*
      2  * Copyright  2013 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 DEALINGS
     21  * IN THE SOFTWARE.
     22  */
     23 
     24 #include "brw_cfg.h"
     25 
     26 using namespace brw;
     27 
     28 /** @file brw_predicated_break.cpp
     29  *
     30  * Loops are often structured as
     31  *
     32  * loop:
     33  *    CMP.f0
     34  *    (+f0) IF
     35  *    BREAK
     36  *    ENDIF
     37  *    ...
     38  *    WHILE loop
     39  *
     40  * This peephole pass removes the IF and ENDIF instructions and predicates the
     41  * BREAK, dropping two instructions from the loop body.
     42  *
     43  * If the loop was a DO { ... } WHILE loop, it looks like
     44  *
     45  * loop:
     46  *    ...
     47  *    CMP.f0
     48  *    (+f0) IF
     49  *    BREAK
     50  *    ENDIF
     51  *    WHILE loop
     52  *
     53  * and we can remove the BREAK instruction and predicate the WHILE.
     54  */
     55 
     56 bool
     57 opt_predicated_break(backend_shader *s)
     58 {
     59    bool progress = false;
     60 
     61    foreach_block (block, s->cfg) {
     62       if (block->start_ip != block->end_ip)
     63          continue;
     64 
     65       /* BREAK and CONTINUE instructions, by definition, can only be found at
     66        * the ends of basic blocks.
     67        */
     68       backend_instruction *jump_inst = block->end();
     69       if (jump_inst->opcode != BRW_OPCODE_BREAK &&
     70           jump_inst->opcode != BRW_OPCODE_CONTINUE)
     71          continue;
     72 
     73       backend_instruction *if_inst = block->prev()->end();
     74       if (if_inst->opcode != BRW_OPCODE_IF)
     75          continue;
     76 
     77       backend_instruction *endif_inst = block->next()->start();
     78       if (endif_inst->opcode != BRW_OPCODE_ENDIF)
     79          continue;
     80 
     81       bblock_t *jump_block = block;
     82       bblock_t *if_block = jump_block->prev();
     83       bblock_t *endif_block = jump_block->next();
     84 
     85       jump_inst->predicate = if_inst->predicate;
     86       jump_inst->predicate_inverse = if_inst->predicate_inverse;
     87 
     88       bblock_t *earlier_block = if_block;
     89       if (if_block->start_ip == if_block->end_ip) {
     90          earlier_block = if_block->prev();
     91       }
     92 
     93       if_inst->remove(if_block);
     94 
     95       bblock_t *later_block = endif_block;
     96       if (endif_block->start_ip == endif_block->end_ip) {
     97          later_block = endif_block->next();
     98       }
     99       endif_inst->remove(endif_block);
    100 
    101       if (!earlier_block->ends_with_control_flow()) {
    102          earlier_block->children.make_empty();
    103          earlier_block->add_successor(s->cfg->mem_ctx, jump_block);
    104       }
    105 
    106       if (!later_block->starts_with_control_flow()) {
    107          later_block->parents.make_empty();
    108       }
    109       jump_block->add_successor(s->cfg->mem_ctx, later_block);
    110 
    111       if (earlier_block->can_combine_with(jump_block)) {
    112          earlier_block->combine_with(jump_block);
    113 
    114          block = earlier_block;
    115       }
    116 
    117       /* Now look at the first instruction of the block following the BREAK. If
    118        * it's a WHILE, we can delete the break, predicate the WHILE, and join
    119        * the two basic blocks.
    120        */
    121       bblock_t *while_block = earlier_block->next();
    122       backend_instruction *while_inst = while_block->start();
    123 
    124       if (jump_inst->opcode == BRW_OPCODE_BREAK &&
    125           while_inst->opcode == BRW_OPCODE_WHILE &&
    126           while_inst->predicate == BRW_PREDICATE_NONE) {
    127          jump_inst->remove(earlier_block);
    128          while_inst->predicate = jump_inst->predicate;
    129          while_inst->predicate_inverse = !jump_inst->predicate_inverse;
    130 
    131          earlier_block->children.make_empty();
    132          earlier_block->add_successor(s->cfg->mem_ctx, while_block);
    133 
    134          assert(earlier_block->can_combine_with(while_block));
    135          earlier_block->combine_with(while_block);
    136 
    137          earlier_block->next()->parents.make_empty();
    138          earlier_block->add_successor(s->cfg->mem_ctx, earlier_block->next());
    139       }
    140 
    141       progress = true;
    142    }
    143 
    144    if (progress)
    145       s->invalidate_live_intervals();
    146 
    147    return progress;
    148 }
    149