[Mesa-dev] [PATCH 3/3] glsl_to_tgsi: Use mesa register allocator

Vincent Lejeune vljn at ovi.com
Sat Jan 7 14:06:02 PST 2012


---
 src/mesa/state_tracker/st_glsl_to_tgsi.cpp |  189 +++++++++++++++-------------
 1 files changed, 101 insertions(+), 88 deletions(-)

diff --git a/src/mesa/state_tracker/st_glsl_to_tgsi.cpp b/src/mesa/state_tracker/st_glsl_to_tgsi.cpp
index ab93a65..73333a7 100644
--- a/src/mesa/state_tracker/st_glsl_to_tgsi.cpp
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi.cpp
@@ -55,6 +55,7 @@ extern "C" {
 #include "program/program.h"
 #include "program/prog_parameter.h"
 #include "program/sampler.h"
+#include "program/register_allocate.h"
 
 #include "pipe/p_compiler.h"
 #include "pipe/p_context.h"
@@ -727,6 +728,12 @@ void glsl_to_tgsi_dereference_to_address::visit(ir_swizzle *)
 
 class glsl_to_tgsi_visitor : public ir_visitor {
 public:
+
+struct interval {
+   int first_line;
+   int last_line;
+};
+
    glsl_to_tgsi_visitor();
    ~glsl_to_tgsi_visitor();
 
@@ -852,17 +859,17 @@ public:
    void remove_output_reads(gl_register_file type);
    void simplify_cmp(void);
 
-   void rename_temp_register(int index, int new_index);
    int get_first_temp_read(int index);
    int get_first_temp_write(int index);
    int get_last_temp_read(int index);
    int get_last_temp_write(int index);
 
+   struct interval *get_live_intervals();
+
    void copy_propagate(void);
    void eliminate_dead_code(void);
    int eliminate_dead_code_advanced(void);
-   void merge_registers(void);
-   void renumber_registers(void);
+   unsigned *regalloc(struct interval*, unsigned);
    void renumber_temp_regs(unsigned*);
 
    void *mem_ctx;
@@ -3437,27 +3444,6 @@ glsl_to_tgsi_visitor::simplify_cmp(void)
    delete [] tempWrites;
 }
 
-/* Replaces all references to a temporary register index with another index. */
-void
-glsl_to_tgsi_visitor::rename_temp_register(int index, int new_index)
-{
-   foreach_iter(exec_list_iterator, iter, this->instructions) {
-      glsl_to_tgsi_instruction *inst = (glsl_to_tgsi_instruction *)iter.get();
-      unsigned j;
-      
-      for (j=0; j < num_inst_src_regs(inst->op); j++) {
-         if (inst->src[j].file == PROGRAM_TEMPORARY && 
-             inst->src[j].index == index) {
-            inst->src[j].index = new_index;
-         }
-      }
-      
-      if (inst->dst.file == PROGRAM_TEMPORARY && inst->dst.index == index) {
-         inst->dst.index = new_index;
-      }
-   }
-}
-
 int
 glsl_to_tgsi_visitor::get_first_temp_read(int index)
 {
@@ -3961,73 +3947,94 @@ glsl_to_tgsi_visitor::eliminate_dead_code_advanced(void)
    return removed;
 }
 
-/* Merges temporary registers together where possible to reduce the number of 
- * registers needed to run a program.
- * 
- * Produces optimal code only after copy propagation and dead code elimination 
- * have been run. */
-void
-glsl_to_tgsi_visitor::merge_registers(void)
+   /** Read the indices of the last read and first write to each temp register
+    * into an array so that we don't have to traverse the instruction list as
+    * much. Only parse temp not directly addressed. */
+struct glsl_to_tgsi_visitor::interval*
+glsl_to_tgsi_visitor::get_live_intervals()
 {
-   int *last_reads = rzalloc_array(mem_ctx, int, this->next_temp);
-   int *first_writes = rzalloc_array(mem_ctx, int, this->next_temp);
-   int i, j;
-   
-   /* Read the indices of the last read and first write to each temp register
-    * into an array so that we don't have to traverse the instruction list as 
-    * much. */
-   for (i=0; i < this->next_temp; i++) {
-      last_reads[i] = get_last_temp_read(i);
-      first_writes[i] = get_first_temp_write(i);
+   unsigned total_temps = store.temp_amount();
+   unsigned first_non_array_temp = store.temp_array_amount() + 1;
+   unsigned allocable_regs = total_temps - first_non_array_temp;
+   struct interval *live_interval = rzalloc_array(mem_ctx, struct interval, allocable_regs);
+
+   for (unsigned i=0; i < allocable_regs; i++) {
+      live_interval[i].first_line = get_first_temp_write(i + first_non_array_temp);
+      live_interval[i].last_line = MAX2(get_last_temp_read(i + first_non_array_temp), live_interval[i].first_line);
    }
-   
-   /* Start looking for registers with non-overlapping usages that can be 
-    * merged together. */
-   for (i=0; i < this->next_temp; i++) {
-      /* Don't touch unused registers. */
-      if (last_reads[i] < 0 || first_writes[i] < 0) continue;
-      
-      for (j=0; j < this->next_temp; j++) {
-         /* Don't touch unused registers. */
-         if (last_reads[j] < 0 || first_writes[j] < 0) continue;
-         
-         /* We can merge the two registers if the first write to j is after or 
-          * in the same instruction as the last read from i.  Note that the 
-          * register at index i will always be used earlier or at the same time 
-          * as the register at index j. */
-         if (first_writes[i] <= first_writes[j] && 
-             last_reads[i] <= first_writes[j])
-         {
-            rename_temp_register(j, i); /* Replace all references to j with i.*/
-            
-            /* Update the first_writes and last_reads arrays with the new 
-             * values for the merged register index, and mark the newly unused 
-             * register index as such. */
-            last_reads[i] = last_reads[j];
-            first_writes[j] = -1;
-            last_reads[j] = -1;
-         }
+   return live_interval;
+}
+
+static bool
+overlap(const glsl_to_tgsi_visitor::interval &a, const glsl_to_tgsi_visitor::interval &b)
+{
+   bool a_before_b = a.last_line <= b.first_line;
+   bool b_before_a = b.last_line <= a.first_line;
+   return !(a_before_b || b_before_a);
+}
+
+/**
+ * This function try to find a register map for st_src_reg and st_dst_reg not indirectly accessed that only
+ * requires suggested_temp_amount TEMP registers.
+ *
+ * It can fails and return NULL ; thus it might be relevant to call this function several time with higher
+ * suggested_temp_amount
+ */
+unsigned *
+glsl_to_tgsi_visitor::regalloc(struct interval *live_interval, unsigned suggested_temp_amount)
+{
+   unsigned total_temps = store.temp_amount();
+   unsigned first_non_array_temp = store.temp_array_amount() + 1;
+   unsigned allocable_regs = total_temps - first_non_array_temp;
+
+   unsigned i, j;
+   struct ra_regs *regs = ra_alloc_reg_set(suggested_temp_amount);
+   unsigned temp_class = ra_alloc_reg_class(regs);
+
+   for (i = 0; i < suggested_temp_amount; i++) {
+      ra_class_add_reg(regs, temp_class, i);
+   }
+
+   ra_set_finalize(regs);
+
+   struct ra_graph *graph = ra_alloc_interference_graph(regs, total_temps);
+
+   for (i = 0; i < first_non_array_temp; i++) {
+      ra_set_node_class(graph, i, temp_class);
+   }
+
+
+   for (i = 0; i < allocable_regs; i++) {
+      for (j = i + 1; j < allocable_regs; j++) {
+         if (overlap(live_interval[i], live_interval[j]))
+            ra_add_node_interference(graph, i, j);
       }
    }
-   
-   ralloc_free(last_reads);
-   ralloc_free(first_writes);
+
+   if (!ra_allocate_no_spills(graph)) {
+      printf("UNABLE TO ALLOCATE REGS\n");
+      ralloc_free(graph);
+      ralloc_free(regs);
+      return NULL;
+   }
+
+   unsigned *reindex_table = rzalloc_array(mem_ctx, unsigned, total_temps);
+   for (unsigned index = 0; index < first_non_array_temp; index++) {
+      reindex_table[index] = index;
+   }
+
+   for (unsigned index = first_non_array_temp; index < total_temps; index++) {
+      reindex_table[index] = ra_get_node_reg(graph, index - first_non_array_temp) + first_non_array_temp;
+   }
+
+   ralloc_free(graph);
+   ralloc_free(regs);
+
+   return reindex_table;
 }
 
-/* Reassign indices to temporary registers by reusing unused indices created 
- * by optimization passes. */
-void
-glsl_to_tgsi_visitor::renumber_registers(void)
 void glsl_to_tgsi_visitor::renumber_temp_regs(unsigned *reindex_table)
 {
-   int i = 0;
-   int new_index = 0;
-   
-   for (i=0; i < this->next_temp; i++) {
-      if (get_first_temp_read(i) < 0) continue;
-      if (i != new_index)
-         rename_temp_register(i, new_index);
-      new_index++;
    foreach_iter(exec_list_iterator, iter, this->instructions) {
       glsl_to_tgsi_instruction *inst = (glsl_to_tgsi_instruction *)iter.get();
       unsigned j;
@@ -4044,8 +4051,6 @@ void glsl_to_tgsi_visitor::renumber_temp_regs(unsigned *reindex_table)
          inst->dst.index = reindex_table[index];
       }
    }
-   
-   this->next_temp = new_index;
 }
 
 /**
@@ -5304,10 +5309,18 @@ get_mesa_program(struct gl_context *ctx,
     */
    if (!v->indirect_addr_temps) {
       v->eliminate_dead_code();
-      v->merge_registers();
-      v->renumber_registers();
    }
-   
+
+   struct glsl_to_tgsi_visitor::interval *live_interval = v->get_live_intervals();
+   unsigned *reindex_table = NULL;
+   unsigned suggested_temp = 4;
+
+   while (!reindex_table) {
+      reindex_table = v->regalloc(live_interval,suggested_temp);
+      suggested_temp *=2;
+   }
+   v->renumber_temp_regs(reindex_table);
+
    /* Write the END instruction. */
    v->emit(NULL, TGSI_OPCODE_END);
 
-- 
1.7.7



More information about the mesa-dev mailing list