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, 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
 133          cur_if = cur;
 134          cur_else = NULL;
 135          cur_endif = NULL;
 136
 137          /* Set up our immediately following block, full of "then"
 138           * instructions.
 139           */
 140          next = new_block();
 141          next->start = (backend_instruction *)inst->next;
 142          cur_if->add_successor(mem_ctx, next);
 143
 144          set_next_block(next);
 145          break;
 146
 147       case BRW_OPCODE_ELSE:
 148          cur_else = cur;
 149
 150          next = new_block();
 151          next->start = (backend_instruction *)inst->next;
 152          cur_if->add_successor(mem_ctx, next);
 153
 154          set_next_block(next);
 155          break;
 156
 157       case BRW_OPCODE_ENDIF: {
 158          if (cur->start == inst) {
 159             /* New block was just created; use it. */
 160             cur_endif = cur;
 161          } else {
 162             cur_endif = new_block();
 163             cur_endif->start = inst;
 164
 165             cur->end = (backend_instruction *)inst->prev;
 166             cur->add_successor(mem_ctx, cur_endif);
 167
 168             ip--;
 169             set_next_block(cur_endif);
 170             ip++;
 171          }
 172
 173          backend_instruction *else_inst = NULL;
 174          if (cur_else) {
 175             else_inst = (backend_instruction *)cur_else->end;
 176
 177             cur_else->add_successor(mem_ctx, cur_endif);
 178          } else {
 179             cur_if->add_successor(mem_ctx, cur_endif);
 180          }
 181
 182          assert(cur_if->end->opcode == BRW_OPCODE_IF);
 183          assert(!else_inst || else_inst->opcode == BRW_OPCODE_ELSE);
 184          assert(inst->opcode == BRW_OPCODE_ENDIF);
 185
 186          cur_if->if_inst = cur_if->end;
 187          cur_if->else_inst = else_inst;
 188          cur_if->endif_inst = inst;
 189
 190          if (cur_else) {
 191             cur_else->if_inst = cur_if->end;
 192             cur_else->else_inst = else_inst;
 193             cur_else->endif_inst = inst;
 194          }
 195
 196          cur->if_inst = cur_if->end;
 197          cur->else_inst = else_inst;
 198          cur->endif_inst = inst;
 199
 200          /* Pop the stack so we're in the previous if/else/endif */
 201          cur_if = pop_stack(&if_stack);
 202          cur_else = pop_stack(&else_stack);
 203          break;
 204       }
 205       case BRW_OPCODE_DO:
 206          /* Push our information onto a stack so we can recover from
 207           * nested loops.
 208           */
 209          do_stack.push_tail(cur_do->make_list(mem_ctx));
 210          while_stack.push_tail(cur_while->make_list(mem_ctx));
 211
 212          /* Set up the block just after the while.  Don't know when exactly
 213           * it will start, yet.
 214           */
 215          cur_while = new_block();
 216
 217          /* Set up our immediately following block, full of "then"
 218           * instructions.
 219           */
 220          next = new_block();
 221          next->start = (backend_instruction *)inst->next;
 222          cur->add_successor(mem_ctx, next);
 223          cur_do = next;
 224
 225          set_next_block(next);
 226          break;
 227
 228       case BRW_OPCODE_CONTINUE:
 229          cur->add_successor(mem_ctx, cur_do);
 230
 231          next = new_block();
 232          next->start = (backend_instruction *)inst->next;
 233          if (inst->predicate)
 234             cur->add_successor(mem_ctx, next);
 235
 236          set_next_block(next);
 237          break;
 238
 239       case BRW_OPCODE_BREAK:
 240          cur->add_successor(mem_ctx, cur_while);
 241
 242          next = new_block();
 243          next->start = (backend_instruction *)inst->next;
 244          if (inst->predicate)
 245             cur->add_successor(mem_ctx, next);
 246
 247          set_next_block(next);
 248          break;
 249
 250       case BRW_OPCODE_WHILE:
 251          cur_while->start = (backend_instruction *)inst->next;
 252
 253          cur->add_successor(mem_ctx, cur_do);
 254          set_next_block(cur_while);
 255
 256          /* Pop the stack so we're in the previous loop */
 257          cur_do = pop_stack(&do_stack);
 258          cur_while = pop_stack(&while_stack);
 259          break;
 260
 261       default:
 262          break;
 263       }
 264    }
 265
 266    cur->end_ip = ip;
 267
 268    make_block_array();
 269 }
 270
 271 cfg_t::~cfg_t()
 272 {
 273    ralloc_free(mem_ctx);
 274 }
 275
 276 bblock_t *
 277 cfg_t::new_block()
 278 {
 279    bblock_t *block = new(mem_ctx) bblock_t();
 280
 281    return block;
 282 }
 283
 284 void
 285 cfg_t::set_next_block(bblock_t *block)
 286 {
 287    if (cur) {
 288       assert(cur->end->next == block->start);
 289       cur->end_ip = ip - 1;
 290    }
 291
 292    block->start_ip = ip;
 293    block->block_num = num_blocks++;
 294    block_list.push_tail(block->make_list(mem_ctx));
 295    cur = block;
 296 }
 297
 298 void
 299 cfg_t::make_block_array()
 300 {
 301    blocks = ralloc_array(mem_ctx, bblock_t *, num_blocks);
 302
 303    int i = 0;
 304    foreach_list(block_node, &block_list) {
 305       bblock_link *link = (bblock_link *)block_node;
 306       blocks[i++] = link->block;
 307    }
 308    assert(i == num_blocks);
 309 }
 310
 311 void
 312 cfg_t::dump(backend_visitor *v)
 313 {
 314    for (int b = 0; b < this->num_blocks; b++) {
 315         bblock_t *block = this->blocks[b];
 316       printf("START B%d", b);
 317       foreach_list(node, &block->parents) {
 318          bblock_link *link = (bblock_link *)node;
 319          printf(" <-B%d", link->block->block_num);
 320       }
 321       printf("\n");
 322       block->dump(v);
 323       printf("END B%d", b);
 324       foreach_list(node, &block->children) {
 325          bblock_link *link = (bblock_link *)node;
 326          printf(" ->B%d", link->block->block_num);
 327       }
 328       printf("\n");
 329    }
 330 }