X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur4.c;h=76a19306f8cfa48be5b2e662def06a770836e408;hb=6e96ec2cff42d9e59757d486e9b64b8f3bdb1704;hp=c95106b7f907e3efbdd2ee0b075bccbbd6bf8166;hpb=ebd4fd4ac7f950d10225a0a0fe7825e816cd6068;p=libfirm diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c index c95106b7f..76a19306f 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 { @@ -99,8 +99,8 @@ typedef struct _aff_chunk_t { 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; @@ -193,7 +192,7 @@ static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) { #endif /* DEBUG_libfirm */ -static INLINE int get_mst_irn_col(const co_mst_irn_t *node) { +static inline int get_mst_irn_col(const co_mst_irn_t *node) { return node->tmp_col >= 0 ? node->tmp_col : node->col; } @@ -253,8 +252,8 @@ 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])); +static inline aff_chunk_t *new_aff_chunk(co_mst_env_t *env) { + 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(const ir_node *, 0); c->weight = -1; @@ -269,7 +268,7 @@ static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) { /** * Frees all memory allocated by an affinity chunk. */ -static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { +static inline void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { pset_remove(env->chunkset, c, c->id); DEL_ARR_F(c->interfere); DEL_ARR_F(c->n); @@ -283,7 +282,7 @@ static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { * @return the position where n is found in the array arr or ~pos * if the nodes is not here. */ -static INLINE int nodes_bsearch(const ir_node **arr, const ir_node *n) { +static inline int nodes_bsearch(const ir_node **arr, const ir_node *n) { int hi = ARR_LEN(arr); int lo = 0; @@ -335,7 +334,7 @@ static int nodes_insert(const ir_node ***arr, const ir_node *irn) { /** * Adds a node to an affinity chunk */ -static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) { +static inline void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) { int i; if (! nodes_insert(&c->n, node->irn)) @@ -369,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); @@ -379,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_out(irn); if (arch_register_req_is(req, limited)) rbitset_copy_to_bitset(req->limited, res->adm_colors); else @@ -397,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_ignore(neigh)) { obstack_ptr_grow(phase_obst(ph), neigh); ++len; } @@ -411,7 +410,7 @@ static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old) { /** * Check if affinity chunk @p chunk interferes with node @p irn. */ -static INLINE int aff_chunk_interferes(const aff_chunk_t *chunk, const ir_node *irn) { +static inline int aff_chunk_interferes(const aff_chunk_t *chunk, const ir_node *irn) { return node_contains(chunk->interfere, irn); } @@ -421,7 +420,7 @@ static INLINE int aff_chunk_interferes(const aff_chunk_t *chunk, const ir_node * * @param c2 Another chunk * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise. */ -static INLINE int aff_chunks_interfere(const aff_chunk_t *c1, const aff_chunk_t *c2) { +static inline int aff_chunks_interfere(const aff_chunk_t *c1, const aff_chunk_t *c2) { int i; if (c1 == c2) @@ -441,7 +440,7 @@ static INLINE int aff_chunks_interfere(const aff_chunk_t *c1, const aff_chunk_t * Returns the affinity chunk of @p irn or creates a new * one with @p irn as element if there is none assigned. */ -static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, const ir_node *irn) { +static inline aff_chunk_t *get_aff_chunk(co_mst_env_t *env, const ir_node *irn) { co_mst_irn_t *node = get_co_mst_irn(env, irn); return node->chunk; } @@ -456,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 { @@ -553,10 +552,9 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) { if (an != NULL) { neighb_t *neigh; co_gs_foreach_neighb(an, neigh) { - const ir_node *m = neigh->irn; + const ir_node *m = neigh->irn; - /* skip ignore nodes */ - if (arch_irn_is(env->aenv, m, ignore)) + if (arch_irn_is_ignore(m)) continue; w += node_contains(c->n, m) ? neigh->costs : 0; @@ -586,8 +584,7 @@ static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t const ir_node *n = neigh->irn; int i; - /* skip ignore nodes */ - if (arch_irn_is(env->aenv, n, ignore)) + if (arch_irn_is_ignore(n)) continue; /* check if the affinity neighbour interfere */ @@ -622,8 +619,7 @@ static void build_affinity_chunks(co_mst_env_t *env) { co_mst_irn_t *n1; affinity_node_t *an; - /* skip ignore nodes */ - if (arch_irn_is(env->aenv, n, ignore)) + if (arch_irn_is_ignore(n)) continue; n1 = get_co_mst_irn(env, n); @@ -646,7 +642,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_ignore(m)) continue; edge.src = n; @@ -681,7 +677,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")); @@ -698,7 +694,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")); @@ -711,7 +707,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; @@ -722,7 +718,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_ignore(irn)) continue; if (an) { @@ -746,11 +742,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; + neighb_t *neigh; - if (arch_irn_is(env->aenv, irn, ignore)) + if (arch_irn_is_ignore(irn)) continue; assert(i <= ARR_LEN(chunk->n)); @@ -782,7 +778,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); @@ -803,8 +799,7 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v int m_idx = get_irn_idx(m); co_mst_irn_t *n2; - /* skip ignore nodes */ - if (arch_irn_is(env->aenv, m, ignore)) + if (arch_irn_is_ignore(m)) continue; n2 = get_co_mst_irn(env, m); @@ -862,12 +857,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 */ @@ -891,7 +886,7 @@ static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, w * Resets the temporary fixed color of all nodes within wait queue @p nodes. * ATTENTION: the queue is empty after calling this function! */ -static INLINE void reject_coloring(struct list_head *nodes) { +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) { @@ -903,7 +898,7 @@ static INLINE void reject_coloring(struct list_head *nodes) { DB((dbg, LEVEL_4, "\n")); } -static INLINE void materialize_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); @@ -913,7 +908,7 @@ static INLINE void materialize_coloring(struct list_head *nodes) { } } -static INLINE void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed) +static inline void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed) { assert(col >= 0); assert(!node->fixed); @@ -925,7 +920,7 @@ static INLINE void set_temp_color(co_mst_irn_t *node, int col, struct list_head node->tmp_col = col; } -static INLINE int is_loose(co_mst_irn_t *node) +static inline int is_loose(co_mst_irn_t *node) { return !node->fixed && node->tmp_col < 0; } @@ -933,11 +928,12 @@ static INLINE int is_loose(co_mst_irn_t *node) /** * Determines the costs for each color if it would be assigned to node @p node. */ -static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) { - int *neigh_cols = alloca(env->n_regs * sizeof(*neigh_cols)); - int n_loose = 0; +static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) +{ + int *neigh_cols = ALLOCAN(int, env->n_regs); + int n_loose = 0; real_t coeff; - int i; + int i; for (i = 0; i < env->n_regs; ++i) { neigh_cols[i] = 0; @@ -982,7 +978,7 @@ static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int /* The node has the color it should not have _and_ has not been visited yet. */ if (is_loose(node)) { - col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0])); + col_cost_t *costs = ALLOCAN(col_cost_t, env->n_regs); /* Get the costs for giving the node a specific color. */ determine_color_costs(env, node, costs); @@ -1013,21 +1009,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."); @@ -1042,8 +1042,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_ignore(neigh)) continue; nn = get_co_mst_irn(env, neigh); @@ -1080,6 +1079,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; } @@ -1145,22 +1145,20 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { int n_int_chunks = 0; waitq *tmp_chunks = new_waitq(); waitq *best_starts = NULL; - col_cost_t *order = alloca(env->n_regs * sizeof(order[0])); + col_cost_t *order = ALLOCANZ(col_cost_t, env->n_regs); bitset_t *visited; 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; /* compute color preference */ - memset(order, 0, env->n_regs * sizeof(order[0])); - for (pos = 0, len = ARR_LEN(c->interfere); pos < len; ++pos) { const ir_node *n = c->interfere[pos]; co_mst_irn_t *node = get_co_mst_irn(env, n); @@ -1258,7 +1256,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) { @@ -1267,7 +1265,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); @@ -1299,7 +1297,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)); @@ -1309,7 +1307,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); @@ -1390,6 +1388,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 */ @@ -1404,7 +1404,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); @@ -1431,19 +1430,19 @@ 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); } /* apply coloring */ foreach_phase_irn(&mst_env.ph, irn) { - co_mst_irn_t *mirn; + co_mst_irn_t *mirn; const arch_register_t *reg; - if (arch_irn_is(mst_env.aenv, irn, ignore)) + if (arch_irn_is_ignore(irn)) continue; mirn = get_co_mst_irn(&mst_env, irn); @@ -1454,7 +1453,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)); }