xserver and mesa git update 28-12-2010

1 files changed, 1250 insertions, 1250 deletions

diff --git a/mesalib/src/mesa/program/prog_optimize.c b/mesalib/src/mesa/program/prog_optimize.c
index 0dc779073..892f5b6ec 100644
--- a/mesalib/src/mesa/program/prog_optimize.c
+++ b/mesalib/src/mesa/program/prog_optimize.c
@@ -1,1250 +1,1250 @@
-/*
- * 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
-/* MAX_PROGRAM_TEMPS is a low number (256), and we want to be able to
- * register allocate many temporary values into that small number of
- * temps.  So allow large temporary indices coming into the register
- * allocator.
- */
-#define REG_ALLOCATE_MAX_PROGRAM_TEMPS	((1 << INST_INDEX_BITS) - 1)
-
-static GLboolean dbg = GL_FALSE;
-
-#define NO_MASK 0xf
-
-/**
- * Returns the mask of channels (bitmask of WRITEMASK_X,Y,Z,W) which
- * are read from the given src in this instruction, We also provide
- * one optional masks which may mask other components in the dst
- * register
- */
-static GLuint
-get_src_arg_mask(const struct prog_instruction *inst,
-                 GLuint arg, GLuint dst_mask)
-{
-   GLuint read_mask, channel_mask;
-   GLuint comp;
-
-   ASSERT(arg < _mesa_num_inst_src_regs(inst->Opcode));
-
-   /* Form the dst register, find the written channels */
-   if (inst->CondUpdate) {
-      channel_mask = WRITEMASK_XYZW;
-   }
-   else {
-      switch (inst->Opcode) {
-      case OPCODE_MOV:
-      case OPCODE_MIN:
-      case OPCODE_MAX:
-      case OPCODE_ABS:
-      case OPCODE_ADD:
-      case OPCODE_MAD:
-      case OPCODE_MUL:
-      case OPCODE_SUB:
-         channel_mask = inst->DstReg.WriteMask & dst_mask;
-         break;
-      case OPCODE_RCP:
-      case OPCODE_SIN:
-      case OPCODE_COS:
-      case OPCODE_RSQ:
-      case OPCODE_POW:
-      case OPCODE_EX2:
-      case OPCODE_LOG:
-         channel_mask = WRITEMASK_X;
-         break;
-      case OPCODE_DP2:
-         channel_mask = WRITEMASK_XY;
-         break;
-      case OPCODE_DP3:
-      case OPCODE_XPD:
-         channel_mask = WRITEMASK_XYZ;
-         break;
-      default:
-         channel_mask = WRITEMASK_XYZW;
-         break;
-      }
-   }
-
-   /* Now, given the src swizzle and the written channels, find which
-    * components are actually read
-    */
-   read_mask = 0x0;
-   for (comp = 0; comp < 4; ++comp) {
-      const GLuint coord = GET_SWZ(inst->SrcReg[arg].Swizzle, comp);
-      ASSERT(coord < 4);
-      if (channel_mask & (1 << comp) && coord <= SWIZZLE_W)
-         read_mask |= 1 << coord;
-   }
-
-   return read_mask;
-}
-
-
-/**
- * For a MOV instruction, compute a write mask when src register also has
- * a mask
- */
-static GLuint
-get_dst_mask_for_mov(const struct prog_instruction *mov, GLuint src_mask)
-{
-   const GLuint mask = mov->DstReg.WriteMask;
-   GLuint comp;
-   GLuint updated_mask = 0x0;
-
-   ASSERT(mov->Opcode == OPCODE_MOV);
-
-   for (comp = 0; comp < 4; ++comp) {
-      GLuint src_comp;
-      if ((mask & (1 << comp)) == 0)
-         continue;
-      src_comp = GET_SWZ(mov->SrcReg[0].Swizzle, comp);
-      if ((src_mask & (1 << src_comp)) == 0)
-         continue;
-      updated_mask |= 1 << comp;
-   }
-
-   return updated_mask;
-}
-
-
-/**
- * Ensure that the swizzle is regular.  That is, all of the swizzle
- * terms are SWIZZLE_X,Y,Z,W and not SWIZZLE_ZERO or SWIZZLE_ONE.
- */
-static GLboolean
-is_swizzle_regular(GLuint swz)
-{
-   return GET_SWZ(swz,0) <= SWIZZLE_W &&
-          GET_SWZ(swz,1) <= SWIZZLE_W &&
-          GET_SWZ(swz,2) <= SWIZZLE_W &&
-          GET_SWZ(swz,3) <= SWIZZLE_W;
-}
-
-
-/**
- * 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];
-      }
-   }
-}
-
-
-/**
- * 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 GLboolean
-_mesa_remove_dead_code_global(struct gl_program *prog)
-{
-   GLboolean tempRead[REG_ALLOCATE_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 < REG_ALLOCATE_MAX_PROGRAM_TEMPS);
-	    read_mask = get_src_arg_mask(inst, j, NO_MASK);
-
-            if (inst->SrcReg[j].RelAddr) {
-               if (dbg)
-                  printf("abort remove dead code (indirect temp)\n");
-               goto done;
-            }
-
-	    for (comp = 0; comp < 4; comp++) {
-	       const GLuint swz = GET_SWZ(inst->SrcReg[j].Swizzle, comp);
-	       ASSERT(swz < 4);
-               if ((read_mask & (1 << swz)) == 0)
-		  continue;
-               if (swz <= SWIZZLE_W)
-                  tempRead[index][swz] = GL_TRUE;
-	    }
-         }
-      }
-
-      /* check dst reg */
-      if (inst->DstReg.File == PROGRAM_TEMPORARY) {
-         const GLuint index = inst->DstReg.Index;
-         ASSERT(index < REG_ALLOCATE_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);
-   return rem != 0;
-}
-
-
-enum inst_use
-{
-   READ,
-   WRITE,
-   FLOW,
-   END
-};
-
-
-/**
- * Scan forward in program from 'start' for the next occurances of TEMP[index].
- * We look if an instruction reads the component given by the masks and if they
- * are overwritten.
- * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator
- * that we can't look further.
- */
-static enum inst_use
-find_next_use(const struct gl_program *prog,
-              GLuint start,
-              GLuint index,
-              GLuint mask)
-{
-   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_BGNSUB:
-      case OPCODE_BRA:
-      case OPCODE_CAL:
-      case OPCODE_CONT:
-      case OPCODE_IF:
-      case OPCODE_ELSE:
-      case OPCODE_ENDIF:
-      case OPCODE_ENDLOOP:
-      case OPCODE_ENDSUB:
-      case OPCODE_RET:
-         return FLOW;
-      case OPCODE_END:
-         return END;
-      default:
-         {
-            const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
-            GLuint j;
-            for (j = 0; j < numSrc; j++) {
-               if (inst->SrcReg[j].RelAddr ||
-                   (inst->SrcReg[j].File == PROGRAM_TEMPORARY &&
-                   inst->SrcReg[j].Index == index &&
-                   (get_src_arg_mask(inst,j,NO_MASK) & mask)))
-                  return READ;
-            }
-            if (_mesa_num_inst_dst_regs(inst->Opcode) == 1 &&
-                inst->DstReg.File == PROGRAM_TEMPORARY &&
-                inst->DstReg.Index == index) {
-               mask &= ~inst->DstReg.WriteMask;
-               if (mask == 0)
-                  return WRITE;
-            }
-         }
-      }
-   }
-   return END;
-}
-
-
-/**
- * Is the given instruction opcode a flow-control opcode?
- * XXX maybe move this into prog_instruction.[ch]
- */
-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;
-   }
-}
-
-
-/**
- * Test if the given instruction is a simple MOV (no conditional updating,
- * not relative addressing, no negation/abs, etc).
- */
-static GLboolean
-can_downward_mov_be_modifed(const struct prog_instruction *mov)
-{
-   return
-      mov->Opcode == OPCODE_MOV &&
-      mov->CondUpdate == GL_FALSE &&
-      mov->SrcReg[0].RelAddr == 0 &&
-      mov->SrcReg[0].Negate == 0 &&
-      mov->SrcReg[0].Abs == 0 &&
-      mov->SrcReg[0].HasIndex2 == 0 &&
-      mov->SrcReg[0].RelAddr2 == 0 &&
-      mov->DstReg.RelAddr == 0 &&
-      mov->DstReg.CondMask == COND_TR &&
-      mov->SaturateMode == SATURATE_OFF;
-}
-
-
-static GLboolean
-can_upward_mov_be_modifed(const struct prog_instruction *mov)
-{
-   return
-      can_downward_mov_be_modifed(mov) &&
-      mov->DstReg.File == PROGRAM_TEMPORARY;
-}
-
-
-/**
- * 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;
-      GLuint dst_mask, src_mask;
-      if (can_upward_mov_be_modifed(mov) == GL_FALSE)
-         continue;
-
-      /* Scanning the code, we maintain the components which are still active in
-       * these two masks
-       */
-      dst_mask = mov->DstReg.WriteMask;
-      src_mask = get_src_arg_mask(mov, 0, NO_MASK);
-
-      /* 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++) {
-	    GLuint comp, read_mask;
-
-	    if (inst2->SrcReg[arg].File != mov->DstReg.File ||
-		inst2->SrcReg[arg].Index != mov->DstReg.Index ||
-		inst2->SrcReg[arg].RelAddr ||
-		inst2->SrcReg[arg].Abs)
-	       continue;
-            read_mask = get_src_arg_mask(inst2, arg, NO_MASK);
-
-	    /* Adjust the swizzles of inst2 to point at MOV's source if ALL the
-             * components read still come from the mov instructions
-             */
-            if (is_swizzle_regular(inst2->SrcReg[arg].Swizzle) &&
-               (read_mask & dst_mask) == read_mask) {
-               for (comp = 0; comp < 4; comp++) {
-                  const GLuint inst2_swz =
-                     GET_SWZ(inst2->SrcReg[arg].Swizzle, comp);
-                  const 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;
-            }
-	 }
-
-	 /* The source of MOV is written. This potentially deactivates some
-          * components from the src and dst of the MOV instruction
-          */
-	 if (inst2->DstReg.File == mov->DstReg.File &&
-	     (inst2->DstReg.RelAddr ||
-	      inst2->DstReg.Index == mov->DstReg.Index)) {
-            dst_mask &= ~inst2->DstReg.WriteMask;
-            src_mask = get_src_arg_mask(mov, 0, dst_mask);
-         }
-
-         /* Idem when the destination of mov is written */
-	 if (inst2->DstReg.File == mov->SrcReg[0].File &&
-	     (inst2->DstReg.RelAddr ||
-	      inst2->DstReg.Index == mov->SrcReg[0].Index)) {
-            src_mask &= ~inst2->DstReg.WriteMask;
-            dst_mask &= get_dst_mask_for_mov(mov, src_mask);
-         }
-         if (dst_mask == 0)
-            break;
-      }
-   }
-
-   if (dbg) {
-      printf("Optimize: End remove extra move use.\n");
-      /*_mesa_print_program(prog);*/
-   }
-}
-
-
-/**
- * Complements dead_code_global. Try to remove code in block of code by
- * carefully monitoring the swizzles. Both functions should be merged into one
- * with a proper control flow graph
- */
-static GLboolean
-_mesa_remove_dead_code_local(struct gl_program *prog)
-{
-   GLboolean *removeInst;
-   GLuint i, arg, rem = 0;
-
-   removeInst = (GLboolean *)
-      calloc(1, prog->NumInstructions * sizeof(GLboolean));
-
-   for (i = 0; i < prog->NumInstructions; i++) {
-      const struct prog_instruction *inst = prog->Instructions + i;
-      const GLuint index = inst->DstReg.Index;
-      const GLuint mask = inst->DstReg.WriteMask;
-      enum inst_use use;
-
-      /* We must deactivate the pass as soon as some indirection is used */
-      if (inst->DstReg.RelAddr)
-         goto done;
-      for (arg = 0; arg < _mesa_num_inst_src_regs(inst->Opcode); arg++)
-         if (inst->SrcReg[arg].RelAddr)
-            goto done;
-
-      if (_mesa_is_flow_control_opcode(inst->Opcode) ||
-          _mesa_num_inst_dst_regs(inst->Opcode) == 0 ||
-          inst->DstReg.File != PROGRAM_TEMPORARY ||
-          inst->DstReg.RelAddr)
-         continue;
-
-      use = find_next_use(prog, i+1, index, mask);
-      if (use == WRITE || use == END)
-         removeInst[i] = GL_TRUE;
-   }
-
-   rem = remove_instructions(prog, removeInst);
-
-done:
-   free(removeInst);
-   return rem != 0;
-}
-
-
-/**
- * Try to inject the destination of mov as the destination of inst and recompute
- * the swizzles operators for the sources of inst if required. Return GL_TRUE
- * of the substitution was possible, GL_FALSE otherwise
- */
-static GLboolean
-_mesa_merge_mov_into_inst(struct prog_instruction *inst,
-                          const struct prog_instruction *mov)
-{
-   /* Indirection table which associates destination and source components for
-    * the mov instruction
-    */
-   const GLuint mask = get_src_arg_mask(mov, 0, NO_MASK);
-
-   /* Some components are not written by inst. We cannot remove the mov */
-   if (mask != (inst->DstReg.WriteMask & mask))
-      return GL_FALSE;
-
-   /* Depending on the instruction, we may need to recompute the swizzles.
-    * Also, some other instructions (like TEX) are not linear. We will only
-    * consider completely active sources and destinations
-    */
-   switch (inst->Opcode) {
-
-   /* Carstesian instructions: we compute the swizzle */
-   case OPCODE_MOV:
-   case OPCODE_MIN:
-   case OPCODE_MAX:
-   case OPCODE_ABS:
-   case OPCODE_ADD:
-   case OPCODE_MAD:
-   case OPCODE_MUL:
-   case OPCODE_SUB:
-   {
-      GLuint dst_to_src_comp[4] = {0,0,0,0};
-      GLuint dst_comp, arg;
-      for (dst_comp = 0; dst_comp < 4; ++dst_comp) {
-         if (mov->DstReg.WriteMask & (1 << dst_comp)) {
-            const GLuint src_comp = GET_SWZ(mov->SrcReg[0].Swizzle, dst_comp);
-            ASSERT(src_comp < 4);
-            dst_to_src_comp[dst_comp] = src_comp;
-         }
-      }
-
-      /* Patch each source of the instruction */
-      for (arg = 0; arg < _mesa_num_inst_src_regs(inst->Opcode); arg++) {
-         const GLuint arg_swz = inst->SrcReg[arg].Swizzle;
-         inst->SrcReg[arg].Swizzle = 0;
-
-         /* Reset each active component of the swizzle */
-         for (dst_comp = 0; dst_comp < 4; ++dst_comp) {
-            GLuint src_comp, arg_comp;
-            if ((mov->DstReg.WriteMask & (1 << dst_comp)) == 0)
-               continue;
-            src_comp = dst_to_src_comp[dst_comp];
-            ASSERT(src_comp < 4);
-            arg_comp = GET_SWZ(arg_swz, src_comp);
-            ASSERT(arg_comp < 4);
-            inst->SrcReg[arg].Swizzle |= arg_comp << (3*dst_comp);
-         }
-      }
-      inst->DstReg = mov->DstReg;
-      return GL_TRUE;
-   }
-
-   /* Dot products and scalar instructions: we only change the destination */
-   case OPCODE_RCP:
-   case OPCODE_SIN:
-   case OPCODE_COS:
-   case OPCODE_RSQ:
-   case OPCODE_POW:
-   case OPCODE_EX2:
-   case OPCODE_LOG:
-   case OPCODE_DP2:
-   case OPCODE_DP3:
-   case OPCODE_DP4:
-      inst->DstReg = mov->DstReg;
-      return GL_TRUE;
-
-   /* All other instructions require fully active components with no swizzle */
-   default:
-      if (mov->SrcReg[0].Swizzle != SWIZZLE_XYZW ||
-          inst->DstReg.WriteMask != WRITEMASK_XYZW)
-         return GL_FALSE;
-      inst->DstReg = mov->DstReg;
-      return GL_TRUE;
-   }
-}
-
-
-/**
- * Try to remove extraneous MOV instructions from the given program.
- */
-static GLboolean
-_mesa_remove_extra_moves(struct gl_program *prog)
-{
-   GLboolean *removeInst; /* per-instruction removal flag */
-   GLuint i, rem = 0, nesting = 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 *mov = prog->Instructions + i;
-
-      switch (mov->Opcode) {
-      case OPCODE_BGNLOOP:
-      case OPCODE_BGNSUB:
-      case OPCODE_IF:
-         nesting++;
-         break;
-      case OPCODE_ENDLOOP:
-      case OPCODE_ENDSUB:
-      case OPCODE_ENDIF:
-         nesting--;
-         break;
-      case OPCODE_MOV:
-         if (i > 0 &&
-             can_downward_mov_be_modifed(mov) &&
-             mov->SrcReg[0].File == PROGRAM_TEMPORARY &&
-             nesting == 0)
-         {
-
-            /* see if this MOV can be removed */
-            const GLuint id = mov->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 == id &&
-                prevInst->DstReg.RelAddr == 0 &&
-                prevInst->DstReg.CondSrc == 0 && 
-                prevInst->DstReg.CondMask == COND_TR) {
-
-               const GLuint dst_mask = prevInst->DstReg.WriteMask;
-               enum inst_use next_use = find_next_use(prog, i+1, id, dst_mask);
-
-               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;
-                   */
-                  if (_mesa_merge_mov_into_inst(prevInst, mov)) {
-                     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);*/
-   }
-
-   return rem != 0;
-}
-
-
-/** 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[REG_ALLOCATE_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
-}
-
-struct loop_info
-{
-   GLuint Start, End;  /**< Start, end instructions of loop */
-};
-
-/**
- * Update the intermediate interval info for register 'index' and
- * instruction 'ic'.
- */
-static void
-update_interval(GLint intBegin[], GLint intEnd[],
-		struct loop_info *loopStack, GLuint loopStackDepth,
-		GLuint index, GLuint ic)
-{
-   int i;
-
-   /* If the register is used in a loop, extend its lifetime through the end
-    * of the outermost loop that doesn't contain its definition.
-    */
-   for (i = 0; i < loopStackDepth; i++) {
-      if (intBegin[index] < loopStack[i].Start) {
-	 ic = loopStack[i].End;
-	 break;
-      }
-   }
-
-   ASSERT(index < REG_ALLOCATE_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[REG_ALLOCATE_MAX_PROGRAM_TEMPS],
-                          GLint intEnd[REG_ALLOCATE_MAX_PROGRAM_TEMPS])
-{
-   struct loop_info loopStack[MAX_LOOP_NESTING];
-   GLuint loopStackDepth = 0;
-   GLuint i;
-
-   for (i = 0; i < REG_ALLOCATE_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, loopStack, loopStackDepth,
-			       index, i);
-            }
-         }
-         if (inst->DstReg.File == PROGRAM_TEMPORARY) {
-            const GLuint index = inst->DstReg.Index;
-            if (inst->DstReg.RelAddr)
-               return GL_FALSE;
-            update_interval(intBegin, intEnd, loopStack, loopStackDepth,
-			    index, i);
-         }
-      }
-   }
-
-   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[REG_ALLOCATE_MAX_PROGRAM_TEMPS];
-   GLint intEnd[REG_ALLOCATE_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 < REG_ALLOCATE_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[REG_ALLOCATE_MAX_PROGRAM_TEMPS])
-{
-   GLuint k;
-   for (k = 0; k < REG_ALLOCATE_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[REG_ALLOCATE_MAX_PROGRAM_TEMPS];
-   GLboolean usedRegs[REG_ALLOCATE_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 < REG_ALLOCATE_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);
-   }
-}
-
-
-#if 0
-static void
-print_it(GLcontext *ctx, struct gl_program *program, const char *txt) {
-   fprintf(stderr, "%s (%u inst):\n", txt, program->NumInstructions);
-   _mesa_print_program(program);
-   _mesa_print_program_parameters(ctx, program);
-   fprintf(stderr, "\n\n");
-}
-#endif
-
-
-/**
- * Apply optimizations to the given program to eliminate unnecessary
- * instructions, temp regs, etc.
- */
-void
-_mesa_optimize_program(GLcontext *ctx, struct gl_program *program)
-{
-   GLboolean any_change;
-
-   /* Stop when no modifications were output */
-   do {
-      any_change = GL_FALSE;
-      _mesa_remove_extra_move_use(program);
-      if (_mesa_remove_dead_code_global(program))
-         any_change = GL_TRUE;
-      if (_mesa_remove_extra_moves(program))
-         any_change = GL_TRUE;
-      if (_mesa_remove_dead_code_local(program))
-         any_change = GL_TRUE;
-      _mesa_reallocate_registers(program);
-   } while (any_change);
-}
-
+/*

+ * 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

+/* MAX_PROGRAM_TEMPS is a low number (256), and we want to be able to

+ * register allocate many temporary values into that small number of

+ * temps.  So allow large temporary indices coming into the register

+ * allocator.

+ */

+#define REG_ALLOCATE_MAX_PROGRAM_TEMPS	((1 << INST_INDEX_BITS) - 1)

+

+static GLboolean dbg = GL_FALSE;

+

+#define NO_MASK 0xf

+

+/**

+ * Returns the mask of channels (bitmask of WRITEMASK_X,Y,Z,W) which

+ * are read from the given src in this instruction, We also provide

+ * one optional masks which may mask other components in the dst

+ * register

+ */

+static GLuint

+get_src_arg_mask(const struct prog_instruction *inst,

+                 GLuint arg, GLuint dst_mask)

+{

+   GLuint read_mask, channel_mask;

+   GLuint comp;

+

+   ASSERT(arg < _mesa_num_inst_src_regs(inst->Opcode));

+

+   /* Form the dst register, find the written channels */

+   if (inst->CondUpdate) {

+      channel_mask = WRITEMASK_XYZW;

+   }

+   else {

+      switch (inst->Opcode) {

+      case OPCODE_MOV:

+      case OPCODE_MIN:

+      case OPCODE_MAX:

+      case OPCODE_ABS:

+      case OPCODE_ADD:

+      case OPCODE_MAD:

+      case OPCODE_MUL:

+      case OPCODE_SUB:

+         channel_mask = inst->DstReg.WriteMask & dst_mask;

+         break;

+      case OPCODE_RCP:

+      case OPCODE_SIN:

+      case OPCODE_COS:

+      case OPCODE_RSQ:

+      case OPCODE_POW:

+      case OPCODE_EX2:

+      case OPCODE_LOG:

+         channel_mask = WRITEMASK_X;

+         break;

+      case OPCODE_DP2:

+         channel_mask = WRITEMASK_XY;

+         break;

+      case OPCODE_DP3:

+      case OPCODE_XPD:

+         channel_mask = WRITEMASK_XYZ;

+         break;

+      default:

+         channel_mask = WRITEMASK_XYZW;

+         break;

+      }

+   }

+

+   /* Now, given the src swizzle and the written channels, find which

+    * components are actually read

+    */

+   read_mask = 0x0;

+   for (comp = 0; comp < 4; ++comp) {

+      const GLuint coord = GET_SWZ(inst->SrcReg[arg].Swizzle, comp);

+      ASSERT(coord < 4);

+      if (channel_mask & (1 << comp) && coord <= SWIZZLE_W)

+         read_mask |= 1 << coord;

+   }

+

+   return read_mask;

+}

+

+

+/**

+ * For a MOV instruction, compute a write mask when src register also has

+ * a mask

+ */

+static GLuint

+get_dst_mask_for_mov(const struct prog_instruction *mov, GLuint src_mask)

+{

+   const GLuint mask = mov->DstReg.WriteMask;

+   GLuint comp;

+   GLuint updated_mask = 0x0;

+

+   ASSERT(mov->Opcode == OPCODE_MOV);

+

+   for (comp = 0; comp < 4; ++comp) {

+      GLuint src_comp;

+      if ((mask & (1 << comp)) == 0)

+         continue;

+      src_comp = GET_SWZ(mov->SrcReg[0].Swizzle, comp);

+      if ((src_mask & (1 << src_comp)) == 0)

+         continue;

+      updated_mask |= 1 << comp;

+   }

+

+   return updated_mask;

+}

+

+

+/**

+ * Ensure that the swizzle is regular.  That is, all of the swizzle

+ * terms are SWIZZLE_X,Y,Z,W and not SWIZZLE_ZERO or SWIZZLE_ONE.

+ */

+static GLboolean

+is_swizzle_regular(GLuint swz)

+{

+   return GET_SWZ(swz,0) <= SWIZZLE_W &&

+          GET_SWZ(swz,1) <= SWIZZLE_W &&

+          GET_SWZ(swz,2) <= SWIZZLE_W &&

+          GET_SWZ(swz,3) <= SWIZZLE_W;

+}

+

+

+/**

+ * 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];

+      }

+   }

+}

+

+

+/**

+ * 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 GLboolean

+_mesa_remove_dead_code_global(struct gl_program *prog)

+{

+   GLboolean tempRead[REG_ALLOCATE_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 < REG_ALLOCATE_MAX_PROGRAM_TEMPS);

+	    read_mask = get_src_arg_mask(inst, j, NO_MASK);

+

+            if (inst->SrcReg[j].RelAddr) {

+               if (dbg)

+                  printf("abort remove dead code (indirect temp)\n");

+               goto done;

+            }

+

+	    for (comp = 0; comp < 4; comp++) {

+	       const GLuint swz = GET_SWZ(inst->SrcReg[j].Swizzle, comp);

+	       ASSERT(swz < 4);

+               if ((read_mask & (1 << swz)) == 0)

+		  continue;

+               if (swz <= SWIZZLE_W)

+                  tempRead[index][swz] = GL_TRUE;

+	    }

+         }

+      }

+

+      /* check dst reg */

+      if (inst->DstReg.File == PROGRAM_TEMPORARY) {

+         const GLuint index = inst->DstReg.Index;

+         ASSERT(index < REG_ALLOCATE_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);

+   return rem != 0;

+}

+

+

+enum inst_use

+{

+   READ,

+   WRITE,

+   FLOW,

+   END

+};

+

+

+/**

+ * Scan forward in program from 'start' for the next occurances of TEMP[index].

+ * We look if an instruction reads the component given by the masks and if they

+ * are overwritten.

+ * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator

+ * that we can't look further.

+ */

+static enum inst_use

+find_next_use(const struct gl_program *prog,

+              GLuint start,

+              GLuint index,

+              GLuint mask)

+{

+   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_BGNSUB:

+      case OPCODE_BRA:

+      case OPCODE_CAL:

+      case OPCODE_CONT:

+      case OPCODE_IF:

+      case OPCODE_ELSE:

+      case OPCODE_ENDIF:

+      case OPCODE_ENDLOOP:

+      case OPCODE_ENDSUB:

+      case OPCODE_RET:

+         return FLOW;

+      case OPCODE_END:

+         return END;

+      default:

+         {

+            const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);

+            GLuint j;

+            for (j = 0; j < numSrc; j++) {

+               if (inst->SrcReg[j].RelAddr ||

+                   (inst->SrcReg[j].File == PROGRAM_TEMPORARY &&

+                   inst->SrcReg[j].Index == index &&

+                   (get_src_arg_mask(inst,j,NO_MASK) & mask)))

+                  return READ;

+            }

+            if (_mesa_num_inst_dst_regs(inst->Opcode) == 1 &&

+                inst->DstReg.File == PROGRAM_TEMPORARY &&

+                inst->DstReg.Index == index) {

+               mask &= ~inst->DstReg.WriteMask;

+               if (mask == 0)

+                  return WRITE;

+            }

+         }

+      }

+   }

+   return END;

+}

+

+

+/**

+ * Is the given instruction opcode a flow-control opcode?

+ * XXX maybe move this into prog_instruction.[ch]

+ */

+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;

+   }

+}

+

+

+/**

+ * Test if the given instruction is a simple MOV (no conditional updating,

+ * not relative addressing, no negation/abs, etc).

+ */

+static GLboolean

+can_downward_mov_be_modifed(const struct prog_instruction *mov)

+{

+   return

+      mov->Opcode == OPCODE_MOV &&

+      mov->CondUpdate == GL_FALSE &&

+      mov->SrcReg[0].RelAddr == 0 &&

+      mov->SrcReg[0].Negate == 0 &&

+      mov->SrcReg[0].Abs == 0 &&

+      mov->SrcReg[0].HasIndex2 == 0 &&

+      mov->SrcReg[0].RelAddr2 == 0 &&

+      mov->DstReg.RelAddr == 0 &&

+      mov->DstReg.CondMask == COND_TR &&

+      mov->SaturateMode == SATURATE_OFF;

+}

+

+

+static GLboolean

+can_upward_mov_be_modifed(const struct prog_instruction *mov)

+{

+   return

+      can_downward_mov_be_modifed(mov) &&

+      mov->DstReg.File == PROGRAM_TEMPORARY;

+}

+

+

+/**

+ * 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;

+      GLuint dst_mask, src_mask;

+      if (can_upward_mov_be_modifed(mov) == GL_FALSE)

+         continue;

+

+      /* Scanning the code, we maintain the components which are still active in

+       * these two masks

+       */

+      dst_mask = mov->DstReg.WriteMask;

+      src_mask = get_src_arg_mask(mov, 0, NO_MASK);

+

+      /* 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++) {

+	    GLuint comp, read_mask;

+

+	    if (inst2->SrcReg[arg].File != mov->DstReg.File ||

+		inst2->SrcReg[arg].Index != mov->DstReg.Index ||

+		inst2->SrcReg[arg].RelAddr ||

+		inst2->SrcReg[arg].Abs)

+	       continue;

+            read_mask = get_src_arg_mask(inst2, arg, NO_MASK);

+

+	    /* Adjust the swizzles of inst2 to point at MOV's source if ALL the

+             * components read still come from the mov instructions

+             */

+            if (is_swizzle_regular(inst2->SrcReg[arg].Swizzle) &&

+               (read_mask & dst_mask) == read_mask) {

+               for (comp = 0; comp < 4; comp++) {

+                  const GLuint inst2_swz =

+                     GET_SWZ(inst2->SrcReg[arg].Swizzle, comp);

+                  const 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;

+            }

+	 }

+

+	 /* The source of MOV is written. This potentially deactivates some

+          * components from the src and dst of the MOV instruction

+          */

+	 if (inst2->DstReg.File == mov->DstReg.File &&

+	     (inst2->DstReg.RelAddr ||

+	      inst2->DstReg.Index == mov->DstReg.Index)) {

+            dst_mask &= ~inst2->DstReg.WriteMask;

+            src_mask = get_src_arg_mask(mov, 0, dst_mask);

+         }

+

+         /* Idem when the destination of mov is written */

+	 if (inst2->DstReg.File == mov->SrcReg[0].File &&

+	     (inst2->DstReg.RelAddr ||

+	      inst2->DstReg.Index == mov->SrcReg[0].Index)) {

+            src_mask &= ~inst2->DstReg.WriteMask;

+            dst_mask &= get_dst_mask_for_mov(mov, src_mask);

+         }

+         if (dst_mask == 0)

+            break;

+      }

+   }

+

+   if (dbg) {

+      printf("Optimize: End remove extra move use.\n");

+      /*_mesa_print_program(prog);*/

+   }

+}

+

+

+/**

+ * Complements dead_code_global. Try to remove code in block of code by

+ * carefully monitoring the swizzles. Both functions should be merged into one

+ * with a proper control flow graph

+ */

+static GLboolean

+_mesa_remove_dead_code_local(struct gl_program *prog)

+{

+   GLboolean *removeInst;

+   GLuint i, arg, rem = 0;

+

+   removeInst = (GLboolean *)

+      calloc(1, prog->NumInstructions * sizeof(GLboolean));

+

+   for (i = 0; i < prog->NumInstructions; i++) {

+      const struct prog_instruction *inst = prog->Instructions + i;

+      const GLuint index = inst->DstReg.Index;

+      const GLuint mask = inst->DstReg.WriteMask;

+      enum inst_use use;

+

+      /* We must deactivate the pass as soon as some indirection is used */

+      if (inst->DstReg.RelAddr)

+         goto done;

+      for (arg = 0; arg < _mesa_num_inst_src_regs(inst->Opcode); arg++)

+         if (inst->SrcReg[arg].RelAddr)

+            goto done;

+

+      if (_mesa_is_flow_control_opcode(inst->Opcode) ||

+          _mesa_num_inst_dst_regs(inst->Opcode) == 0 ||

+          inst->DstReg.File != PROGRAM_TEMPORARY ||

+          inst->DstReg.RelAddr)

+         continue;

+

+      use = find_next_use(prog, i+1, index, mask);

+      if (use == WRITE || use == END)

+         removeInst[i] = GL_TRUE;

+   }

+

+   rem = remove_instructions(prog, removeInst);

+

+done:

+   free(removeInst);

+   return rem != 0;

+}

+

+

+/**

+ * Try to inject the destination of mov as the destination of inst and recompute

+ * the swizzles operators for the sources of inst if required. Return GL_TRUE

+ * of the substitution was possible, GL_FALSE otherwise

+ */

+static GLboolean

+_mesa_merge_mov_into_inst(struct prog_instruction *inst,

+                          const struct prog_instruction *mov)

+{

+   /* Indirection table which associates destination and source components for

+    * the mov instruction

+    */

+   const GLuint mask = get_src_arg_mask(mov, 0, NO_MASK);

+

+   /* Some components are not written by inst. We cannot remove the mov */

+   if (mask != (inst->DstReg.WriteMask & mask))

+      return GL_FALSE;

+

+   /* Depending on the instruction, we may need to recompute the swizzles.

+    * Also, some other instructions (like TEX) are not linear. We will only

+    * consider completely active sources and destinations

+    */

+   switch (inst->Opcode) {

+

+   /* Carstesian instructions: we compute the swizzle */

+   case OPCODE_MOV:

+   case OPCODE_MIN:

+   case OPCODE_MAX:

+   case OPCODE_ABS:

+   case OPCODE_ADD:

+   case OPCODE_MAD:

+   case OPCODE_MUL:

+   case OPCODE_SUB:

+   {

+      GLuint dst_to_src_comp[4] = {0,0,0,0};

+      GLuint dst_comp, arg;

+      for (dst_comp = 0; dst_comp < 4; ++dst_comp) {

+         if (mov->DstReg.WriteMask & (1 << dst_comp)) {

+            const GLuint src_comp = GET_SWZ(mov->SrcReg[0].Swizzle, dst_comp);

+            ASSERT(src_comp < 4);

+            dst_to_src_comp[dst_comp] = src_comp;

+         }

+      }

+

+      /* Patch each source of the instruction */

+      for (arg = 0; arg < _mesa_num_inst_src_regs(inst->Opcode); arg++) {

+         const GLuint arg_swz = inst->SrcReg[arg].Swizzle;

+         inst->SrcReg[arg].Swizzle = 0;

+

+         /* Reset each active component of the swizzle */

+         for (dst_comp = 0; dst_comp < 4; ++dst_comp) {

+            GLuint src_comp, arg_comp;

+            if ((mov->DstReg.WriteMask & (1 << dst_comp)) == 0)

+               continue;

+            src_comp = dst_to_src_comp[dst_comp];

+            ASSERT(src_comp < 4);

+            arg_comp = GET_SWZ(arg_swz, src_comp);

+            ASSERT(arg_comp < 4);

+            inst->SrcReg[arg].Swizzle |= arg_comp << (3*dst_comp);

+         }

+      }

+      inst->DstReg = mov->DstReg;

+      return GL_TRUE;

+   }

+

+   /* Dot products and scalar instructions: we only change the destination */

+   case OPCODE_RCP:

+   case OPCODE_SIN:

+   case OPCODE_COS:

+   case OPCODE_RSQ:

+   case OPCODE_POW:

+   case OPCODE_EX2:

+   case OPCODE_LOG:

+   case OPCODE_DP2:

+   case OPCODE_DP3:

+   case OPCODE_DP4:

+      inst->DstReg = mov->DstReg;

+      return GL_TRUE;

+

+   /* All other instructions require fully active components with no swizzle */

+   default:

+      if (mov->SrcReg[0].Swizzle != SWIZZLE_XYZW ||

+          inst->DstReg.WriteMask != WRITEMASK_XYZW)

+         return GL_FALSE;

+      inst->DstReg = mov->DstReg;

+      return GL_TRUE;

+   }

+}

+

+

+/**

+ * Try to remove extraneous MOV instructions from the given program.

+ */

+static GLboolean

+_mesa_remove_extra_moves(struct gl_program *prog)

+{

+   GLboolean *removeInst; /* per-instruction removal flag */

+   GLuint i, rem = 0, nesting = 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 *mov = prog->Instructions + i;

+

+      switch (mov->Opcode) {

+      case OPCODE_BGNLOOP:

+      case OPCODE_BGNSUB:

+      case OPCODE_IF:

+         nesting++;

+         break;

+      case OPCODE_ENDLOOP:

+      case OPCODE_ENDSUB:

+      case OPCODE_ENDIF:

+         nesting--;

+         break;

+      case OPCODE_MOV:

+         if (i > 0 &&

+             can_downward_mov_be_modifed(mov) &&

+             mov->SrcReg[0].File == PROGRAM_TEMPORARY &&

+             nesting == 0)

+         {

+

+            /* see if this MOV can be removed */

+            const GLuint id = mov->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 == id &&

+                prevInst->DstReg.RelAddr == 0 &&

+                prevInst->DstReg.CondSrc == 0 && 

+                prevInst->DstReg.CondMask == COND_TR) {

+

+               const GLuint dst_mask = prevInst->DstReg.WriteMask;

+               enum inst_use next_use = find_next_use(prog, i+1, id, dst_mask);

+

+               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;

+                   */

+                  if (_mesa_merge_mov_into_inst(prevInst, mov)) {

+                     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);*/

+   }

+

+   return rem != 0;

+}

+

+

+/** 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[REG_ALLOCATE_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

+}

+

+struct loop_info

+{

+   GLuint Start, End;  /**< Start, end instructions of loop */

+};

+

+/**

+ * Update the intermediate interval info for register 'index' and

+ * instruction 'ic'.

+ */

+static void

+update_interval(GLint intBegin[], GLint intEnd[],

+		struct loop_info *loopStack, GLuint loopStackDepth,

+		GLuint index, GLuint ic)

+{

+   int i;

+

+   /* If the register is used in a loop, extend its lifetime through the end

+    * of the outermost loop that doesn't contain its definition.

+    */

+   for (i = 0; i < loopStackDepth; i++) {

+      if (intBegin[index] < loopStack[i].Start) {

+	 ic = loopStack[i].End;

+	 break;

+      }

+   }

+

+   ASSERT(index < REG_ALLOCATE_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[REG_ALLOCATE_MAX_PROGRAM_TEMPS],

+                          GLint intEnd[REG_ALLOCATE_MAX_PROGRAM_TEMPS])

+{

+   struct loop_info loopStack[MAX_LOOP_NESTING];

+   GLuint loopStackDepth = 0;

+   GLuint i;

+

+   for (i = 0; i < REG_ALLOCATE_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, loopStack, loopStackDepth,

+			       index, i);

+            }

+         }

+         if (inst->DstReg.File == PROGRAM_TEMPORARY) {

+            const GLuint index = inst->DstReg.Index;

+            if (inst->DstReg.RelAddr)

+               return GL_FALSE;

+            update_interval(intBegin, intEnd, loopStack, loopStackDepth,

+			    index, i);

+         }

+      }

+   }

+

+   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[REG_ALLOCATE_MAX_PROGRAM_TEMPS];

+   GLint intEnd[REG_ALLOCATE_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 < REG_ALLOCATE_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[REG_ALLOCATE_MAX_PROGRAM_TEMPS])

+{

+   GLuint k;

+   for (k = 0; k < REG_ALLOCATE_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[REG_ALLOCATE_MAX_PROGRAM_TEMPS];

+   GLboolean usedRegs[REG_ALLOCATE_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 < REG_ALLOCATE_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);

+   }

+}

+

+

+#if 0

+static void

+print_it(struct gl_context *ctx, struct gl_program *program, const char *txt) {

+   fprintf(stderr, "%s (%u inst):\n", txt, program->NumInstructions);

+   _mesa_print_program(program);

+   _mesa_print_program_parameters(ctx, program);

+   fprintf(stderr, "\n\n");

+}

+#endif

+

+

+/**

+ * Apply optimizations to the given program to eliminate unnecessary

+ * instructions, temp regs, etc.

+ */

+void

+_mesa_optimize_program(struct gl_context *ctx, struct gl_program *program)

+{

+   GLboolean any_change;

+

+   /* Stop when no modifications were output */

+   do {

+      any_change = GL_FALSE;

+      _mesa_remove_extra_move_use(program);

+      if (_mesa_remove_dead_code_global(program))

+         any_change = GL_TRUE;

+      if (_mesa_remove_extra_moves(program))

+         any_change = GL_TRUE;

+      if (_mesa_remove_dead_code_local(program))

+         any_change = GL_TRUE;

+      _mesa_reallocate_registers(program);

+   } while (any_change);

+}

+