prog_optimize.c revision 05749542384abc4d4776bfe2a386b6396002e0df
1/* 2 * Mesa 3-D graphics library 3 * Version: 7.5 4 * 5 * Copyright (C) 2009 VMware, Inc. All Rights Reserved. 6 * 7 * Permission is hereby granted, free of charge, to any person obtaining a 8 * copy of this software and associated documentation files (the "Software"), 9 * to deal in the Software without restriction, including without limitation 10 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 11 * and/or sell copies of the Software, and to permit persons to whom the 12 * Software is furnished to do so, subject to the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be included 15 * in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 20 * VMWARE BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 21 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 22 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 23 */ 24 25 26 27#include "main/glheader.h" 28#include "main/context.h" 29#include "main/macros.h" 30#include "program.h" 31#include "prog_instruction.h" 32#include "prog_optimize.h" 33#include "prog_print.h" 34 35 36#define MAX_LOOP_NESTING 50 37 38 39static GLboolean dbg = GL_FALSE; 40 41 42/** 43 * In 'prog' remove instruction[i] if removeFlags[i] == TRUE. 44 * \return number of instructions removed 45 */ 46static GLuint 47remove_instructions(struct gl_program *prog, const GLboolean *removeFlags) 48{ 49 GLint i, removeEnd = 0, removeCount = 0; 50 GLuint totalRemoved = 0; 51 52 /* go backward */ 53 for (i = prog->NumInstructions - 1; i >= 0; i--) { 54 if (removeFlags[i]) { 55 totalRemoved++; 56 if (removeCount == 0) { 57 /* begin a run of instructions to remove */ 58 removeEnd = i; 59 removeCount = 1; 60 } 61 else { 62 /* extend the run of instructions to remove */ 63 removeCount++; 64 } 65 } 66 else { 67 /* don't remove this instruction, but check if the preceeding 68 * instructions are to be removed. 69 */ 70 if (removeCount > 0) { 71 GLint removeStart = removeEnd - removeCount + 1; 72 _mesa_delete_instructions(prog, removeStart, removeCount); 73 removeStart = removeCount = 0; /* reset removal info */ 74 } 75 } 76 } 77 return totalRemoved; 78} 79 80 81/** 82 * Remap register indexes according to map. 83 * \param prog the program to search/replace 84 * \param file the type of register file to search/replace 85 * \param map maps old register indexes to new indexes 86 */ 87static void 88replace_regs(struct gl_program *prog, gl_register_file file, const GLint map[]) 89{ 90 GLuint i; 91 92 for (i = 0; i < prog->NumInstructions; i++) { 93 struct prog_instruction *inst = prog->Instructions + i; 94 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); 95 GLuint j; 96 for (j = 0; j < numSrc; j++) { 97 if (inst->SrcReg[j].File == file) { 98 GLuint index = inst->SrcReg[j].Index; 99 ASSERT(map[index] >= 0); 100 inst->SrcReg[j].Index = map[index]; 101 } 102 } 103 if (inst->DstReg.File == file) { 104 const GLuint index = inst->DstReg.Index; 105 ASSERT(map[index] >= 0); 106 inst->DstReg.Index = map[index]; 107 } 108 } 109} 110 111 112/** 113 * Consolidate temporary registers to use low numbers. For example, if the 114 * shader only uses temps 4, 5, 8, replace them with 0, 1, 2. 115 */ 116static void 117_mesa_consolidate_registers(struct gl_program *prog) 118{ 119 GLboolean tempUsed[MAX_PROGRAM_TEMPS]; 120 GLint tempMap[MAX_PROGRAM_TEMPS]; 121 GLuint tempMax = 0, i; 122 123 if (dbg) { 124 _mesa_printf("Optimize: Begin register consolidation\n"); 125 } 126 127 memset(tempUsed, 0, sizeof(tempUsed)); 128 129 for (i = 0; i < MAX_PROGRAM_TEMPS; i++) { 130 tempMap[i] = -1; 131 } 132 133 /* set tempUsed[i] if temporary [i] is referenced */ 134 for (i = 0; i < prog->NumInstructions; i++) { 135 const struct prog_instruction *inst = prog->Instructions + i; 136 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); 137 GLuint j; 138 for (j = 0; j < numSrc; j++) { 139 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) { 140 const GLuint index = inst->SrcReg[j].Index; 141 ASSERT(index < MAX_PROGRAM_TEMPS); 142 tempUsed[index] = GL_TRUE; 143 tempMax = MAX2(tempMax, index); 144 break; 145 } 146 } 147 if (inst->DstReg.File == PROGRAM_TEMPORARY) { 148 const GLuint index = inst->DstReg.Index; 149 ASSERT(index < MAX_PROGRAM_TEMPS); 150 tempUsed[index] = GL_TRUE; 151 tempMax = MAX2(tempMax, index); 152 } 153 } 154 155 /* allocate a new index for each temp that's used */ 156 { 157 GLuint freeTemp = 0; 158 for (i = 0; i <= tempMax; i++) { 159 if (tempUsed[i]) { 160 tempMap[i] = freeTemp++; 161 /*_mesa_printf("replace %u with %u\n", i, tempMap[i]);*/ 162 } 163 } 164 if (freeTemp == tempMax + 1) { 165 /* no consolidation possible */ 166 return; 167 } 168 if (dbg) { 169 _mesa_printf("Replace regs 0..%u with 0..%u\n", tempMax, freeTemp-1); 170 } 171 } 172 173 replace_regs(prog, PROGRAM_TEMPORARY, tempMap); 174 175 if (dbg) { 176 _mesa_printf("Optimize: End register consolidation\n"); 177 } 178} 179 180 181/** 182 * Remove dead instructions from the given program. 183 * This is very primitive for now. Basically look for temp registers 184 * that are written to but never read. Remove any instructions that 185 * write to such registers. Be careful with condition code setters. 186 */ 187static void 188_mesa_remove_dead_code(struct gl_program *prog) 189{ 190 GLboolean tempWritten[MAX_PROGRAM_TEMPS], tempRead[MAX_PROGRAM_TEMPS]; 191 GLboolean *removeInst; /* per-instruction removal flag */ 192 GLuint i, rem; 193 194 memset(tempWritten, 0, sizeof(tempWritten)); 195 memset(tempRead, 0, sizeof(tempRead)); 196 197 if (dbg) { 198 _mesa_printf("Optimize: Begin dead code removal\n"); 199 /*_mesa_print_program(prog);*/ 200 } 201 202 removeInst = (GLboolean *) 203 _mesa_calloc(prog->NumInstructions * sizeof(GLboolean)); 204 205 /* Determine which temps are read and written */ 206 for (i = 0; i < prog->NumInstructions; i++) { 207 const struct prog_instruction *inst = prog->Instructions + i; 208 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); 209 GLuint j; 210 211 /* check src regs */ 212 for (j = 0; j < numSrc; j++) { 213 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) { 214 const GLuint index = inst->SrcReg[j].Index; 215 ASSERT(index < MAX_PROGRAM_TEMPS); 216 217 if (inst->SrcReg[j].RelAddr) { 218 if (dbg) 219 _mesa_printf("abort remove dead code (indirect temp)\n"); 220 _mesa_free(removeInst); 221 return; 222 } 223 224 tempRead[index] = GL_TRUE; 225 } 226 } 227 228 /* check dst reg */ 229 if (inst->DstReg.File == PROGRAM_TEMPORARY) { 230 const GLuint index = inst->DstReg.Index; 231 ASSERT(index < MAX_PROGRAM_TEMPS); 232 233 if (inst->DstReg.RelAddr) { 234 if (dbg) 235 _mesa_printf("abort remove dead code (indirect temp)\n"); 236 _mesa_free(removeInst); 237 return; 238 } 239 240 tempWritten[index] = GL_TRUE; 241 if (inst->CondUpdate) { 242 /* If we're writing to this register and setting condition 243 * codes we cannot remove the instruction. Prevent removal 244 * by setting the 'read' flag. 245 */ 246 tempRead[index] = GL_TRUE; 247 } 248 } 249 } 250 251 if (dbg) { 252 for (i = 0; i < MAX_PROGRAM_TEMPS; i++) { 253 if (tempWritten[i] && !tempRead[i]) 254 _mesa_printf("Remove writes to tmp %u\n", i); 255 } 256 } 257 258 /* find instructions that write to dead registers, flag for removal */ 259 for (i = 0; i < prog->NumInstructions; i++) { 260 const struct prog_instruction *inst = prog->Instructions + i; 261 if (inst->DstReg.File == PROGRAM_TEMPORARY) { 262 GLint index = inst->DstReg.Index; 263 removeInst[i] = (tempWritten[index] && !tempRead[index]); 264 if (dbg && removeInst[i]) { 265 _mesa_printf("Remove inst %u: ", i); 266 _mesa_print_instruction(inst); 267 } 268 } 269 } 270 271 /* now remove the instructions which aren't needed */ 272 rem = remove_instructions(prog, removeInst); 273 274 _mesa_free(removeInst); 275 276 if (dbg) { 277 _mesa_printf("Optimize: End dead code removal. %u instructions removed\n", rem); 278 /*_mesa_print_program(prog);*/ 279 } 280} 281 282 283enum temp_use 284{ 285 READ, 286 WRITE, 287 FLOW, 288 END 289}; 290 291/** 292 * Scan forward in program from 'start' for the next occurance of TEMP[index]. 293 * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator 294 * that we can't look further. 295 */ 296static enum temp_use 297find_next_temp_use(const struct gl_program *prog, GLuint start, GLuint index) 298{ 299 GLuint i; 300 301 for (i = start; i < prog->NumInstructions; i++) { 302 const struct prog_instruction *inst = prog->Instructions + i; 303 switch (inst->Opcode) { 304 case OPCODE_BGNLOOP: 305 case OPCODE_ENDLOOP: 306 case OPCODE_BGNSUB: 307 case OPCODE_ENDSUB: 308 return FLOW; 309 default: 310 { 311 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); 312 GLuint j; 313 for (j = 0; j < numSrc; j++) { 314 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY && 315 inst->SrcReg[j].Index == index) 316 return READ; 317 } 318 if (inst->DstReg.File == PROGRAM_TEMPORARY && 319 inst->DstReg.Index == index) 320 return WRITE; 321 } 322 } 323 } 324 325 return END; 326} 327 328 329/** 330 * Try to remove extraneous MOV instructions from the given program. 331 */ 332static void 333_mesa_remove_extra_moves(struct gl_program *prog) 334{ 335 GLboolean *removeInst; /* per-instruction removal flag */ 336 GLuint i, rem, loopNesting = 0, subroutineNesting = 0; 337 338 if (dbg) { 339 _mesa_printf("Optimize: Begin remove extra moves\n"); 340 _mesa_print_program(prog); 341 } 342 343 removeInst = (GLboolean *) 344 _mesa_calloc(prog->NumInstructions * sizeof(GLboolean)); 345 346 /* 347 * Look for sequences such as this: 348 * FOO tmpX, arg0, arg1; 349 * MOV tmpY, tmpX; 350 * and convert into: 351 * FOO tmpY, arg0, arg1; 352 */ 353 354 for (i = 0; i < prog->NumInstructions; i++) { 355 const struct prog_instruction *inst = prog->Instructions + i; 356 357 switch (inst->Opcode) { 358 case OPCODE_BGNLOOP: 359 loopNesting++; 360 break; 361 case OPCODE_ENDLOOP: 362 loopNesting--; 363 break; 364 case OPCODE_BGNSUB: 365 subroutineNesting++; 366 break; 367 case OPCODE_ENDSUB: 368 subroutineNesting--; 369 break; 370 case OPCODE_MOV: 371 if (i > 0 && 372 loopNesting == 0 && 373 subroutineNesting == 0 && 374 inst->SrcReg[0].File == PROGRAM_TEMPORARY && 375 inst->SrcReg[0].Swizzle == SWIZZLE_XYZW) { 376 /* see if this MOV can be removed */ 377 const GLuint tempIndex = inst->SrcReg[0].Index; 378 struct prog_instruction *prevInst; 379 GLuint prevI; 380 381 /* get pointer to previous instruction */ 382 prevI = i - 1; 383 while (removeInst[prevI] && prevI > 0) 384 prevI--; 385 prevInst = prog->Instructions + prevI; 386 387 if (prevInst->DstReg.File == PROGRAM_TEMPORARY && 388 prevInst->DstReg.Index == tempIndex && 389 prevInst->DstReg.WriteMask == WRITEMASK_XYZW) { 390 391 enum temp_use next_use = 392 find_next_temp_use(prog, i + 1, tempIndex); 393 394 if (next_use == WRITE || next_use == END) { 395 /* OK, we can safely remove this MOV instruction. 396 * Transform: 397 * prevI: FOO tempIndex, x, y; 398 * i: MOV z, tempIndex; 399 * Into: 400 * prevI: FOO z, x, y; 401 */ 402 403 /* patch up prev inst */ 404 prevInst->DstReg.File = inst->DstReg.File; 405 prevInst->DstReg.Index = inst->DstReg.Index; 406 407 /* flag this instruction for removal */ 408 removeInst[i] = GL_TRUE; 409 410 if (dbg) { 411 _mesa_printf("Remove MOV at %u\n", i); 412 _mesa_printf("new prev inst %u: ", prevI); 413 _mesa_print_instruction(prevInst); 414 } 415 } 416 } 417 } 418 break; 419 default: 420 ; /* nothing */ 421 } 422 } 423 424 /* now remove the instructions which aren't needed */ 425 rem = remove_instructions(prog, removeInst); 426 427 _mesa_free(removeInst); 428 429 if (dbg) { 430 _mesa_printf("Optimize: End remove extra moves. %u instructions removed\n", rem); 431 /*_mesa_print_program(prog);*/ 432 } 433} 434 435 436/** A live register interval */ 437struct interval 438{ 439 GLuint Reg; /** The temporary register index */ 440 GLuint Start, End; /** Start/end instruction numbers */ 441}; 442 443 444/** A list of register intervals */ 445struct interval_list 446{ 447 GLuint Num; 448 struct interval Intervals[MAX_PROGRAM_TEMPS]; 449}; 450 451 452static void 453append_interval(struct interval_list *list, const struct interval *inv) 454{ 455 list->Intervals[list->Num++] = *inv; 456} 457 458 459/** Insert interval inv into list, sorted by interval end */ 460static void 461insert_interval_by_end(struct interval_list *list, const struct interval *inv) 462{ 463 /* XXX we could do a binary search insertion here since list is sorted */ 464 GLint i = list->Num - 1; 465 while (i >= 0 && list->Intervals[i].End > inv->End) { 466 list->Intervals[i + 1] = list->Intervals[i]; 467 i--; 468 } 469 list->Intervals[i + 1] = *inv; 470 list->Num++; 471 472#ifdef DEBUG 473 { 474 GLuint i; 475 for (i = 0; i + 1 < list->Num; i++) { 476 ASSERT(list->Intervals[i].End <= list->Intervals[i + 1].End); 477 } 478 } 479#endif 480} 481 482 483/** Remove the given interval from the interval list */ 484static void 485remove_interval(struct interval_list *list, const struct interval *inv) 486{ 487 /* XXX we could binary search since list is sorted */ 488 GLuint k; 489 for (k = 0; k < list->Num; k++) { 490 if (list->Intervals[k].Reg == inv->Reg) { 491 /* found, remove it */ 492 ASSERT(list->Intervals[k].Start == inv->Start); 493 ASSERT(list->Intervals[k].End == inv->End); 494 while (k < list->Num - 1) { 495 list->Intervals[k] = list->Intervals[k + 1]; 496 k++; 497 } 498 list->Num--; 499 return; 500 } 501 } 502} 503 504 505/** called by qsort() */ 506static int 507compare_start(const void *a, const void *b) 508{ 509 const struct interval *ia = (const struct interval *) a; 510 const struct interval *ib = (const struct interval *) b; 511 if (ia->Start < ib->Start) 512 return -1; 513 else if (ia->Start > ib->Start) 514 return +1; 515 else 516 return 0; 517} 518 519/** sort the interval list according to interval starts */ 520static void 521sort_interval_list_by_start(struct interval_list *list) 522{ 523 qsort(list->Intervals, list->Num, sizeof(struct interval), compare_start); 524#ifdef DEBUG 525 { 526 GLuint i; 527 for (i = 0; i + 1 < list->Num; i++) { 528 ASSERT(list->Intervals[i].Start <= list->Intervals[i + 1].Start); 529 } 530 } 531#endif 532} 533 534 535/** 536 * Update the intermediate interval info for register 'index' and 537 * instruction 'ic'. 538 */ 539static void 540update_interval(GLint intBegin[], GLint intEnd[], GLuint index, GLuint ic) 541{ 542 ASSERT(index < MAX_PROGRAM_TEMPS); 543 if (intBegin[index] == -1) { 544 ASSERT(intEnd[index] == -1); 545 intBegin[index] = intEnd[index] = ic; 546 } 547 else { 548 intEnd[index] = ic; 549 } 550} 551 552 553/** 554 * Find first/last instruction that references each temporary register. 555 */ 556GLboolean 557_mesa_find_temp_intervals(const struct prog_instruction *instructions, 558 GLuint numInstructions, 559 GLint intBegin[MAX_PROGRAM_TEMPS], 560 GLint intEnd[MAX_PROGRAM_TEMPS]) 561{ 562 struct loop_info 563 { 564 GLuint Start, End; /**< Start, end instructions of loop */ 565 }; 566 struct loop_info loopStack[MAX_LOOP_NESTING]; 567 GLuint loopStackDepth = 0; 568 GLuint i; 569 570 for (i = 0; i < MAX_PROGRAM_TEMPS; i++){ 571 intBegin[i] = intEnd[i] = -1; 572 } 573 574 /* Scan instructions looking for temporary registers */ 575 for (i = 0; i < numInstructions; i++) { 576 const struct prog_instruction *inst = instructions + i; 577 if (inst->Opcode == OPCODE_BGNLOOP) { 578 loopStack[loopStackDepth].Start = i; 579 loopStack[loopStackDepth].End = inst->BranchTarget; 580 loopStackDepth++; 581 } 582 else if (inst->Opcode == OPCODE_ENDLOOP) { 583 loopStackDepth--; 584 } 585 else if (inst->Opcode == OPCODE_CAL) { 586 return GL_FALSE; 587 } 588 else { 589 const GLuint numSrc = 3;/*_mesa_num_inst_src_regs(inst->Opcode);*/ 590 GLuint j; 591 for (j = 0; j < numSrc; j++) { 592 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) { 593 const GLuint index = inst->SrcReg[j].Index; 594 if (inst->SrcReg[j].RelAddr) 595 return GL_FALSE; 596 update_interval(intBegin, intEnd, index, i); 597 if (loopStackDepth > 0) { 598 /* extend temp register's interval to end of loop */ 599 GLuint loopEnd = loopStack[loopStackDepth - 1].End; 600 update_interval(intBegin, intEnd, index, loopEnd); 601 } 602 } 603 } 604 if (inst->DstReg.File == PROGRAM_TEMPORARY) { 605 const GLuint index = inst->DstReg.Index; 606 if (inst->DstReg.RelAddr) 607 return GL_FALSE; 608 update_interval(intBegin, intEnd, index, i); 609 if (loopStackDepth > 0) { 610 /* extend temp register's interval to end of loop */ 611 GLuint loopEnd = loopStack[loopStackDepth - 1].End; 612 update_interval(intBegin, intEnd, index, loopEnd); 613 } 614 } 615 } 616 } 617 618 return GL_TRUE; 619} 620 621 622/** 623 * Find the live intervals for each temporary register in the program. 624 * For register R, the interval [A,B] indicates that R is referenced 625 * from instruction A through instruction B. 626 * Special consideration is needed for loops and subroutines. 627 * \return GL_TRUE if success, GL_FALSE if we cannot proceed for some reason 628 */ 629static GLboolean 630find_live_intervals(struct gl_program *prog, 631 struct interval_list *liveIntervals) 632{ 633 GLint intBegin[MAX_PROGRAM_TEMPS], intEnd[MAX_PROGRAM_TEMPS]; 634 GLuint i; 635 636 /* 637 * Note: we'll return GL_FALSE below if we find relative indexing 638 * into the TEMP register file. We can't handle that yet. 639 * We also give up on subroutines for now. 640 */ 641 642 if (dbg) { 643 _mesa_printf("Optimize: Begin find intervals\n"); 644 } 645 646 /* build intermediate arrays */ 647 if (!_mesa_find_temp_intervals(prog->Instructions, prog->NumInstructions, 648 intBegin, intEnd)) 649 return GL_FALSE; 650 651 /* Build live intervals list from intermediate arrays */ 652 liveIntervals->Num = 0; 653 for (i = 0; i < MAX_PROGRAM_TEMPS; i++) { 654 if (intBegin[i] >= 0) { 655 struct interval inv; 656 inv.Reg = i; 657 inv.Start = intBegin[i]; 658 inv.End = intEnd[i]; 659 append_interval(liveIntervals, &inv); 660 } 661 } 662 663 /* Sort the list according to interval starts */ 664 sort_interval_list_by_start(liveIntervals); 665 666 if (dbg) { 667 /* print interval info */ 668 for (i = 0; i < liveIntervals->Num; i++) { 669 const struct interval *inv = liveIntervals->Intervals + i; 670 _mesa_printf("Reg[%d] live [%d, %d]:", 671 inv->Reg, inv->Start, inv->End); 672 if (1) { 673 int j; 674 for (j = 0; j < inv->Start; j++) 675 _mesa_printf(" "); 676 for (j = inv->Start; j <= inv->End; j++) 677 _mesa_printf("x"); 678 } 679 _mesa_printf("\n"); 680 } 681 } 682 683 return GL_TRUE; 684} 685 686 687/** Scan the array of used register flags to find free entry */ 688static GLint 689alloc_register(GLboolean usedRegs[MAX_PROGRAM_TEMPS]) 690{ 691 GLuint k; 692 for (k = 0; k < MAX_PROGRAM_TEMPS; k++) { 693 if (!usedRegs[k]) { 694 usedRegs[k] = GL_TRUE; 695 return k; 696 } 697 } 698 return -1; 699} 700 701 702/** 703 * This function implements "Linear Scan Register Allocation" to reduce 704 * the number of temporary registers used by the program. 705 * 706 * We compute the "live interval" for all temporary registers then 707 * examine the overlap of the intervals to allocate new registers. 708 * Basically, if two intervals do not overlap, they can use the same register. 709 */ 710static void 711_mesa_reallocate_registers(struct gl_program *prog) 712{ 713 struct interval_list liveIntervals; 714 GLint registerMap[MAX_PROGRAM_TEMPS]; 715 GLboolean usedRegs[MAX_PROGRAM_TEMPS]; 716 GLuint i; 717 GLint maxTemp = -1; 718 719 if (dbg) { 720 _mesa_printf("Optimize: Begin live-interval register reallocation\n"); 721 _mesa_print_program(prog); 722 } 723 724 for (i = 0; i < MAX_PROGRAM_TEMPS; i++){ 725 registerMap[i] = -1; 726 usedRegs[i] = GL_FALSE; 727 } 728 729 if (!find_live_intervals(prog, &liveIntervals)) { 730 if (dbg) 731 _mesa_printf("Aborting register reallocation\n"); 732 return; 733 } 734 735 { 736 struct interval_list activeIntervals; 737 activeIntervals.Num = 0; 738 739 /* loop over live intervals, allocating a new register for each */ 740 for (i = 0; i < liveIntervals.Num; i++) { 741 const struct interval *live = liveIntervals.Intervals + i; 742 743 if (dbg) 744 _mesa_printf("Consider register %u\n", live->Reg); 745 746 /* Expire old intervals. Intervals which have ended with respect 747 * to the live interval can have their remapped registers freed. 748 */ 749 { 750 GLint j; 751 for (j = 0; j < activeIntervals.Num; j++) { 752 const struct interval *inv = activeIntervals.Intervals + j; 753 if (inv->End >= live->Start) { 754 /* Stop now. Since the activeInterval list is sorted 755 * we know we don't have to go further. 756 */ 757 break; 758 } 759 else { 760 /* Interval 'inv' has expired */ 761 const GLint regNew = registerMap[inv->Reg]; 762 ASSERT(regNew >= 0); 763 764 if (dbg) 765 _mesa_printf(" expire interval for reg %u\n", inv->Reg); 766 767 /* remove interval j from active list */ 768 remove_interval(&activeIntervals, inv); 769 j--; /* counter-act j++ in for-loop above */ 770 771 /* return register regNew to the free pool */ 772 if (dbg) 773 _mesa_printf(" free reg %d\n", regNew); 774 ASSERT(usedRegs[regNew] == GL_TRUE); 775 usedRegs[regNew] = GL_FALSE; 776 } 777 } 778 } 779 780 /* find a free register for this live interval */ 781 { 782 const GLint k = alloc_register(usedRegs); 783 if (k < 0) { 784 /* out of registers, give up */ 785 return; 786 } 787 registerMap[live->Reg] = k; 788 maxTemp = MAX2(maxTemp, k); 789 if (dbg) 790 _mesa_printf(" remap register %u -> %d\n", live->Reg, k); 791 } 792 793 /* Insert this live interval into the active list which is sorted 794 * by increasing end points. 795 */ 796 insert_interval_by_end(&activeIntervals, live); 797 } 798 } 799 800 if (maxTemp + 1 < liveIntervals.Num) { 801 /* OK, we've reduced the number of registers needed. 802 * Scan the program and replace all the old temporary register 803 * indexes with the new indexes. 804 */ 805 replace_regs(prog, PROGRAM_TEMPORARY, registerMap); 806 807 prog->NumTemporaries = maxTemp + 1; 808 } 809 810 if (dbg) { 811 _mesa_printf("Optimize: End live-interval register reallocation\n"); 812 _mesa_printf("Num temp regs before: %u after: %u\n", 813 liveIntervals.Num, maxTemp + 1); 814 _mesa_print_program(prog); 815 } 816} 817 818 819/** 820 * Apply optimizations to the given program to eliminate unnecessary 821 * instructions, temp regs, etc. 822 */ 823void 824_mesa_optimize_program(GLcontext *ctx, struct gl_program *program) 825{ 826 if (1) 827 _mesa_remove_dead_code(program); 828 829 if (0) /* not tested much yet */ 830 _mesa_remove_extra_moves(program); 831 832 if (0) 833 _mesa_consolidate_registers(program); 834 else 835 _mesa_reallocate_registers(program); 836} 837