2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Interface for interference graphs.
23 * @author Sebastian Hack
32 #include "lc_opts_enum.h"
42 #include "beifg_impl.h"
43 #include "irphase_t.h"
47 #include "becopystat.h"
48 #include "becopyopt.h"
52 /** Defines values for the ifg performance test */
53 #define BE_CH_PERFORMANCETEST_MIN_NODES (50)
54 #define BE_CH_PERFORMANCETEST_COUNT (500)
56 typedef struct _coloring_t coloring_t;
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(ir_phase *ph, const ir_node *irn, void *data)
83 return (void*)arch_get_irn_register(irn);
86 static coloring_t *coloring_init(coloring_t *c, ir_graph *irg)
88 phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init, NULL);
93 static void get_irn_color(ir_node *irn, void *c)
95 coloring_t *coloring = c;
96 phase_get_or_set_irn_data(&coloring->ph, irn);
99 static void restore_irn_color(ir_node *irn, void *c)
101 coloring_t *coloring = c;
102 const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn);
104 arch_set_irn_register(irn, reg);
107 static void coloring_save(coloring_t *c)
109 irg_walk_graph(c->irg, NULL, get_irn_color, c);
112 static void coloring_restore(coloring_t *c)
114 irg_walk_graph(c->irg, NULL, restore_irn_color, c);
117 void (be_ifg_free)(be_ifg_t *ifg)
119 ifg->impl->free(ifg);
122 int (be_ifg_connected)(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
124 return ifg->impl->connected(ifg, a, b);
127 ir_node *(be_ifg_neighbours_begin)(const be_ifg_t *ifg, void *iter, const ir_node *irn)
129 return ifg->impl->neighbours_begin(ifg, iter, irn);
132 ir_node *(be_ifg_neighbours_next)(const be_ifg_t *ifg, void *iter)
134 return ifg->impl->neighbours_next(ifg, iter);
137 void (be_ifg_neighbours_break)(const be_ifg_t *ifg, void *iter)
139 ifg->impl->neighbours_break(ifg, iter);
142 ir_node *(be_ifg_nodes_begin)(const be_ifg_t *ifg, void *iter)
144 return ifg->impl->nodes_begin(ifg, iter);
147 ir_node *(be_ifg_nodes_next)(const be_ifg_t *ifg, void *iter)
149 return ifg->impl->nodes_next(ifg, iter);
152 void (be_ifg_nodes_break)(const be_ifg_t *ifg, void *iter)
154 ifg->impl->nodes_break(ifg, iter);
157 int (be_ifg_cliques_begin)(const be_ifg_t *ifg, void *iter, ir_node **buf)
159 return ifg->impl->cliques_begin(ifg, iter, buf);
162 int (be_ifg_cliques_next)(const be_ifg_t *ifg, void *iter)
164 return ifg->impl->cliques_next(ifg, iter);
167 void (be_ifg_cliques_break)(const be_ifg_t *ifg, void *iter)
169 ifg->impl->cliques_break(ifg, iter);
172 int (be_ifg_degree)(const be_ifg_t *ifg, const ir_node *irn)
174 return ifg->impl->degree(ifg, irn);
178 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
180 int degree = be_ifg_degree(ifg, irn);
181 void *iter = be_ifg_neighbours_iter_alloca(ifg);
183 ir_node **neighbours = XMALLOCN(ir_node*, degree);
189 be_ifg_foreach_neighbour(ifg, iter, irn, curr)
190 neighbours[i++] = curr;
192 for (i = 0; i < degree; ++i) {
193 for (j = 0; j < i; ++j)
194 if (!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
205 void be_ifg_check(const be_ifg_t *ifg)
207 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
208 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
212 int neighbours_count = 0;
215 /* count all nodes */
216 ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
217 be_ifg_foreach_node(ifg,iter1,n)
220 degree = be_ifg_degree(ifg, n);
221 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
224 ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
226 /* Check, if all neighbours are indeed connected to the node. */
227 be_ifg_foreach_node(ifg, iter1, n)
229 ir_printf("\n%+F; ", n);
230 be_ifg_foreach_neighbour(ifg, iter2, n, m)
232 ir_printf("%+F; ", m);
234 if (!be_ifg_connected(ifg, n, m))
235 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
238 ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
241 int be_ifg_check_get_node_count(const be_ifg_t *ifg)
243 void *iter = be_ifg_nodes_iter_alloca(ifg);
247 be_ifg_foreach_node(ifg, iter, n)
255 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
257 const ir_node *node_a = *(ir_node **)a;
258 const ir_node *node_b = *(ir_node **)b;
260 long nr_a = get_irn_idx(node_a);
261 long nr_b = get_irn_idx(node_b);
263 return QSORT_CMP(nr_a, nr_b);
266 void be_ifg_check_sorted(const be_ifg_t *ifg)
268 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
269 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
272 const int node_count = be_ifg_check_get_node_count(ifg);
275 ir_node **all_nodes = XMALLOCN(ir_node*, node_count);
277 be_ifg_foreach_node(ifg, iter1, n)
279 if (!node_is_in_irgs_storage(ifg->env->irg, n))
281 ir_printf("+%F is in ifg but not in the current irg!", n);
282 assert (node_is_in_irgs_storage(ifg->env->irg, n));
289 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
291 for (i = 0; i < node_count; i++)
293 ir_node **neighbours = XMALLOCN(ir_node*, node_count);
298 degree = be_ifg_degree(ifg, all_nodes[i]);
300 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
306 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
308 ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
310 for (k = 0; k < j; k++)
312 ir_printf("%+F, ", neighbours[k]);
324 void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
326 void *iter1 = be_ifg_nodes_iter_alloca(ifg);
327 void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
330 const int node_count = be_ifg_check_get_node_count(ifg);
333 ir_node **all_nodes = XMALLOCN(ir_node*, node_count);
335 be_ifg_foreach_node(ifg, iter1, n)
337 if (!node_is_in_irgs_storage(ifg->env->irg, n))
339 ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
340 assert (node_is_in_irgs_storage(ifg->env->irg, n));
347 qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
349 for (i = 0; i < node_count; i++)
351 ir_node **neighbours = XMALLOCN(ir_node*, node_count);
356 degree = be_ifg_degree(ifg, all_nodes[i]);
358 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
364 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
366 ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
368 for (k = 0; k < j; k++)
370 ir_fprintf (f,"%+F, ", neighbours[k]);
382 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 ir_timer_t *timer = ir_timer_new();
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);
400 coloring_save(&coloring);
402 ir_timer_reset(timer);
404 for (i = 0; i<tests; i++) /* performance test with std */
407 used_memory = ir_get_heap_used_bytes();
409 rt = ir_timer_enter_high_priority();
410 ir_timer_start(timer);
412 chordal_env->ifg = be_ifg_std_new(chordal_env);
414 ir_timer_stop(timer);
415 rt = ir_timer_leave_high_priority();
417 used_memory = ir_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 = ir_timer_enter_high_priority();
427 ir_timer_start(timer);
429 co_solve_heuristic_new(co);
431 ir_timer_stop(timer);
432 rt = ir_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 = ir_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 = ir_get_heap_used_bytes();
454 rt = ir_timer_enter_high_priority();
455 ir_timer_start(timer);
457 chordal_env->ifg = be_ifg_clique_new(chordal_env);
459 ir_timer_stop(timer);
460 rt = ir_timer_leave_high_priority();
462 used_memory = ir_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 = ir_timer_enter_high_priority();
472 ir_timer_start(timer);
474 co_solve_heuristic_new(co);
476 ir_timer_stop(timer);
477 rt = ir_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 = ir_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 = ir_get_heap_used_bytes();
499 rt = ir_timer_enter_high_priority();
500 ir_timer_start(timer);
502 chordal_env->ifg = be_ifg_list_new(chordal_env);
504 ir_timer_stop(timer);
505 rt = ir_timer_leave_high_priority();
507 used_memory = ir_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 = ir_timer_enter_high_priority();
517 ir_timer_start(timer);
519 co_solve_heuristic_new(co);
521 ir_timer_stop(timer);
522 rt = ir_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 = ir_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 = ir_get_heap_used_bytes();
544 rt = ir_timer_enter_high_priority();
545 ir_timer_start(timer);
547 chordal_env->ifg = be_ifg_pointer_new(chordal_env);
549 ir_timer_stop(timer);
550 rt = ir_timer_leave_high_priority();
552 used_memory = ir_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 = ir_timer_enter_high_priority();
562 ir_timer_start(timer);
564 co_solve_heuristic_new(co);
566 ir_timer_stop(timer);
567 rt = ir_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 = ir_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;
589 ir_timer_free(timer);
592 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
594 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
595 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
596 bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
600 fprintf(file, "graph G {\n\tgraph [");
602 cb->graph_attr(file, self);
603 fprintf(file, "];\n");
606 cb->at_begin(file, self);
608 be_ifg_foreach_node(ifg, nodes_it, n) {
609 if (cb->is_dump_node && cb->is_dump_node(self, n)) {
610 int idx = get_irn_idx(n);
611 bitset_set(nodes, idx);
612 fprintf(file, "\tnode [");
614 cb->node_attr(file, self, n);
615 fprintf(file, "]; n%d;\n", idx);
619 /* Check, if all neighbours are indeed connected to the node. */
620 be_ifg_foreach_node(ifg, nodes_it, n) {
621 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
622 int n_idx = get_irn_idx(n);
623 int m_idx = get_irn_idx(m);
625 if (n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
626 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
628 cb->edge_attr(file, self, n, m);
629 fprintf(file, "];\n");
635 cb->at_end(file, self);
637 fprintf(file, "}\n");
641 static void int_comp_rec(be_ifg_t *ifg, ir_node *n, bitset_t *seen)
643 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
646 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
647 if (bitset_contains_irn(seen, m))
650 if (arch_get_register_req_out(m)->type & arch_register_req_type_ignore)
653 bitset_add_irn(seen, m);
654 int_comp_rec(ifg, m, seen);
659 static int int_component_stat(be_irg_t *birg, be_ifg_t *ifg)
662 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
663 bitset_t *seen = bitset_irg_malloc(birg->irg);
667 be_ifg_foreach_node(ifg, nodes_it, n) {
668 if (bitset_contains_irn(seen, n))
671 if (arch_get_register_req_out(n)->type & arch_register_req_type_ignore)
675 bitset_add_irn(seen, n);
676 int_comp_rec(ifg, n, seen);
683 void be_ifg_stat(be_irg_t *birg, be_ifg_t *ifg, be_ifg_stat_t *stat)
685 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
686 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
687 bitset_t *nodes = bitset_irg_malloc(birg->irg);
690 memset(stat, 0, sizeof(stat[0]));
692 be_ifg_foreach_node(ifg, nodes_it, n) {
694 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
695 bitset_add_irn(nodes, n);
696 stat->n_edges += !bitset_contains_irn(nodes, m);
700 stat->n_comps = int_component_stat(birg, ifg);
713 static int ifg_flavor = BE_IFG_STD;
715 static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
716 { "std", BE_IFG_STD },
717 { "fast", BE_IFG_FAST },
718 { "clique", BE_IFG_CLIQUE },
719 { "pointer", BE_IFG_POINTER },
720 { "list", BE_IFG_LIST },
721 { "check", BE_IFG_CHECK },
725 static lc_opt_enum_int_var_t ifg_flavor_var = {
726 &ifg_flavor, ifg_flavor_items
729 static const lc_opt_table_entry_t be_ifg_options[] = {
730 LC_OPT_ENT_ENUM_PTR ("ifg", "interference graph flavour", &ifg_flavor_var),
734 void be_init_ifg(void)
736 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
737 lc_opt_entry_t *ifg_grp = lc_opt_get_grp(be_grp, "ifg");
739 lc_opt_add_table(ifg_grp, be_ifg_options);
742 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ifg);
744 static FILE *be_ifg_open(const be_chordal_env_t *env, const char *prefix)
749 ir_snprintf(buf, sizeof(buf), "%s%F_%s.log", prefix, env->irg, env->cls->name);
750 result = fopen(buf, "wt");
751 if (result == NULL) {
752 panic("Couldn't open '%s' for writing.", buf);
758 static void check_ifg_implementations(const be_chordal_env_t *chordal_env)
763 f = be_ifg_open(chordal_env, "std");
764 ifg = be_ifg_std_new(chordal_env);
765 be_ifg_check_sorted_to_file(ifg, f);
769 f = be_ifg_open(chordal_env, "list");
770 ifg = be_ifg_list_new(chordal_env);
771 be_ifg_check_sorted_to_file(ifg, f);
775 f = be_ifg_open(chordal_env, "clique");
776 ifg = be_ifg_clique_new(chordal_env);
777 be_ifg_check_sorted_to_file(ifg, f);
781 f = be_ifg_open(chordal_env, "pointer");
782 ifg = be_ifg_pointer_new(chordal_env);
783 be_ifg_check_sorted_to_file(ifg, f);
788 be_ifg_t *be_create_ifg(const be_chordal_env_t *chordal_env)
790 be_ifg_t *ifg = NULL;
792 switch (ifg_flavor) {
795 fprintf(stderr, "no valid ifg flavour selected. falling back to std\n");
798 ifg = be_ifg_std_new(chordal_env);
801 ifg = be_ifg_clique_new(chordal_env);
804 ifg = be_ifg_pointer_new(chordal_env);
807 ifg = be_ifg_list_new(chordal_env);
810 check_ifg_implementations(chordal_env);
811 /* Build the interference graph. */
812 ifg = be_ifg_std_new(chordal_env);