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