| /* |
| * Mesa 3-D graphics library |
| * Version: 7.5 |
| * |
| * Copyright (C) 2009 VMware, Inc. All Rights Reserved. |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice shall be included |
| * in all copies or substantial portions of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |
| * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * VMWARE BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN |
| * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| */ |
| |
| |
| |
| #include "main/glheader.h" |
| #include "main/context.h" |
| #include "main/macros.h" |
| #include "program.h" |
| #include "prog_instruction.h" |
| #include "prog_optimize.h" |
| #include "prog_print.h" |
| |
| |
| static GLboolean dbg = GL_FALSE; |
| |
| |
| /** |
| * In 'prog' remove instruction[i] if removeFlags[i] == TRUE. |
| * \return number of instructions removed |
| */ |
| static GLuint |
| remove_instructions(struct gl_program *prog, const GLboolean *removeFlags) |
| { |
| GLint i, removeEnd = 0, removeCount = 0; |
| GLuint totalRemoved = 0; |
| |
| /* go backward */ |
| for (i = prog->NumInstructions - 1; i >= 0; i--) { |
| if (removeFlags[i]) { |
| totalRemoved++; |
| if (removeCount == 0) { |
| /* begin a run of instructions to remove */ |
| removeEnd = i; |
| removeCount = 1; |
| } |
| else { |
| /* extend the run of instructions to remove */ |
| removeCount++; |
| } |
| } |
| else { |
| /* don't remove this instruction, but check if the preceeding |
| * instructions are to be removed. |
| */ |
| if (removeCount > 0) { |
| GLint removeStart = removeEnd - removeCount + 1; |
| _mesa_delete_instructions(prog, removeStart, removeCount); |
| removeStart = removeCount = 0; /* reset removal info */ |
| } |
| } |
| } |
| return totalRemoved; |
| } |
| |
| |
| /** |
| * Consolidate temporary registers to use low numbers. For example, if the |
| * shader only uses temps 4, 5, 8, replace them with 0, 1, 2. |
| */ |
| static void |
| _mesa_consolidate_registers(struct gl_program *prog) |
| { |
| GLboolean tempUsed[MAX_PROGRAM_TEMPS]; |
| GLuint tempMap[MAX_PROGRAM_TEMPS]; |
| GLuint tempMax = 0, i; |
| |
| if (dbg) { |
| _mesa_printf("Optimize: Begin register consolidation\n"); |
| } |
| |
| memset(tempUsed, 0, sizeof(tempUsed)); |
| |
| /* set tempUsed[i] if temporary [i] is referenced */ |
| for (i = 0; i < prog->NumInstructions; i++) { |
| const struct prog_instruction *inst = prog->Instructions + i; |
| const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); |
| GLuint j; |
| for (j = 0; j < numSrc; j++) { |
| if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) { |
| const GLuint index = inst->SrcReg[j].Index; |
| ASSERT(index < MAX_PROGRAM_TEMPS); |
| tempUsed[index] = GL_TRUE; |
| tempMax = MAX2(tempMax, index); |
| break; |
| } |
| } |
| if (inst->DstReg.File == PROGRAM_TEMPORARY) { |
| const GLuint index = inst->DstReg.Index; |
| ASSERT(index < MAX_PROGRAM_TEMPS); |
| tempUsed[index] = GL_TRUE; |
| tempMax = MAX2(tempMax, index); |
| } |
| } |
| |
| /* allocate a new index for each temp that's used */ |
| { |
| GLuint freeTemp = 0; |
| for (i = 0; i <= tempMax; i++) { |
| if (tempUsed[i]) { |
| tempMap[i] = freeTemp++; |
| /*_mesa_printf("replace %u with %u\n", i, tempMap[i]);*/ |
| } |
| } |
| if (freeTemp == tempMax + 1) { |
| /* no consolidation possible */ |
| return; |
| } |
| if (dbg) { |
| _mesa_printf("Replace regs 0..%u with 0..%u\n", tempMax, freeTemp-1); |
| } |
| } |
| |
| /* now replace occurances of old temp indexes with new indexes */ |
| for (i = 0; i < prog->NumInstructions; i++) { |
| struct prog_instruction *inst = prog->Instructions + i; |
| const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); |
| GLuint j; |
| for (j = 0; j < numSrc; j++) { |
| if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) { |
| GLuint index = inst->SrcReg[j].Index; |
| assert(index <= tempMax); |
| assert(tempUsed[index]); |
| inst->SrcReg[j].Index = tempMap[index]; |
| } |
| } |
| if (inst->DstReg.File == PROGRAM_TEMPORARY) { |
| const GLuint index = inst->DstReg.Index; |
| assert(tempUsed[index]); |
| assert(index <= tempMax); |
| inst->DstReg.Index = tempMap[index]; |
| } |
| } |
| if (dbg) { |
| _mesa_printf("Optimize: End register consolidation\n"); |
| } |
| } |
| |
| |
| /** |
| * Remove dead instructions from the given program. |
| * This is very primitive for now. Basically look for temp registers |
| * that are written to but never read. Remove any instructions that |
| * write to such registers. Be careful with condition code setters. |
| */ |
| static void |
| _mesa_remove_dead_code(struct gl_program *prog) |
| { |
| GLboolean tempWritten[MAX_PROGRAM_TEMPS], tempRead[MAX_PROGRAM_TEMPS]; |
| GLboolean *removeInst; /* per-instruction removal flag */ |
| GLuint i, rem; |
| |
| memset(tempWritten, 0, sizeof(tempWritten)); |
| memset(tempRead, 0, sizeof(tempRead)); |
| |
| if (dbg) { |
| _mesa_printf("Optimize: Begin dead code removal\n"); |
| /*_mesa_print_program(prog);*/ |
| } |
| |
| removeInst = (GLboolean *) |
| _mesa_calloc(prog->NumInstructions * sizeof(GLboolean)); |
| |
| /* Determine which temps are read and written */ |
| for (i = 0; i < prog->NumInstructions; i++) { |
| const struct prog_instruction *inst = prog->Instructions + i; |
| const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); |
| GLuint j; |
| |
| /* check src regs */ |
| for (j = 0; j < numSrc; j++) { |
| if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) { |
| const GLuint index = inst->SrcReg[j].Index; |
| ASSERT(index < MAX_PROGRAM_TEMPS); |
| |
| if (inst->SrcReg[j].RelAddr) { |
| if (dbg) |
| _mesa_printf("abort remove dead code (indirect temp)\n"); |
| return; |
| } |
| |
| tempRead[index] = GL_TRUE; |
| } |
| } |
| |
| /* check dst reg */ |
| if (inst->DstReg.File == PROGRAM_TEMPORARY) { |
| const GLuint index = inst->DstReg.Index; |
| ASSERT(index < MAX_PROGRAM_TEMPS); |
| |
| if (inst->DstReg.RelAddr) { |
| if (dbg) |
| _mesa_printf("abort remove dead code (indirect temp)\n"); |
| return; |
| } |
| |
| tempWritten[index] = GL_TRUE; |
| if (inst->CondUpdate) { |
| /* If we're writing to this register and setting condition |
| * codes we cannot remove the instruction. Prevent removal |
| * by setting the 'read' flag. |
| */ |
| tempRead[index] = GL_TRUE; |
| } |
| } |
| } |
| |
| if (dbg) { |
| for (i = 0; i < MAX_PROGRAM_TEMPS; i++) { |
| if (tempWritten[i] && !tempRead[i]) |
| _mesa_printf("Remove writes to tmp %u\n", i); |
| } |
| } |
| |
| /* find instructions that write to dead registers, flag for removal */ |
| for (i = 0; i < prog->NumInstructions; i++) { |
| const struct prog_instruction *inst = prog->Instructions + i; |
| if (inst->DstReg.File == PROGRAM_TEMPORARY) { |
| GLint index = inst->DstReg.Index; |
| removeInst[i] = (tempWritten[index] && !tempRead[index]); |
| if (dbg && removeInst[i]) { |
| _mesa_printf("Remove inst %u: ", i); |
| _mesa_print_instruction(inst); |
| } |
| } |
| } |
| |
| /* now remove the instructions which aren't needed */ |
| rem = remove_instructions(prog, removeInst); |
| |
| _mesa_free(removeInst); |
| |
| if (dbg) { |
| _mesa_printf("Optimize: End dead code removal. %u instructions removed\n", rem); |
| /*_mesa_print_program(prog);*/ |
| } |
| } |
| |
| |
| enum temp_use |
| { |
| READ, |
| WRITE, |
| FLOW, |
| END |
| }; |
| |
| /** |
| * Scan forward in program from 'start' for the next occurance of TEMP[index]. |
| * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator |
| * that we can't look further. |
| */ |
| static enum temp_use |
| find_next_temp_use(const struct gl_program *prog, GLuint start, GLuint index) |
| { |
| GLuint i; |
| |
| for (i = start; i < prog->NumInstructions; i++) { |
| const struct prog_instruction *inst = prog->Instructions + i; |
| switch (inst->Opcode) { |
| case OPCODE_BGNLOOP: |
| case OPCODE_ENDLOOP: |
| case OPCODE_BGNSUB: |
| case OPCODE_ENDSUB: |
| return FLOW; |
| default: |
| { |
| const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode); |
| GLuint j; |
| for (j = 0; j < numSrc; j++) { |
| if (inst->SrcReg[j].File == PROGRAM_TEMPORARY && |
| inst->SrcReg[j].Index == index) |
| return READ; |
| } |
| if (inst->DstReg.File == PROGRAM_TEMPORARY && |
| inst->DstReg.Index == index) |
| return WRITE; |
| } |
| } |
| } |
| |
| return END; |
| } |
| |
| |
| /** |
| * Try to remove extraneous MOV instructions from the given program. |
| */ |
| static void |
| _mesa_remove_extra_moves(struct gl_program *prog) |
| { |
| GLboolean *removeInst; /* per-instruction removal flag */ |
| GLuint i, rem, loopNesting = 0, subroutineNesting = 0; |
| |
| if (dbg) { |
| _mesa_printf("Optimize: Begin remove extra moves\n"); |
| _mesa_print_program(prog); |
| } |
| |
| removeInst = (GLboolean *) |
| _mesa_calloc(prog->NumInstructions * sizeof(GLboolean)); |
| |
| /* |
| * Look for sequences such as this: |
| * FOO tmpX, arg0, arg1; |
| * MOV tmpY, tmpX; |
| * and convert into: |
| * FOO tmpY, arg0, arg1; |
| */ |
| |
| for (i = 0; i < prog->NumInstructions; i++) { |
| const struct prog_instruction *inst = prog->Instructions + i; |
| |
| switch (inst->Opcode) { |
| case OPCODE_BGNLOOP: |
| loopNesting++; |
| break; |
| case OPCODE_ENDLOOP: |
| loopNesting--; |
| break; |
| case OPCODE_BGNSUB: |
| subroutineNesting++; |
| break; |
| case OPCODE_ENDSUB: |
| subroutineNesting--; |
| break; |
| case OPCODE_MOV: |
| if (i > 0 && |
| loopNesting == 0 && |
| subroutineNesting == 0 && |
| inst->SrcReg[0].File == PROGRAM_TEMPORARY && |
| inst->SrcReg[0].Swizzle == SWIZZLE_XYZW) { |
| /* see if this MOV can be removed */ |
| const GLuint tempIndex = inst->SrcReg[0].Index; |
| struct prog_instruction *prevInst; |
| GLuint prevI; |
| |
| /* get pointer to previous instruction */ |
| prevI = i - 1; |
| while (removeInst[prevI] && prevI > 0) |
| prevI--; |
| prevInst = prog->Instructions + prevI; |
| |
| if (prevInst->DstReg.File == PROGRAM_TEMPORARY && |
| prevInst->DstReg.Index == tempIndex && |
| prevInst->DstReg.WriteMask == WRITEMASK_XYZW) { |
| |
| enum temp_use next_use = |
| find_next_temp_use(prog, i + 1, tempIndex); |
| |
| if (next_use == WRITE || next_use == END) { |
| /* OK, we can safely remove this MOV instruction. |
| * Transform: |
| * prevI: FOO tempIndex, x, y; |
| * i: MOV z, tempIndex; |
| * Into: |
| * prevI: FOO z, x, y; |
| */ |
| |
| /* patch up prev inst */ |
| prevInst->DstReg.File = inst->DstReg.File; |
| prevInst->DstReg.Index = inst->DstReg.Index; |
| |
| /* flag this instruction for removal */ |
| removeInst[i] = GL_TRUE; |
| |
| if (dbg) { |
| _mesa_printf("Remove MOV at %u\n", i); |
| _mesa_printf("new prev inst %u: ", prevI); |
| _mesa_print_instruction(prevInst); |
| } |
| } |
| } |
| } |
| break; |
| default: |
| ; /* nothing */ |
| } |
| } |
| |
| /* now remove the instructions which aren't needed */ |
| rem = remove_instructions(prog, removeInst); |
| |
| if (dbg) { |
| _mesa_printf("Optimize: End remove extra moves. %u instructions removed\n", rem); |
| /*_mesa_print_program(prog);*/ |
| } |
| } |
| |
| |
| /** |
| * Apply optimizations to the given program to eliminate unnecessary |
| * instructions, temp regs, etc. |
| */ |
| void |
| _mesa_optimize_program(GLcontext *ctx, struct gl_program *program) |
| { |
| if (1) |
| _mesa_remove_dead_code(program); |
| |
| if (0) /* not test much yet */ |
| _mesa_remove_extra_moves(program); |
| |
| if (1) |
| _mesa_consolidate_registers(program); |
| } |