prog_optimize.c revision 12256fc2b2e0a54db24210a4b86f6fb5919d0fe8
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 return; 221 } 222 223 tempRead[index] = GL_TRUE; 224 } 225 } 226 227 /* check dst reg */ 228 if (inst->DstReg.File == PROGRAM_TEMPORARY) { 229 const GLuint index = inst->DstReg.Index; 230 ASSERT(index < MAX_PROGRAM_TEMPS); 231 232 if (inst->DstReg.RelAddr) { 233 if (dbg) 234 _mesa_printf("abort remove dead code (indirect temp)\n"); 235 return; 236 } 237 238 tempWritten[index] = GL_TRUE; 239 if (inst->CondUpdate) { 240 /* If we're writing to this register and setting condition 241 * codes we cannot remove the instruction. Prevent removal 242 * by setting the 'read' flag. 243 */ 244 tempRead[index] = GL_TRUE; 245 } 246 } 247 } 248 249 if (dbg) { 250 for (i = 0; i < MAX_PROGRAM_TEMPS; i++) { 251 if (tempWritten[i] && !tempRead[i]) 252 _mesa_printf("Remove writes to tmp %u\n", i); 253 } 254 } 255 256 /* find instructions that write to dead registers, flag for removal */ 257 for (i = 0; i < prog->NumInstructions; i++) { 258 const struct prog_instruction *inst = prog->Instructions + i; 259 if (inst->DstReg.File == PROGRAM_TEMPORARY) { 260 GLint index = inst->DstReg.Index; 261 removeInst[i] = (tempWritten[index] && !tempRead[index]); 262 if (dbg && removeInst[i]) { 263 _mesa_printf("Remove inst %u: ", i); 264 _mesa_print_instruction(inst); 265 } 266 } 267 } 268 269 /* now remove the instructions which aren't needed */ 270 rem = remove_instructions(prog, removeInst); 271 272 _mesa_free(removeInst); 273 274 if (dbg) { 275 _mesa_printf("Optimize: End dead code removal. %u instructions removed\n", rem); 276 /*_mesa_print_program(prog);*/ 277 } 278} 279 280 281enum temp_use 282{ 283 READ, 284 WRITE, 285 FLOW, 286 END 287}; 288 289/** 290 * Scan forward in program from 'start' for the next occurance of TEMP[index]. 291 * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator 292 * that we can't look further. 293 */ 294static enum temp_use 295find_next_temp_use(const struct gl_program *prog, GLuint start, GLuint index) 296{ 297 GLuint i; 298 299 for (i = start; i < prog->NumInstructions; i++) { 300 const struct prog_instruction *inst = prog->Instructions + i; 301 switch (inst->Opcode) { 302 case OPCODE_BGNLOOP: 303 case OPCODE_ENDLOOP: 304 case OPCODE_BGNSUB: 305 case OPCODE_ENDSUB: 306 return FLOW; 307 default: 308 { 309 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); 310 GLuint j; 311 for (j = 0; j < numSrc; j++) { 312 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY && 313 inst->SrcReg[j].Index == index) 314 return READ; 315 } 316 if (inst->DstReg.File == PROGRAM_TEMPORARY && 317 inst->DstReg.Index == index) 318 return WRITE; 319 } 320 } 321 } 322 323 return END; 324} 325 326 327/** 328 * Try to remove extraneous MOV instructions from the given program. 329 */ 330static void 331_mesa_remove_extra_moves(struct gl_program *prog) 332{ 333 GLboolean *removeInst; /* per-instruction removal flag */ 334 GLuint i, rem, loopNesting = 0, subroutineNesting = 0; 335 336 if (dbg) { 337 _mesa_printf("Optimize: Begin remove extra moves\n"); 338 _mesa_print_program(prog); 339 } 340 341 removeInst = (GLboolean *) 342 _mesa_calloc(prog->NumInstructions * sizeof(GLboolean)); 343 344 /* 345 * Look for sequences such as this: 346 * FOO tmpX, arg0, arg1; 347 * MOV tmpY, tmpX; 348 * and convert into: 349 * FOO tmpY, arg0, arg1; 350 */ 351 352 for (i = 0; i < prog->NumInstructions; i++) { 353 const struct prog_instruction *inst = prog->Instructions + i; 354 355 switch (inst->Opcode) { 356 case OPCODE_BGNLOOP: 357 loopNesting++; 358 break; 359 case OPCODE_ENDLOOP: 360 loopNesting--; 361 break; 362 case OPCODE_BGNSUB: 363 subroutineNesting++; 364 break; 365 case OPCODE_ENDSUB: 366 subroutineNesting--; 367 break; 368 case OPCODE_MOV: 369 if (i > 0 && 370 loopNesting == 0 && 371 subroutineNesting == 0 && 372 inst->SrcReg[0].File == PROGRAM_TEMPORARY && 373 inst->SrcReg[0].Swizzle == SWIZZLE_XYZW) { 374 /* see if this MOV can be removed */ 375 const GLuint tempIndex = inst->SrcReg[0].Index; 376 struct prog_instruction *prevInst; 377 GLuint prevI; 378 379 /* get pointer to previous instruction */ 380 prevI = i - 1; 381 while (removeInst[prevI] && prevI > 0) 382 prevI--; 383 prevInst = prog->Instructions + prevI; 384 385 if (prevInst->DstReg.File == PROGRAM_TEMPORARY && 386 prevInst->DstReg.Index == tempIndex && 387 prevInst->DstReg.WriteMask == WRITEMASK_XYZW) { 388 389 enum temp_use next_use = 390 find_next_temp_use(prog, i + 1, tempIndex); 391 392 if (next_use == WRITE || next_use == END) { 393 /* OK, we can safely remove this MOV instruction. 394 * Transform: 395 * prevI: FOO tempIndex, x, y; 396 * i: MOV z, tempIndex; 397 * Into: 398 * prevI: FOO z, x, y; 399 */ 400 401 /* patch up prev inst */ 402 prevInst->DstReg.File = inst->DstReg.File; 403 prevInst->DstReg.Index = inst->DstReg.Index; 404 405 /* flag this instruction for removal */ 406 removeInst[i] = GL_TRUE; 407 408 if (dbg) { 409 _mesa_printf("Remove MOV at %u\n", i); 410 _mesa_printf("new prev inst %u: ", prevI); 411 _mesa_print_instruction(prevInst); 412 } 413 } 414 } 415 } 416 break; 417 default: 418 ; /* nothing */ 419 } 420 } 421 422 /* now remove the instructions which aren't needed */ 423 rem = remove_instructions(prog, removeInst); 424 425 if (dbg) { 426 _mesa_printf("Optimize: End remove extra moves. %u instructions removed\n", rem); 427 /*_mesa_print_program(prog);*/ 428 } 429} 430 431 432/** A live register interval */ 433struct interval 434{ 435 GLuint Reg; /** The temporary register index */ 436 GLuint Start, End; /** Start/end instruction numbers */ 437}; 438 439 440/** A list of register intervals */ 441struct interval_list 442{ 443 GLuint Num; 444 struct interval Intervals[MAX_PROGRAM_TEMPS]; 445}; 446 447 448static void 449append_interval(struct interval_list *list, const struct interval *inv) 450{ 451 list->Intervals[list->Num++] = *inv; 452} 453 454 455/** Insert interval inv into list, sorted by interval end */ 456static void 457insert_interval_by_end(struct interval_list *list, const struct interval *inv) 458{ 459 /* XXX we could do a binary search insertion here since list is sorted */ 460 GLint i = list->Num - 1; 461 while (i >= 0 && list->Intervals[i].End > inv->End) { 462 list->Intervals[i + 1] = list->Intervals[i]; 463 i--; 464 } 465 list->Intervals[i + 1] = *inv; 466 list->Num++; 467 468#ifdef DEBUG 469 { 470 GLuint i; 471 for (i = 0; i + 1 < list->Num; i++) { 472 ASSERT(list->Intervals[i].End <= list->Intervals[i + 1].End); 473 } 474 } 475#endif 476} 477 478 479/** Remove the given interval from the interval list */ 480static void 481remove_interval(struct interval_list *list, const struct interval *inv) 482{ 483 /* XXX we could binary search since list is sorted */ 484 GLuint k; 485 for (k = 0; k < list->Num; k++) { 486 if (list->Intervals[k].Reg == inv->Reg) { 487 /* found, remove it */ 488 ASSERT(list->Intervals[k].Start == inv->Start); 489 ASSERT(list->Intervals[k].End == inv->End); 490 while (k < list->Num - 1) { 491 list->Intervals[k] = list->Intervals[k + 1]; 492 k++; 493 } 494 list->Num--; 495 return; 496 } 497 } 498} 499 500 501/** called by qsort() */ 502static int 503compare_start(const void *a, const void *b) 504{ 505 const struct interval *ia = (const struct interval *) a; 506 const struct interval *ib = (const struct interval *) b; 507 if (ia->Start < ib->Start) 508 return -1; 509 else if (ia->Start > ib->Start) 510 return +1; 511 else 512 return 0; 513} 514 515/** sort the interval list according to interval starts */ 516static void 517sort_interval_list_by_start(struct interval_list *list) 518{ 519 qsort(list->Intervals, list->Num, sizeof(struct interval), compare_start); 520#ifdef DEBUG 521 { 522 GLuint i; 523 for (i = 0; i + 1 < list->Num; i++) { 524 ASSERT(list->Intervals[i].Start <= list->Intervals[i + 1].Start); 525 } 526 } 527#endif 528} 529 530 531/** 532 * Update the intermediate interval info for register 'index' and 533 * instruction 'ic'. 534 */ 535static void 536update_interval(GLint intBegin[], GLint intEnd[], GLuint index, GLuint ic) 537{ 538 ASSERT(index < MAX_PROGRAM_TEMPS); 539 if (intBegin[index] == -1) { 540 ASSERT(intEnd[index] == -1); 541 intBegin[index] = intEnd[index] = ic; 542 } 543 else { 544 intEnd[index] = ic; 545 } 546} 547 548 549/** 550 * Find the live intervals for each temporary register in the program. 551 * For register R, the interval [A,B] indicates that R is referenced 552 * from instruction A through instruction B. 553 * Special consideration is needed for loops and subroutines. 554 * \return GL_TRUE if success, GL_FALSE if we cannot proceed for some reason 555 */ 556static GLboolean 557find_live_intervals(struct gl_program *prog, 558 struct interval_list *liveIntervals) 559{ 560 struct loop_info 561 { 562 GLuint Start, End; /**< Start, end instructions of loop */ 563 }; 564 struct loop_info loopStack[MAX_LOOP_NESTING]; 565 GLuint loopStackDepth = 0; 566 GLint intBegin[MAX_PROGRAM_TEMPS], intEnd[MAX_PROGRAM_TEMPS]; 567 GLuint i; 568 569 /* 570 * Note: we'll return GL_FALSE below if we find relative indexing 571 * into the TEMP register file. We can't handle that yet. 572 * We also give up on subroutines for now. 573 */ 574 575 if (dbg) { 576 _mesa_printf("Optimize: Begin find intervals\n"); 577 } 578 579 for (i = 0; i < MAX_PROGRAM_TEMPS; i++){ 580 intBegin[i] = intEnd[i] = -1; 581 } 582 583 /* Scan instructions looking for temporary registers */ 584 for (i = 0; i < prog->NumInstructions; i++) { 585 const struct prog_instruction *inst = prog->Instructions + i; 586 if (inst->Opcode == OPCODE_BGNLOOP) { 587 loopStack[loopStackDepth].Start = i; 588 loopStack[loopStackDepth].End = inst->BranchTarget; 589 loopStackDepth++; 590 } 591 else if (inst->Opcode == OPCODE_ENDLOOP) { 592 loopStackDepth--; 593 } 594 else if (inst->Opcode == OPCODE_CAL) { 595 return GL_FALSE; 596 } 597 else { 598 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); 599 GLuint j; 600 for (j = 0; j < numSrc; j++) { 601 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) { 602 const GLuint index = inst->SrcReg[j].Index; 603 if (inst->SrcReg[j].RelAddr) 604 return GL_FALSE; 605 update_interval(intBegin, intEnd, index, i); 606 if (loopStackDepth > 0) { 607 /* extend temp register's interval to end of loop */ 608 GLuint loopEnd = loopStack[loopStackDepth - 1].End; 609 update_interval(intBegin, intEnd, index, loopEnd); 610 } 611 } 612 } 613 if (inst->DstReg.File == PROGRAM_TEMPORARY) { 614 const GLuint index = inst->DstReg.Index; 615 if (inst->DstReg.RelAddr) 616 return GL_FALSE; 617 update_interval(intBegin, intEnd, index, i); 618 if (loopStackDepth > 0) { 619 /* extend temp register's interval to end of loop */ 620 GLuint loopEnd = loopStack[loopStackDepth - 1].End; 621 update_interval(intBegin, intEnd, index, loopEnd); 622 } 623 } 624 } 625 } 626 627 /* Build live intervals list from intermediate arrays */ 628 liveIntervals->Num = 0; 629 for (i = 0; i < MAX_PROGRAM_TEMPS; i++) { 630 if (intBegin[i] >= 0) { 631 struct interval inv; 632 inv.Reg = i; 633 inv.Start = intBegin[i]; 634 inv.End = intEnd[i]; 635 append_interval(liveIntervals, &inv); 636 } 637 } 638 639 /* Sort the list according to interval starts */ 640 sort_interval_list_by_start(liveIntervals); 641 642 if (dbg) { 643 /* print interval info */ 644 for (i = 0; i < liveIntervals->Num; i++) { 645 const struct interval *inv = liveIntervals->Intervals + i; 646 _mesa_printf("Reg[%d] live [%d, %d]:", 647 inv->Reg, inv->Start, inv->End); 648 if (1) { 649 int j; 650 for (j = 0; j < inv->Start; j++) 651 _mesa_printf(" "); 652 for (j = inv->Start; j <= inv->End; j++) 653 _mesa_printf("x"); 654 } 655 _mesa_printf("\n"); 656 } 657 } 658 659 return GL_TRUE; 660} 661 662 663static GLuint 664alloc_register(GLboolean usedRegs[MAX_PROGRAM_TEMPS]) 665{ 666 GLuint k; 667 for (k = 0; k < MAX_PROGRAM_TEMPS; k++) { 668 if (!usedRegs[k]) { 669 usedRegs[k] = GL_TRUE; 670 return k; 671 } 672 } 673 return MAX_PROGRAM_TEMPS; 674} 675 676 677/** 678 * This function implements "Linear Scan Register Allocation" to reduce 679 * the number of temporary registers used by the program. 680 * 681 * We compute the "live interval" for all temporary registers then 682 * examine the overlap of the intervals to allocate new registers. 683 * Basically, if two intervals do not overlap, they can use the same register. 684 */ 685static void 686_mesa_reallocate_registers(struct gl_program *prog) 687{ 688 struct interval_list liveIntervals; 689 GLint registerMap[MAX_PROGRAM_TEMPS]; 690 GLboolean usedRegs[MAX_PROGRAM_TEMPS]; 691 GLuint i; 692 GLuint maxTemp = 0; 693 694 if (dbg) { 695 _mesa_printf("Optimize: Begin live-interval register reallocation\n"); 696 _mesa_print_program(prog); 697 } 698 699 for (i = 0; i < MAX_PROGRAM_TEMPS; i++){ 700 registerMap[i] = -1; 701 usedRegs[i] = GL_FALSE; 702 } 703 704 if (!find_live_intervals(prog, &liveIntervals)) { 705 if (dbg) 706 _mesa_printf("Aborting register reallocation\n"); 707 return; 708 } 709 710 { 711 struct interval_list activeIntervals; 712 activeIntervals.Num = 0; 713 714 /* loop over live intervals, allocating a new register for each */ 715 for (i = 0; i < liveIntervals.Num; i++) { 716 const struct interval *live = liveIntervals.Intervals + i; 717 718 if (dbg) 719 _mesa_printf("Consider register %u\n", live->Reg); 720 721 /* Expire old intervals. Intervals which have ended with respect 722 * to the live interval can have their remapped registers freed. 723 */ 724 { 725 GLint j; 726 for (j = 0; j < activeIntervals.Num; j++) { 727 const struct interval *inv = activeIntervals.Intervals + j; 728 if (inv->End >= live->Start) { 729 /* Stop now. Since the activeInterval list is sorted 730 * we know we don't have to go further. 731 */ 732 break; 733 } 734 else { 735 /* Interval 'inv' has expired */ 736 const GLint regNew = registerMap[inv->Reg]; 737 ASSERT(regNew >= 0); 738 739 if (dbg) 740 _mesa_printf(" expire interval for reg %u\n", inv->Reg); 741 742 /* remove interval j from active list */ 743 remove_interval(&activeIntervals, inv); 744 j--; /* counter-act j++ in for-loop above */ 745 746 /* return register regNew to the free pool */ 747 if (dbg) 748 _mesa_printf(" free reg %d\n", regNew); 749 ASSERT(usedRegs[regNew] == GL_TRUE); 750 usedRegs[regNew] = GL_FALSE; 751 } 752 } 753 } 754 755 /* find a free register for this live interval */ 756 { 757 const GLuint k = alloc_register(usedRegs); 758 if (k == MAX_PROGRAM_TEMPS) { 759 /* out of registers, give up */ 760 return; 761 } 762 registerMap[live->Reg] = k; 763 maxTemp = MAX2(maxTemp, k); 764 if (dbg) 765 _mesa_printf(" remap register %d -> %d\n", live->Reg, k); 766 } 767 768 /* Insert this live interval into the active list which is sorted 769 * by increasing end points. 770 */ 771 insert_interval_by_end(&activeIntervals, live); 772 } 773 } 774 775 if (maxTemp + 1 < liveIntervals.Num) { 776 /* OK, we've reduced the number of registers needed. 777 * Scan the program and replace all the old temporary register 778 * indexes with the new indexes. 779 */ 780 replace_regs(prog, PROGRAM_TEMPORARY, registerMap); 781 782 prog->NumTemporaries = maxTemp + 1; 783 } 784 785 if (dbg) { 786 _mesa_printf("Optimize: End live-interval register reallocation\n"); 787 _mesa_printf("Num temp regs before: %u after: %u\n", 788 liveIntervals.Num, maxTemp + 1); 789 _mesa_print_program(prog); 790 } 791} 792 793 794 795 796/** 797 * Apply optimizations to the given program to eliminate unnecessary 798 * instructions, temp regs, etc. 799 */ 800void 801_mesa_optimize_program(GLcontext *ctx, struct gl_program *program) 802{ 803 if (1) 804 _mesa_remove_dead_code(program); 805 806 if (0) /* not test much yet */ 807 _mesa_remove_extra_moves(program); 808 809 if (1) 810 _mesa_consolidate_registers(program); 811 else /*NEW*/ 812 _mesa_reallocate_registers(program); 813} 814