X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Futil%2Fregister_allocate.c;h=2ad8c3ce11a1611cb3e561cf77a3bdb6da5c58ef;hb=dfb274af4c6e0991fa20af1606e45bea6f947fed;hp=afab9ddd31d8b04c9f7ed3c711770c2dd1502baa;hpb=517e01b5c3db9ba750698096e823134b288e213f;p=mesa.git

diff --git a/src/util/register_allocate.c b/src/util/register_allocate.c
index afab9ddd31d..2ad8c3ce11a 100644
--- a/src/util/register_allocate.c
+++ b/src/util/register_allocate.c
@@ -76,10 +76,10 @@
 #include "main/imports.h"
 #include "main/macros.h"
 #include "main/mtypes.h"
-#include "main/bitset.h"
+#include "util/bitset.h"
 #include "register_allocate.h"
 
-#define NO_REG ~0
+#define NO_REG ~0U
 
 struct ra_reg {
    BITSET_WORD *conflicts;
@@ -168,6 +168,12 @@ struct ra_graph {
 
    unsigned int *stack;
    unsigned int stack_count;
+
+   /**
+    * Tracks the start of the set of optimistically-colored registers in the
+    * stack.
+    */
+   unsigned int stack_optimistic_start;
 };
 
 /**
@@ -251,7 +257,7 @@ void
 ra_add_transitive_reg_conflict(struct ra_regs *regs,
 			       unsigned int base_reg, unsigned int reg)
 {
-   int i;
+   unsigned int i;
 
    ra_add_reg_conflict(regs, reg, base_reg);
 
@@ -328,14 +334,14 @@ ra_set_finalize(struct ra_regs *regs, unsigned int **q_values)
 
 	 for (rc = 0; rc < regs->count; rc++) {
 	    int conflicts = 0;
-	    int i;
+	    unsigned int i;
 
             if (!reg_belongs_to_class(rc, regs->classes[c]))
 	       continue;
 
 	    for (i = 0; i < regs->regs[rc].num_conflicts; i++) {
 	       unsigned int rb = regs->regs[rc].conflict_list[i];
-	       if (BITSET_TEST(regs->classes[b]->regs, rb))
+	       if (reg_belongs_to_class(rb, regs->classes[b]))
 		  conflicts++;
 	    }
 	    max_conflicts = MAX2(max_conflicts, conflicts);
@@ -374,7 +380,7 @@ ra_alloc_interference_graph(struct ra_regs *regs, unsigned int count)
    struct ra_graph *g;
    unsigned int i;
 
-   g = rzalloc(regs, struct ra_graph);
+   g = rzalloc(NULL, struct ra_graph);
    g->regs = regs;
    g->nodes = rzalloc_array(g, struct ra_node, count);
    g->count = count;
@@ -454,6 +460,7 @@ static void
 ra_simplify(struct ra_graph *g)
 {
    bool progress = true;
+   unsigned int stack_optimistic_start = UINT_MAX;
    int i;
 
    while (progress) {
@@ -481,7 +488,10 @@ ra_simplify(struct ra_graph *g)
 	 }
       }
 
-      if (!progress && best_optimistic_node != ~0) {
+      if (!progress && best_optimistic_node != ~0U) {
+         if (stack_optimistic_start == UINT_MAX)
+            stack_optimistic_start = g->stack_count;
+
 	 decrement_q(g, best_optimistic_node);
 	 g->stack[g->stack_count] = best_optimistic_node;
 	 g->stack_count++;
@@ -489,6 +499,8 @@ ra_simplify(struct ra_graph *g)
 	 progress = true;
       }
    }
+
+   g->stack_optimistic_start = stack_optimistic_start;
 }
 
 /**
@@ -501,10 +513,10 @@ ra_simplify(struct ra_graph *g)
 static bool
 ra_select(struct ra_graph *g)
 {
-   int i;
    int start_search_reg = 0;
 
    while (g->stack_count != 0) {
+      unsigned int i;
       unsigned int ri;
       unsigned int r = -1;
       int n = g->stack[g->stack_count - 1];
@@ -542,7 +554,17 @@ ra_select(struct ra_graph *g)
       g->nodes[n].reg = r;
       g->stack_count--;
 
-      if (g->regs->round_robin)
+      /* Rotate the starting point except for any nodes above the lowest
+       * optimistically colorable node.  The likelihood that we will succeed
+       * at allocating optimistically colorable nodes is highly dependent on
+       * the way that the previous nodes popped off the stack are laid out.
+       * The round-robin strategy increases the fragmentation of the register
+       * file and decreases the number of nearby nodes assigned to the same
+       * color, what increases the likelihood of spilling with respect to the
+       * dense packing strategy.
+       */
+      if (g->regs->round_robin &&
+          g->stack_count - 1 <= g->stack_optimistic_start)
          start_search_reg = r + 1;
    }
 
@@ -585,7 +607,7 @@ ra_set_node_reg(struct ra_graph *g, unsigned int n, unsigned int reg)
 static float
 ra_get_spill_benefit(struct ra_graph *g, unsigned int n)
 {
-   int j;
+   unsigned int j;
    float benefit = 0;
    int n_class = g->nodes[n].class;