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