#include <stdbool.h>
#include "ralloc.h"
-#include "main/imports.h"
+#include "util/imports.h"
#include "main/macros.h"
#include "util/bitset.h"
#include "register_allocate.h"
-#define NO_REG ~0U
-
struct ra_reg {
BITSET_WORD *conflicts;
unsigned int *conflict_list;
unsigned int class;
+ /* Client-assigned register, if assigned, or NO_REG. */
+ unsigned int forced_reg;
+
/* Register, if assigned, or NO_REG. */
unsigned int reg;
* 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 {
unsigned int alloc; /**< count of nodes allocated. */
- unsigned int *stack;
- unsigned int stack_count;
+ ra_select_reg_callback select_reg_callback;
+ void *select_reg_callback_data;
- /** Bit-set indicating, for each register, if it's in the stack */
- BITSET_WORD *in_stack;
+ /* 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 pre-assigned */
- BITSET_WORD *reg_assigned;
+ /** Bit-set indicating, for each register, if it's in the stack */
+ BITSET_WORD *in_stack;
- /** Bit-set indicating, for each register, the value of the pq test */
- BITSET_WORD *pq_test;
+ /** Bit-set indicating, for each register, if it pre-assigned */
+ BITSET_WORD *reg_assigned;
- /** For each BITSET_WORD, the minimum q value or ~0 if unknown */
- unsigned int *min_q_total;
+ /** Bit-set indicating, for each register, the value of the pq test */
+ BITSET_WORD *pq_test;
- /*
- * * For each BITSET_WORD, the node with the minimum q_total if
- * min_q_total[i] != ~0.
- */
- unsigned int *min_q_node;
+ /** For each BITSET_WORD, the minimum q value or ~0 if unknown */
+ unsigned int *min_q_total;
- /**
- * Tracks the start of the set of optimistically-colored registers in the
- * stack.
- */
- unsigned int stack_optimistic_start;
+ /*
+ * * For each BITSET_WORD, the node with the minimum q_total if
+ * min_q_total[i] != ~0.
+ */
+ unsigned int *min_q_node;
- unsigned int (*select_reg_callback)(struct ra_graph *g, BITSET_WORD *regs,
- void *data);
- void *select_reg_callback_data;
+ /**
+ * Tracks the start of the set of optimistically-colored registers in the
+ * stack.
+ */
+ unsigned int stack_optimistic_start;
+ } tmp;
};
/**
}
}
+/**
+ * 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
ra_make_reg_conflicts_transitive(struct ra_regs *regs, unsigned int r)
{
struct ra_reg *reg = ®s->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 = ®s->regs[c];
unsigned i;
for (i = 0; i < BITSET_WORDS(regs->count); i++)
g->nodes[n1].adjacency_count++;
}
+static void
+ra_node_remove_adjacency(struct ra_graph *g, unsigned int n1, unsigned int n2)
+{
+ 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--;
+}
+
static void
ra_realloc_interference_graph(struct ra_graph *g, unsigned int alloc)
{
g->nodes[i].adjacency_count = 0;
g->nodes[i].q_total = 0;
+ g->nodes[i].forced_reg = NO_REG;
g->nodes[i].reg = NO_REG;
}
- g->stack = reralloc(g, g->stack, unsigned int, alloc);
- g->in_stack = rerzalloc(g, g->in_stack, BITSET_WORD,
- g_bitset_count, bitset_count);
+ /* 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->reg_assigned = rerzalloc(g, g->reg_assigned, BITSET_WORD,
- g_bitset_count, bitset_count);
- g->pq_test = rerzalloc(g, g->pq_test, BITSET_WORD,
- g_bitset_count, bitset_count);
- g->min_q_total = rerzalloc(g, g->min_q_total, unsigned int,
- g_bitset_count, bitset_count);
- g->min_q_node = rerzalloc(g, g->min_q_node, unsigned int,
- g_bitset_count, 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;
}
}
void ra_set_select_reg_callback(struct ra_graph *g,
- unsigned int (*callback)(struct ra_graph *g,
- BITSET_WORD *regs,
- void *data),
+ ra_select_reg_callback callback,
void *data)
{
g->select_reg_callback = callback;
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)
{
ra_add_node_interference(struct ra_graph *g,
unsigned int n1, unsigned int 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);
}
}
+void
+ra_reset_node_interference(struct ra_graph *g, unsigned int n)
+{
+ 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;
+}
+
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].q_total < g->regs->classes[n_class]->p) {
- BITSET_SET(g->pq_test, n);
- } else if (g->min_q_total[i] != UINT_MAX) {
+ 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].q_total < g->min_q_total[i] ||
- (g->nodes[n].q_total == g->min_q_total[i] &&
- n > g->min_q_node[i])) {
- g->min_q_total[i] = g->nodes[n].q_total;
- g->min_q_node[i] = n;
+ 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;
}
}
}
unsigned int i;
int n_class = g->nodes[n].class;
- assert(!BITSET_TEST(g->in_stack, n));
+ 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 (!BITSET_TEST(g->in_stack, n2) && !BITSET_TEST(g->reg_assigned, n2)) {
- 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->stack[g->stack_count] = n;
- g->stack_count++;
- BITSET_SET(g->in_stack, n);
+ 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->min_q_total[n / BITSET_WORDBITS] = UINT_MAX;
+ g->tmp.min_q_total[n / BITSET_WORDBITS] = UINT_MAX;
}
/**
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->min_q_total[i] = UINT_MAX;
- g->min_q_node[i] = UINT_MAX;
+ 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->reg_assigned[i] |= BITSET_BIT(j);
+ g->tmp.reg_assigned[i] |= BITSET_BIT(j);
update_pq_info(g, n);
}
}
i >= 0; i--, high_bit = BITSET_WORDBITS - 1) {
BITSET_WORD mask = ~(BITSET_WORD)0 >> (31 - high_bit);
- BITSET_WORD skip = g->in_stack[i] | g->reg_assigned[i];
+ BITSET_WORD skip = g->tmp.in_stack[i] | g->tmp.reg_assigned[i];
if (skip == mask)
continue;
- BITSET_WORD pq = g->pq_test[i] & ~skip;
+ 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
/* add_node_to_stack() may update pq_test for this word so
* we need to update our local copy.
*/
- pq = g->pq_test[i] & ~skip;
+ pq = g->tmp.pq_test[i] & ~skip;
progress = true;
}
}
} else if (!progress) {
- if (g->min_q_total[i] == UINT_MAX) {
+ 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.
unsigned int n = i * BITSET_WORDBITS + j;
assert(n < g->count);
- if (g->nodes[n].q_total < g->min_q_total[i]) {
- g->min_q_total[i] = g->nodes[n].q_total;
- g->min_q_node[i] = n;
+ 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->min_q_total[i] < min_q_total) {
- min_q_node = g->min_q_node[i];
- min_q_total = g->min_q_total[i];
+ 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->stack_count;
+ stack_optimistic_start = g->tmp.stack_count;
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
for (i = 0; i < g->nodes[n].adjacency_count; i++) {
unsigned int n2 = g->nodes[n].adjacency_list[i];
- if (!BITSET_TEST(g->in_stack, n2) &&
+ if (!BITSET_TEST(g->tmp.in_stack, n2) &&
BITSET_TEST(g->regs->regs[r].conflicts, g->nodes[n2].reg)) {
return true;
}
unsigned int n2 = g->nodes[n].adjacency_list[i];
unsigned int r = g->nodes[n2].reg;
- if (!BITSET_TEST(g->in_stack, n2)) {
+ 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];
}
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];
/* set this to false even if we return here so that
* ra_get_best_spill_node() considers this node later.
*/
- BITSET_CLEAR(g->in_stack, n);
+ BITSET_CLEAR(g->tmp.in_stack, n);
if (g->select_reg_callback) {
if (!ra_compute_available_regs(g, n, select_regs)) {
return false;
}
- r = g->select_reg_callback(g, select_regs, g->select_reg_callback_data);
+ 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.
}
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
* 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;
}
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;
}
/**
void
ra_set_node_reg(struct ra_graph *g, unsigned int n, unsigned int reg)
{
- g->nodes[n].reg = reg;
- BITSET_CLEAR(g->in_stack, n);
+ g->nodes[n].forced_reg = reg;
}
static float
if (cost <= 0.0f)
continue;
- if (BITSET_TEST(g->in_stack, n))
+ if (BITSET_TEST(g->tmp.in_stack, n))
continue;
benefit = ra_get_spill_benefit(g, n);
projects / mesa.git / blobdiff