#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 ~0U
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;
};
/**
* 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;
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;
}
{
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);
}
*/
void
ra_add_transitive_reg_conflict(struct ra_regs *regs,
- unsigned int base_reg, unsigned int reg)
+ unsigned int base_reg, unsigned int reg)
{
unsigned int 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];
+ BITSET_WORD tmp;
+ int c;
+
+ BITSET_FOREACH_SET(c, tmp, 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;
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;
- 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;
- }
+ for (b = 0; b < regs->count; b++) {
+ ralloc_free(regs->regs[b].conflict_list);
+ regs->regs[b].conflict_list = NULL;
}
}
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;
}
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)) {
ra_add_node_adjacency(g, n1, n2);
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];
+ g->nodes[n2].q_total -= g->regs->classes[n2_class]->q[n_class];
}
}
}
ra_simplify(struct ra_graph *g)
{
bool progress = true;
+ unsigned int stack_optimistic_start = UINT_MAX;
int i;
while (progress) {
}
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++;
progress = true;
}
}
+
+ g->stack_optimistic_start = stack_optimistic_start;
}
/**
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;
}
float cost = g->nodes[n].spill_cost;
float benefit;
- if (cost <= 0.0)
+ if (cost <= 0.0f)
continue;
if (g->nodes[n].in_stack)
projects / mesa.git / blobdiff