X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fbe%2Fbecopyheur4.c;h=bac5a04bc20360b544d886ab32fc7563b56e9a4a;hb=0e4318adc38a54110c1b1f7f1d5edc0ee2c78170;hp=ba38dfe2787e3584fca835d2e5bcbe7985189459;hpb=5a5b0a8806277f92f5950cfedd8a231f4d00a306;p=libfirm diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c index ba38dfe27..bac5a04bc 100644 --- a/ir/be/becopyheur4.c +++ b/ir/be/becopyheur4.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. * @@ -82,9 +82,9 @@ typedef float real_t; static unsigned last_chunk_id = 0; static int recolor_limit = 7; -static real_t dislike_influence = REAL(0.1); +static double dislike_influence = REAL(0.1); -typedef struct _col_cost_t { +typedef struct col_cost_t { int col; real_t cost; } col_cost_t; @@ -92,7 +92,7 @@ typedef struct _col_cost_t { /** * An affinity chunk. */ -typedef struct _aff_chunk_t { +typedef struct aff_chunk_t { const ir_node **n; /**< An ARR_F containing all nodes of the chunk. */ const ir_node **interfere; /**< An ARR_F containing all inference. */ int weight; /**< Weight of this chunk */ @@ -107,17 +107,17 @@ typedef struct _aff_chunk_t { /** * An affinity edge. */ -typedef struct _aff_edge_t { +typedef struct aff_edge_t { const ir_node *src; /**< Source node. */ const ir_node *tgt; /**< Target node. */ int weight; /**< The weight of this edge. */ } aff_edge_t; /* main coalescing environment */ -typedef struct _co_mst_env_t { +typedef struct co_mst_env_t { int n_regs; /**< number of regs in class */ int k; /**< number of non-ignore registers in class */ - bitset_t *ignore_regs; /**< set containing all global ignore registers */ + bitset_t *allocatable_regs; /**< set containing all global ignore registers */ ir_phase ph; /**< phase object holding data for nodes */ pqueue_t *chunks; /**< priority queue for chunks */ list_head chunklist; /**< list holding all chunks */ @@ -128,7 +128,7 @@ typedef struct _co_mst_env_t { } co_mst_env_t; /* stores coalescing related information for a node */ -typedef struct _co_mst_irn_t { +typedef struct co_mst_irn_t { const ir_node *irn; /**< the irn this information belongs to */ aff_chunk_t *chunk; /**< the chunk this irn belongs to */ bitset_t *adm_colors; /**< set of admissible colors for this irn */ @@ -143,7 +143,10 @@ typedef struct _co_mst_irn_t { real_t constr_factor; } co_mst_irn_t; -#define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn))) +static co_mst_irn_t *get_co_mst_irn(co_mst_env_t *env, const ir_node *node) +{ + return (co_mst_irn_t*)phase_get_or_set_irn_data(&env->ph, node); +} typedef int decide_func_t(const co_mst_irn_t *node, int col); @@ -171,14 +174,14 @@ static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) */ static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node) { - unsigned idx; + size_t idx; (void) env; if (bitset_popcount(node->adm_colors) < 1) fprintf(stderr, "no admissible colors?!?"); else { bitset_foreach(node->adm_colors, idx) { - fprintf(stderr, " %d", idx); + ir_fprintf(stderr, " %zu", idx); } } } @@ -229,8 +232,8 @@ static int decider_always_yes(const co_mst_irn_t *node, int col) /** compares two affinity edges by its weight */ static int cmp_aff_edge(const void *a, const void *b) { - const aff_edge_t *e1 = a; - const aff_edge_t *e2 = b; + const aff_edge_t *e1 = (const aff_edge_t*)a; + const aff_edge_t *e2 = (const aff_edge_t*)b; if (e2->weight == e1->weight) { if (e2->src->node_idx == e1->src->node_idx) @@ -245,20 +248,21 @@ static int cmp_aff_edge(const void *a, const void *b) /** compares to color-cost pairs */ static __attribute__((unused)) int cmp_col_cost_lt(const void *a, const void *b) { - const col_cost_t *c1 = a; - const col_cost_t *c2 = b; + const col_cost_t *c1 = (const col_cost_t*)a; + const col_cost_t *c2 = (const col_cost_t*)b; real_t diff = c1->cost - c2->cost; return (diff > 0) - (diff < 0); } static int cmp_col_cost_gt(const void *a, const void *b) { - const col_cost_t *c1 = a; - const col_cost_t *c2 = b; - if (c2->cost == c1->cost) + const col_cost_t *c1 = (const col_cost_t*)a; + const col_cost_t *c2 = (const col_cost_t*)b; + real_t diff = c2->cost - c1->cost; + + if (diff == 0.0) return QSORT_CMP(c1->col, c2->col); - real_t diff = c2->cost - c1->cost; return (diff > 0) - (diff < 0); } @@ -373,8 +377,8 @@ static inline void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) */ static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn) { - co_mst_irn_t *res = phase_alloc(ph, sizeof(res[0])); - co_mst_env_t *env = ph->priv; + co_mst_irn_t *res = (co_mst_irn_t*)phase_alloc(ph, sizeof(res[0])); + co_mst_env_t *env = (co_mst_env_t*)ph->priv; const arch_register_req_t *req; neighbours_iter_t nodes_it; @@ -397,14 +401,14 @@ static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn) res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs); /* Exclude colors not assignable to the irn */ - req = arch_get_register_req_out(irn); + req = arch_get_irn_register_req(irn); if (arch_register_req_is(req, limited)) rbitset_copy_to_bitset(req->limited, res->adm_colors); else bitset_set_all(res->adm_colors); /* exclude global ignore registers as well */ - bitset_andnot(res->adm_colors, env->ignore_regs); + bitset_and(res->adm_colors, env->allocatable_regs); /* compute the constraint factor */ res->constr_factor = (real_t) (1 + env->n_regs - bitset_popcount(res->adm_colors)) / env->n_regs; @@ -420,7 +424,7 @@ static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn) ++len; } } - res->int_neighs = obstack_finish(phase_obst(ph)); + res->int_neighs = (ir_node**)obstack_finish(phase_obst(ph)); res->n_neighs = len; return res; } @@ -567,7 +571,7 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) node->chunk = c; if (node->constr_factor > REAL(0.0)) { - unsigned col; + size_t col; bitset_foreach (node->adm_colors, col) c->color_affinity[col].cost += node->constr_factor; } @@ -732,13 +736,13 @@ static void build_affinity_chunks(co_mst_env_t *env) static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk) { - pqueue_t *grow = new_pqueue(); - const ir_node *max_node = NULL; - int max_weight = 0; - int i; + pqueue_t *grow = new_pqueue(); + ir_node const *max_node = NULL; + int max_weight = 0; + size_t i; - for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) { - const ir_node *irn = chunk->n[i]; + for (i = ARR_LEN(chunk->n); i != 0;) { + const ir_node *irn = chunk->n[--i]; affinity_node_t *an = get_affinity_info(env->co, irn); int w = 0; neighb_t *neigh; @@ -760,14 +764,14 @@ static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chu if (max_node) { bitset_t *visited = bitset_irg_malloc(env->co->irg); - for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i) - bitset_add_irn(visited, chunk->n[i]); + for (i = ARR_LEN(chunk->n); i != 0;) + bitset_add_irn(visited, chunk->n[--i]); pqueue_put(grow, (void *) max_node, max_weight); bitset_remv_irn(visited, max_node); i = 0; while (!pqueue_empty(grow)) { - ir_node *irn = pqueue_pop_front(grow); + ir_node *irn = (ir_node*)pqueue_pop_front(grow); affinity_node_t *an = get_affinity_info(env->co, irn); neighb_t *neigh; @@ -813,7 +817,7 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v /* as long as there are nodes in the queue */ while (! waitq_empty(nodes)) { - co_mst_irn_t *n = waitq_get(nodes); + co_mst_irn_t *n = (co_mst_irn_t*)waitq_get(nodes); affinity_node_t *an = get_affinity_info(env->co, n->irn); /* check all affinity neighbors */ @@ -1114,7 +1118,7 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost } /** - * Tries to bring node @p node and all it's neighbours to color @p tgt_col. + * Tries to bring node @p node and all its neighbours to color @p tgt_col. * @return 1 if color @p col could be applied, 0 otherwise */ static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed) @@ -1131,7 +1135,7 @@ static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, /* Node has not yet a fixed color and target color is admissible - -> try to recolor node and it's affinity neighbours + -> try to recolor node and its affinity neighbours */ if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) { col_cost_t *costs = env->single_cols[tgt_col]; @@ -1179,7 +1183,11 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) waitq *best_starts = NULL; col_cost_t *order = ALLOCANZ(col_cost_t, env->n_regs); bitset_t *visited; - int idx, len, i, nidx, pos; + int i; + size_t idx; + size_t len; + size_t nidx; + size_t pos; struct list_head changed; DB((dbg, LEVEL_2, "fragmentizing chunk #%u", c->id)); @@ -1233,7 +1241,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) int n_succeeded; /* skip ignore colors */ - if (bitset_is_set(env->ignore_regs, col)) + if (!bitset_is_set(env->allocatable_regs, col)) continue; DB((dbg, LEVEL_2, "\ttrying color %d\n", col)); @@ -1316,7 +1324,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) /* free all intermediate created chunks except best one */ while (! waitq_empty(tmp_chunks)) { - aff_chunk_t *tmp = waitq_get(tmp_chunks); + aff_chunk_t *tmp = (aff_chunk_t*)waitq_get(tmp_chunks); if (tmp != best_chunk) delete_aff_chunk(tmp); } @@ -1415,9 +1423,10 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) */ static int co_solve_heuristic_mst(copy_opt_t *co) { - unsigned n_regs = co->cls->n_regs; - bitset_t *ignore_regs = bitset_alloca(n_regs); - unsigned i, j, k; + unsigned n_regs = co->cls->n_regs; + bitset_t *allocatable_regs = bitset_alloca(n_regs); + unsigned i, j; + size_t k; ir_node *irn; co_mst_env_t mst_env; @@ -1429,21 +1438,21 @@ static int co_solve_heuristic_mst(copy_opt_t *co) phase_init(&mst_env.ph, co->irg, co_mst_irn_init); phase_set_private(&mst_env.ph, &mst_env); - k = be_put_ignore_regs(co->cenv->irg, co->cls, ignore_regs); - k = n_regs - k; + be_put_allocatable_regs(co->cenv->irg, co->cls, allocatable_regs); + k = bitset_popcount(allocatable_regs); - mst_env.n_regs = n_regs; - mst_env.k = k; - mst_env.chunks = new_pqueue(); - mst_env.co = co; - mst_env.ignore_regs = ignore_regs; - mst_env.ifg = co->cenv->ifg; + mst_env.n_regs = n_regs; + mst_env.k = k; + mst_env.chunks = new_pqueue(); + mst_env.co = co; + mst_env.allocatable_regs = allocatable_regs; + mst_env.ifg = co->cenv->ifg; INIT_LIST_HEAD(&mst_env.chunklist); - mst_env.chunk_visited = 0; - mst_env.single_cols = phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs); + mst_env.chunk_visited = 0; + mst_env.single_cols = (col_cost_t**)phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs); for (i = 0; i < n_regs; ++i) { - col_cost_t *vec = phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs); + col_cost_t *vec = (col_cost_t*)phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs); mst_env.single_cols[i] = vec; for (j = 0; j < n_regs; ++j) { @@ -1464,7 +1473,7 @@ static int co_solve_heuristic_mst(copy_opt_t *co) /* color chunks as long as there are some */ while (! pqueue_empty(mst_env.chunks)) { - aff_chunk_t *chunk = pqueue_pop_front(mst_env.chunks); + aff_chunk_t *chunk = (aff_chunk_t*)pqueue_pop_front(mst_env.chunks); color_aff_chunk(&mst_env, chunk); DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%u) done\n", chunk->id)); @@ -1506,7 +1515,7 @@ static const lc_opt_table_entry_t options[] = { LC_OPT_LAST }; -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4) void be_init_copyheur4(void) { lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");