4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
15 #include <libcore/lc_opts.h>
16 #include <libcore/lc_opts_enum.h>
17 #include <libcore/lc_timing.h>
27 #include "beifg_impl.h"
29 #include "irphase_t.h"
30 #include "bechordal.h"
34 #include "becopystat.h"
35 #include "becopyopt.h"
38 /** Defines values for the ifg performance test */
39 #define BE_CH_PERFORMANCETEST_MIN_NODES (50)
40 #define BE_CH_PERFORMANCETEST_COUNT (500)
42 typedef struct _coloring_t coloring_t;
46 const arch_env_t *arch_env;
50 size_t (be_ifg_nodes_iter_size)(const be_ifg_t *ifg)
52 return ifg->impl->nodes_iter_size;
55 size_t (be_ifg_neighbours_iter_size)(const be_ifg_t *ifg)
57 return ifg->impl->neighbours_iter_size;
60 size_t (be_ifg_cliques_iter_size)(const be_ifg_t *ifg)
62 return ifg->impl->cliques_iter_size;
65 static void *regs_irn_data_init(phase_t *ph, ir_node *irn, void *data)
67 coloring_t *coloring = (coloring_t *) ph;
68 return (void *) arch_get_irn_register(coloring->arch_env, irn);
71 coloring_t *coloring_init(coloring_t *c, ir_graph *irg, const arch_env_t *aenv)
73 phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init);
79 static void get_irn_color(ir_node *irn, void *c)
81 coloring_t *coloring = c;
82 phase_get_or_set_irn_data(&coloring->ph, irn);
85 static void restore_irn_color(ir_node *irn, void *c)
87 coloring_t *coloring = c;
88 const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn);
90 arch_set_irn_register(coloring->arch_env, irn, reg);
93 void coloring_save(coloring_t *c)
95 irg_walk_graph(c->irg, NULL, get_irn_color, c);
98 void coloring_restore(coloring_t *c)
100 irg_walk_graph(c->irg, NULL, restore_irn_color, c);
103 void (be_ifg_free)(be_ifg_t *ifg)
105 ifg->impl->free(ifg);
108 int (be_ifg_connected)(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
110 return ifg->impl->connected(ifg, a, b);
113 ir_node *(be_ifg_neighbours_begin)(const be_ifg_t *ifg, void *iter, const ir_node *irn)
115 return ifg->impl->neighbours_begin(ifg, iter, irn);
118 ir_node *(be_ifg_neighbours_next)(const be_ifg_t *ifg, void *iter)
120 return ifg->impl->neighbours_next(ifg, iter);
123 void (be_ifg_neighbours_break)(const be_ifg_t *ifg, void *iter)
125 ifg->impl->neighbours_break(ifg, iter);
128 ir_node *(be_ifg_nodes_begin)(const be_ifg_t *ifg, void *iter)
130 return ifg->impl->nodes_begin(ifg, iter);
133 ir_node *(be_ifg_nodes_next)(const be_ifg_t *ifg, void *iter)
135 return ifg->impl->nodes_next(ifg, iter);
138 void (be_ifg_nodes_break)(const be_ifg_t *ifg, void *iter)
140 ifg->impl->nodes_break(ifg, iter);
143 int (be_ifg_cliques_begin)(const be_ifg_t *ifg, void *iter, ir_node **buf)
145 return ifg->impl->cliques_begin(ifg, iter, buf);
148 int (be_ifg_cliques_next)(const be_ifg_t *ifg, void *iter)
150 return ifg->impl->cliques_next(ifg, iter);
153 void (be_ifg_cliques_break)(const be_ifg_t *ifg, void *iter)
155 ifg->impl->cliques_break(ifg, iter);
158 int (be_ifg_degree)(const be_ifg_t *ifg, const ir_node *irn)
160 return ifg->impl->degree(ifg, irn);
164 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
166 int degree = be_ifg_degree(ifg, irn);
167 void *iter = be_ifg_neighbours_iter_alloca(ifg);
169 ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0]));
175 be_ifg_foreach_neighbour(ifg, iter, irn, curr)
176 neighbours[i++] = curr;
178 for(i = 0; i < degree; ++i) {
179 for(j = 0; j < i; ++j)
180 if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
191 void be_ifg_check(const be_ifg_t *ifg)
193 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
194 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
198 int neighbours_count = 0;
201 /* count all nodes */
202 ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
203 be_ifg_foreach_node(ifg,iter1,n)
206 degree = be_ifg_degree(ifg, n);
207 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
210 ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
212 /* Check, if all neighbours are indeed connected to the node. */
213 be_ifg_foreach_node(ifg, iter1, n)
215 ir_printf("\n%+F; ", n);
216 be_ifg_foreach_neighbour(ifg, iter2, n, m)
218 ir_printf("%+F; ", m);
220 if(!be_ifg_connected(ifg, n, m))
221 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
224 ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
227 int be_ifg_check_get_node_count(const be_ifg_t *ifg)
229 void *iter = be_ifg_nodes_iter_alloca(ifg);
233 be_ifg_foreach_node(ifg, iter, n)
241 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
243 const ir_node *node_a = *(ir_node **)a;
244 const ir_node *node_b = *(ir_node **)b;
246 long nr_a = get_irn_node_nr(node_a);
247 long nr_b = get_irn_node_nr(node_b);
249 return QSORT_CMP(nr_a, nr_b);
252 void be_ifg_check_sorted(const be_ifg_t *ifg)
254 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
255 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
258 const int node_count = be_ifg_check_get_node_count(ifg);
261 ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
263 be_ifg_foreach_node(ifg, iter1, n)
265 if(!node_is_in_irgs_storage(ifg->env->irg, n))
267 ir_printf("+%F is in ifg but not in the current irg!", n);
268 assert (node_is_in_irgs_storage(ifg->env->irg, n));
275 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
277 for (i = 0; i < node_count; i++)
279 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
284 degree = be_ifg_degree(ifg, all_nodes[i]);
286 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
292 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
294 ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
296 for(k = 0; k < j; k++)
298 ir_printf("%+F, ", neighbours[k]);
310 void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
312 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
313 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
316 const int node_count = be_ifg_check_get_node_count(ifg);
319 ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
321 be_ifg_foreach_node(ifg, iter1, n)
323 if(!node_is_in_irgs_storage(ifg->env->irg, n))
325 ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
326 assert (node_is_in_irgs_storage(ifg->env->irg, n));
333 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
335 for (i = 0; i < node_count; i++)
337 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
342 degree = be_ifg_degree(ifg, all_nodes[i]);
344 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
350 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
352 ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
354 for(k = 0; k < j; k++)
356 ir_fprintf (f,"%+F, ", neighbours[k]);
368 void be_ifg_check_performance(be_chordal_env_t *chordal_env)
370 int tests = BE_CH_PERFORMANCETEST_COUNT;
378 be_ifg_t *old_if = chordal_env->ifg;
380 lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg");
381 unsigned long elapsed_usec = 0;
383 if (get_irg_estimated_node_cnt(chordal_env->irg) >= BE_CH_PERFORMANCETEST_MIN_NODES)
385 coloring_init(&coloring, chordal_env->irg, chordal_env->birg->main_env->arch_env);
386 coloring_save(&coloring);
388 lc_timer_reset(timer);
390 for (i = 0; i<tests; i++) /* performance test with std */
393 used_memory = lc_get_heap_used_bytes();
395 rt = lc_timer_enter_high_priority();
396 lc_timer_start(timer);
398 chordal_env->ifg = be_ifg_std_new(chordal_env);
400 lc_timer_stop(timer);
401 rt = lc_timer_leave_high_priority();
403 used_memory = lc_get_heap_used_bytes() - used_memory;
405 coloring_restore(&coloring);
408 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
409 co_build_ou_structure(co);
410 co_build_graph_structure(co);
412 rt = lc_timer_enter_high_priority();
413 lc_timer_start(timer);
415 co_solve_heuristic_new(co);
417 lc_timer_stop(timer);
418 rt = lc_timer_leave_high_priority();
420 co_free_graph_structure(co);
421 co_free_ou_structure(co);
423 be_ifg_free(chordal_env->ifg);
427 elapsed_usec = lc_timer_elapsed_usec(timer);
428 /* calculating average */
429 elapsed_usec = elapsed_usec / tests;
431 ir_printf("\nstd:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
436 for (i = 0; i<tests; i++) /* performance test with clique */
438 used_memory = lc_get_heap_used_bytes();
440 rt = lc_timer_enter_high_priority();
441 lc_timer_start(timer);
443 chordal_env->ifg = be_ifg_clique_new(chordal_env);
445 lc_timer_stop(timer);
446 rt = lc_timer_leave_high_priority();
448 used_memory = lc_get_heap_used_bytes() - used_memory;
450 coloring_restore(&coloring);
453 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
454 co_build_ou_structure(co);
455 co_build_graph_structure(co);
457 rt = lc_timer_enter_high_priority();
458 lc_timer_start(timer);
460 co_solve_heuristic_new(co);
462 lc_timer_stop(timer);
463 rt = lc_timer_leave_high_priority();
465 co_free_graph_structure(co);
466 co_free_ou_structure(co);
468 be_ifg_free(chordal_env->ifg);
472 elapsed_usec = lc_timer_elapsed_usec(timer);
473 /* calculating average */
474 elapsed_usec = elapsed_usec / tests;
476 ir_printf("\nclique:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
481 for (i = 0; i<tests; i++) /* performance test with list */
483 used_memory = lc_get_heap_used_bytes();
485 rt = lc_timer_enter_high_priority();
486 lc_timer_start(timer);
488 chordal_env->ifg = be_ifg_list_new(chordal_env);
490 lc_timer_stop(timer);
491 rt = lc_timer_leave_high_priority();
493 used_memory = lc_get_heap_used_bytes() - used_memory;
495 coloring_restore(&coloring);
498 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
499 co_build_ou_structure(co);
500 co_build_graph_structure(co);
502 rt = lc_timer_enter_high_priority();
503 lc_timer_start(timer);
505 co_solve_heuristic_new(co);
507 lc_timer_stop(timer);
508 rt = lc_timer_leave_high_priority();
510 co_free_graph_structure(co);
511 co_free_ou_structure(co);
513 be_ifg_free(chordal_env->ifg);
517 elapsed_usec = lc_timer_elapsed_usec(timer);
518 /* calculating average */
519 elapsed_usec = elapsed_usec / tests;
521 ir_printf("\nlist:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
526 for (i = 0; i<tests; i++) /* performance test with pointer */
528 used_memory = lc_get_heap_used_bytes();
530 rt = lc_timer_enter_high_priority();
531 lc_timer_start(timer);
533 chordal_env->ifg = be_ifg_pointer_new(chordal_env);
535 lc_timer_stop(timer);
536 rt = lc_timer_leave_high_priority();
538 used_memory = lc_get_heap_used_bytes() - used_memory;
540 coloring_restore(&coloring);
543 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
544 co_build_ou_structure(co);
545 co_build_graph_structure(co);
547 rt = lc_timer_enter_high_priority();
548 lc_timer_start(timer);
550 co_solve_heuristic_new(co);
552 lc_timer_stop(timer);
553 rt = lc_timer_leave_high_priority();
555 co_free_graph_structure(co);
556 co_free_ou_structure(co);
558 be_ifg_free(chordal_env->ifg);
562 elapsed_usec = lc_timer_elapsed_usec(timer);
563 /* calculating average */
564 elapsed_usec = elapsed_usec / tests;
566 ir_printf("\npointer:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
573 chordal_env->ifg = old_if;
576 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
578 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
579 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
580 bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
584 fprintf(file, "graph G {\n\tgraph [");
586 cb->graph_attr(file, self);
587 fprintf(file, "];\n");
590 cb->at_begin(file, self);
592 be_ifg_foreach_node(ifg, nodes_it, n) {
593 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
594 int idx = get_irn_idx(n);
595 bitset_set(nodes, idx);
596 fprintf(file, "\tnode [");
598 cb->node_attr(file, self, n);
599 fprintf(file, "]; n%d;\n", idx);
603 /* Check, if all neighbours are indeed connected to the node. */
604 be_ifg_foreach_node(ifg, nodes_it, n) {
605 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
606 int n_idx = get_irn_idx(n);
607 int m_idx = get_irn_idx(m);
609 if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
610 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
612 cb->edge_attr(file, self, n, m);
613 fprintf(file, "];\n");
619 cb->at_end(file, self);
621 fprintf(file, "}\n");
625 static void int_comp_rec(be_irg_t *birg, be_ifg_t *ifg, ir_node *n, bitset_t *seen)
627 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
630 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
631 if(!bitset_contains_irn(seen, m) && !arch_irn_is(birg->main_env->arch_env, m, ignore)) {
632 bitset_add_irn(seen, m);
633 int_comp_rec(birg, ifg, m, seen);
639 static int int_component_stat(be_irg_t *birg, be_ifg_t *ifg)
642 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
643 bitset_t *seen = bitset_irg_malloc(birg->irg);
647 be_ifg_foreach_node(ifg, nodes_it, n) {
648 if (! bitset_contains_irn(seen, n) && ! arch_irn_is(birg->main_env->arch_env, n, ignore)) {
650 bitset_add_irn(seen, n);
651 int_comp_rec(birg, ifg, n, seen);
659 void be_ifg_stat(be_irg_t *birg, be_ifg_t *ifg, be_ifg_stat_t *stat)
661 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
662 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
663 bitset_t *nodes = bitset_irg_malloc(birg->irg);
666 memset(stat, 0, sizeof(stat[0]));
668 be_ifg_foreach_node(ifg, nodes_it, n) {
670 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
671 bitset_add_irn(nodes, n);
672 stat->n_edges += !bitset_contains_irn(nodes, m);
676 stat->n_comps = int_component_stat(birg, ifg);
689 static int ifg_flavor = BE_IFG_STD;
691 static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
692 { "std", BE_IFG_STD },
693 { "fast", BE_IFG_FAST },
694 { "clique", BE_IFG_CLIQUE },
695 { "pointer", BE_IFG_POINTER },
696 { "list", BE_IFG_LIST },
697 { "check", BE_IFG_CHECK },
701 static lc_opt_enum_int_var_t ifg_flavor_var = {
702 &ifg_flavor, ifg_flavor_items
705 static const lc_opt_table_entry_t be_ifg_options[] = {
706 LC_OPT_ENT_ENUM_PTR ("ifg", "interference graph flavour", &ifg_flavor_var),
710 void be_init_ifg(void)
712 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
713 lc_opt_entry_t *ifg_grp = lc_opt_get_grp(be_grp, "ifg");
715 lc_opt_add_table(ifg_grp, be_ifg_options);
718 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ifg);
720 static FILE *be_ifg_open(const be_chordal_env_t *env, const char *prefix)
725 ir_snprintf(buf, sizeof(buf), "%s%F_%s.log", prefix, env->irg, env->cls->name);
726 result = fopen(buf, "wt");
728 panic("Couldn't open '%s' for writing.", buf);
734 static void check_ifg_implementations(const be_chordal_env_t *chordal_env)
739 f = be_ifg_open(chordal_env, "std");
740 ifg = be_ifg_std_new(chordal_env);
741 be_ifg_check_sorted_to_file(ifg, f);
745 f = be_ifg_open(chordal_env, "list");
746 ifg = be_ifg_list_new(chordal_env);
747 be_ifg_check_sorted_to_file(ifg, f);
751 f = be_ifg_open(chordal_env, "clique");
752 ifg = be_ifg_clique_new(chordal_env);
753 be_ifg_check_sorted_to_file(ifg, f);
757 f = be_ifg_open(chordal_env, "pointer");
758 ifg = be_ifg_pointer_new(chordal_env);
759 be_ifg_check_sorted_to_file(ifg, f);
764 be_ifg_t *be_create_ifg(const be_chordal_env_t *chordal_env)
766 be_ifg_t *ifg = NULL;
768 switch (ifg_flavor) {
771 fprintf(stderr, "no valid ifg flavour selected. falling back to std\n");
774 ifg = be_ifg_std_new(chordal_env);
777 ifg = be_ifg_clique_new(chordal_env);
780 ifg = be_ifg_pointer_new(chordal_env);
783 ifg = be_ifg_list_new(chordal_env);
786 check_ifg_implementations(chordal_env);
787 /* Build the interference graph. */
788 ifg = be_ifg_std_new(chordal_env);