4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
21 #endif /* __linux__ */
28 #include <libcore/lc_opts.h>
29 #include <libcore/lc_opts_enum.h>
30 #include <libcore/lc_timing.h>
31 #endif /* WITH_LIBCORE */
41 #include "beifg_impl.h"
43 #include "irphase_t.h"
44 #include "bechordal.h"
47 #include "becopystat.h"
48 #include "becopyopt.h"
51 /** Defines values for the ifg performance test */
52 #define BE_CH_PERFORMANCETEST_MIN_NODES (50)
53 #define BE_CH_PERFORMANCETEST_COUNT (500)
55 typedef struct _coloring_t coloring_t;
59 const arch_env_t *arch_env;
63 size_t (be_ifg_nodes_iter_size)(const be_ifg_t *ifg)
65 return ifg->impl->nodes_iter_size;
68 size_t (be_ifg_neighbours_iter_size)(const be_ifg_t *ifg)
70 return ifg->impl->neighbours_iter_size;
73 size_t (be_ifg_cliques_iter_size)(const be_ifg_t *ifg)
75 return ifg->impl->cliques_iter_size;
78 static void *regs_irn_data_init(phase_t *ph, ir_node *irn, void *data)
80 coloring_t *coloring = (coloring_t *) ph;
81 return (void *) arch_get_irn_register(coloring->arch_env, irn);
84 coloring_t *coloring_init(coloring_t *c, ir_graph *irg, const arch_env_t *aenv)
86 phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init);
92 static void get_irn_color(ir_node *irn, void *c)
94 coloring_t *coloring = c;
95 phase_get_or_set_irn_data(&coloring->ph, irn);
98 static void restore_irn_color(ir_node *irn, void *c)
100 coloring_t *coloring = c;
101 const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn);
103 arch_set_irn_register(coloring->arch_env, irn, reg);
106 void coloring_save(coloring_t *c)
108 irg_walk_graph(c->irg, NULL, get_irn_color, c);
111 void coloring_restore(coloring_t *c)
113 irg_walk_graph(c->irg, NULL, restore_irn_color, c);
116 void (be_ifg_free)(be_ifg_t *ifg)
118 ifg->impl->free(ifg);
121 int (be_ifg_connected)(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
123 return ifg->impl->connected(ifg, a, b);
126 ir_node *(be_ifg_neighbours_begin)(const be_ifg_t *ifg, void *iter, const ir_node *irn)
128 return ifg->impl->neighbours_begin(ifg, iter, irn);
131 ir_node *(be_ifg_neighbours_next)(const be_ifg_t *ifg, void *iter)
133 return ifg->impl->neighbours_next(ifg, iter);
136 void (be_ifg_neighbours_break)(const be_ifg_t *ifg, void *iter)
138 ifg->impl->neighbours_break(ifg, iter);
141 ir_node *(be_ifg_nodes_begin)(const be_ifg_t *ifg, void *iter)
143 return ifg->impl->nodes_begin(ifg, iter);
146 ir_node *(be_ifg_nodes_next)(const be_ifg_t *ifg, void *iter)
148 return ifg->impl->nodes_next(ifg, iter);
151 void (be_ifg_nodes_break)(const be_ifg_t *ifg, void *iter)
153 ifg->impl->nodes_break(ifg, iter);
156 int (be_ifg_cliques_begin)(const be_ifg_t *ifg, void *iter, ir_node **buf)
158 return ifg->impl->cliques_begin(ifg, iter, buf);
161 int (be_ifg_cliques_next)(const be_ifg_t *ifg, void *iter)
163 return ifg->impl->cliques_next(ifg, iter);
166 void (be_ifg_cliques_break)(const be_ifg_t *ifg, void *iter)
168 ifg->impl->cliques_break(ifg, iter);
171 int (be_ifg_degree)(const be_ifg_t *ifg, const ir_node *irn)
173 return ifg->impl->degree(ifg, irn);
177 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
179 int degree = be_ifg_degree(ifg, irn);
180 void *iter = be_ifg_neighbours_iter_alloca(ifg);
182 ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0]));
188 be_ifg_foreach_neighbour(ifg, iter, irn, curr)
189 neighbours[i++] = curr;
191 for(i = 0; i < degree; ++i) {
192 for(j = 0; j < i; ++j)
193 if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
204 void be_ifg_check(const be_ifg_t *ifg)
206 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
207 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
211 int neighbours_count = 0;
214 /* count all nodes */
215 ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
216 be_ifg_foreach_node(ifg,iter1,n)
219 degree = be_ifg_degree(ifg, n);
220 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
223 ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
225 /* Check, if all neighbours are indeed connected to the node. */
226 be_ifg_foreach_node(ifg, iter1, n)
228 ir_printf("\n%+F; ", n);
229 be_ifg_foreach_neighbour(ifg, iter2, n, m)
231 ir_printf("%+F; ", m);
233 if(!be_ifg_connected(ifg, n, m))
234 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
237 ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
240 int be_ifg_check_get_node_count(const be_ifg_t *ifg)
242 void *iter = be_ifg_nodes_iter_alloca(ifg);
246 be_ifg_foreach_node(ifg, iter, n)
254 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
256 const ir_node *node_a = *(ir_node **)a;
257 const ir_node *node_b = *(ir_node **)b;
259 long nr_a = get_irn_node_nr(node_a);
260 long nr_b = get_irn_node_nr(node_b);
262 return QSORT_CMP(nr_a, nr_b);
265 void be_ifg_check_sorted(const be_ifg_t *ifg)
267 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
268 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
271 const int node_count = be_ifg_check_get_node_count(ifg);
274 ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
276 be_ifg_foreach_node(ifg, iter1, n)
278 if(!node_is_in_irgs_storage(ifg->env->irg, n))
280 ir_printf("+%F is in ifg but not in the current irg!", n);
281 assert (node_is_in_irgs_storage(ifg->env->irg, n));
288 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
290 for (i = 0; i < node_count; i++)
292 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
297 degree = be_ifg_degree(ifg, all_nodes[i]);
299 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
305 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
307 ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
309 for(k = 0; k < j; k++)
311 ir_printf("%+F, ", neighbours[k]);
323 void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
325 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
326 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
329 const int node_count = be_ifg_check_get_node_count(ifg);
332 ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
334 be_ifg_foreach_node(ifg, iter1, n)
336 if(!node_is_in_irgs_storage(ifg->env->irg, n))
338 ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
339 assert (node_is_in_irgs_storage(ifg->env->irg, n));
346 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
348 for (i = 0; i < node_count; i++)
350 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
355 degree = be_ifg_degree(ifg, all_nodes[i]);
357 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
363 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
365 ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
367 for(k = 0; k < j; k++)
369 ir_fprintf (f,"%+F, ", neighbours[k]);
381 void be_ifg_check_performance(be_chordal_env_t *chordal_env)
384 int tests = BE_CH_PERFORMANCETEST_COUNT;
392 be_ifg_t *old_if = chordal_env->ifg;
394 lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg");
395 unsigned long elapsed_usec = 0;
397 if (get_irg_estimated_node_cnt(chordal_env->irg) >= BE_CH_PERFORMANCETEST_MIN_NODES)
399 coloring_init(&coloring, chordal_env->irg, chordal_env->birg->main_env->arch_env);
400 coloring_save(&coloring);
402 lc_timer_reset(timer);
404 for (i = 0; i<tests; i++) /* performance test with std */
407 used_memory = lc_get_heap_used_bytes();
409 rt = lc_timer_enter_high_priority();
410 lc_timer_start(timer);
412 chordal_env->ifg = be_ifg_std_new(chordal_env);
414 lc_timer_stop(timer);
415 rt = lc_timer_leave_high_priority();
417 used_memory = lc_get_heap_used_bytes() - used_memory;
419 coloring_restore(&coloring);
422 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
423 co_build_ou_structure(co);
424 co_build_graph_structure(co);
426 rt = lc_timer_enter_high_priority();
427 lc_timer_start(timer);
429 co_solve_heuristic_new(co);
431 lc_timer_stop(timer);
432 rt = lc_timer_leave_high_priority();
434 co_free_graph_structure(co);
435 co_free_ou_structure(co);
437 be_ifg_free(chordal_env->ifg);
441 elapsed_usec = lc_timer_elapsed_usec(timer);
442 /* calculating average */
443 elapsed_usec = elapsed_usec / tests;
445 ir_printf("\nstd:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
450 for (i = 0; i<tests; i++) /* performance test with clique */
452 used_memory = lc_get_heap_used_bytes();
454 rt = lc_timer_enter_high_priority();
455 lc_timer_start(timer);
457 chordal_env->ifg = be_ifg_clique_new(chordal_env);
459 lc_timer_stop(timer);
460 rt = lc_timer_leave_high_priority();
462 used_memory = lc_get_heap_used_bytes() - used_memory;
464 coloring_restore(&coloring);
467 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
468 co_build_ou_structure(co);
469 co_build_graph_structure(co);
471 rt = lc_timer_enter_high_priority();
472 lc_timer_start(timer);
474 co_solve_heuristic_new(co);
476 lc_timer_stop(timer);
477 rt = lc_timer_leave_high_priority();
479 co_free_graph_structure(co);
480 co_free_ou_structure(co);
482 be_ifg_free(chordal_env->ifg);
486 elapsed_usec = lc_timer_elapsed_usec(timer);
487 /* calculating average */
488 elapsed_usec = elapsed_usec / tests;
490 ir_printf("\nclique:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
495 for (i = 0; i<tests; i++) /* performance test with list */
497 used_memory = lc_get_heap_used_bytes();
499 rt = lc_timer_enter_high_priority();
500 lc_timer_start(timer);
502 chordal_env->ifg = be_ifg_list_new(chordal_env);
504 lc_timer_stop(timer);
505 rt = lc_timer_leave_high_priority();
507 used_memory = lc_get_heap_used_bytes() - used_memory;
509 coloring_restore(&coloring);
512 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
513 co_build_ou_structure(co);
514 co_build_graph_structure(co);
516 rt = lc_timer_enter_high_priority();
517 lc_timer_start(timer);
519 co_solve_heuristic_new(co);
521 lc_timer_stop(timer);
522 rt = lc_timer_leave_high_priority();
524 co_free_graph_structure(co);
525 co_free_ou_structure(co);
527 be_ifg_free(chordal_env->ifg);
531 elapsed_usec = lc_timer_elapsed_usec(timer);
532 /* calculating average */
533 elapsed_usec = elapsed_usec / tests;
535 ir_printf("\nlist:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
540 for (i = 0; i<tests; i++) /* performance test with pointer */
542 used_memory = lc_get_heap_used_bytes();
544 rt = lc_timer_enter_high_priority();
545 lc_timer_start(timer);
547 chordal_env->ifg = be_ifg_pointer_new(chordal_env);
549 lc_timer_stop(timer);
550 rt = lc_timer_leave_high_priority();
552 used_memory = lc_get_heap_used_bytes() - used_memory;
554 coloring_restore(&coloring);
557 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
558 co_build_ou_structure(co);
559 co_build_graph_structure(co);
561 rt = lc_timer_enter_high_priority();
562 lc_timer_start(timer);
564 co_solve_heuristic_new(co);
566 lc_timer_stop(timer);
567 rt = lc_timer_leave_high_priority();
569 co_free_graph_structure(co);
570 co_free_ou_structure(co);
572 be_ifg_free(chordal_env->ifg);
576 elapsed_usec = lc_timer_elapsed_usec(timer);
577 /* calculating average */
578 elapsed_usec = elapsed_usec / tests;
580 ir_printf("\npointer:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
587 chordal_env->ifg = old_if;
588 #endif /* WITH_LIBCORE */
591 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
593 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
594 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
595 bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
599 fprintf(file, "graph G {\n\tgraph [");
601 cb->graph_attr(file, self);
602 fprintf(file, "];\n");
605 cb->at_begin(file, self);
607 be_ifg_foreach_node(ifg, nodes_it, n) {
608 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
609 int idx = get_irn_idx(n);
610 bitset_set(nodes, idx);
611 fprintf(file, "\tnode [");
613 cb->node_attr(file, self, n);
614 fprintf(file, "]; n%d;\n", idx);
618 /* Check, if all neighbours are indeed connected to the node. */
619 be_ifg_foreach_node(ifg, nodes_it, n) {
620 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
621 int n_idx = get_irn_idx(n);
622 int m_idx = get_irn_idx(m);
624 if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
625 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
627 cb->edge_attr(file, self, n, m);
628 fprintf(file, "];\n");
634 cb->at_end(file, self);
636 fprintf(file, "}\n");
640 static void int_comp_rec(be_irg_t *birg, be_ifg_t *ifg, ir_node *n, bitset_t *seen)
642 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
645 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
646 if(!bitset_contains_irn(seen, m) && !arch_irn_is(birg->main_env->arch_env, m, ignore)) {
647 bitset_add_irn(seen, m);
648 int_comp_rec(birg, ifg, m, seen);
654 static int int_component_stat(be_irg_t *birg, be_ifg_t *ifg)
657 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
658 bitset_t *seen = bitset_irg_malloc(birg->irg);
662 be_ifg_foreach_node(ifg, nodes_it, n) {
663 if (! bitset_contains_irn(seen, n) && ! arch_irn_is(birg->main_env->arch_env, n, ignore)) {
665 bitset_add_irn(seen, n);
666 int_comp_rec(birg, ifg, n, seen);
674 void be_ifg_stat(be_irg_t *birg, be_ifg_t *ifg, be_ifg_stat_t *stat)
676 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
677 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
678 bitset_t *nodes = bitset_irg_malloc(birg->irg);
681 memset(stat, 0, sizeof(stat[0]));
683 be_ifg_foreach_node(ifg, nodes_it, n) {
685 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
686 bitset_add_irn(nodes, n);
687 stat->n_edges += !bitset_contains_irn(nodes, m);
691 stat->n_comps = int_component_stat(birg, ifg);
704 static int ifg_flavor = BE_IFG_STD;
706 static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
707 { "std", BE_IFG_STD },
708 { "fast", BE_IFG_FAST },
709 { "clique", BE_IFG_CLIQUE },
710 { "pointer", BE_IFG_POINTER },
711 { "list", BE_IFG_LIST },
712 { "check", BE_IFG_CHECK },
716 static lc_opt_enum_int_var_t ifg_flavor_var = {
717 &ifg_flavor, ifg_flavor_items
720 static const lc_opt_table_entry_t be_ifg_options[] = {
721 LC_OPT_ENT_ENUM_PTR ("ifg", "interference graph flavour", &ifg_flavor_var),
725 void be_init_ifg(void)
727 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
728 lc_opt_entry_t *ifg_grp = lc_opt_get_grp(be_grp, "ifg");
730 lc_opt_add_table(ifg_grp, be_ifg_options);
733 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ifg);
735 static FILE *be_ifg_open(const be_chordal_env_t *env, const char *prefix)
740 ir_snprintf(buf, sizeof(buf), "%s%F_%s.log", prefix, env->irg, env->cls->name);
741 result = fopen(buf, "wt");
743 panic("Couldn't open '%s' for writing.", buf);
749 static void check_ifg_implementations(const be_chordal_env_t *chordal_env)
754 f = be_ifg_open(chordal_env, "std");
755 ifg = be_ifg_std_new(chordal_env);
756 be_ifg_check_sorted_to_file(ifg, f);
760 f = be_ifg_open(chordal_env, "list");
761 ifg = be_ifg_list_new(chordal_env);
762 be_ifg_check_sorted_to_file(ifg, f);
766 f = be_ifg_open(chordal_env, "clique");
767 ifg = be_ifg_clique_new(chordal_env);
768 be_ifg_check_sorted_to_file(ifg, f);
772 f = be_ifg_open(chordal_env, "pointer");
773 ifg = be_ifg_pointer_new(chordal_env);
774 be_ifg_check_sorted_to_file(ifg, f);
779 be_ifg_t *be_create_ifg(const be_chordal_env_t *chordal_env)
781 be_ifg_t *ifg = NULL;
783 switch (ifg_flavor) {
786 fprintf(stderr, "no valid ifg flavour selected. falling back to std\n");
789 ifg = be_ifg_std_new(chordal_env);
792 ifg = be_ifg_clique_new(chordal_env);
795 ifg = be_ifg_pointer_new(chordal_env);
798 ifg = be_ifg_list_new(chordal_env);
801 check_ifg_implementations(chordal_env);
802 /* Build the interference graph. */
803 ifg = be_ifg_std_new(chordal_env);