X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur4.c;h=feb2b79eba2461a8d4ce45b19a7a1fb6b686a80e;hb=04906225f6fe1bc22f73b5d6a98eb9c0992a9b54;hp=a5bd67233cdc4bca604e8623a2bf3732d1aa2fe4;hpb=5af4cb6fd26054ef16c8da79d534abacb2a32c6e;p=libfirm diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c index a5bd67233..feb2b79eb 100644 --- a/ir/be/becopyheur4.c +++ b/ir/be/becopyheur4.c @@ -29,9 +29,9 @@ * (also known as "heur3" :) * Performs simple copy minimization. */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif /* HAVE_CONFIG_H */ + +#define DISABLE_STATEV #include @@ -81,8 +81,8 @@ static firm_dbg_module_t *dbg = NULL; typedef float real_t; #define REAL(C) (C ## f) -static int last_chunk_id = 0; -static int recolor_limit = 4; +static unsigned last_chunk_id = 0; +static int recolor_limit = 7; static real_t dislike_influence = REAL(0.1); typedef struct _col_cost_t { @@ -95,12 +95,12 @@ typedef struct _col_cost_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. */ + const ir_node **interfere; /**< An ARR_F containing all inference. */ int weight; /**< Weight of this chunk */ unsigned weight_consistent : 1; /**< Set if the weight is consistent. */ unsigned deleted : 1; /**< For debugging: Set if the was deleted. */ - int id; /**< An id of this chunk. */ - int visited; + unsigned id; /**< An id of this chunk. */ + unsigned visited; col_cost_t color_affinity[1]; } aff_chunk_t; @@ -110,7 +110,7 @@ typedef struct _aff_chunk_t { typedef struct _aff_edge_t { const ir_node *src; /**< Source node. */ const ir_node *tgt; /**< Target node. */ - double weight; /**< The weight of this edge. */ + int weight; /**< The weight of this edge. */ } aff_edge_t; /* main coalescing environment */ @@ -119,12 +119,11 @@ typedef struct _co_mst_env_t { int k; /**< number of non-ignore registers in class */ bitset_t *ignore_regs; /**< set containing all global ignore registers */ ir_phase ph; /**< phase object holding data for nodes */ - pqueue *chunks; /**< priority queue for chunks */ + pqueue_t *chunks; /**< priority queue for chunks */ pset *chunkset; /**< set holding all chunks */ be_ifg_t *ifg; /**< the interference graph */ - const arch_env_t *aenv; /**< the arch environment */ copy_opt_t *co; /**< the copy opt object */ - int chunk_visited; + unsigned chunk_visited; col_cost_t **single_cols; } co_mst_env_t; @@ -156,7 +155,6 @@ typedef int decide_func_t(const co_mst_irn_t *node, int col); static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) { int i, l; (void) env; - if (c->weight_consistent) ir_fprintf(stderr, " $%d ", c->weight); ir_fprintf(stderr, "{"); @@ -255,9 +253,9 @@ static int cmp_col_cost_gt(const void *a, const void *b) { * Creates a new affinity chunk */ static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) { - aff_chunk_t *c = xmalloc(sizeof(*c) + (env->n_regs - 1) * sizeof(c->color_affinity[0])); + aff_chunk_t *c = XMALLOCF(aff_chunk_t, color_affinity, env->n_regs); c->n = NEW_ARR_F(const ir_node *, 0); - c->interfere = NEW_ARR_F(ir_node *, 0); + c->interfere = NEW_ARR_F(const ir_node *, 0); c->weight = -1; c->weight_consistent = 0; c->deleted = 0; @@ -370,7 +368,7 @@ static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old) { res->tmp_col = -1; res->int_neighs = NULL; res->int_aff_neigh = 0; - res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn)); + res->col = arch_register_get_index(arch_get_irn_register(irn)); res->init_col = res->col; INIT_LIST_HEAD(&res->list); @@ -380,7 +378,7 @@ static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old) { res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs); /* Exclude colors not assignable to the irn */ - req = arch_get_register_req(env->aenv, irn, -1); + req = arch_get_register_req(irn, -1); if (arch_register_req_is(req, limited)) rbitset_copy_to_bitset(req->limited, res->adm_colors); else @@ -398,7 +396,7 @@ static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old) { /* build list of interfering neighbours */ len = 0; be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) { - if (! arch_irn_is(env->aenv, neigh, ignore)) { + if (!arch_irn_is(neigh, ignore)) { obstack_ptr_grow(phase_obst(ph), neigh); ++len; } @@ -457,13 +455,13 @@ static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node aff_chunk_t *c2 = get_aff_chunk(env, tgt); #ifdef DEBUG_libfirm - DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1)); + DB((dbg, LEVEL_4, "Attempt to let c1 (id %u): ", c1 ? c1->id : 0)); if (c1) { DBG_AFF_CHUNK(env, LEVEL_4, c1); } else { DB((dbg, LEVEL_4, "{%+F}", src)); } - DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2 ? c2->id : -1)); + DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %u): ", c2 ? c2->id : 0)); if (c2) { DBG_AFF_CHUNK(env, LEVEL_4, c2); } else { @@ -555,10 +553,9 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) { neighb_t *neigh; co_gs_foreach_neighb(an, neigh) { const ir_node *m = neigh->irn; - const int m_idx = get_irn_idx(m); /* skip ignore nodes */ - if (arch_irn_is(env->aenv, m, ignore)) + if (arch_irn_is(m, ignore)) continue; w += node_contains(c->n, m) ? neigh->costs : 0; @@ -589,7 +586,7 @@ static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t int i; /* skip ignore nodes */ - if (arch_irn_is(env->aenv, n, ignore)) + if (arch_irn_is(n, ignore)) continue; /* check if the affinity neighbour interfere */ @@ -625,7 +622,7 @@ static void build_affinity_chunks(co_mst_env_t *env) { affinity_node_t *an; /* skip ignore nodes */ - if (arch_irn_is(env->aenv, n, ignore)) + if (arch_irn_is(n, ignore)) continue; n1 = get_co_mst_irn(env, n); @@ -648,7 +645,7 @@ static void build_affinity_chunks(co_mst_env_t *env) { aff_edge_t edge; /* skip ignore nodes */ - if (arch_irn_is(env->aenv, m, ignore)) + if (arch_irn_is(m, ignore)) continue; edge.src = n; @@ -683,7 +680,7 @@ static void build_affinity_chunks(co_mst_env_t *env) { foreach_pset(env->chunkset, curr_chunk) { aff_chunk_assure_weight(env, curr_chunk); - DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id)); + DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id)); DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk); DBG((dbg, LEVEL_1, "\n")); @@ -700,7 +697,7 @@ static void build_affinity_chunks(co_mst_env_t *env) { aff_chunk_assure_weight(env, curr_chunk); - DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id)); + DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id)); DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk); DBG((dbg, LEVEL_1, "\n")); @@ -713,7 +710,7 @@ 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 *grow = new_pqueue(); + pqueue_t *grow = new_pqueue(); const ir_node *max_node = NULL; int max_weight = 0; int i; @@ -724,7 +721,7 @@ static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chu int w = 0; neighb_t *neigh; - if (arch_irn_is(env->aenv, irn, ignore)) + if (arch_irn_is(irn, ignore)) continue; if (an) { @@ -748,11 +745,11 @@ static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chu bitset_remv_irn(visited, max_node); i = 0; while (!pqueue_empty(grow)) { - ir_node *irn = pqueue_get(grow); + ir_node *irn = pqueue_pop_front(grow); affinity_node_t *an = get_affinity_info(env->co, irn); neighb_t *neigh; - if (arch_irn_is(env->aenv, irn, ignore)) + if (arch_irn_is(irn, ignore)) continue; assert(i <= ARR_LEN(chunk->n)); @@ -784,7 +781,7 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v { waitq *nodes = new_waitq(); - DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%d) from %+F, color %d:", chunk->id, node->irn, col)); + DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%u) from %+F, color %d:", chunk->id, node->irn, col)); /* init queue and chunk */ waitq_put(nodes, node); @@ -806,7 +803,7 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v co_mst_irn_t *n2; /* skip ignore nodes */ - if (arch_irn_is(env->aenv, m, ignore)) + if (arch_irn_is(m, ignore)) continue; n2 = get_co_mst_irn(env, m); @@ -864,12 +861,12 @@ static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, w if (get_mst_irn_col(node) == col) { decider = decider_has_color; check_for_best = 1; - DBG((dbg, LEVEL_4, "\tcolor %d wanted", col)); + DBG((dbg, LEVEL_4, "\tcolor %d wanted\n", col)); } else { decider = decider_hasnot_color; check_for_best = 0; - DBG((dbg, LEVEL_4, "\tcolor %d forbidden", col)); + DBG((dbg, LEVEL_4, "\tcolor %d forbidden\n", col)); } /* create a new chunk starting at current node */ @@ -1015,21 +1012,25 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost if (depth > *max_depth) *max_depth = depth; - if (depth >= recolor_limit) - return 0; - DBG((dbg, LEVEL_4, "\tRecoloring %+F with color-costs", node->irn)); DBG_COL_COST(env, LEVEL_4, costs); DB((dbg, LEVEL_4, "\n")); + if (depth >= recolor_limit) { + DBG((dbg, LEVEL_4, "\tHit recolor limit\n")); + return 0; + } + for (i = 0; i < env->n_regs; ++i) { int tgt_col = costs[i].col; int neigh_ok = 1; int j; /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */ - if (costs[i].cost == REAL(0.0)) + if (costs[i].cost == REAL(0.0)) { + DBG((dbg, LEVEL_4, "\tAll further colors forbidden\n")); return 0; + } /* Set the new color of the node and mark the node as temporarily fixed. */ assert(node->tmp_col < 0 && "Node must not have been temporary fixed."); @@ -1045,7 +1046,7 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost neigh = node->int_neighs[j]; /* skip ignore nodes */ - if (arch_irn_is(env->aenv, neigh, ignore)) + if (arch_irn_is(neigh, ignore)) continue; nn = get_co_mst_irn(env, neigh); @@ -1082,6 +1083,7 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost } } + DBG((dbg, LEVEL_4, "\tAll colors failed\n")); return 0; } @@ -1152,11 +1154,11 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { int idx, len, i, nidx, pos; struct list_head changed; - DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id)); + DB((dbg, LEVEL_2, "fragmentizing chunk #%u", c->id)); DBG_AFF_CHUNK(env, LEVEL_2, c); DB((dbg, LEVEL_2, "\n")); - stat_ev_ctx_push_fmt("heur4_color_chunk", "%d", c->id); + stat_ev_ctx_push_fmt("heur4_color_chunk", "%u", c->id); ++env->chunk_visited; @@ -1260,7 +1262,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { if (local_best) { aff_chunk_assure_weight(env, local_best); - DB((dbg, LEVEL_3, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col)); + DB((dbg, LEVEL_3, "\t\tlocal best chunk (id %u) for color %d: ", local_best->id, col)); DBG_AFF_CHUNK(env, LEVEL_3, local_best); if (! best_chunk || best_chunk->weight < local_best->weight) { @@ -1269,7 +1271,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { if (best_starts) del_waitq(best_starts); best_starts = good_starts; - DB((dbg, LEVEL_3, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color)); + DB((dbg, LEVEL_3, "\n\t\t... setting global best chunk (id %u), color %d\n", best_chunk->id, best_color)); } else { DB((dbg, LEVEL_3, "\n\t\t... omitting, global best is better\n")); del_waitq(good_starts); @@ -1301,7 +1303,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { return; } - DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id)); + DB((dbg, LEVEL_2, "\tbest chunk #%u ", best_chunk->id)); DBG_AFF_CHUNK(env, LEVEL_2, best_chunk); DB((dbg, LEVEL_2, "using color %d\n", best_color)); @@ -1311,7 +1313,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { int res; /* bring the node to the color. */ - DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, node->irn, best_chunk->id)); + DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%u\n", best_color, node->irn, best_chunk->id)); INIT_LIST_HEAD(&changed); stat_ev_tim_push(); res = change_node_color(env, node, best_color, &changed); @@ -1392,6 +1394,8 @@ int co_solve_heuristic_mst(copy_opt_t *co) { ir_node *irn; co_mst_env_t mst_env; + last_chunk_id = 0; + stat_ev_tim_push(); /* init phase */ @@ -1406,7 +1410,6 @@ int co_solve_heuristic_mst(copy_opt_t *co) { mst_env.co = co; mst_env.ignore_regs = ignore_regs; mst_env.ifg = co->cenv->ifg; - mst_env.aenv = co->aenv; mst_env.chunkset = pset_new_ptr(512); mst_env.chunk_visited = 0; mst_env.single_cols = phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs); @@ -1433,10 +1436,10 @@ 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_get(mst_env.chunks); + aff_chunk_t *chunk = pqueue_pop_front(mst_env.chunks); color_aff_chunk(&mst_env, chunk); - DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id)); + DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%u) done\n", chunk->id)); delete_aff_chunk(&mst_env, chunk); } @@ -1445,7 +1448,7 @@ int co_solve_heuristic_mst(copy_opt_t *co) { co_mst_irn_t *mirn; const arch_register_t *reg; - if (arch_irn_is(mst_env.aenv, irn, ignore)) + if (arch_irn_is(irn, ignore)) continue; mirn = get_co_mst_irn(&mst_env, irn); @@ -1456,7 +1459,7 @@ int co_solve_heuristic_mst(copy_opt_t *co) { continue; reg = arch_register_for_index(co->cls, mirn->col); - arch_set_irn_register(co->aenv, irn, reg); + arch_set_irn_register(irn, reg); DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col)); }