[Mesa-dev,15/16] mesa: Make Mesa IR a linked list of instructions.

Submitted by Eric Anholt on May 28, 2014, 6:37 p.m.

Details

Message ID 1401302267-5038-16-git-send-email-eric@anholt.net
State New
Headers show

Not browsing as part of any series.

Commit Message

Eric Anholt May 28, 2014, 6:37 p.m.
Arrays are nice to iterate, but it makes doing optimization that might
remove instructions (or, worse, generate new instructions) a real pain.
---
 src/mesa/drivers/dri/i915/i915_fragprog.c      |  23 +-
 src/mesa/drivers/dri/i965/brw_fs_fp.cpp        |   5 +-
 src/mesa/drivers/dri/i965/brw_vec4_vp.cpp      |   5 +-
 src/mesa/drivers/dri/i965/intel_asm_printer.c  |   4 +-
 src/mesa/drivers/dri/r200/r200_vertprog.c      |  10 +-
 src/mesa/main/ffvertex_prog.c                  |  42 +--
 src/mesa/main/mtypes.h                         |   2 +-
 src/mesa/main/simple_list.h                    |  12 +
 src/mesa/main/state.c                          |   4 +-
 src/mesa/program/arbprogparse.c                |   8 +-
 src/mesa/program/ir_to_mesa.cpp                | 103 ++++---
 src/mesa/program/prog_execute.c                |  73 ++---
 src/mesa/program/prog_execute.h                |   7 +-
 src/mesa/program/prog_instruction.c            | 153 ++++++-----
 src/mesa/program/prog_instruction.h            |  32 ++-
 src/mesa/program/prog_opt_constant_fold.c      |   6 +-
 src/mesa/program/prog_optimize.c               | 194 +++++--------
 src/mesa/program/prog_print.c                  |  25 +-
 src/mesa/program/program.c                     | 224 ++++++---------
 src/mesa/program/program.h                     |  10 +-
 src/mesa/program/program_parse.y               |  51 ++--
 src/mesa/program/programopt.c                  | 361 ++++++++++++-------------
 src/mesa/state_tracker/st_atom_pixeltransfer.c | 140 +++++-----
 src/mesa/state_tracker/st_cb_bitmap.c          |  54 ++--
 src/mesa/state_tracker/st_cb_drawpixels.c      | 100 +++----
 src/mesa/state_tracker/st_glsl_to_tgsi.cpp     |   1 -
 src/mesa/state_tracker/st_mesa_to_tgsi.c       |  63 ++---
 27 files changed, 794 insertions(+), 918 deletions(-)

Patch hide | download patch | download mbox

diff --git a/src/mesa/drivers/dri/i915/i915_fragprog.c b/src/mesa/drivers/dri/i915/i915_fragprog.c
index 96fdd3c..6efb83d 100644
--- a/src/mesa/drivers/dri/i915/i915_fragprog.c
+++ b/src/mesa/drivers/dri/i915/i915_fragprog.c
@@ -293,12 +293,13 @@  do {									\
 static bool calc_live_regs( struct i915_fragment_program *p )
 {
     const struct gl_fragment_program *program = &p->FragProg;
+    struct simple_node *node;
     GLuint regsUsed = ~((1 << I915_MAX_TEMPORARY) - 1);
     uint8_t live_components[I915_MAX_TEMPORARY] = { 0, };
-    GLint i;
-   
-    for (i = program->Base.NumInstructions - 1; i >= 0; i--) {
-        struct prog_instruction *inst = &program->Base.Instructions[i];
+    GLint i = program->Base.NumInstructions - 1;
+
+    foreach_rev(node, &program->Base.Instructions) {
+        struct prog_instruction *inst = (struct prog_instruction *)node;
         int opArgs = _mesa_num_inst_src_regs(inst->Opcode);
         int a;
 
@@ -332,6 +333,7 @@  static bool calc_live_regs( struct i915_fragment_program *p )
         }
 
         p->usedRegs[i] = regsUsed;
+        i--;
     }
 
     return true;
@@ -341,7 +343,7 @@  static GLuint get_live_regs( struct i915_fragment_program *p,
                              const struct prog_instruction *inst )
 {
     const struct gl_fragment_program *program = &p->FragProg;
-    GLuint nr = inst - program->Base.Instructions;
+    GLuint nr = _mesa_count_from_program_start(&program->Base, inst);
 
     return p->usedRegs[nr];
 }
@@ -362,7 +364,8 @@  static void
 upload_program(struct i915_fragment_program *p)
 {
    const struct gl_fragment_program *program = &p->FragProg;
-   const struct prog_instruction *inst = program->Base.Instructions;
+   const struct prog_instruction *inst =
+      (struct prog_instruction *)first_elem(&program->Base.Instructions);
 
    if (INTEL_DEBUG & DEBUG_WM)
       _mesa_print_program(&program->Base);
@@ -371,7 +374,7 @@  upload_program(struct i915_fragment_program *p)
     * loaded, as the flagging of an error isn't sufficient to stop
     * this being uploaded to hardware.
     */
-   if (inst[0].Opcode == OPCODE_END) {
+   if (inst->Opcode == OPCODE_END) {
       GLuint tmp = i915_get_utemp(p);
       i915_emit_arith(p,
                       A0_MOV,
@@ -394,10 +397,13 @@  upload_program(struct i915_fragment_program *p)
       return;
    }
 
-   while (1) {
+   struct simple_node *node;
+   foreach(node, &program->Base.Instructions) {
       GLuint src0, src1, src2, flags;
       GLuint tmp = 0, dst, consts0 = 0, consts1 = 0;
 
+      inst = (struct prog_instruction *)node;
+
       switch (inst->Opcode) {
       case OPCODE_ABS:
          src0 = src_vector(p, &inst->SrcReg[0], program);
@@ -1168,7 +1174,6 @@  upload_program(struct i915_fragment_program *p)
          return;
       }
 
-      inst++;
       i915_release_utemps(p);
    }
 }
diff --git a/src/mesa/drivers/dri/i965/brw_fs_fp.cpp b/src/mesa/drivers/dri/i965/brw_fs_fp.cpp
index ba5514a..5d3c77f 100644
--- a/src/mesa/drivers/dri/i965/brw_fs_fp.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs_fp.cpp
@@ -130,8 +130,9 @@  fs_visitor::emit_fragment_program_code()
    fs_reg one = fs_reg(this, glsl_type::float_type);
    emit(MOV(one, fs_reg(1.0f)));
 
-   for (unsigned int insn = 0; insn < prog->NumInstructions; insn++) {
-      const struct prog_instruction *fpi = &prog->Instructions[insn];
+   struct simple_node *node;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *fpi = (struct prog_instruction *)node;
       base_ir = fpi;
 
       //_mesa_print_instruction(fpi);
diff --git a/src/mesa/drivers/dri/i965/brw_vec4_vp.cpp b/src/mesa/drivers/dri/i965/brw_vec4_vp.cpp
index f1000f2..59861aa 100644
--- a/src/mesa/drivers/dri/i965/brw_vec4_vp.cpp
+++ b/src/mesa/drivers/dri/i965/brw_vec4_vp.cpp
@@ -70,8 +70,9 @@  vec4_vs_visitor::emit_program_code()
    src_reg one = src_reg(this, glsl_type::float_type);
    emit(MOV(dst_reg(one), src_reg(1.0f)));
 
-   for (unsigned int insn = 0; insn < prog->NumInstructions; insn++) {
-      const struct prog_instruction *vpi = &prog->Instructions[insn];
+   struct simple_node *node;
+   foreach(node, &prog->Instructions) {
+      const struct prog_instruction *vpi = (struct prog_instruction *)node;
       base_ir = vpi;
 
       dst_reg dst;
diff --git a/src/mesa/drivers/dri/i965/intel_asm_printer.c b/src/mesa/drivers/dri/i965/intel_asm_printer.c
index f533e7c..5456aba 100644
--- a/src/mesa/drivers/dri/i965/intel_asm_printer.c
+++ b/src/mesa/drivers/dri/i965/intel_asm_printer.c
@@ -52,13 +52,13 @@  dump_assembly(void *assembly, int num_annotations, struct annotation *annotation
          last_annotation_ir = annotation[i].ir;
          if (last_annotation_ir) {
             fprintf(stderr, "   ");
-            if (!prog->Instructions)
+            if (is_empty_list(&prog->Instructions))
                fprint_ir(stderr, annotation[i].ir);
             else {
                const struct prog_instruction *pi =
                   (const struct prog_instruction *)annotation[i].ir;
                fprintf(stderr, "%d: ",
-                       (int)(pi - prog->Instructions));
+                       _mesa_count_from_program_start(prog, pi));
                _mesa_fprint_instruction_opt(stderr,
                                             pi,
                                             0, PROG_PRINT_DEBUG, NULL);
diff --git a/src/mesa/drivers/dri/r200/r200_vertprog.c b/src/mesa/drivers/dri/r200/r200_vertprog.c
index 2397473..676f543 100644
--- a/src/mesa/drivers/dri/r200/r200_vertprog.c
+++ b/src/mesa/drivers/dri/r200/r200_vertprog.c
@@ -393,7 +393,6 @@  static unsigned long op_operands(enum prog_opcode opcode)
 static GLboolean r200_translate_vertex_program(struct gl_context *ctx, struct r200_vertex_program *vp)
 {
    struct gl_vertex_program *mesa_vp = &vp->mesa_program;
-   struct prog_instruction *vpi;
    int i;
    VERTEX_SHADER_INSTRUCTION *o_inst;
    unsigned long operands;
@@ -589,7 +588,13 @@  static GLboolean r200_translate_vertex_program(struct gl_context *ctx, struct r2
    }
 
    o_inst = vp->instr;
-   for (vpi = mesa_vp->Base.Instructions; vpi->Opcode != OPCODE_END; vpi++, o_inst++){
+   struct simple_node *node;
+   foreach(node, &mesa_vp->Base.Instructions) {
+      const struct prog_instruction *vpi = (struct prog_instruction *)node;
+
+      if (vpi->Opcode == OPCODE_END)
+         break;
+
       operands = op_operands(vpi->Opcode);
       are_srcs_scalar = operands & SCALAR_FLAG;
       operands &= OP_MASK;
@@ -1091,6 +1096,7 @@  else {
       if ((o_inst->op & R200_VSF_OUT_CLASS_MASK) == R200_VSF_OUT_CLASS_RESULT_POS) {
 	 vp->pos_end = (o_inst - vp->instr);
       }
+      o_inst++;
    }
 
    vp->native = GL_TRUE;
diff --git a/src/mesa/main/ffvertex_prog.c b/src/mesa/main/ffvertex_prog.c
index 728cf96..3033a93 100644
--- a/src/mesa/main/ffvertex_prog.c
+++ b/src/mesa/main/ffvertex_prog.c
@@ -302,7 +302,6 @@  struct ureg {
 struct tnl_program {
    const struct state_key *state;
    struct gl_vertex_program *program;
-   GLint max_inst;  /** number of instructions allocated for program */
    GLboolean mvp_with_dp4;
 
    GLuint temp_in_use;
@@ -575,38 +574,13 @@  static void emit_op3fn(struct tnl_program *p,
 		       const char *fn,
 		       GLuint line)
 {
-   GLuint nr;
    struct prog_instruction *inst;
 
-   assert((GLint) p->program->Base.NumInstructions <= p->max_inst);
-
-   if (p->program->Base.NumInstructions == p->max_inst) {
-      /* need to extend the program's instruction array */
-      struct prog_instruction *newInst;
-
-      /* double the size */
-      p->max_inst *= 2;
-
-      newInst = _mesa_alloc_instructions(p->max_inst);
-      if (!newInst) {
-         _mesa_error(NULL, GL_OUT_OF_MEMORY, "vertex program build");
-         return;
-      }
-
-      _mesa_copy_instructions(newInst,
-                              p->program->Base.Instructions,
-                              p->program->Base.NumInstructions);
-
-      _mesa_free_instructions(p->program->Base.Instructions,
-                              p->program->Base.NumInstructions);
-
-      p->program->Base.Instructions = newInst;
-   }
-
-   nr = p->program->Base.NumInstructions++;
+   inst = _mesa_alloc_instruction(op);
+   if (!inst)
+      return;
 
-   inst = &p->program->Base.Instructions[nr];
-   inst->Opcode = (enum prog_opcode) op;
+   p->program->Base.NumInstructions++;
 
    emit_arg( &inst->SrcReg[0], src0 );
    emit_arg( &inst->SrcReg[1], src1 );
@@ -614,6 +588,8 @@  static void emit_op3fn(struct tnl_program *p,
 
    emit_dst( &inst->DstReg, dest, mask );
 
+   insert_at_tail(&p->program->Base.Instructions, &inst->link);
+
    debug_insn(inst, fn, line);
 }
 
@@ -1629,11 +1605,7 @@  create_new_program( const struct state_key *key,
    else
       p.temp_reserved = ~((1<<max_temps)-1);
 
-   /* Start by allocating 32 instructions.
-    * If we need more, we'll grow the instruction array as needed.
-    */
-   p.max_inst = 32;
-   p.program->Base.Instructions = _mesa_alloc_instructions(p.max_inst);
+   make_empty_list(&p.program->Base.Instructions);
    p.program->Base.String = NULL;
    p.program->Base.NumInstructions =
    p.program->Base.NumTemporaries =
diff --git a/src/mesa/main/mtypes.h b/src/mesa/main/mtypes.h
index 917d071..1cc3187 100644
--- a/src/mesa/main/mtypes.h
+++ b/src/mesa/main/mtypes.h
@@ -2088,7 +2088,7 @@  struct gl_program
    GLenum Target;    /**< GL_VERTEX/FRAGMENT_PROGRAM_ARB, GL_GEOMETRY_PROGRAM_NV */
    GLenum Format;    /**< String encoding format */
 
-   struct prog_instruction *Instructions;
+   struct simple_node Instructions;
 
    GLbitfield64 InputsRead;     /**< Bitmask of which input regs are read */
    GLbitfield64 OutputsWritten; /**< Bitmask of which output regs are written */
diff --git a/src/mesa/main/simple_list.h b/src/mesa/main/simple_list.h
index 903432d..15bfa9f 100644
--- a/src/mesa/main/simple_list.h
+++ b/src/mesa/main/simple_list.h
@@ -120,6 +120,15 @@  do {						\
    (sentinal)->prev = sentinal;			\
 } while (0)
 
+#define move_list(to, from)                     \
+   do {                                         \
+      assert((from)->next->prev == from);       \
+      assert((from)->prev->next == from);       \
+      *(to) = *(from);                          \
+      (to)->next->prev = to;                    \
+      (to)->prev->next = to;                    \
+} while (0)                                     \
+
 /**
  * Get list first element.
  *
@@ -187,6 +196,9 @@  do {						\
 #define foreach(ptr, list)     \
         for( ptr=(list)->next ;  ptr!=list ;  ptr=(ptr)->next )
 
+#define foreach_rev(ptr, list)     \
+        for( ptr=(list)->prev ;  ptr!=list ;  ptr=(ptr)->prev )
+
 /**
  * Walk through the elements of a list.
  *
diff --git a/src/mesa/main/state.c b/src/mesa/main/state.c
index c122c16..d6ef06e 100644
--- a/src/mesa/main/state.c
+++ b/src/mesa/main/state.c
@@ -69,9 +69,9 @@  update_program_enables(struct gl_context *ctx)
     * GLSL shaders not relevant here.
     */
    ctx->VertexProgram._Enabled = ctx->VertexProgram.Enabled
-      && ctx->VertexProgram.Current->Base.Instructions;
+      && !is_empty_list(&ctx->VertexProgram.Current->Base.Instructions);
    ctx->FragmentProgram._Enabled = ctx->FragmentProgram.Enabled
-      && ctx->FragmentProgram.Current->Base.Instructions;
+      && !is_empty_list(&ctx->FragmentProgram.Current->Base.Instructions);
    ctx->ATIFragmentShader._Enabled = ctx->ATIFragmentShader.Enabled
       && ctx->ATIFragmentShader.Current->Instructions[0];
 }
diff --git a/src/mesa/program/arbprogparse.c b/src/mesa/program/arbprogparse.c
index 5b96650..d2e4a44 100644
--- a/src/mesa/program/arbprogparse.c
+++ b/src/mesa/program/arbprogparse.c
@@ -121,8 +121,8 @@  _mesa_parse_arb_fragment_program(struct gl_context* ctx, GLenum target,
    program->UsesKill            = state.fragment.UsesKill;
    program->UsesDFdy            = state.fragment.UsesDFdy;
 
-   free(program->Base.Instructions);
-   program->Base.Instructions = prog.Instructions;
+   _mesa_free_instructions(&program->Base.Instructions);
+   move_list(&program->Base.Instructions, &prog.Instructions);
 
    if (program->Base.Parameters)
       _mesa_free_parameter_list(program->Base.Parameters);
@@ -199,8 +199,8 @@  _mesa_parse_arb_vertex_program(struct gl_context *ctx, GLenum target,
    program->IsPositionInvariant = (state.option.PositionInvariant)
       ? GL_TRUE : GL_FALSE;
 
-   free(program->Base.Instructions);
-   program->Base.Instructions = prog.Instructions;
+   _mesa_free_instructions(&program->Base.Instructions);
+   move_list(&program->Base.Instructions, &prog.Instructions);
 
    if (program->Base.Parameters)
       _mesa_free_parameter_list(program->Base.Parameters);
diff --git a/src/mesa/program/ir_to_mesa.cpp b/src/mesa/program/ir_to_mesa.cpp
index 1b9a519..1777614 100644
--- a/src/mesa/program/ir_to_mesa.cpp
+++ b/src/mesa/program/ir_to_mesa.cpp
@@ -204,12 +204,11 @@  public:
    ir_to_mesa_instruction *bgn_inst;
 
    /**
-    * Index of the first instruction of the function body in actual
-    * Mesa IR.
+    * First instruction of the function body in actual Mesa IR.
     *
     * Set after convertion from ir_to_mesa_instruction to prog_instruction.
     */
-   int inst;
+   struct prog_instruction *inst;
 
    /** Storage for the return value. */
    src_reg return_reg;
@@ -2273,16 +2272,16 @@  mesa_src_reg_from_ir_src_reg(src_reg reg)
 
 static void
 set_branchtargets(ir_to_mesa_visitor *v,
-		  struct prog_instruction *mesa_instructions,
-		  int num_instructions)
+		  struct simple_node *mesa_instructions)
 {
+   struct simple_node *node;
    int if_count = 0, loop_count = 0;
-   int *if_stack, *loop_stack;
+   struct prog_instruction **if_stack, **loop_stack;
    int if_stack_pos = 0, loop_stack_pos = 0;
-   int i, j;
 
-   for (i = 0; i < num_instructions; i++) {
-      switch (mesa_instructions[i].Opcode) {
+   foreach(node, mesa_instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
+      switch (inst->Opcode) {
       case OPCODE_IF:
 	 if_count++;
 	 break;
@@ -2291,32 +2290,36 @@  set_branchtargets(ir_to_mesa_visitor *v,
 	 break;
       case OPCODE_BRK:
       case OPCODE_CONT:
-	 mesa_instructions[i].BranchTarget = -1;
+	 inst->BranchTarget = NULL;
 	 break;
       default:
 	 break;
       }
    }
 
-   if_stack = rzalloc_array(v->mem_ctx, int, if_count);
-   loop_stack = rzalloc_array(v->mem_ctx, int, loop_count);
+   if_stack = rzalloc_array(v->mem_ctx, struct prog_instruction *, if_count);
+   loop_stack = rzalloc_array(v->mem_ctx, struct prog_instruction *,
+                              loop_count);
+
+   foreach(node, mesa_instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
+      struct simple_node *node2;
 
-   for (i = 0; i < num_instructions; i++) {
-      switch (mesa_instructions[i].Opcode) {
+      switch (inst->Opcode) {
       case OPCODE_IF:
-	 if_stack[if_stack_pos] = i;
+	 if_stack[if_stack_pos] = inst;
 	 if_stack_pos++;
 	 break;
       case OPCODE_ELSE:
-	 mesa_instructions[if_stack[if_stack_pos - 1]].BranchTarget = i;
-	 if_stack[if_stack_pos - 1] = i;
+	 if_stack[if_stack_pos - 1]->BranchTarget = inst;
+	 if_stack[if_stack_pos - 1] = inst;
 	 break;
       case OPCODE_ENDIF:
-	 mesa_instructions[if_stack[if_stack_pos - 1]].BranchTarget = i;
+	 if_stack[if_stack_pos - 1]->BranchTarget = inst;
 	 if_stack_pos--;
 	 break;
       case OPCODE_BGNLOOP:
-	 loop_stack[loop_stack_pos] = i;
+	 loop_stack[loop_stack_pos] = inst;
 	 loop_stack_pos++;
 	 break;
       case OPCODE_ENDLOOP:
@@ -2325,24 +2328,27 @@  set_branchtargets(ir_to_mesa_visitor *v,
 	  * already had a BranchTarget assigned) to point to the end
 	  * of the loop.
 	  */
-	 for (j = loop_stack[loop_stack_pos]; j < i; j++) {
-	    if (mesa_instructions[j].Opcode == OPCODE_BRK ||
-		mesa_instructions[j].Opcode == OPCODE_CONT) {
-	       if (mesa_instructions[j].BranchTarget == -1) {
-		  mesa_instructions[j].BranchTarget = i;
+	 for (node2 = loop_stack[loop_stack_pos]->link.next;
+              node2 != node;
+              node2 = node2->next) {
+            struct prog_instruction *brkcont = (struct prog_instruction *)node2;
+	    if (brkcont->Opcode == OPCODE_BRK ||
+		brkcont->Opcode == OPCODE_CONT) {
+	       if (!brkcont->BranchTarget) {
+		  brkcont->BranchTarget = inst;
 	       }
 	    }
 	 }
 	 /* The loop ends point at each other. */
-	 mesa_instructions[i].BranchTarget = loop_stack[loop_stack_pos];
-	 mesa_instructions[loop_stack[loop_stack_pos]].BranchTarget = i;
+	 inst->BranchTarget = loop_stack[loop_stack_pos];
+	 loop_stack[loop_stack_pos]->BranchTarget = inst;
 	 break;
       case OPCODE_CAL:
 	 foreach_list(n, &v->function_signatures) {
 	    function_entry *entry = (function_entry *) n;
 
-	    if (entry->sig_id == mesa_instructions[i].BranchTarget) {
-	       mesa_instructions[i].BranchTarget = entry->inst;
+	    if (entry->sig_id == (intptr_t)inst->BranchTarget) {
+	       inst->BranchTarget = entry->inst;
 	       break;
 	    }
 	 }
@@ -2354,16 +2360,16 @@  set_branchtargets(ir_to_mesa_visitor *v,
 }
 
 static void
-print_program(struct prog_instruction *mesa_instructions,
-	      ir_instruction **mesa_instruction_annotation,
-	      int num_instructions)
+print_program(struct gl_program *prog,
+	      ir_instruction **mesa_instruction_annotation)
 {
+   struct simple_node *node;
    ir_instruction *last_ir = NULL;
-   int i;
+   int i = 0;
    int indent = 0;
 
-   for (i = 0; i < num_instructions; i++) {
-      struct prog_instruction *mesa_inst = mesa_instructions + i;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *mesa_inst = (struct prog_instruction *)node;
       ir_instruction *ir = mesa_instruction_annotation[i];
 
       fprintf(stderr, "%3d: ", i);
@@ -2382,7 +2388,8 @@  print_program(struct prog_instruction *mesa_instructions,
       }
 
       indent = _mesa_fprint_instruction_opt(stderr, mesa_inst, indent,
-					    PROG_PRINT_DEBUG, NULL);
+					    PROG_PRINT_DEBUG, prog);
+      i++;
    }
 }
 
@@ -2796,7 +2803,8 @@  get_mesa_program(struct gl_context *ctx,
 		 struct gl_shader *shader)
 {
    ir_to_mesa_visitor v;
-   struct prog_instruction *mesa_instructions, *mesa_inst;
+   struct simple_node mesa_instructions;
+   struct prog_instruction *mesa_inst;
    ir_instruction **mesa_instruction_annotation;
    int i;
    struct gl_program *prog;
@@ -2830,9 +2838,6 @@  get_mesa_program(struct gl_context *ctx,
       num_instructions++;
    }
 
-   mesa_instructions =
-      (struct prog_instruction *)calloc(num_instructions,
-					sizeof(*mesa_instructions));
    mesa_instruction_annotation = ralloc_array(v.mem_ctx, ir_instruction *,
 					      num_instructions);
 
@@ -2840,11 +2845,13 @@  get_mesa_program(struct gl_context *ctx,
 
    /* Convert ir_mesa_instructions into prog_instructions.
     */
-   mesa_inst = mesa_instructions;
    i = 0;
    foreach_list(node, &v.instructions) {
       const ir_to_mesa_instruction *inst = (ir_to_mesa_instruction *) node;
 
+      mesa_inst = (struct prog_instruction *)calloc(1, sizeof(*mesa_inst));
+      if (!mesa_inst)
+         goto fail_exit;
       mesa_inst->Opcode = inst->op;
       mesa_inst->CondUpdate = inst->cond_update;
       if (inst->saturate)
@@ -2861,6 +2868,7 @@  get_mesa_program(struct gl_context *ctx,
       mesa_inst->TexSrcTarget = inst->tex_target;
       mesa_inst->TexShadow = inst->tex_shadow;
       mesa_instruction_annotation[i] = inst->ir;
+      _mesa_append_instruction(prog, mesa_inst);
 
       /* Set IndirectRegisterFiles. */
       if (mesa_inst->DstReg.RelAddr)
@@ -2903,7 +2911,6 @@  get_mesa_program(struct gl_context *ctx,
 	 break;
       }
 
-      mesa_inst++;
       i++;
 
       if (!shader_program->LinkStatus)
@@ -2914,7 +2921,7 @@  get_mesa_program(struct gl_context *ctx,
       goto fail_exit;
    }
 
-   set_branchtargets(&v, mesa_instructions, num_instructions);
+   set_branchtargets(&v, &prog->Instructions);
 
    if (ctx->_Shader->Flags & GLSL_DUMP) {
       fprintf(stderr, "\n");
@@ -2925,19 +2932,10 @@  get_mesa_program(struct gl_context *ctx,
       fprintf(stderr, "\n");
       fprintf(stderr, "Mesa IR for linked %s program %d:\n", target_string,
 	      shader_program->Name);
-      print_program(mesa_instructions, mesa_instruction_annotation,
-		    num_instructions);
+      print_program(prog, mesa_instruction_annotation);
       fflush(stderr);
    }
 
-   prog->Instructions = mesa_instructions;
-   prog->NumInstructions = num_instructions;
-
-   /* Setting this to NULL prevents a possible double free in the fail_exit
-    * path (far below).
-    */
-   mesa_instructions = NULL;
-
    do_set_program_inouts(shader->ir, prog, shader->Stage);
 
    prog->SamplersUsed = shader->active_samplers;
@@ -2976,7 +2974,6 @@  get_mesa_program(struct gl_context *ctx,
    return prog;
 
 fail_exit:
-   free(mesa_instructions);
    _mesa_reference_program(ctx, &shader->Program, NULL);
    return NULL;
 }
diff --git a/src/mesa/program/prog_execute.c b/src/mesa/program/prog_execute.c
index 115525e..cd2db98 100644
--- a/src/mesa/program/prog_execute.c
+++ b/src/mesa/program/prog_execute.c
@@ -572,7 +572,8 @@  _mesa_execute_program(struct gl_context * ctx,
 {
    const GLuint numInst = program->NumInstructions;
    const GLuint maxExec = 65536;
-   GLuint pc, numExec = 0;
+   GLuint numExec = 0;
+   struct simple_node *node;
 
    machine->CurProgram = program;
 
@@ -587,8 +588,8 @@  _mesa_execute_program(struct gl_context * ctx,
       machine->EnvParams = ctx->FragmentProgram.Parameters;
    }
 
-   for (pc = 0; pc < numInst; pc++) {
-      const struct prog_instruction *inst = program->Instructions + pc;
+   foreach(node, &program->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
 
       if (DEBUG_PROG) {
          _mesa_print_instruction(inst);
@@ -635,35 +636,35 @@  _mesa_execute_program(struct gl_context * ctx,
          break;
       case OPCODE_BGNLOOP:
          /* no-op */
-         ASSERT(program->Instructions[inst->BranchTarget].Opcode
-                == OPCODE_ENDLOOP);
+         ASSERT(inst->BranchTarget->Opcode == OPCODE_ENDLOOP);
          break;
       case OPCODE_ENDLOOP:
-         /* subtract 1 here since pc is incremented by for(pc) loop */
-         ASSERT(program->Instructions[inst->BranchTarget].Opcode
-                == OPCODE_BGNLOOP);
-         pc = inst->BranchTarget - 1;   /* go to matching BNGLOOP */
+         /* Jump to instruction preceding the branch target, since the loop
+          * will increment the instruction.
+          */
+         ASSERT(inst->BranchTarget->Opcode == OPCODE_BGNLOOP);
+         node = inst->BranchTarget->link.prev;
          break;
       case OPCODE_BGNSUB:      /* begin subroutine */
          break;
       case OPCODE_ENDSUB:      /* end subroutine */
          break;
       case OPCODE_BRK:         /* break out of loop (conditional) */
-         ASSERT(program->Instructions[inst->BranchTarget].Opcode
-                == OPCODE_ENDLOOP);
+         ASSERT(inst->BranchTarget->Opcode == OPCODE_ENDLOOP);
          if (eval_condition(machine, inst)) {
-            /* break out of loop */
-            /* pc++ at end of for-loop will put us after the ENDLOOP inst */
-            pc = inst->BranchTarget;
+            /* Jump to the ENDLOOP, since the main loop will increment the
+             * instruction.
+             */
+            node = &inst->BranchTarget->link;
          }
          break;
       case OPCODE_CONT:        /* continue loop (conditional) */
-         ASSERT(program->Instructions[inst->BranchTarget].Opcode
-                == OPCODE_ENDLOOP);
+         ASSERT(inst->BranchTarget->Opcode == OPCODE_ENDLOOP);
          if (eval_condition(machine, inst)) {
-            /* continue at ENDLOOP */
-            /* Subtract 1 here since we'll do pc++ at end of for-loop */
-            pc = inst->BranchTarget - 1;
+            /* Jump to instruction preceding the ENDLOOP, since the main loop
+             * will increment the instruction.
+             */
+            node = inst->BranchTarget->link.prev;
          }
          break;
       case OPCODE_CAL:         /* Call subroutine (conditional) */
@@ -672,9 +673,11 @@  _mesa_execute_program(struct gl_context * ctx,
             if (machine->StackDepth >= MAX_PROGRAM_CALL_DEPTH) {
                return GL_TRUE;  /* Per GL_NV_vertex_program2 spec */
             }
-            machine->CallStack[machine->StackDepth++] = pc + 1; /* next inst */
-            /* Subtract 1 here since we'll do pc++ at end of for-loop */
-            pc = inst->BranchTarget - 1;
+            machine->CallStack[machine->StackDepth++] = inst->link.next; /* next inst */
+            /* Jump to instruction preceding the branch target, since the main
+             * loop will increment the instruction.
+             */
+            node = inst->BranchTarget->link.prev;
          }
          break;
       case OPCODE_CMP:
@@ -847,10 +850,8 @@  _mesa_execute_program(struct gl_context * ctx,
       case OPCODE_IF:
          {
             GLboolean cond;
-            ASSERT(program->Instructions[inst->BranchTarget].Opcode
-                   == OPCODE_ELSE ||
-                   program->Instructions[inst->BranchTarget].Opcode
-                   == OPCODE_ENDIF);
+            ASSERT(inst->BranchTarget->Opcode == OPCODE_ELSE ||
+                   inst->BranchTarget->Opcode == OPCODE_ENDIF);
             /* eval condition */
             if (inst->SrcReg[0].File != PROGRAM_UNDEFINED) {
                GLfloat a[4];
@@ -868,18 +869,17 @@  _mesa_execute_program(struct gl_context * ctx,
                /* do if-clause (just continue execution) */
             }
             else {
-               /* go to the instruction after ELSE or ENDIF */
-               assert(inst->BranchTarget >= 0);
-               pc = inst->BranchTarget;
+               /* Jump to the instruction after the ELSE or ENDIF (the main loop
+                * will increment the instruction).
+                */
+               node = &inst->BranchTarget->link;
             }
          }
          break;
       case OPCODE_ELSE:
          /* goto ENDIF */
-         ASSERT(program->Instructions[inst->BranchTarget].Opcode
-                == OPCODE_ENDIF);
-         assert(inst->BranchTarget >= 0);
-         pc = inst->BranchTarget;
+         ASSERT(inst->BranchTarget->Opcode == OPCODE_ENDIF);
+         node = inst->BranchTarget;
          break;
       case OPCODE_ENDIF:
          /* nothing */
@@ -1225,8 +1225,10 @@  _mesa_execute_program(struct gl_context * ctx,
             if (machine->StackDepth == 0) {
                return GL_TRUE;  /* Per GL_NV_vertex_program2 spec */
             }
-            /* subtract one because of pc++ in the for loop */
-            pc = machine->CallStack[--machine->StackDepth] - 1;
+            /* The CallStack holds the address of the CAL, so the foreach will
+             * go to the instruction after the CAL.
+             */
+            node = machine->CallStack[--machine->StackDepth];
          }
          break;
       case OPCODE_RFL:         /* reflection vector */
@@ -1672,7 +1674,6 @@  _mesa_execute_program(struct gl_context * ctx,
 	 }
          return GL_TRUE;
       }
-
    } /* for pc */
 
    return GL_TRUE;
diff --git a/src/mesa/program/prog_execute.h b/src/mesa/program/prog_execute.h
index 09542bf..44a4000 100644
--- a/src/mesa/program/prog_execute.h
+++ b/src/mesa/program/prog_execute.h
@@ -69,7 +69,12 @@  struct gl_program_machine
 
    const GLubyte *Samplers;  /** Array mapping sampler var to tex unit */
 
-   GLuint CallStack[MAX_PROGRAM_CALL_DEPTH]; /**< For CAL/RET instructions */
+
+   /**
+    * For a series of CAL/RET instructions, this stack holds a pointers to the
+    * CAL instructions.
+    */
+   struct simple_node *CallStack[MAX_PROGRAM_CALL_DEPTH];
    GLuint StackDepth; /**< Index/ptr to top of CallStack[] */
 
    /** Texture fetch functions */
diff --git a/src/mesa/program/prog_instruction.c b/src/mesa/program/prog_instruction.c
index dcfedb7..ab0adfb 100644
--- a/src/mesa/program/prog_instruction.c
+++ b/src/mesa/program/prog_instruction.c
@@ -29,107 +29,92 @@ 
 #include "main/mtypes.h"
 #include "prog_instruction.h"
 
-
-/**
- * Initialize program instruction fields to defaults.
- * \param inst  first instruction to initialize
- * \param count  number of instructions to initialize
- */
-void
-_mesa_init_instructions(struct prog_instruction *inst, GLuint count)
+struct prog_instruction *
+_mesa_alloc_instruction(gl_inst_opcode opcode)
 {
-   GLuint i;
+   struct prog_instruction *inst = calloc(1, sizeof(struct prog_instruction));
 
-   memset(inst, 0, count * sizeof(struct prog_instruction));
+   if (!inst)
+      return NULL;
 
-   for (i = 0; i < count; i++) {
-      inst[i].SrcReg[0].File = PROGRAM_UNDEFINED;
-      inst[i].SrcReg[0].Swizzle = SWIZZLE_NOOP;
-      inst[i].SrcReg[1].File = PROGRAM_UNDEFINED;
-      inst[i].SrcReg[1].Swizzle = SWIZZLE_NOOP;
-      inst[i].SrcReg[2].File = PROGRAM_UNDEFINED;
-      inst[i].SrcReg[2].Swizzle = SWIZZLE_NOOP;
+   inst->Opcode = opcode;
+   inst->SrcReg[0].File = PROGRAM_UNDEFINED;
+   inst->SrcReg[0].Swizzle = SWIZZLE_NOOP;
+   inst->SrcReg[1].File = PROGRAM_UNDEFINED;
+   inst->SrcReg[1].Swizzle = SWIZZLE_NOOP;
+   inst->SrcReg[2].File = PROGRAM_UNDEFINED;
+   inst->SrcReg[2].Swizzle = SWIZZLE_NOOP;
 
-      inst[i].DstReg.File = PROGRAM_UNDEFINED;
-      inst[i].DstReg.WriteMask = WRITEMASK_XYZW;
-      inst[i].DstReg.CondMask = COND_TR;
-      inst[i].DstReg.CondSwizzle = SWIZZLE_NOOP;
+   inst->DstReg.File = PROGRAM_UNDEFINED;
+   inst->DstReg.WriteMask = WRITEMASK_XYZW;
+   inst->DstReg.CondMask = COND_TR;
+   inst->DstReg.CondSwizzle = SWIZZLE_NOOP;
 
-      inst[i].SaturateMode = SATURATE_OFF;
-      inst[i].Precision = FLOAT32;
-   }
+   inst->SaturateMode = SATURATE_OFF;
+   inst->Precision = FLOAT32;
+
+   return inst;
 }
 
 
 /**
- * Allocate an array of program instructions.
- * \param numInst  number of instructions
- * \return pointer to instruction memory
+ * Duplicate a list of program instructions to the end of an existing list.
  */
-struct prog_instruction *
-_mesa_alloc_instructions(GLuint numInst)
+bool
+_mesa_copy_instructions(struct simple_node *dst, const struct simple_node *src)
 {
-   return
-      calloc(1, numInst * sizeof(struct prog_instruction));
-}
+   struct simple_node *node;
 
+   foreach(node, src) {
+      struct prog_instruction *src_inst = (struct prog_instruction *)node;
+      struct prog_instruction *dst_inst;
 
-/**
- * Reallocate memory storing an array of program instructions.
- * This is used when we need to append additional instructions onto an
- * program.
- * \param oldInst  pointer to first of old/src instructions
- * \param numOldInst  number of instructions at <oldInst>
- * \param numNewInst  desired size of new instruction array.
- * \return  pointer to start of new instruction array.
- */
-struct prog_instruction *
-_mesa_realloc_instructions(struct prog_instruction *oldInst,
-                           GLuint numOldInst, GLuint numNewInst)
-{
-   struct prog_instruction *newInst;
+      /* We don't have fixup code for this, but no callers currently ask us to
+       * copy code that branches.
+       */
+      assert(!src_inst->BranchTarget);
 
-   newInst = (struct prog_instruction *)
-      _mesa_realloc(oldInst,
-                    numOldInst * sizeof(struct prog_instruction),
-                    numNewInst * sizeof(struct prog_instruction));
+      dst_inst = _mesa_alloc_instruction(src_inst->Opcode);
+      if (!dst_inst)
+         return false;
 
-   return newInst;
-}
+      *dst_inst = *src_inst;
+      if (dst_inst->Comment)
+         dst_inst->Comment = _mesa_strdup(dst_inst->Comment);
+
+      insert_at_tail(dst, &dst_inst->link);
+   }
 
+   return true;
+}
 
 /**
- * Copy an array of program instructions.
- * \param dest  pointer to destination.
- * \param src  pointer to source.
- * \param n  number of instructions to copy.
- * \return pointer to destination.
+ * Free a single instruction.
+ *
+ * Our prog_instructions aren't contained in any pool or anything, so memory
+ * management is totally manual.
  */
-struct prog_instruction *
-_mesa_copy_instructions(struct prog_instruction *dest,
-                        const struct prog_instruction *src, GLuint n)
+void
+_mesa_free_instruction(struct prog_instruction *inst)
 {
-   GLuint i;
-   memcpy(dest, src, n * sizeof(struct prog_instruction));
-   for (i = 0; i < n; i++) {
-      if (src[i].Comment)
-         dest[i].Comment = _mesa_strdup(src[i].Comment);
-   }
-   return dest;
+   free((char *)inst->Comment);
+   free(inst);
 }
 
-
 /**
  * Free an array of instructions
  */
 void
-_mesa_free_instructions(struct prog_instruction *inst, GLuint count)
+_mesa_free_instructions(struct simple_node *list)
 {
-   GLuint i;
-   for (i = 0; i < count; i++) {
-      free((char *)inst[i].Comment);
+   struct simple_node *node, *temp_node;
+
+   foreach_s(node, temp_node, list) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
+      remove_from_list(&inst->link);
+      _mesa_free_instruction(inst);
    }
-   free(inst);
+   make_empty_list(list);
 }
 
 
@@ -332,3 +317,25 @@  _mesa_opcode_string(gl_inst_opcode opcode)
    }
 }
 
+unsigned
+_mesa_count_between_instructions(const struct prog_instruction *a,
+                                 const struct prog_instruction *b)
+{
+   const struct simple_node *node;
+   int count = 0;
+
+   for (node = &a->link; node != &b->link; node = node->next)
+      count++;
+
+   return count;
+}
+
+unsigned
+_mesa_count_from_program_start(const struct gl_program *prog,
+                               const struct prog_instruction *inst)
+{
+   struct prog_instruction *first =
+      (struct prog_instruction *)first_elem(&prog->Instructions);
+
+   return _mesa_count_between_instructions(first, inst);
+}
diff --git a/src/mesa/program/prog_instruction.h b/src/mesa/program/prog_instruction.h
index b9604e5..fee1be7 100644
--- a/src/mesa/program/prog_instruction.h
+++ b/src/mesa/program/prog_instruction.h
@@ -39,7 +39,7 @@ 
 
 
 #include "main/glheader.h"
-
+#include "main/simple_list.h"
 
 /**
  * Swizzle indexes.
@@ -310,6 +310,9 @@  struct prog_dst_register
  */
 struct prog_instruction
 {
+   /* Must be the first field in prog_instruction */
+   struct simple_node link;
+
    gl_inst_opcode Opcode;
    struct prog_src_register SrcReg[3];
    struct prog_dst_register DstReg;
@@ -376,7 +379,7 @@  struct prog_instruction
     * For IF, points to ELSE or ENDIF.
     * For ELSE, points to ENDIF.
     */
-   GLint BranchTarget;
+   struct prog_instruction *BranchTarget;
 
    /** for debugging purposes */
    const char *Comment;
@@ -390,22 +393,25 @@  struct prog_instruction
 extern "C" {
 #endif
 
-extern void
-_mesa_init_instructions(struct prog_instruction *inst, GLuint count);
-
 extern struct prog_instruction *
-_mesa_alloc_instructions(GLuint numInst);
+_mesa_alloc_instruction(gl_inst_opcode opcode);
 
-extern struct prog_instruction *
-_mesa_realloc_instructions(struct prog_instruction *oldInst,
-                           GLuint numOldInst, GLuint numNewInst);
+extern bool
+_mesa_copy_instructions(struct simple_node *dst, const struct simple_node *src);
 
-extern struct prog_instruction *
-_mesa_copy_instructions(struct prog_instruction *dest,
-                        const struct prog_instruction *src, GLuint n);
+extern void
+_mesa_free_instruction(struct prog_instruction *inst);
 
 extern void
-_mesa_free_instructions(struct prog_instruction *inst, GLuint count);
+_mesa_free_instructions(struct simple_node *list);
+
+extern unsigned
+_mesa_count_between_instructions(const struct prog_instruction *a,
+                                 const struct prog_instruction *b);
+
+extern unsigned
+_mesa_count_from_program_start(const struct gl_program *prog,
+                               const struct prog_instruction *b);
 
 extern GLuint
 _mesa_num_inst_src_regs(gl_inst_opcode opcode);
diff --git a/src/mesa/program/prog_opt_constant_fold.c b/src/mesa/program/prog_opt_constant_fold.c
index 3811c0d..9ca2005 100644
--- a/src/mesa/program/prog_opt_constant_fold.c
+++ b/src/mesa/program/prog_opt_constant_fold.c
@@ -131,10 +131,10 @@  GLboolean
 _mesa_constant_fold(struct gl_program *prog)
 {
    bool progress = false;
-   unsigned i;
+   struct simple_node *node;
 
-   for (i = 0; i < prog->NumInstructions; i++) {
-      struct prog_instruction *const inst = &prog->Instructions[i];
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
 
       switch (inst->Opcode) {
       case OPCODE_ADD:
diff --git a/src/mesa/program/prog_optimize.c b/src/mesa/program/prog_optimize.c
index 88dc177..6bcbce1 100644
--- a/src/mesa/program/prog_optimize.c
+++ b/src/mesa/program/prog_optimize.c
@@ -38,6 +38,14 @@  static GLboolean dbg = GL_FALSE;
 
 #define NO_MASK 0xf
 
+static void
+remove_instruction(struct gl_program *prog, struct prog_instruction *inst)
+{
+   remove_from_list(&inst->link);
+   _mesa_free_instruction(inst);
+   prog->NumInstructions--;
+}
+
 /**
  * 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
@@ -157,51 +165,6 @@  is_swizzle_regular(GLuint swz)
           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
@@ -209,12 +172,12 @@  remove_instructions(struct gl_program *prog, const GLboolean *removeFlags)
  * \param map  maps old register indexes to new indexes
  */
 static void
-replace_regs(struct gl_program *prog, gl_register_file file, const GLint map[])
+replace_regs(struct simple_node *list, gl_register_file file, const GLint map[])
 {
-   GLuint i;
+   struct simple_node *node;
 
-   for (i = 0; i < prog->NumInstructions; i++) {
-      struct prog_instruction *inst = prog->Instructions + i;
+   foreach(node, list) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
       GLuint j;
       for (j = 0; j < numSrc; j++) {
@@ -243,8 +206,9 @@  static GLboolean
 _mesa_remove_dead_code_global(struct gl_program *prog)
 {
    bool *tempRead;
-   GLboolean *removeInst; /* per-instruction removal flag */
-   GLuint i, rem = 0, comp;
+   bool rem = false;
+   GLuint i, comp;
+   struct simple_node *node, *node_temp;
 
    tempRead = calloc(prog->NumTemporaries, 4 * sizeof(bool));
    if (!tempRead)
@@ -255,12 +219,9 @@  _mesa_remove_dead_code_global(struct gl_program *prog)
       /*_mesa_print_program(prog);*/
    }
 
-   removeInst =
-      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;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
       GLuint j;
 
@@ -313,9 +274,10 @@  _mesa_remove_dead_code_global(struct gl_program *prog)
       }
    }
 
-   /* find instructions that write to dead registers, flag for removal */
-   for (i = 0; i < prog->NumInstructions; i++) {
-      struct prog_instruction *inst = prog->Instructions + i;
+   /* find instructions that write to dead registers and remove them */
+   i = 0;
+   foreach_s(node, node_temp, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       const GLuint numDst = _mesa_num_inst_dst_regs(inst->Opcode);
 
       if (numDst != 0 && inst->DstReg.File == PROGRAM_TEMPORARY) {
@@ -337,14 +299,13 @@  _mesa_remove_dead_code_global(struct gl_program *prog)
 	    /* If we cleared all writes, the instruction can be removed. */
 	    if (dbg)
                fprintf(stderr, "Remove instruction %u: \n", i);
-	    removeInst[i] = GL_TRUE;
+            remove_instruction(prog, inst);
+            rem = true;
 	 }
       }
+      i++;
    }
 
-   /* now remove the instructions which aren't needed */
-   rem = remove_instructions(prog, removeInst);
-
    if (dbg) {
       fprintf(stderr, "Optimize: End dead code removal.\n");
       fprintf(stderr, "  %u channel writes removed\n", rem);
@@ -354,8 +315,7 @@  _mesa_remove_dead_code_global(struct gl_program *prog)
 
 done:
    free(tempRead);
-   free(removeInst);
-   return rem != 0;
+   return rem;
 }
 
 
@@ -377,14 +337,17 @@  enum inst_use
  */
 static enum inst_use
 find_next_use(const struct gl_program *prog,
-              GLuint start,
+              struct prog_instruction *inst,
               GLuint index,
               GLuint mask)
 {
-   GLuint i;
+   struct simple_node *node;
+
+   for (node = next_elem(&inst->link);
+        !at_end(&prog->Instructions, node);
+        node = next_elem(node)) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
 
-   for (i = start; i < prog->NumInstructions; i++) {
-      const struct prog_instruction *inst = prog->Instructions + i;
       switch (inst->Opcode) {
       case OPCODE_BGNLOOP:
       case OPCODE_BGNSUB:
@@ -488,7 +451,7 @@  can_upward_mov_be_modifed(const struct prog_instruction *mov)
 static void
 _mesa_remove_extra_move_use(struct gl_program *prog)
 {
-   GLuint i, j;
+   struct simple_node *node;
 
    if (dbg) {
       fprintf(stderr, "Optimize: Begin remove extra move use\n");
@@ -506,8 +469,10 @@  _mesa_remove_extra_move_use(struct gl_program *prog)
     *    FOO tmpY, arg0, arg1;
     */
 
-   for (i = 0; i < prog->NumInstructions; i++) {
-      const struct prog_instruction *mov = prog->Instructions + i;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *mov = (struct prog_instruction *)node;
+      struct simple_node *node2;
+
       GLuint dst_mask, src_mask;
       if (can_upward_mov_be_modifed(mov) == GL_FALSE)
          continue;
@@ -522,8 +487,10 @@  _mesa_remove_extra_move_use(struct gl_program *prog)
        * 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;
+      for (node2 = mov->link.next;
+           node2 != &prog->Instructions;
+           node2 = node2->next) {
+	 struct prog_instruction *inst2 = (struct prog_instruction *)node2;
          GLuint arg;
 
 	 if (_mesa_is_flow_control_opcode(inst2->Opcode))
@@ -596,14 +563,12 @@  _mesa_remove_extra_move_use(struct gl_program *prog)
 static GLboolean
 _mesa_remove_dead_code_local(struct gl_program *prog)
 {
-   GLboolean *removeInst;
-   GLuint i, arg, rem = 0;
-
-   removeInst =
-      calloc(1, prog->NumInstructions * sizeof(GLboolean));
+   bool rem = false;
+   GLuint arg;
+   struct simple_node *node, *t;
 
-   for (i = 0; i < prog->NumInstructions; i++) {
-      const struct prog_instruction *inst = prog->Instructions + i;
+   foreach_s(node, t, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       const GLuint index = inst->DstReg.Index;
       const GLuint mask = inst->DstReg.WriteMask;
       enum inst_use use;
@@ -621,16 +586,15 @@  _mesa_remove_dead_code_local(struct gl_program *prog)
           inst->DstReg.RelAddr)
          continue;
 
-      use = find_next_use(prog, i+1, index, mask);
-      if (use == WRITE || use == END)
-         removeInst[i] = GL_TRUE;
+      use = find_next_use(prog, inst, index, mask);
+      if (use == WRITE || use == END) {
+         remove_instruction(prog, inst);
+         rem = true;
+      }
    }
 
-   rem = remove_instructions(prog, removeInst);
-
 done:
-   free(removeInst);
-   return rem != 0;
+   return rem;
 }
 
 
@@ -732,17 +696,14 @@  _mesa_merge_mov_into_inst(struct prog_instruction *inst,
 static GLboolean
 _mesa_remove_extra_moves(struct gl_program *prog)
 {
-   GLboolean *removeInst; /* per-instruction removal flag */
-   GLuint i, rem = 0, nesting = 0;
+   struct simple_node *node, *t;
+   GLuint rem = 0, nesting = 0;
 
    if (dbg) {
       fprintf(stderr, "Optimize: Begin remove extra moves\n");
       _mesa_print_program(prog);
    }
 
-   removeInst =
-      calloc(1, prog->NumInstructions * sizeof(GLboolean));
-
    /*
     * Look for sequences such as this:
     *    FOO tmpX, arg0, arg1;
@@ -751,8 +712,8 @@  _mesa_remove_extra_moves(struct gl_program *prog)
     *    FOO tmpY, arg0, arg1;
     */
 
-   for (i = 0; i < prog->NumInstructions; i++) {
-      const struct prog_instruction *mov = prog->Instructions + i;
+   foreach_s(node, t, &prog->Instructions) {
+      struct prog_instruction *mov = (struct prog_instruction *)node;
 
       switch (mov->Opcode) {
       case OPCODE_BGNLOOP:
@@ -766,7 +727,7 @@  _mesa_remove_extra_moves(struct gl_program *prog)
          nesting--;
          break;
       case OPCODE_MOV:
-         if (i > 0 &&
+         if (mov->link.prev != &prog->Instructions &&
              can_downward_mov_be_modifed(mov) &&
              mov->SrcReg[0].File == PROGRAM_TEMPORARY &&
              nesting == 0)
@@ -774,14 +735,8 @@  _mesa_remove_extra_moves(struct gl_program *prog)
 
             /* 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;
+            struct prog_instruction *prevInst =
+               (struct prog_instruction *)mov->link.prev;
 
             if (prevInst->DstReg.File == PROGRAM_TEMPORARY &&
                 prevInst->DstReg.Index == id &&
@@ -789,7 +744,7 @@  _mesa_remove_extra_moves(struct gl_program *prog)
                 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);
+               enum inst_use next_use = find_next_use(prog, mov, id, dst_mask);
 
                if (next_use == WRITE || next_use == END) {
                   /* OK, we can safely remove this MOV instruction.
@@ -800,12 +755,13 @@  _mesa_remove_extra_moves(struct gl_program *prog)
                    *   prevI: FOO z, x, y;
                    */
                   if (_mesa_merge_mov_into_inst(prevInst, mov)) {
-                     removeInst[i] = GL_TRUE;
                      if (dbg) {
-                        fprintf(stderr, "Remove MOV at %u\n", i);
-                        fprintf(stderr, "new prev inst %u: ", prevI);
+                        fprintf(stderr, "Remove MOV: ");
+                        _mesa_print_instruction(mov);
+                        fprintf(stderr, "new prev: ");
                         _mesa_print_instruction(prevInst);
                      }
+                     remove_instruction(prog, mov);
                   }
                }
             }
@@ -816,11 +772,6 @@  _mesa_remove_extra_moves(struct gl_program *prog)
       }
    }
 
-   /* now remove the instructions which aren't needed */
-   rem = remove_instructions(prog, removeInst);
-
-   free(removeInst);
-
    if (dbg) {
       fprintf(stderr, "Optimize: End remove extra moves.  %u instructions removed\n", rem);
       /*_mesa_print_program(prog);*/
@@ -975,6 +926,7 @@  static GLboolean
 _mesa_find_temp_intervals(struct gl_program *prog,
                           struct interval_list *intervals)
 {
+   struct simple_node *node;
    struct loop_info loopStack[MAX_LOOP_NESTING];
    GLuint loopStackDepth = 0;
    GLuint i;
@@ -995,11 +947,13 @@  _mesa_find_temp_intervals(struct gl_program *prog,
    intervals->Num = prog->NumTemporaries;
 
    /* Scan instructions looking for temporary registers */
-   for (i = 0; i < prog->NumInstructions; i++) {
-      const struct prog_instruction *inst = prog->Instructions + i;
+   i = 0;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       if (inst->Opcode == OPCODE_BGNLOOP) {
          loopStack[loopStackDepth].Start = i;
-         loopStack[loopStackDepth].End = inst->BranchTarget;
+         loopStack[loopStackDepth].End =
+            i + _mesa_count_between_instructions(inst, inst->BranchTarget);
          loopStackDepth++;
       }
       else if (inst->Opcode == OPCODE_ENDLOOP) {
@@ -1028,6 +982,7 @@  _mesa_find_temp_intervals(struct gl_program *prog,
                             loopStack, loopStackDepth, i);
          }
       }
+      i++;
    }
 
    return GL_TRUE;
@@ -1227,7 +1182,7 @@  _mesa_reallocate_registers(struct gl_program *prog)
        * Scan the program and replace all the old temporary register
        * indexes with the new indexes.
        */
-      replace_regs(prog, PROGRAM_TEMPORARY, registerMap);
+      replace_regs(&prog->Instructions, PROGRAM_TEMPORARY, registerMap);
 
       prog->NumTemporaries = maxTemp + 1;
    }
@@ -1280,6 +1235,7 @@  print_it(struct gl_context *ctx, struct gl_program *program, const char *txt) {
 static void
 _mesa_simplify_cmp(struct gl_program * program)
 {
+   struct simple_node *node;
    GLuint *tempWrites;
    GLuint outputWrites[MAX_PROGRAM_OUTPUTS];
    GLuint i;
@@ -1297,8 +1253,8 @@  _mesa_simplify_cmp(struct gl_program * program)
       outputWrites[i] = 0;
    }
 
-   for (i = 0; i < program->NumInstructions; i++) {
-      struct prog_instruction *inst = program->Instructions + i;
+   foreach(node, &program->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       GLuint prevWriteMask;
 
       /* Give up if we encounter relative addressing or flow control. */
diff --git a/src/mesa/program/prog_print.c b/src/mesa/program/prog_print.c
index 4a5c1c1..a822dac 100644
--- a/src/mesa/program/prog_print.c
+++ b/src/mesa/program/prog_print.c
@@ -632,6 +632,11 @@  _mesa_print_alu_instruction(const struct prog_instruction *inst,
 				numRegs, PROG_PRINT_DEBUG, NULL);
 }
 
+static unsigned
+branch_index(const struct gl_program *prog, const struct prog_instruction *inst)
+{
+   return _mesa_count_from_program_start(prog, inst->BranchTarget);
+}
 
 /**
  * Print a single vertex/fragment program instruction.
@@ -741,20 +746,20 @@  _mesa_fprint_instruction_opt(FILE *f,
 		 _mesa_swizzle_string(inst->DstReg.CondSwizzle,
 				      0, GL_FALSE));
       }
-      fprintf(f, " # (if false, goto %d)", inst->BranchTarget);
+      fprintf(f, " # (if false, goto %d)", branch_index(prog, inst));
       fprint_comment(f, inst);
       return indent + 3;
    case OPCODE_ELSE:
-      fprintf(f, "ELSE; # (goto %d)\n", inst->BranchTarget);
+      fprintf(f, "ELSE; # (goto %d)\n", branch_index(prog, inst));
       return indent + 3;
    case OPCODE_ENDIF:
       fprintf(f, "ENDIF;\n");
       break;
    case OPCODE_BGNLOOP:
-      fprintf(f, "BGNLOOP; # (end at %d)\n", inst->BranchTarget);
+      fprintf(f, "BGNLOOP; # (end at %d)\n", branch_index(prog, inst));
       return indent + 3;
    case OPCODE_ENDLOOP:
-      fprintf(f, "ENDLOOP; # (goto %d)\n", inst->BranchTarget);
+      fprintf(f, "ENDLOOP; # (goto %d)\n", branch_index(prog, inst));
       break;
    case OPCODE_BRK:
    case OPCODE_CONT:
@@ -762,7 +767,7 @@  _mesa_fprint_instruction_opt(FILE *f,
 	      _mesa_opcode_string(inst->Opcode),
 	      _mesa_condcode_string(inst->DstReg.CondMask),
 	      _mesa_swizzle_string(inst->DstReg.CondSwizzle, 0, GL_FALSE),
-	      inst->BranchTarget);
+	      branch_index(prog, inst));
       fprint_comment(f, inst);
       break;
 
@@ -777,7 +782,7 @@  _mesa_fprint_instruction_opt(FILE *f,
       }
       break;
    case OPCODE_CAL:
-      fprintf(f, "CAL %u", inst->BranchTarget);
+      fprintf(f, "CAL %u", branch_index(prog, inst));
       fprint_comment(f, inst);
       break;
    case OPCODE_RET:
@@ -850,6 +855,7 @@  _mesa_fprint_program_opt(FILE *f,
                          GLboolean lineNumbers)
 {
    GLuint i, indent = 0;
+   struct simple_node *node;
 
    switch (prog->Target) {
    case GL_VERTEX_PROGRAM_ARB:
@@ -868,11 +874,14 @@  _mesa_fprint_program_opt(FILE *f,
       fprintf(f, "# Geometry Shader\n");
    }
 
-   for (i = 0; i < prog->NumInstructions; i++) {
+   i = 0;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       if (lineNumbers)
          fprintf(f, "%3d: ", i);
-      indent = _mesa_fprint_instruction_opt(f, prog->Instructions + i,
+      indent = _mesa_fprint_instruction_opt(f, inst,
                                            indent, mode, prog);
+      i++;
    }
 }
 
diff --git a/src/mesa/program/program.c b/src/mesa/program/program.c
index b7332fc..ee6d8c0 100644
--- a/src/mesa/program/program.c
+++ b/src/mesa/program/program.c
@@ -240,6 +240,7 @@  _mesa_init_program_struct( struct gl_context *ctx, struct gl_program *prog,
       prog->Target = target;
       prog->RefCount = 1;
       prog->Format = GL_PROGRAM_FORMAT_ASCII_ARB;
+      make_empty_list(&prog->Instructions);
 
       /* default mapping from samplers to texture units */
       for (i = 0; i < MAX_SAMPLERS; i++)
@@ -371,9 +372,7 @@  _mesa_delete_program(struct gl_context *ctx, struct gl_program *prog)
    free(prog->String);
    free(prog->LocalParams);
 
-   if (prog->Instructions) {
-      _mesa_free_instructions(prog->Instructions, prog->NumInstructions);
-   }
+   _mesa_free_instructions(&prog->Instructions);
    if (prog->Parameters) {
       _mesa_free_parameter_list(prog->Parameters);
    }
@@ -483,13 +482,11 @@  _mesa_clone_program(struct gl_context *ctx, const struct gl_program *prog)
 
    clone->String = (GLubyte *) _mesa_strdup((char *) prog->String);
    clone->Format = prog->Format;
-   clone->Instructions = _mesa_alloc_instructions(prog->NumInstructions);
-   if (!clone->Instructions) {
+   if (!_mesa_copy_instructions(&clone->Instructions, &prog->Instructions)) {
       _mesa_reference_program(ctx, &clone, NULL);
       return NULL;
    }
-   _mesa_copy_instructions(clone->Instructions, prog->Instructions,
-                           prog->NumInstructions);
+
    clone->InputsRead = prog->InputsRead;
    clone->OutputsWritten = prog->OutputsWritten;
    clone->SamplersUsed = prog->SamplersUsed;
@@ -563,124 +560,32 @@  _mesa_clone_program(struct gl_context *ctx, const struct gl_program *prog)
 
 
 /**
- * Insert 'count' NOP instructions at 'start' in the given program.
- * Adjust branch targets accordingly.
- */
-GLboolean
-_mesa_insert_instructions(struct gl_program *prog, GLuint start, GLuint count)
-{
-   const GLuint origLen = prog->NumInstructions;
-   const GLuint newLen = origLen + count;
-   struct prog_instruction *newInst;
-   GLuint i;
-
-   /* adjust branches */
-   for (i = 0; i < prog->NumInstructions; i++) {
-      struct prog_instruction *inst = prog->Instructions + i;
-      if (inst->BranchTarget > 0) {
-         if ((GLuint)inst->BranchTarget >= start) {
-            inst->BranchTarget += count;
-         }
-      }
-   }
-
-   /* Alloc storage for new instructions */
-   newInst = _mesa_alloc_instructions(newLen);
-   if (!newInst) {
-      return GL_FALSE;
-   }
-
-   /* Copy 'start' instructions into new instruction buffer */
-   _mesa_copy_instructions(newInst, prog->Instructions, start);
-
-   /* init the new instructions */
-   _mesa_init_instructions(newInst + start, count);
-
-   /* Copy the remaining/tail instructions to new inst buffer */
-   _mesa_copy_instructions(newInst + start + count,
-                           prog->Instructions + start,
-                           origLen - start);
-
-   /* free old instructions */
-   _mesa_free_instructions(prog->Instructions, origLen);
-
-   /* install new instructions */
-   prog->Instructions = newInst;
-   prog->NumInstructions = newLen;
-
-   return GL_TRUE;
-}
-
-/**
- * Delete 'count' instructions at 'start' in the given program.
- * Adjust branch targets accordingly.
- */
-GLboolean
-_mesa_delete_instructions(struct gl_program *prog, GLuint start, GLuint count)
-{
-   const GLuint origLen = prog->NumInstructions;
-   const GLuint newLen = origLen - count;
-   struct prog_instruction *newInst;
-   GLuint i;
-
-   /* adjust branches */
-   for (i = 0; i < prog->NumInstructions; i++) {
-      struct prog_instruction *inst = prog->Instructions + i;
-      if (inst->BranchTarget > 0) {
-         if (inst->BranchTarget > (GLint) start) {
-            inst->BranchTarget -= count;
-         }
-      }
-   }
-
-   /* Alloc storage for new instructions */
-   newInst = _mesa_alloc_instructions(newLen);
-   if (!newInst) {
-      return GL_FALSE;
-   }
-
-   /* Copy 'start' instructions into new instruction buffer */
-   _mesa_copy_instructions(newInst, prog->Instructions, start);
-
-   /* Copy the remaining/tail instructions to new inst buffer */
-   _mesa_copy_instructions(newInst + start,
-                           prog->Instructions + start + count,
-                           newLen - start);
-
-   /* free old instructions */
-   _mesa_free_instructions(prog->Instructions, origLen);
-
-   /* install new instructions */
-   prog->Instructions = newInst;
-   prog->NumInstructions = newLen;
-
-   return GL_TRUE;
-}
-
-
-/**
  * Search instructions for registers that match (oldFile, oldIndex),
  * replacing them with (newFile, newIndex).
  */
 static void
-replace_registers(struct prog_instruction *inst, GLuint numInst,
+replace_registers(struct simple_node *list,
                   GLuint oldFile, GLuint oldIndex,
                   GLuint newFile, GLuint newIndex)
 {
-   GLuint i, j;
-   for (i = 0; i < numInst; i++) {
+   GLuint i;
+   struct simple_node *node;
+
+   foreach(node, list) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
+
       /* src regs */
-      for (j = 0; j < _mesa_num_inst_src_regs(inst[i].Opcode); j++) {
-         if (inst[i].SrcReg[j].File == oldFile &&
-             inst[i].SrcReg[j].Index == oldIndex) {
-            inst[i].SrcReg[j].File = newFile;
-            inst[i].SrcReg[j].Index = newIndex;
+      for (i = 0; i < _mesa_num_inst_src_regs(inst->Opcode); i++) {
+         if (inst->SrcReg[i].File == oldFile &&
+             inst->SrcReg[i].Index == oldIndex) {
+            inst->SrcReg[i].File = newFile;
+            inst->SrcReg[i].Index = newIndex;
          }
       }
       /* dst reg */
-      if (inst[i].DstReg.File == oldFile && inst[i].DstReg.Index == oldIndex) {
-         inst[i].DstReg.File = newFile;
-         inst[i].DstReg.Index = newIndex;
+      if (inst->DstReg.File == oldFile && inst->DstReg.Index == oldIndex) {
+         inst->DstReg.File = newFile;
+         inst->DstReg.Index = newIndex;
       }
    }
 }
@@ -692,17 +597,20 @@  replace_registers(struct prog_instruction *inst, GLuint numInst,
  * Used when combining programs.
  */
 static void
-adjust_param_indexes(struct prog_instruction *inst, GLuint numInst,
-                     GLuint offset)
+adjust_param_indexes(struct simple_node *list, GLuint offset)
 {
-   GLuint i, j;
-   for (i = 0; i < numInst; i++) {
-      for (j = 0; j < _mesa_num_inst_src_regs(inst[i].Opcode); j++) {
-         GLuint f = inst[i].SrcReg[j].File;
+   GLuint i;
+   struct simple_node *node;
+
+   foreach(node, list) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
+
+      for (i = 0; i < _mesa_num_inst_src_regs(inst->Opcode); i++) {
+         GLuint f = inst->SrcReg->File;
          if (f == PROGRAM_CONSTANT ||
              f == PROGRAM_UNIFORM ||
              f == PROGRAM_STATE_VAR) {
-            inst[i].SrcReg[j].Index += offset;
+            inst->SrcReg->Index += offset;
          }
       }
    }
@@ -718,7 +626,6 @@  _mesa_combine_programs(struct gl_context *ctx,
                        const struct gl_program *progA,
                        const struct gl_program *progB)
 {
-   struct prog_instruction *newInst;
    struct gl_program *newProg;
    const GLuint lenA = progA->NumInstructions - 1; /* omit END instr */
    const GLuint lenB = progB->NumInstructions;
@@ -728,25 +635,19 @@  _mesa_combine_programs(struct gl_context *ctx,
    GLuint firstTemp = 0;
    GLbitfield64 inputsB;
    GLuint i;
+   struct simple_node progA_copy, progB_copy, *node, *node_temp;
 
    ASSERT(progA->Target == progB->Target);
 
-   newInst = _mesa_alloc_instructions(newLength);
-   if (!newInst)
-      return GL_FALSE;
-
-   _mesa_copy_instructions(newInst, progA->Instructions, lenA);
-   _mesa_copy_instructions(newInst + lenA, progB->Instructions, lenB);
-
-   /* adjust branch / instruction addresses for B's instructions */
-   for (i = 0; i < lenB; i++) {
-      newInst[lenA + i].BranchTarget += lenA;
-   }
-
    newProg = ctx->Driver.NewProgram(ctx, progA->Target, 0);
-   newProg->Instructions = newInst;
+   make_empty_list(&newProg->Instructions);
    newProg->NumInstructions = newLength;
 
+   make_empty_list(&progA_copy);
+   make_empty_list(&progB_copy);
+   _mesa_copy_instructions(&progA_copy, &progA->Instructions);
+   _mesa_copy_instructions(&progB_copy, &progB->Instructions);
+
    /* find used temp regs (we may need new temps below) */
    _mesa_find_used_registers(newProg, PROGRAM_TEMPORARY,
                              usedTemps, MAX_PROGRAM_TEMPS);
@@ -806,11 +707,11 @@  _mesa_combine_programs(struct gl_context *ctx,
          firstTemp = tempReg + 1;
 
          /* replace writes to result.color[0] with tempReg */
-         replace_registers(newInst, lenA,
+         replace_registers(&progA_copy,
                            PROGRAM_OUTPUT, FRAG_RESULT_COLOR,
                            PROGRAM_TEMPORARY, tempReg);
          /* replace reads from the input color with tempReg */
-         replace_registers(newInst + lenA, lenB,
+         replace_registers(&progB_copy,
                            progB_colorFile, progB_colorIndex, /* search for */
                            PROGRAM_TEMPORARY, tempReg  /* replace with */ );
       }
@@ -835,8 +736,16 @@  _mesa_combine_programs(struct gl_context *ctx,
    newProg->Parameters = _mesa_combine_parameter_lists(progA->Parameters,
                                                        progB->Parameters);
 
-   adjust_param_indexes(newInst + lenA, lenB, numParamsA);
+   adjust_param_indexes(&progB_copy, numParamsA);
+
+   move_list(&newProg->Instructions, &progA_copy);
 
+   foreach_s(node, node_temp, &progB_copy) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
+
+      remove_from_list(&inst->link);
+      insert_at_tail(&newProg->Instructions, &inst->link);
+   }
 
    return newProg;
 }
@@ -854,12 +763,13 @@  _mesa_find_used_registers(const struct gl_program *prog,
                           gl_register_file file,
                           GLboolean used[], GLuint usedSize)
 {
-   GLuint i, j;
+   struct simple_node *node;
+   GLuint j;
 
    memset(used, 0, usedSize);
 
-   for (i = 0; i < prog->NumInstructions; i++) {
-      const struct prog_instruction *inst = prog->Instructions + i;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       const GLuint n = _mesa_num_inst_src_regs(inst->Opcode);
 
       if (inst->DstReg.File == file) {
@@ -988,16 +898,16 @@  void
 _mesa_postprocess_program(struct gl_context *ctx, struct gl_program *prog)
 {
    static const GLfloat white[4] = { 0.5, 0.5, 0.5, 0.5 };
-   GLuint i;
    GLuint whiteSwizzle;
    GLint whiteIndex = _mesa_add_unnamed_constant(prog->Parameters,
                                                  (gl_constant_value *) white,
                                                  4, &whiteSwizzle);
+   struct simple_node *node;
 
    (void) whiteIndex;
 
-   for (i = 0; i < prog->NumInstructions; i++) {
-      struct prog_instruction *inst = prog->Instructions + i;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       const GLuint n = _mesa_num_inst_src_regs(inst->Opcode);
 
       (void) n;
@@ -1077,3 +987,29 @@  _mesa_get_min_invocations_per_fragment(struct gl_context *ctx,
    }
    return 1;
 }
+
+/**
+ * Inserts an instruction at the end of a struct gl_program.
+ *
+ * If there is an OPCODE_END already present, then it inserts the new thing
+ * before OPCODE_END.  If there is no OPCODE_END, then it's just inserted at
+ * the end of the program.
+ */
+void
+_mesa_append_instruction(struct gl_program *prog, struct prog_instruction *inst)
+{
+   struct simple_node *list = &prog->Instructions;
+   struct simple_node *end_node = last_elem(list);
+   struct prog_instruction *end = (struct prog_instruction *)end_node;
+
+   if (!inst)
+      return;
+
+   if (!is_empty_list(list) && end->Opcode == OPCODE_END) {
+      insert_at_tail(&end->link, &inst->link);
+   } else {
+      insert_at_tail(list, &inst->link);
+   }
+
+   prog->NumInstructions++;
+}
diff --git a/src/mesa/program/program.h b/src/mesa/program/program.h
index ef69824..20f61cf 100644
--- a/src/mesa/program/program.h
+++ b/src/mesa/program/program.h
@@ -63,6 +63,9 @@  _mesa_update_default_objects_program(struct gl_context *ctx);
 extern void
 _mesa_set_program_error(struct gl_context *ctx, GLint pos, const char *string);
 
+extern void
+_mesa_append_instruction(struct gl_program *prog, struct prog_instruction *inst);
+
 extern const GLubyte *
 _mesa_find_line_column(const GLubyte *string, const GLubyte *pos,
                        GLint *line, GLint *col);
@@ -162,13 +165,6 @@  _mesa_clone_fragment_program(struct gl_context *ctx,
    return (struct gl_fragment_program *) _mesa_clone_program(ctx, &prog->Base);
 }
 
-
-extern  GLboolean
-_mesa_insert_instructions(struct gl_program *prog, GLuint start, GLuint count);
-
-extern  GLboolean
-_mesa_delete_instructions(struct gl_program *prog, GLuint start, GLuint count);
-
 extern struct gl_program *
 _mesa_combine_programs(struct gl_context *ctx,
                        const struct gl_program *progA,
diff --git a/src/mesa/program/program_parse.y b/src/mesa/program/program_parse.y
index f6ec7e5..d4263cb 100644
--- a/src/mesa/program/program_parse.y
+++ b/src/mesa/program/program_parse.y
@@ -2282,13 +2282,11 @@  asm_instruction_ctor(gl_inst_opcode op,
    struct asm_instruction *inst = CALLOC_STRUCT(asm_instruction);
 
    if (inst) {
-      inst->Base = _mesa_alloc_instructions(1);
+      inst->Base = _mesa_alloc_instruction(op);
       if (!inst->Base) {
          free(inst);
          return NULL;
       }
-      _mesa_init_instructions(inst->Base, 1);
-      inst->Base->Opcode = op;
 
       asm_instruction_set_operands(inst, dst, src0, src1, src2);
    }
@@ -2307,13 +2305,11 @@  asm_instruction_copy_ctor(const struct prog_instruction *base,
    struct asm_instruction *inst = CALLOC_STRUCT(asm_instruction);
 
    if (inst) {
-      inst->Base = _mesa_alloc_instructions(1);
+      inst->Base = _mesa_alloc_instruction(base->Opcode);
       if (!inst->Base) {
          free(inst);
          return NULL;
       }
-      _mesa_init_instructions(inst->Base, 1);
-      inst->Base->Opcode = base->Opcode;
       inst->Base->CondUpdate = base->CondUpdate;
       inst->Base->CondDst = base->CondDst;
       inst->Base->SaturateMode = base->SaturateMode;
@@ -2691,8 +2687,8 @@  GLboolean
 _mesa_parse_arb_program(struct gl_context *ctx, GLenum target, const GLubyte *str,
 			GLsizei len, struct asm_parser_state *state)
 {
-   struct asm_instruction *inst;
-   unsigned i;
+   struct prog_instruction *inst;
+   struct asm_instruction *asm_inst;
    GLubyte *strz;
    GLboolean result = GL_FALSE;
    void *temp;
@@ -2753,32 +2749,18 @@  _mesa_parse_arb_program(struct gl_context *ctx, GLenum target, const GLubyte *st
       goto error;
    }
 
-
-   
-   /* Add one instruction to store the "END" instruction.
-    */
-   state->prog->Instructions =
-      _mesa_alloc_instructions(state->prog->NumInstructions + 1);
-
-   if (state->prog->Instructions == NULL) {
-      goto error;
-   }
-
-   inst = state->inst_head;
-   for (i = 0; i < state->prog->NumInstructions; i++) {
-      struct asm_instruction *const temp = inst->next;
-
-      state->prog->Instructions[i] = *inst->Base;
-      inst = temp;
+   /* Copy the assembled instructions to the program. */
+   state->prog->NumInstructions = 0;
+   make_empty_list(&state->prog->Instructions);
+   for (asm_inst = state->inst_head; asm_inst; asm_inst = asm_inst->next) {
+      _mesa_append_instruction(state->prog, asm_inst->Base);
    }
 
    /* Finally, tag on an OPCODE_END instruction */
-   {
-      const GLuint numInst = state->prog->NumInstructions;
-      _mesa_init_instructions(state->prog->Instructions + numInst, 1);
-      state->prog->Instructions[numInst].Opcode = OPCODE_END;
-   }
-   state->prog->NumInstructions++;
+   inst = _mesa_alloc_instruction(OPCODE_END);
+   if (!inst)
+      goto error;
+   _mesa_append_instruction(state->prog, inst);
 
    state->prog->NumParameters = state->prog->Parameters->NumParameters;
    state->prog->NumAttributes = _mesa_bitcount_64(state->prog->InputsRead);
@@ -2796,10 +2778,9 @@  _mesa_parse_arb_program(struct gl_context *ctx, GLenum target, const GLubyte *st
    result = GL_TRUE;
 
 error:
-   for (inst = state->inst_head; inst != NULL; inst = temp) {
-      temp = inst->next;
-      _mesa_free_instructions(inst->Base, 1);
-      free(inst);
+   for (asm_inst = state->inst_head; asm_inst != NULL; asm_inst = temp) {
+      temp = asm_inst->next;
+      free(asm_inst);
    }
 
    state->inst_head = NULL;
diff --git a/src/mesa/program/programopt.c b/src/mesa/program/programopt.c
index bcc0b75..98ad632 100644
--- a/src/mesa/program/programopt.c
+++ b/src/mesa/program/programopt.c
@@ -39,6 +39,23 @@ 
 #include "programopt.h"
 #include "prog_instruction.h"
 
+/**
+ * Inserts a new prog_instruction just before the OPCODE_END of the program's
+ * list of instructions.
+ */
+static void
+insert_at_end(struct gl_program *prog, struct prog_instruction *inst)
+{
+   struct simple_node *list = &prog->Instructions;
+   struct prog_instruction *end = (struct prog_instruction *)last_elem(list);
+   assert(end->Opcode == OPCODE_END);
+
+   if (!inst)
+      return;
+
+   insert_at_tail(&end->link, &inst->link);
+   prog->NumInstructions++;
+}
 
 /**
  * This function inserts instructions for coordinate modelview * projection
@@ -48,9 +65,8 @@ 
 static void
 _mesa_insert_mvp_dp4_code(struct gl_context *ctx, struct gl_vertex_program *vprog)
 {
+   struct gl_program *prog = &vprog->Base;
    struct prog_instruction *newInst;
-   const GLuint origLen = vprog->Base.NumInstructions;
-   const GLuint newLen = origLen + 4;
    GLuint i;
 
    /* Set up state references for the modelview/projection matrix. */
@@ -67,14 +83,6 @@  _mesa_insert_mvp_dp4_code(struct gl_context *ctx, struct gl_vertex_program *vpro
                                             mvpState[i]);
    }
 
-   /* Alloc storage for new instructions */
-   newInst = _mesa_alloc_instructions(newLen);
-   if (!newInst) {
-      _mesa_error(ctx, GL_OUT_OF_MEMORY,
-                  "glProgramString(inserting position_invariant code)");
-      return;
-   }
-
    /*
     * Generated instructions:
     * newInst[0] = DP4 result.position.x, mvp.row[0], vertex.position;
@@ -82,38 +90,36 @@  _mesa_insert_mvp_dp4_code(struct gl_context *ctx, struct gl_vertex_program *vpro
     * newInst[2] = DP4 result.position.z, mvp.row[2], vertex.position;
     * newInst[3] = DP4 result.position.w, mvp.row[3], vertex.position;
     */
-   _mesa_init_instructions(newInst, 4);
    for (i = 0; i < 4; i++) {
-      newInst[i].Opcode = OPCODE_DP4;
-      newInst[i].DstReg.File = PROGRAM_OUTPUT;
-      newInst[i].DstReg.Index = VARYING_SLOT_POS;
-      newInst[i].DstReg.WriteMask = (WRITEMASK_X << i);
-      newInst[i].SrcReg[0].File = PROGRAM_STATE_VAR;
-      newInst[i].SrcReg[0].Index = mvpRef[i];
-      newInst[i].SrcReg[1].File = PROGRAM_INPUT;
-      newInst[i].SrcReg[1].Index = VERT_ATTRIB_POS;
+      newInst = _mesa_alloc_instruction(OPCODE_DP4);
+      if (!newInst)
+         goto fail;
+      newInst->DstReg.File = PROGRAM_OUTPUT;
+      newInst->DstReg.Index = VARYING_SLOT_POS;
+      newInst->DstReg.WriteMask = (WRITEMASK_X << i);
+      newInst->SrcReg[0].File = PROGRAM_STATE_VAR;
+      newInst->SrcReg[0].Index = mvpRef[i];
+      newInst->SrcReg[1].File = PROGRAM_INPUT;
+      newInst->SrcReg[1].Index = VERT_ATTRIB_POS;
+      insert_at_end(prog, newInst);
    }
 
-   /* Append original instructions after new instructions */
-   _mesa_copy_instructions (newInst + 4, vprog->Base.Instructions, origLen);
-
-   /* free old instructions */
-   _mesa_free_instructions(vprog->Base.Instructions, origLen);
-
-   /* install new instructions */
-   vprog->Base.Instructions = newInst;
-   vprog->Base.NumInstructions = newLen;
    vprog->Base.InputsRead |= VERT_BIT_POS;
    vprog->Base.OutputsWritten |= BITFIELD64_BIT(VARYING_SLOT_POS);
+
+   return;
+
+fail:
+   _mesa_error(ctx, GL_OUT_OF_MEMORY,
+               "glProgramString(inserting position_invariant code)");
 }
 
 
 static void
 _mesa_insert_mvp_mad_code(struct gl_context *ctx, struct gl_vertex_program *vprog)
 {
+   struct gl_program *prog = &vprog->Base;
    struct prog_instruction *newInst;
-   const GLuint origLen = vprog->Base.NumInstructions;
-   const GLuint newLen = origLen + 4;
    GLuint hposTemp;
    GLuint i;
 
@@ -131,14 +137,6 @@  _mesa_insert_mvp_mad_code(struct gl_context *ctx, struct gl_vertex_program *vpro
                                             mvpState[i]);
    }
 
-   /* Alloc storage for new instructions */
-   newInst = _mesa_alloc_instructions(newLen);
-   if (!newInst) {
-      _mesa_error(ctx, GL_OUT_OF_MEMORY,
-                  "glProgramString(inserting position_invariant code)");
-      return;
-   }
-
    /* TEMP hposTemp; */
    hposTemp = vprog->Base.NumTemporaries++;
 
@@ -149,53 +147,58 @@  _mesa_insert_mvp_mad_code(struct gl_context *ctx, struct gl_vertex_program *vpro
     *    emit_op3(p, OPCODE_MAD, tmp, 0, swizzle1(src,Z), mat[2], tmp);
     *    emit_op3(p, OPCODE_MAD, dest, 0, swizzle1(src,W), mat[3], tmp);
     */
-   _mesa_init_instructions(newInst, 4);
 
-   newInst[0].Opcode = OPCODE_MUL;
-   newInst[0].DstReg.File = PROGRAM_TEMPORARY;
-   newInst[0].DstReg.Index = hposTemp;
-   newInst[0].SrcReg[0].File = PROGRAM_INPUT;
-   newInst[0].SrcReg[0].Index = VERT_ATTRIB_POS;
-   newInst[0].SrcReg[0].Swizzle = SWIZZLE_XXXX;
-   newInst[0].SrcReg[1].File = PROGRAM_STATE_VAR;
-   newInst[0].SrcReg[1].Index = mvpRef[0];
+   newInst = _mesa_alloc_instruction(OPCODE_MUL);
+   if (!newInst)
+      goto fail;
+   newInst->DstReg.File = PROGRAM_TEMPORARY;
+   newInst->DstReg.Index = hposTemp;
+   newInst->SrcReg[0].File = PROGRAM_INPUT;
+   newInst->SrcReg[0].Index = VERT_ATTRIB_POS;
+   newInst->SrcReg[0].Swizzle = SWIZZLE_XXXX;
+   newInst->SrcReg[1].File = PROGRAM_STATE_VAR;
+   newInst->SrcReg[1].Index = mvpRef[0];
+   insert_at_end(prog, newInst);
 
    for (i = 1; i <= 2; i++) {
-      newInst[i].Opcode = OPCODE_MAD;
-      newInst[i].DstReg.File = PROGRAM_TEMPORARY;
-      newInst[i].DstReg.Index = hposTemp;
-      newInst[i].SrcReg[0].File = PROGRAM_INPUT;
-      newInst[i].SrcReg[0].Index = VERT_ATTRIB_POS;
-      newInst[i].SrcReg[0].Swizzle = MAKE_SWIZZLE4(i,i,i,i);
-      newInst[i].SrcReg[1].File = PROGRAM_STATE_VAR;
-      newInst[i].SrcReg[1].Index = mvpRef[i];
-      newInst[i].SrcReg[2].File = PROGRAM_TEMPORARY;
-      newInst[i].SrcReg[2].Index = hposTemp;
+      newInst = _mesa_alloc_instruction(OPCODE_MAD);
+      if (!newInst)
+         goto fail;
+      newInst->DstReg.File = PROGRAM_TEMPORARY;
+      newInst->DstReg.Index = hposTemp;
+      newInst->SrcReg[0].File = PROGRAM_INPUT;
+      newInst->SrcReg[0].Index = VERT_ATTRIB_POS;
+      newInst->SrcReg[0].Swizzle = MAKE_SWIZZLE4(i,i,i,i);
+      newInst->SrcReg[1].File = PROGRAM_STATE_VAR;
+      newInst->SrcReg[1].Index = mvpRef[i];
+      newInst->SrcReg[2].File = PROGRAM_TEMPORARY;
+      newInst->SrcReg[2].Index = hposTemp;
+      insert_at_end(prog, newInst);
    }
 
-   newInst[3].Opcode = OPCODE_MAD;
-   newInst[3].DstReg.File = PROGRAM_OUTPUT;
-   newInst[3].DstReg.Index = VARYING_SLOT_POS;
-   newInst[3].SrcReg[0].File = PROGRAM_INPUT;
-   newInst[3].SrcReg[0].Index = VERT_ATTRIB_POS;
-   newInst[3].SrcReg[0].Swizzle = SWIZZLE_WWWW;
-   newInst[3].SrcReg[1].File = PROGRAM_STATE_VAR;
-   newInst[3].SrcReg[1].Index = mvpRef[3];
-   newInst[3].SrcReg[2].File = PROGRAM_TEMPORARY;
-   newInst[3].SrcReg[2].Index = hposTemp;
-
-
-   /* Append original instructions after new instructions */
-   _mesa_copy_instructions (newInst + 4, vprog->Base.Instructions, origLen);
-
-   /* free old instructions */
-   _mesa_free_instructions(vprog->Base.Instructions, origLen);
+   newInst = _mesa_alloc_instruction(OPCODE_MAD);
+   if (!newInst)
+      goto fail;
+   newInst->DstReg.File = PROGRAM_OUTPUT;
+   newInst->DstReg.Index = VARYING_SLOT_POS;
+   newInst->SrcReg[0].File = PROGRAM_INPUT;
+   newInst->SrcReg[0].Index = VERT_ATTRIB_POS;
+   newInst->SrcReg[0].Swizzle = SWIZZLE_WWWW;
+   newInst->SrcReg[1].File = PROGRAM_STATE_VAR;
+   newInst->SrcReg[1].Index = mvpRef[3];
+   newInst->SrcReg[2].File = PROGRAM_TEMPORARY;
+   newInst->SrcReg[2].Index = hposTemp;
+   insert_at_end(prog, newInst);
 
    /* install new instructions */
-   vprog->Base.Instructions = newInst;
-   vprog->Base.NumInstructions = newLen;
    vprog->Base.InputsRead |= VERT_BIT_POS;
    vprog->Base.OutputsWritten |= BITFIELD64_BIT(VARYING_SLOT_POS);
+
+   return;
+
+fail:
+   _mesa_error(ctx, GL_OUT_OF_MEMORY,
+               "glProgramString(inserting position_invariant code)");
 }
 
 
@@ -238,12 +241,11 @@  _mesa_append_fog_code(struct gl_context *ctx,
       = { STATE_INTERNAL, STATE_FOG_PARAMS_OPTIMIZED, 0, 0, 0 };
    static const gl_state_index fogColorState[STATE_LENGTH]
       = { STATE_FOG_COLOR, 0, 0, 0, 0};
-   struct prog_instruction *newInst, *inst;
-   const GLuint origLen = fprog->Base.NumInstructions;
-   const GLuint newLen = origLen + 5;
-   GLuint i;
+   struct gl_program *prog = &fprog->Base;
+   struct prog_instruction *inst;
    GLint fogPRefOpt, fogColorRef; /* state references */
    GLuint colorTemp, fogFactorTemp; /* temporary registerss */
+   struct simple_node *node;
 
    if (fog_mode == GL_NONE) {
       _mesa_problem(ctx, "_mesa_append_fog_code() called for fragment program"
@@ -256,17 +258,6 @@  _mesa_append_fog_code(struct gl_context *ctx,
       return;
    }
 
-   /* Alloc storage for new instructions */
-   newInst = _mesa_alloc_instructions(newLen);
-   if (!newInst) {
-      _mesa_error(ctx, GL_OUT_OF_MEMORY,
-                  "glProgramString(inserting fog_option code)");
-      return;
-   }
-
-   /* Copy orig instructions into new instruction buffer */
-   _mesa_copy_instructions(newInst, fprog->Base.Instructions, origLen);
-
    /* PARAM fogParamsRefOpt = internal optimized fog params; */
    fogPRefOpt
       = _mesa_add_state_reference(fprog->Base.Parameters, fogPStateOpt);
@@ -280,10 +271,9 @@  _mesa_append_fog_code(struct gl_context *ctx,
    fogFactorTemp = fprog->Base.NumTemporaries++;
 
    /* Scan program to find where result.color is written */
-   inst = newInst;
-   for (i = 0; i < fprog->Base.NumInstructions; i++) {
-      if (inst->Opcode == OPCODE_END)
-         break;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
+
       if (inst->DstReg.File == PROGRAM_OUTPUT &&
           inst->DstReg.Index == FRAG_RESULT_COLOR) {
          /* change the instruction to write to colorTemp w/ clamping */
@@ -292,17 +282,15 @@  _mesa_append_fog_code(struct gl_context *ctx,
          inst->SaturateMode = saturate;
          /* don't break (may be several writes to result.color) */
       }
-      inst++;
    }
-   assert(inst->Opcode == OPCODE_END); /* we'll overwrite this inst */
-
-   _mesa_init_instructions(inst, 5);
 
    /* emit instructions to compute fog blending factor */
    /* this is always clamped to [0, 1] regardless of fragment clamping */
    if (fog_mode == GL_LINEAR) {
       /* MAD fogFactorTemp.x, fragment.fogcoord.x, fogPRefOpt.x, fogPRefOpt.y; */
-      inst->Opcode = OPCODE_MAD;
+      inst = _mesa_alloc_instruction(OPCODE_MAD);
+      if (!inst)
+         goto fail;
       inst->DstReg.File = PROGRAM_TEMPORARY;
       inst->DstReg.Index = fogFactorTemp;
       inst->DstReg.WriteMask = WRITEMASK_X;
@@ -316,14 +304,16 @@  _mesa_append_fog_code(struct gl_context *ctx,
       inst->SrcReg[2].Index = fogPRefOpt;
       inst->SrcReg[2].Swizzle = SWIZZLE_YYYY;
       inst->SaturateMode = SATURATE_ZERO_ONE;
-      inst++;
+      insert_at_end(prog, inst);
    }
    else {
       ASSERT(fog_mode == GL_EXP || fog_mode == GL_EXP2);
       /* fogPRefOpt.z = d/ln(2), fogPRefOpt.w = d/sqrt(ln(2) */
       /* EXP: MUL fogFactorTemp.x, fogPRefOpt.z, fragment.fogcoord.x; */
       /* EXP2: MUL fogFactorTemp.x, fogPRefOpt.w, fragment.fogcoord.x; */
-      inst->Opcode = OPCODE_MUL;
+      inst = _mesa_alloc_instruction(OPCODE_MUL);
+      if (!inst)
+         goto fail;
       inst->DstReg.File = PROGRAM_TEMPORARY;
       inst->DstReg.Index = fogFactorTemp;
       inst->DstReg.WriteMask = WRITEMASK_X;
@@ -334,10 +324,13 @@  _mesa_append_fog_code(struct gl_context *ctx,
       inst->SrcReg[1].File = PROGRAM_INPUT;
       inst->SrcReg[1].Index = VARYING_SLOT_FOGC;
       inst->SrcReg[1].Swizzle = SWIZZLE_XXXX;
-      inst++;
+      insert_at_end(prog, inst);
+
       if (fog_mode == GL_EXP2) {
          /* MUL fogFactorTemp.x, fogFactorTemp.x, fogFactorTemp.x; */
-         inst->Opcode = OPCODE_MUL;
+         inst = _mesa_alloc_instruction(OPCODE_MUL);
+         if (!inst)
+            goto fail;
          inst->DstReg.File = PROGRAM_TEMPORARY;
          inst->DstReg.Index = fogFactorTemp;
          inst->DstReg.WriteMask = WRITEMASK_X;
@@ -347,10 +340,13 @@  _mesa_append_fog_code(struct gl_context *ctx,
          inst->SrcReg[1].File = PROGRAM_TEMPORARY;
          inst->SrcReg[1].Index = fogFactorTemp;
          inst->SrcReg[1].Swizzle = SWIZZLE_XXXX;
-         inst++;
+         insert_at_end(prog, inst);
       }
+
       /* EX2_SAT fogFactorTemp.x, -fogFactorTemp.x; */
-      inst->Opcode = OPCODE_EX2;
+      inst = _mesa_alloc_instruction(OPCODE_EX2);
+      if (!inst)
+         goto fail;
       inst->DstReg.File = PROGRAM_TEMPORARY;
       inst->DstReg.Index = fogFactorTemp;
       inst->DstReg.WriteMask = WRITEMASK_X;
@@ -359,10 +355,13 @@  _mesa_append_fog_code(struct gl_context *ctx,
       inst->SrcReg[0].Negate = NEGATE_XYZW;
       inst->SrcReg[0].Swizzle = SWIZZLE_XXXX;
       inst->SaturateMode = SATURATE_ZERO_ONE;
-      inst++;
+      insert_at_end(prog, inst);
    }
+
    /* LRP result.color.xyz, fogFactorTemp.xxxx, colorTemp, fogColorRef; */
-   inst->Opcode = OPCODE_LRP;
+   inst = _mesa_alloc_instruction(OPCODE_LRP);
+   if (!inst)
+      goto fail;
    inst->DstReg.File = PROGRAM_OUTPUT;
    inst->DstReg.Index = FRAG_RESULT_COLOR;
    inst->DstReg.WriteMask = WRITEMASK_XYZ;
@@ -375,28 +374,27 @@  _mesa_append_fog_code(struct gl_context *ctx,
    inst->SrcReg[2].File = PROGRAM_STATE_VAR;
    inst->SrcReg[2].Index = fogColorRef;
    inst->SrcReg[2].Swizzle = SWIZZLE_NOOP;
-   inst++;
+   insert_at_end(prog, inst);
+
    /* MOV result.color.w, colorTemp.x;  # copy alpha */
-   inst->Opcode = OPCODE_MOV;
+   inst = _mesa_alloc_instruction(OPCODE_MOV);
+   if (!inst)
+      goto fail;
    inst->DstReg.File = PROGRAM_OUTPUT;
    inst->DstReg.Index = FRAG_RESULT_COLOR;
    inst->DstReg.WriteMask = WRITEMASK_W;
    inst->SrcReg[0].File = PROGRAM_TEMPORARY;
    inst->SrcReg[0].Index = colorTemp;
    inst->SrcReg[0].Swizzle = SWIZZLE_NOOP;
-   inst++;
-   /* END; */
-   inst->Opcode = OPCODE_END;
-   inst++;
-
-   /* free old instructions */
-   _mesa_free_instructions(fprog->Base.Instructions, origLen);
+   insert_at_end(prog, inst);
 
-   /* install new instructions */
-   fprog->Base.Instructions = newInst;
-   fprog->Base.NumInstructions = inst - newInst;
    fprog->Base.InputsRead |= VARYING_BIT_FOGC;
    assert(fprog->Base.OutputsWritten & (1 << FRAG_RESULT_COLOR));
+   return;
+
+fail:
+   _mesa_error(ctx, GL_OUT_OF_MEMORY,
+               "glProgramString(inserting fog_option code)");
 }
 
 
@@ -431,10 +429,10 @@  _mesa_count_texture_indirections(struct gl_program *prog)
    GLuint indirections = 1;
    GLbitfield tempsOutput = 0x0;
    GLbitfield aluTemps = 0x0;
-   GLuint i;
+   struct simple_node *node;
 
-   for (i = 0; i < prog->NumInstructions; i++) {
-      const struct prog_instruction *inst = prog->Instructions + i;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
 
       if (is_texture_instruction(inst)) {
          if (((inst->SrcReg[0].File == PROGRAM_TEMPORARY) && 
@@ -473,10 +471,12 @@  _mesa_count_texture_indirections(struct gl_program *prog)
 void
 _mesa_count_texture_instructions(struct gl_program *prog)
 {
-   GLuint i;
+   struct simple_node *node;
+
    prog->NumTexInstructions = 0;
-   for (i = 0; i < prog->NumInstructions; i++) {
-      prog->NumTexInstructions += is_texture_instruction(prog->Instructions + i);
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
+      prog->NumTexInstructions += is_texture_instruction(inst);
    }
 }
 
@@ -495,6 +495,7 @@  _mesa_remove_output_reads(struct gl_program *prog, gl_register_file type)
    GLuint numVaryingReads = 0;
    GLboolean usedTemps[MAX_PROGRAM_TEMPS];
    GLuint firstTemp = 0;
+   struct simple_node *node;
 
    _mesa_find_used_registers(prog, PROGRAM_TEMPORARY,
                              usedTemps, MAX_PROGRAM_TEMPS);
@@ -505,8 +506,8 @@  _mesa_remove_output_reads(struct gl_program *prog, gl_register_file type)
       outputMap[i] = -1;
 
    /* look for instructions which read from varying vars */
-   for (i = 0; i < prog->NumInstructions; i++) {
-      struct prog_instruction *inst = prog->Instructions + i;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
       GLuint j;
       for (j = 0; j < numSrc; j++) {
@@ -530,8 +531,8 @@  _mesa_remove_output_reads(struct gl_program *prog, gl_register_file type)
       return; /* nothing to be done */
 
    /* look for instructions which write to the varying vars identified above */
-   for (i = 0; i < prog->NumInstructions; i++) {
-      struct prog_instruction *inst = prog->Instructions + i;
+   foreach(node, &prog->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
       if (inst->DstReg.File == type &&
           outputMap[inst->DstReg.Index] >= 0) {
          /* change inst to write to the temp reg, instead of the varying */
@@ -543,32 +544,22 @@  _mesa_remove_output_reads(struct gl_program *prog, gl_register_file type)
    /* insert new instructions to copy the temp vars to the varying vars */
    {
       struct prog_instruction *inst;
-      GLint endPos, var;
-
-      /* Look for END instruction and insert the new varying writes */
-      endPos = -1;
-      for (i = 0; i < prog->NumInstructions; i++) {
-         struct prog_instruction *inst = prog->Instructions + i;
-         if (inst->Opcode == OPCODE_END) {
-            endPos = i;
-            _mesa_insert_instructions(prog, i, numVaryingReads);
-            break;
-         }
-      }
-
-      assert(endPos >= 0);
+      GLint var;
 
       /* insert new MOV instructions here */
-      inst = prog->Instructions + endPos;
       for (var = 0; var < VARYING_SLOT_MAX; var++) {
          if (outputMap[var] >= 0) {
             /* MOV VAR[var], TEMP[tmp]; */
-            inst->Opcode = OPCODE_MOV;
+            inst = _mesa_alloc_instruction(OPCODE_MOV);
+            if (!inst) {
+               _mesa_error(NULL, GL_OUT_OF_MEMORY, __FUNCTION__);
+               return;
+            }
             inst->DstReg.File = type;
             inst->DstReg.Index = var;
             inst->SrcReg[0].File = PROGRAM_TEMPORARY;
             inst->SrcReg[0].Index = outputMap[var];
-            inst++;
+            insert_at_end(prog, inst);
          }
       }
    }
@@ -587,33 +578,34 @@  _mesa_nop_fragment_program(struct gl_context *ctx, struct gl_fragment_program *p
    struct prog_instruction *inst;
    GLuint inputAttr;
 
-   inst = _mesa_alloc_instructions(2);
-   if (!inst) {
-      _mesa_error(ctx, GL_OUT_OF_MEMORY, "_mesa_nop_fragment_program");
-      return;
-   }
+   _mesa_free_instructions(&prog->Base.Instructions);
+   prog->Base.NumInstructions = 0;
 
-   _mesa_init_instructions(inst, 2);
-
-   inst[0].Opcode = OPCODE_MOV;
-   inst[0].DstReg.File = PROGRAM_OUTPUT;
-   inst[0].DstReg.Index = FRAG_RESULT_COLOR;
-   inst[0].SrcReg[0].File = PROGRAM_INPUT;
+   inst = _mesa_alloc_instruction(OPCODE_MOV);
+   if (!inst)
+      goto fail;
+   inst->DstReg.File = PROGRAM_OUTPUT;
+   inst->DstReg.Index = FRAG_RESULT_COLOR;
+   inst->SrcReg[0].File = PROGRAM_INPUT;
    if (prog->Base.InputsRead & VARYING_BIT_COL0)
       inputAttr = VARYING_SLOT_COL0;
    else
       inputAttr = VARYING_SLOT_TEX0;
-   inst[0].SrcReg[0].Index = inputAttr;
-
-   inst[1].Opcode = OPCODE_END;
+   inst->SrcReg[0].Index = inputAttr;
+   insert_at_end(&prog->Base, inst);
 
-   _mesa_free_instructions(prog->Base.Instructions,
-                           prog->Base.NumInstructions);
+   inst = _mesa_alloc_instruction(OPCODE_END);
+   if (!inst)
+      goto fail;
+   insert_at_end(&prog->Base, inst);
 
-   prog->Base.Instructions = inst;
-   prog->Base.NumInstructions = 2;
    prog->Base.InputsRead = BITFIELD64_BIT(inputAttr);
    prog->Base.OutputsWritten = BITFIELD64_BIT(FRAG_RESULT_COLOR);
+   return;
+
+fail:
+   _mesa_error(ctx, GL_OUT_OF_MEMORY, __FUNCTION__);
+   return;
 }
 
 
@@ -628,34 +620,30 @@  _mesa_nop_vertex_program(struct gl_context *ctx, struct gl_vertex_program *prog)
    struct prog_instruction *inst;
    GLuint inputAttr;
 
+   _mesa_free_instructions(&prog->Base.Instructions);
+   prog->Base.NumInstructions = 0;
+
    /*
     * Start with a simple vertex program that emits color.
     */
-   inst = _mesa_alloc_instructions(2);
-   if (!inst) {
-      _mesa_error(ctx, GL_OUT_OF_MEMORY, "_mesa_nop_vertex_program");
-      return;
-   }
-
-   _mesa_init_instructions(inst, 2);
-
-   inst[0].Opcode = OPCODE_MOV;
-   inst[0].DstReg.File = PROGRAM_OUTPUT;
-   inst[0].DstReg.Index = VARYING_SLOT_COL0;
-   inst[0].SrcReg[0].File = PROGRAM_INPUT;
+   inst = _mesa_alloc_instruction(OPCODE_MOV);
+   if (!inst)
+      goto fail;
+   inst->DstReg.File = PROGRAM_OUTPUT;
+   inst->DstReg.Index = VARYING_SLOT_COL0;
+   inst->SrcReg[0].File = PROGRAM_INPUT;
    if (prog->Base.InputsRead & VERT_BIT_COLOR0)
       inputAttr = VERT_ATTRIB_COLOR0;
    else
       inputAttr = VERT_ATTRIB_TEX0;
-   inst[0].SrcReg[0].Index = inputAttr;
-
-   inst[1].Opcode = OPCODE_END;
+   inst->SrcReg[0].Index = inputAttr;
+   insert_at_end(&prog->Base, inst);
 
-   _mesa_free_instructions(prog->Base.Instructions,
-                           prog->Base.NumInstructions);
+   inst = _mesa_alloc_instruction(OPCODE_END);
+   if (!inst)
+      goto fail;
+   insert_at_end(&prog->Base, inst);
 
-   prog->Base.Instructions = inst;
-   prog->Base.NumInstructions = 2;
    prog->Base.InputsRead = BITFIELD64_BIT(inputAttr);
    prog->Base.OutputsWritten = BITFIELD64_BIT(VARYING_SLOT_COL0);
 
@@ -663,4 +651,9 @@  _mesa_nop_vertex_program(struct gl_context *ctx, struct gl_vertex_program *prog)
     * Now insert code to do standard modelview/projection transformation.
     */
    _mesa_insert_mvp_code(ctx, prog);
+   return;
+
+fail:
+   _mesa_error(ctx, GL_OUT_OF_MEMORY, __FUNCTION__);
+   return;
 }
diff --git a/src/mesa/state_tracker/st_atom_pixeltransfer.c b/src/mesa/state_tracker/st_atom_pixeltransfer.c
index a04163c..9d5dd34 100644
--- a/src/mesa/state_tracker/st_atom_pixeltransfer.c
+++ b/src/mesa/state_tracker/st_atom_pixeltransfer.c
@@ -139,10 +139,9 @@  static struct gl_fragment_program *
 get_pixel_transfer_program(struct gl_context *ctx, const struct state_key *key)
 {
    struct st_context *st = st_context(ctx);
-   struct prog_instruction inst[MAX_INST];
+   struct prog_instruction *inst;
    struct gl_program_parameter_list *params;
    struct gl_fragment_program *fp;
-   GLuint ic = 0;
    const GLuint colorTemp = 0;
 
    fp = (struct gl_fragment_program *)
@@ -156,15 +155,17 @@  get_pixel_transfer_program(struct gl_context *ctx, const struct state_key *key)
     * Get initial pixel color from the texture.
     * TEX colorTemp, fragment.texcoord[0], texture[0], 2D;
     */
-   _mesa_init_instructions(inst + ic, 1);
-   inst[ic].Opcode = OPCODE_TEX;
-   inst[ic].DstReg.File = PROGRAM_TEMPORARY;
-   inst[ic].DstReg.Index = colorTemp;
-   inst[ic].SrcReg[0].File = PROGRAM_INPUT;
-   inst[ic].SrcReg[0].Index = VARYING_SLOT_TEX0;
-   inst[ic].TexSrcUnit = 0;
-   inst[ic].TexSrcTarget = TEXTURE_2D_INDEX;
-   ic++;
+   inst = _mesa_alloc_instruction(OPCODE_TEX);
+   if (!inst)
+      goto fail_exit;
+   inst->DstReg.File = PROGRAM_TEMPORARY;
+   inst->DstReg.Index = colorTemp;
+   inst->SrcReg[0].File = PROGRAM_INPUT;
+   inst->SrcReg[0].Index = VARYING_SLOT_TEX0;
+   inst->TexSrcUnit = 0;
+   inst->TexSrcTarget = TEXTURE_2D_INDEX;
+   _mesa_append_instruction(&fp->Base, inst);
+
    fp->Base.InputsRead = BITFIELD64_BIT(VARYING_SLOT_TEX0);
    fp->Base.OutputsWritten = BITFIELD64_BIT(FRAG_RESULT_COLOR);
    fp->Base.SamplersUsed = 0x1;  /* sampler 0 (bit 0) is used */
@@ -180,17 +181,18 @@  get_pixel_transfer_program(struct gl_context *ctx, const struct state_key *key)
       bias_p = _mesa_add_state_reference(params, bias_state);
 
       /* MAD colorTemp, colorTemp, scale, bias; */
-      _mesa_init_instructions(inst + ic, 1);
-      inst[ic].Opcode = OPCODE_MAD;
-      inst[ic].DstReg.File = PROGRAM_TEMPORARY;
-      inst[ic].DstReg.Index = colorTemp;
-      inst[ic].SrcReg[0].File = PROGRAM_TEMPORARY;
-      inst[ic].SrcReg[0].Index = colorTemp;
-      inst[ic].SrcReg[1].File = PROGRAM_STATE_VAR;
-      inst[ic].SrcReg[1].Index = scale_p;
-      inst[ic].SrcReg[2].File = PROGRAM_STATE_VAR;
-      inst[ic].SrcReg[2].Index = bias_p;
-      ic++;
+      inst = _mesa_alloc_instruction(OPCODE_MAD);
+      if (!inst)
+         goto fail_exit;
+      inst->DstReg.File = PROGRAM_TEMPORARY;
+      inst->DstReg.Index = colorTemp;
+      inst->SrcReg[0].File = PROGRAM_TEMPORARY;
+      inst->SrcReg[0].Index = colorTemp;
+      inst->SrcReg[1].File = PROGRAM_STATE_VAR;
+      inst->SrcReg[1].Index = scale_p;
+      inst->SrcReg[2].File = PROGRAM_STATE_VAR;
+      inst->SrcReg[2].Index = bias_p;
+      _mesa_append_instruction(&fp->Base, inst);
    }
 
    if (key->pixelMaps) {
@@ -209,68 +211,56 @@  get_pixel_transfer_program(struct gl_context *ctx, const struct state_key *key)
        */
 
       /* TEX temp.rg, colorTemp.rgba, texture[1], 2D; */
-      _mesa_init_instructions(inst + ic, 1);
-      inst[ic].Opcode = OPCODE_TEX;
-      inst[ic].DstReg.File = PROGRAM_TEMPORARY;
-      inst[ic].DstReg.Index = temp;
-      inst[ic].DstReg.WriteMask = WRITEMASK_XY; /* write R,G */
-      inst[ic].SrcReg[0].File = PROGRAM_TEMPORARY;
-      inst[ic].SrcReg[0].Index = colorTemp;
-      inst[ic].TexSrcUnit = 1;
-      inst[ic].TexSrcTarget = TEXTURE_2D_INDEX;
-      ic++;
+      inst = _mesa_alloc_instruction(OPCODE_TEX);
+      if (!inst)
+         goto fail_exit;
+      inst->DstReg.File = PROGRAM_TEMPORARY;
+      inst->DstReg.Index = temp;
+      inst->DstReg.WriteMask = WRITEMASK_XY; /* write R,G */
+      inst->SrcReg[0].File = PROGRAM_TEMPORARY;
+      inst->SrcReg[0].Index = colorTemp;
+      inst->TexSrcUnit = 1;
+      inst->TexSrcTarget = TEXTURE_2D_INDEX;
+      _mesa_append_instruction(&fp->Base, inst);
 
       /* TEX temp.ba, colorTemp.baba, texture[1], 2D; */
-      _mesa_init_instructions(inst + ic, 1);
-      inst[ic].Opcode = OPCODE_TEX;
-      inst[ic].DstReg.File = PROGRAM_TEMPORARY;
-      inst[ic].DstReg.Index = temp;
-      inst[ic].DstReg.WriteMask = WRITEMASK_ZW; /* write B,A */
-      inst[ic].SrcReg[0].File = PROGRAM_TEMPORARY;
-      inst[ic].SrcReg[0].Index = colorTemp;
-      inst[ic].SrcReg[0].Swizzle = MAKE_SWIZZLE4(SWIZZLE_Z, SWIZZLE_W,
-                                                 SWIZZLE_Z, SWIZZLE_W);
-      inst[ic].TexSrcUnit = 1;
-      inst[ic].TexSrcTarget = TEXTURE_2D_INDEX;
-      ic++;
+      inst = _mesa_alloc_instruction(OPCODE_TEX);
+      if (!inst)
+         goto fail_exit;
+      inst->DstReg.File = PROGRAM_TEMPORARY;
+      inst->DstReg.Index = temp;
+      inst->DstReg.WriteMask = WRITEMASK_ZW; /* write B,A */
+      inst->SrcReg[0].File = PROGRAM_TEMPORARY;
+      inst->SrcReg[0].Index = colorTemp;
+      inst->SrcReg[0].Swizzle = MAKE_SWIZZLE4(SWIZZLE_Z, SWIZZLE_W,
+                                              SWIZZLE_Z, SWIZZLE_W);
+      inst->TexSrcUnit = 1;
+      inst->TexSrcTarget = TEXTURE_2D_INDEX;
+      _mesa_append_instruction(&fp->Base, inst);
 
       /* MOV colorTemp, temp; */
-      _mesa_init_instructions(inst + ic, 1);
-      inst[ic].Opcode = OPCODE_MOV;
-      inst[ic].DstReg.File = PROGRAM_TEMPORARY;
-      inst[ic].DstReg.Index = colorTemp;
-      inst[ic].SrcReg[0].File = PROGRAM_TEMPORARY;
-      inst[ic].SrcReg[0].Index = temp;
-      ic++;
+      inst = _mesa_alloc_instruction(OPCODE_MOV);
+      if (!inst)
+         goto fail_exit;
+      inst->DstReg.File = PROGRAM_TEMPORARY;
+      inst->DstReg.Index = colorTemp;
+      inst->SrcReg[0].File = PROGRAM_TEMPORARY;
+      inst->SrcReg[0].Index = temp;
+      _mesa_append_instruction(&fp->Base, inst);
 
       fp->Base.SamplersUsed |= (1 << 1);  /* sampler 1 is used */
    }
 
    /* Modify last instruction's dst reg to write to result.color */
-   {
-      struct prog_instruction *last = &inst[ic - 1];
-      last->DstReg.File = PROGRAM_OUTPUT;
-      last->DstReg.Index = FRAG_RESULT_COLOR;
-   }
+   inst->DstReg.File = PROGRAM_OUTPUT;
+   inst->DstReg.Index = FRAG_RESULT_COLOR;
 
    /* END; */
-   _mesa_init_instructions(inst + ic, 1);
-   inst[ic].Opcode = OPCODE_END;
-   ic++;
-
-   assert(ic <= MAX_INST);
-
+   inst = _mesa_alloc_instruction(OPCODE_END);
+   if (!inst)
+      goto fail_exit;
+   _mesa_append_instruction(&fp->Base, inst);
 
-   fp->Base.Instructions = _mesa_alloc_instructions(ic);
-   if (!fp->Base.Instructions) {
-      _mesa_error(ctx, GL_OUT_OF_MEMORY,
-                  "generating pixel transfer program");
-      _mesa_free_parameter_list(params);
-      return NULL;
-   }
-
-   _mesa_copy_instructions(fp->Base.Instructions, inst, ic);
-   fp->Base.NumInstructions = ic;
    fp->Base.Parameters = params;
 
 #if 0
@@ -280,6 +270,12 @@  get_pixel_transfer_program(struct gl_context *ctx, const struct state_key *key)
 #endif
 
    return fp;
+
+fail_exit:
+   _mesa_error(ctx, GL_OUT_OF_MEMORY,
+               "generating pixel transfer program");
+   _mesa_free_parameter_list(params);
+   return NULL;
 }
 
 
diff --git a/src/mesa/state_tracker/st_cb_bitmap.c b/src/mesa/state_tracker/st_cb_bitmap.c
index e3ba5a8..3a23c59 100644
--- a/src/mesa/state_tracker/st_cb_bitmap.c
+++ b/src/mesa/state_tracker/st_cb_bitmap.c
@@ -118,46 +118,42 @@  make_bitmap_fragment_program(struct gl_context *ctx, GLuint samplerIndex)
    struct st_context *st = st_context(ctx);
    struct st_fragment_program *stfp;
    struct gl_program *p;
-   GLuint ic = 0;
+   struct prog_instruction *inst;
 
    p = ctx->Driver.NewProgram(ctx, GL_FRAGMENT_PROGRAM_ARB, 0);
    if (!p)
       return NULL;
 
-   p->NumInstructions = 3;
-
-   p->Instructions = _mesa_alloc_instructions(p->NumInstructions);
-   if (!p->Instructions) {
-      ctx->Driver.DeleteProgram(ctx, p);
-      return NULL;
-   }
-   _mesa_init_instructions(p->Instructions, p->NumInstructions);
-
    /* TEX tmp0, fragment.texcoord[0], texture[0], 2D; */
-   p->Instructions[ic].Opcode = OPCODE_TEX;
-   p->Instructions[ic].DstReg.File = PROGRAM_TEMPORARY;
-   p->Instructions[ic].DstReg.Index = 0;
-   p->Instructions[ic].SrcReg[0].File = PROGRAM_INPUT;
-   p->Instructions[ic].SrcReg[0].Index = VARYING_SLOT_TEX0;
-   p->Instructions[ic].TexSrcUnit = samplerIndex;
-   p->Instructions[ic].TexSrcTarget = TEXTURE_2D_INDEX;
-   ic++;
+   inst = _mesa_alloc_instruction(OPCODE_TEX);
+   if (!inst)
+      goto fail_exit;
+   inst->DstReg.File = PROGRAM_TEMPORARY;
+   inst->DstReg.Index = 0;
+   inst->SrcReg[0].File = PROGRAM_INPUT;
+   inst->SrcReg[0].Index = VARYING_SLOT_TEX0;
+   inst->TexSrcUnit = samplerIndex;
+   inst->TexSrcTarget = TEXTURE_2D_INDEX;
+   _mesa_append_instruction(p, inst);
 
    /* KIL if -tmp0 < 0 # texel=0 -> keep / texel=0 -> discard */
-   p->Instructions[ic].Opcode = OPCODE_KIL;
-   p->Instructions[ic].SrcReg[0].File = PROGRAM_TEMPORARY;
+   inst = _mesa_alloc_instruction(OPCODE_KIL);
+   if (!inst)
+      goto fail_exit;
+   inst->SrcReg[0].File = PROGRAM_TEMPORARY;
 
    if (st->bitmap.tex_format == PIPE_FORMAT_L8_UNORM)
-      p->Instructions[ic].SrcReg[0].Swizzle = SWIZZLE_XXXX;
+      inst->SrcReg[0].Swizzle = SWIZZLE_XXXX;
 
-   p->Instructions[ic].SrcReg[0].Index = 0;
-   p->Instructions[ic].SrcReg[0].Negate = NEGATE_XYZW;
-   ic++;
+   inst->SrcReg[0].Index = 0;
+   inst->SrcReg[0].Negate = NEGATE_XYZW;
+   _mesa_append_instruction(p, inst);
 
    /* END; */
-   p->Instructions[ic++].Opcode = OPCODE_END;
-
-   assert(ic == p->NumInstructions);
+   inst = _mesa_alloc_instruction(OPCODE_END);
+   if (!inst)
+      goto fail_exit;
+   _mesa_append_instruction(p, inst);
 
    p->InputsRead = VARYING_BIT_TEX0;
    p->OutputsWritten = 0x0;
@@ -167,6 +163,10 @@  make_bitmap_fragment_program(struct gl_context *ctx, GLuint samplerIndex)
    stfp->Base.UsesKill = GL_TRUE;
 
    return stfp;
+
+fail_exit:
+   ctx->Driver.DeleteProgram(ctx, p);
+   return NULL;
 }
 
 
diff --git a/src/mesa/state_tracker/st_cb_drawpixels.c b/src/mesa/state_tracker/st_cb_drawpixels.c
index 6119cc2..b99e9fd 100644
--- a/src/mesa/state_tracker/st_cb_drawpixels.c
+++ b/src/mesa/state_tracker/st_cb_drawpixels.c
@@ -79,15 +79,19 @@  static GLboolean
 is_passthrough_program(const struct gl_fragment_program *prog)
 {
    if (prog->Base.NumInstructions == 2) {
-      const struct prog_instruction *inst = prog->Base.Instructions;
-      if (inst[0].Opcode == OPCODE_MOV &&
-          inst[1].Opcode == OPCODE_END &&
-          inst[0].DstReg.File == PROGRAM_OUTPUT &&
-          inst[0].DstReg.Index == FRAG_RESULT_COLOR &&
-          inst[0].DstReg.WriteMask == WRITEMASK_XYZW &&
-          inst[0].SrcReg[0].File == PROGRAM_INPUT &&
-          inst[0].SrcReg[0].Index == VARYING_SLOT_COL0 &&
-          inst[0].SrcReg[0].Swizzle == SWIZZLE_XYZW) {
+      const struct prog_instruction *inst[2] = {
+         (struct prog_instruction *)first_elem(&prog->Base.Instructions),
+         (struct prog_instruction *)first_elem(&prog->Base.Instructions)->next
+      };
+
+      if (inst[0]->Opcode == OPCODE_MOV &&
+          inst[1]->Opcode == OPCODE_END &&
+          inst[0]->DstReg.File == PROGRAM_OUTPUT &&
+          inst[0]->DstReg.Index == FRAG_RESULT_COLOR &&
+          inst[0]->DstReg.WriteMask == WRITEMASK_XYZW &&
+          inst[0]->SrcReg[0].File == PROGRAM_INPUT &&
+          inst[0]->SrcReg[0].Index == VARYING_SLOT_COL0 &&
+          inst[0]->SrcReg[0].Swizzle == SWIZZLE_XYZW) {
          return GL_TRUE;
       }
    }
@@ -198,7 +202,7 @@  st_make_drawpix_z_stencil_program(struct st_context *st,
    struct gl_context *ctx = st->ctx;
    struct gl_program *p;
    struct gl_fragment_program *fp;
-   GLuint ic = 0;
+   struct prog_instruction *inst;
    const GLuint shaderIndex = write_depth * 2 + write_stencil;
 
    assert(shaderIndex < Elements(st->drawpix.shaders));
@@ -215,53 +219,51 @@  st_make_drawpix_z_stencil_program(struct st_context *st,
    if (!p)
       return NULL;
 
-   p->NumInstructions = write_depth ? 3 : 1;
-   p->NumInstructions += write_stencil ? 1 : 0;
-
-   p->Instructions = _mesa_alloc_instructions(p->NumInstructions);
-   if (!p->Instructions) {
-      ctx->Driver.DeleteProgram(ctx, p);
-      return NULL;
-   }
-   _mesa_init_instructions(p->Instructions, p->NumInstructions);
-
    if (write_depth) {
       /* TEX result.depth, fragment.texcoord[0], texture[0], 2D; */
-      p->Instructions[ic].Opcode = OPCODE_TEX;
-      p->Instructions[ic].DstReg.File = PROGRAM_OUTPUT;
-      p->Instructions[ic].DstReg.Index = FRAG_RESULT_DEPTH;
-      p->Instructions[ic].DstReg.WriteMask = WRITEMASK_Z;
-      p->Instructions[ic].SrcReg[0].File = PROGRAM_INPUT;
-      p->Instructions[ic].SrcReg[0].Index = VARYING_SLOT_TEX0;
-      p->Instructions[ic].TexSrcUnit = 0;
-      p->Instructions[ic].TexSrcTarget = TEXTURE_2D_INDEX;
-      ic++;
+      inst = _mesa_alloc_instruction(OPCODE_TEX);
+      if (!inst)
+         goto fail_exit;
+      inst->DstReg.File = PROGRAM_OUTPUT;
+      inst->DstReg.Index = FRAG_RESULT_DEPTH;
+      inst->DstReg.WriteMask = WRITEMASK_Z;
+      inst->SrcReg[0].File = PROGRAM_INPUT;
+      inst->SrcReg[0].Index = VARYING_SLOT_TEX0;
+      inst->TexSrcUnit = 0;
+      inst->TexSrcTarget = TEXTURE_2D_INDEX;
+      _mesa_append_instruction(p, inst);
+
       /* MOV result.color, fragment.color; */
-      p->Instructions[ic].Opcode = OPCODE_MOV;
-      p->Instructions[ic].DstReg.File = PROGRAM_OUTPUT;
-      p->Instructions[ic].DstReg.Index = FRAG_RESULT_COLOR;
-      p->Instructions[ic].SrcReg[0].File = PROGRAM_INPUT;
-      p->Instructions[ic].SrcReg[0].Index = VARYING_SLOT_COL0;
-      ic++;
+      inst = _mesa_alloc_instruction(OPCODE_MOV);
+      if (!inst)
+         goto fail_exit;
+      inst->DstReg.File = PROGRAM_OUTPUT;
+      inst->DstReg.Index = FRAG_RESULT_COLOR;
+      inst->SrcReg[0].File = PROGRAM_INPUT;
+      inst->SrcReg[0].Index = VARYING_SLOT_COL0;
+      _mesa_append_instruction(p, inst);
    }
 
    if (write_stencil) {
       /* TEX result.stencil, fragment.texcoord[0], texture[0], 2D; */
-      p->Instructions[ic].Opcode = OPCODE_TEX;
-      p->Instructions[ic].DstReg.File = PROGRAM_OUTPUT;
-      p->Instructions[ic].DstReg.Index = FRAG_RESULT_STENCIL;
-      p->Instructions[ic].DstReg.WriteMask = WRITEMASK_Y;
-      p->Instructions[ic].SrcReg[0].File = PROGRAM_INPUT;
-      p->Instructions[ic].SrcReg[0].Index = VARYING_SLOT_TEX0;
-      p->Instructions[ic].TexSrcUnit = 1;
-      p->Instructions[ic].TexSrcTarget = TEXTURE_2D_INDEX;
-      ic++;
+      inst = _mesa_alloc_instruction(OPCODE_TEX);
+      if (!inst)
+         goto fail_exit;
+      inst->DstReg.File = PROGRAM_OUTPUT;
+      inst->DstReg.Index = FRAG_RESULT_STENCIL;
+      inst->DstReg.WriteMask = WRITEMASK_Y;
+      inst->SrcReg[0].File = PROGRAM_INPUT;
+      inst->SrcReg[0].Index = VARYING_SLOT_TEX0;
+      inst->TexSrcUnit = 1;
+      inst->TexSrcTarget = TEXTURE_2D_INDEX;
+      _mesa_append_instruction(p, inst);
    }
 
    /* END; */
-   p->Instructions[ic++].Opcode = OPCODE_END;
-
-   assert(ic == p->NumInstructions);
+   inst = _mesa_alloc_instruction(OPCODE_END);
+   if (!inst)
+      goto fail_exit;
+   _mesa_append_instruction(p, inst);
 
    p->InputsRead = VARYING_BIT_TEX0 | VARYING_BIT_COL0;
    p->OutputsWritten = 0;
@@ -282,6 +284,10 @@  st_make_drawpix_z_stencil_program(struct st_context *st,
    st->drawpix.shaders[shaderIndex] = fp;
 
    return fp;
+
+fail_exit:
+   ctx->Driver.DeleteProgram(ctx, p);
+   return NULL;
 }
 
 
diff --git a/src/mesa/state_tracker/st_glsl_to_tgsi.cpp b/src/mesa/state_tracker/st_glsl_to_tgsi.cpp
index 739e108..90aa8d6 100644
--- a/src/mesa/state_tracker/st_glsl_to_tgsi.cpp
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi.cpp
@@ -5307,7 +5307,6 @@  get_mesa_program(struct gl_context *ctx,
       fflush(stdout);
    }
 
-   prog->Instructions = NULL;
    prog->NumInstructions = 0;
 
    do_set_program_inouts(shader->ir, prog, shader->Stage);
diff --git a/src/mesa/state_tracker/st_mesa_to_tgsi.c b/src/mesa/state_tracker/st_mesa_to_tgsi.c
index 683cd1c..ae7299a 100644
--- a/src/mesa/state_tracker/st_mesa_to_tgsi.c
+++ b/src/mesa/state_tracker/st_mesa_to_tgsi.c
@@ -44,6 +44,8 @@ 
 #include "util/u_debug.h"
 #include "util/u_math.h"
 #include "util/u_memory.h"
+#include "main/hash_table.h"
+#include "ralloc.h"
 
 
 #define PROGRAM_ANY_CONST ((1 << PROGRAM_STATE_VAR) |    \
@@ -52,7 +54,7 @@ 
 
 
 struct label {
-   unsigned branch_target;
+   struct prog_instruction *branch_target;
    unsigned token;
 };
 
@@ -82,13 +84,10 @@  struct st_translate {
    unsigned labels_size;
    unsigned labels_count;
 
-   /* Keep a record of the tgsi instruction number that each mesa
-    * instruction starts at, will be used to fix up labels after
-    * translation.
+   /* Maps from a struct prog_instruction * to the index of the generated TGSI
+    * instruction, used to fix up branch targets.
     */
-   unsigned *insn;
-   unsigned insn_size;
-   unsigned insn_count;
+   struct hash_table *insn_map;
 
    unsigned procType;  /**< TGSI_PROCESSOR_VERTEX/FRAGMENT */
 
@@ -111,7 +110,7 @@  static unsigned mesa_sysval_to_semantic[SYSTEM_VALUE_MAX] = {
  * location of each label.
  */
 static unsigned *get_label( struct st_translate *t,
-                            unsigned branch_target )
+                            struct prog_instruction *branch_target )
 {
    unsigned i;
 
@@ -130,29 +129,6 @@  static unsigned *get_label( struct st_translate *t,
    return &t->labels[i].token;
 }
 
-
-/**
- * Called prior to emitting the TGSI code for each Mesa instruction.
- * Allocate additional space for instructions if needed.
- * Update the insn[] array so the next Mesa instruction points to
- * the next TGSI instruction.
- */
-static void set_insn_start( struct st_translate *t,
-                            unsigned start )
-{
-   if (t->insn_count + 1 >= t->insn_size) {
-      t->insn_size = 1 << (util_logbase2(t->insn_size) + 1);
-      t->insn = realloc(t->insn, t->insn_size * sizeof t->insn[0]);
-      if (t->insn == NULL) {
-         t->error = TRUE;
-         return;
-      }
-   }
-
-   t->insn[t->insn_count++] = start;
-}
-
-
 /**
  * Map a Mesa dst register to a TGSI ureg_dst register.
  */
@@ -1029,6 +1005,7 @@  st_translate_mesa_program(
    struct st_translate translate, *t;
    unsigned i;
    enum pipe_error ret = PIPE_OK;
+   struct simple_node *node;
 
    assert(numInputs <= Elements(t->inputs));
    assert(numOutputs <= Elements(t->outputs));
@@ -1040,6 +1017,7 @@  st_translate_mesa_program(
    t->inputMapping = inputMapping;
    t->outputMapping = outputMapping;
    t->ureg = ureg;
+   t->insn_map = _mesa_hash_table_create(NULL, _mesa_key_pointer_equal);
 
    /*_mesa_print_program(program);*/
 
@@ -1233,23 +1211,36 @@  st_translate_mesa_program(
 
    /* Emit each instruction in turn:
     */
-   for (i = 0; i < program->NumInstructions; i++) {
-      set_insn_start( t, ureg_get_instruction_number( ureg ));
-      compile_instruction( ctx, t, &program->Instructions[i], clamp_color );
+   foreach(node, &program->Instructions) {
+      struct prog_instruction *inst = (struct prog_instruction *)node;
+      unsigned tgsi_index = ureg_get_instruction_number( ureg );
+      _mesa_hash_table_insert(t->insn_map,
+                              _mesa_hash_pointer(inst),
+                              inst,
+                              (void *)(uintptr_t)tgsi_index);
+
+      compile_instruction( ctx, t, inst, clamp_color );
    }
 
    /* Fix up all emitted labels:
     */
    for (i = 0; i < t->labels_count; i++) {
+      struct prog_instruction *branch_target = t->labels[i].branch_target;
+      struct hash_entry *he =
+         _mesa_hash_table_search(t->insn_map,
+                                 _mesa_hash_pointer(branch_target),
+                                 branch_target);
+      unsigned tgsi_target = (uintptr_t)he->data;
+
       ureg_fixup_label( ureg,
                         t->labels[i].token,
-                        t->insn[t->labels[i].branch_target] );
+                        tgsi_target );
    }
 
 out:
-   free(t->insn);
    free(t->labels);
    free(t->constants);
+   ralloc_free(t->insn_map);
 
    if (t->error) {
       debug_printf("%s: translate error flag set\n", __FUNCTION__);