Mesa (9.1): ra: Fix register spilling.

[Carl Worth]

Module: Mesa
Branch: 9.1
Commit: d3ab091433393a2823a68bc97ff7437e8b64d7ef
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=d3ab091433393a2823a68bc97ff7437e8b64d7ef

Author: Eric Anholt <eric at anholt.net>
Date:   Thu Jun  6 13:21:21 2013 -0700

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.
(cherry picked from commit da00782ed81776473270028cda262c913d737438)

---

 src/mesa/program/register_allocate.c |   44 ++++++++++++++++++++++++++++++----
 1 files changed, 39 insertions(+), 5 deletions(-)

diff --git a/src/mesa/program/register_allocate.c b/src/mesa/program/register_allocate.c
index d5acc9f..22b5578 100644
--- a/src/mesa/program/register_allocate.c
+++ b/src/mesa/program/register_allocate.c
@@ -152,6 +152,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;
 };
 
 /**
@@ -468,6 +478,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;
@@ -546,8 +557,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;
@@ -555,10 +574,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;
 
@@ -570,6 +585,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;
 }