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 static GLboolean dbg = GL_FALSE;
  37
  38
  39 /**
  40  * In 'prog' remove instruction[i] if removeFlags[i] == TRUE.
  41  * \return number of instructions removed
  42  */
  43 static GLuint
  44 remove_instructions(struct gl_program *prog, const GLboolean *removeFlags)
  45 {
  46    GLint i, removeEnd = 0, removeCount = 0;
  47    GLuint totalRemoved = 0;
  48
  49    /* go backward */
  50    for (i = prog->NumInstructions - 1; i >= 0; i--) {
  51       if (removeFlags[i]) {
  52          totalRemoved++;
  53          if (removeCount == 0) {
  54             /* begin a run of instructions to remove */
  55             removeEnd = i;
  56             removeCount = 1;
  57          }
  58          else {
  59             /* extend the run of instructions to remove */
  60             removeCount++;
  61          }
  62       }
  63       else {
  64          /* don't remove this instruction, but check if the preceeding
  65           * instructions are to be removed.
  66           */
  67          if (removeCount > 0) {
  68             GLint removeStart = removeEnd - removeCount + 1;
  69             _mesa_delete_instructions(prog, removeStart, removeCount);
  70             removeStart = removeCount = 0; /* reset removal info */
  71          }
  72       }
  73    }
  74    return totalRemoved;
  75 }
  76
  77
  78 /**
  79  * Consolidate temporary registers to use low numbers.  For example, if the
  80  * shader only uses temps 4, 5, 8, replace them with 0, 1, 2.
  81  */
  82 static void
  83 _mesa_consolidate_registers(struct gl_program *prog)
  84 {
  85    GLboolean tempUsed[MAX_PROGRAM_TEMPS];
  86    GLuint tempMap[MAX_PROGRAM_TEMPS];
  87    GLuint tempMax = 0, i;
  88
  89    if (dbg) {
  90       _mesa_printf("Optimize: Begin register consolidation\n");
  91    }
  92
  93    memset(tempUsed, 0, sizeof(tempUsed));
  94
  95    /* set tempUsed[i] if temporary [i] is referenced */
  96    for (i = 0; i < prog->NumInstructions; i++) {
  97       const struct prog_instruction *inst = prog->Instructions + i;
  98       const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
  99       GLuint j;
 100       for (j = 0; j < numSrc; j++) {
 101          if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) {
 102             const GLuint index = inst->SrcReg[j].Index;
 103             ASSERT(index < MAX_PROGRAM_TEMPS);
 104             tempUsed[index] = GL_TRUE;
 105             tempMax = MAX2(tempMax, index);
 106             break;
 107          }
 108       }
 109       if (inst->DstReg.File == PROGRAM_TEMPORARY) {
 110          const GLuint index = inst->DstReg.Index;
 111          ASSERT(index < MAX_PROGRAM_TEMPS);
 112          tempUsed[index] = GL_TRUE;
 113          tempMax = MAX2(tempMax, index);
 114       }
 115    }
 116
 117    /* allocate a new index for each temp that's used */
 118    {
 119       GLuint freeTemp = 0;
 120       for (i = 0; i <= tempMax; i++) {
 121          if (tempUsed[i]) {
 122             tempMap[i] = freeTemp++;
 123             /*_mesa_printf("replace %u with %u\n", i, tempMap[i]);*/
 124          }
 125       }
 126       if (freeTemp == tempMax + 1) {
 127          /* no consolidation possible */
 128          return;
 129       }
 130       if (dbg) {
 131          _mesa_printf("Replace regs 0..%u with 0..%u\n", tempMax, freeTemp-1);
 132       }
 133    }
 134
 135    /* now replace occurances of old temp indexes with new indexes */
 136    for (i = 0; i < prog->NumInstructions; i++) {
 137       struct prog_instruction *inst = prog->Instructions + i;
 138       const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
 139       GLuint j;
 140       for (j = 0; j < numSrc; j++) {
 141          if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) {
 142             GLuint index = inst->SrcReg[j].Index;
 143             assert(index <= tempMax);
 144             assert(tempUsed[index]);
 145             inst->SrcReg[j].Index = tempMap[index];
 146          }
 147       }
 148       if (inst->DstReg.File == PROGRAM_TEMPORARY) {
 149          const GLuint index = inst->DstReg.Index;
 150          assert(tempUsed[index]);
 151          assert(index <= tempMax);
 152          inst->DstReg.Index = tempMap[index];
 153       }
 154    }
 155    if (dbg) {
 156       _mesa_printf("Optimize: End register consolidation\n");
 157    }
 158 }
 159
 160
 161 /**
 162  * Remove dead instructions from the given program.
 163  * This is very primitive for now.  Basically look for temp registers
 164  * that are written to but never read.  Remove any instructions that
 165  * write to such registers.  Be careful with condition code setters.
 166  */
 167 static void
 168 _mesa_remove_dead_code(struct gl_program *prog)
 169 {
 170    GLboolean tempWritten[MAX_PROGRAM_TEMPS], tempRead[MAX_PROGRAM_TEMPS];
 171    GLboolean *removeInst; /* per-instruction removal flag */
 172    GLuint i, rem;
 173
 174    memset(tempWritten, 0, sizeof(tempWritten));
 175    memset(tempRead, 0, sizeof(tempRead));
 176
 177    if (dbg) {
 178       _mesa_printf("Optimize: Begin dead code removal\n");
 179       /*_mesa_print_program(prog);*/
 180    }
 181
 182    removeInst = (GLboolean *)
 183       _mesa_calloc(prog->NumInstructions * sizeof(GLboolean));
 184
 185    /* Determine which temps are read and written */
 186    for (i = 0; i < prog->NumInstructions; i++) {
 187       const struct prog_instruction *inst = prog->Instructions + i;
 188       const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
 189       GLuint j;
 190
 191       /* check src regs */
 192       for (j = 0; j < numSrc; j++) {
 193          if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) {
 194             const GLuint index = inst->SrcReg[j].Index;
 195             ASSERT(index < MAX_PROGRAM_TEMPS);
 196
 197             if (inst->SrcReg[j].RelAddr) {
 198                if (dbg)
 199                   _mesa_printf("abort remove dead code (indirect temp)\n");
 200                return;
 201             }
 202
 203             tempRead[index] = GL_TRUE;
 204          }
 205       }
 206
 207       /* check dst reg */
 208       if (inst->DstReg.File == PROGRAM_TEMPORARY) {
 209          const GLuint index = inst->DstReg.Index;
 210          ASSERT(index < MAX_PROGRAM_TEMPS);
 211
 212          if (inst->DstReg.RelAddr) {
 213             if (dbg)
 214                _mesa_printf("abort remove dead code (indirect temp)\n");
 215             return;
 216          }
 217
 218          tempWritten[index] = GL_TRUE;
 219          if (inst->CondUpdate) {
 220             /* If we're writing to this register and setting condition
 221              * codes we cannot remove the instruction.  Prevent removal
 222              * by setting the 'read' flag.
 223              */
 224             tempRead[index] = GL_TRUE;
 225          }
 226       }
 227    }
 228
 229    if (dbg) {
 230       for (i = 0; i < MAX_PROGRAM_TEMPS; i++) {
 231          if (tempWritten[i] && !tempRead[i])
 232             _mesa_printf("Remove writes to tmp %u\n", i);
 233       }
 234    }
 235
 236    /* find instructions that write to dead registers, flag for removal */
 237    for (i = 0; i < prog->NumInstructions; i++) {
 238       const struct prog_instruction *inst = prog->Instructions + i;
 239       if (inst->DstReg.File == PROGRAM_TEMPORARY) {
 240          GLint index = inst->DstReg.Index;
 241          removeInst[i] = (tempWritten[index] && !tempRead[index]);
 242          if (dbg && removeInst[i]) {
 243             _mesa_printf("Remove inst %u: ", i);
 244             _mesa_print_instruction(inst);
 245          }
 246       }
 247    }
 248
 249    /* now remove the instructions which aren't needed */
 250    rem = remove_instructions(prog, removeInst);
 251
 252    _mesa_free(removeInst);
 253
 254    if (dbg) {
 255       _mesa_printf("Optimize: End dead code removal.  %u instructions removed\n", rem);
 256       /*_mesa_print_program(prog);*/
 257    }
 258 }
 259
 260
 261 enum temp_use
 262 {
 263    READ,
 264    WRITE,
 265    FLOW,
 266    END
 267 };
 268
 269 /**
 270  * Scan forward in program from 'start' for the next occurance of TEMP[index].
 271  * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator
 272  * that we can't look further.
 273  */
 274 static enum temp_use
 275 find_next_temp_use(const struct gl_program *prog, GLuint start, GLuint index)
 276 {
 277    GLuint i;
 278
 279    for (i = start; i < prog->NumInstructions; i++) {
 280       const struct prog_instruction *inst = prog->Instructions + i;
 281       switch (inst->Opcode) {
 282       case OPCODE_BGNLOOP:
 283       case OPCODE_ENDLOOP:
 284       case OPCODE_BGNSUB:
 285       case OPCODE_ENDSUB:
 286          return FLOW;
 287       default:
 288          {
 289             const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
 290             GLuint j;
 291             for (j = 0; j < numSrc; j++) {
 292                if (inst->SrcReg[j].File == PROGRAM_TEMPORARY &&
 293                    inst->SrcReg[j].Index == index)
 294                   return READ;
 295             }
 296             if (inst->DstReg.File == PROGRAM_TEMPORARY &&
 297                 inst->DstReg.Index == index)
 298                return WRITE;
 299          }
 300       }
 301    }
 302
 303    return END;
 304 }
 305
 306
 307 /**
 308  * Try to remove extraneous MOV instructions from the given program.
 309  */
 310 static void
 311 _mesa_remove_extra_moves(struct gl_program *prog)
 312 {
 313    GLboolean *removeInst; /* per-instruction removal flag */
 314    GLuint i, rem, loopNesting = 0, subroutineNesting = 0;
 315
 316    if (dbg) {
 317       _mesa_printf("Optimize: Begin remove extra moves\n");
 318       _mesa_print_program(prog);
 319    }
 320
 321    removeInst = (GLboolean *)
 322       _mesa_calloc(prog->NumInstructions * sizeof(GLboolean));
 323
 324    /*
 325     * Look for sequences such as this:
 326     *    FOO tmpX, arg0, arg1;
 327     *    MOV tmpY, tmpX;
 328     * and convert into:
 329     *    FOO tmpY, arg0, arg1;
 330     */
 331
 332    for (i = 0; i < prog->NumInstructions; i++) {
 333       const struct prog_instruction *inst = prog->Instructions + i;
 334
 335       switch (inst->Opcode) {
 336       case OPCODE_BGNLOOP:
 337          loopNesting++;
 338          break;
 339       case OPCODE_ENDLOOP:
 340          loopNesting--;
 341          break;
 342       case OPCODE_BGNSUB:
 343          subroutineNesting++;
 344          break;
 345       case OPCODE_ENDSUB:
 346          subroutineNesting--;
 347          break;
 348       case OPCODE_MOV:
 349          if (i > 0 &&
 350              loopNesting == 0 &&
 351              subroutineNesting == 0 &&
 352              inst->SrcReg[0].File == PROGRAM_TEMPORARY &&
 353              inst->SrcReg[0].Swizzle == SWIZZLE_XYZW) {
 354             /* see if this MOV can be removed */
 355             const GLuint tempIndex = inst->SrcReg[0].Index;
 356             struct prog_instruction *prevInst;
 357             GLuint prevI;
 358
 359             /* get pointer to previous instruction */
 360             prevI = i - 1;
 361             while (removeInst[prevI] && prevI > 0)
 362                prevI--;
 363             prevInst = prog->Instructions + prevI;
 364
 365             if (prevInst->DstReg.File == PROGRAM_TEMPORARY &&
 366                 prevInst->DstReg.Index == tempIndex &&
 367                 prevInst->DstReg.WriteMask == WRITEMASK_XYZW) {
 368
 369                enum temp_use next_use =
 370                   find_next_temp_use(prog, i + 1, tempIndex);
 371
 372                if (next_use == WRITE || next_use == END) {
 373                   /* OK, we can safely remove this MOV instruction.
 374                    * Transform:
 375                    *   prevI: FOO tempIndex, x, y;
 376                    *       i: MOV z, tempIndex;
 377                    * Into:
 378                    *   prevI: FOO z, x, y;
 379                    */
 380
 381                   /* patch up prev inst */
 382                   prevInst->DstReg.File = inst->DstReg.File;
 383                   prevInst->DstReg.Index = inst->DstReg.Index;
 384
 385                   /* flag this instruction for removal */
 386                   removeInst[i] = GL_TRUE;
 387
 388                   if (dbg) {
 389                      _mesa_printf("Remove MOV at %u\n", i);
 390                      _mesa_printf("new prev inst %u: ", prevI);
 391                      _mesa_print_instruction(prevInst);
 392                   }
 393                }
 394             }
 395          }
 396          break;
 397       default:
 398          ; /* nothing */
 399       }
 400    }
 401
 402    /* now remove the instructions which aren't needed */
 403    rem = remove_instructions(prog, removeInst);
 404
 405    if (dbg) {
 406       _mesa_printf("Optimize: End remove extra moves.  %u instructions removed\n", rem);
 407       /*_mesa_print_program(prog);*/
 408    }
 409 }
 410
 411
 412 /**
 413  * Apply optimizations to the given program to eliminate unnecessary
 414  * instructions, temp regs, etc.
 415  */
 416 void
 417 _mesa_optimize_program(GLcontext *ctx, struct gl_program *program)
 418 {
 419    if (1)
 420       _mesa_remove_dead_code(program);
 421
 422    if (0) /* not test much yet */
 423       _mesa_remove_extra_moves(program);
 424
 425    if (1)
 426       _mesa_consolidate_registers(program);
 427 }