X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg.c;h=e42cc6ca69803adf0e2101c2e0181a8a248bfa04;hb=80a6158fdd766f42ee6c508a773bc114ff1b61f3;hp=895de1277f092a15b1d315807f0482abfc7d6fbb;hpb=ef20e413d7caa50ff62d2e8c536934116433d891;p=libfirm diff --git a/ir/be/beifg.c b/ir/be/beifg.c index 895de1277..e42cc6ca6 100644 --- a/ir/be/beifg.c +++ b/ir/be/beifg.c @@ -1,101 +1,707 @@ /** - * Common use interference graph. - * Originally written by Sebastian Hack. Refactored into a seperate - * source file and header by Kimon Hoffmann. + * @file beifg.c + * @date 18.11.2005 * @author Sebastian Hack - * @date 27.06.2005 + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL */ #ifdef HAVE_CONFIG_H #include "config.h" #endif +#include + #ifdef HAVE_MALLOC_H #include #endif + +#ifdef __linux__ +#include +#endif /* __linux__ */ + #ifdef HAVE_ALLOCA_H #include #endif -#include "debug.h" +#ifdef WITH_LIBCORE +#include +#include +#include +#endif /* WITH_LIBCORE */ + +#include "bitset.h" +#include "irgwalk.h" +#include "irnode_t.h" +#include "irprintf.h" +#include "irtools.h" +#include "irbitset.h" #include "beifg_t.h" +#include "beifg_impl.h" +#include "irphase.h" +#include "irphase_t.h" +#include "bechordal.h" + +#include "becopystat.h" +#include "becopyopt.h" +#include "beirg_t.h" + +/** Defines values for the ifg performance test */ +#define BE_CH_PERFORMANCETEST_MIN_NODES (50) +#define BE_CH_PERFORMANCETEST_COUNT (500) + +typedef struct _coloring_t coloring_t; + +struct _coloring_t { + phase_t ph; + const arch_env_t *arch_env; + ir_graph *irg; +}; + +size_t (be_ifg_nodes_iter_size)(const void *self) +{ + const be_ifg_t *ifg = self; + return ifg->impl->nodes_iter_size; +} + +size_t (be_ifg_neighbours_iter_size)(const void *self) +{ + const be_ifg_t *ifg = self; + return ifg->impl->neighbours_iter_size; +} + +size_t (be_ifg_cliques_iter_size)(const void *self) +{ + const be_ifg_t *ifg = self; + return ifg->impl->cliques_iter_size; +} + +static void *regs_irn_data_init(phase_t *ph, ir_node *irn, void *data) +{ + coloring_t *coloring = (coloring_t *) ph; + return (void *) arch_get_irn_register(coloring->arch_env, irn); +} + +coloring_t *coloring_init(coloring_t *c, ir_graph *irg, const arch_env_t *aenv) +{ + phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init); + c->arch_env = aenv; + c->irg = irg; + return c; +} + +static void get_irn_color(ir_node *irn, void *c) +{ + coloring_t *coloring = c; + phase_get_or_set_irn_data(&coloring->ph, irn); +} + +static void restore_irn_color(ir_node *irn, void *c) +{ + coloring_t *coloring = c; + const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn); + if(reg) + arch_set_irn_register(coloring->arch_env, irn, reg); +} + +void coloring_save(coloring_t *c) +{ + irg_walk_graph(c->irg, NULL, get_irn_color, c); +} + +void coloring_restore(coloring_t *c) +{ + irg_walk_graph(c->irg, NULL, restore_irn_color, c); +} + +void (be_ifg_free)(void *self) +{ + be_ifg_t *ifg = self; + ifg->impl->free(self); +} + +int (be_ifg_connected)(const void *self, const ir_node *a, const ir_node *b) +{ + const be_ifg_t *ifg = self; + return ifg->impl->connected(self, a, b); +} + +ir_node *(be_ifg_neighbours_begin)(const void *self, void *iter, const ir_node *irn) +{ + const be_ifg_t *ifg = self; + return ifg->impl->neighbours_begin(self, iter, irn); +} + +ir_node *(be_ifg_neighbours_next)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + return ifg->impl->neighbours_next(self, iter); +} + +void (be_ifg_neighbours_break)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + ifg->impl->neighbours_break(self, iter); +} + +ir_node *(be_ifg_nodes_begin)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + return ifg->impl->nodes_begin(self, iter); +} + +ir_node *(be_ifg_nodes_next)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + return ifg->impl->nodes_next(self, iter); +} + +void (be_ifg_nodes_break)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + ifg->impl->nodes_break(self, iter); +} + +int (be_ifg_cliques_begin)(const void *self, void *iter, ir_node **buf) +{ + const be_ifg_t *ifg = self; + return ifg->impl->cliques_begin(self, iter, buf); +} + +int (be_ifg_cliques_next)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + return ifg->impl->cliques_next(self, iter); +} + +void (be_ifg_cliques_break)(const void *self, void *iter) +{ + const be_ifg_t *ifg = self; + ifg->impl->cliques_break(self, iter); +} + +int (be_ifg_degree)(const void *self, const ir_node *irn) +{ + const be_ifg_t *ifg = self; + return ifg->impl->degree(self, irn); +} + + +int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn) +{ + int degree = be_ifg_degree(ifg, irn); + void *iter = be_ifg_neighbours_iter_alloca(ifg); + + ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0])); + + ir_node *curr; + int i, j; + + i = 0; + be_ifg_foreach_neighbour(ifg, iter, irn, curr) + neighbours[i++] = curr; + + for(i = 0; i < degree; ++i) { + for(j = 0; j < i; ++j) + if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) { + free(neighbours); + return 0; + } + } + + + free(neighbours); + return 1; +} + +void be_ifg_check(const be_ifg_t *ifg) +{ + void *iter1 = be_ifg_nodes_iter_alloca(ifg); + void *iter2 = be_ifg_neighbours_iter_alloca(ifg); + + ir_node *n, *m; + int node_count = 0; + int neighbours_count = 0; + int degree = 0; + + /* count all nodes */ + ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph); + be_ifg_foreach_node(ifg,iter1,n) + { + node_count++; + degree = be_ifg_degree(ifg, n); + ir_printf("%d. %+F with degree: %d\n", node_count, n, degree); + } + + ir_printf("\n\nNumber of nodes: %d\n\n", node_count); + + /* Check, if all neighbours are indeed connected to the node. */ + be_ifg_foreach_node(ifg, iter1, n) + { + ir_printf("\n%+F; ", n); + be_ifg_foreach_neighbour(ifg, iter2, n, m) + { + ir_printf("%+F; ", m); + neighbours_count++; + if(!be_ifg_connected(ifg, n, m)) + ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m); + } + } + ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count); +} + +int be_ifg_check_get_node_count(const be_ifg_t *ifg) +{ + void *iter = be_ifg_nodes_iter_alloca(ifg); + int node_count = 0; + ir_node *n; + + be_ifg_foreach_node(ifg, iter, n) + { + node_count++; + } -#define IF_EDGE_HASH(e) ((e)->sourceNode) -#define IF_NODE_HASH(n) ((n)->nodeNumber) -#define IF_NODE_NEIGHBOUR_SLOTS 8 + return node_count; +} + +static int be_ifg_check_cmp_nodes(const void *a, const void *b) +{ + const ir_node *node_a = *(ir_node **)a; + const ir_node *node_b = *(ir_node **)b; -static int if_edge_cmp(const void* p1, const void* p2, size_t size) { - const be_if_edge_t* e1 = p1; - const be_if_edge_t* e2 = p2; + long nr_a = get_irn_node_nr(node_a); + long nr_b = get_irn_node_nr(node_b); - return !((e1->sourceNode == e2->sourceNode) && (e1->targetNode == e2->targetNode)); + return QSORT_CMP(nr_a, nr_b); } -static int if_node_cmp(const void* p1, const void* p2, size_t size) { - const be_if_node_t* n1 = p1; - const be_if_node_t* n2 = p2; +void be_ifg_check_sorted(const be_ifg_t *ifg) +{ + void *iter1 = be_ifg_nodes_iter_alloca(ifg); + void *iter2 = be_ifg_neighbours_iter_alloca(ifg); + + ir_node *n, *m; + const int node_count = be_ifg_check_get_node_count(ifg); + int i = 0; + + ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0])); + + be_ifg_foreach_node(ifg, iter1, n) + { + if(!node_is_in_irgs_storage(ifg->env->irg, n)) + { + ir_printf("+%F is in ifg but not in the current irg!", n); + assert (node_is_in_irgs_storage(ifg->env->irg, n)); + } + + all_nodes[i] = n; + i++; + } + + qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes); + + for (i = 0; i < node_count; i++) + { + ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0])); + int j = 0; + int k = 0; + int degree = 0; + + degree = be_ifg_degree(ifg, all_nodes[i]); + + be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m) + { + neighbours[j] = m; + j++; + } + + qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes); + + ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree); + + for(k = 0; k < j; k++) + { + ir_printf("%+F, ", neighbours[k]); + } + + ir_printf("\n"); + + free(neighbours); + } + + free(all_nodes); - return (n1->nodeNumber != n2->nodeNumber); } -static INLINE be_if_edge_t *edge_init(be_if_edge_t* edge, int source, int target) { - /* Bring the smaller entry to src. */ - if (source > target) { - edge->sourceNode = target; - edge->targetNode = source; - } else { - edge->sourceNode = source; - edge->targetNode = target; +void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f) +{ + void *iter1 = be_ifg_nodes_iter_alloca(ifg); + void *iter2 = be_ifg_neighbours_iter_alloca(ifg); + + ir_node *n, *m; + const int node_count = be_ifg_check_get_node_count(ifg); + int i = 0; + + ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0])); + + be_ifg_foreach_node(ifg, iter1, n) + { + if(!node_is_in_irgs_storage(ifg->env->irg, n)) + { + ir_fprintf (f,"+%F is in ifg but not in the current irg!",n); + assert (node_is_in_irgs_storage(ifg->env->irg, n)); + } + + all_nodes[i] = n; + i++; + } + + qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes); + + for (i = 0; i < node_count; i++) + { + ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0])); + int j = 0; + int k = 0; + int degree = 0; + + degree = be_ifg_degree(ifg, all_nodes[i]); + + be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m) + { + neighbours[j] = m; + j++; + } + + qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes); + + ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree); + + for(k = 0; k < j; k++) + { + ir_fprintf (f,"%+F, ", neighbours[k]); + } + + ir_fprintf (f,"\n"); + + free(neighbours); } - return edge; + + free(all_nodes); + } -be_if_graph_t* be_ifg_new(int slots) { - be_if_graph_t* graph = malloc(sizeof(*graph)); - graph->edges = new_set(if_edge_cmp, slots); - graph->nodes = new_set(if_node_cmp, slots); - return graph; +void be_ifg_check_performance(be_chordal_env_t *chordal_env) +{ +#ifdef WITH_LIBCORE + int tests = BE_CH_PERFORMANCETEST_COUNT; + coloring_t coloring; + + int used_memory; + + int i = 0; + int rt; + copy_opt_t *co; + be_ifg_t *old_if = chordal_env->ifg; + + lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg"); + unsigned long elapsed_usec = 0; + + if (get_irg_estimated_node_cnt(chordal_env->irg) >= BE_CH_PERFORMANCETEST_MIN_NODES) + { + coloring_init(&coloring, chordal_env->irg, chordal_env->birg->main_env->arch_env); + coloring_save(&coloring); + + lc_timer_reset(timer); + + for (i = 0; iifg = be_ifg_std_new(chordal_env); + + lc_timer_stop(timer); + rt = lc_timer_leave_high_priority(); + + used_memory = lc_get_heap_used_bytes() - used_memory; + + coloring_restore(&coloring); + + co = NULL; + co = new_copy_opt(chordal_env, co_get_costs_loop_depth); + co_build_ou_structure(co); + co_build_graph_structure(co); + + rt = lc_timer_enter_high_priority(); + lc_timer_start(timer); + + co_solve_heuristic_new(co); + + lc_timer_stop(timer); + rt = lc_timer_leave_high_priority(); + + co_free_graph_structure(co); + co_free_ou_structure(co); + free_copy_opt(co); + be_ifg_free(chordal_env->ifg); + + } + + elapsed_usec = lc_timer_elapsed_usec(timer); + /* calculating average */ + elapsed_usec = elapsed_usec / tests; + + ir_printf("\nstd:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec); + + used_memory=0; + elapsed_usec=0; + + for (i = 0; iifg = be_ifg_clique_new(chordal_env); + + lc_timer_stop(timer); + rt = lc_timer_leave_high_priority(); + + used_memory = lc_get_heap_used_bytes() - used_memory; + + coloring_restore(&coloring); + + co = NULL; + co = new_copy_opt(chordal_env, co_get_costs_loop_depth); + co_build_ou_structure(co); + co_build_graph_structure(co); + + rt = lc_timer_enter_high_priority(); + lc_timer_start(timer); + + co_solve_heuristic_new(co); + + lc_timer_stop(timer); + rt = lc_timer_leave_high_priority(); + + co_free_graph_structure(co); + co_free_ou_structure(co); + free_copy_opt(co); + be_ifg_free(chordal_env->ifg); + + } + + elapsed_usec = lc_timer_elapsed_usec(timer); + /* calculating average */ + elapsed_usec = elapsed_usec / tests; + + ir_printf("\nclique:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec); + + used_memory=0; + elapsed_usec=0; + + for (i = 0; iifg = be_ifg_list_new(chordal_env); + + lc_timer_stop(timer); + rt = lc_timer_leave_high_priority(); + + used_memory = lc_get_heap_used_bytes() - used_memory; + + coloring_restore(&coloring); + + co = NULL; + co = new_copy_opt(chordal_env, co_get_costs_loop_depth); + co_build_ou_structure(co); + co_build_graph_structure(co); + + rt = lc_timer_enter_high_priority(); + lc_timer_start(timer); + + co_solve_heuristic_new(co); + + lc_timer_stop(timer); + rt = lc_timer_leave_high_priority(); + + co_free_graph_structure(co); + co_free_ou_structure(co); + free_copy_opt(co); + be_ifg_free(chordal_env->ifg); + + } + + elapsed_usec = lc_timer_elapsed_usec(timer); + /* calculating average */ + elapsed_usec = elapsed_usec / tests; + + ir_printf("\nlist:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec); + + used_memory=0; + elapsed_usec=0; + + for (i = 0; iifg = be_ifg_pointer_new(chordal_env); + + lc_timer_stop(timer); + rt = lc_timer_leave_high_priority(); + + used_memory = lc_get_heap_used_bytes() - used_memory; + + coloring_restore(&coloring); + + co = NULL; + co = new_copy_opt(chordal_env, co_get_costs_loop_depth); + co_build_ou_structure(co); + co_build_graph_structure(co); + + rt = lc_timer_enter_high_priority(); + lc_timer_start(timer); + + co_solve_heuristic_new(co); + + lc_timer_stop(timer); + rt = lc_timer_leave_high_priority(); + + co_free_graph_structure(co); + co_free_ou_structure(co); + free_copy_opt(co); + be_ifg_free(chordal_env->ifg); + + } + + elapsed_usec = lc_timer_elapsed_usec(timer); + /* calculating average */ + elapsed_usec = elapsed_usec / tests; + + ir_printf("\npointer:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec); + + i=0; + used_memory=0; + elapsed_usec=0; + } + + chordal_env->ifg = old_if; +#endif /* WITH_LIBCORE */ } -void be_ifg_free(be_if_graph_t* graph) { - be_if_node_t* ifn; - for (ifn = set_first(graph->nodes); ifn; ifn = set_next(graph->nodes)) { - free(ifn->neighbourNodes); - ifn->neighbourNodes = 0; +void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self) +{ + void *nodes_it = be_ifg_nodes_iter_alloca(ifg); + void *neigh_it = be_ifg_neighbours_iter_alloca(ifg); + bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg)); + + ir_node *n, *m; + + fprintf(file, "graph G {\n\tgraph ["); + if(cb->graph_attr) + cb->graph_attr(file, self); + fprintf(file, "];\n"); + + if(cb->at_begin) + cb->at_begin(file, self); + + be_ifg_foreach_node(ifg, nodes_it, n) { + if(cb->is_dump_node && cb->is_dump_node(self, n)) { + int idx = get_irn_idx(n); + bitset_set(nodes, idx); + fprintf(file, "\tnode ["); + if(cb->node_attr) + cb->node_attr(file, self, n); + fprintf(file, "]; n%d;\n", idx); + } + } + + /* Check, if all neighbours are indeed connected to the node. */ + be_ifg_foreach_node(ifg, nodes_it, n) { + be_ifg_foreach_neighbour(ifg, neigh_it, n, m) { + int n_idx = get_irn_idx(n); + int m_idx = get_irn_idx(m); + + if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) { + fprintf(file, "\tn%d -- n%d [", n_idx, m_idx); + if(cb->edge_attr) + cb->edge_attr(file, self, n, m); + fprintf(file, "];\n"); + } + } } - free(graph->nodes); - graph->nodes = 0; - free(graph->edges); - graph->edges = 0; - free(graph); + + if(cb->at_end) + cb->at_end(file, self); + + fprintf(file, "}\n"); + bitset_free(nodes); } -void be_ifg_add_interference(be_if_graph_t* graph, int source, int target) { - /* insert edge */ - be_if_edge_t edge; - edge_init(&edge, source, target); - set_insert(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)); +static void int_comp_rec(const be_chordal_env_t *cenv, ir_node *n, bitset_t *seen) +{ + void *neigh_it = be_ifg_neighbours_iter_alloca(cenv->ifg); + ir_node *m; - /* insert nodes */ - be_if_node_t node; - node.nodeNumber = source; - node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS); - be_if_node_t* sourceNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node)); - node.nodeNumber = target; - node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS); - be_if_node_t* targetNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node)); + be_ifg_foreach_neighbour(cenv->ifg, neigh_it, n, m) { + if(!bitset_contains_irn(seen, m) && !arch_irn_is(cenv->birg->main_env->arch_env, m, ignore)) { + bitset_add_irn(seen, m); + int_comp_rec(cenv, m, seen); + } + } - /* insert neighbors into nodes */ - pset_insert_ptr(sourceNode->neighbourNodes, targetNode); - pset_insert_ptr(targetNode->neighbourNodes, sourceNode); } -static INLINE int are_connected(const be_if_graph_t* graph, int source, int target) { - be_if_edge_t edge; - edge_init(&edge, source, target); - return set_find(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL; +static int int_component_stat(const be_chordal_env_t *cenv) +{ + int n_comp = 0; + void *nodes_it = be_ifg_nodes_iter_alloca(cenv->ifg); + bitset_t *seen = bitset_irg_malloc(cenv->irg); + + ir_node *n; + + be_ifg_foreach_node(cenv->ifg, nodes_it, n) { + if(!bitset_contains_irn(seen, n) && !arch_irn_is(cenv->birg->main_env->arch_env, n, ignore)) { + ++n_comp; + bitset_add_irn(seen, n); + int_comp_rec(cenv, n, seen); + } + } + + free(seen); + return n_comp; } -int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2) { - return are_connected(graph, n1->nodeNumber, n2->nodeNumber); +void be_ifg_stat(const be_chordal_env_t *cenv, be_ifg_stat_t *stat) +{ + void *nodes_it = be_ifg_nodes_iter_alloca(cenv->ifg); + void *neigh_it = be_ifg_neighbours_iter_alloca(cenv->ifg); + bitset_t *nodes = bitset_irg_malloc(cenv->irg); + + ir_node *n, *m; + + memset(stat, 0, sizeof(stat[0])); + be_ifg_foreach_node(cenv->ifg, nodes_it, n) { + stat->n_nodes += 1; + be_ifg_foreach_neighbour(cenv->ifg, neigh_it, n, m) { + bitset_add_irn(nodes, n); + stat->n_edges += !bitset_contains_irn(nodes, m); + } + } + + stat->n_comps = int_component_stat(cenv); + bitset_free(nodes); }