src/mesa/shader/prog_optimize.c

   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
  39 static GLboolean dbg = GL_FALSE;
  40
  41 /* Returns the mask of channels read from the given srcreg in this instruction.
  42  */
  43 static GLuint
  44 get_src_arg_mask(const struct prog_instruction *inst, int arg)
  45 {
  46    int writemask = inst->DstReg.WriteMask;
  47
  48    if (inst->CondUpdate)
  49       writemask = WRITEMASK_XYZW;
  50
  51    switch (inst->Opcode) {
  52    case OPCODE_MOV:
  53    case OPCODE_ABS:
  54    case OPCODE_ADD:
  55    case OPCODE_MUL:
  56    case OPCODE_SUB:
  57       return writemask;
  58    case OPCODE_RCP:
  59    case OPCODE_SIN:
  60    case OPCODE_COS:
  61    case OPCODE_RSQ:
  62    case OPCODE_POW:
  63    case OPCODE_EX2:
  64       return WRITEMASK_X;
  65    case OPCODE_DP2:
  66       return WRITEMASK_XY;
  67    case OPCODE_DP3:
  68       return WRITEMASK_XYZ;
  69    default:
  70       return WRITEMASK_XYZW;
  71    }
  72 }
  73
  74 /**
  75  * In 'prog' remove instruction[i] if removeFlags[i] == TRUE.
  76  * \return number of instructions removed
  77  */
  78 static GLuint
  79 remove_instructions(struct gl_program *prog, const GLboolean *removeFlags)
  80 {
  81    GLint i, removeEnd = 0, removeCount = 0;
  82    GLuint totalRemoved = 0;
  83
  84    /* go backward */
  85    for (i = prog->NumInstructions - 1; i >= 0; i--) {
  86       if (removeFlags[i]) {
  87          totalRemoved++;
  88          if (removeCount == 0) {
  89             /* begin a run of instructions to remove */
  90             removeEnd = i;
  91             removeCount = 1;
  92          }
  93          else {
  94             /* extend the run of instructions to remove */
  95             removeCount++;
  96          }
  97       }
  98       else {
  99          /* don't remove this instruction, but check if the preceeding
 100           * instructions are to be removed.
 101           */
 102          if (removeCount > 0) {
 103             GLint removeStart = removeEnd - removeCount + 1;
 104             _mesa_delete_instructions(prog, removeStart, removeCount);
 105             removeStart = removeCount = 0; /* reset removal info */
 106          }
 107       }
 108    }
 109    /* Finish removing if the first instruction was to be removed. */
 110    if (removeCount > 0) {
 111       GLint removeStart = removeEnd - removeCount + 1;
 112       _mesa_delete_instructions(prog, removeStart, removeCount);
 113       removeStart = removeCount = 0; /* reset removal info */
 114    }
 115    return totalRemoved;
 116 }
 117
 118
 119 /**
 120  * Remap register indexes according to map.
 121  * \param prog  the program to search/replace
 122  * \param file  the type of register file to search/replace
 123  * \param map  maps old register indexes to new indexes
 124  */
 125 static void
 126 replace_regs(struct gl_program *prog, gl_register_file file, const GLint map[])
 127 {
 128    GLuint i;
 129
 130    for (i = 0; i < prog->NumInstructions; i++) {
 131       struct prog_instruction *inst = prog->Instructions + i;
 132       const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
 133       GLuint j;
 134       for (j = 0; j < numSrc; j++) {
 135          if (inst->SrcReg[j].File == file) {
 136             GLuint index = inst->SrcReg[j].Index;
 137             ASSERT(map[index] >= 0);
 138             inst->SrcReg[j].Index = map[index];
 139          }
 140       }
 141       if (inst->DstReg.File == file) {
 142          const GLuint index = inst->DstReg.Index;
 143          ASSERT(map[index] >= 0);
 144          inst->DstReg.Index = map[index];
 145       }
 146    }
 147 }
 148
 149
 150 /**
 151  * Consolidate temporary registers to use low numbers.  For example, if the
 152  * shader only uses temps 4, 5, 8, replace them with 0, 1, 2.
 153  */
 154 static void
 155 _mesa_consolidate_registers(struct gl_program *prog)
 156 {
 157    GLboolean tempUsed[MAX_PROGRAM_TEMPS];
 158    GLint tempMap[MAX_PROGRAM_TEMPS];
 159    GLuint tempMax = 0, i;
 160
 161    if (dbg) {
 162       _mesa_printf("Optimize: Begin register consolidation\n");
 163    }
 164
 165    memset(tempUsed, 0, sizeof(tempUsed));
 166
 167    for (i = 0; i < MAX_PROGRAM_TEMPS; i++) {
 168       tempMap[i] = -1;
 169    }
 170
 171    /* set tempUsed[i] if temporary [i] is referenced */
 172    for (i = 0; i < prog->NumInstructions; i++) {
 173       const struct prog_instruction *inst = prog->Instructions + i;
 174       const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
 175       GLuint j;
 176       for (j = 0; j < numSrc; j++) {
 177          if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) {
 178             const GLuint index = inst->SrcReg[j].Index;
 179             ASSERT(index < MAX_PROGRAM_TEMPS);
 180             tempUsed[index] = GL_TRUE;
 181             tempMax = MAX2(tempMax, index);
 182             break;
 183          }
 184       }
 185       if (inst->DstReg.File == PROGRAM_TEMPORARY) {
 186          const GLuint index = inst->DstReg.Index;
 187          ASSERT(index < MAX_PROGRAM_TEMPS);
 188          tempUsed[index] = GL_TRUE;
 189          tempMax = MAX2(tempMax, index);
 190       }
 191    }
 192
 193    /* allocate a new index for each temp that's used */
 194    {
 195       GLuint freeTemp = 0;
 196       for (i = 0; i <= tempMax; i++) {
 197          if (tempUsed[i]) {
 198             tempMap[i] = freeTemp++;
 199             /*_mesa_printf("replace %u with %u\n", i, tempMap[i]);*/
 200          }
 201       }
 202       if (freeTemp == tempMax + 1) {
 203          /* no consolidation possible */
 204          return;
 205       }
 206       if (dbg) {
 207          _mesa_printf("Replace regs 0..%u with 0..%u\n", tempMax, freeTemp-1);
 208       }
 209    }
 210
 211    replace_regs(prog, PROGRAM_TEMPORARY, tempMap);
 212
 213    if (dbg) {
 214       _mesa_printf("Optimize: End register consolidation\n");
 215    }
 216 }
 217
 218
 219 /**
 220  * Remove dead instructions from the given program.
 221  * This is very primitive for now.  Basically look for temp registers
 222  * that are written to but never read.  Remove any instructions that
 223  * write to such registers.  Be careful with condition code setters.
 224  */
 225 static void
 226 _mesa_remove_dead_code(struct gl_program *prog)
 227 {
 228    GLboolean tempRead[MAX_PROGRAM_TEMPS][4];
 229    GLboolean *removeInst; /* per-instruction removal flag */
 230    GLuint i, rem = 0, comp;
 231
 232    memset(tempRead, 0, sizeof(tempRead));
 233
 234    if (dbg) {
 235       _mesa_printf("Optimize: Begin dead code removal\n");
 236       /*_mesa_print_program(prog);*/
 237    }
 238
 239    removeInst = (GLboolean *)
 240       _mesa_calloc(prog->NumInstructions * sizeof(GLboolean));
 241
 242    /* Determine which temps are read and written */
 243    for (i = 0; i < prog->NumInstructions; i++) {
 244       const struct prog_instruction *inst = prog->Instructions + i;
 245       const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
 246       GLuint j;
 247
 248       /* check src regs */
 249       for (j = 0; j < numSrc; j++) {
 250          if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) {
 251             const GLuint index = inst->SrcReg[j].Index;
 252             ASSERT(index < MAX_PROGRAM_TEMPS);
 253             int read_mask = get_src_arg_mask(inst, j);
 254
 255             if (inst->SrcReg[j].RelAddr) {
 256                if (dbg)
 257                   _mesa_printf("abort remove dead code (indirect temp)\n");
 258                goto done;
 259             }
 260
 261             for (comp = 0; comp < 4; comp++) {
 262                GLuint swz = (inst->SrcReg[j].Swizzle >> (3 * comp)) & 0x7;
 263
 264                if ((read_mask & (1 << comp)) == 0)
 265                   continue;
 266
 267                switch (swz) {
 268                case SWIZZLE_X:
 269                   tempRead[index][0] = GL_TRUE;
 270                   break;
 271                case SWIZZLE_Y:
 272                   tempRead[index][1] = GL_TRUE;
 273                   break;
 274                case SWIZZLE_Z:
 275                   tempRead[index][2] = GL_TRUE;
 276                   break;
 277                case SWIZZLE_W:
 278                   tempRead[index][3] = GL_TRUE;
 279                   break;
 280                }
 281             }
 282          }
 283       }
 284
 285       /* check dst reg */
 286       if (inst->DstReg.File == PROGRAM_TEMPORARY) {
 287          const GLuint index = inst->DstReg.Index;
 288          ASSERT(index < MAX_PROGRAM_TEMPS);
 289
 290          if (inst->DstReg.RelAddr) {
 291             if (dbg)
 292                _mesa_printf("abort remove dead code (indirect temp)\n");
 293             goto done;
 294          }
 295
 296          if (inst->CondUpdate) {
 297             /* If we're writing to this register and setting condition
 298              * codes we cannot remove the instruction.  Prevent removal
 299              * by setting the 'read' flag.
 300              */
 301             tempRead[index][0] = GL_TRUE;
 302             tempRead[index][1] = GL_TRUE;
 303             tempRead[index][2] = GL_TRUE;
 304             tempRead[index][3] = GL_TRUE;
 305          }
 306       }
 307    }
 308
 309    /* find instructions that write to dead registers, flag for removal */
 310    for (i = 0; i < prog->NumInstructions; i++) {
 311       struct prog_instruction *inst = prog->Instructions + i;
 312       const GLuint numDst = _mesa_num_inst_dst_regs(inst->Opcode);
 313
 314       if (numDst != 0 && inst->DstReg.File == PROGRAM_TEMPORARY) {
 315          GLint chan, index = inst->DstReg.Index;
 316
 317          for (chan = 0; chan < 4; chan++) {
 318             if (!tempRead[index][chan] &&
 319                 inst->DstReg.WriteMask & (1 << chan)) {
 320                if (dbg) {
 321                   _mesa_printf("Remove writemask on %u.%c\n", i,
 322                                chan == 3 ? 'w' : 'x' + chan);
 323                }
 324                inst->DstReg.WriteMask &= ~(1 << chan);
 325                rem++;
 326             }
 327          }
 328
 329          if (inst->DstReg.WriteMask == 0) {
 330             /* If we cleared all writes, the instruction can be removed. */
 331             if (dbg)
 332                _mesa_printf("Remove instruction %u: \n", i);
 333             removeInst[i] = GL_TRUE;
 334          }
 335       }
 336    }
 337
 338    /* now remove the instructions which aren't needed */
 339    rem = remove_instructions(prog, removeInst);
 340
 341    if (dbg) {
 342       _mesa_printf("Optimize: End dead code removal.\n");
 343       _mesa_printf("  %u channel writes removed\n", rem);
 344       _mesa_printf("  %u instructions removed\n", rem);
 345       /*_mesa_print_program(prog);*/
 346    }
 347
 348 done:
 349    _mesa_free(removeInst);
 350 }
 351
 352
 353 enum temp_use
 354 {
 355    READ,
 356    WRITE,
 357    FLOW,
 358    END
 359 };
 360
 361 /**
 362  * Scan forward in program from 'start' for the next occurance of TEMP[index].
 363  * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator
 364  * that we can't look further.
 365  */
 366 static enum temp_use
 367 find_next_temp_use(const struct gl_program *prog, GLuint start, GLuint index)
 368 {
 369    GLuint i;
 370
 371    for (i = start; i < prog->NumInstructions; i++) {
 372       const struct prog_instruction *inst = prog->Instructions + i;
 373       switch (inst->Opcode) {
 374       case OPCODE_BGNLOOP:
 375       case OPCODE_ENDLOOP:
 376       case OPCODE_BGNSUB:
 377       case OPCODE_ENDSUB:
 378          return FLOW;
 379       default:
 380          {
 381             const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
 382             GLuint j;
 383             for (j = 0; j < numSrc; j++) {
 384                if (inst->SrcReg[j].File == PROGRAM_TEMPORARY &&
 385                    inst->SrcReg[j].Index == index)
 386                   return READ;
 387             }
 388             if (inst->DstReg.File == PROGRAM_TEMPORARY &&
 389                 inst->DstReg.Index == index)
 390                return WRITE;
 391          }
 392       }
 393    }
 394
 395    return END;
 396 }
 397
 398
 399 /**
 400  * Try to remove use of extraneous MOV instructions, to free them up for dead
 401  * code removal.
 402  */
 403 static void
 404 _mesa_remove_extra_move_use(struct gl_program *prog)
 405 {
 406    GLuint i;
 407
 408    if (dbg) {
 409       _mesa_printf("Optimize: Begin remove extra move use\n");
 410       _mesa_print_program(prog);
 411    }
 412
 413    /*
 414     * Look for sequences such as this:
 415     *    MOV tmpX, arg0;
 416     *    FOO tmpY, tmpX, arg1;
 417     * and convert into:
 418     *    MOV tmpX, arg0;
 419     *    FOO tmpY, arg0, arg1;
 420     */
 421
 422    for (i = 0; i < prog->NumInstructions - 1; i++) {
 423       const struct prog_instruction *mov = prog->Instructions + i;
 424       struct prog_instruction *inst2 = prog->Instructions + i + 1;
 425       int arg;
 426
 427       if (mov->Opcode != OPCODE_MOV ||
 428           mov->DstReg.File != PROGRAM_TEMPORARY ||
 429           mov->DstReg.RelAddr ||
 430           mov->DstReg.CondMask != COND_TR ||
 431           mov->SaturateMode != SATURATE_OFF)
 432          continue;
 433
 434       for (arg = 0; arg < _mesa_num_inst_src_regs(inst2->Opcode); arg++) {
 435          int comp;
 436          int read_mask = get_src_arg_mask(inst2, arg);
 437
 438          if (inst2->SrcReg[arg].File != mov->DstReg.File ||
 439              inst2->SrcReg[arg].Index != mov->DstReg.Index ||
 440              inst2->SrcReg[arg].RelAddr ||
 441              inst2->SrcReg[arg].Abs)
 442             continue;
 443
 444          /* Check that all the sources for this arg of inst2 come from inst1
 445           * or constants.
 446           */
 447          for (comp = 0; comp < 4; comp++) {
 448             int src_swz = GET_SWZ(inst2->SrcReg[arg].Swizzle, comp);
 449
 450             /* If the MOV didn't write that channel, can't use it. */
 451             if ((read_mask & (1 << comp)) &&
 452                 src_swz <= SWIZZLE_W &&
 453                 (mov->DstReg.WriteMask & (1 << src_swz)) == 0)
 454                break;
 455          }
 456          if (comp != 4)
 457             continue;
 458
 459          /* Adjust the swizzles of inst2 to point at MOV's source */
 460          for (comp = 0; comp < 4; comp++) {
 461             int inst2_swz = GET_SWZ(inst2->SrcReg[arg].Swizzle, comp);
 462
 463             if (inst2_swz <= SWIZZLE_W) {
 464                GLuint s = GET_SWZ(mov->SrcReg[0].Swizzle, inst2_swz);
 465                inst2->SrcReg[arg].Swizzle &= ~(7 << (3 * comp));
 466                inst2->SrcReg[arg].Swizzle |= s << (3 * comp);
 467                inst2->SrcReg[arg].Negate ^= (((mov->SrcReg[0].Negate >>
 468                                                inst2_swz) & 0x1) << comp);
 469             }
 470          }
 471          inst2->SrcReg[arg].File = mov->SrcReg[0].File;
 472          inst2->SrcReg[arg].Index = mov->SrcReg[0].Index;
 473       }
 474    }
 475
 476    if (dbg) {
 477       _mesa_printf("Optimize: End remove extra move use.\n");
 478       /*_mesa_print_program(prog);*/
 479    }
 480 }
 481
 482 /**
 483  * Try to remove extraneous MOV instructions from the given program.
 484  */
 485 static void
 486 _mesa_remove_extra_moves(struct gl_program *prog)
 487 {
 488    GLboolean *removeInst; /* per-instruction removal flag */
 489    GLuint i, rem, loopNesting = 0, subroutineNesting = 0;
 490
 491    if (dbg) {
 492       _mesa_printf("Optimize: Begin remove extra moves\n");
 493       _mesa_print_program(prog);
 494    }
 495
 496    removeInst = (GLboolean *)
 497       _mesa_calloc(prog->NumInstructions * sizeof(GLboolean));
 498
 499    /*
 500     * Look for sequences such as this:
 501     *    FOO tmpX, arg0, arg1;
 502     *    MOV tmpY, tmpX;
 503     * and convert into:
 504     *    FOO tmpY, arg0, arg1;
 505     */
 506
 507    for (i = 0; i < prog->NumInstructions; i++) {
 508       const struct prog_instruction *inst = prog->Instructions + i;
 509
 510       switch (inst->Opcode) {
 511       case OPCODE_BGNLOOP:
 512          loopNesting++;
 513          break;
 514       case OPCODE_ENDLOOP:
 515          loopNesting--;
 516          break;
 517       case OPCODE_BGNSUB:
 518          subroutineNesting++;
 519          break;
 520       case OPCODE_ENDSUB:
 521          subroutineNesting--;
 522          break;
 523       case OPCODE_MOV:
 524          if (i > 0 &&
 525              loopNesting == 0 &&
 526              subroutineNesting == 0 &&
 527              inst->SrcReg[0].File == PROGRAM_TEMPORARY &&
 528              inst->SrcReg[0].Swizzle == SWIZZLE_XYZW) {
 529             /* see if this MOV can be removed */
 530             const GLuint tempIndex = inst->SrcReg[0].Index;
 531             struct prog_instruction *prevInst;
 532             GLuint prevI;
 533
 534             /* get pointer to previous instruction */
 535             prevI = i - 1;
 536             while (removeInst[prevI] && prevI > 0)
 537                prevI--;
 538             prevInst = prog->Instructions + prevI;
 539
 540             if (prevInst->DstReg.File == PROGRAM_TEMPORARY &&
 541                 prevInst->DstReg.Index == tempIndex &&
 542                 prevInst->DstReg.WriteMask == WRITEMASK_XYZW) {
 543
 544                enum temp_use next_use =
 545                   find_next_temp_use(prog, i + 1, tempIndex);
 546
 547                if (next_use == WRITE || next_use == END) {
 548                   /* OK, we can safely remove this MOV instruction.
 549                    * Transform:
 550                    *   prevI: FOO tempIndex, x, y;
 551                    *       i: MOV z, tempIndex;
 552                    * Into:
 553                    *   prevI: FOO z, x, y;
 554                    */
 555
 556                   /* patch up prev inst */
 557                   prevInst->DstReg.File = inst->DstReg.File;
 558                   prevInst->DstReg.Index = inst->DstReg.Index;
 559
 560                   /* flag this instruction for removal */
 561                   removeInst[i] = GL_TRUE;
 562
 563                   if (dbg) {
 564                      _mesa_printf("Remove MOV at %u\n", i);
 565                      _mesa_printf("new prev inst %u: ", prevI);
 566                      _mesa_print_instruction(prevInst);
 567                   }
 568                }
 569             }
 570          }
 571          break;
 572       default:
 573          ; /* nothing */
 574       }
 575    }
 576
 577    /* now remove the instructions which aren't needed */
 578    rem = remove_instructions(prog, removeInst);
 579
 580    _mesa_free(removeInst);
 581
 582    if (dbg) {
 583       _mesa_printf("Optimize: End remove extra moves.  %u instructions removed\n", rem);
 584       /*_mesa_print_program(prog);*/
 585    }
 586 }
 587
 588
 589 /** A live register interval */
 590 struct interval
 591 {
 592    GLuint Reg;         /** The temporary register index */
 593    GLuint Start, End;  /** Start/end instruction numbers */
 594 };
 595
 596
 597 /** A list of register intervals */
 598 struct interval_list
 599 {
 600    GLuint Num;
 601    struct interval Intervals[MAX_PROGRAM_TEMPS];
 602 };
 603
 604
 605 static void
 606 append_interval(struct interval_list *list, const struct interval *inv)
 607 {
 608    list->Intervals[list->Num++] = *inv;
 609 }
 610
 611
 612 /** Insert interval inv into list, sorted by interval end */
 613 static void
 614 insert_interval_by_end(struct interval_list *list, const struct interval *inv)
 615 {
 616    /* XXX we could do a binary search insertion here since list is sorted */
 617    GLint i = list->Num - 1;
 618    while (i >= 0 && list->Intervals[i].End > inv->End) {
 619       list->Intervals[i + 1] = list->Intervals[i];
 620       i--;
 621    }
 622    list->Intervals[i + 1] = *inv;
 623    list->Num++;
 624
 625 #ifdef DEBUG
 626    {
 627       GLuint i;
 628       for (i = 0; i + 1 < list->Num; i++) {
 629          ASSERT(list->Intervals[i].End <= list->Intervals[i + 1].End);
 630       }
 631    }
 632 #endif
 633 }
 634
 635
 636 /** Remove the given interval from the interval list */
 637 static void
 638 remove_interval(struct interval_list *list, const struct interval *inv)
 639 {
 640    /* XXX we could binary search since list is sorted */
 641    GLuint k;
 642    for (k = 0; k < list->Num; k++) {
 643       if (list->Intervals[k].Reg == inv->Reg) {
 644          /* found, remove it */
 645          ASSERT(list->Intervals[k].Start == inv->Start);
 646          ASSERT(list->Intervals[k].End == inv->End);
 647          while (k < list->Num - 1) {
 648             list->Intervals[k] = list->Intervals[k + 1];
 649             k++;
 650          }
 651          list->Num--;
 652          return;
 653       }
 654    }
 655 }
 656
 657
 658 /** called by qsort() */
 659 static int
 660 compare_start(const void *a, const void *b)
 661 {
 662    const struct interval *ia = (const struct interval *) a;
 663    const struct interval *ib = (const struct interval *) b;
 664    if (ia->Start < ib->Start)
 665       return -1;
 666    else if (ia->Start > ib->Start)
 667       return +1;
 668    else
 669       return 0;
 670 }
 671
 672 /** sort the interval list according to interval starts */
 673 static void
 674 sort_interval_list_by_start(struct interval_list *list)
 675 {
 676    qsort(list->Intervals, list->Num, sizeof(struct interval), compare_start);
 677 #ifdef DEBUG
 678    {
 679       GLuint i;
 680       for (i = 0; i + 1 < list->Num; i++) {
 681          ASSERT(list->Intervals[i].Start <= list->Intervals[i + 1].Start);
 682       }
 683    }
 684 #endif
 685 }
 686
 687
 688 /**
 689  * Update the intermediate interval info for register 'index' and
 690  * instruction 'ic'.
 691  */
 692 static void
 693 update_interval(GLint intBegin[], GLint intEnd[], GLuint index, GLuint ic)
 694 {
 695    ASSERT(index < MAX_PROGRAM_TEMPS);
 696    if (intBegin[index] == -1) {
 697       ASSERT(intEnd[index] == -1);
 698       intBegin[index] = intEnd[index] = ic;
 699    }
 700    else {
 701       intEnd[index] = ic;
 702    }
 703 }
 704
 705
 706 /**
 707  * Find first/last instruction that references each temporary register.
 708  */
 709 GLboolean
 710 _mesa_find_temp_intervals(const struct prog_instruction *instructions,
 711                           GLuint numInstructions,
 712                           GLint intBegin[MAX_PROGRAM_TEMPS],
 713                           GLint intEnd[MAX_PROGRAM_TEMPS])
 714 {
 715    struct loop_info
 716    {
 717       GLuint Start, End;  /**< Start, end instructions of loop */
 718    };
 719    struct loop_info loopStack[MAX_LOOP_NESTING];
 720    GLuint loopStackDepth = 0;
 721    GLuint i;
 722
 723    for (i = 0; i < MAX_PROGRAM_TEMPS; i++){
 724       intBegin[i] = intEnd[i] = -1;
 725    }
 726
 727    /* Scan instructions looking for temporary registers */
 728    for (i = 0; i < numInstructions; i++) {
 729       const struct prog_instruction *inst = instructions + i;
 730       if (inst->Opcode == OPCODE_BGNLOOP) {
 731          loopStack[loopStackDepth].Start = i;
 732          loopStack[loopStackDepth].End = inst->BranchTarget;
 733          loopStackDepth++;
 734       }
 735       else if (inst->Opcode == OPCODE_ENDLOOP) {
 736          loopStackDepth--;
 737       }
 738       else if (inst->Opcode == OPCODE_CAL) {
 739          return GL_FALSE;
 740       }
 741       else {
 742          const GLuint numSrc = 3;/*_mesa_num_inst_src_regs(inst->Opcode);*/
 743          GLuint j;
 744          for (j = 0; j < numSrc; j++) {
 745             if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) {
 746                const GLuint index = inst->SrcReg[j].Index;
 747                if (inst->SrcReg[j].RelAddr)
 748                   return GL_FALSE;
 749                update_interval(intBegin, intEnd, index, i);
 750                if (loopStackDepth > 0) {
 751                   /* extend temp register's interval to end of loop */
 752                   GLuint loopEnd = loopStack[loopStackDepth - 1].End;
 753                   update_interval(intBegin, intEnd, index, loopEnd);
 754                }
 755             }
 756          }
 757          if (inst->DstReg.File == PROGRAM_TEMPORARY) {
 758             const GLuint index = inst->DstReg.Index;
 759             if (inst->DstReg.RelAddr)
 760                return GL_FALSE;
 761             update_interval(intBegin, intEnd, index, i);
 762             if (loopStackDepth > 0) {
 763                /* extend temp register's interval to end of loop */
 764                GLuint loopEnd = loopStack[loopStackDepth - 1].End;
 765                update_interval(intBegin, intEnd, index, loopEnd);
 766             }
 767          }
 768       }
 769    }
 770
 771    return GL_TRUE;
 772 }
 773
 774
 775 /**
 776  * Find the live intervals for each temporary register in the program.
 777  * For register R, the interval [A,B] indicates that R is referenced
 778  * from instruction A through instruction B.
 779  * Special consideration is needed for loops and subroutines.
 780  * \return GL_TRUE if success, GL_FALSE if we cannot proceed for some reason
 781  */
 782 static GLboolean
 783 find_live_intervals(struct gl_program *prog,
 784                     struct interval_list *liveIntervals)
 785 {
 786    GLint intBegin[MAX_PROGRAM_TEMPS], intEnd[MAX_PROGRAM_TEMPS];
 787    GLuint i;
 788
 789    /*
 790     * Note: we'll return GL_FALSE below if we find relative indexing
 791     * into the TEMP register file.  We can't handle that yet.
 792     * We also give up on subroutines for now.
 793     */
 794
 795    if (dbg) {
 796       _mesa_printf("Optimize: Begin find intervals\n");
 797    }
 798
 799    /* build intermediate arrays */
 800    if (!_mesa_find_temp_intervals(prog->Instructions, prog->NumInstructions,
 801                                   intBegin, intEnd))
 802       return GL_FALSE;
 803
 804    /* Build live intervals list from intermediate arrays */
 805    liveIntervals->Num = 0;
 806    for (i = 0; i < MAX_PROGRAM_TEMPS; i++) {
 807       if (intBegin[i] >= 0) {
 808          struct interval inv;
 809          inv.Reg = i;
 810          inv.Start = intBegin[i];
 811          inv.End = intEnd[i];
 812          append_interval(liveIntervals, &inv);
 813       }
 814    }
 815
 816    /* Sort the list according to interval starts */
 817    sort_interval_list_by_start(liveIntervals);
 818
 819    if (dbg) {
 820       /* print interval info */
 821       for (i = 0; i < liveIntervals->Num; i++) {
 822          const struct interval *inv = liveIntervals->Intervals + i;
 823          _mesa_printf("Reg[%d] live [%d, %d]:",
 824                       inv->Reg, inv->Start, inv->End);
 825          if (1) {
 826             int j;
 827             for (j = 0; j < inv->Start; j++)
 828                _mesa_printf(" ");
 829             for (j = inv->Start; j <= inv->End; j++)
 830                _mesa_printf("x");
 831          }
 832          _mesa_printf("\n");
 833       }
 834    }
 835
 836    return GL_TRUE;
 837 }
 838
 839
 840 /** Scan the array of used register flags to find free entry */
 841 static GLint
 842 alloc_register(GLboolean usedRegs[MAX_PROGRAM_TEMPS])
 843 {
 844    GLuint k;
 845    for (k = 0; k < MAX_PROGRAM_TEMPS; k++) {
 846       if (!usedRegs[k]) {
 847          usedRegs[k] = GL_TRUE;
 848          return k;
 849       }
 850    }
 851    return -1;
 852 }
 853
 854
 855 /**
 856  * This function implements "Linear Scan Register Allocation" to reduce
 857  * the number of temporary registers used by the program.
 858  *
 859  * We compute the "live interval" for all temporary registers then
 860  * examine the overlap of the intervals to allocate new registers.
 861  * Basically, if two intervals do not overlap, they can use the same register.
 862  */
 863 static void
 864 _mesa_reallocate_registers(struct gl_program *prog)
 865 {
 866    struct interval_list liveIntervals;
 867    GLint registerMap[MAX_PROGRAM_TEMPS];
 868    GLboolean usedRegs[MAX_PROGRAM_TEMPS];
 869    GLuint i;
 870    GLint maxTemp = -1;
 871
 872    if (dbg) {
 873       _mesa_printf("Optimize: Begin live-interval register reallocation\n");
 874       _mesa_print_program(prog);
 875    }
 876
 877    for (i = 0; i < MAX_PROGRAM_TEMPS; i++){
 878       registerMap[i] = -1;
 879       usedRegs[i] = GL_FALSE;
 880    }
 881
 882    if (!find_live_intervals(prog, &liveIntervals)) {
 883       if (dbg)
 884          _mesa_printf("Aborting register reallocation\n");
 885       return;
 886    }
 887
 888    {
 889       struct interval_list activeIntervals;
 890       activeIntervals.Num = 0;
 891
 892       /* loop over live intervals, allocating a new register for each */
 893       for (i = 0; i < liveIntervals.Num; i++) {
 894          const struct interval *live = liveIntervals.Intervals + i;
 895
 896          if (dbg)
 897             _mesa_printf("Consider register %u\n", live->Reg);
 898
 899          /* Expire old intervals.  Intervals which have ended with respect
 900           * to the live interval can have their remapped registers freed.
 901           */
 902          {
 903             GLint j;
 904             for (j = 0; j < activeIntervals.Num; j++) {
 905                const struct interval *inv = activeIntervals.Intervals + j;
 906                if (inv->End >= live->Start) {
 907                   /* Stop now.  Since the activeInterval list is sorted
 908                    * we know we don't have to go further.
 909                    */
 910                   break;
 911                }
 912                else {
 913                   /* Interval 'inv' has expired */
 914                   const GLint regNew = registerMap[inv->Reg];
 915                   ASSERT(regNew >= 0);
 916
 917                   if (dbg)
 918                      _mesa_printf("  expire interval for reg %u\n", inv->Reg);
 919
 920                   /* remove interval j from active list */
 921                   remove_interval(&activeIntervals, inv);
 922                   j--;  /* counter-act j++ in for-loop above */
 923
 924                   /* return register regNew to the free pool */
 925                   if (dbg)
 926                      _mesa_printf("  free reg %d\n", regNew);
 927                   ASSERT(usedRegs[regNew] == GL_TRUE);
 928                   usedRegs[regNew] = GL_FALSE;
 929                }
 930             }
 931          }
 932
 933          /* find a free register for this live interval */
 934          {
 935             const GLint k = alloc_register(usedRegs);
 936             if (k < 0) {
 937                /* out of registers, give up */
 938                return;
 939             }
 940             registerMap[live->Reg] = k;
 941             maxTemp = MAX2(maxTemp, k);
 942             if (dbg)
 943                _mesa_printf("  remap register %u -> %d\n", live->Reg, k);
 944          }
 945
 946          /* Insert this live interval into the active list which is sorted
 947           * by increasing end points.
 948           */
 949          insert_interval_by_end(&activeIntervals, live);
 950       }
 951    }
 952
 953    if (maxTemp + 1 < liveIntervals.Num) {
 954       /* OK, we've reduced the number of registers needed.
 955        * Scan the program and replace all the old temporary register
 956        * indexes with the new indexes.
 957        */
 958       replace_regs(prog, PROGRAM_TEMPORARY, registerMap);
 959
 960       prog->NumTemporaries = maxTemp + 1;
 961    }
 962
 963    if (dbg) {
 964       _mesa_printf("Optimize: End live-interval register reallocation\n");
 965       _mesa_printf("Num temp regs before: %u  after: %u\n",
 966                    liveIntervals.Num, maxTemp + 1);
 967       _mesa_print_program(prog);
 968    }
 969 }
 970
 971
 972 /**
 973  * Apply optimizations to the given program to eliminate unnecessary
 974  * instructions, temp regs, etc.
 975  */
 976 void
 977 _mesa_optimize_program(GLcontext *ctx, struct gl_program *program)
 978 {
 979    _mesa_remove_extra_move_use(program);
 980
 981    if (1)
 982       _mesa_remove_dead_code(program);
 983
 984    if (0) /* not tested much yet */
 985       _mesa_remove_extra_moves(program);
 986
 987    if (0)
 988       _mesa_consolidate_registers(program);
 989    else
 990       _mesa_reallocate_registers(program);
 991 }