diff options
Diffstat (limited to 'mesalib/src/mesa/program/register_allocate.c')
| -rw-r--r-- | mesalib/src/mesa/program/register_allocate.c | 145 |
1 files changed, 61 insertions, 84 deletions
diff --git a/mesalib/src/mesa/program/register_allocate.c b/mesalib/src/mesa/program/register_allocate.c index 549154e8a..db2be5dfa 100644 --- a/mesalib/src/mesa/program/register_allocate.c +++ b/mesalib/src/mesa/program/register_allocate.c @@ -146,6 +146,12 @@ struct ra_node { */ bool in_stack; + /** + * The q total, as defined in the Runeson/Nyström paper, for all the + * interfering nodes not in the stack. + */ + unsigned int q_total; + /* For an implementation that needs register spilling, this is the * approximate cost of spilling this node. */ @@ -162,16 +168,6 @@ 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; }; /** @@ -354,6 +350,12 @@ 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]; + } + if (g->nodes[n1].adjacency_count >= g->nodes[n1].adjacency_list_size) { g->nodes[n1].adjacency_list_size *= 2; @@ -387,6 +389,7 @@ ra_alloc_interference_graph(struct ra_regs *regs, unsigned int count) 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].reg = NO_REG; @@ -415,20 +418,25 @@ ra_add_node_interference(struct ra_graph *g, static bool pq_test(struct ra_graph *g, unsigned int n) { - unsigned int j; - unsigned int q = 0; int n_class = g->nodes[n].class; - for (j = 0; j < g->nodes[n].adjacency_count; j++) { - unsigned int n2 = g->nodes[n].adjacency_list[j]; + return g->nodes[n].q_total < g->regs->classes[n_class]->p; +} + +static void +decrement_q(struct ra_graph *g, unsigned int n) +{ + unsigned int i; + int n_class = g->nodes[n].class; + + 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) { - q += g->regs->classes[n_class]->q[n2_class]; + g->nodes[n2].q_total -= g->regs->classes[n2_class]->q[n_class]; } } - - return q < g->regs->classes[n_class]->p; } /** @@ -436,17 +444,21 @@ pq_test(struct ra_graph *g, unsigned int n) * trivially-colorable nodes into a stack of nodes to be colored, * removing them from the graph, and rinsing and repeating. * - * Returns true if all nodes were removed from the graph. false - * means that either spilling will be required, or optimistic coloring - * should be applied. + * If we encounter a case where we can't push any nodes on the stack, then + * we optimistically choose a node and push it on the stack. We heuristically + * push the node with the lowest total q value, since it has the fewest + * neighbors and therefore is most likely to be allocated. */ -bool +static void ra_simplify(struct ra_graph *g) { bool progress = true; int i; while (progress) { + unsigned int best_optimistic_node = ~0; + unsigned int lowest_q_total = ~0; + progress = false; for (i = g->count - 1; i >= 0; i--) { @@ -454,20 +466,28 @@ ra_simplify(struct ra_graph *g) 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 (i = 0; i < g->count; i++) { - if (!g->nodes[i].in_stack && g->nodes[i].reg == -1) - return false; + if (!progress && best_optimistic_node != ~0) { + 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; + } } - - return true; } /** @@ -477,7 +497,7 @@ ra_simplify(struct ra_graph *g) * If all nodes were trivially colorable, then this must succeed. If * not (optimistic coloring), then it may return false; */ -bool +static bool ra_select(struct ra_graph *g) { int i; @@ -509,11 +529,16 @@ ra_select(struct ra_graph *g) if (i == g->nodes[n].adjacency_count) 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; + if (ri == g->regs->count) return false; g->nodes[n].reg = r; - g->nodes[n].in_stack = false; g->stack_count--; if (g->regs->round_robin) @@ -523,35 +548,10 @@ ra_select(struct ra_graph *g) return true; } -/** - * Optimistic register coloring: Just push the remaining nodes - * on the stack. They'll be colored first in ra_select(), and - * if they succeed then the locally-colorable nodes are still - * locally-colorable and the rest of the register allocation - * will succeed. - */ -void -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; - - g->stack[g->stack_count] = i; - g->stack_count++; - g->nodes[i].in_stack = true; - } -} - bool -ra_allocate_no_spills(struct ra_graph *g) +ra_allocate(struct ra_graph *g) { - if (!ra_simplify(g)) { - ra_optimistic_color(g); - } + ra_simplify(g); return ra_select(g); } @@ -614,15 +614,12 @@ ra_get_best_spill_node(struct ra_graph *g) { unsigned int best_node = -1; float best_benefit = 0.0; - unsigned int n, i; + unsigned int n; - /* 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(). + /* Consider any nodes that we colored successfully or the node we failed to + * color for spilling. When we failed to color a node in ra_select(), we + * only considered these nodes, so spilling any other ones would not result + * in us making progress. */ for (n = 0; n < g->count; n++) { float cost = g->nodes[n].spill_cost; @@ -642,26 +639,6 @@ 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++) { - float cost, benefit; - - n = g->stack[i]; - cost = g->nodes[n].spill_cost; - - 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; } |