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