1 /* 2 * Copyright 2011 Tom Stellard <tstellar (at) gmail.com> 3 * 4 * All Rights Reserved. 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining 7 * a copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sublicense, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice (including the 15 * next paragraph) shall be included in all copies or substantial 16 * portions of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 21 * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE 22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25 * 26 */ 27 28 #include "radeon_variable.h" 29 30 #include "memory_pool.h" 31 #include "radeon_compiler_util.h" 32 #include "radeon_dataflow.h" 33 #include "radeon_list.h" 34 #include "radeon_opcodes.h" 35 #include "radeon_program.h" 36 37 /** 38 * Rewrite the index and writemask for the destination register of var 39 * and its friends to new_index and new_writemask. This function also takes 40 * care of rewriting the swizzles for the sources of var. 41 */ 42 void rc_variable_change_dst( 43 struct rc_variable * var, 44 unsigned int new_index, 45 unsigned int new_writemask) 46 { 47 struct rc_variable * var_ptr; 48 struct rc_list * readers; 49 unsigned int old_mask = rc_variable_writemask_sum(var); 50 unsigned int conversion_swizzle = 51 rc_make_conversion_swizzle(old_mask, new_writemask); 52 53 for (var_ptr = var; var_ptr; var_ptr = var_ptr->Friend) { 54 if (var_ptr->Inst->Type == RC_INSTRUCTION_NORMAL) { 55 rc_normal_rewrite_writemask(var_ptr->Inst, 56 conversion_swizzle); 57 var_ptr->Inst->U.I.DstReg.Index = new_index; 58 } else { 59 struct rc_pair_sub_instruction * sub; 60 if (var_ptr->Dst.WriteMask == RC_MASK_W) { 61 assert(new_writemask & RC_MASK_W); 62 sub = &var_ptr->Inst->U.P.Alpha; 63 } else { 64 sub = &var_ptr->Inst->U.P.RGB; 65 rc_pair_rewrite_writemask(sub, 66 conversion_swizzle); 67 } 68 sub->DestIndex = new_index; 69 } 70 } 71 72 readers = rc_variable_readers_union(var); 73 74 for ( ; readers; readers = readers->Next) { 75 struct rc_reader * reader = readers->Item; 76 if (reader->Inst->Type == RC_INSTRUCTION_NORMAL) { 77 reader->U.I.Src->Index = new_index; 78 reader->U.I.Src->Swizzle = rc_rewrite_swizzle( 79 reader->U.I.Src->Swizzle, conversion_swizzle); 80 } else { 81 struct rc_pair_instruction * pair_inst = 82 &reader->Inst->U.P; 83 unsigned int src_type = rc_source_type_swz( 84 reader->U.P.Arg->Swizzle); 85 86 int src_index = reader->U.P.Arg->Source; 87 if (src_index == RC_PAIR_PRESUB_SRC) { 88 src_index = rc_pair_get_src_index( 89 pair_inst, reader->U.P.Src); 90 } 91 /* Try to delete the old src, it is OK if this fails, 92 * because rc_pair_alloc_source might be able to 93 * find a source the ca be reused. 94 */ 95 if (rc_pair_remove_src(reader->Inst, src_type, 96 src_index, old_mask)) { 97 /* Reuse the source index of the source that 98 * was just deleted and set its register 99 * index. We can't use rc_pair_alloc_source 100 * for this becuase it might return a source 101 * index that is already being used. */ 102 if (src_type & RC_SOURCE_RGB) { 103 pair_inst->RGB.Src[src_index] 104 .Used = 1; 105 pair_inst->RGB.Src[src_index] 106 .Index = new_index; 107 pair_inst->RGB.Src[src_index] 108 .File = RC_FILE_TEMPORARY; 109 } 110 if (src_type & RC_SOURCE_ALPHA) { 111 pair_inst->Alpha.Src[src_index] 112 .Used = 1; 113 pair_inst->Alpha.Src[src_index] 114 .Index = new_index; 115 pair_inst->Alpha.Src[src_index] 116 .File = RC_FILE_TEMPORARY; 117 } 118 } else { 119 src_index = rc_pair_alloc_source( 120 &reader->Inst->U.P, 121 src_type & RC_SOURCE_RGB, 122 src_type & RC_SOURCE_ALPHA, 123 RC_FILE_TEMPORARY, 124 new_index); 125 if (src_index < 0) { 126 rc_error(var->C, "Rewrite of inst %u failed " 127 "Can't allocate source for " 128 "Inst %u src_type=%x " 129 "new_index=%u new_mask=%u\n", 130 var->Inst->IP, reader->Inst->IP, src_type, new_index, new_writemask); 131 continue; 132 } 133 } 134 reader->U.P.Arg->Swizzle = rc_rewrite_swizzle( 135 reader->U.P.Arg->Swizzle, conversion_swizzle); 136 if (reader->U.P.Arg->Source != RC_PAIR_PRESUB_SRC) { 137 reader->U.P.Arg->Source = src_index; 138 } 139 } 140 } 141 } 142 143 /** 144 * Compute the live intervals for var and its friends. 145 */ 146 void rc_variable_compute_live_intervals(struct rc_variable * var) 147 { 148 while(var) { 149 unsigned int i; 150 unsigned int start = var->Inst->IP; 151 152 for (i = 0; i < var->ReaderCount; i++) { 153 unsigned int chan; 154 unsigned int chan_start = start; 155 unsigned int chan_end = var->Readers[i].Inst->IP; 156 unsigned int mask = var->Readers[i].WriteMask; 157 struct rc_instruction * inst; 158 159 /* Extend the live interval of T0 to the start of the 160 * loop for sequences like: 161 * BGNLOOP 162 * read T0 163 * ... 164 * write T0 165 * ENDLOOP 166 */ 167 if (var->Readers[i].Inst->IP < start) { 168 struct rc_instruction * bgnloop = 169 rc_match_endloop(var->Readers[i].Inst); 170 chan_start = bgnloop->IP; 171 } 172 173 /* Extend the live interval of T0 to the start of the 174 * loop in case there is a BRK instruction in the loop 175 * (we don't actually check for a BRK instruction we 176 * assume there is one somewhere in the loop, which 177 * there usually is) for sequences like: 178 * BGNLOOP 179 * ... 180 * conditional BRK 181 * ... 182 * write T0 183 * ENDLOOP 184 * read T0 185 *************************************************** 186 * Extend the live interval of T0 to the end of the 187 * loop for sequences like: 188 * write T0 189 * BGNLOOP 190 * ... 191 * read T0 192 * ENDLOOP 193 */ 194 for (inst = var->Inst; inst != var->Readers[i].Inst; 195 inst = inst->Next) { 196 rc_opcode op = rc_get_flow_control_inst(inst); 197 if (op == RC_OPCODE_ENDLOOP) { 198 struct rc_instruction * bgnloop = 199 rc_match_endloop(inst); 200 if (bgnloop->IP < chan_start) { 201 chan_start = bgnloop->IP; 202 } 203 } else if (op == RC_OPCODE_BGNLOOP) { 204 struct rc_instruction * endloop = 205 rc_match_bgnloop(inst); 206 if (endloop->IP > chan_end) { 207 chan_end = endloop->IP; 208 } 209 } 210 } 211 212 for (chan = 0; chan < 4; chan++) { 213 if ((mask >> chan) & 0x1) { 214 if (!var->Live[chan].Used 215 || chan_start < var->Live[chan].Start) { 216 var->Live[chan].Start = 217 chan_start; 218 } 219 if (!var->Live[chan].Used 220 || chan_end > var->Live[chan].End) { 221 var->Live[chan].End = chan_end; 222 } 223 var->Live[chan].Used = 1; 224 } 225 } 226 } 227 var = var->Friend; 228 } 229 } 230 231 /** 232 * @return 1 if a and b share a reader 233 * @return 0 if they do not 234 */ 235 static unsigned int readers_intersect( 236 struct rc_variable * a, 237 struct rc_variable * b) 238 { 239 unsigned int a_index, b_index; 240 for (a_index = 0; a_index < a->ReaderCount; a_index++) { 241 struct rc_reader reader_a = a->Readers[a_index]; 242 for (b_index = 0; b_index < b->ReaderCount; b_index++) { 243 struct rc_reader reader_b = b->Readers[b_index]; 244 if (reader_a.Inst->Type == RC_INSTRUCTION_NORMAL 245 && reader_b.Inst->Type == RC_INSTRUCTION_NORMAL 246 && reader_a.U.I.Src == reader_b.U.I.Src) { 247 248 return 1; 249 } 250 if (reader_a.Inst->Type == RC_INSTRUCTION_PAIR 251 && reader_b.Inst->Type == RC_INSTRUCTION_PAIR 252 && reader_a.U.P.Src == reader_b.U.P.Src) { 253 254 return 1; 255 } 256 } 257 } 258 return 0; 259 } 260 261 void rc_variable_add_friend( 262 struct rc_variable * var, 263 struct rc_variable * friend) 264 { 265 assert(var->Dst.Index == friend->Dst.Index); 266 while(var->Friend) { 267 var = var->Friend; 268 } 269 var->Friend = friend; 270 } 271 272 struct rc_variable * rc_variable( 273 struct radeon_compiler * c, 274 unsigned int DstFile, 275 unsigned int DstIndex, 276 unsigned int DstWriteMask, 277 struct rc_reader_data * reader_data) 278 { 279 struct rc_variable * new = 280 memory_pool_malloc(&c->Pool, sizeof(struct rc_variable)); 281 memset(new, 0, sizeof(struct rc_variable)); 282 new->C = c; 283 new->Dst.File = DstFile; 284 new->Dst.Index = DstIndex; 285 new->Dst.WriteMask = DstWriteMask; 286 if (reader_data) { 287 new->Inst = reader_data->Writer; 288 new->ReaderCount = reader_data->ReaderCount; 289 new->Readers = reader_data->Readers; 290 } 291 return new; 292 } 293 294 static void get_variable_helper( 295 struct rc_list ** variable_list, 296 struct rc_variable * variable) 297 { 298 struct rc_list * list_ptr; 299 for (list_ptr = *variable_list; list_ptr; list_ptr = list_ptr->Next) { 300 struct rc_variable * var; 301 for (var = list_ptr->Item; var; var = var->Friend) { 302 if (readers_intersect(var, variable)) { 303 rc_variable_add_friend(var, variable); 304 return; 305 } 306 } 307 } 308 rc_list_add(variable_list, rc_list(&variable->C->Pool, variable)); 309 } 310 311 static void get_variable_pair_helper( 312 struct rc_list ** variable_list, 313 struct radeon_compiler * c, 314 struct rc_instruction * inst, 315 struct rc_pair_sub_instruction * sub_inst) 316 { 317 struct rc_reader_data reader_data; 318 struct rc_variable * new_var; 319 rc_register_file file; 320 unsigned int writemask; 321 322 if (sub_inst->Opcode == RC_OPCODE_NOP) { 323 return; 324 } 325 memset(&reader_data, 0, sizeof(struct rc_reader_data)); 326 rc_get_readers_sub(c, inst, sub_inst, &reader_data, NULL, NULL, NULL); 327 328 if (reader_data.ReaderCount == 0) { 329 return; 330 } 331 332 if (sub_inst->WriteMask) { 333 file = RC_FILE_TEMPORARY; 334 writemask = sub_inst->WriteMask; 335 } else if (sub_inst->OutputWriteMask) { 336 file = RC_FILE_OUTPUT; 337 writemask = sub_inst->OutputWriteMask; 338 } else { 339 writemask = 0; 340 file = RC_FILE_NONE; 341 } 342 new_var = rc_variable(c, file, sub_inst->DestIndex, writemask, 343 &reader_data); 344 get_variable_helper(variable_list, new_var); 345 } 346 347 /** 348 * Generate a list of variables used by the shader program. Each instruction 349 * that writes to a register is considered a variable. The struct rc_variable 350 * data structure includes a list of readers and is essentially a 351 * definition-use chain. Any two variables that share a reader are considered 352 * "friends" and they are linked together via the Friend attribute. 353 */ 354 struct rc_list * rc_get_variables(struct radeon_compiler * c) 355 { 356 struct rc_instruction * inst; 357 struct rc_list * variable_list = NULL; 358 359 for (inst = c->Program.Instructions.Next; 360 inst != &c->Program.Instructions; 361 inst = inst->Next) { 362 struct rc_reader_data reader_data; 363 struct rc_variable * new_var; 364 memset(&reader_data, 0, sizeof(reader_data)); 365 366 if (inst->Type == RC_INSTRUCTION_NORMAL) { 367 rc_get_readers(c, inst, &reader_data, NULL, NULL, NULL); 368 if (reader_data.ReaderCount == 0) { 369 continue; 370 } 371 new_var = rc_variable(c, inst->U.I.DstReg.File, 372 inst->U.I.DstReg.Index, 373 inst->U.I.DstReg.WriteMask, &reader_data); 374 get_variable_helper(&variable_list, new_var); 375 } else { 376 get_variable_pair_helper(&variable_list, c, inst, 377 &inst->U.P.RGB); 378 get_variable_pair_helper(&variable_list, c, inst, 379 &inst->U.P.Alpha); 380 } 381 } 382 383 return variable_list; 384 } 385 386 /** 387 * @return The bitwise or of the writemasks of a variable and all of its 388 * friends. 389 */ 390 unsigned int rc_variable_writemask_sum(struct rc_variable * var) 391 { 392 unsigned int writemask = 0; 393 while(var) { 394 writemask |= var->Dst.WriteMask; 395 var = var->Friend; 396 } 397 return writemask; 398 } 399 400 /* 401 * @return A list of readers for a variable and its friends. Readers 402 * that read from two different variable friends are only included once in 403 * this list. 404 */ 405 struct rc_list * rc_variable_readers_union(struct rc_variable * var) 406 { 407 struct rc_list * list = NULL; 408 while (var) { 409 unsigned int i; 410 for (i = 0; i < var->ReaderCount; i++) { 411 struct rc_list * temp; 412 struct rc_reader * a = &var->Readers[i]; 413 unsigned int match = 0; 414 for (temp = list; temp; temp = temp->Next) { 415 struct rc_reader * b = temp->Item; 416 if (a->Inst->Type != b->Inst->Type) { 417 continue; 418 } 419 if (a->Inst->Type == RC_INSTRUCTION_NORMAL) { 420 if (a->U.I.Src == b->U.I.Src) { 421 match = 1; 422 break; 423 } 424 } 425 if (a->Inst->Type == RC_INSTRUCTION_PAIR) { 426 if (a->U.P.Arg == b->U.P.Arg 427 && a->U.P.Src == b->U.P.Src) { 428 match = 1; 429 break; 430 } 431 } 432 } 433 if (match) { 434 continue; 435 } 436 rc_list_add(&list, rc_list(&var->C->Pool, a)); 437 } 438 var = var->Friend; 439 } 440 return list; 441 } 442 443 static unsigned int reader_equals_src( 444 struct rc_reader reader, 445 unsigned int src_type, 446 void * src) 447 { 448 if (reader.Inst->Type != src_type) { 449 return 0; 450 } 451 if (src_type == RC_INSTRUCTION_NORMAL) { 452 return reader.U.I.Src == src; 453 } else { 454 return reader.U.P.Src == src; 455 } 456 } 457 458 static unsigned int variable_writes_src( 459 struct rc_variable * var, 460 unsigned int src_type, 461 void * src) 462 { 463 unsigned int i; 464 for (i = 0; i < var->ReaderCount; i++) { 465 if (reader_equals_src(var->Readers[i], src_type, src)) { 466 return 1; 467 } 468 } 469 return 0; 470 } 471 472 473 struct rc_list * rc_variable_list_get_writers( 474 struct rc_list * var_list, 475 unsigned int src_type, 476 void * src) 477 { 478 struct rc_list * list_ptr; 479 struct rc_list * writer_list = NULL; 480 for (list_ptr = var_list; list_ptr; list_ptr = list_ptr->Next) { 481 struct rc_variable * var = list_ptr->Item; 482 if (variable_writes_src(var, src_type, src)) { 483 struct rc_variable * friend; 484 rc_list_add(&writer_list, rc_list(&var->C->Pool, var)); 485 for (friend = var->Friend; friend; 486 friend = friend->Friend) { 487 if (variable_writes_src(friend, src_type, src)) { 488 rc_list_add(&writer_list, 489 rc_list(&var->C->Pool, friend)); 490 } 491 } 492 /* Once we have indentifed the variable and its 493 * friends that write this source, we can stop 494 * stop searching, because we know know of the 495 * other variables in the list will write this source. 496 * If they did they would be friends of var. 497 */ 498 break; 499 } 500 } 501 return writer_list; 502 } 503 504 struct rc_list * rc_variable_list_get_writers_one_reader( 505 struct rc_list * var_list, 506 unsigned int src_type, 507 void * src) 508 { 509 struct rc_list * writer_list = 510 rc_variable_list_get_writers(var_list, src_type, src); 511 struct rc_list * reader_list = 512 rc_variable_readers_union(writer_list->Item); 513 if (rc_list_count(reader_list) > 1) { 514 return NULL; 515 } else { 516 return writer_list; 517 } 518 } 519 520 void rc_variable_print(struct rc_variable * var) 521 { 522 unsigned int i; 523 while (var) { 524 fprintf(stderr, "%u: TEMP[%u].%u: ", 525 var->Inst->IP, var->Dst.Index, var->Dst.WriteMask); 526 for (i = 0; i < 4; i++) { 527 fprintf(stderr, "chan %u: start=%u end=%u ", i, 528 var->Live[i].Start, var->Live[i].End); 529 } 530 fprintf(stderr, "%u readers\n", var->ReaderCount); 531 if (var->Friend) { 532 fprintf(stderr, "Friend: \n\t"); 533 } 534 var = var->Friend; 535 } 536 } 537
