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 (at) anholt.net> 25 * 26 */ 27 28 #include "brw_cfg.h" 29 #include "brw_fs_live_variables.h" 30 31 using namespace brw; 32 33 #define MAX_INSTRUCTION (1 << 30) 34 35 /** @file brw_fs_live_variables.cpp 36 * 37 * Support for calculating liveness information about virtual GRFs. 38 * 39 * This produces a live interval for each whole virtual GRF. We could 40 * choose to expose per-component live intervals for VGRFs of size > 1, 41 * but we currently do not. It is easier for the consumers of this 42 * information to work with whole VGRFs. 43 * 44 * However, we internally track use/def information at the per-GRF level for 45 * greater accuracy. Large VGRFs may be accessed piecemeal over many 46 * (possibly non-adjacent) instructions. In this case, examining a single 47 * instruction is insufficient to decide whether a whole VGRF is ultimately 48 * used or defined. Tracking individual components allows us to easily 49 * assemble this information. 50 * 51 * See Muchnick's Advanced Compiler Design and Implementation, section 52 * 14.1 (p444). 53 */ 54 55 void 56 fs_live_variables::setup_one_read(struct block_data *bd, fs_inst *inst, 57 int ip, const fs_reg ®) 58 { 59 int var = var_from_reg(reg); 60 assert(var < num_vars); 61 62 start[var] = MIN2(start[var], ip); 63 end[var] = MAX2(end[var], ip); 64 65 /* The use[] bitset marks when the block makes use of a variable (VGRF 66 * channel) without having completely defined that variable within the 67 * block. 68 */ 69 if (!BITSET_TEST(bd->def, var)) 70 BITSET_SET(bd->use, var); 71 } 72 73 void 74 fs_live_variables::setup_one_write(struct block_data *bd, fs_inst *inst, 75 int ip, const fs_reg ®) 76 { 77 int var = var_from_reg(reg); 78 assert(var < num_vars); 79 80 start[var] = MIN2(start[var], ip); 81 end[var] = MAX2(end[var], ip); 82 83 /* The def[] bitset marks when an initialization in a block completely 84 * screens off previous updates of that variable (VGRF channel). 85 */ 86 if (inst->dst.file == VGRF && !inst->is_partial_write()) { 87 if (!BITSET_TEST(bd->use, var)) 88 BITSET_SET(bd->def, var); 89 } 90 } 91 92 /** 93 * Sets up the use[] and def[] bitsets. 94 * 95 * The basic-block-level live variable analysis needs to know which 96 * variables get used before they're completely defined, and which 97 * variables are completely defined before they're used. 98 * 99 * These are tracked at the per-component level, rather than whole VGRFs. 100 */ 101 void 102 fs_live_variables::setup_def_use() 103 { 104 int ip = 0; 105 106 foreach_block (block, cfg) { 107 assert(ip == block->start_ip); 108 if (block->num > 0) 109 assert(cfg->blocks[block->num - 1]->end_ip == ip - 1); 110 111 struct block_data *bd = &block_data[block->num]; 112 113 foreach_inst_in_block(fs_inst, inst, block) { 114 /* Set use[] for this instruction */ 115 for (unsigned int i = 0; i < inst->sources; i++) { 116 fs_reg reg = inst->src[i]; 117 118 if (reg.file != VGRF) 119 continue; 120 121 for (unsigned j = 0; j < regs_read(inst, i); j++) { 122 setup_one_read(bd, inst, ip, reg); 123 reg.offset += REG_SIZE; 124 } 125 } 126 127 bd->flag_use[0] |= inst->flags_read(v->devinfo) & ~bd->flag_def[0]; 128 129 /* Set def[] for this instruction */ 130 if (inst->dst.file == VGRF) { 131 fs_reg reg = inst->dst; 132 for (unsigned j = 0; j < regs_written(inst); j++) { 133 setup_one_write(bd, inst, ip, reg); 134 reg.offset += REG_SIZE; 135 } 136 } 137 138 if (!inst->predicate && inst->exec_size >= 8) 139 bd->flag_def[0] |= inst->flags_written() & ~bd->flag_use[0]; 140 141 ip++; 142 } 143 } 144 } 145 146 /** 147 * The algorithm incrementally sets bits in liveout and livein, 148 * propagating it through control flow. It will eventually terminate 149 * because it only ever adds bits, and stops when no bits are added in 150 * a pass. 151 */ 152 void 153 fs_live_variables::compute_live_variables() 154 { 155 bool cont = true; 156 157 while (cont) { 158 cont = false; 159 160 foreach_block_reverse (block, cfg) { 161 struct block_data *bd = &block_data[block->num]; 162 163 /* Update liveout */ 164 foreach_list_typed(bblock_link, child_link, link, &block->children) { 165 struct block_data *child_bd = &block_data[child_link->block->num]; 166 167 for (int i = 0; i < bitset_words; i++) { 168 BITSET_WORD new_liveout = (child_bd->livein[i] & 169 ~bd->liveout[i]); 170 if (new_liveout) { 171 bd->liveout[i] |= new_liveout; 172 cont = true; 173 } 174 } 175 BITSET_WORD new_liveout = (child_bd->flag_livein[0] & 176 ~bd->flag_liveout[0]); 177 if (new_liveout) { 178 bd->flag_liveout[0] |= new_liveout; 179 cont = true; 180 } 181 } 182 183 /* Update livein */ 184 for (int i = 0; i < bitset_words; i++) { 185 BITSET_WORD new_livein = (bd->use[i] | 186 (bd->liveout[i] & 187 ~bd->def[i])); 188 if (new_livein & ~bd->livein[i]) { 189 bd->livein[i] |= new_livein; 190 cont = true; 191 } 192 } 193 BITSET_WORD new_livein = (bd->flag_use[0] | 194 (bd->flag_liveout[0] & 195 ~bd->flag_def[0])); 196 if (new_livein & ~bd->flag_livein[0]) { 197 bd->flag_livein[0] |= new_livein; 198 cont = true; 199 } 200 } 201 } 202 } 203 204 /** 205 * Extend the start/end ranges for each variable to account for the 206 * new information calculated from control flow. 207 */ 208 void 209 fs_live_variables::compute_start_end() 210 { 211 foreach_block (block, cfg) { 212 struct block_data *bd = &block_data[block->num]; 213 214 for (int i = 0; i < num_vars; i++) { 215 if (BITSET_TEST(bd->livein, i)) { 216 start[i] = MIN2(start[i], block->start_ip); 217 end[i] = MAX2(end[i], block->start_ip); 218 } 219 220 if (BITSET_TEST(bd->liveout, i)) { 221 start[i] = MIN2(start[i], block->end_ip); 222 end[i] = MAX2(end[i], block->end_ip); 223 } 224 } 225 } 226 } 227 228 fs_live_variables::fs_live_variables(fs_visitor *v, const cfg_t *cfg) 229 : v(v), cfg(cfg) 230 { 231 mem_ctx = ralloc_context(NULL); 232 233 num_vgrfs = v->alloc.count; 234 num_vars = 0; 235 var_from_vgrf = rzalloc_array(mem_ctx, int, num_vgrfs); 236 for (int i = 0; i < num_vgrfs; i++) { 237 var_from_vgrf[i] = num_vars; 238 num_vars += v->alloc.sizes[i]; 239 } 240 241 vgrf_from_var = rzalloc_array(mem_ctx, int, num_vars); 242 for (int i = 0; i < num_vgrfs; i++) { 243 for (unsigned j = 0; j < v->alloc.sizes[i]; j++) { 244 vgrf_from_var[var_from_vgrf[i] + j] = i; 245 } 246 } 247 248 start = ralloc_array(mem_ctx, int, num_vars); 249 end = rzalloc_array(mem_ctx, int, num_vars); 250 for (int i = 0; i < num_vars; i++) { 251 start[i] = MAX_INSTRUCTION; 252 end[i] = -1; 253 } 254 255 block_data= rzalloc_array(mem_ctx, struct block_data, cfg->num_blocks); 256 257 bitset_words = BITSET_WORDS(num_vars); 258 for (int i = 0; i < cfg->num_blocks; i++) { 259 block_data[i].def = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words); 260 block_data[i].use = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words); 261 block_data[i].livein = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words); 262 block_data[i].liveout = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words); 263 264 block_data[i].flag_def[0] = 0; 265 block_data[i].flag_use[0] = 0; 266 block_data[i].flag_livein[0] = 0; 267 block_data[i].flag_liveout[0] = 0; 268 } 269 270 setup_def_use(); 271 compute_live_variables(); 272 compute_start_end(); 273 } 274 275 fs_live_variables::~fs_live_variables() 276 { 277 ralloc_free(mem_ctx); 278 } 279 280 void 281 fs_visitor::invalidate_live_intervals() 282 { 283 ralloc_free(live_intervals); 284 live_intervals = NULL; 285 } 286 287 /** 288 * Compute the live intervals for each virtual GRF. 289 * 290 * This uses the per-component use/def data, but combines it to produce 291 * information about whole VGRFs. 292 */ 293 void 294 fs_visitor::calculate_live_intervals() 295 { 296 if (this->live_intervals) 297 return; 298 299 int num_vgrfs = this->alloc.count; 300 ralloc_free(this->virtual_grf_start); 301 ralloc_free(this->virtual_grf_end); 302 virtual_grf_start = ralloc_array(mem_ctx, int, num_vgrfs); 303 virtual_grf_end = ralloc_array(mem_ctx, int, num_vgrfs); 304 305 for (int i = 0; i < num_vgrfs; i++) { 306 virtual_grf_start[i] = MAX_INSTRUCTION; 307 virtual_grf_end[i] = -1; 308 } 309 310 this->live_intervals = new(mem_ctx) fs_live_variables(this, cfg); 311 312 /* Merge the per-component live ranges to whole VGRF live ranges. */ 313 for (int i = 0; i < live_intervals->num_vars; i++) { 314 int vgrf = live_intervals->vgrf_from_var[i]; 315 virtual_grf_start[vgrf] = MIN2(virtual_grf_start[vgrf], 316 live_intervals->start[i]); 317 virtual_grf_end[vgrf] = MAX2(virtual_grf_end[vgrf], 318 live_intervals->end[i]); 319 } 320 } 321 322 bool 323 fs_live_variables::vars_interfere(int a, int b) 324 { 325 return !(end[b] <= start[a] || 326 end[a] <= start[b]); 327 } 328 329 bool 330 fs_visitor::virtual_grf_interferes(int a, int b) 331 { 332 return !(virtual_grf_end[a] <= virtual_grf_start[b] || 333 virtual_grf_end[b] <= virtual_grf_start[a]); 334 } 335
