X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur4.c;h=dbe5acc87077f0ca241ae239f05d553e7bb8db3d;hb=6ee1fce95429dbf57fda4455ca5f2cf011ac8190;hp=ad5ca80d0c43f429cfb6c041ab2f3cc0a055aca1;hpb=c5ff6a4703ccf54f3f18371dcbe79bb4b91fe066;p=libfirm diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c index ad5ca80d0..dbe5acc87 100644 --- a/ir/be/becopyheur4.c +++ b/ir/be/becopyheur4.c @@ -1,20 +1,6 @@ /* - * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. - * * This file is part of libFirm. - * - * This file may be distributed and/or modified under the terms of the - * GNU General Public License version 2 as published by the Free Software - * Foundation and appearing in the file LICENSE.GPL included in the - * packaging of this file. - * - * Licensees holding valid libFirm Professional Edition licenses may use - * this file in accordance with the libFirm Commercial License. - * Agreement provided with the Software. - * - * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE - * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE. + * Copyright (C) 2012 University of Karlsruhe. */ /** @@ -47,7 +33,7 @@ #include "irtools.h" #include "error.h" #include "list.h" -#include "statev.h" +#include "statev_t.h" #include "bearch.h" #include "beifg.h" @@ -56,11 +42,6 @@ #include "bemodule.h" -#define COL_COST_INFEASIBLE DBL_MAX -#define AFF_NEIGHBOUR_FIX_BENEFIT 128.0 -#define NEIGHBOUR_CONSTR_COSTS 64.0 - - #ifdef DEBUG_libfirm #define DBG_AFF_CHUNK(env, level, chunk) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while (0) @@ -114,8 +95,7 @@ typedef struct aff_edge_t { /* main coalescing environment */ 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 *allocatable_regs; /**< set containing all global ignore registers */ + bitset_t const *allocatable_regs; /**< set containing all global ignore registers */ ir_nodemap map; /**< phase object holding data for nodes */ struct obstack obst; pqueue_t *chunks; /**< priority queue for chunks */ @@ -151,7 +131,6 @@ static co_mst_irn_t *co_mst_irn_init(co_mst_env_t *env, const ir_node *irn) const arch_register_req_t *req; neighbours_iter_t nodes_it; - ir_node *neigh; unsigned len; res->irn = irn; @@ -160,7 +139,7 @@ static co_mst_irn_t *co_mst_irn_init(co_mst_env_t *env, const ir_node *irn) res->tmp_col = -1; res->int_neighs = NULL; res->int_aff_neigh = 0; - res->col = arch_register_get_index(arch_get_irn_register(irn)); + res->col = arch_get_irn_register(irn)->index; res->init_col = res->col; INIT_LIST_HEAD(&res->list); @@ -173,13 +152,12 @@ static co_mst_irn_t *co_mst_irn_init(co_mst_env_t *env, const ir_node *irn) req = arch_get_irn_register_req(irn); if (arch_register_req_is(req, limited)) { rbitset_copy_to_bitset(req->limited, res->adm_colors); + /* exclude global ignore registers as well */ + bitset_and(res->adm_colors, env->allocatable_regs); } else { - bitset_set_all(res->adm_colors); + bitset_copy(res->adm_colors, env->allocatable_regs); } - /* exclude global ignore registers as well */ - 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; @@ -201,7 +179,7 @@ static co_mst_irn_t *co_mst_irn_init(co_mst_env_t *env, const ir_node *irn) static co_mst_irn_t *get_co_mst_irn(co_mst_env_t *env, const ir_node *node) { - co_mst_irn_t *res = (co_mst_irn_t*)ir_nodemap_get(&env->map, node); + co_mst_irn_t *res = ir_nodemap_get(co_mst_irn_t, &env->map, node); if (res == NULL) { res = co_mst_irn_init(env, node); ir_nodemap_insert(&env->map, node, res); @@ -235,7 +213,6 @@ 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) { - size_t idx; (void) env; if (bitset_popcount(node->adm_colors) < 1) @@ -312,7 +289,13 @@ static __attribute__((unused)) int cmp_col_cost_lt(const void *a, const void *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); + + if (diff < 0) + return 1; + if (diff > 0) + return -1; + + return QSORT_CMP(c1->col, c2->col); } static int cmp_col_cost_gt(const void *a, const void *b) @@ -321,10 +304,12 @@ static int cmp_col_cost_gt(const void *a, const void *b) 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); + if (diff > 0) + return 1; + if (diff < 0) + return -1; - return (diff > 0) - (diff < 0); + return QSORT_CMP(c1->col, c2->col); } /** @@ -575,13 +560,11 @@ 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)) { - size_t col; bitset_foreach (node->adm_colors, col) c->color_affinity[col].cost += node->constr_factor; } if (an != NULL) { - neighb_t *neigh; co_gs_foreach_neighb(an, neigh) { const ir_node *m = neigh->irn; @@ -607,7 +590,6 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) */ static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) { - const neighb_t *neigh; const ir_node *irn = an->irn; const co_mst_irn_t *node = get_co_mst_irn(env, irn); int res = 0; @@ -640,15 +622,10 @@ static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t */ static void build_affinity_chunks(co_mst_env_t *env) { - nodes_iter_t nodes_it; - aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0); - ir_node *n; - int i, len; - aff_chunk_t *curr_chunk; - size_t pn; + aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0); /* at first we create the affinity edge objects */ - be_ifg_foreach_node(env->ifg, &nodes_it, n) { + be_ifg_foreach_node(env->ifg, n) { int n_idx = get_irn_idx(n); co_mst_irn_t *n1; affinity_node_t *an; @@ -660,8 +637,6 @@ static void build_affinity_chunks(co_mst_env_t *env) an = get_affinity_info(env->co, n); if (an != NULL) { - neighb_t *neigh; - if (n1->int_aff_neigh < 0) n1->int_aff_neigh = count_interfering_aff_neighs(env, an); @@ -699,9 +674,9 @@ static void build_affinity_chunks(co_mst_env_t *env) } /* now: sort edges and build the affinity chunks */ - len = ARR_LEN(edges); + size_t const len = ARR_LEN(edges); qsort(edges, len, sizeof(edges[0]), cmp_aff_edge); - for (i = 0; i < len; ++i) { + for (size_t i = 0; i < len; ++i) { DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight)); (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt); @@ -718,8 +693,8 @@ static void build_affinity_chunks(co_mst_env_t *env) pqueue_put(env->chunks, curr_chunk, curr_chunk->weight); } - for (pn = 0; pn < ARR_LEN(env->map.data); ++pn) { - co_mst_irn_t *mirn = env->map.data[pn]; + for (size_t pn = 0; pn < ARR_LEN(env->map.data); ++pn) { + co_mst_irn_t *mirn = (co_mst_irn_t*)env->map.data[pn]; if (mirn == NULL) continue; if (mirn->chunk != NULL) @@ -752,7 +727,6 @@ static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chu const ir_node *irn = chunk->n[--i]; affinity_node_t *an = get_affinity_info(env->co, irn); int w = 0; - neighb_t *neigh; if (arch_irn_is_ignore(irn)) continue; @@ -780,7 +754,6 @@ static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chu while (!pqueue_empty(grow)) { ir_node *irn = (ir_node*)pqueue_pop_front(grow); affinity_node_t *an = get_affinity_info(env->co, irn); - neighb_t *neigh; if (arch_irn_is_ignore(irn)) continue; @@ -829,7 +802,6 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v /* check all affinity neighbors */ if (an != NULL) { - neighb_t *neigh; co_gs_foreach_neighb(an, neigh) { const ir_node *m = neigh->irn; int m_idx = get_irn_idx(m); @@ -925,7 +897,6 @@ static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, w */ static inline void reject_coloring(struct list_head *nodes) { - co_mst_irn_t *n, *temp; DB((dbg, LEVEL_4, "\treject coloring for")); list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) { DB((dbg, LEVEL_4, " %+F", n->irn)); @@ -938,7 +909,6 @@ static inline void reject_coloring(struct list_head *nodes) static inline void materialize_coloring(struct list_head *nodes) { - co_mst_irn_t *n, *temp; list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) { assert(n->tmp_col >= 0); n->col = n->tmp_col; @@ -1241,7 +1211,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) * TODO Sebastian: Perhaps we should at all nodes and figure out * a suitable color using costs as done above (determine_color_costs). */ - for (i = 0; i < env->k; ++i) { + for (i = 0; i < env->n_regs; ++i) { int col = order[i].col; waitq *good_starts; aff_chunk_t *local_best; @@ -1433,40 +1403,31 @@ 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 *allocatable_regs = bitset_alloca(n_regs); - unsigned i, j; - size_t k; - size_t pn; - ir_node *irn; - co_mst_env_t mst_env; - last_chunk_id = 0; stat_ev_tim_push(); /* init phase */ + co_mst_env_t mst_env; ir_nodemap_init(&mst_env.map, co->irg); obstack_init(&mst_env.obst); - be_put_allocatable_regs(co->cenv->irg, co->cls, allocatable_regs); - k = bitset_popcount(allocatable_regs); + unsigned const n_regs = co->cls->n_regs; 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.allocatable_regs = co->cenv->allocatable_regs; mst_env.ifg = co->cenv->ifg; INIT_LIST_HEAD(&mst_env.chunklist); mst_env.chunk_visited = 0; mst_env.single_cols = OALLOCN(&mst_env.obst, col_cost_t*, n_regs); - for (i = 0; i < n_regs; ++i) { + for (unsigned i = 0; i < n_regs; ++i) { col_cost_t *vec = OALLOCN(&mst_env.obst, col_cost_t, n_regs); mst_env.single_cols[i] = vec; - for (j = 0; j < n_regs; ++j) { + for (unsigned j = 0; j < n_regs; ++j) { vec[j].col = j; vec[j].cost = REAL(0.0); } @@ -1492,12 +1453,12 @@ static int co_solve_heuristic_mst(copy_opt_t *co) } /* apply coloring */ - for (pn = 0; pn < ARR_LEN(mst_env.map.data); ++pn) { - co_mst_irn_t *mirn = mst_env.map.data[pn]; + for (size_t pn = 0; pn < ARR_LEN(mst_env.map.data); ++pn) { + co_mst_irn_t *mirn = (co_mst_irn_t*)mst_env.map.data[pn]; const arch_register_t *reg; if (mirn == NULL) continue; - irn = get_idx_irn(co->irg, pn); + ir_node *const irn = get_idx_irn(co->irg, pn); if (arch_irn_is_ignore(irn)) continue;