X-Git-Url: https://git.libre-soc.org/?p=mesa.git;a=blobdiff_plain;f=src%2Futil%2Fregister_allocate.c;h=56517b5161cd834b817cffe42b1e8310ba984ea5;hp=afab9ddd31d8b04c9f7ed3c711770c2dd1502baa;hb=36aed70b591f7f4f642b26f46f7928be6d137e7b;hpb=517e01b5c3db9ba750698096e823134b288e213f diff --git a/src/util/register_allocate.c b/src/util/register_allocate.c index afab9ddd31d..56517b5161c 100644 --- a/src/util/register_allocate.c +++ b/src/util/register_allocate.c @@ -75,11 +75,10 @@ #include "ralloc.h" #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; @@ -135,17 +134,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 +150,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,8 +169,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. */ + + 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; }; /** @@ -177,7 +212,7 @@ struct ra_graph { * using ralloc_free(). */ struct ra_regs * -ra_alloc_reg_set(void *mem_ctx, unsigned int count) +ra_alloc_reg_set(void *mem_ctx, unsigned int count, bool need_conflict_lists) { unsigned int i; struct ra_regs *regs; @@ -191,9 +226,15 @@ ra_alloc_reg_set(void *mem_ctx, unsigned int count) BITSET_WORDS(count)); BITSET_SET(regs->regs[i].conflicts, i); - regs->regs[i].conflict_list = ralloc_array(regs->regs, unsigned int, 4); - regs->regs[i].conflict_list_size = 4; - regs->regs[i].conflict_list[0] = i; + if (need_conflict_lists) { + regs->regs[i].conflict_list = ralloc_array(regs->regs, + unsigned int, 4); + regs->regs[i].conflict_list_size = 4; + regs->regs[i].conflict_list[0] = i; + } else { + regs->regs[i].conflict_list = NULL; + regs->regs[i].conflict_list_size = 0; + } regs->regs[i].num_conflicts = 1; } @@ -221,12 +262,14 @@ ra_add_conflict_list(struct ra_regs *regs, unsigned int r1, unsigned int r2) { struct ra_reg *reg1 = ®s->regs[r1]; - if (reg1->conflict_list_size == reg1->num_conflicts) { - reg1->conflict_list_size *= 2; - reg1->conflict_list = reralloc(regs->regs, reg1->conflict_list, - unsigned int, reg1->conflict_list_size); + if (reg1->conflict_list) { + if (reg1->conflict_list_size == reg1->num_conflicts) { + reg1->conflict_list_size *= 2; + reg1->conflict_list = reralloc(regs->regs, reg1->conflict_list, + unsigned int, reg1->conflict_list_size); + } + reg1->conflict_list[reg1->num_conflicts++] = r2; } - reg1->conflict_list[reg1->num_conflicts++] = r2; BITSET_SET(reg1->conflicts, r2); } @@ -249,9 +292,9 @@ ra_add_reg_conflict(struct ra_regs *regs, unsigned int r1, unsigned int r2) */ void ra_add_transitive_reg_conflict(struct ra_regs *regs, - unsigned int base_reg, unsigned int reg) + unsigned int base_reg, unsigned int reg) { - int i; + unsigned int i; ra_add_reg_conflict(regs, reg, base_reg); @@ -260,13 +303,61 @@ 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 + * register conflicting with r. + * + * This can simplify code for setting up multiple register classes + * which are aggregates of some base hardware registers, compared to + * explicitly using ra_add_reg_conflict. + */ +void +ra_make_reg_conflicts_transitive(struct ra_regs *regs, unsigned int r) +{ + struct ra_reg *reg = ®s->regs[r]; + int c; + + BITSET_FOREACH_SET(c, reg->conflicts, regs->count) { + struct ra_reg *other = ®s->regs[c]; + unsigned i; + for (i = 0; i < BITSET_WORDS(regs->count); i++) + other->conflicts[i] |= reg->conflicts[i]; + } +} + unsigned int ra_alloc_reg_class(struct ra_regs *regs) { struct ra_class *class; regs->classes = reralloc(regs->regs, regs->classes, struct ra_class *, - regs->class_count + 1); + regs->class_count + 1); class = rzalloc(regs, struct ra_class); regs->classes[regs->class_count] = class; @@ -313,35 +404,39 @@ ra_set_finalize(struct ra_regs *regs, unsigned int **q_values) for (b = 0; b < regs->class_count; b++) { for (c = 0; c < regs->class_count; c++) { regs->classes[b]->q[c] = q_values[b][c]; - } + } + } + } else { + /* Compute, for each class B and C, how many regs of B an + * allocation to C could conflict with. + */ + for (b = 0; b < regs->class_count; b++) { + for (c = 0; c < regs->class_count; c++) { + unsigned int rc; + int max_conflicts = 0; + + for (rc = 0; rc < regs->count; rc++) { + int conflicts = 0; + 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 (reg_belongs_to_class(rb, regs->classes[b])) + conflicts++; + } + max_conflicts = MAX2(max_conflicts, conflicts); + } + regs->classes[b]->q[c] = max_conflicts; + } } - return; } - /* Compute, for each class B and C, how many regs of B an - * allocation to C could conflict with. - */ - for (b = 0; b < regs->class_count; b++) { - for (c = 0; c < regs->class_count; c++) { - unsigned int rc; - int max_conflicts = 0; - - for (rc = 0; rc < regs->count; rc++) { - int conflicts = 0; - 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)) - conflicts++; - } - max_conflicts = MAX2(max_conflicts, conflicts); - } - regs->classes[b]->q[c] = max_conflicts; - } + for (b = 0; b < regs->count; b++) { + ralloc_free(regs->regs[b].conflict_list); + regs->regs[b].conflict_list = NULL; } } @@ -350,11 +445,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) { @@ -368,76 +463,210 @@ 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(regs, 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) + unsigned int n, unsigned int class) { 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) + 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); + + memset(g->nodes[n].adjacency, 0, + BITSET_WORDS(g->count) * sizeof(BITSET_WORD)); + g->nodes[n].adjacency_count = 0; +} - return g->nodes[n].q_total < g->regs->classes[n_class]->p; +static void +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 -decrement_q(struct ra_graph *g, unsigned int n) +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; } /** @@ -454,41 +683,153 @@ static void ra_simplify(struct ra_graph *g) { bool progress = true; - int i; + unsigned int stack_optimistic_start = UINT_MAX; + + /* 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 && min_q_total != UINT_MAX) { + if (stack_optimistic_start == UINT_MAX) + stack_optimistic_start = g->tmp.stack_count; + + add_node_to_stack(g, min_q_node); + progress = true; + } + } + + g->tmp.stack_optimistic_start = stack_optimistic_start; +} + +static bool +ra_any_neighbors_conflict(struct ra_graph *g, unsigned int n, unsigned int r) +{ + unsigned int i; + + for (i = 0; i < g->nodes[n].adjacency_count; i++) { + unsigned int n2 = g->nodes[n].adjacency_list[i]; + + if (!BITSET_TEST(g->tmp.in_stack, n2) && + BITSET_TEST(g->regs->regs[r].conflicts, g->nodes[n2].reg)) { + return true; } + } + + 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 (!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; + 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; } /** @@ -501,51 +842,66 @@ ra_simplify(struct ra_graph *g) static bool ra_select(struct ra_graph *g) { - int i; int start_search_reg = 0; + BITSET_WORD *select_regs = NULL; - while (g->stack_count != 0) { + if (g->select_reg_callback) + select_regs = malloc(BITSET_WORDS(g->regs->count) * sizeof(BITSET_WORD)); + + 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; - - /* Check if any of our neighbors conflict with this register choice. */ - 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 && - BITSET_TEST(g->regs->regs[r].conflicts, g->nodes[n2].reg)) { - break; - } - } - 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; + BITSET_CLEAR(g->tmp.in_stack, n); + + 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--; - - if (g->regs->round_robin) + g->tmp.stack_count--; + + /* 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->tmp.stack_count - 1 <= g->tmp.stack_optimistic_start) start_search_reg = r + 1; } + free(select_regs); + return true; } @@ -559,7 +915,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; } /** @@ -578,14 +937,13 @@ 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 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; @@ -596,11 +954,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; @@ -626,17 +982,17 @@ ra_get_best_spill_node(struct ra_graph *g) float cost = g->nodes[n].spill_cost; float benefit; - if (cost <= 0.0) - continue; + if (cost <= 0.0f) + 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; } }