i965: Add support for register spilling.

It can be tested with if (0) replaced with if (1) to force spilling for all
virtual GRFs.  Some simple tests work, but large texturing tests fail.

2 files changed, 65 insertions, 0 deletions

diff --git a/src/mesa/program/register_allocate.c b/src/mesa/program/register_allocate.c
index 03f04697bf..a6aa7f39cb 100644
--- a/src/mesa/program/register_allocate.c
+++ b/src/mesa/program/register_allocate.c
@@ -72,6 +72,7 @@ struct ra_node {
    unsigned int adjacency_count;
    unsigned int reg;
    GLboolean in_stack;
+   float spill_cost;
 };
 
 struct ra_graph {
@@ -359,3 +360,65 @@ ra_get_node_reg(struct ra_graph *g, unsigned int n)
 {
    return g->nodes[n].reg;
 }
+
+static float
+ra_get_spill_benefit(struct ra_graph *g, unsigned int n)
+{
+   int j;
+   float benefit = 0;
+   int n_class = g->nodes[n].class;
+
+   /* Define the benefit of eliminating an interference between n, j
+    * through spilling as q(C, B) / p(C).  This is similar to the
+    * "count number of edges" approach of traditional graph coloring,
+    * but takes classes into account.
+    */
+   for (j = 0; j < g->count; j++) {
+      if (j != n && g->nodes[n].adjacency[j]) {
+	 unsigned int j_class = g->nodes[j].class;
+	 benefit += ((float)g->regs->classes[n_class]->q[j_class] /
+		     g->regs->classes[n_class]->p);
+	 break;
+      }
+   }
+
+   return benefit;
+}
+
+/**
+ * Returns a node number to be spilled according to the cost/benefit using
+ * the pq test, or -1 if there are no spillable nodes.
+ */
+int
+ra_get_best_spill_node(struct ra_graph *g)
+{
+   unsigned int best_node = -1;
+   unsigned int best_benefit = 0.0;
+   unsigned int n;
+
+   for (n = 0; n < g->count; n++) {
+      float cost = g->nodes[n].spill_cost;
+
+      if (cost <= 0.0)
+	 continue;
+
+      float benefit = ra_get_spill_benefit(g, n);
+
+      if (benefit / cost > best_benefit) {
+	 best_benefit = benefit / cost;
+	 best_node = n;
+      }
+   }
+
+   return best_node;
+}
+
+/**
+ * Only nodes with a spill cost set (cost != 0.0) will be considered
+ * for register spilling.
+ */
+void
+ra_set_node_spill_cost(struct ra_graph *g, unsigned int n, float cost)
+{
+   g->nodes[n].spill_cost = cost;
+}
diff --git a/src/mesa/program/register_allocate.h b/src/mesa/program/register_allocate.h
index 42647b50b8..198b89f2d7 100644
--- a/src/mesa/program/register_allocate.h
+++ b/src/mesa/program/register_allocate.h
@@ -65,5 +65,7 @@ GLboolean ra_select(struct ra_graph *g);
 GLboolean ra_allocate_no_spills(struct ra_graph *g);
 
 unsigned int ra_get_node_reg(struct ra_graph *g, unsigned int n);
+void ra_set_node_spill_cost(struct ra_graph *g, unsigned int n, float cost);
+int ra_get_best_spill_node(struct ra_graph *g);
 /** @} */