4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
21 #endif /* __linux__ */
27 #include <libcore/lc_opts.h>
28 #include <libcore/lc_opts_enum.h>
29 #include <libcore/lc_timing.h>
39 #include "beifg_impl.h"
41 #include "irphase_t.h"
42 #include "bechordal.h"
45 #include "becopystat.h"
46 #include "becopyopt.h"
49 /** Defines values for the ifg performance test */
50 #define BE_CH_PERFORMANCETEST_MIN_NODES (50)
51 #define BE_CH_PERFORMANCETEST_COUNT (500)
53 typedef struct _coloring_t coloring_t;
57 const arch_env_t *arch_env;
61 size_t (be_ifg_nodes_iter_size)(const be_ifg_t *ifg)
63 return ifg->impl->nodes_iter_size;
66 size_t (be_ifg_neighbours_iter_size)(const be_ifg_t *ifg)
68 return ifg->impl->neighbours_iter_size;
71 size_t (be_ifg_cliques_iter_size)(const be_ifg_t *ifg)
73 return ifg->impl->cliques_iter_size;
76 static void *regs_irn_data_init(phase_t *ph, ir_node *irn, void *data)
78 coloring_t *coloring = (coloring_t *) ph;
79 return (void *) arch_get_irn_register(coloring->arch_env, irn);
82 coloring_t *coloring_init(coloring_t *c, ir_graph *irg, const arch_env_t *aenv)
84 phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init);
90 static void get_irn_color(ir_node *irn, void *c)
92 coloring_t *coloring = c;
93 phase_get_or_set_irn_data(&coloring->ph, irn);
96 static void restore_irn_color(ir_node *irn, void *c)
98 coloring_t *coloring = c;
99 const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn);
101 arch_set_irn_register(coloring->arch_env, irn, reg);
104 void coloring_save(coloring_t *c)
106 irg_walk_graph(c->irg, NULL, get_irn_color, c);
109 void coloring_restore(coloring_t *c)
111 irg_walk_graph(c->irg, NULL, restore_irn_color, c);
114 void (be_ifg_free)(be_ifg_t *ifg)
116 ifg->impl->free(ifg);
119 int (be_ifg_connected)(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
121 return ifg->impl->connected(ifg, a, b);
124 ir_node *(be_ifg_neighbours_begin)(const be_ifg_t *ifg, void *iter, const ir_node *irn)
126 return ifg->impl->neighbours_begin(ifg, iter, irn);
129 ir_node *(be_ifg_neighbours_next)(const be_ifg_t *ifg, void *iter)
131 return ifg->impl->neighbours_next(ifg, iter);
134 void (be_ifg_neighbours_break)(const be_ifg_t *ifg, void *iter)
136 ifg->impl->neighbours_break(ifg, iter);
139 ir_node *(be_ifg_nodes_begin)(const be_ifg_t *ifg, void *iter)
141 return ifg->impl->nodes_begin(ifg, iter);
144 ir_node *(be_ifg_nodes_next)(const be_ifg_t *ifg, void *iter)
146 return ifg->impl->nodes_next(ifg, iter);
149 void (be_ifg_nodes_break)(const be_ifg_t *ifg, void *iter)
151 ifg->impl->nodes_break(ifg, iter);
154 int (be_ifg_cliques_begin)(const be_ifg_t *ifg, void *iter, ir_node **buf)
156 return ifg->impl->cliques_begin(ifg, iter, buf);
159 int (be_ifg_cliques_next)(const be_ifg_t *ifg, void *iter)
161 return ifg->impl->cliques_next(ifg, iter);
164 void (be_ifg_cliques_break)(const be_ifg_t *ifg, void *iter)
166 ifg->impl->cliques_break(ifg, iter);
169 int (be_ifg_degree)(const be_ifg_t *ifg, const ir_node *irn)
171 return ifg->impl->degree(ifg, irn);
175 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
177 int degree = be_ifg_degree(ifg, irn);
178 void *iter = be_ifg_neighbours_iter_alloca(ifg);
180 ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0]));
186 be_ifg_foreach_neighbour(ifg, iter, irn, curr)
187 neighbours[i++] = curr;
189 for(i = 0; i < degree; ++i) {
190 for(j = 0; j < i; ++j)
191 if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
202 void be_ifg_check(const be_ifg_t *ifg)
204 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
205 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
209 int neighbours_count = 0;
212 /* count all nodes */
213 ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
214 be_ifg_foreach_node(ifg,iter1,n)
217 degree = be_ifg_degree(ifg, n);
218 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
221 ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
223 /* Check, if all neighbours are indeed connected to the node. */
224 be_ifg_foreach_node(ifg, iter1, n)
226 ir_printf("\n%+F; ", n);
227 be_ifg_foreach_neighbour(ifg, iter2, n, m)
229 ir_printf("%+F; ", m);
231 if(!be_ifg_connected(ifg, n, m))
232 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
235 ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
238 int be_ifg_check_get_node_count(const be_ifg_t *ifg)
240 void *iter = be_ifg_nodes_iter_alloca(ifg);
244 be_ifg_foreach_node(ifg, iter, n)
252 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
254 const ir_node *node_a = *(ir_node **)a;
255 const ir_node *node_b = *(ir_node **)b;
257 long nr_a = get_irn_node_nr(node_a);
258 long nr_b = get_irn_node_nr(node_b);
260 return QSORT_CMP(nr_a, nr_b);
263 void be_ifg_check_sorted(const be_ifg_t *ifg)
265 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
266 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
269 const int node_count = be_ifg_check_get_node_count(ifg);
272 ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
274 be_ifg_foreach_node(ifg, iter1, n)
276 if(!node_is_in_irgs_storage(ifg->env->irg, n))
278 ir_printf("+%F is in ifg but not in the current irg!", n);
279 assert (node_is_in_irgs_storage(ifg->env->irg, n));
286 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
288 for (i = 0; i < node_count; i++)
290 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
295 degree = be_ifg_degree(ifg, all_nodes[i]);
297 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
303 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
305 ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
307 for(k = 0; k < j; k++)
309 ir_printf("%+F, ", neighbours[k]);
321 void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
323 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
324 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
327 const int node_count = be_ifg_check_get_node_count(ifg);
330 ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
332 be_ifg_foreach_node(ifg, iter1, n)
334 if(!node_is_in_irgs_storage(ifg->env->irg, n))
336 ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
337 assert (node_is_in_irgs_storage(ifg->env->irg, n));
344 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
346 for (i = 0; i < node_count; i++)
348 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
353 degree = be_ifg_degree(ifg, all_nodes[i]);
355 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
361 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
363 ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
365 for(k = 0; k < j; k++)
367 ir_fprintf (f,"%+F, ", neighbours[k]);
379 void be_ifg_check_performance(be_chordal_env_t *chordal_env)
381 int tests = BE_CH_PERFORMANCETEST_COUNT;
389 be_ifg_t *old_if = chordal_env->ifg;
391 lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg");
392 unsigned long elapsed_usec = 0;
394 if (get_irg_estimated_node_cnt(chordal_env->irg) >= BE_CH_PERFORMANCETEST_MIN_NODES)
396 coloring_init(&coloring, chordal_env->irg, chordal_env->birg->main_env->arch_env);
397 coloring_save(&coloring);
399 lc_timer_reset(timer);
401 for (i = 0; i<tests; i++) /* performance test with std */
404 used_memory = lc_get_heap_used_bytes();
406 rt = lc_timer_enter_high_priority();
407 lc_timer_start(timer);
409 chordal_env->ifg = be_ifg_std_new(chordal_env);
411 lc_timer_stop(timer);
412 rt = lc_timer_leave_high_priority();
414 used_memory = lc_get_heap_used_bytes() - used_memory;
416 coloring_restore(&coloring);
419 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
420 co_build_ou_structure(co);
421 co_build_graph_structure(co);
423 rt = lc_timer_enter_high_priority();
424 lc_timer_start(timer);
426 co_solve_heuristic_new(co);
428 lc_timer_stop(timer);
429 rt = lc_timer_leave_high_priority();
431 co_free_graph_structure(co);
432 co_free_ou_structure(co);
434 be_ifg_free(chordal_env->ifg);
438 elapsed_usec = lc_timer_elapsed_usec(timer);
439 /* calculating average */
440 elapsed_usec = elapsed_usec / tests;
442 ir_printf("\nstd:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
447 for (i = 0; i<tests; i++) /* performance test with clique */
449 used_memory = lc_get_heap_used_bytes();
451 rt = lc_timer_enter_high_priority();
452 lc_timer_start(timer);
454 chordal_env->ifg = be_ifg_clique_new(chordal_env);
456 lc_timer_stop(timer);
457 rt = lc_timer_leave_high_priority();
459 used_memory = lc_get_heap_used_bytes() - used_memory;
461 coloring_restore(&coloring);
464 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
465 co_build_ou_structure(co);
466 co_build_graph_structure(co);
468 rt = lc_timer_enter_high_priority();
469 lc_timer_start(timer);
471 co_solve_heuristic_new(co);
473 lc_timer_stop(timer);
474 rt = lc_timer_leave_high_priority();
476 co_free_graph_structure(co);
477 co_free_ou_structure(co);
479 be_ifg_free(chordal_env->ifg);
483 elapsed_usec = lc_timer_elapsed_usec(timer);
484 /* calculating average */
485 elapsed_usec = elapsed_usec / tests;
487 ir_printf("\nclique:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
492 for (i = 0; i<tests; i++) /* performance test with list */
494 used_memory = lc_get_heap_used_bytes();
496 rt = lc_timer_enter_high_priority();
497 lc_timer_start(timer);
499 chordal_env->ifg = be_ifg_list_new(chordal_env);
501 lc_timer_stop(timer);
502 rt = lc_timer_leave_high_priority();
504 used_memory = lc_get_heap_used_bytes() - used_memory;
506 coloring_restore(&coloring);
509 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
510 co_build_ou_structure(co);
511 co_build_graph_structure(co);
513 rt = lc_timer_enter_high_priority();
514 lc_timer_start(timer);
516 co_solve_heuristic_new(co);
518 lc_timer_stop(timer);
519 rt = lc_timer_leave_high_priority();
521 co_free_graph_structure(co);
522 co_free_ou_structure(co);
524 be_ifg_free(chordal_env->ifg);
528 elapsed_usec = lc_timer_elapsed_usec(timer);
529 /* calculating average */
530 elapsed_usec = elapsed_usec / tests;
532 ir_printf("\nlist:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
537 for (i = 0; i<tests; i++) /* performance test with pointer */
539 used_memory = lc_get_heap_used_bytes();
541 rt = lc_timer_enter_high_priority();
542 lc_timer_start(timer);
544 chordal_env->ifg = be_ifg_pointer_new(chordal_env);
546 lc_timer_stop(timer);
547 rt = lc_timer_leave_high_priority();
549 used_memory = lc_get_heap_used_bytes() - used_memory;
551 coloring_restore(&coloring);
554 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
555 co_build_ou_structure(co);
556 co_build_graph_structure(co);
558 rt = lc_timer_enter_high_priority();
559 lc_timer_start(timer);
561 co_solve_heuristic_new(co);
563 lc_timer_stop(timer);
564 rt = lc_timer_leave_high_priority();
566 co_free_graph_structure(co);
567 co_free_ou_structure(co);
569 be_ifg_free(chordal_env->ifg);
573 elapsed_usec = lc_timer_elapsed_usec(timer);
574 /* calculating average */
575 elapsed_usec = elapsed_usec / tests;
577 ir_printf("\npointer:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
584 chordal_env->ifg = old_if;
587 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
589 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
590 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
591 bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
595 fprintf(file, "graph G {\n\tgraph [");
597 cb->graph_attr(file, self);
598 fprintf(file, "];\n");
601 cb->at_begin(file, self);
603 be_ifg_foreach_node(ifg, nodes_it, n) {
604 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
605 int idx = get_irn_idx(n);
606 bitset_set(nodes, idx);
607 fprintf(file, "\tnode [");
609 cb->node_attr(file, self, n);
610 fprintf(file, "]; n%d;\n", idx);
614 /* Check, if all neighbours are indeed connected to the node. */
615 be_ifg_foreach_node(ifg, nodes_it, n) {
616 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
617 int n_idx = get_irn_idx(n);
618 int m_idx = get_irn_idx(m);
620 if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
621 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
623 cb->edge_attr(file, self, n, m);
624 fprintf(file, "];\n");
630 cb->at_end(file, self);
632 fprintf(file, "}\n");
636 static void int_comp_rec(be_irg_t *birg, be_ifg_t *ifg, ir_node *n, bitset_t *seen)
638 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
641 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
642 if(!bitset_contains_irn(seen, m) && !arch_irn_is(birg->main_env->arch_env, m, ignore)) {
643 bitset_add_irn(seen, m);
644 int_comp_rec(birg, ifg, m, seen);
650 static int int_component_stat(be_irg_t *birg, be_ifg_t *ifg)
653 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
654 bitset_t *seen = bitset_irg_malloc(birg->irg);
658 be_ifg_foreach_node(ifg, nodes_it, n) {
659 if (! bitset_contains_irn(seen, n) && ! arch_irn_is(birg->main_env->arch_env, n, ignore)) {
661 bitset_add_irn(seen, n);
662 int_comp_rec(birg, ifg, n, seen);
670 void be_ifg_stat(be_irg_t *birg, be_ifg_t *ifg, be_ifg_stat_t *stat)
672 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
673 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
674 bitset_t *nodes = bitset_irg_malloc(birg->irg);
677 memset(stat, 0, sizeof(stat[0]));
679 be_ifg_foreach_node(ifg, nodes_it, n) {
681 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
682 bitset_add_irn(nodes, n);
683 stat->n_edges += !bitset_contains_irn(nodes, m);
687 stat->n_comps = int_component_stat(birg, ifg);
700 static int ifg_flavor = BE_IFG_STD;
702 static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
703 { "std", BE_IFG_STD },
704 { "fast", BE_IFG_FAST },
705 { "clique", BE_IFG_CLIQUE },
706 { "pointer", BE_IFG_POINTER },
707 { "list", BE_IFG_LIST },
708 { "check", BE_IFG_CHECK },
712 static lc_opt_enum_int_var_t ifg_flavor_var = {
713 &ifg_flavor, ifg_flavor_items
716 static const lc_opt_table_entry_t be_ifg_options[] = {
717 LC_OPT_ENT_ENUM_PTR ("ifg", "interference graph flavour", &ifg_flavor_var),
721 void be_init_ifg(void)
723 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
724 lc_opt_entry_t *ifg_grp = lc_opt_get_grp(be_grp, "ifg");
726 lc_opt_add_table(ifg_grp, be_ifg_options);
729 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ifg);
731 static FILE *be_ifg_open(const be_chordal_env_t *env, const char *prefix)
736 ir_snprintf(buf, sizeof(buf), "%s%F_%s.log", prefix, env->irg, env->cls->name);
737 result = fopen(buf, "wt");
739 panic("Couldn't open '%s' for writing.", buf);
745 static void check_ifg_implementations(const be_chordal_env_t *chordal_env)
750 f = be_ifg_open(chordal_env, "std");
751 ifg = be_ifg_std_new(chordal_env);
752 be_ifg_check_sorted_to_file(ifg, f);
756 f = be_ifg_open(chordal_env, "list");
757 ifg = be_ifg_list_new(chordal_env);
758 be_ifg_check_sorted_to_file(ifg, f);
762 f = be_ifg_open(chordal_env, "clique");
763 ifg = be_ifg_clique_new(chordal_env);
764 be_ifg_check_sorted_to_file(ifg, f);
768 f = be_ifg_open(chordal_env, "pointer");
769 ifg = be_ifg_pointer_new(chordal_env);
770 be_ifg_check_sorted_to_file(ifg, f);
775 be_ifg_t *be_create_ifg(const be_chordal_env_t *chordal_env)
777 be_ifg_t *ifg = NULL;
779 switch (ifg_flavor) {
782 fprintf(stderr, "no valid ifg flavour selected. falling back to std\n");
785 ifg = be_ifg_std_new(chordal_env);
788 ifg = be_ifg_clique_new(chordal_env);
791 ifg = be_ifg_pointer_new(chordal_env);
794 ifg = be_ifg_list_new(chordal_env);
797 check_ifg_implementations(chordal_env);
798 /* Build the interference graph. */
799 ifg = be_ifg_std_new(chordal_env);