mesa: change _mesa_find_free_register() to find multiple free regs

Before, _mesa_find_free_register() would scan the given shader to
find a free/unused register of the given type.  But subsequent calls
would return the same register again.  This caused a failure in the
_mesa_remove_output_reads() function which sometimes needs several
free temps.

Now use a new function which build a vector of 'used' flags and another
function which searches that vector for an unused register starting at
a position that's incremented for each call.

Fixes fd.o bug 26317.  Note that a regression test for this has been
added to the glean/glsl1 test.

(cherry picked from commit e0d01c9d7f46ccd531f8dd1a04c5ac067200ef1e)

3 files changed, 62 insertions, 29 deletions

diff --git a/src/mesa/shader/program.c b/src/mesa/shader/program.c
index 3e86d0adad..aaf5f96e2a 100644
--- a/src/mesa/shader/program.c
+++ b/src/mesa/shader/program.c
@@ -677,6 +677,8 @@ _mesa_combine_programs(GLcontext *ctx,
    const GLuint lenB = progB->NumInstructions;
    const GLuint numParamsA = _mesa_num_parameters(progA->Parameters);
    const GLuint newLength = lenA + lenB;
+   GLboolean usedTemps[MAX_PROGRAM_TEMPS];
+   GLuint firstTemp = 0;
    GLbitfield inputsB;
    GLuint i;
 
@@ -698,6 +700,10 @@ _mesa_combine_programs(GLcontext *ctx,
    newProg->Instructions = newInst;
    newProg->NumInstructions = newLength;
 
+   /* find used temp regs (we may need new temps below) */
+   _mesa_find_used_registers(newProg, PROGRAM_TEMPORARY,
+                             usedTemps, MAX_PROGRAM_TEMPS);
+
    if (newProg->Target == GL_FRAGMENT_PROGRAM_ARB) {
       struct gl_fragment_program *fprogA, *fprogB, *newFprog;
       GLbitfield progB_inputsRead = progB->InputsRead;
@@ -741,12 +747,15 @@ _mesa_combine_programs(GLcontext *ctx,
        */
       if ((progA->OutputsWritten & (1 << FRAG_RESULT_COLOR)) &&
           (progB_inputsRead & FRAG_BIT_COL0)) {
-         GLint tempReg = _mesa_find_free_register(newProg, PROGRAM_TEMPORARY);
+         GLint tempReg = _mesa_find_free_register(usedTemps, MAX_PROGRAM_TEMPS,
+                                                  firstTemp);
          if (tempReg < 0) {
             _mesa_problem(ctx, "No free temp regs found in "
                           "_mesa_combine_programs(), using 31");
             tempReg = 31;
          }
+         firstTemp = tempReg + 1;
+
          /* replace writes to result.color[0] with tempReg */
          replace_registers(newInst, lenA,
                            PROGRAM_OUTPUT, FRAG_RESULT_COLOR,
@@ -784,53 +793,64 @@ _mesa_combine_programs(GLcontext *ctx,
 }
 
 
-
-
 /**
- * Scan the given program to find a free register of the given type.
- * \param regFile - PROGRAM_INPUT, PROGRAM_OUTPUT or PROGRAM_TEMPORARY
+ * Populate the 'used' array with flags indicating which registers (TEMPs,
+ * INPUTs, OUTPUTs, etc, are used by the given program.
+ * \param file  type of register to scan for
+ * \param used  returns true/false flags for in use / free
+ * \param usedSize  size of the 'used' array
  */
-GLint
-_mesa_find_free_register(const struct gl_program *prog, GLuint regFile)
+void
+_mesa_find_used_registers(const struct gl_program *prog,
+                          gl_register_file file,
+                          GLboolean used[], GLuint usedSize)
 {
-   GLboolean used[MAX_PROGRAM_TEMPS];
-   GLuint i, k;
-
-   assert(regFile == PROGRAM_INPUT ||
-          regFile == PROGRAM_OUTPUT ||
-          regFile == PROGRAM_TEMPORARY);
+   GLuint i, j;
 
-   _mesa_memset(used, 0, sizeof(used));
+   _mesa_memset(used, 0, usedSize);
 
    for (i = 0; i < prog->NumInstructions; i++) {
       const struct prog_instruction *inst = prog->Instructions + i;
       const GLuint n = _mesa_num_inst_src_regs(inst->Opcode);
 
-      /* check dst reg first */
-      if (inst->DstReg.File == regFile) {
+      if (inst->DstReg.File == file) {
          used[inst->DstReg.Index] = GL_TRUE;
       }
-      else {
-         /* check src regs otherwise */
-         for (k = 0; k < n; k++) {
-            if (inst->SrcReg[k].File == regFile) {
-               used[inst->SrcReg[k].Index] = GL_TRUE;
-               break;
-            }
+
+      for (j = 0; j < n; j++) {
+         if (inst->SrcReg[j].File == file) {
+            used[inst->SrcReg[j].Index] = GL_TRUE;
          }
       }
    }
+}
 
-   for (i = 0; i < MAX_PROGRAM_TEMPS; i++) {
+
+/**
+ * Scan the given 'used' register flag array for the first entry
+ * that's >= firstReg.
+ * \param used  vector of flags indicating registers in use (as returned
+ *              by _mesa_find_used_registers())
+ * \param usedSize  size of the 'used' array
+ * \param firstReg  first register to start searching at
+ * \return index of unused register, or -1 if none.
+ */
+GLint
+_mesa_find_free_register(const GLboolean used[],
+                         GLuint usedSize, GLuint firstReg)
+{
+   GLuint i;
+
+   assert(firstReg < usedSize);
+
+   for (i = firstReg; i < usedSize; i++)
       if (!used[i])
          return i;
-   }
 
    return -1;
 }
 
 
-
 /**
  * "Post-process" a GPU program.  This is intended to be used for debugging.
  * Example actions include no-op'ing instructions or changing instruction
diff --git a/src/mesa/shader/program.h b/src/mesa/shader/program.h
index 56a4191f57..0187a2c55f 100644
--- a/src/mesa/shader/program.h
+++ b/src/mesa/shader/program.h
@@ -119,8 +119,14 @@ _mesa_combine_programs(GLcontext *ctx,
                        const struct gl_program *progA,
                        const struct gl_program *progB);
 
+extern void
+_mesa_find_used_registers(const struct gl_program *prog,
+                          gl_register_file file,
+                          GLboolean used[], GLuint usedSize);
+
 extern GLint
-_mesa_find_free_register(const struct gl_program *prog, GLuint regFile);
+_mesa_find_free_register(const GLboolean used[],
+                         GLuint maxRegs, GLuint firstReg);
 
 extern void
 _mesa_postprocess_program(GLcontext *ctx, struct gl_program *prog);
diff --git a/src/mesa/shader/programopt.c b/src/mesa/shader/programopt.c
index 9514545709..fb2ebe6338 100644
--- a/src/mesa/shader/programopt.c
+++ b/src/mesa/shader/programopt.c
@@ -495,6 +495,11 @@ _mesa_remove_output_reads(struct gl_program *prog, gl_register_file type)
    GLuint i;
    GLint outputMap[VERT_RESULT_MAX];
    GLuint numVaryingReads = 0;
+   GLboolean usedTemps[MAX_PROGRAM_TEMPS];
+   GLuint firstTemp = 0;
+
+   _mesa_find_used_registers(prog, PROGRAM_TEMPORARY,
+                             usedTemps, MAX_PROGRAM_TEMPS);
 
    assert(type == PROGRAM_VARYING || type == PROGRAM_OUTPUT);
    assert(prog->Target == GL_VERTEX_PROGRAM_ARB || type != PROGRAM_VARYING);
@@ -513,8 +518,10 @@ _mesa_remove_output_reads(struct gl_program *prog, gl_register_file type)
             const GLuint var = inst->SrcReg[j].Index;
             if (outputMap[var] == -1) {
                numVaryingReads++;
-               outputMap[var] = _mesa_find_free_register(prog,
-                                                         PROGRAM_TEMPORARY);
+               outputMap[var] = _mesa_find_free_register(usedTemps,
+                                                         MAX_PROGRAM_TEMPS,
+                                                         firstTemp);
+               firstTemp = outputMap[var] + 1;
             }
             inst->SrcReg[j].File = PROGRAM_TEMPORARY;
             inst->SrcReg[j].Index = outputMap[var];