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