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