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