X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Futil%2Fregister_allocate.c;h=9c654080a09a8e4b2449a2e396f20b6323d35c2c;hb=e5339fe4a47c242693962c9f90bbab8b74935cba;hp=35ef9a714cc83400f483015589f7d44f3b0ab98e;hpb=30146f29a723a3a3abe7cf7ef6cc8567880a077d;p=mesa.git

diff --git a/src/util/register_allocate.c b/src/util/register_allocate.c
index 35ef9a714cc..9c654080a09 100644
--- a/src/util/register_allocate.c
+++ b/src/util/register_allocate.c
@@ -73,14 +73,11 @@
 #include <stdbool.h>
 
 #include "ralloc.h"
-#include "main/imports.h"
+#include "util/imports.h"
 #include "main/macros.h"
-#include "main/mtypes.h"
 #include "util/bitset.h"
 #include "register_allocate.h"
 
-#define NO_REG ~0U
-
 struct ra_reg {
    BITSET_WORD *conflicts;
    unsigned int *conflict_list;
@@ -135,17 +132,12 @@ struct ra_node {
 
    unsigned int class;
 
+   /* Client-assigned register, if assigned, or NO_REG. */
+   unsigned int forced_reg;
+
    /* Register, if assigned, or NO_REG. */
    unsigned int reg;
 
-   /**
-    * Set when the node is in the trivially colorable stack.  When
-    * set, the adjacency to this node is ignored, to implement the
-    * "remove the edge from the graph" in simplification without
-    * having to actually modify the adjacency_list.
-    */
-   bool in_stack;
-
    /**
     * The q total, as defined in the Runeson/Nyström paper, for all the
     * interfering nodes not in the stack.
@@ -156,6 +148,15 @@ struct ra_node {
     * approximate cost of spilling this node.
     */
    float spill_cost;
+
+   /* Temporary data for the algorithm to scratch around in */
+   struct {
+      /**
+       * Temporary version of q_total which we decrement as things are placed
+       * into the stack.
+       */
+      unsigned int q_total;
+   } tmp;
 };
 
 struct ra_graph {
@@ -166,14 +167,40 @@ struct ra_graph {
    struct ra_node *nodes;
    unsigned int count; /**< count of nodes. */
 
-   unsigned int *stack;
-   unsigned int stack_count;
+   unsigned int alloc; /**< count of nodes allocated. */
 
-   /**
-    * Tracks the start of the set of optimistically-colored registers in the
-    * stack.
-    */
-   unsigned int stack_optimistic_start;
+   ra_select_reg_callback select_reg_callback;
+   void *select_reg_callback_data;
+
+   /* Temporary data for the algorithm to scratch around in */
+   struct {
+      unsigned int *stack;
+      unsigned int stack_count;
+
+      /** Bit-set indicating, for each register, if it's in the stack */
+      BITSET_WORD *in_stack;
+
+      /** Bit-set indicating, for each register, if it pre-assigned */
+      BITSET_WORD *reg_assigned;
+
+      /** Bit-set indicating, for each register, the value of the pq test */
+      BITSET_WORD *pq_test;
+
+      /** For each BITSET_WORD, the minimum q value or ~0 if unknown */
+      unsigned int *min_q_total;
+
+      /*
+       * * For each BITSET_WORD, the node with the minimum q_total if
+       * min_q_total[i] != ~0.
+       */
+      unsigned int *min_q_node;
+
+      /**
+       * Tracks the start of the set of optimistically-colored registers in the
+       * stack.
+       */
+      unsigned int stack_optimistic_start;
+   } tmp;
 };
 
 /**
@@ -274,6 +301,31 @@ ra_add_transitive_reg_conflict(struct ra_regs *regs,
    }
 }
 
+/**
+ * Set up conflicts between base_reg and it's two half registers reg0 and
+ * reg1, but take care to not add conflicts between reg0 and reg1.
+ *
+ * This is useful for architectures where full size registers are aliased by
+ * two half size registers (eg 32 bit float and 16 bit float registers).
+ */
+void
+ra_add_transitive_reg_pair_conflict(struct ra_regs *regs,
+                                    unsigned int base_reg, unsigned int reg0, unsigned int reg1)
+{
+   unsigned int i;
+
+   ra_add_reg_conflict(regs, reg0, base_reg);
+   ra_add_reg_conflict(regs, reg1, base_reg);
+
+   for (i = 0; i < regs->regs[base_reg].num_conflicts; i++) {
+      unsigned int conflict = regs->regs[base_reg].conflict_list[i];
+      if (conflict != reg1)
+         ra_add_reg_conflict(regs, reg0, regs->regs[base_reg].conflict_list[i]);
+      if (conflict != reg0)
+         ra_add_reg_conflict(regs, reg1, regs->regs[base_reg].conflict_list[i]);
+   }
+}
+
 /**
  * Makes every conflict on the given register transitive.  In other words,
  * every register that conflicts with r will now conflict with every other
@@ -287,10 +339,9 @@ void
 ra_make_reg_conflicts_transitive(struct ra_regs *regs, unsigned int r)
 {
    struct ra_reg *reg = &regs->regs[r];
-   BITSET_WORD tmp;
    int c;
 
-   BITSET_FOREACH_SET(c, tmp, reg->conflicts, regs->count) {
+   BITSET_FOREACH_SET(c, reg->conflicts, regs->count) {
       struct ra_reg *other = &regs->regs[c];
       unsigned i;
       for (i = 0; i < BITSET_WORDS(regs->count); i++)
@@ -392,11 +443,11 @@ ra_add_node_adjacency(struct ra_graph *g, unsigned int n1, unsigned int n2)
 {
    BITSET_SET(g->nodes[n1].adjacency, n2);
 
-   if (n1 != n2) {
-      int n1_class = g->nodes[n1].class;
-      int n2_class = g->nodes[n2].class;
-      g->nodes[n1].q_total += g->regs->classes[n1_class]->q[n2_class];
-   }
+   assert(n1 != n2);
+
+   int n1_class = g->nodes[n1].class;
+   int n2_class = g->nodes[n2].class;
+   g->nodes[n1].q_total += g->regs->classes[n1_class]->q[n2_class];
 
    if (g->nodes[n1].adjacency_count >=
        g->nodes[n1].adjacency_list_size) {
@@ -410,36 +461,114 @@ ra_add_node_adjacency(struct ra_graph *g, unsigned int n1, unsigned int n2)
    g->nodes[n1].adjacency_count++;
 }
 
-struct ra_graph *
-ra_alloc_interference_graph(struct ra_regs *regs, unsigned int count)
+static void
+ra_node_remove_adjacency(struct ra_graph *g, unsigned int n1, unsigned int n2)
 {
-   struct ra_graph *g;
+   BITSET_CLEAR(g->nodes[n1].adjacency, n2);
+
+   assert(n1 != n2);
+
+   int n1_class = g->nodes[n1].class;
+   int n2_class = g->nodes[n2].class;
+   g->nodes[n1].q_total -= g->regs->classes[n1_class]->q[n2_class];
+
    unsigned int i;
+   for (i = 0; i < g->nodes[n1].adjacency_count; i++) {
+      if (g->nodes[n1].adjacency_list[i] == n2) {
+         memmove(&g->nodes[n1].adjacency_list[i],
+                 &g->nodes[n1].adjacency_list[i + 1],
+                 (g->nodes[n1].adjacency_count - i - 1) *
+                 sizeof(g->nodes[n1].adjacency_list[0]));
+         break;
+      }
+   }
+   assert(i < g->nodes[n1].adjacency_count);
+   g->nodes[n1].adjacency_count--;
+}
 
-   g = rzalloc(NULL, struct ra_graph);
-   g->regs = regs;
-   g->nodes = rzalloc_array(g, struct ra_node, count);
-   g->count = count;
+static void
+ra_realloc_interference_graph(struct ra_graph *g, unsigned int alloc)
+{
+   if (alloc <= g->alloc)
+      return;
 
-   g->stack = rzalloc_array(g, unsigned int, count);
+   /* If we always have a whole number of BITSET_WORDs, it makes it much
+    * easier to memset the top of the growing bitsets.
+    */
+   assert(g->alloc % BITSET_WORDBITS == 0);
+   alloc = ALIGN(alloc, BITSET_WORDBITS);
+
+   g->nodes = reralloc(g, g->nodes, struct ra_node, alloc);
+
+   unsigned g_bitset_count = BITSET_WORDS(g->alloc);
+   unsigned bitset_count = BITSET_WORDS(alloc);
+   /* For nodes already in the graph, we just have to grow the adjacency set */
+   for (unsigned i = 0; i < g->alloc; i++) {
+      assert(g->nodes[i].adjacency != NULL);
+      g->nodes[i].adjacency = rerzalloc(g, g->nodes[i].adjacency, BITSET_WORD,
+                                        g_bitset_count, bitset_count);
+   }
 
-   for (i = 0; i < count; i++) {
-      int bitset_count = BITSET_WORDS(count);
+   /* For new nodes, we have to fully initialize them */
+   for (unsigned i = g->alloc; i < alloc; i++) {
+      memset(&g->nodes[i], 0, sizeof(g->nodes[i]));
       g->nodes[i].adjacency = rzalloc_array(g, BITSET_WORD, bitset_count);
-
       g->nodes[i].adjacency_list_size = 4;
       g->nodes[i].adjacency_list =
          ralloc_array(g, unsigned int, g->nodes[i].adjacency_list_size);
       g->nodes[i].adjacency_count = 0;
       g->nodes[i].q_total = 0;
 
-      ra_add_node_adjacency(g, i, i);
+      g->nodes[i].forced_reg = NO_REG;
       g->nodes[i].reg = NO_REG;
    }
 
+   /* These are scratch values and don't need to be zeroed.  We'll clear them
+    * as part of ra_select() setup.
+    */
+   g->tmp.stack = reralloc(g, g->tmp.stack, unsigned int, alloc);
+   g->tmp.in_stack = reralloc(g, g->tmp.in_stack, BITSET_WORD, bitset_count);
+
+   g->tmp.reg_assigned = reralloc(g, g->tmp.reg_assigned, BITSET_WORD,
+                                  bitset_count);
+   g->tmp.pq_test = reralloc(g, g->tmp.pq_test, BITSET_WORD, bitset_count);
+   g->tmp.min_q_total = reralloc(g, g->tmp.min_q_total, unsigned int,
+                                 bitset_count);
+   g->tmp.min_q_node = reralloc(g, g->tmp.min_q_node, unsigned int,
+                                bitset_count);
+
+   g->alloc = alloc;
+}
+
+struct ra_graph *
+ra_alloc_interference_graph(struct ra_regs *regs, unsigned int count)
+{
+   struct ra_graph *g;
+
+   g = rzalloc(NULL, struct ra_graph);
+   g->regs = regs;
+   g->count = count;
+   ra_realloc_interference_graph(g, count);
+
    return g;
 }
 
+void
+ra_resize_interference_graph(struct ra_graph *g, unsigned int count)
+{
+   g->count = count;
+   if (count > g->alloc)
+      ra_realloc_interference_graph(g, g->alloc * 2);
+}
+
+void ra_set_select_reg_callback(struct ra_graph *g,
+                                ra_select_reg_callback callback,
+                                void *data)
+{
+   g->select_reg_callback = callback;
+   g->select_reg_callback_data = data;
+}
+
 void
 ra_set_node_class(struct ra_graph *g,
                   unsigned int n, unsigned int class)
@@ -447,39 +576,95 @@ ra_set_node_class(struct ra_graph *g,
    g->nodes[n].class = class;
 }
 
+unsigned int
+ra_get_node_class(struct ra_graph *g,
+                  unsigned int n)
+{
+   return g->nodes[n].class;
+}
+
+unsigned int
+ra_add_node(struct ra_graph *g, unsigned int class)
+{
+   unsigned int n = g->count;
+   ra_resize_interference_graph(g, g->count + 1);
+
+   ra_set_node_class(g, n, class);
+
+   return n;
+}
+
 void
 ra_add_node_interference(struct ra_graph *g,
                          unsigned int n1, unsigned int n2)
 {
-   if (!BITSET_TEST(g->nodes[n1].adjacency, n2)) {
+   assert(n1 < g->count && n2 < g->count);
+   if (n1 != n2 && !BITSET_TEST(g->nodes[n1].adjacency, n2)) {
       ra_add_node_adjacency(g, n1, n2);
       ra_add_node_adjacency(g, n2, n1);
    }
 }
 
-static bool
-pq_test(struct ra_graph *g, unsigned int n)
+void
+ra_reset_node_interference(struct ra_graph *g, unsigned int n)
 {
-   int n_class = g->nodes[n].class;
+   for (unsigned int i = 0; i < g->nodes[n].adjacency_count; i++)
+      ra_node_remove_adjacency(g, g->nodes[n].adjacency_list[i], n);
 
-   return g->nodes[n].q_total < g->regs->classes[n_class]->p;
+   memset(g->nodes[n].adjacency, 0,
+          BITSET_WORDS(g->count) * sizeof(BITSET_WORD));
+   g->nodes[n].adjacency_count = 0;
 }
 
 static void
-decrement_q(struct ra_graph *g, unsigned int n)
+update_pq_info(struct ra_graph *g, unsigned int n)
+{
+   int i = n / BITSET_WORDBITS;
+   int n_class = g->nodes[n].class;
+   if (g->nodes[n].tmp.q_total < g->regs->classes[n_class]->p) {
+      BITSET_SET(g->tmp.pq_test, n);
+   } else if (g->tmp.min_q_total[i] != UINT_MAX) {
+      /* Only update min_q_total and min_q_node if min_q_total != UINT_MAX so
+       * that we don't update while we have stale data and accidentally mark
+       * it as non-stale.  Also, in order to remain consistent with the old
+       * naive implementation of the algorithm, we do a lexicographical sort
+       * to ensure that we always choose the node with the highest node index.
+       */
+      if (g->nodes[n].tmp.q_total < g->tmp.min_q_total[i] ||
+          (g->nodes[n].tmp.q_total == g->tmp.min_q_total[i] &&
+           n > g->tmp.min_q_node[i])) {
+         g->tmp.min_q_total[i] = g->nodes[n].tmp.q_total;
+         g->tmp.min_q_node[i] = n;
+      }
+   }
+}
+
+static void
+add_node_to_stack(struct ra_graph *g, unsigned int n)
 {
    unsigned int i;
    int n_class = g->nodes[n].class;
 
+   assert(!BITSET_TEST(g->tmp.in_stack, n));
+
    for (i = 0; i < g->nodes[n].adjacency_count; i++) {
       unsigned int n2 = g->nodes[n].adjacency_list[i];
       unsigned int n2_class = g->nodes[n2].class;
 
-      if (n != n2 && !g->nodes[n2].in_stack) {
-         assert(g->nodes[n2].q_total >= g->regs->classes[n2_class]->q[n_class]);
-         g->nodes[n2].q_total -= g->regs->classes[n2_class]->q[n_class];
+      if (!BITSET_TEST(g->tmp.in_stack, n2) &&
+          !BITSET_TEST(g->tmp.reg_assigned, n2)) {
+         assert(g->nodes[n2].tmp.q_total >= g->regs->classes[n2_class]->q[n_class]);
+         g->nodes[n2].tmp.q_total -= g->regs->classes[n2_class]->q[n_class];
+         update_pq_info(g, n2);
       }
    }
+
+   g->tmp.stack[g->tmp.stack_count] = n;
+   g->tmp.stack_count++;
+   BITSET_SET(g->tmp.in_stack, n);
+
+   /* Flag the min_q_total for n's block as dirty so it gets recalculated */
+   g->tmp.min_q_total[n / BITSET_WORDBITS] = UINT_MAX;
 }
 
 /**
@@ -497,46 +682,100 @@ ra_simplify(struct ra_graph *g)
 {
    bool progress = true;
    unsigned int stack_optimistic_start = UINT_MAX;
-   int i;
+
+   /* Figure out the high bit and bit mask for the first iteration of a loop
+    * over BITSET_WORDs.
+    */
+   const unsigned int top_word_high_bit = (g->count - 1) % BITSET_WORDBITS;
+
+   /* Do a quick pre-pass to set things up */
+   g->tmp.stack_count = 0;
+   for (int i = BITSET_WORDS(g->count) - 1, high_bit = top_word_high_bit;
+        i >= 0; i--, high_bit = BITSET_WORDBITS - 1) {
+      g->tmp.in_stack[i] = 0;
+      g->tmp.reg_assigned[i] = 0;
+      g->tmp.pq_test[i] = 0;
+      g->tmp.min_q_total[i] = UINT_MAX;
+      g->tmp.min_q_node[i] = UINT_MAX;
+      for (int j = high_bit; j >= 0; j--) {
+         unsigned int n = i * BITSET_WORDBITS + j;
+         g->nodes[n].reg = g->nodes[n].forced_reg;
+         g->nodes[n].tmp.q_total = g->nodes[n].q_total;
+         if (g->nodes[n].reg != NO_REG)
+            g->tmp.reg_assigned[i] |= BITSET_BIT(j);
+         update_pq_info(g, n);
+      }
+   }
 
    while (progress) {
-      unsigned int best_optimistic_node = ~0;
-      unsigned int lowest_q_total = ~0;
+      unsigned int min_q_total = UINT_MAX;
+      unsigned int min_q_node = UINT_MAX;
 
       progress = false;
 
-      for (i = g->count - 1; i >= 0; i--) {
-	 if (g->nodes[i].in_stack || g->nodes[i].reg != NO_REG)
-	    continue;
-
-	 if (pq_test(g, i)) {
-	    decrement_q(g, i);
-	    g->stack[g->stack_count] = i;
-	    g->stack_count++;
-	    g->nodes[i].in_stack = true;
-	    progress = true;
-	 } else {
-	    unsigned int new_q_total = g->nodes[i].q_total;
-	    if (new_q_total < lowest_q_total) {
-	       best_optimistic_node = i;
-	       lowest_q_total = new_q_total;
-	    }
-	 }
+      for (int i = BITSET_WORDS(g->count) - 1, high_bit = top_word_high_bit;
+           i >= 0; i--, high_bit = BITSET_WORDBITS - 1) {
+         BITSET_WORD mask = ~(BITSET_WORD)0 >> (31 - high_bit);
+
+         BITSET_WORD skip = g->tmp.in_stack[i] | g->tmp.reg_assigned[i];
+         if (skip == mask)
+            continue;
+
+         BITSET_WORD pq = g->tmp.pq_test[i] & ~skip;
+         if (pq) {
+            /* In this case, we have stuff we can immediately take off the
+             * stack.  This also means that we're guaranteed to make progress
+             * and we don't need to bother updating lowest_q_total because we
+             * know we're going to loop again before attempting to do anything
+             * optimistic.
+             */
+            for (int j = high_bit; j >= 0; j--) {
+               if (pq & BITSET_BIT(j)) {
+                  unsigned int n = i * BITSET_WORDBITS + j;
+                  assert(n < g->count);
+                  add_node_to_stack(g, n);
+                  /* add_node_to_stack() may update pq_test for this word so
+                   * we need to update our local copy.
+                   */
+                  pq = g->tmp.pq_test[i] & ~skip;
+                  progress = true;
+               }
+            }
+         } else if (!progress) {
+            if (g->tmp.min_q_total[i] == UINT_MAX) {
+               /* The min_q_total and min_q_node are dirty because we added
+                * one of these nodes to the stack.  It needs to be
+                * recalculated.
+                */
+               for (int j = high_bit; j >= 0; j--) {
+                  if (skip & BITSET_BIT(j))
+                     continue;
+
+                  unsigned int n = i * BITSET_WORDBITS + j;
+                  assert(n < g->count);
+                  if (g->nodes[n].tmp.q_total < g->tmp.min_q_total[i]) {
+                     g->tmp.min_q_total[i] = g->nodes[n].tmp.q_total;
+                     g->tmp.min_q_node[i] = n;
+                  }
+               }
+            }
+            if (g->tmp.min_q_total[i] < min_q_total) {
+               min_q_node = g->tmp.min_q_node[i];
+               min_q_total = g->tmp.min_q_total[i];
+            }
+         }
       }
 
-      if (!progress && best_optimistic_node != ~0U) {
+      if (!progress && min_q_total != UINT_MAX) {
          if (stack_optimistic_start == UINT_MAX)
-            stack_optimistic_start = g->stack_count;
+            stack_optimistic_start = g->tmp.stack_count;
 
-	 decrement_q(g, best_optimistic_node);
-	 g->stack[g->stack_count] = best_optimistic_node;
-	 g->stack_count++;
-	 g->nodes[best_optimistic_node].in_stack = true;
-	 progress = true;
+         add_node_to_stack(g, min_q_node);
+         progress = true;
       }
    }
 
-   g->stack_optimistic_start = stack_optimistic_start;
+   g->tmp.stack_optimistic_start = stack_optimistic_start;
 }
 
 static bool
@@ -547,7 +786,7 @@ ra_any_neighbors_conflict(struct ra_graph *g, unsigned int n, unsigned int r)
    for (i = 0; i < g->nodes[n].adjacency_count; i++) {
       unsigned int n2 = g->nodes[n].adjacency_list[i];
 
-      if (!g->nodes[n2].in_stack &&
+      if (!BITSET_TEST(g->tmp.in_stack, n2) &&
           BITSET_TEST(g->regs->regs[r].conflicts, g->nodes[n2].reg)) {
          return true;
       }
@@ -556,6 +795,41 @@ ra_any_neighbors_conflict(struct ra_graph *g, unsigned int n, unsigned int r)
    return false;
 }
 
+/* Computes a bitfield of what regs are available for a given register
+ * selection.
+ *
+ * This lets drivers implement a more complicated policy than our simple first
+ * or round robin policies (which don't require knowing the whole bitset)
+ */
+static bool
+ra_compute_available_regs(struct ra_graph *g, unsigned int n, BITSET_WORD *regs)
+{
+   struct ra_class *c = g->regs->classes[g->nodes[n].class];
+
+   /* Populate with the set of regs that are in the node's class. */
+   memcpy(regs, c->regs, BITSET_WORDS(g->regs->count) * sizeof(BITSET_WORD));
+
+   /* Remove any regs that conflict with nodes that we're adjacent to and have
+    * already colored.
+    */
+   for (int i = 0; i < g->nodes[n].adjacency_count; i++) {
+      unsigned int n2 = g->nodes[n].adjacency_list[i];
+      unsigned int r = g->nodes[n2].reg;
+
+      if (!BITSET_TEST(g->tmp.in_stack, n2)) {
+         for (int j = 0; j < BITSET_WORDS(g->regs->count); j++)
+            regs[j] &= ~g->regs->regs[r].conflicts[j];
+      }
+   }
+
+   for (int i = 0; i < BITSET_WORDS(g->regs->count); i++) {
+      if (regs[i])
+         return true;
+   }
+
+   return false;
+}
+
 /**
  * Pops nodes from the stack back into the graph, coloring them with
  * registers as they go.
@@ -567,35 +841,48 @@ static bool
 ra_select(struct ra_graph *g)
 {
    int start_search_reg = 0;
+   BITSET_WORD *select_regs = NULL;
+
+   if (g->select_reg_callback)
+      select_regs = malloc(BITSET_WORDS(g->regs->count) * sizeof(BITSET_WORD));
 
-   while (g->stack_count != 0) {
+   while (g->tmp.stack_count != 0) {
       unsigned int ri;
       unsigned int r = -1;
-      int n = g->stack[g->stack_count - 1];
+      int n = g->tmp.stack[g->tmp.stack_count - 1];
       struct ra_class *c = g->regs->classes[g->nodes[n].class];
 
-      /* Find the lowest-numbered reg which is not used by a member
-       * of the graph adjacent to us.
-       */
-      for (ri = 0; ri < g->regs->count; ri++) {
-         r = (start_search_reg + ri) % g->regs->count;
-         if (!reg_belongs_to_class(r, c))
-	    continue;
-
-         if (!ra_any_neighbors_conflict(g, n, r))
-            break;
-      }
-
       /* set this to false even if we return here so that
        * ra_get_best_spill_node() considers this node later.
        */
-      g->nodes[n].in_stack = false;
+      BITSET_CLEAR(g->tmp.in_stack, n);
 
-      if (ri == g->regs->count)
-	 return false;
+      if (g->select_reg_callback) {
+         if (!ra_compute_available_regs(g, n, select_regs)) {
+            free(select_regs);
+            return false;
+         }
+
+         r = g->select_reg_callback(n, select_regs, g->select_reg_callback_data);
+      } else {
+         /* Find the lowest-numbered reg which is not used by a member
+          * of the graph adjacent to us.
+          */
+         for (ri = 0; ri < g->regs->count; ri++) {
+            r = (start_search_reg + ri) % g->regs->count;
+            if (!reg_belongs_to_class(r, c))
+               continue;
+
+            if (!ra_any_neighbors_conflict(g, n, r))
+               break;
+         }
+
+         if (ri >= g->regs->count)
+            return false;
+      }
 
       g->nodes[n].reg = r;
-      g->stack_count--;
+      g->tmp.stack_count--;
 
       /* Rotate the starting point except for any nodes above the lowest
        * optimistically colorable node.  The likelihood that we will succeed
@@ -607,10 +894,12 @@ ra_select(struct ra_graph *g)
        * dense packing strategy.
        */
       if (g->regs->round_robin &&
-          g->stack_count - 1 <= g->stack_optimistic_start)
+          g->tmp.stack_count - 1 <= g->tmp.stack_optimistic_start)
          start_search_reg = r + 1;
    }
 
+   free(select_regs);
+
    return true;
 }
 
@@ -624,7 +913,10 @@ ra_allocate(struct ra_graph *g)
 unsigned int
 ra_get_node_reg(struct ra_graph *g, unsigned int n)
 {
-   return g->nodes[n].reg;
+   if (g->nodes[n].forced_reg != NO_REG)
+      return g->nodes[n].forced_reg;
+   else
+      return g->nodes[n].reg;
 }
 
 /**
@@ -643,8 +935,7 @@ ra_get_node_reg(struct ra_graph *g, unsigned int n)
 void
 ra_set_node_reg(struct ra_graph *g, unsigned int n, unsigned int reg)
 {
-   g->nodes[n].reg = reg;
-   g->nodes[n].in_stack = false;
+   g->nodes[n].forced_reg = reg;
 }
 
 static float
@@ -661,11 +952,9 @@ ra_get_spill_benefit(struct ra_graph *g, unsigned int n)
     */
    for (j = 0; j < g->nodes[n].adjacency_count; j++) {
       unsigned int n2 = g->nodes[n].adjacency_list[j];
-      if (n != n2) {
-	 unsigned int n2_class = g->nodes[n2].class;
-	 benefit += ((float)g->regs->classes[n_class]->q[n2_class] /
-		     g->regs->classes[n_class]->p);
-      }
+      unsigned int n2_class = g->nodes[n2].class;
+      benefit += ((float)g->regs->classes[n_class]->q[n2_class] /
+                  g->regs->classes[n_class]->p);
    }
 
    return benefit;
@@ -692,16 +981,16 @@ ra_get_best_spill_node(struct ra_graph *g)
       float benefit;
 
       if (cost <= 0.0f)
-	 continue;
+         continue;
 
-      if (g->nodes[n].in_stack)
+      if (BITSET_TEST(g->tmp.in_stack, n))
          continue;
 
       benefit = ra_get_spill_benefit(g, n);
 
       if (benefit / cost > best_benefit) {
-	 best_benefit = benefit / cost;
-	 best_node = n;
+         best_benefit = benefit / cost;
+         best_node = n;
       }
    }