src/mesa/drivers/dri/i965/brw_cfg.cpp

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