src/mesa/drivers/dri/i965/brw_vec4_live_variables.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 #include "brw_vec4_live_variables.h"
  30
  31 using namespace brw;
  32
  33 /** @file brw_vec4_live_variables.cpp
  34  *
  35  * Support for computing at the basic block level which variables
  36  * (virtual GRFs in our case) are live at entry and exit.
  37  *
  38  * See Muchnick's Advanced Compiler Design and Implementation, section
  39  * 14.1 (p444).
  40  */
  41
  42 /**
  43  * Sets up the use[] and def[] arrays.
  44  *
  45  * The basic-block-level live variable analysis needs to know which
  46  * variables get used before they're completely defined, and which
  47  * variables are completely defined before they're used.
  48  *
  49  * We independently track each channel of a vec4.  This is because we need to
  50  * be able to recognize a sequence like:
  51  *
  52  * ...
  53  * DP4 tmp.x a b;
  54  * DP4 tmp.y c d;
  55  * MUL result.xy tmp.xy e.xy
  56  * ...
  57  *
  58  * as having tmp live only across that sequence (assuming it's used nowhere
  59  * else), because it's a common pattern.  A more conservative approach that
  60  * doesn't get tmp marked a deffed in this block will tend to result in
  61  * spilling.
  62  */
  63 void
  64 vec4_live_variables::setup_def_use()
  65 {
  66    int ip = 0;
  67
  68    for (int b = 0; b < cfg->num_blocks; b++) {
  69       bblock_t *block = cfg->blocks[b];
  70
  71       assert(ip == block->start_ip);
  72       if (b > 0)
  73          assert(cfg->blocks[b - 1]->end_ip == ip - 1);
  74
  75       foreach_inst_in_block(vec4_instruction, inst, block) {
  76          /* Set use[] for this instruction */
  77          for (unsigned int i = 0; i < 3; i++) {
  78             if (inst->src[i].file == GRF) {
  79                int reg = inst->src[i].reg;
  80
  81                for (int j = 0; j < 4; j++) {
  82                   int c = BRW_GET_SWZ(inst->src[i].swizzle, j);
  83                   if (!BITSET_TEST(bd[b].def, reg * 4 + c))
  84                      BITSET_SET(bd[b].use, reg * 4 + c);
  85                }
  86             }
  87          }
  88
  89          /* Check for unconditional writes to whole registers. These
  90           * are the things that screen off preceding definitions of a
  91           * variable, and thus qualify for being in def[].
  92           */
  93          if (inst->dst.file == GRF &&
  94              v->virtual_grf_sizes[inst->dst.reg] == 1 &&
  95              !inst->predicate) {
  96             for (int c = 0; c < 4; c++) {
  97                if (inst->dst.writemask & (1 << c)) {
  98                   int reg = inst->dst.reg;
  99                   if (!BITSET_TEST(bd[b].use, reg * 4 + c))
 100                      BITSET_SET(bd[b].def, reg * 4 + c);
 101                }
 102             }
 103          }
 104
 105          ip++;
 106       }
 107    }
 108 }
 109
 110 /**
 111  * The algorithm incrementally sets bits in liveout and livein,
 112  * propagating it through control flow.  It will eventually terminate
 113  * because it only ever adds bits, and stops when no bits are added in
 114  * a pass.
 115  */
 116 void
 117 vec4_live_variables::compute_live_variables()
 118 {
 119    bool cont = true;
 120
 121    while (cont) {
 122       cont = false;
 123
 124       for (int b = 0; b < cfg->num_blocks; b++) {
 125          /* Update livein */
 126          for (int i = 0; i < bitset_words; i++) {
 127             BITSET_WORD new_livein = (bd[b].use[i] |
 128                                       (bd[b].liveout[i] & ~bd[b].def[i]));
 129             if (new_livein & ~bd[b].livein[i]) {
 130                bd[b].livein[i] |= new_livein;
 131                cont = true;
 132             }
 133          }
 134
 135          /* Update liveout */
 136          foreach_list_typed(bblock_link, link, link, &cfg->blocks[b]->children) {
 137             bblock_t *block = link->block;
 138
 139             for (int i = 0; i < bitset_words; i++) {
 140                BITSET_WORD new_liveout = (bd[block->block_num].livein[i] &
 141                                           ~bd[b].liveout[i]);
 142                if (new_liveout) {
 143                   bd[b].liveout[i] |= new_liveout;
 144                   cont = true;
 145                }
 146             }
 147          }
 148       }
 149    }
 150 }
 151
 152 vec4_live_variables::vec4_live_variables(vec4_visitor *v, cfg_t *cfg)
 153    : v(v), cfg(cfg)
 154 {
 155    mem_ctx = ralloc_context(NULL);
 156
 157    num_vars = v->virtual_grf_count * 4;
 158    bd = rzalloc_array(mem_ctx, struct block_data, cfg->num_blocks);
 159
 160    bitset_words = BITSET_WORDS(num_vars);
 161    for (int i = 0; i < cfg->num_blocks; i++) {
 162       bd[i].def = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words);
 163       bd[i].use = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words);
 164       bd[i].livein = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words);
 165       bd[i].liveout = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words);
 166    }
 167
 168    setup_def_use();
 169    compute_live_variables();
 170 }
 171
 172 vec4_live_variables::~vec4_live_variables()
 173 {
 174    ralloc_free(mem_ctx);
 175 }
 176
 177 #define MAX_INSTRUCTION (1 << 30)
 178
 179 /**
 180  * Computes a conservative start/end of the live intervals for each virtual GRF.
 181  *
 182  * We could expose per-channel live intervals to the consumer based on the
 183  * information we computed in vec4_live_variables, except that our only
 184  * current user is virtual_grf_interferes().  So we instead union the
 185  * per-channel ranges into a per-vgrf range for virtual_grf_start[] and
 186  * virtual_grf_end[].
 187  *
 188  * We could potentially have virtual_grf_interferes() do the test per-channel,
 189  * which would let some interesting register allocation occur (particularly on
 190  * code-generated GLSL sequences from the Cg compiler which does register
 191  * allocation at the GLSL level and thus reuses components of the variable
 192  * with distinct lifetimes).  But right now the complexity of doing so doesn't
 193  * seem worth it, since having virtual_grf_interferes() be cheap is important
 194  * for register allocation performance.
 195  */
 196 void
 197 vec4_visitor::calculate_live_intervals()
 198 {
 199    if (this->live_intervals_valid)
 200       return;
 201
 202    int *start = ralloc_array(mem_ctx, int, this->virtual_grf_count * 4);
 203    int *end = ralloc_array(mem_ctx, int, this->virtual_grf_count * 4);
 204    ralloc_free(this->virtual_grf_start);
 205    ralloc_free(this->virtual_grf_end);
 206    this->virtual_grf_start = start;
 207    this->virtual_grf_end = end;
 208
 209    for (int i = 0; i < this->virtual_grf_count * 4; i++) {
 210       start[i] = MAX_INSTRUCTION;
 211       end[i] = -1;
 212    }
 213
 214    /* Start by setting up the intervals with no knowledge of control
 215     * flow.
 216     */
 217    int ip = 0;
 218    foreach_in_list(vec4_instruction, inst, &instructions) {
 219       for (unsigned int i = 0; i < 3; i++) {
 220          if (inst->src[i].file == GRF) {
 221             int reg = inst->src[i].reg;
 222
 223             for (int j = 0; j < 4; j++) {
 224                int c = BRW_GET_SWZ(inst->src[i].swizzle, j);
 225
 226                start[reg * 4 + c] = MIN2(start[reg * 4 + c], ip);
 227                end[reg * 4 + c] = ip;
 228             }
 229          }
 230       }
 231
 232       if (inst->dst.file == GRF) {
 233          int reg = inst->dst.reg;
 234
 235          for (int c = 0; c < 4; c++) {
 236             if (inst->dst.writemask & (1 << c)) {
 237                start[reg * 4 + c] = MIN2(start[reg * 4 + c], ip);
 238                end[reg * 4 + c] = ip;
 239             }
 240          }
 241       }
 242
 243       ip++;
 244    }
 245
 246    /* Now, extend those intervals using our analysis of control flow.
 247     *
 248     * The control flow-aware analysis was done at a channel level, while at
 249     * this point we're distilling it down to vgrfs.
 250     */
 251    calculate_cfg();
 252    vec4_live_variables livevars(this, cfg);
 253
 254    for (int b = 0; b < cfg->num_blocks; b++) {
 255       for (int i = 0; i < livevars.num_vars; i++) {
 256          if (BITSET_TEST(livevars.bd[b].livein, i)) {
 257             start[i] = MIN2(start[i], cfg->blocks[b]->start_ip);
 258             end[i] = MAX2(end[i], cfg->blocks[b]->start_ip);
 259          }
 260
 261          if (BITSET_TEST(livevars.bd[b].liveout, i)) {
 262             start[i] = MIN2(start[i], cfg->blocks[b]->end_ip);
 263             end[i] = MAX2(end[i], cfg->blocks[b]->end_ip);
 264          }
 265       }
 266    }
 267
 268    this->live_intervals_valid = true;
 269 }
 270
 271 void
 272 vec4_visitor::invalidate_live_intervals()
 273 {
 274    live_intervals_valid = false;
 275
 276    invalidate_cfg();
 277 }
 278
 279 bool
 280 vec4_visitor::virtual_grf_interferes(int a, int b)
 281 {
 282    int start_a = MIN2(MIN2(virtual_grf_start[a * 4 + 0],
 283                            virtual_grf_start[a * 4 + 1]),
 284                       MIN2(virtual_grf_start[a * 4 + 2],
 285                            virtual_grf_start[a * 4 + 3]));
 286    int start_b = MIN2(MIN2(virtual_grf_start[b * 4 + 0],
 287                            virtual_grf_start[b * 4 + 1]),
 288                       MIN2(virtual_grf_start[b * 4 + 2],
 289                            virtual_grf_start[b * 4 + 3]));
 290    int end_a = MAX2(MAX2(virtual_grf_end[a * 4 + 0],
 291                          virtual_grf_end[a * 4 + 1]),
 292                     MAX2(virtual_grf_end[a * 4 + 2],
 293                          virtual_grf_end[a * 4 + 3]));
 294    int end_b = MAX2(MAX2(virtual_grf_end[b * 4 + 0],
 295                          virtual_grf_end[b * 4 + 1]),
 296                     MAX2(virtual_grf_end[b * 4 + 2],
 297                          virtual_grf_end[b * 4 + 3]));
 298    return !(end_a <= start_b ||
 299             end_b <= start_a);
 300 }