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"
28 #include "irphase_t.h"
29 #include "bechordal.h"
33 #include "becopystat.h"
34 #include "becopyopt.h"
37 /** Defines values for the ifg performance test */
38 #define BE_CH_PERFORMANCETEST_MIN_NODES (50)
39 #define BE_CH_PERFORMANCETEST_COUNT (500)
41 typedef struct _coloring_t coloring_t;
45 const arch_env_t *arch_env;
49 size_t (be_ifg_nodes_iter_size)(const be_ifg_t *ifg)
51 return ifg->impl->nodes_iter_size;
54 size_t (be_ifg_neighbours_iter_size)(const be_ifg_t *ifg)
56 return ifg->impl->neighbours_iter_size;
59 size_t (be_ifg_cliques_iter_size)(const be_ifg_t *ifg)
61 return ifg->impl->cliques_iter_size;
64 static void *regs_irn_data_init(ir_phase *ph, ir_node *irn, void *data)
66 coloring_t *coloring = (coloring_t *) ph;
67 return (void *) arch_get_irn_register(coloring->arch_env, irn);
70 coloring_t *coloring_init(coloring_t *c, ir_graph *irg, const arch_env_t *aenv)
72 phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init, NULL);
78 static void get_irn_color(ir_node *irn, void *c)
80 coloring_t *coloring = c;
81 phase_get_or_set_irn_data(&coloring->ph, irn);
84 static void restore_irn_color(ir_node *irn, void *c)
86 coloring_t *coloring = c;
87 const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn);
89 arch_set_irn_register(coloring->arch_env, irn, reg);
92 void coloring_save(coloring_t *c)
94 irg_walk_graph(c->irg, NULL, get_irn_color, c);
97 void coloring_restore(coloring_t *c)
99 irg_walk_graph(c->irg, NULL, restore_irn_color, c);
102 void (be_ifg_free)(be_ifg_t *ifg)
104 ifg->impl->free(ifg);
107 int (be_ifg_connected)(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
109 return ifg->impl->connected(ifg, a, b);
112 ir_node *(be_ifg_neighbours_begin)(const be_ifg_t *ifg, void *iter, const ir_node *irn)
114 return ifg->impl->neighbours_begin(ifg, iter, irn);
117 ir_node *(be_ifg_neighbours_next)(const be_ifg_t *ifg, void *iter)
119 return ifg->impl->neighbours_next(ifg, iter);
122 void (be_ifg_neighbours_break)(const be_ifg_t *ifg, void *iter)
124 ifg->impl->neighbours_break(ifg, iter);
127 ir_node *(be_ifg_nodes_begin)(const be_ifg_t *ifg, void *iter)
129 return ifg->impl->nodes_begin(ifg, iter);
132 ir_node *(be_ifg_nodes_next)(const be_ifg_t *ifg, void *iter)
134 return ifg->impl->nodes_next(ifg, iter);
137 void (be_ifg_nodes_break)(const be_ifg_t *ifg, void *iter)
139 ifg->impl->nodes_break(ifg, iter);
142 int (be_ifg_cliques_begin)(const be_ifg_t *ifg, void *iter, ir_node **buf)
144 return ifg->impl->cliques_begin(ifg, iter, buf);
147 int (be_ifg_cliques_next)(const be_ifg_t *ifg, void *iter)
149 return ifg->impl->cliques_next(ifg, iter);
152 void (be_ifg_cliques_break)(const be_ifg_t *ifg, void *iter)
154 ifg->impl->cliques_break(ifg, iter);
157 int (be_ifg_degree)(const be_ifg_t *ifg, const ir_node *irn)
159 return ifg->impl->degree(ifg, irn);
163 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
165 int degree = be_ifg_degree(ifg, irn);
166 void *iter = be_ifg_neighbours_iter_alloca(ifg);
168 ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0]));
174 be_ifg_foreach_neighbour(ifg, iter, irn, curr)
175 neighbours[i++] = curr;
177 for(i = 0; i < degree; ++i) {
178 for(j = 0; j < i; ++j)
179 if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
190 void be_ifg_check(const be_ifg_t *ifg)
192 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
193 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
197 int neighbours_count = 0;
200 /* count all nodes */
201 ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
202 be_ifg_foreach_node(ifg,iter1,n)
205 degree = be_ifg_degree(ifg, n);
206 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
209 ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
211 /* Check, if all neighbours are indeed connected to the node. */
212 be_ifg_foreach_node(ifg, iter1, n)
214 ir_printf("\n%+F; ", n);
215 be_ifg_foreach_neighbour(ifg, iter2, n, m)
217 ir_printf("%+F; ", m);
219 if(!be_ifg_connected(ifg, n, m))
220 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
223 ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
226 int be_ifg_check_get_node_count(const be_ifg_t *ifg)
228 void *iter = be_ifg_nodes_iter_alloca(ifg);
232 be_ifg_foreach_node(ifg, iter, n)
240 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
242 const ir_node *node_a = *(ir_node **)a;
243 const ir_node *node_b = *(ir_node **)b;
245 long nr_a = get_irn_node_nr(node_a);
246 long nr_b = get_irn_node_nr(node_b);
248 return QSORT_CMP(nr_a, nr_b);
251 void be_ifg_check_sorted(const be_ifg_t *ifg)
253 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
254 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
257 const int node_count = be_ifg_check_get_node_count(ifg);
260 ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
262 be_ifg_foreach_node(ifg, iter1, n)
264 if(!node_is_in_irgs_storage(ifg->env->irg, n))
266 ir_printf("+%F is in ifg but not in the current irg!", n);
267 assert (node_is_in_irgs_storage(ifg->env->irg, n));
274 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
276 for (i = 0; i < node_count; i++)
278 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
283 degree = be_ifg_degree(ifg, all_nodes[i]);
285 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
291 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
293 ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
295 for(k = 0; k < j; k++)
297 ir_printf("%+F, ", neighbours[k]);
309 void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
311 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
312 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
315 const int node_count = be_ifg_check_get_node_count(ifg);
318 ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
320 be_ifg_foreach_node(ifg, iter1, n)
322 if(!node_is_in_irgs_storage(ifg->env->irg, n))
324 ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
325 assert (node_is_in_irgs_storage(ifg->env->irg, n));
332 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
334 for (i = 0; i < node_count; i++)
336 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
341 degree = be_ifg_degree(ifg, all_nodes[i]);
343 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
349 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
351 ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
353 for(k = 0; k < j; k++)
355 ir_fprintf (f,"%+F, ", neighbours[k]);
367 void be_ifg_check_performance(be_chordal_env_t *chordal_env)
369 int tests = BE_CH_PERFORMANCETEST_COUNT;
377 be_ifg_t *old_if = chordal_env->ifg;
379 lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg");
380 unsigned long elapsed_usec = 0;
382 if (get_irg_estimated_node_cnt(chordal_env->irg) >= BE_CH_PERFORMANCETEST_MIN_NODES)
384 coloring_init(&coloring, chordal_env->irg, chordal_env->birg->main_env->arch_env);
385 coloring_save(&coloring);
387 lc_timer_reset(timer);
389 for (i = 0; i<tests; i++) /* performance test with std */
392 used_memory = lc_get_heap_used_bytes();
394 rt = lc_timer_enter_high_priority();
395 lc_timer_start(timer);
397 chordal_env->ifg = be_ifg_std_new(chordal_env);
399 lc_timer_stop(timer);
400 rt = lc_timer_leave_high_priority();
402 used_memory = lc_get_heap_used_bytes() - used_memory;
404 coloring_restore(&coloring);
407 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
408 co_build_ou_structure(co);
409 co_build_graph_structure(co);
411 rt = lc_timer_enter_high_priority();
412 lc_timer_start(timer);
414 co_solve_heuristic_new(co);
416 lc_timer_stop(timer);
417 rt = lc_timer_leave_high_priority();
419 co_free_graph_structure(co);
420 co_free_ou_structure(co);
422 be_ifg_free(chordal_env->ifg);
426 elapsed_usec = lc_timer_elapsed_usec(timer);
427 /* calculating average */
428 elapsed_usec = elapsed_usec / tests;
430 ir_printf("\nstd:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
435 for (i = 0; i<tests; i++) /* performance test with clique */
437 used_memory = lc_get_heap_used_bytes();
439 rt = lc_timer_enter_high_priority();
440 lc_timer_start(timer);
442 chordal_env->ifg = be_ifg_clique_new(chordal_env);
444 lc_timer_stop(timer);
445 rt = lc_timer_leave_high_priority();
447 used_memory = lc_get_heap_used_bytes() - used_memory;
449 coloring_restore(&coloring);
452 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
453 co_build_ou_structure(co);
454 co_build_graph_structure(co);
456 rt = lc_timer_enter_high_priority();
457 lc_timer_start(timer);
459 co_solve_heuristic_new(co);
461 lc_timer_stop(timer);
462 rt = lc_timer_leave_high_priority();
464 co_free_graph_structure(co);
465 co_free_ou_structure(co);
467 be_ifg_free(chordal_env->ifg);
471 elapsed_usec = lc_timer_elapsed_usec(timer);
472 /* calculating average */
473 elapsed_usec = elapsed_usec / tests;
475 ir_printf("\nclique:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
480 for (i = 0; i<tests; i++) /* performance test with list */
482 used_memory = lc_get_heap_used_bytes();
484 rt = lc_timer_enter_high_priority();
485 lc_timer_start(timer);
487 chordal_env->ifg = be_ifg_list_new(chordal_env);
489 lc_timer_stop(timer);
490 rt = lc_timer_leave_high_priority();
492 used_memory = lc_get_heap_used_bytes() - used_memory;
494 coloring_restore(&coloring);
497 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
498 co_build_ou_structure(co);
499 co_build_graph_structure(co);
501 rt = lc_timer_enter_high_priority();
502 lc_timer_start(timer);
504 co_solve_heuristic_new(co);
506 lc_timer_stop(timer);
507 rt = lc_timer_leave_high_priority();
509 co_free_graph_structure(co);
510 co_free_ou_structure(co);
512 be_ifg_free(chordal_env->ifg);
516 elapsed_usec = lc_timer_elapsed_usec(timer);
517 /* calculating average */
518 elapsed_usec = elapsed_usec / tests;
520 ir_printf("\nlist:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
525 for (i = 0; i<tests; i++) /* performance test with pointer */
527 used_memory = lc_get_heap_used_bytes();
529 rt = lc_timer_enter_high_priority();
530 lc_timer_start(timer);
532 chordal_env->ifg = be_ifg_pointer_new(chordal_env);
534 lc_timer_stop(timer);
535 rt = lc_timer_leave_high_priority();
537 used_memory = lc_get_heap_used_bytes() - used_memory;
539 coloring_restore(&coloring);
542 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
543 co_build_ou_structure(co);
544 co_build_graph_structure(co);
546 rt = lc_timer_enter_high_priority();
547 lc_timer_start(timer);
549 co_solve_heuristic_new(co);
551 lc_timer_stop(timer);
552 rt = lc_timer_leave_high_priority();
554 co_free_graph_structure(co);
555 co_free_ou_structure(co);
557 be_ifg_free(chordal_env->ifg);
561 elapsed_usec = lc_timer_elapsed_usec(timer);
562 /* calculating average */
563 elapsed_usec = elapsed_usec / tests;
565 ir_printf("\npointer:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
572 chordal_env->ifg = old_if;
575 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
577 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
578 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
579 bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
583 fprintf(file, "graph G {\n\tgraph [");
585 cb->graph_attr(file, self);
586 fprintf(file, "];\n");
589 cb->at_begin(file, self);
591 be_ifg_foreach_node(ifg, nodes_it, n) {
592 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
593 int idx = get_irn_idx(n);
594 bitset_set(nodes, idx);
595 fprintf(file, "\tnode [");
597 cb->node_attr(file, self, n);
598 fprintf(file, "]; n%d;\n", idx);
602 /* Check, if all neighbours are indeed connected to the node. */
603 be_ifg_foreach_node(ifg, nodes_it, n) {
604 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
605 int n_idx = get_irn_idx(n);
606 int m_idx = get_irn_idx(m);
608 if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
609 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
611 cb->edge_attr(file, self, n, m);
612 fprintf(file, "];\n");
618 cb->at_end(file, self);
620 fprintf(file, "}\n");
624 static void int_comp_rec(be_irg_t *birg, be_ifg_t *ifg, ir_node *n, bitset_t *seen)
626 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
629 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
630 if(!bitset_contains_irn(seen, m) && !arch_irn_is(birg->main_env->arch_env, m, ignore)) {
631 bitset_add_irn(seen, m);
632 int_comp_rec(birg, ifg, m, seen);
638 static int int_component_stat(be_irg_t *birg, be_ifg_t *ifg)
641 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
642 bitset_t *seen = bitset_irg_malloc(birg->irg);
646 be_ifg_foreach_node(ifg, nodes_it, n) {
647 if (! bitset_contains_irn(seen, n) && ! arch_irn_is(birg->main_env->arch_env, n, ignore)) {
649 bitset_add_irn(seen, n);
650 int_comp_rec(birg, ifg, n, seen);
658 void be_ifg_stat(be_irg_t *birg, be_ifg_t *ifg, be_ifg_stat_t *stat)
660 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
661 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
662 bitset_t *nodes = bitset_irg_malloc(birg->irg);
665 memset(stat, 0, sizeof(stat[0]));
667 be_ifg_foreach_node(ifg, nodes_it, n) {
669 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
670 bitset_add_irn(nodes, n);
671 stat->n_edges += !bitset_contains_irn(nodes, m);
675 stat->n_comps = int_component_stat(birg, ifg);
688 static int ifg_flavor = BE_IFG_STD;
690 static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
691 { "std", BE_IFG_STD },
692 { "fast", BE_IFG_FAST },
693 { "clique", BE_IFG_CLIQUE },
694 { "pointer", BE_IFG_POINTER },
695 { "list", BE_IFG_LIST },
696 { "check", BE_IFG_CHECK },
700 static lc_opt_enum_int_var_t ifg_flavor_var = {
701 &ifg_flavor, ifg_flavor_items
704 static const lc_opt_table_entry_t be_ifg_options[] = {
705 LC_OPT_ENT_ENUM_PTR ("ifg", "interference graph flavour", &ifg_flavor_var),
709 void be_init_ifg(void)
711 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
712 lc_opt_entry_t *ifg_grp = lc_opt_get_grp(be_grp, "ifg");
714 lc_opt_add_table(ifg_grp, be_ifg_options);
717 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ifg);
719 static FILE *be_ifg_open(const be_chordal_env_t *env, const char *prefix)
724 ir_snprintf(buf, sizeof(buf), "%s%F_%s.log", prefix, env->irg, env->cls->name);
725 result = fopen(buf, "wt");
727 panic("Couldn't open '%s' for writing.", buf);
733 static void check_ifg_implementations(const be_chordal_env_t *chordal_env)
738 f = be_ifg_open(chordal_env, "std");
739 ifg = be_ifg_std_new(chordal_env);
740 be_ifg_check_sorted_to_file(ifg, f);
744 f = be_ifg_open(chordal_env, "list");
745 ifg = be_ifg_list_new(chordal_env);
746 be_ifg_check_sorted_to_file(ifg, f);
750 f = be_ifg_open(chordal_env, "clique");
751 ifg = be_ifg_clique_new(chordal_env);
752 be_ifg_check_sorted_to_file(ifg, f);
756 f = be_ifg_open(chordal_env, "pointer");
757 ifg = be_ifg_pointer_new(chordal_env);
758 be_ifg_check_sorted_to_file(ifg, f);
763 be_ifg_t *be_create_ifg(const be_chordal_env_t *chordal_env)
765 be_ifg_t *ifg = NULL;
767 switch (ifg_flavor) {
770 fprintf(stderr, "no valid ifg flavour selected. falling back to std\n");
773 ifg = be_ifg_std_new(chordal_env);
776 ifg = be_ifg_clique_new(chordal_env);
779 ifg = be_ifg_pointer_new(chordal_env);
782 ifg = be_ifg_list_new(chordal_env);
785 check_ifg_implementations(chordal_env);
786 /* Build the interference graph. */
787 ifg = be_ifg_std_new(chordal_env);