aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/mesa/shader/prog_optimize.c
diff options
context:
space:
mode:
authormarha <marha@users.sourceforge.net>2010-11-22 19:42:40 +0000
committermarha <marha@users.sourceforge.net>2010-11-22 19:42:40 +0000
commit85ef9930f56bf15181f9a0b238f03d55303cf411 (patch)
tree63b43286956ebd1c35c96e9b3d5305aabdf71a0f /mesalib/src/mesa/shader/prog_optimize.c
parent94810d19989336862251dbf69c3f3acb18a9b06d (diff)
downloadvcxsrv-85ef9930f56bf15181f9a0b238f03d55303cf411.tar.gz
vcxsrv-85ef9930f56bf15181f9a0b238f03d55303cf411.tar.bz2
vcxsrv-85ef9930f56bf15181f9a0b238f03d55303cf411.zip
Updated to mesalib 7.9
Diffstat (limited to 'mesalib/src/mesa/shader/prog_optimize.c')
-rw-r--r--mesalib/src/mesa/shader/prog_optimize.c1035
1 files changed, 0 insertions, 1035 deletions
diff --git a/mesalib/src/mesa/shader/prog_optimize.c b/mesalib/src/mesa/shader/prog_optimize.c
deleted file mode 100644
index 2941a17da..000000000
--- a/mesalib/src/mesa/shader/prog_optimize.c
+++ /dev/null
@@ -1,1035 +0,0 @@
-/*
- * 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"
-
-
-#define MAX_LOOP_NESTING 50
-
-
-static GLboolean dbg = GL_FALSE;
-
-/* Returns the mask of channels read from the given srcreg in this instruction.
- */
-static GLuint
-get_src_arg_mask(const struct prog_instruction *inst, int arg)
-{
- int writemask = inst->DstReg.WriteMask;
-
- if (inst->CondUpdate)
- writemask = WRITEMASK_XYZW;
-
- switch (inst->Opcode) {
- case OPCODE_MOV:
- case OPCODE_ABS:
- case OPCODE_ADD:
- case OPCODE_MUL:
- case OPCODE_SUB:
- return writemask;
- case OPCODE_RCP:
- case OPCODE_SIN:
- case OPCODE_COS:
- case OPCODE_RSQ:
- case OPCODE_POW:
- case OPCODE_EX2:
- return WRITEMASK_X;
- case OPCODE_DP2:
- return WRITEMASK_XY;
- case OPCODE_DP3:
- case OPCODE_XPD:
- return WRITEMASK_XYZ;
- default:
- return WRITEMASK_XYZW;
- }
-}
-
-/**
- * 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 */
- }
- }
- }
- /* Finish removing if the first instruction was to be removed. */
- if (removeCount > 0) {
- GLint removeStart = removeEnd - removeCount + 1;
- _mesa_delete_instructions(prog, removeStart, removeCount);
- }
- return totalRemoved;
-}
-
-
-/**
- * Remap register indexes according to map.
- * \param prog the program to search/replace
- * \param file the type of register file to search/replace
- * \param map maps old register indexes to new indexes
- */
-static void
-replace_regs(struct gl_program *prog, gl_register_file file, const GLint map[])
-{
- GLuint i;
-
- 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 == file) {
- GLuint index = inst->SrcReg[j].Index;
- ASSERT(map[index] >= 0);
- inst->SrcReg[j].Index = map[index];
- }
- }
- if (inst->DstReg.File == file) {
- const GLuint index = inst->DstReg.Index;
- ASSERT(map[index] >= 0);
- inst->DstReg.Index = map[index];
- }
- }
-}
-
-
-/**
- * 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];
- GLint tempMap[MAX_PROGRAM_TEMPS];
- GLuint tempMax = 0, i;
-
- if (dbg) {
- printf("Optimize: Begin register consolidation\n");
- }
-
- memset(tempUsed, 0, sizeof(tempUsed));
-
- for (i = 0; i < MAX_PROGRAM_TEMPS; i++) {
- tempMap[i] = -1;
- }
-
- /* 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++;
- /*printf("replace %u with %u\n", i, tempMap[i]);*/
- }
- }
- if (freeTemp == tempMax + 1) {
- /* no consolidation possible */
- return;
- }
- if (dbg) {
- printf("Replace regs 0..%u with 0..%u\n", tempMax, freeTemp-1);
- }
- }
-
- replace_regs(prog, PROGRAM_TEMPORARY, tempMap);
-
- if (dbg) {
- 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 tempRead[MAX_PROGRAM_TEMPS][4];
- GLboolean *removeInst; /* per-instruction removal flag */
- GLuint i, rem = 0, comp;
-
- memset(tempRead, 0, sizeof(tempRead));
-
- if (dbg) {
- printf("Optimize: Begin dead code removal\n");
- /*_mesa_print_program(prog);*/
- }
-
- removeInst = (GLboolean *)
- calloc(1, 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;
- GLuint read_mask;
- ASSERT(index < MAX_PROGRAM_TEMPS);
- read_mask = get_src_arg_mask(inst, j);
-
- if (inst->SrcReg[j].RelAddr) {
- if (dbg)
- printf("abort remove dead code (indirect temp)\n");
- goto done;
- }
-
- for (comp = 0; comp < 4; comp++) {
- GLuint swz = (inst->SrcReg[j].Swizzle >> (3 * comp)) & 0x7;
-
- if ((read_mask & (1 << comp)) == 0)
- continue;
-
- switch (swz) {
- case SWIZZLE_X:
- tempRead[index][0] = GL_TRUE;
- break;
- case SWIZZLE_Y:
- tempRead[index][1] = GL_TRUE;
- break;
- case SWIZZLE_Z:
- tempRead[index][2] = GL_TRUE;
- break;
- case SWIZZLE_W:
- tempRead[index][3] = GL_TRUE;
- break;
- }
- }
- }
- }
-
- /* 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)
- printf("abort remove dead code (indirect temp)\n");
- goto done;
- }
-
- 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][0] = GL_TRUE;
- tempRead[index][1] = GL_TRUE;
- tempRead[index][2] = GL_TRUE;
- tempRead[index][3] = GL_TRUE;
- }
- }
- }
-
- /* find instructions that write to dead registers, flag for removal */
- for (i = 0; i < prog->NumInstructions; i++) {
- struct prog_instruction *inst = prog->Instructions + i;
- const GLuint numDst = _mesa_num_inst_dst_regs(inst->Opcode);
-
- if (numDst != 0 && inst->DstReg.File == PROGRAM_TEMPORARY) {
- GLint chan, index = inst->DstReg.Index;
-
- for (chan = 0; chan < 4; chan++) {
- if (!tempRead[index][chan] &&
- inst->DstReg.WriteMask & (1 << chan)) {
- if (dbg) {
- printf("Remove writemask on %u.%c\n", i,
- chan == 3 ? 'w' : 'x' + chan);
- }
- inst->DstReg.WriteMask &= ~(1 << chan);
- rem++;
- }
- }
-
- if (inst->DstReg.WriteMask == 0) {
- /* If we cleared all writes, the instruction can be removed. */
- if (dbg)
- printf("Remove instruction %u: \n", i);
- removeInst[i] = GL_TRUE;
- }
- }
- }
-
- /* now remove the instructions which aren't needed */
- rem = remove_instructions(prog, removeInst);
-
- if (dbg) {
- printf("Optimize: End dead code removal.\n");
- printf(" %u channel writes removed\n", rem);
- printf(" %u instructions removed\n", rem);
- /*_mesa_print_program(prog);*/
- }
-
-done:
- free(removeInst);
-}
-
-
-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;
-}
-
-static GLboolean _mesa_is_flow_control_opcode(enum prog_opcode opcode)
-{
- switch (opcode) {
- case OPCODE_BGNLOOP:
- case OPCODE_BGNSUB:
- case OPCODE_BRA:
- case OPCODE_CAL:
- case OPCODE_CONT:
- case OPCODE_IF:
- case OPCODE_ELSE:
- case OPCODE_END:
- case OPCODE_ENDIF:
- case OPCODE_ENDLOOP:
- case OPCODE_ENDSUB:
- case OPCODE_RET:
- return GL_TRUE;
- default:
- return GL_FALSE;
- }
-}
-
-/**
- * Try to remove use of extraneous MOV instructions, to free them up for dead
- * code removal.
- */
-static void
-_mesa_remove_extra_move_use(struct gl_program *prog)
-{
- GLuint i, j;
-
- if (dbg) {
- printf("Optimize: Begin remove extra move use\n");
- _mesa_print_program(prog);
- }
-
- /*
- * Look for sequences such as this:
- * MOV tmpX, arg0;
- * ...
- * FOO tmpY, tmpX, arg1;
- * and convert into:
- * MOV tmpX, arg0;
- * ...
- * FOO tmpY, arg0, arg1;
- */
-
- for (i = 0; i + 1 < prog->NumInstructions; i++) {
- const struct prog_instruction *mov = prog->Instructions + i;
-
- if (mov->Opcode != OPCODE_MOV ||
- mov->DstReg.File != PROGRAM_TEMPORARY ||
- mov->DstReg.RelAddr ||
- mov->DstReg.CondMask != COND_TR ||
- mov->SaturateMode != SATURATE_OFF ||
- mov->SrcReg[0].RelAddr)
- continue;
-
- /* Walk through remaining instructions until the or src reg gets
- * rewritten or we get into some flow-control, eliminating the use of
- * this MOV.
- */
- for (j = i + 1; j < prog->NumInstructions; j++) {
- struct prog_instruction *inst2 = prog->Instructions + j;
- GLuint arg;
-
- if (_mesa_is_flow_control_opcode(inst2->Opcode))
- break;
-
- /* First rewrite this instruction's args if appropriate. */
- for (arg = 0; arg < _mesa_num_inst_src_regs(inst2->Opcode); arg++) {
- int comp;
- int read_mask = get_src_arg_mask(inst2, arg);
-
- if (inst2->SrcReg[arg].File != mov->DstReg.File ||
- inst2->SrcReg[arg].Index != mov->DstReg.Index ||
- inst2->SrcReg[arg].RelAddr ||
- inst2->SrcReg[arg].Abs)
- continue;
-
- /* Check that all the sources for this arg of inst2 come from inst1
- * or constants.
- */
- for (comp = 0; comp < 4; comp++) {
- int src_swz = GET_SWZ(inst2->SrcReg[arg].Swizzle, comp);
-
- /* If the MOV didn't write that channel, can't use it. */
- if ((read_mask & (1 << comp)) &&
- src_swz <= SWIZZLE_W &&
- (mov->DstReg.WriteMask & (1 << src_swz)) == 0)
- break;
- }
- if (comp != 4)
- continue;
-
- /* Adjust the swizzles of inst2 to point at MOV's source */
- for (comp = 0; comp < 4; comp++) {
- int inst2_swz = GET_SWZ(inst2->SrcReg[arg].Swizzle, comp);
-
- if (inst2_swz <= SWIZZLE_W) {
- GLuint s = GET_SWZ(mov->SrcReg[0].Swizzle, inst2_swz);
- inst2->SrcReg[arg].Swizzle &= ~(7 << (3 * comp));
- inst2->SrcReg[arg].Swizzle |= s << (3 * comp);
- inst2->SrcReg[arg].Negate ^= (((mov->SrcReg[0].Negate >>
- inst2_swz) & 0x1) << comp);
- }
- }
- inst2->SrcReg[arg].File = mov->SrcReg[0].File;
- inst2->SrcReg[arg].Index = mov->SrcReg[0].Index;
- }
-
- /* If this instruction overwrote part of the move, our time is up. */
- if ((inst2->DstReg.File == mov->DstReg.File &&
- (inst2->DstReg.RelAddr ||
- inst2->DstReg.Index == mov->DstReg.Index)) ||
- (inst2->DstReg.File == mov->SrcReg[0].File &&
- (inst2->DstReg.RelAddr ||
- inst2->DstReg.Index == mov->SrcReg[0].Index)))
- break;
- }
- }
-
- if (dbg) {
- printf("Optimize: End remove extra move use.\n");
- /*_mesa_print_program(prog);*/
- }
-}
-
-/**
- * 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) {
- printf("Optimize: Begin remove extra moves\n");
- _mesa_print_program(prog);
- }
-
- removeInst = (GLboolean *)
- calloc(1, 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 (prevI > 0 && removeInst[prevI])
- 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) {
- printf("Remove MOV at %u\n", i);
- 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);
-
- free(removeInst);
-
- if (dbg) {
- printf("Optimize: End remove extra moves. %u instructions removed\n", rem);
- /*_mesa_print_program(prog);*/
- }
-}
-
-
-/** A live register interval */
-struct interval
-{
- GLuint Reg; /** The temporary register index */
- GLuint Start, End; /** Start/end instruction numbers */
-};
-
-
-/** A list of register intervals */
-struct interval_list
-{
- GLuint Num;
- struct interval Intervals[MAX_PROGRAM_TEMPS];
-};
-
-
-static void
-append_interval(struct interval_list *list, const struct interval *inv)
-{
- list->Intervals[list->Num++] = *inv;
-}
-
-
-/** Insert interval inv into list, sorted by interval end */
-static void
-insert_interval_by_end(struct interval_list *list, const struct interval *inv)
-{
- /* XXX we could do a binary search insertion here since list is sorted */
- GLint i = list->Num - 1;
- while (i >= 0 && list->Intervals[i].End > inv->End) {
- list->Intervals[i + 1] = list->Intervals[i];
- i--;
- }
- list->Intervals[i + 1] = *inv;
- list->Num++;
-
-#ifdef DEBUG
- {
- GLuint i;
- for (i = 0; i + 1 < list->Num; i++) {
- ASSERT(list->Intervals[i].End <= list->Intervals[i + 1].End);
- }
- }
-#endif
-}
-
-
-/** Remove the given interval from the interval list */
-static void
-remove_interval(struct interval_list *list, const struct interval *inv)
-{
- /* XXX we could binary search since list is sorted */
- GLuint k;
- for (k = 0; k < list->Num; k++) {
- if (list->Intervals[k].Reg == inv->Reg) {
- /* found, remove it */
- ASSERT(list->Intervals[k].Start == inv->Start);
- ASSERT(list->Intervals[k].End == inv->End);
- while (k < list->Num - 1) {
- list->Intervals[k] = list->Intervals[k + 1];
- k++;
- }
- list->Num--;
- return;
- }
- }
-}
-
-
-/** called by qsort() */
-static int
-compare_start(const void *a, const void *b)
-{
- const struct interval *ia = (const struct interval *) a;
- const struct interval *ib = (const struct interval *) b;
- if (ia->Start < ib->Start)
- return -1;
- else if (ia->Start > ib->Start)
- return +1;
- else
- return 0;
-}
-
-/** sort the interval list according to interval starts */
-static void
-sort_interval_list_by_start(struct interval_list *list)
-{
- qsort(list->Intervals, list->Num, sizeof(struct interval), compare_start);
-#ifdef DEBUG
- {
- GLuint i;
- for (i = 0; i + 1 < list->Num; i++) {
- ASSERT(list->Intervals[i].Start <= list->Intervals[i + 1].Start);
- }
- }
-#endif
-}
-
-
-/**
- * Update the intermediate interval info for register 'index' and
- * instruction 'ic'.
- */
-static void
-update_interval(GLint intBegin[], GLint intEnd[], GLuint index, GLuint ic)
-{
- ASSERT(index < MAX_PROGRAM_TEMPS);
- if (intBegin[index] == -1) {
- ASSERT(intEnd[index] == -1);
- intBegin[index] = intEnd[index] = ic;
- }
- else {
- intEnd[index] = ic;
- }
-}
-
-
-/**
- * Find first/last instruction that references each temporary register.
- */
-GLboolean
-_mesa_find_temp_intervals(const struct prog_instruction *instructions,
- GLuint numInstructions,
- GLint intBegin[MAX_PROGRAM_TEMPS],
- GLint intEnd[MAX_PROGRAM_TEMPS])
-{
- struct loop_info
- {
- GLuint Start, End; /**< Start, end instructions of loop */
- };
- struct loop_info loopStack[MAX_LOOP_NESTING];
- GLuint loopStackDepth = 0;
- GLuint i;
-
- for (i = 0; i < MAX_PROGRAM_TEMPS; i++){
- intBegin[i] = intEnd[i] = -1;
- }
-
- /* Scan instructions looking for temporary registers */
- for (i = 0; i < numInstructions; i++) {
- const struct prog_instruction *inst = instructions + i;
- if (inst->Opcode == OPCODE_BGNLOOP) {
- loopStack[loopStackDepth].Start = i;
- loopStack[loopStackDepth].End = inst->BranchTarget;
- loopStackDepth++;
- }
- else if (inst->Opcode == OPCODE_ENDLOOP) {
- loopStackDepth--;
- }
- else if (inst->Opcode == OPCODE_CAL) {
- return GL_FALSE;
- }
- else {
- const GLuint numSrc = 3;/*_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;
- if (inst->SrcReg[j].RelAddr)
- return GL_FALSE;
- update_interval(intBegin, intEnd, index, i);
- if (loopStackDepth > 0) {
- /* extend temp register's interval to end of loop */
- GLuint loopEnd = loopStack[loopStackDepth - 1].End;
- update_interval(intBegin, intEnd, index, loopEnd);
- }
- }
- }
- if (inst->DstReg.File == PROGRAM_TEMPORARY) {
- const GLuint index = inst->DstReg.Index;
- if (inst->DstReg.RelAddr)
- return GL_FALSE;
- update_interval(intBegin, intEnd, index, i);
- if (loopStackDepth > 0) {
- /* extend temp register's interval to end of loop */
- GLuint loopEnd = loopStack[loopStackDepth - 1].End;
- update_interval(intBegin, intEnd, index, loopEnd);
- }
- }
- }
- }
-
- return GL_TRUE;
-}
-
-
-/**
- * Find the live intervals for each temporary register in the program.
- * For register R, the interval [A,B] indicates that R is referenced
- * from instruction A through instruction B.
- * Special consideration is needed for loops and subroutines.
- * \return GL_TRUE if success, GL_FALSE if we cannot proceed for some reason
- */
-static GLboolean
-find_live_intervals(struct gl_program *prog,
- struct interval_list *liveIntervals)
-{
- GLint intBegin[MAX_PROGRAM_TEMPS], intEnd[MAX_PROGRAM_TEMPS];
- GLuint i;
-
- /*
- * Note: we'll return GL_FALSE below if we find relative indexing
- * into the TEMP register file. We can't handle that yet.
- * We also give up on subroutines for now.
- */
-
- if (dbg) {
- printf("Optimize: Begin find intervals\n");
- }
-
- /* build intermediate arrays */
- if (!_mesa_find_temp_intervals(prog->Instructions, prog->NumInstructions,
- intBegin, intEnd))
- return GL_FALSE;
-
- /* Build live intervals list from intermediate arrays */
- liveIntervals->Num = 0;
- for (i = 0; i < MAX_PROGRAM_TEMPS; i++) {
- if (intBegin[i] >= 0) {
- struct interval inv;
- inv.Reg = i;
- inv.Start = intBegin[i];
- inv.End = intEnd[i];
- append_interval(liveIntervals, &inv);
- }
- }
-
- /* Sort the list according to interval starts */
- sort_interval_list_by_start(liveIntervals);
-
- if (dbg) {
- /* print interval info */
- for (i = 0; i < liveIntervals->Num; i++) {
- const struct interval *inv = liveIntervals->Intervals + i;
- printf("Reg[%d] live [%d, %d]:",
- inv->Reg, inv->Start, inv->End);
- if (1) {
- GLuint j;
- for (j = 0; j < inv->Start; j++)
- printf(" ");
- for (j = inv->Start; j <= inv->End; j++)
- printf("x");
- }
- printf("\n");
- }
- }
-
- return GL_TRUE;
-}
-
-
-/** Scan the array of used register flags to find free entry */
-static GLint
-alloc_register(GLboolean usedRegs[MAX_PROGRAM_TEMPS])
-{
- GLuint k;
- for (k = 0; k < MAX_PROGRAM_TEMPS; k++) {
- if (!usedRegs[k]) {
- usedRegs[k] = GL_TRUE;
- return k;
- }
- }
- return -1;
-}
-
-
-/**
- * This function implements "Linear Scan Register Allocation" to reduce
- * the number of temporary registers used by the program.
- *
- * We compute the "live interval" for all temporary registers then
- * examine the overlap of the intervals to allocate new registers.
- * Basically, if two intervals do not overlap, they can use the same register.
- */
-static void
-_mesa_reallocate_registers(struct gl_program *prog)
-{
- struct interval_list liveIntervals;
- GLint registerMap[MAX_PROGRAM_TEMPS];
- GLboolean usedRegs[MAX_PROGRAM_TEMPS];
- GLuint i;
- GLint maxTemp = -1;
-
- if (dbg) {
- printf("Optimize: Begin live-interval register reallocation\n");
- _mesa_print_program(prog);
- }
-
- for (i = 0; i < MAX_PROGRAM_TEMPS; i++){
- registerMap[i] = -1;
- usedRegs[i] = GL_FALSE;
- }
-
- if (!find_live_intervals(prog, &liveIntervals)) {
- if (dbg)
- printf("Aborting register reallocation\n");
- return;
- }
-
- {
- struct interval_list activeIntervals;
- activeIntervals.Num = 0;
-
- /* loop over live intervals, allocating a new register for each */
- for (i = 0; i < liveIntervals.Num; i++) {
- const struct interval *live = liveIntervals.Intervals + i;
-
- if (dbg)
- printf("Consider register %u\n", live->Reg);
-
- /* Expire old intervals. Intervals which have ended with respect
- * to the live interval can have their remapped registers freed.
- */
- {
- GLint j;
- for (j = 0; j < (GLint) activeIntervals.Num; j++) {
- const struct interval *inv = activeIntervals.Intervals + j;
- if (inv->End >= live->Start) {
- /* Stop now. Since the activeInterval list is sorted
- * we know we don't have to go further.
- */
- break;
- }
- else {
- /* Interval 'inv' has expired */
- const GLint regNew = registerMap[inv->Reg];
- ASSERT(regNew >= 0);
-
- if (dbg)
- printf(" expire interval for reg %u\n", inv->Reg);
-
- /* remove interval j from active list */
- remove_interval(&activeIntervals, inv);
- j--; /* counter-act j++ in for-loop above */
-
- /* return register regNew to the free pool */
- if (dbg)
- printf(" free reg %d\n", regNew);
- ASSERT(usedRegs[regNew] == GL_TRUE);
- usedRegs[regNew] = GL_FALSE;
- }
- }
- }
-
- /* find a free register for this live interval */
- {
- const GLint k = alloc_register(usedRegs);
- if (k < 0) {
- /* out of registers, give up */
- return;
- }
- registerMap[live->Reg] = k;
- maxTemp = MAX2(maxTemp, k);
- if (dbg)
- printf(" remap register %u -> %d\n", live->Reg, k);
- }
-
- /* Insert this live interval into the active list which is sorted
- * by increasing end points.
- */
- insert_interval_by_end(&activeIntervals, live);
- }
- }
-
- if (maxTemp + 1 < (GLint) liveIntervals.Num) {
- /* OK, we've reduced the number of registers needed.
- * Scan the program and replace all the old temporary register
- * indexes with the new indexes.
- */
- replace_regs(prog, PROGRAM_TEMPORARY, registerMap);
-
- prog->NumTemporaries = maxTemp + 1;
- }
-
- if (dbg) {
- printf("Optimize: End live-interval register reallocation\n");
- printf("Num temp regs before: %u after: %u\n",
- liveIntervals.Num, maxTemp + 1);
- _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)
-{
- _mesa_remove_extra_move_use(program);
-
- if (1)
- _mesa_remove_dead_code(program);
-
- if (0) /* not tested much yet */
- _mesa_remove_extra_moves(program);
-
- if (0)
- _mesa_consolidate_registers(program);
- else
- _mesa_reallocate_registers(program);
-}