From 82f1c0be1325130ab03d3bef629264618924b897 Mon Sep 17 00:00:00 2001 From: Brian Paul Date: Fri, 6 Mar 2009 16:18:22 -0700 Subject: [PATCH] mesa: add new program optimizer code This is pretty simplistic for now, but helps with certain shaders. --- src/mesa/SConscript | 1 + src/mesa/shader/prog_optimize.c | 427 ++++++++++++++++++++++++++++++++ src/mesa/shader/prog_optimize.h | 33 +++ src/mesa/sources.mak | 1 + 4 files changed, 462 insertions(+) create mode 100644 src/mesa/shader/prog_optimize.c create mode 100644 src/mesa/shader/prog_optimize.h diff --git a/src/mesa/SConscript b/src/mesa/SConscript index b2f3d96d937..273ce112806 100644 --- a/src/mesa/SConscript +++ b/src/mesa/SConscript @@ -193,6 +193,7 @@ if env['platform'] != 'winddk': 'shader/prog_execute.c', 'shader/prog_instruction.c', 'shader/prog_noise.c', + 'shader/prog_optimize.c', 'shader/prog_parameter.c', 'shader/prog_print.c', 'shader/prog_statevars.c', diff --git a/src/mesa/shader/prog_optimize.c b/src/mesa/shader/prog_optimize.c new file mode 100644 index 00000000000..ec06da141da --- /dev/null +++ b/src/mesa/shader/prog_optimize.c @@ -0,0 +1,427 @@ +/* + * 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); +} diff --git a/src/mesa/shader/prog_optimize.h b/src/mesa/shader/prog_optimize.h new file mode 100644 index 00000000000..d102cfd9fc1 --- /dev/null +++ b/src/mesa/shader/prog_optimize.h @@ -0,0 +1,33 @@ +/* + * 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. + */ + +#ifndef PROG_OPT_H +#define PROG_OPT_H + +struct gl_program; + +extern void +_mesa_optimize_program(GLcontext *ctx, struct gl_program *program); + +#endif diff --git a/src/mesa/sources.mak b/src/mesa/sources.mak index f019ef40baa..08ba345009b 100644 --- a/src/mesa/sources.mak +++ b/src/mesa/sources.mak @@ -224,6 +224,7 @@ SHADER_SOURCES = \ shader/prog_execute.c \ shader/prog_instruction.c \ shader/prog_noise.c \ + shader/prog_optimize.c \ shader/prog_parameter.c \ shader/prog_print.c \ shader/prog_statevars.c \ -- 2.30.2