Home | History | Annotate | Download | only in i965 
      1 /*
      2  * Copyright  2012 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  * Authors:
     24  *    Eric Anholt <eric (at) anholt.net>
     25  *
     26  */
     27 
     28 #include "brw_fs.h"
     29 #include "brw_fs_cfg.h"
     30 
     31 /** @file brw_fs_cfg.cpp
     32  *
     33  * Walks the shader instructions generated and creates a set of basic
     34  * blocks with successor/predecessor edges connecting them.
     35  */
     36 
     37 static fs_bblock *
     38 pop_stack(exec_list *list)
     39 {
     40    fs_bblock_link *link = (fs_bblock_link *)list->get_tail();
     41    fs_bblock *block = link->block;
     42    link->remove();
     43 
     44    return block;
     45 }
     46 
     47 fs_bblock::fs_bblock()
     48 {
     49    start = NULL;
     50    end = NULL;
     51 
     52    parents.make_empty();
     53    children.make_empty();
     54 }
     55 
     56 void
     57 fs_bblock::add_successor(void *mem_ctx, fs_bblock *successor)
     58 {
     59    successor->parents.push_tail(this->make_list(mem_ctx));
     60    children.push_tail(successor->make_list(mem_ctx));
     61 }
     62 
     63 fs_bblock_link *
     64 fs_bblock::make_list(void *mem_ctx)
     65 {
     66    return new(mem_ctx) fs_bblock_link(this);
     67 }
     68 
     69 fs_cfg::fs_cfg(fs_visitor *v)
     70 {
     71    mem_ctx = ralloc_context(v->mem_ctx);
     72    block_list.make_empty();
     73    num_blocks = 0;
     74    ip = 0;
     75    cur = NULL;
     76 
     77    fs_bblock *entry = new_block();
     78    fs_bblock *cur_if = NULL, *cur_else = NULL, *cur_endif = NULL;
     79    fs_bblock *cur_do = NULL, *cur_while = NULL;
     80    exec_list if_stack, else_stack, endif_stack, do_stack, while_stack;
     81    fs_bblock *next;
     82 
     83    set_next_block(entry);
     84 
     85    entry->start = (fs_inst *)v->instructions.get_head();
     86 
     87    foreach_list(node, &v->instructions) {
     88       fs_inst *inst = (fs_inst *)node;
     89 
     90       cur->end = inst;
     91 
     92       /* set_next_block wants the post-incremented ip */
     93       ip++;
     94 
     95       switch (inst->opcode) {
     96       case BRW_OPCODE_IF:
     97 	 /* Push our information onto a stack so we can recover from
     98 	  * nested ifs.
     99 	  */
    100 	 if_stack.push_tail(cur_if->make_list(mem_ctx));
    101 	 else_stack.push_tail(cur_else->make_list(mem_ctx));
    102 	 endif_stack.push_tail(cur_endif->make_list(mem_ctx));
    103 
    104 	 cur_if = cur;
    105 	 cur_else = NULL;
    106 	 /* Set up the block just after the endif.  Don't know when exactly
    107 	  * it will start, yet.
    108 	  */
    109 	 cur_endif = new_block();
    110 
    111 	 /* Set up our immediately following block, full of "then"
    112 	  * instructions.
    113 	  */
    114 	 next = new_block();
    115 	 next->start = (fs_inst *)inst->next;
    116 	 cur_if->add_successor(mem_ctx, next);
    117 
    118 	 set_next_block(next);
    119 	 break;
    120 
    121       case BRW_OPCODE_ELSE:
    122 	 cur->add_successor(mem_ctx, cur_endif);
    123 
    124 	 next = new_block();
    125 	 next->start = (fs_inst *)inst->next;
    126 	 cur_if->add_successor(mem_ctx, next);
    127 	 cur_else = next;
    128 
    129 	 set_next_block(next);
    130 	 break;
    131 
    132       case BRW_OPCODE_ENDIF:
    133 	 cur_endif->start = (fs_inst *)inst->next;
    134 	 cur->add_successor(mem_ctx, cur_endif);
    135 	 set_next_block(cur_endif);
    136 
    137 	 if (!cur_else)
    138 	    cur_if->add_successor(mem_ctx, cur_endif);
    139 
    140 	 /* Pop the stack so we're in the previous if/else/endif */
    141 	 cur_if = pop_stack(&if_stack);
    142 	 cur_else = pop_stack(&else_stack);
    143 	 cur_endif = pop_stack(&endif_stack);
    144 	 break;
    145 
    146       case BRW_OPCODE_DO:
    147 	 /* Push our information onto a stack so we can recover from
    148 	  * nested loops.
    149 	  */
    150 	 do_stack.push_tail(cur_do->make_list(mem_ctx));
    151 	 while_stack.push_tail(cur_while->make_list(mem_ctx));
    152 
    153 	 /* Set up the block just after the while.  Don't know when exactly
    154 	  * it will start, yet.
    155 	  */
    156 	 cur_while = new_block();
    157 
    158 	 /* Set up our immediately following block, full of "then"
    159 	  * instructions.
    160 	  */
    161 	 next = new_block();
    162 	 next->start = (fs_inst *)inst->next;
    163 	 cur->add_successor(mem_ctx, next);
    164 	 cur_do = next;
    165 
    166 	 set_next_block(next);
    167 	 break;
    168 
    169       case BRW_OPCODE_CONTINUE:
    170 	 cur->add_successor(mem_ctx, cur_do);
    171 
    172 	 next = new_block();
    173 	 next->start = (fs_inst *)inst->next;
    174 	 if (inst->predicated)
    175 	    cur->add_successor(mem_ctx, next);
    176 
    177 	 set_next_block(next);
    178 	 break;
    179 
    180       case BRW_OPCODE_BREAK:
    181 	 cur->add_successor(mem_ctx, cur_while);
    182 
    183 	 next = new_block();
    184 	 next->start = (fs_inst *)inst->next;
    185 	 if (inst->predicated)
    186 	    cur->add_successor(mem_ctx, next);
    187 
    188 	 set_next_block(next);
    189 	 break;
    190 
    191       case BRW_OPCODE_WHILE:
    192 	 cur_while->start = (fs_inst *)inst->next;
    193 
    194 	 cur->add_successor(mem_ctx, cur_do);
    195 	 set_next_block(cur_while);
    196 
    197 	 /* Pop the stack so we're in the previous loop */
    198 	 cur_do = pop_stack(&do_stack);
    199 	 cur_while = pop_stack(&while_stack);
    200 	 break;
    201 
    202       default:
    203 	 break;
    204       }
    205    }
    206 
    207    cur->end_ip = ip;
    208 
    209    make_block_array();
    210 }
    211 
    212 fs_cfg::~fs_cfg()
    213 {
    214    ralloc_free(mem_ctx);
    215 }
    216 
    217 fs_bblock *
    218 fs_cfg::new_block()
    219 {
    220    fs_bblock *block = new(mem_ctx) fs_bblock();
    221 
    222    return block;
    223 }
    224 
    225 void
    226 fs_cfg::set_next_block(fs_bblock *block)
    227 {
    228    if (cur) {
    229       assert(cur->end->next == block->start);
    230       cur->end_ip = ip - 1;
    231    }
    232 
    233    block->start_ip = ip;
    234    block->block_num = num_blocks++;
    235    block_list.push_tail(block->make_list(mem_ctx));
    236    cur = block;
    237 }
    238 
    239 void
    240 fs_cfg::make_block_array()
    241 {
    242    blocks = ralloc_array(mem_ctx, fs_bblock *, num_blocks);
    243 
    244    int i = 0;
    245    foreach_list(block_node, &block_list) {
    246       fs_bblock_link *link = (fs_bblock_link *)block_node;
    247       blocks[i++] = link->block;
    248    }
    249    assert(i == num_blocks);
    250 }
    251