X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur4.c;h=ad5ca80d0c43f429cfb6c041ab2f3cc0a055aca1;hb=5474a1c188c9d59eea2c915515980cd9cbab58d8;hp=f96cc26c2a1b7b3ba7ec63fd79c17fd06c5de7ed;hpb=15ad7ccd8dff64e1808e1d093d4a8d7cda5af33e;p=libfirm diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c index f96cc26c2..ad5ca80d0 100644 --- a/ir/be/becopyheur4.c +++ b/ir/be/becopyheur4.c @@ -22,7 +22,6 @@ * @brief Simple copy minimization heuristics. * @author Christian Wuerdig * @date 27.04.2007 - * @version $Id$ * * This is the C implementation of the mst algorithm * originally written in Java by Sebastian Hack. @@ -39,18 +38,17 @@ #include "irnode_t.h" #include "bitset.h" #include "raw_bitset.h" -#include "irphase_t.h" +#include "irnodemap.h" #include "pqueue.h" #include "xmalloc.h" #include "pdeq.h" #include "irprintf.h" -#include "irbitset.h" +#include "util.h" +#include "irtools.h" #include "error.h" #include "list.h" #include "statev.h" -#include "irbitset.h" - #include "bearch.h" #include "beifg.h" #include "be_t.h" @@ -82,7 +80,7 @@ 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 { int col; @@ -118,7 +116,8 @@ 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 */ - ir_phase ph; /**< phase object holding data for nodes */ + ir_nodemap map; /**< phase object holding data for nodes */ + struct obstack obst; pqueue_t *chunks; /**< priority queue for chunks */ list_head chunklist; /**< list holding all chunks */ be_ifg_t *ifg; /**< the interference graph */ @@ -143,9 +142,71 @@ typedef struct co_mst_irn_t { real_t constr_factor; } co_mst_irn_t; +/** + * In case there is no phase information for irn, initialize it. + */ +static co_mst_irn_t *co_mst_irn_init(co_mst_env_t *env, const ir_node *irn) +{ + co_mst_irn_t *res = OALLOC(&env->obst, co_mst_irn_t); + + const arch_register_req_t *req; + neighbours_iter_t nodes_it; + ir_node *neigh; + unsigned len; + + res->irn = irn; + res->chunk = NULL; + res->fixed = 0; + 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->init_col = res->col; + INIT_LIST_HEAD(&res->list); + + DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn)); + + /* set admissible registers */ + res->adm_colors = bitset_obstack_alloc(&env->obst, env->n_regs); + + /* Exclude colors not assignable to the 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_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; + + /* set the number of interfering affinity neighbours to -1, they are calculated later */ + res->int_aff_neigh = -1; + + /* build list of interfering neighbours */ + len = 0; + be_ifg_foreach_neighbour(env->ifg, &nodes_it, irn, neigh) { + if (!arch_irn_is_ignore(neigh)) { + obstack_ptr_grow(&env->obst, neigh); + ++len; + } + } + res->int_neighs = (ir_node**)obstack_finish(&env->obst); + res->n_neighs = len; + return res; +} + 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); + co_mst_irn_t *res = (co_mst_irn_t*)ir_nodemap_get(&env->map, node); + if (res == NULL) { + res = co_mst_irn_init(env, node); + ir_nodemap_insert(&env->map, node, res); + } + return res; } typedef int decide_func_t(const co_mst_irn_t *node, int col); @@ -372,63 +433,6 @@ static inline void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) } } -/** - * In case there is no phase information for irn, initialize it. - */ -static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn) -{ - 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; - ir_node *neigh; - unsigned len; - - res->irn = irn; - res->chunk = NULL; - res->fixed = 0; - 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->init_col = res->col; - INIT_LIST_HEAD(&res->list); - - DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn)); - - /* set admissible registers */ - 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); - 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_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; - - /* set the number of interfering affinity neighbours to -1, they are calculated later */ - res->int_aff_neigh = -1; - - /* build list of interfering neighbours */ - len = 0; - be_ifg_foreach_neighbour(env->ifg, &nodes_it, irn, neigh) { - if (!arch_irn_is_ignore(neigh)) { - obstack_ptr_grow(phase_obst(ph), neigh); - ++len; - } - } - res->int_neighs = (ir_node**)obstack_finish(phase_obst(ph)); - res->n_neighs = len; - return res; -} - /** * Check if affinity chunk @p chunk interferes with node @p irn. */ @@ -641,6 +645,7 @@ static void build_affinity_chunks(co_mst_env_t *env) ir_node *n; int i, len; aff_chunk_t *curr_chunk; + size_t pn; /* at first we create the affinity edge objects */ be_ifg_foreach_node(env->ifg, &nodes_it, n) { @@ -713,22 +718,24 @@ static void build_affinity_chunks(co_mst_env_t *env) pqueue_put(env->chunks, curr_chunk, curr_chunk->weight); } - foreach_phase_irn(&env->ph, n) { - co_mst_irn_t *mirn = get_co_mst_irn(env, n); + for (pn = 0; pn < ARR_LEN(env->map.data); ++pn) { + co_mst_irn_t *mirn = env->map.data[pn]; + if (mirn == NULL) + continue; + if (mirn->chunk != NULL) + continue; - if (mirn->chunk == NULL) { - /* no chunk is allocated so far, do it now */ - aff_chunk_t *curr_chunk = new_aff_chunk(env); - aff_chunk_add_node(curr_chunk, mirn); + /* no chunk is allocated so far, do it now */ + aff_chunk_t *curr_chunk = new_aff_chunk(env); + aff_chunk_add_node(curr_chunk, mirn); - aff_chunk_assure_weight(env, curr_chunk); + aff_chunk_assure_weight(env, curr_chunk); - DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id)); - DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk); - DBG((dbg, LEVEL_1, "\n")); + DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id)); + DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk); + DBG((dbg, LEVEL_1, "\n")); - pqueue_put(env->chunks, curr_chunk, curr_chunk->weight); - } + pqueue_put(env->chunks, curr_chunk, curr_chunk->weight); } DEL_ARR_F(edges); @@ -762,13 +769,13 @@ 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); + bitset_t *visited = bitset_malloc(get_irg_last_idx(env->co->irg)); for (i = ARR_LEN(chunk->n); i != 0;) - bitset_add_irn(visited, chunk->n[--i]); + bitset_set(visited, get_irn_idx(chunk->n[--i])); pqueue_put(grow, (void *) max_node, max_weight); - bitset_remv_irn(visited, max_node); + bitset_clear(visited, get_irn_idx(max_node)); i = 0; while (!pqueue_empty(grow)) { ir_node *irn = (ir_node*)pqueue_pop_front(grow); @@ -787,9 +794,9 @@ static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chu co_gs_foreach_neighb(an, neigh) { co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn); - if (bitset_contains_irn(visited, node->irn)) { + if (bitset_is_set(visited, get_irn_idx(node->irn))) { pqueue_put(grow, (void *) neigh->irn, neigh->costs); - bitset_remv_irn(visited, node->irn); + bitset_clear(visited, get_irn_idx(node->irn)); } } } @@ -867,7 +874,7 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v */ static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) { - bitset_t *visited = bitset_irg_malloc(env->co->irg); + bitset_t *visited = bitset_malloc(get_irg_last_idx(env->co->irg)); int idx, len; aff_chunk_t *best = NULL; @@ -1236,7 +1243,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) */ for (i = 0; i < env->k; ++i) { int col = order[i].col; - waitq *good_starts = new_waitq(); + waitq *good_starts; aff_chunk_t *local_best; int n_succeeded; @@ -1247,6 +1254,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) DB((dbg, LEVEL_2, "\ttrying color %d\n", col)); n_succeeded = 0; + good_starts = new_waitq(); /* try to bring all nodes of given chunk to the current color. */ for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { @@ -1285,8 +1293,10 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) } /* try next color when failed */ - if (n_succeeded == 0) + if (n_succeeded == 0) { + del_waitq(good_starts); continue; + } /* fragment the chunk according to the coloring */ local_best = fragment_chunk(env, col, c, tmp_chunks); @@ -1387,7 +1397,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) } /* fragment the remaining chunk */ - visited = bitset_irg_malloc(env->co->irg); + visited = bitset_malloc(get_irg_last_idx(env->co->irg)); for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) bitset_set(visited, get_irn_idx(best_chunk->n[idx])); @@ -1427,6 +1437,7 @@ static int co_solve_heuristic_mst(copy_opt_t *co) 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; @@ -1435,8 +1446,8 @@ static int co_solve_heuristic_mst(copy_opt_t *co) stat_ev_tim_push(); /* init phase */ - phase_init(&mst_env.ph, co->irg, co_mst_irn_init); - phase_set_private(&mst_env.ph, &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); @@ -1449,10 +1460,10 @@ static int co_solve_heuristic_mst(copy_opt_t *co) mst_env.ifg = co->cenv->ifg; INIT_LIST_HEAD(&mst_env.chunklist); mst_env.chunk_visited = 0; - mst_env.single_cols = (col_cost_t**)phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs); + mst_env.single_cols = OALLOCN(&mst_env.obst, col_cost_t*, n_regs); for (i = 0; i < n_regs; ++i) { - col_cost_t *vec = (col_cost_t*)phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs); + 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) { @@ -1481,16 +1492,15 @@ static int co_solve_heuristic_mst(copy_opt_t *co) } /* apply coloring */ - foreach_phase_irn(&mst_env.ph, irn) { - co_mst_irn_t *mirn; + for (pn = 0; pn < ARR_LEN(mst_env.map.data); ++pn) { + co_mst_irn_t *mirn = mst_env.map.data[pn]; const arch_register_t *reg; - + if (mirn == NULL) + continue; + irn = get_idx_irn(co->irg, pn); if (arch_irn_is_ignore(irn)) continue; - mirn = get_co_mst_irn(&mst_env, irn); - // assert(mirn->fixed && "Node should have fixed color"); - /* skip nodes where color hasn't changed */ if (mirn->init_col == mirn->col) continue; @@ -1502,7 +1512,8 @@ static int co_solve_heuristic_mst(copy_opt_t *co) /* free allocated memory */ del_pqueue(mst_env.chunks); - phase_deinit(&mst_env.ph); + obstack_free(&mst_env.obst, NULL); + ir_nodemap_destroy(&mst_env.map); stat_ev_tim_pop("heur4_total"); @@ -1515,7 +1526,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");