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.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    if_inst = NULL;
  57    else_inst = NULL;
  58    endif_inst = NULL;
  59 }
  60
  61 void
  62 bblock_t::add_successor(void *mem_ctx, bblock_t *successor)
  63 {
  64    successor->parents.push_tail(this->make_list(mem_ctx));
  65    children.push_tail(successor->make_list(mem_ctx));
  66 }
  67
  68 bblock_link *
  69 bblock_t::make_list(void *mem_ctx)
  70 {
  71    return new(mem_ctx) bblock_link(this);
  72 }
  73
  74 void
  75 bblock_t::dump(backend_visitor *v)
  76 {
  77    int ip = this->start_ip;
  78    for (backend_instruction *inst = (backend_instruction *)this->start;
  79         inst != this->end->next;
  80         inst = (backend_instruction *) inst->next) {
  81       printf("%5d: ", ip);
  82       v->dump_instruction(inst);
  83       ip++;
  84    }
  85 }
  86
  87 cfg_t::cfg_t(backend_visitor *v)
  88 {
  89    create(v->mem_ctx, &v->instructions);
  90 }
  91
  92 cfg_t::cfg_t(void *mem_ctx, exec_list *instructions)
  93 {
  94    create(mem_ctx, instructions);
  95 }
  96
  97 void
  98 cfg_t::create(void *parent_mem_ctx, exec_list *instructions)
  99 {
 100    mem_ctx = ralloc_context(NULL);
 101    block_list.make_empty();
 102    blocks = NULL;
 103    num_blocks = 0;
 104    ip = 0;
 105    cur = NULL;
 106
 107    bblock_t *entry = new_block();
 108    bblock_t *cur_if = NULL, *cur_else = NULL, *cur_endif = NULL;
 109    bblock_t *cur_do = NULL, *cur_while = NULL;
 110    exec_list if_stack, else_stack, endif_stack, do_stack, while_stack;
 111    bblock_t *next;
 112
 113    set_next_block(entry);
 114
 115    entry->start = (backend_instruction *) instructions->get_head();
 116
 117    foreach_list(node, instructions) {
 118       backend_instruction *inst = (backend_instruction *)node;
 119
 120       cur->end = inst;
 121
 122       /* set_next_block wants the post-incremented ip */
 123       ip++;
 124
 125       switch (inst->opcode) {
 126       case BRW_OPCODE_IF:
 127          /* Push our information onto a stack so we can recover from
 128           * nested ifs.
 129           */
 130          if_stack.push_tail(cur_if->make_list(mem_ctx));
 131          else_stack.push_tail(cur_else->make_list(mem_ctx));
 132          endif_stack.push_tail(cur_endif->make_list(mem_ctx));
 133
 134          cur_if = cur;
 135          cur_else = NULL;
 136          /* Set up the block just after the endif.  Don't know when exactly
 137           * it will start, yet.
 138           */
 139          cur_endif = new_block();
 140
 141          /* Set up our immediately following block, full of "then"
 142           * instructions.
 143           */
 144          next = new_block();
 145          next->start = (backend_instruction *)inst->next;
 146          cur_if->add_successor(mem_ctx, next);
 147
 148          set_next_block(next);
 149          break;
 150
 151       case BRW_OPCODE_ELSE:
 152          cur->add_successor(mem_ctx, cur_endif);
 153
 154          next = new_block();
 155          next->start = (backend_instruction *)inst->next;
 156          cur_if->add_successor(mem_ctx, next);
 157          cur_else = next;
 158
 159          set_next_block(next);
 160          break;
 161
 162       case BRW_OPCODE_ENDIF: {
 163          cur_endif->start = (backend_instruction *)inst->next;
 164          cur->add_successor(mem_ctx, cur_endif);
 165          set_next_block(cur_endif);
 166
 167          if (!cur_else)
 168             cur_if->add_successor(mem_ctx, cur_endif);
 169
 170          backend_instruction *else_inst = cur_else ?
 171             (backend_instruction *) cur_else->start->prev : NULL;
 172
 173          assert(cur_if->end->opcode == BRW_OPCODE_IF);
 174          assert(!else_inst || else_inst->opcode == BRW_OPCODE_ELSE);
 175          assert(inst->opcode == BRW_OPCODE_ENDIF);
 176
 177          cur_if->if_inst = cur_if->end;
 178          cur_if->else_inst = else_inst;
 179          cur_if->endif_inst = inst;
 180
 181          if (cur_else) {
 182             cur_else->if_inst = cur_if->end;
 183             cur_else->else_inst = else_inst;
 184             cur_else->endif_inst = inst;
 185          }
 186
 187          cur->if_inst = cur_if->end;
 188          cur->else_inst = else_inst;
 189          cur->endif_inst = inst;
 190
 191          /* Pop the stack so we're in the previous if/else/endif */
 192          cur_if = pop_stack(&if_stack);
 193          cur_else = pop_stack(&else_stack);
 194          cur_endif = pop_stack(&endif_stack);
 195          break;
 196       }
 197       case BRW_OPCODE_DO:
 198          /* Push our information onto a stack so we can recover from
 199           * nested loops.
 200           */
 201          do_stack.push_tail(cur_do->make_list(mem_ctx));
 202          while_stack.push_tail(cur_while->make_list(mem_ctx));
 203
 204          /* Set up the block just after the while.  Don't know when exactly
 205           * it will start, yet.
 206           */
 207          cur_while = new_block();
 208
 209          /* Set up our immediately following block, full of "then"
 210           * instructions.
 211           */
 212          next = new_block();
 213          next->start = (backend_instruction *)inst->next;
 214          cur->add_successor(mem_ctx, next);
 215          cur_do = next;
 216
 217          set_next_block(next);
 218          break;
 219
 220       case BRW_OPCODE_CONTINUE:
 221          cur->add_successor(mem_ctx, cur_do);
 222
 223          next = new_block();
 224          next->start = (backend_instruction *)inst->next;
 225          if (inst->predicate)
 226             cur->add_successor(mem_ctx, next);
 227
 228          set_next_block(next);
 229          break;
 230
 231       case BRW_OPCODE_BREAK:
 232          cur->add_successor(mem_ctx, cur_while);
 233
 234          next = new_block();
 235          next->start = (backend_instruction *)inst->next;
 236          if (inst->predicate)
 237             cur->add_successor(mem_ctx, next);
 238
 239          set_next_block(next);
 240          break;
 241
 242       case BRW_OPCODE_WHILE:
 243          cur_while->start = (backend_instruction *)inst->next;
 244
 245          cur->add_successor(mem_ctx, cur_do);
 246          set_next_block(cur_while);
 247
 248          /* Pop the stack so we're in the previous loop */
 249          cur_do = pop_stack(&do_stack);
 250          cur_while = pop_stack(&while_stack);
 251          break;
 252
 253       default:
 254          break;
 255       }
 256    }
 257
 258    cur->end_ip = ip;
 259
 260    make_block_array();
 261 }
 262
 263 cfg_t::~cfg_t()
 264 {
 265    ralloc_free(mem_ctx);
 266 }
 267
 268 bblock_t *
 269 cfg_t::new_block()
 270 {
 271    bblock_t *block = new(mem_ctx) bblock_t();
 272
 273    return block;
 274 }
 275
 276 void
 277 cfg_t::set_next_block(bblock_t *block)
 278 {
 279    if (cur) {
 280       assert(cur->end->next == block->start);
 281       cur->end_ip = ip - 1;
 282    }
 283
 284    block->start_ip = ip;
 285    block->block_num = num_blocks++;
 286    block_list.push_tail(block->make_list(mem_ctx));
 287    cur = block;
 288 }
 289
 290 void
 291 cfg_t::make_block_array()
 292 {
 293    blocks = ralloc_array(mem_ctx, bblock_t *, num_blocks);
 294
 295    int i = 0;
 296    foreach_list(block_node, &block_list) {
 297       bblock_link *link = (bblock_link *)block_node;
 298       blocks[i++] = link->block;
 299    }
 300    assert(i == num_blocks);
 301 }
 302
 303 void
 304 cfg_t::dump(backend_visitor *v)
 305 {
 306    for (int b = 0; b < this->num_blocks; b++) {
 307         bblock_t *block = this->blocks[b];
 308       printf("START B%d", b);
 309       foreach_list(node, &block->parents) {
 310          bblock_link *link = (bblock_link *)node;
 311          printf(" <-B%d", link->block->block_num);
 312       }
 313       printf("\n");
 314       block->dump(v);
 315       printf("END B%d", b);
 316       foreach_list(node, &block->children) {
 317          bblock_link *link = (bblock_link *)node;
 318          printf(" ->B%d", link->block->block_num);
 319       }
 320       printf("\n");
 321    }
 322 }