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 24 #include "brw_fs.h" 25 #include "brw_cfg.h" 26 27 /** @file brw_fs_cse.cpp 28 * 29 * Support for local common subexpression elimination. 30 * 31 * See Muchnick's Advanced Compiler Design and Implementation, section 32 * 13.1 (p378). 33 */ 34 35 using namespace brw; 36 37 namespace { 38 struct aeb_entry : public exec_node { 39 /** The instruction that generates the expression value. */ 40 fs_inst *generator; 41 42 /** The temporary where the value is stored. */ 43 fs_reg tmp; 44 }; 45 } 46 47 static bool 48 is_expression(const fs_visitor *v, const fs_inst *const inst) 49 { 50 switch (inst->opcode) { 51 case BRW_OPCODE_MOV: 52 case BRW_OPCODE_SEL: 53 case BRW_OPCODE_NOT: 54 case BRW_OPCODE_AND: 55 case BRW_OPCODE_OR: 56 case BRW_OPCODE_XOR: 57 case BRW_OPCODE_SHR: 58 case BRW_OPCODE_SHL: 59 case BRW_OPCODE_ASR: 60 case BRW_OPCODE_CMP: 61 case BRW_OPCODE_CMPN: 62 case BRW_OPCODE_ADD: 63 case BRW_OPCODE_MUL: 64 case SHADER_OPCODE_MULH: 65 case BRW_OPCODE_FRC: 66 case BRW_OPCODE_RNDU: 67 case BRW_OPCODE_RNDD: 68 case BRW_OPCODE_RNDE: 69 case BRW_OPCODE_RNDZ: 70 case BRW_OPCODE_LINE: 71 case BRW_OPCODE_PLN: 72 case BRW_OPCODE_MAD: 73 case BRW_OPCODE_LRP: 74 case FS_OPCODE_FB_READ_LOGICAL: 75 case FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD: 76 case FS_OPCODE_VARYING_PULL_CONSTANT_LOAD_LOGICAL: 77 case FS_OPCODE_VARYING_PULL_CONSTANT_LOAD_GEN7: 78 case FS_OPCODE_CINTERP: 79 case FS_OPCODE_LINTERP: 80 case SHADER_OPCODE_FIND_LIVE_CHANNEL: 81 case SHADER_OPCODE_BROADCAST: 82 case SHADER_OPCODE_MOV_INDIRECT: 83 case SHADER_OPCODE_TEX_LOGICAL: 84 case SHADER_OPCODE_TXD_LOGICAL: 85 case SHADER_OPCODE_TXF_LOGICAL: 86 case SHADER_OPCODE_TXL_LOGICAL: 87 case SHADER_OPCODE_TXS_LOGICAL: 88 case FS_OPCODE_TXB_LOGICAL: 89 case SHADER_OPCODE_TXF_CMS_LOGICAL: 90 case SHADER_OPCODE_TXF_CMS_W_LOGICAL: 91 case SHADER_OPCODE_TXF_UMS_LOGICAL: 92 case SHADER_OPCODE_TXF_MCS_LOGICAL: 93 case SHADER_OPCODE_LOD_LOGICAL: 94 case SHADER_OPCODE_TG4_LOGICAL: 95 case SHADER_OPCODE_TG4_OFFSET_LOGICAL: 96 case FS_OPCODE_PACK: 97 return true; 98 case SHADER_OPCODE_RCP: 99 case SHADER_OPCODE_RSQ: 100 case SHADER_OPCODE_SQRT: 101 case SHADER_OPCODE_EXP2: 102 case SHADER_OPCODE_LOG2: 103 case SHADER_OPCODE_POW: 104 case SHADER_OPCODE_INT_QUOTIENT: 105 case SHADER_OPCODE_INT_REMAINDER: 106 case SHADER_OPCODE_SIN: 107 case SHADER_OPCODE_COS: 108 return inst->mlen < 2; 109 case SHADER_OPCODE_LOAD_PAYLOAD: 110 return !inst->is_copy_payload(v->alloc); 111 default: 112 return inst->is_send_from_grf() && !inst->has_side_effects() && 113 !inst->is_volatile(); 114 } 115 } 116 117 static bool 118 operands_match(const fs_inst *a, const fs_inst *b, bool *negate) 119 { 120 fs_reg *xs = a->src; 121 fs_reg *ys = b->src; 122 123 if (a->opcode == BRW_OPCODE_MAD) { 124 return xs[0].equals(ys[0]) && 125 ((xs[1].equals(ys[1]) && xs[2].equals(ys[2])) || 126 (xs[2].equals(ys[1]) && xs[1].equals(ys[2]))); 127 } else if (a->opcode == BRW_OPCODE_MUL && a->dst.type == BRW_REGISTER_TYPE_F) { 128 bool xs0_negate = xs[0].negate; 129 bool xs1_negate = xs[1].file == IMM ? xs[1].f < 0.0f 130 : xs[1].negate; 131 bool ys0_negate = ys[0].negate; 132 bool ys1_negate = ys[1].file == IMM ? ys[1].f < 0.0f 133 : ys[1].negate; 134 float xs1_imm = xs[1].f; 135 float ys1_imm = ys[1].f; 136 137 xs[0].negate = false; 138 xs[1].negate = false; 139 ys[0].negate = false; 140 ys[1].negate = false; 141 xs[1].f = fabsf(xs[1].f); 142 ys[1].f = fabsf(ys[1].f); 143 144 bool ret = (xs[0].equals(ys[0]) && xs[1].equals(ys[1])) || 145 (xs[1].equals(ys[0]) && xs[0].equals(ys[1])); 146 147 xs[0].negate = xs0_negate; 148 xs[1].negate = xs[1].file == IMM ? false : xs1_negate; 149 ys[0].negate = ys0_negate; 150 ys[1].negate = ys[1].file == IMM ? false : ys1_negate; 151 xs[1].f = xs1_imm; 152 ys[1].f = ys1_imm; 153 154 *negate = (xs0_negate != xs1_negate) != (ys0_negate != ys1_negate); 155 if (*negate && (a->saturate || b->saturate)) 156 return false; 157 return ret; 158 } else if (!a->is_commutative()) { 159 bool match = true; 160 for (int i = 0; i < a->sources; i++) { 161 if (!xs[i].equals(ys[i])) { 162 match = false; 163 break; 164 } 165 } 166 return match; 167 } else { 168 return (xs[0].equals(ys[0]) && xs[1].equals(ys[1])) || 169 (xs[1].equals(ys[0]) && xs[0].equals(ys[1])); 170 } 171 } 172 173 static bool 174 instructions_match(fs_inst *a, fs_inst *b, bool *negate) 175 { 176 return a->opcode == b->opcode && 177 a->force_writemask_all == b->force_writemask_all && 178 a->exec_size == b->exec_size && 179 a->group == b->group && 180 a->saturate == b->saturate && 181 a->predicate == b->predicate && 182 a->predicate_inverse == b->predicate_inverse && 183 a->conditional_mod == b->conditional_mod && 184 a->flag_subreg == b->flag_subreg && 185 a->dst.type == b->dst.type && 186 a->offset == b->offset && 187 a->mlen == b->mlen && 188 a->size_written == b->size_written && 189 a->base_mrf == b->base_mrf && 190 a->eot == b->eot && 191 a->header_size == b->header_size && 192 a->shadow_compare == b->shadow_compare && 193 a->pi_noperspective == b->pi_noperspective && 194 a->target == b->target && 195 a->sources == b->sources && 196 operands_match(a, b, negate); 197 } 198 199 static void 200 create_copy_instr(const fs_builder &bld, fs_inst *inst, fs_reg src, bool negate) 201 { 202 unsigned written = regs_written(inst); 203 unsigned dst_width = 204 DIV_ROUND_UP(inst->dst.component_size(inst->exec_size), REG_SIZE); 205 fs_inst *copy; 206 207 if (inst->opcode == SHADER_OPCODE_LOAD_PAYLOAD || 208 written != dst_width) { 209 fs_reg *payload; 210 int sources, header_size; 211 if (inst->opcode == SHADER_OPCODE_LOAD_PAYLOAD) { 212 sources = inst->sources; 213 header_size = inst->header_size; 214 } else { 215 assert(written % dst_width == 0); 216 sources = written / dst_width; 217 header_size = 0; 218 } 219 220 assert(src.file == VGRF); 221 payload = ralloc_array(bld.shader->mem_ctx, fs_reg, sources); 222 for (int i = 0; i < header_size; i++) { 223 payload[i] = src; 224 src.offset += REG_SIZE; 225 } 226 for (int i = header_size; i < sources; i++) { 227 payload[i] = src; 228 src = offset(src, bld, 1); 229 } 230 copy = bld.LOAD_PAYLOAD(inst->dst, payload, sources, header_size); 231 } else { 232 copy = bld.MOV(inst->dst, src); 233 copy->group = inst->group; 234 copy->force_writemask_all = inst->force_writemask_all; 235 copy->src[0].negate = negate; 236 } 237 assert(regs_written(copy) == written); 238 } 239 240 bool 241 fs_visitor::opt_cse_local(bblock_t *block) 242 { 243 bool progress = false; 244 exec_list aeb; 245 246 void *cse_ctx = ralloc_context(NULL); 247 248 int ip = block->start_ip; 249 foreach_inst_in_block(fs_inst, inst, block) { 250 /* Skip some cases. */ 251 if (is_expression(this, inst) && !inst->is_partial_write() && 252 ((inst->dst.file != ARF && inst->dst.file != FIXED_GRF) || 253 inst->dst.is_null())) 254 { 255 bool found = false; 256 bool negate = false; 257 258 foreach_in_list_use_after(aeb_entry, entry, &aeb) { 259 /* Match current instruction's expression against those in AEB. */ 260 if (!(entry->generator->dst.is_null() && !inst->dst.is_null()) && 261 instructions_match(inst, entry->generator, &negate)) { 262 found = true; 263 progress = true; 264 break; 265 } 266 } 267 268 if (!found) { 269 if (inst->opcode != BRW_OPCODE_MOV || 270 (inst->opcode == BRW_OPCODE_MOV && 271 inst->src[0].file == IMM && 272 inst->src[0].type == BRW_REGISTER_TYPE_VF)) { 273 /* Our first sighting of this expression. Create an entry. */ 274 aeb_entry *entry = ralloc(cse_ctx, aeb_entry); 275 entry->tmp = reg_undef; 276 entry->generator = inst; 277 aeb.push_tail(entry); 278 } 279 } else { 280 /* This is at least our second sighting of this expression. 281 * If we don't have a temporary already, make one. 282 */ 283 bool no_existing_temp = entry->tmp.file == BAD_FILE; 284 if (no_existing_temp && !entry->generator->dst.is_null()) { 285 const fs_builder ibld = fs_builder(this, block, entry->generator) 286 .at(block, entry->generator->next); 287 int written = regs_written(entry->generator); 288 289 entry->tmp = fs_reg(VGRF, alloc.allocate(written), 290 entry->generator->dst.type); 291 292 create_copy_instr(ibld, entry->generator, entry->tmp, false); 293 294 entry->generator->dst = entry->tmp; 295 } 296 297 /* dest <- temp */ 298 if (!inst->dst.is_null()) { 299 assert(inst->size_written == entry->generator->size_written); 300 assert(inst->dst.type == entry->tmp.type); 301 const fs_builder ibld(this, block, inst); 302 303 create_copy_instr(ibld, inst, entry->tmp, negate); 304 } 305 306 /* Set our iterator so that next time through the loop inst->next 307 * will get the instruction in the basic block after the one we've 308 * removed. 309 */ 310 fs_inst *prev = (fs_inst *)inst->prev; 311 312 inst->remove(block); 313 inst = prev; 314 } 315 } 316 317 foreach_in_list_safe(aeb_entry, entry, &aeb) { 318 /* Kill all AEB entries that write a different value to or read from 319 * the flag register if we just wrote it. 320 */ 321 if (inst->flags_written()) { 322 bool negate; /* dummy */ 323 if (entry->generator->flags_read(devinfo) || 324 (entry->generator->flags_written() && 325 !instructions_match(inst, entry->generator, &negate))) { 326 entry->remove(); 327 ralloc_free(entry); 328 continue; 329 } 330 } 331 332 for (int i = 0; i < entry->generator->sources; i++) { 333 fs_reg *src_reg = &entry->generator->src[i]; 334 335 /* Kill all AEB entries that use the destination we just 336 * overwrote. 337 */ 338 if (regions_overlap(inst->dst, inst->size_written, 339 entry->generator->src[i], 340 entry->generator->size_read(i))) { 341 entry->remove(); 342 ralloc_free(entry); 343 break; 344 } 345 346 /* Kill any AEB entries using registers that don't get reused any 347 * more -- a sure sign they'll fail operands_match(). 348 */ 349 if (src_reg->file == VGRF && virtual_grf_end[src_reg->nr] < ip) { 350 entry->remove(); 351 ralloc_free(entry); 352 break; 353 } 354 } 355 } 356 357 ip++; 358 } 359 360 ralloc_free(cse_ctx); 361 362 return progress; 363 } 364 365 bool 366 fs_visitor::opt_cse() 367 { 368 bool progress = false; 369 370 calculate_live_intervals(); 371 372 foreach_block (block, cfg) { 373 progress = opt_cse_local(block) || progress; 374 } 375 376 if (progress) 377 invalidate_live_intervals(); 378 379 return progress; 380 } 381
