From da00782ed81776473270028cda262c913d737438 Mon Sep 17 00:00:00 2001
From: Eric Anholt <eric@anholt.net>
Date: Thu, 6 Jun 2013 13:21:21 -0700
Subject: [PATCH] ra: Fix register spilling.

Commit 551c991606e543c3a264a762026f11348b37947e tried to avoid spilling
registers that were trivially colorable.  But since we do optimistic
coloring, the top of the stack also contains nodes that are not trivially
colorable, so we need to consider them for spilling (since they are some
of our best candidates).

Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=58384
Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=63674
NOTE: This is a candidate for the 9.1 branch.
---
 src/mesa/program/register_allocate.c | 44 ++++++++++++++++++++++++----
 1 file changed, 39 insertions(+), 5 deletions(-)

diff --git a/src/mesa/program/register_allocate.c b/src/mesa/program/register_allocate.c
index 16739fd3982..ea06a07c6af 100644
--- a/src/mesa/program/register_allocate.c
+++ b/src/mesa/program/register_allocate.c
@@ -157,6 +157,16 @@ struct ra_graph {
 
    unsigned int *stack;
    unsigned int stack_count;
+
+   /**
+    * Tracks the start of the set of optimistically-colored registers in the
+    * stack.
+    *
+    * Along with any registers not in the stack (if one called ra_simplify()
+    * and didn't do optimistic coloring), these need to be considered for
+    * spilling.
+    */
+   unsigned int stack_optimistic_start;
 };
 
 /**
@@ -509,6 +519,7 @@ ra_optimistic_color(struct ra_graph *g)
 {
    unsigned int i;
 
+   g->stack_optimistic_start = g->stack_count;
    for (i = 0; i < g->count; i++) {
       if (g->nodes[i].in_stack || g->nodes[i].reg != NO_REG)
 	 continue;
@@ -587,8 +598,16 @@ ra_get_best_spill_node(struct ra_graph *g)
 {
    unsigned int best_node = -1;
    float best_benefit = 0.0;
-   unsigned int n;
+   unsigned int n, i;
 
+   /* For any registers not in the stack to be colored, consider them for
+    * spilling.  This will mostly collect nodes that were being optimistally
+    * colored as part of ra_allocate_no_spills() if we didn't successfully
+    * optimistically color.
+    *
+    * It also includes nodes not trivially colorable by ra_simplify() if it
+    * was used directly instead of as part of ra_allocate_no_spills().
+    */
    for (n = 0; n < g->count; n++) {
       float cost = g->nodes[n].spill_cost;
       float benefit;
@@ -596,10 +615,6 @@ ra_get_best_spill_node(struct ra_graph *g)
       if (cost <= 0.0)
 	 continue;
 
-      /* Only consider registers for spilling if they are still in the
-       * interference graph (those on the stack have already been proven to be
-       * allocatable without spilling).
-       */
       if (g->nodes[n].in_stack)
          continue;
 
@@ -611,6 +626,25 @@ ra_get_best_spill_node(struct ra_graph *g)
       }
    }
 
+   /* Also consider spilling any nodes that were set up to be optimistically
+    * colored that we couldn't manage to color in ra_select().
+    */
+   for (i = g->stack_optimistic_start; i < g->stack_count; i++) {
+      n = g->stack[i];
+      float cost = g->nodes[n].spill_cost;
+      float benefit;
+
+      if (cost <= 0.0)
+         continue;
+
+      benefit = ra_get_spill_benefit(g, n);
+
+      if (benefit / cost > best_benefit) {
+         best_benefit = benefit / cost;
+         best_node = n;
+      }
+   }
+
    return best_node;
 }
 
-- 
2.30.2