mesa: more/better program optimizations

[mesa.git] / src / mesa / program / prog_optimize.c

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

#define NO_MASK 0xf

/** Returns the mask of channels 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, int arg, int dst_mask)
{
   int read_mask, channel_mask;
   int 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 = 0;
   for (comp = 0; comp < 4; ++comp) {
      const int 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, int src_mask)
{
   const int mask = mov->DstReg.WriteMask;
   int comp;
   int updated_mask = 0;
   ASSERT(mov->Opcode == OPCODE_MOV);

   for (comp = 0; comp < 4; ++comp) {
      int 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 */
static int
is_swizzle_regular(int 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[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, 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 < 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;
}

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

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;
      int 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++) {
            int 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++) {
                  int inst2_swz = GET_SWZ(inst2->SrcReg[arg].Swizzle, comp);

                  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:
   {
      int dst_to_src_comp[4] = {0,0,0,0};
      int dst_comp, arg;
      for (dst_comp = 0; dst_comp < 4; ++dst_comp) {
         if (mov->DstReg.WriteMask & (1 << dst_comp)) {
            const int 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 int 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) {
            int 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) && 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[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);
   }
}

#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);
}