X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg.c;h=e42cc6ca69803adf0e2101c2e0181a8a248bfa04;hb=80a6158fdd766f42ee6c508a773bc114ff1b61f3;hp=25f7caf2c54afe9706825775b8599969293430b1;hpb=2621ba4dee69537e8ab2017574f13f87f4d248bd;p=libfirm diff --git a/ir/be/beifg.c b/ir/be/beifg.c index 25f7caf2c..e42cc6ca6 100644 --- a/ir/be/beifg.c +++ b/ir/be/beifg.c @@ -6,17 +6,20 @@ * Copyright (C) 2005 Universitaet Karlsruhe * Released under the GPL */ - -#include - #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 @@ -33,6 +36,7 @@ #include "irnode_t.h" #include "irprintf.h" #include "irtools.h" +#include "irbitset.h" #include "beifg_t.h" #include "beifg_impl.h" #include "irphase.h" @@ -41,10 +45,11 @@ #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 (10) +#define BE_CH_PERFORMANCETEST_COUNT (500) typedef struct _coloring_t coloring_t; @@ -265,26 +270,31 @@ 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; - int nr_a = node_a->node_nr; - int nr_b = node_b->node_nr; + long nr_a = get_irn_node_nr(node_a); + long nr_b = get_irn_node_nr(node_b); return QSORT_CMP(nr_a, nr_b); } -void be_ifg_check_sorted(const be_ifg_t *ifg, FILE *f) +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 neighbours_count = 0; 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++; } @@ -308,14 +318,72 @@ void be_ifg_check_sorted(const be_ifg_t *ifg, FILE *f) 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); + ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree); for(k = 0; k < j; k++) { - ir_fprintf(f, "%+F, ", neighbours[k]); + ir_printf("%+F, ", neighbours[k]); } - ir_fprintf(f, "\n"); + ir_printf("\n"); + + free(neighbours); + } + + free(all_nodes); + +} + +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); } @@ -326,13 +394,11 @@ void be_ifg_check_sorted(const be_ifg_t *ifg, FILE *f) void be_ifg_check_performance(be_chordal_env_t *chordal_env) { +#ifdef WITH_LIBCORE int tests = BE_CH_PERFORMANCETEST_COUNT; coloring_t coloring; -#ifdef linux - struct mallinfo minfo; - int used_memory = 0; -#endif /* linux */ + int used_memory; int i = 0; int rt; @@ -342,9 +408,8 @@ void be_ifg_check_performance(be_chordal_env_t *chordal_env) lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg"); unsigned long elapsed_usec = 0; - if ((int) get_irg_estimated_node_cnt >= BE_CH_PERFORMANCETEST_MIN_NODES) + 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); @@ -352,10 +417,8 @@ void be_ifg_check_performance(be_chordal_env_t *chordal_env) for (i = 0; iifg = old_if; +#endif /* WITH_LIBCORE */ } void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self) @@ -634,3 +650,58 @@ void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump fprintf(file, "}\n"); bitset_free(nodes); } + +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; + + 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); + } + } + +} + +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; +} + +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); +}