178    unsigned int (*select_reg_callback)(struct ra_graph *g, BITSET_WORD *regs,
395 ra_add_node_adjacency(struct ra_graph *g, unsigned int n1, unsigned int n2)  in ra_add_node_adjacency()  argument
397    BITSET_SET(g->nodes[n1].adjacency, n2);  in ra_add_node_adjacency()
401    int n1_class = g->nodes[n1].class;  in ra_add_node_adjacency()
402    int n2_class = g->nodes[n2].class;  in ra_add_node_adjacency()
403    g->nodes[n1].q_total += g->regs->classes[n1_class]->q[n2_class];  in ra_add_node_adjacency()
405    if (g->nodes[n1].adjacency_count >=  in ra_add_node_adjacency()
406        g->nodes[n1].adjacency_list_size) {  in ra_add_node_adjacency()
407       g->nodes[n1].adjacency_list_size *= 2;  in ra_add_node_adjacency()
408       g->nodes[n1].adjacency_list = reralloc(g, g->nodes[n1].adjacency_list,  in ra_add_node_adjacency()
410                                              g->nodes[n1].adjacency_list_size);  in ra_add_node_adjacency()
413    g->nodes[n1].adjacency_list[g->nodes[n1].adjacency_count] = n2;  in ra_add_node_adjacency()
414    g->nodes[n1].adjacency_count++;  in ra_add_node_adjacency()
420    struct ra_graph *g;  in ra_alloc_interference_graph()  local
423    g = rzalloc(NULL, struct ra_graph);  in ra_alloc_interference_graph()
424    g->regs = regs;  in ra_alloc_interference_graph()
425    g->nodes = rzalloc_array(g, struct ra_node, count);  in ra_alloc_interference_graph()
426    g->count = count;  in ra_alloc_interference_graph()
428    g->stack = rzalloc_array(g, unsigned int, count);  in ra_alloc_interference_graph()
432       g->nodes[i].adjacency = rzalloc_array(g, BITSET_WORD, bitset_count);  in ra_alloc_interference_graph()
434       g->nodes[i].adjacency_list_size = 4;  in ra_alloc_interference_graph()
435       g->nodes[i].adjacency_list =  in ra_alloc_interference_graph()
436          ralloc_array(g, unsigned int, g->nodes[i].adjacency_list_size);  in ra_alloc_interference_graph()
437       g->nodes[i].adjacency_count = 0;  in ra_alloc_interference_graph()
438       g->nodes[i].q_total = 0;  in ra_alloc_interference_graph()
440       g->nodes[i].reg = NO_REG;  in ra_alloc_interference_graph()
443    return g;  in ra_alloc_interference_graph()
446 void ra_set_select_reg_callback(struct ra_graph *g,  in ra_set_select_reg_callback()  argument
447                                 unsigned int (*callback)(struct ra_graph *g,  in ra_set_select_reg_callback()  argument
452    g->select_reg_callback = callback;  in ra_set_select_reg_callback()
453    g->select_reg_callback_data = data;  in ra_set_select_reg_callback()
457 ra_set_node_class(struct ra_graph *g,  in ra_set_node_class()  argument
460    g->nodes[n].class = class;  in ra_set_node_class()
464 ra_add_node_interference(struct ra_graph *g,  in ra_add_node_interference()  argument
467    if (n1 != n2 && !BITSET_TEST(g->nodes[n1].adjacency, n2)) {  in ra_add_node_interference()
468       ra_add_node_adjacency(g, n1, n2);  in ra_add_node_interference()
469       ra_add_node_adjacency(g, n2, n1);  in ra_add_node_interference()
474 pq_test(struct ra_graph *g, unsigned int n)  in pq_test()  argument
476    int n_class = g->nodes[n].class;  in pq_test()
478    return g->nodes[n].q_total < g->regs->classes[n_class]->p;  in pq_test()
482 decrement_q(struct ra_graph *g, unsigned int n)  in decrement_q()  argument
485    int n_class = g->nodes[n].class;  in decrement_q()
487    for (i = 0; i < g->nodes[n].adjacency_count; i++) {  in decrement_q()
488       unsigned int n2 = g->nodes[n].adjacency_list[i];  in decrement_q()
489       unsigned int n2_class = g->nodes[n2].class;  in decrement_q()
491       if (!g->nodes[n2].in_stack) {  in decrement_q()
492          assert(g->nodes[n2].q_total >= g->regs->classes[n2_class]->q[n_class]);  in decrement_q()
493          g->nodes[n2].q_total -= g->regs->classes[n2_class]->q[n_class];  in decrement_q()
509 ra_simplify(struct ra_graph *g)  in ra_simplify()  argument
521       for (i = g->count - 1; i >= 0; i--) {  in ra_simplify()
522 	 if (g->nodes[i].in_stack || g->nodes[i].reg != NO_REG)  in ra_simplify()
525 	 if (pq_test(g, i)) {  in ra_simplify()
526 	    decrement_q(g, i);  in ra_simplify()
527 	    g->stack[g->stack_count] = i;  in ra_simplify()
528 	    g->stack_count++;  in ra_simplify()
529 	    g->nodes[i].in_stack = true;  in ra_simplify()
532 	    unsigned int new_q_total = g->nodes[i].q_total;  in ra_simplify()
542             stack_optimistic_start = g->stack_count;  in ra_simplify()
544 	 decrement_q(g, best_optimistic_node);  in ra_simplify()
545 	 g->stack[g->stack_count] = best_optimistic_node;  in ra_simplify()
546 	 g->stack_count++;  in ra_simplify()
547 	 g->nodes[best_optimistic_node].in_stack = true;  in ra_simplify()
552    g->stack_optimistic_start = stack_optimistic_start;  in ra_simplify()
556 ra_any_neighbors_conflict(struct ra_graph *g, unsigned int n, unsigned int r)  in ra_any_neighbors_conflict()  argument
560    for (i = 0; i < g->nodes[n].adjacency_count; i++) {  in ra_any_neighbors_conflict()
561       unsigned int n2 = g->nodes[n].adjacency_list[i];  in ra_any_neighbors_conflict()
563       if (!g->nodes[n2].in_stack &&  in ra_any_neighbors_conflict()
564           BITSET_TEST(g->regs->regs[r].conflicts, g->nodes[n2].reg)) {  in ra_any_neighbors_conflict()
579 ra_compute_available_regs(struct ra_graph *g, unsigned int n, BITSET_WORD *regs)  in ra_compute_available_regs()  argument
581    struct ra_class *c = g->regs->classes[g->nodes[n].class];  in ra_compute_available_regs()
584    memcpy(regs, c->regs, BITSET_WORDS(g->regs->count) * sizeof(BITSET_WORD));  in ra_compute_available_regs()
589    for (int i = 0; i < g->nodes[n].adjacency_count; i++) {  in ra_compute_available_regs()
590       unsigned int n2 = g->nodes[n].adjacency_list[i];  in ra_compute_available_regs()
591       unsigned int r = g->nodes[n2].reg;  in ra_compute_available_regs()
593       if (!g->nodes[n2].in_stack) {  in ra_compute_available_regs()
594          for (int j = 0; j < BITSET_WORDS(g->regs->count); j++)  in ra_compute_available_regs()
595             regs[j] &= ~g->regs->regs[r].conflicts[j];  in ra_compute_available_regs()
599    for (int i = 0; i < BITSET_WORDS(g->regs->count); i++) {  in ra_compute_available_regs()
615 ra_select(struct ra_graph *g)  in ra_select()  argument
620    if (g->select_reg_callback)  in ra_select()
621       select_regs = malloc(BITSET_WORDS(g->regs->count) * sizeof(BITSET_WORD));  in ra_select()
623    while (g->stack_count != 0) {  in ra_select()
626       int n = g->stack[g->stack_count - 1];  in ra_select()
627       struct ra_class *c = g->regs->classes[g->nodes[n].class];  in ra_select()
632       g->nodes[n].in_stack = false;  in ra_select()
634       if (g->select_reg_callback) {  in ra_select()
635          if (!ra_compute_available_regs(g, n, select_regs)) {  in ra_select()
640          r = g->select_reg_callback(g, select_regs, g->select_reg_callback_data);  in ra_select()
645          for (ri = 0; ri < g->regs->count; ri++) {  in ra_select()
646             r = (start_search_reg + ri) % g->regs->count;  in ra_select()
650             if (!ra_any_neighbors_conflict(g, n, r))  in ra_select()
654          if (ri >= g->regs->count)  in ra_select()
658       g->nodes[n].reg = r;  in ra_select()
659       g->stack_count--;  in ra_select()
670       if (g->regs->round_robin &&  in ra_select()
671           g->stack_count - 1 <= g->stack_optimistic_start)  in ra_select()
681 ra_allocate(struct ra_graph *g)  in ra_allocate()  argument
683    ra_simplify(g);  in ra_allocate()
684    return ra_select(g);  in ra_allocate()
688 ra_get_node_reg(struct ra_graph *g, unsigned int n)  in ra_get_node_reg()  argument
690    return g->nodes[n].reg;  in ra_get_node_reg()
707 ra_set_node_reg(struct ra_graph *g, unsigned int n, unsigned int reg)  in ra_set_node_reg()  argument
709    g->nodes[n].reg = reg;  in ra_set_node_reg()
710    g->nodes[n].in_stack = false;  in ra_set_node_reg()
714 ra_get_spill_benefit(struct ra_graph *g, unsigned int n)  in ra_get_spill_benefit()  argument
718    int n_class = g->nodes[n].class;  in ra_get_spill_benefit()
725    for (j = 0; j < g->nodes[n].adjacency_count; j++) {  in ra_get_spill_benefit()
726       unsigned int n2 = g->nodes[n].adjacency_list[j];  in ra_get_spill_benefit()
727       unsigned int n2_class = g->nodes[n2].class;  in ra_get_spill_benefit()
728       benefit += ((float)g->regs->classes[n_class]->q[n2_class] /  in ra_get_spill_benefit()
729                   g->regs->classes[n_class]->p);  in ra_get_spill_benefit()
740 ra_get_best_spill_node(struct ra_graph *g)  in ra_get_best_spill_node()  argument
751    for (n = 0; n < g->count; n++) {  in ra_get_best_spill_node()
752       float cost = g->nodes[n].spill_cost;  in ra_get_best_spill_node()
758       if (g->nodes[n].in_stack)  in ra_get_best_spill_node()
761       benefit = ra_get_spill_benefit(g, n);  in ra_get_best_spill_node()
777 ra_set_node_spill_cost(struct ra_graph *g, unsigned int n, float cost)  in ra_set_node_spill_cost()  argument
779    g->nodes[n].spill_cost = cost;  in ra_set_node_spill_cost()