X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Futil%2Fregister_allocate.c;h=75f612480828565fc3fba59480fa473e95025b65;hb=57088854e60b1616f3c8a4c793b7d95a87ece9a0;hp=af43c2fbb434e525d1da326747277bb3fdc6c4af;hpb=76f79db3f5d8492370c92080b5bbea7e31827b75;p=mesa.git diff --git a/src/util/register_allocate.c b/src/util/register_allocate.c index af43c2fbb43..75f61248082 100644 --- a/src/util/register_allocate.c +++ b/src/util/register_allocate.c @@ -71,11 +71,12 @@ */ #include -#include +#include #include "ralloc.h" -#include "util/imports.h" +#include "main/macros.h" #include "util/bitset.h" +#include "util/u_dynarray.h" #include "u_math.h" #include "register_allocate.h" @@ -126,9 +127,8 @@ struct ra_node { * symmetric with the other node. */ BITSET_WORD *adjacency; - unsigned int *adjacency_list; - unsigned int adjacency_list_size; - unsigned int adjacency_count; + + struct util_dynarray adjacency_list; /** @} */ unsigned int class; @@ -371,6 +371,8 @@ ra_class_add_reg(struct ra_regs *regs, unsigned int c, unsigned int r) { struct ra_class *class = regs->classes[c]; + assert(r < regs->count); + BITSET_SET(class->regs, r); class->p++; } @@ -450,16 +452,7 @@ ra_add_node_adjacency(struct ra_graph *g, unsigned int n1, unsigned int n2) 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; - g->nodes[n1].adjacency_list = reralloc(g, g->nodes[n1].adjacency_list, - unsigned int, - g->nodes[n1].adjacency_list_size); - } - - g->nodes[n1].adjacency_list[g->nodes[n1].adjacency_count] = n2; - g->nodes[n1].adjacency_count++; + util_dynarray_append(&g->nodes[n1].adjacency_list, unsigned int, n2); } static void @@ -473,18 +466,8 @@ ra_node_remove_adjacency(struct ra_graph *g, unsigned int n1, unsigned int n2) 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--; + util_dynarray_delete_unordered(&g->nodes[n1].adjacency_list, unsigned int, + n2); } static void @@ -514,10 +497,7 @@ ra_realloc_interference_graph(struct ra_graph *g, unsigned int alloc) 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; + util_dynarray_init(&g->nodes[i].adjacency_list, g); g->nodes[i].q_total = 0; g->nodes[i].forced_reg = NO_REG; @@ -609,12 +589,13 @@ ra_add_node_interference(struct ra_graph *g, 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); + util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { + ra_node_remove_adjacency(g, *n2p, n); + } memset(g->nodes[n].adjacency, 0, BITSET_WORDS(g->count) * sizeof(BITSET_WORD)); - g->nodes[n].adjacency_count = 0; + util_dynarray_clear(&g->nodes[n].adjacency_list); } static void @@ -643,13 +624,12 @@ update_pq_info(struct ra_graph *g, unsigned int n) static void 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]; + util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { + unsigned int n2 = *n2p; unsigned int n2_class = g->nodes[n2].class; if (!BITSET_TEST(g->tmp.in_stack, n2) && @@ -782,10 +762,8 @@ ra_simplify(struct ra_graph *g) 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]; + util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { + unsigned int n2 = *n2p; if (!BITSET_TEST(g->tmp.in_stack, n2) && BITSET_TEST(g->regs->regs[r].conflicts, g->nodes[n2].reg)) { @@ -813,8 +791,8 @@ ra_compute_available_regs(struct ra_graph *g, unsigned int n, BITSET_WORD *regs) /* 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]; + util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { + unsigned int n2 = *n2p; unsigned int r = g->nodes[n2].reg; if (!BITSET_TEST(g->tmp.in_stack, n2)) { @@ -865,6 +843,7 @@ ra_select(struct ra_graph *g) } r = g->select_reg_callback(n, select_regs, g->select_reg_callback_data); + assert(r < g->regs->count); } else { /* Find the lowest-numbered reg which is not used by a member * of the graph adjacent to us. @@ -942,7 +921,6 @@ 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) { - unsigned int j; float benefit = 0; int n_class = g->nodes[n].class; @@ -951,8 +929,8 @@ ra_get_spill_benefit(struct ra_graph *g, unsigned int n) * "count number of edges" approach of traditional graph coloring, * but takes classes into account. */ - for (j = 0; j < g->nodes[n].adjacency_count; j++) { - unsigned int n2 = g->nodes[n].adjacency_list[j]; + util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { + unsigned int n2 = *n2p; unsigned int n2_class = g->nodes[n2].class; benefit += ((float)g->regs->classes[n_class]->q[n2_class] / g->regs->classes[n_class]->p);