Lines Matching refs:g
477 ra_add_node_adjacency(struct ra_graph *g, unsigned int n1, unsigned int n2) in ra_add_node_adjacency() argument
479 BITSET_SET(g->nodes[n1].adjacency, n2); in ra_add_node_adjacency()
483 int n1_class = g->nodes[n1].class; in ra_add_node_adjacency()
484 int n2_class = g->nodes[n2].class; in ra_add_node_adjacency()
485 g->nodes[n1].q_total += g->regs->classes[n1_class]->q[n2_class]; in ra_add_node_adjacency()
487 util_dynarray_append(&g->nodes[n1].adjacency_list, unsigned int, n2); in ra_add_node_adjacency()
491 ra_node_remove_adjacency(struct ra_graph *g, unsigned int n1, unsigned int n2) in ra_node_remove_adjacency() argument
493 BITSET_CLEAR(g->nodes[n1].adjacency, n2); in ra_node_remove_adjacency()
497 int n1_class = g->nodes[n1].class; in ra_node_remove_adjacency()
498 int n2_class = g->nodes[n2].class; in ra_node_remove_adjacency()
499 g->nodes[n1].q_total -= g->regs->classes[n1_class]->q[n2_class]; in ra_node_remove_adjacency()
501 util_dynarray_delete_unordered(&g->nodes[n1].adjacency_list, unsigned int, in ra_node_remove_adjacency()
506 ra_realloc_interference_graph(struct ra_graph *g, unsigned int alloc) in ra_realloc_interference_graph() argument
508 if (alloc <= g->alloc) in ra_realloc_interference_graph()
514 assert(g->alloc % BITSET_WORDBITS == 0); in ra_realloc_interference_graph()
517 g->nodes = reralloc(g, g->nodes, struct ra_node, alloc); in ra_realloc_interference_graph()
519 unsigned g_bitset_count = BITSET_WORDS(g->alloc); in ra_realloc_interference_graph()
522 for (unsigned i = 0; i < g->alloc; i++) { in ra_realloc_interference_graph()
523 assert(g->nodes[i].adjacency != NULL); in ra_realloc_interference_graph()
524 g->nodes[i].adjacency = rerzalloc(g, g->nodes[i].adjacency, BITSET_WORD, in ra_realloc_interference_graph()
529 for (unsigned i = g->alloc; i < alloc; i++) { in ra_realloc_interference_graph()
530 memset(&g->nodes[i], 0, sizeof(g->nodes[i])); in ra_realloc_interference_graph()
531 g->nodes[i].adjacency = rzalloc_array(g, BITSET_WORD, bitset_count); in ra_realloc_interference_graph()
532 util_dynarray_init(&g->nodes[i].adjacency_list, g); in ra_realloc_interference_graph()
533 g->nodes[i].q_total = 0; in ra_realloc_interference_graph()
535 g->nodes[i].forced_reg = NO_REG; in ra_realloc_interference_graph()
536 g->nodes[i].reg = NO_REG; in ra_realloc_interference_graph()
542 g->tmp.stack = reralloc(g, g->tmp.stack, unsigned int, alloc); in ra_realloc_interference_graph()
543 g->tmp.in_stack = reralloc(g, g->tmp.in_stack, BITSET_WORD, bitset_count); in ra_realloc_interference_graph()
545 g->tmp.reg_assigned = reralloc(g, g->tmp.reg_assigned, BITSET_WORD, in ra_realloc_interference_graph()
547 g->tmp.pq_test = reralloc(g, g->tmp.pq_test, BITSET_WORD, bitset_count); in ra_realloc_interference_graph()
548 g->tmp.min_q_total = reralloc(g, g->tmp.min_q_total, unsigned int, in ra_realloc_interference_graph()
550 g->tmp.min_q_node = reralloc(g, g->tmp.min_q_node, unsigned int, in ra_realloc_interference_graph()
553 g->alloc = alloc; in ra_realloc_interference_graph()
559 struct ra_graph *g; in ra_alloc_interference_graph() local
561 g = rzalloc(NULL, struct ra_graph); in ra_alloc_interference_graph()
562 g->regs = regs; in ra_alloc_interference_graph()
563 g->count = count; in ra_alloc_interference_graph()
564 ra_realloc_interference_graph(g, count); in ra_alloc_interference_graph()
566 return g; in ra_alloc_interference_graph()
570 ra_resize_interference_graph(struct ra_graph *g, unsigned int count) in ra_resize_interference_graph() argument
572 g->count = count; in ra_resize_interference_graph()
573 if (count > g->alloc) in ra_resize_interference_graph()
574 ra_realloc_interference_graph(g, g->alloc * 2); in ra_resize_interference_graph()
577 void ra_set_select_reg_callback(struct ra_graph *g, in ra_set_select_reg_callback() argument
581 g->select_reg_callback = callback; in ra_set_select_reg_callback()
582 g->select_reg_callback_data = data; in ra_set_select_reg_callback()
586 ra_set_node_class(struct ra_graph *g, in ra_set_node_class() argument
589 g->nodes[n].class = class->index; in ra_set_node_class()
593 ra_get_node_class(struct ra_graph *g, in ra_get_node_class() argument
596 return g->regs->classes[g->nodes[n].class]; in ra_get_node_class()
600 ra_add_node(struct ra_graph *g, struct ra_class *class) in ra_add_node() argument
602 unsigned int n = g->count; in ra_add_node()
603 ra_resize_interference_graph(g, g->count + 1); in ra_add_node()
605 ra_set_node_class(g, n, class); in ra_add_node()
611 ra_add_node_interference(struct ra_graph *g, in ra_add_node_interference() argument
614 assert(n1 < g->count && n2 < g->count); in ra_add_node_interference()
615 if (n1 != n2 && !BITSET_TEST(g->nodes[n1].adjacency, n2)) { in ra_add_node_interference()
616 ra_add_node_adjacency(g, n1, n2); in ra_add_node_interference()
617 ra_add_node_adjacency(g, n2, n1); in ra_add_node_interference()
622 ra_reset_node_interference(struct ra_graph *g, unsigned int n) in ra_reset_node_interference() argument
624 util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { in ra_reset_node_interference()
625 ra_node_remove_adjacency(g, *n2p, n); in ra_reset_node_interference()
628 memset(g->nodes[n].adjacency, 0, in ra_reset_node_interference()
629 BITSET_WORDS(g->count) * sizeof(BITSET_WORD)); in ra_reset_node_interference()
630 util_dynarray_clear(&g->nodes[n].adjacency_list); in ra_reset_node_interference()
634 update_pq_info(struct ra_graph *g, unsigned int n) in update_pq_info() argument
637 int n_class = g->nodes[n].class; in update_pq_info()
638 if (g->nodes[n].tmp.q_total < g->regs->classes[n_class]->p) { in update_pq_info()
639 BITSET_SET(g->tmp.pq_test, n); in update_pq_info()
640 } else if (g->tmp.min_q_total[i] != UINT_MAX) { in update_pq_info()
647 if (g->nodes[n].tmp.q_total < g->tmp.min_q_total[i] || in update_pq_info()
648 (g->nodes[n].tmp.q_total == g->tmp.min_q_total[i] && in update_pq_info()
649 n > g->tmp.min_q_node[i])) { in update_pq_info()
650 g->tmp.min_q_total[i] = g->nodes[n].tmp.q_total; in update_pq_info()
651 g->tmp.min_q_node[i] = n; in update_pq_info()
657 add_node_to_stack(struct ra_graph *g, unsigned int n) in add_node_to_stack() argument
659 int n_class = g->nodes[n].class; in add_node_to_stack()
661 assert(!BITSET_TEST(g->tmp.in_stack, n)); in add_node_to_stack()
663 util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { in add_node_to_stack()
665 unsigned int n2_class = g->nodes[n2].class; in add_node_to_stack()
667 if (!BITSET_TEST(g->tmp.in_stack, n2) && in add_node_to_stack()
668 !BITSET_TEST(g->tmp.reg_assigned, n2)) { in add_node_to_stack()
669 assert(g->nodes[n2].tmp.q_total >= g->regs->classes[n2_class]->q[n_class]); in add_node_to_stack()
670 g->nodes[n2].tmp.q_total -= g->regs->classes[n2_class]->q[n_class]; in add_node_to_stack()
671 update_pq_info(g, n2); in add_node_to_stack()
675 g->tmp.stack[g->tmp.stack_count] = n; in add_node_to_stack()
676 g->tmp.stack_count++; in add_node_to_stack()
677 BITSET_SET(g->tmp.in_stack, n); in add_node_to_stack()
680 g->tmp.min_q_total[n / BITSET_WORDBITS] = UINT_MAX; in add_node_to_stack()
694 ra_simplify(struct ra_graph *g) in ra_simplify() argument
702 const unsigned int top_word_high_bit = (g->count - 1) % BITSET_WORDBITS; in ra_simplify()
705 g->tmp.stack_count = 0; in ra_simplify()
706 for (int i = BITSET_WORDS(g->count) - 1, high_bit = top_word_high_bit; in ra_simplify()
708 g->tmp.in_stack[i] = 0; in ra_simplify()
709 g->tmp.reg_assigned[i] = 0; in ra_simplify()
710 g->tmp.pq_test[i] = 0; in ra_simplify()
711 g->tmp.min_q_total[i] = UINT_MAX; in ra_simplify()
712 g->tmp.min_q_node[i] = UINT_MAX; in ra_simplify()
715 g->nodes[n].reg = g->nodes[n].forced_reg; in ra_simplify()
716 g->nodes[n].tmp.q_total = g->nodes[n].q_total; in ra_simplify()
717 if (g->nodes[n].reg != NO_REG) in ra_simplify()
718 g->tmp.reg_assigned[i] |= BITSET_BIT(j); in ra_simplify()
719 update_pq_info(g, n); in ra_simplify()
729 for (int i = BITSET_WORDS(g->count) - 1, high_bit = top_word_high_bit; in ra_simplify()
733 BITSET_WORD skip = g->tmp.in_stack[i] | g->tmp.reg_assigned[i]; in ra_simplify()
737 BITSET_WORD pq = g->tmp.pq_test[i] & ~skip; in ra_simplify()
748 assert(n < g->count); in ra_simplify()
749 add_node_to_stack(g, n); in ra_simplify()
753 pq = g->tmp.pq_test[i] & ~skip; in ra_simplify()
758 if (g->tmp.min_q_total[i] == UINT_MAX) { in ra_simplify()
768 assert(n < g->count); in ra_simplify()
769 if (g->nodes[n].tmp.q_total < g->tmp.min_q_total[i]) { in ra_simplify()
770 g->tmp.min_q_total[i] = g->nodes[n].tmp.q_total; in ra_simplify()
771 g->tmp.min_q_node[i] = n; in ra_simplify()
775 if (g->tmp.min_q_total[i] < min_q_total) { in ra_simplify()
776 min_q_node = g->tmp.min_q_node[i]; in ra_simplify()
777 min_q_total = g->tmp.min_q_total[i]; in ra_simplify()
784 stack_optimistic_start = g->tmp.stack_count; in ra_simplify()
786 add_node_to_stack(g, min_q_node); in ra_simplify()
791 g->tmp.stack_optimistic_start = stack_optimistic_start; in ra_simplify()
810 ra_find_conflicting_neighbor(struct ra_graph *g, unsigned int n, unsigned int r) in ra_find_conflicting_neighbor() argument
812 util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { in ra_find_conflicting_neighbor()
816 if (!BITSET_TEST(g->tmp.in_stack, n2) && in ra_find_conflicting_neighbor()
817 ra_class_allocations_conflict(g->regs->classes[g->nodes[n].class], r, in ra_find_conflicting_neighbor()
818 g->regs->classes[g->nodes[n2].class], g->nodes[n2].reg)) { in ra_find_conflicting_neighbor()
819 return &g->nodes[n2]; in ra_find_conflicting_neighbor()
833 ra_compute_available_regs(struct ra_graph *g, unsigned int n, BITSET_WORD *regs) in ra_compute_available_regs() argument
835 struct ra_class *c = g->regs->classes[g->nodes[n].class]; in ra_compute_available_regs()
838 memcpy(regs, c->regs, BITSET_WORDS(g->regs->count) * sizeof(BITSET_WORD)); in ra_compute_available_regs()
843 util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { in ra_compute_available_regs()
844 struct ra_node *n2 = &g->nodes[*n2p]; in ra_compute_available_regs()
845 struct ra_class *n2c = g->regs->classes[n2->class]; in ra_compute_available_regs()
847 if (!BITSET_TEST(g->tmp.in_stack, *n2p)) { in ra_compute_available_regs()
850 int end = MIN2(g->regs->count, n2->reg + n2c->contig_len); in ra_compute_available_regs()
854 for (int j = 0; j < BITSET_WORDS(g->regs->count); j++) in ra_compute_available_regs()
855 regs[j] &= ~g->regs->regs[n2->reg].conflicts[j]; in ra_compute_available_regs()
860 for (int i = 0; i < BITSET_WORDS(g->regs->count); i++) { in ra_compute_available_regs()
876 ra_select(struct ra_graph *g) in ra_select() argument
881 if (g->select_reg_callback) in ra_select()
882 select_regs = malloc(BITSET_WORDS(g->regs->count) * sizeof(BITSET_WORD)); in ra_select()
884 while (g->tmp.stack_count != 0) { in ra_select()
887 int n = g->tmp.stack[g->tmp.stack_count - 1]; in ra_select()
888 struct ra_class *c = g->regs->classes[g->nodes[n].class]; in ra_select()
893 BITSET_CLEAR(g->tmp.in_stack, n); in ra_select()
895 if (g->select_reg_callback) { in ra_select()
896 if (!ra_compute_available_regs(g, n, select_regs)) { in ra_select()
901 r = g->select_reg_callback(n, select_regs, g->select_reg_callback_data); in ra_select()
902 assert(r < g->regs->count); in ra_select()
907 for (ri = 0; ri < g->regs->count; ri++) { in ra_select()
908 r = (start_search_reg + ri) % g->regs->count; in ra_select()
912 struct ra_node *conflicting = ra_find_conflicting_neighbor(g, n, r); in ra_select()
917 if (g->regs->classes[conflicting->class]->contig_len) { in ra_select()
923 g->regs->classes[conflicting->class]->contig_len - 1); in ra_select()
929 if (ri >= g->regs->count) in ra_select()
933 g->nodes[n].reg = r; in ra_select()
934 g->tmp.stack_count--; in ra_select()
945 if (g->regs->round_robin && in ra_select()
946 g->tmp.stack_count - 1 <= g->tmp.stack_optimistic_start) in ra_select()
956 ra_allocate(struct ra_graph *g) in ra_allocate() argument
958 ra_simplify(g); in ra_allocate()
959 return ra_select(g); in ra_allocate()
963 ra_get_node_reg(struct ra_graph *g, unsigned int n) in ra_get_node_reg() argument
965 if (g->nodes[n].forced_reg != NO_REG) in ra_get_node_reg()
966 return g->nodes[n].forced_reg; in ra_get_node_reg()
968 return g->nodes[n].reg; in ra_get_node_reg()
985 ra_set_node_reg(struct ra_graph *g, unsigned int n, unsigned int reg) in ra_set_node_reg() argument
987 g->nodes[n].forced_reg = reg; in ra_set_node_reg()
991 ra_get_spill_benefit(struct ra_graph *g, unsigned int n) in ra_get_spill_benefit() argument
994 int n_class = g->nodes[n].class; in ra_get_spill_benefit()
1001 util_dynarray_foreach(&g->nodes[n].adjacency_list, unsigned int, n2p) { in ra_get_spill_benefit()
1003 unsigned int n2_class = g->nodes[n2].class; in ra_get_spill_benefit()
1004 benefit += ((float)g->regs->classes[n_class]->q[n2_class] / in ra_get_spill_benefit()
1005 g->regs->classes[n_class]->p); in ra_get_spill_benefit()
1016 ra_get_best_spill_node(struct ra_graph *g) in ra_get_best_spill_node() argument
1027 for (n = 0; n < g->count; n++) { in ra_get_best_spill_node()
1028 float cost = g->nodes[n].spill_cost; in ra_get_best_spill_node()
1034 if (BITSET_TEST(g->tmp.in_stack, n)) in ra_get_best_spill_node()
1037 benefit = ra_get_spill_benefit(g, n); in ra_get_best_spill_node()
1053 ra_set_node_spill_cost(struct ra_graph *g, unsigned int n, float cost) in ra_set_node_spill_cost() argument
1055 g->nodes[n].spill_cost = cost; in ra_set_node_spill_cost()