X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur2.c;h=8a0e5a89c0a26a25e47067dd3734bb29e4797a40;hb=bba15007f36643c7c6f9281c8be00d8511bfb4f9;hp=3a6487aafeb84f831790db44484276b251072f52;hpb=18814151f8c0ea17b2a7bf84c82ee3c2e66d6a6b;p=libfirm diff --git a/ir/be/becopyheur2.c b/ir/be/becopyheur2.c index 3a6487aaf..8a0e5a89c 100644 --- a/ir/be/becopyheur2.c +++ b/ir/be/becopyheur2.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -95,13 +95,11 @@ static const lc_opt_table_entry_t options[] = { #define INFEASIBLE(cost) ((cost) == INT_MAX) -static be_ifg_dump_dot_cb_t ifg_dot_cb; - typedef unsigned col_t; -typedef struct _co2_irn_t co2_irn_t; -typedef struct _co2_cloud_t co2_cloud_t; -typedef struct _co2_cloud_irn_t co2_cloud_irn_t; +typedef struct co2_irn_t co2_irn_t; +typedef struct co2_cloud_t co2_cloud_t; +typedef struct co2_cloud_irn_t co2_cloud_irn_t; typedef struct { col_t col; @@ -111,7 +109,7 @@ typedef struct { typedef struct { ir_phase ph; copy_opt_t *co; - bitset_t *ignore_regs; + bitset_t *allocatable_regs; co2_irn_t *touched; int visited; int n_regs; @@ -119,13 +117,13 @@ typedef struct { DEBUG_ONLY(firm_dbg_module_t *dbg;) } co2_t; -struct _co2_irn_t { +struct co2_irn_t { const ir_node *irn; affinity_node_t *aff; co2_irn_t *touched_next; col_t tmp_col; col_t orig_col; - int last_color_change; + int last_color_change; bitset_t *adm_cache; unsigned fixed : 1; unsigned tmp_fixed : 1; @@ -133,8 +131,8 @@ struct _co2_irn_t { struct list_head changed_list; }; -struct _co2_cloud_irn_t { - struct _co2_irn_t inh; +struct co2_cloud_irn_t { + struct co2_irn_t inh; co2_cloud_t *cloud; int visited; int index; @@ -151,7 +149,7 @@ struct _co2_cloud_irn_t { struct list_head mst_list; }; -struct _co2_cloud_t { +struct co2_cloud_t { co2_t *env; struct obstack obst; int costs; @@ -161,7 +159,7 @@ struct _co2_cloud_t { int n_memb; int n_constr; int max_degree; - int ticks; + int ticks; double freedom; co2_cloud_irn_t *master; co2_cloud_irn_t *mst_root; @@ -180,12 +178,12 @@ typedef struct { #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn)) #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn)) -static void *co2_irn_init(ir_phase *ph, const ir_node *irn, void *data) +static void *co2_irn_init(ir_phase *ph, const ir_node *irn) { co2_t *env = (co2_t *) ph; affinity_node_t *a = get_affinity_info(env->co, irn); size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t); - co2_irn_t *ci = data ? data : phase_alloc(ph, size); + co2_irn_t *ci = (co2_irn_t*)phase_alloc(ph, size); memset(ci, 0, size); INIT_LIST_HEAD(&ci->changed_list); @@ -208,8 +206,8 @@ static void *co2_irn_init(ir_phase *ph, const ir_node *irn, void *data) static int cmp_clouds_gt(const void *a, const void *b) { - const co2_cloud_t * const *p = a; - const co2_cloud_t * const *q = b; + const co2_cloud_t * const *p = (const co2_cloud_t*const*)a; + const co2_cloud_t * const *q = (const co2_cloud_t*const*)b; double c = CLOUD_WEIGHT(*p); double d = CLOUD_WEIGHT(*q); return QSORT_CMP(d, c); @@ -221,8 +219,8 @@ static int cmp_clouds_gt(const void *a, const void *b) */ static int col_cost_pair_lt(const void *a, const void *b) { - const col_cost_pair_t *p = a; - const col_cost_pair_t *q = b; + const col_cost_pair_t *p = (const col_cost_pair_t*)a; + const col_cost_pair_t *q = (const col_cost_pair_t*)b; int c = p->costs; int d = q->costs; return QSORT_CMP(c, d); @@ -230,8 +228,8 @@ static int col_cost_pair_lt(const void *a, const void *b) static int cmp_edges(const void *a, const void *b) { - const edge_t *p = a; - const edge_t *q = b; + const edge_t *p = (const edge_t*)a; + const edge_t *q = (const edge_t*)b; return QSORT_CMP(q->costs, p->costs); } @@ -264,8 +262,7 @@ static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci) } ci->is_constrained = 1; } else { - bitset_copy(ci->adm_cache, env->ignore_regs); - bitset_flip_all(ci->adm_cache); + bitset_copy(ci->adm_cache, env->allocatable_regs); } } @@ -327,7 +324,7 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co bitset_t *forb = bitset_alloca(n_regs); affinity_node_t *a = ci->aff; - unsigned elm; + size_t elm; const ir_node *pos; neighbours_iter_t it; int i; @@ -612,7 +609,7 @@ static void node_color_badness(co2_cloud_irn_t *ci, int *badness) be_ifg_t *ifg = env->co->cenv->ifg; bitset_t *bs = bitset_alloca(n_regs); - unsigned elm; + size_t elm; const ir_node *irn; neighbours_iter_t it; @@ -627,7 +624,7 @@ static void node_color_badness(co2_cloud_irn_t *ci, int *badness) admissible_colors(env, ni, bs); if (bitset_popcount(bs) == 1) { - unsigned c = bitset_next_set(bs, 0); + size_t c = bitset_next_set(bs, 0); badness[c] += ci->costs; } @@ -813,7 +810,7 @@ static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, i static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a) { - co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0])); + co2_cloud_t *cloud = (co2_cloud_t*)phase_alloc(&env->ph, sizeof(cloud[0])); co2_cloud_irn_t *ci; int i; @@ -829,7 +826,7 @@ static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a) cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom; /* Also allocate space for the node sequence and compute that sequence. */ - cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0])); + cloud->seq = (co2_cloud_irn_t**)phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0])); i = 0; list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) { @@ -855,7 +852,7 @@ static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth) // assert(ok && "Color changing may not fail while committing the coloring"); materialize_coloring(&changed); - for (i = 0; i < ci->mst_n_childs; ++i) { + for (i = 0; i < ci->mst_n_childs; ++i) { apply_coloring(ci->mst_childs[i], front[i], depth + 1); } } @@ -898,7 +895,7 @@ static void process_cloud(co2_cloud_t *cloud) } } } - edges = obstack_finish(&cloud->obst); + edges = (edge_t*)obstack_finish(&cloud->obst); qsort(edges, n_edges, sizeof(edges[0]), cmp_edges); /* Compute the maximum spanning tree using Kruskal/Union-Find */ @@ -928,7 +925,7 @@ static void process_cloud(co2_cloud_t *cloud) cloud->mst_root = cloud->master; q = new_pdeq1(cloud->master); while (!pdeq_empty(q)) { - co2_cloud_irn_t *ci = pdeq_getl(q); + co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q); int ofs = ci->index * cloud->n_memb; int end = ofs + cloud->n_memb; int i; @@ -954,7 +951,7 @@ static void process_cloud(co2_cloud_t *cloud) } obstack_ptr_grow(&cloud->obst, NULL); - ci->mst_childs = obstack_finish(&cloud->obst); + ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst); } del_pdeq(q); free(mst_edges); @@ -1015,61 +1012,6 @@ static int cloud_costs(co2_cloud_t *cloud) return costs / 2; } -static void process(co2_t *env) -{ - affinity_node_t *a; - co2_cloud_t *pos; - co2_cloud_t **clouds; - int n_clouds; - int i; - int init_costs = 0; - int all_costs = 0; - int final_costs = 0; - - n_clouds = 0; - co_gs_foreach_aff_node(env->co, a) { - co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn); - - if (!ci->cloud) { - new_cloud(env, a); - n_clouds++; - } - } - - i = 0; - clouds = XMALLOCN(co2_cloud_t*, n_clouds); - list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list) - clouds[i++] = pos; - qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt); - - for (i = 0; i < n_clouds; ++i) { - init_costs += cloud_costs(clouds[i]); - - /* Process the cloud. */ - process_cloud(clouds[i]); - - all_costs += clouds[i]->costs; - final_costs += cloud_costs(clouds[i]); - - /* Dump the IFG if the user demanded it. */ - if (dump_flags & DUMP_CLOUD) { - char buf[256]; - FILE *f; - - ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i); - f = fopen(buf, "wt"); - if (f != NULL) { - be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env); - fclose(f); - } - } - } - - DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs)); - - xfree(clouds); -} - static void writeback_colors(co2_t *env) { co2_irn_t *irn; @@ -1160,14 +1102,14 @@ static int ifg_is_dump_node(void *self, ir_node *irn) static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn) { - co2_t *env = self; + co2_t *env = (co2_t*)self; co2_irn_t *ci = get_co2_irn(env, irn); int peri = 1; char buf[128] = ""; if (ci->aff) { - co2_cloud_irn_t *cci = (void *) ci; + co2_cloud_irn_t *cci = (co2_cloud_irn_t*) ci; if (cci->cloud && cci->cloud->mst_root == cci) peri = 2; @@ -1181,7 +1123,7 @@ static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn) static void ifg_dump_at_end(FILE *file, void *self) { - co2_t *env = self; + co2_t *env = (co2_t*)self; affinity_node_t *a; co_gs_foreach_aff_node(env->co, a) { @@ -1211,7 +1153,6 @@ static void ifg_dump_at_end(FILE *file, void *self) } } - static be_ifg_dump_dot_cb_t ifg_dot_cb = { ifg_is_dump_node, ifg_dump_graph_attr, @@ -1221,19 +1162,74 @@ static be_ifg_dump_dot_cb_t ifg_dot_cb = { ifg_dump_at_end }; +static void process(co2_t *env) +{ + affinity_node_t *a; + co2_cloud_t *pos; + co2_cloud_t **clouds; + int n_clouds; + int i; + int init_costs = 0; + int all_costs = 0; + int final_costs = 0; + + n_clouds = 0; + co_gs_foreach_aff_node(env->co, a) { + co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn); + + if (!ci->cloud) { + new_cloud(env, a); + n_clouds++; + } + } + + i = 0; + clouds = XMALLOCN(co2_cloud_t*, n_clouds); + list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list) + clouds[i++] = pos; + qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt); + + for (i = 0; i < n_clouds; ++i) { + init_costs += cloud_costs(clouds[i]); + + /* Process the cloud. */ + process_cloud(clouds[i]); + + all_costs += clouds[i]->costs; + final_costs += cloud_costs(clouds[i]); + + /* Dump the IFG if the user demanded it. */ + if (dump_flags & DUMP_CLOUD) { + char buf[256]; + FILE *f; + + ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i); + f = fopen(buf, "wt"); + if (f != NULL) { + be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env); + fclose(f); + } + } + } + + DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs)); + + xfree(clouds); +} + int co_solve_heuristic_new(copy_opt_t *co) { char buf[256]; co2_t env; FILE *f; - phase_init(&env.ph, co->cenv->birg->irg, co2_irn_init); + phase_init(&env.ph, co->cenv->irg, co2_irn_init); env.touched = NULL; env.visited = 0; env.co = co; env.n_regs = co->cls->n_regs; - env.ignore_regs = bitset_alloca(co->cls->n_regs); - be_put_ignore_regs(co->cenv->irg, co->cls, env.ignore_regs); + env.allocatable_regs = bitset_alloca(co->cls->n_regs); + be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs); FIRM_DBG_REGISTER(env.dbg, "firm.be.co2"); INIT_LIST_HEAD(&env.cloud_head);