X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur4.c;h=ee97153b601fc6dab49a33b8f2e8b1efd3a93b98;hb=b0e09fe0aada2e5d9dc0299e969b3c93c1092d97;hp=c28c807790f672b478e867bdb2be39b2d9431d46;hpb=d6768d8d4427959eb045aafb1d15bd189beaa5dd;p=libfirm diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c index c28c80779..ee97153b6 100644 --- a/ir/be/becopyheur4.c +++ b/ir/be/becopyheur4.c @@ -41,23 +41,27 @@ #include "raw_bitset.h" #include "irphase_t.h" #include "pqueue.h" -#include "pset_new.h" #include "xmalloc.h" #include "pdeq.h" +#include "pset.h" #include "irprintf.h" #include "irbitset.h" +#include "error.h" #include "bearch.h" #include "beifg.h" #include "be_t.h" #include "becopyopt_t.h" +#include "bemodule.h" + +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) #define COL_COST_INFEASIBLE DBL_MAX #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0 #define NEIGHBOUR_CONSTR_COSTS 64.0 -#define DBG_AFF_CHUNK(env, level, chunk) DEBUG_ONLY(if (firm_dbg_get_mask((env)->dbg) & (level)) dbg_aff_chunk((env), (chunk));) -#define DBG_COL_COST(env, level, cost) DEBUG_ONLY(if (firm_dbg_get_mask((env)->dbg) & (level)) dbg_col_cost((env), (cost));) +#define DBG_AFF_CHUNK(env, level, chunk) DEBUG_ONLY(do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while(0)) +#define DBG_COL_COST(env, level, cost) DEBUG_ONLY(do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while(0)) static int last_chunk_id = 0; @@ -66,31 +70,39 @@ typedef struct _col_cost_t { double cost; } col_cost_t; +/** + * An affinity chunk. + */ typedef struct _aff_chunk_t { - bitset_t *nodes; - int weight; - unsigned weight_consistent : 1; - int id; + ir_node **n; /**< An ARR_F containing all nodes of the chunk. */ + bitset_t *nodes; /**< A bitset containing all nodes inside this chunk. */ + bitset_t *interfere; /**< A bitset containing all interfering neighbours of the nodes in this chunk. */ + int weight; /**< Weight of this chunk */ + unsigned weight_consistent : 1; /**< Set if the weight is consistent. */ + unsigned deleted : 1; /**< Set if the was deleted. */ + int id; /**< For debugging: An id of this chunk. */ } aff_chunk_t; +/** + * An affinity edge. + */ typedef struct _aff_edge_t { - ir_node *src; - ir_node *tgt; - double weight; + ir_node *src; /**< Source node. */ + ir_node *tgt; /**< Target node. */ + double weight; /**< The weight of this edge. */ } aff_edge_t; -/* main coalescing environment*/ +/* 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 *ignore_regs; /**< set containing all global ignore registers */ ir_phase ph; /**< phase object holding data for nodes */ pqueue *chunks; /**< priority queue for chunks */ - pset_new_t chunkset; /**< set holding all 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 */ - DEBUG_ONLY(firm_dbg_module_t *dbg); } co_mst_env_t; /* stores coalescing related information for a node */ @@ -98,7 +110,8 @@ typedef struct _co_mst_irn_t { 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 */ - ir_node **int_neighs; /**< ARR_D of all interfering neighbours (cached for speed reasons) */ + ir_node **int_neighs; /**< array of all interfering neighbours (cached for speed reasons) */ + int n_neighs; /**< length of the interfering neighbours array. */ int int_aff_neigh; /**< number of interfering affinity neighbours */ int col; /**< color currently assigned */ int init_col; /**< the initial color */ @@ -109,15 +122,15 @@ typedef struct _co_mst_irn_t { #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn))) -typedef int decide_func_t(co_mst_irn_t *node, int col); +typedef int decide_func_t(const co_mst_irn_t *node, int col); #ifdef DEBUG_libfirm /** * Write a chunk to stderr for debugging. */ -static void dbg_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { - int idx; +static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) { + bitset_pos_t idx; if (c->weight_consistent) ir_fprintf(stderr, " $%d ", c->weight); ir_fprintf(stderr, "{"); @@ -131,8 +144,10 @@ static void dbg_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { /** * Dump all admissible colors to stderr. */ -static void dbg_admissible_colors(co_mst_env_t *env, co_mst_irn_t *node) { - int idx; +static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node) { + bitset_pos_t idx; + (void) env; + if (bitset_popcnt(node->adm_colors) < 1) fprintf(stderr, "no admissible colors?!?"); else { @@ -144,7 +159,7 @@ static void dbg_admissible_colors(co_mst_env_t *env, co_mst_irn_t *node) { /** * Dump color-cost pairs to stderr. */ -static void dbg_col_cost(co_mst_env_t *env, col_cost_t *cost) { +static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) { int i; for (i = 0; i < env->n_regs; ++i) { if (cost[i].cost == COL_COST_INFEASIBLE) @@ -156,32 +171,34 @@ static void dbg_col_cost(co_mst_env_t *env, col_cost_t *cost) { #endif /* DEBUG_libfirm */ -static INLINE int get_mst_irn_col(co_mst_irn_t *node) { +static INLINE int get_mst_irn_col(const co_mst_irn_t *node) { return node->tmp_fixed ? node->tmp_col : node->col; } /** * @return 1 if node @p node has color @p col, 0 otherwise. */ -static int decider_has_color(co_mst_irn_t *node, int col) { +static int decider_has_color(const co_mst_irn_t *node, int col) { return get_mst_irn_col(node) == col; } /** * @return 1 if node @p node has not color @p col, 0 otherwise. */ -static int decider_hasnot_color(co_mst_irn_t *node, int col) { +static int decider_hasnot_color(const co_mst_irn_t *node, int col) { return get_mst_irn_col(node) != col; } /** * Always returns true. */ -static int decider_always_yes(co_mst_irn_t *node, int col) { +static int decider_always_yes(const co_mst_irn_t *node, int col) { + (void) node; + (void) col; return 1; } -/* > compares two affinity edges by its weight */ +/** 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; @@ -196,7 +213,7 @@ static int cmp_aff_edge(const void *a, const void *b) { return QSORT_CMP(e2->weight, e1->weight); } -/* compares to color-cost pairs */ +/** compares to color-cost pairs */ static int cmp_col_cost(const void *a, const void *b) { const col_cost_t *c1 = a; const col_cost_t *c2 = b; @@ -211,9 +228,11 @@ static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) { aff_chunk_t *c = xmalloc(sizeof(*c)); c->weight = -1; c->weight_consistent = 0; + c->n = NEW_ARR_F(ir_node *, 0); c->nodes = bitset_irg_malloc(env->co->irg); + c->interfere = bitset_irg_malloc(env->co->irg); c->id = last_chunk_id++; - pset_new_insert(&env->chunkset, c); + pset_insert(env->chunkset, c, c->id); return c; } @@ -221,8 +240,11 @@ 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) { - pset_new_remove(&env->chunkset, c); + pset_remove(env->chunkset, c, c->id); bitset_free(c->nodes); + bitset_free(c->interfere); + DEL_ARR_F(c->n); + c->deleted = 1; free(c); } @@ -230,9 +252,21 @@ static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { * Adds a node to an affinity chunk */ static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) { + int i; + + if (bitset_is_set(c->nodes, get_irn_idx(node->irn))) + return; + c->weight_consistent = 0; node->chunk = c; bitset_set(c->nodes, get_irn_idx(node->irn)); + + ARR_APP1(ir_node *, c->n, node->irn); + + for (i = node->n_neighs - 1; i >= 0; --i) { + ir_node *neigh = node->int_neighs[i]; + bitset_set(c->interfere, get_irn_idx(neigh)); + } } /** @@ -249,7 +283,7 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) { unsigned len; res->irn = irn; - res->chunk = new_aff_chunk(env); + res->chunk = NULL; res->fixed = 0; res->tmp_fixed = 0; res->tmp_col = -1; @@ -258,10 +292,7 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) { res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn)); res->init_col = res->col; - /* add note to new chunk */ - aff_chunk_add_node(res->chunk, res); - - DB((env->dbg, LEVEL_4, "Creating phase info for %+F, chunk %d\n", irn, res->chunk->id)); + 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); @@ -281,13 +312,14 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) { /* build list of interfering neighbours */ len = 0; - /* count them first as an obstack array cannot be extended */ - be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) - len++; - res->int_neighs = NEW_ARR_D(ir_node *, phase_obst(ph), len); - len = 0; - be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) - res->int_neighs[len++] = neigh; + be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) { + if (! arch_irn_is(env->aenv, neigh, ignore)) { + obstack_ptr_grow(phase_obst(ph), neigh); + ++len; + } + } + res->int_neighs = obstack_finish(phase_obst(ph)); + res->n_neighs = len; } return res; } @@ -295,18 +327,9 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) { /** * Check if affinity chunk @p chunk interferes with node @p irn. */ -static INLINE int aff_chunk_interferes(co_mst_env_t *env, aff_chunk_t *chunk, ir_node *irn) { - co_mst_irn_t *node = get_co_mst_irn(env, irn); - ir_node *neigh; - int i; - - for (i = 0; i < ARR_LEN(node->int_neighs); ++i) { - neigh = node->int_neighs[i]; - if (! arch_irn_is(env->aenv, neigh, ignore) && bitset_is_set(chunk->nodes, get_irn_idx(neigh))) - return 1; - } - - return 0; +static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, ir_node *irn) { + (void) env; + return bitset_is_set(chunk->interfere, get_irn_idx(irn)); } /** @@ -316,82 +339,129 @@ static INLINE int aff_chunk_interferes(co_mst_env_t *env, aff_chunk_t *chunk, ir * @param c2 Another chunk * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise. */ -static INLINE int aff_chunks_interfere(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) { - int idx; +static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) { + bitset_t *tmp; if (c1 == c2) return 0; /* check if there is a node in c2 having an interfering neighbor in c1 */ - bitset_foreach(c2->nodes, idx) { - ir_node *n = get_idx_irn(env->co->irg, idx); + tmp = bitset_alloca(get_irg_last_idx(env->co->irg)); + tmp = bitset_copy(tmp, c1->interfere); + tmp = bitset_and(tmp, c2->nodes); - if (aff_chunk_interferes(env, c1, n)) - return 1; - } + return bitset_popcnt(tmp) > 0; +} - return 0; +/** + * 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, ir_node *irn) { + co_mst_irn_t *node = get_co_mst_irn(env, irn); + return node->chunk; } /** - * Let c1 absorb the nodes of c2 (only possible when there - * are no interference edges from c1 to c2). + * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there + * are no interference edges from chunk(src) to chunk(tgt)). * @return 1 if successful, 0 if not possible */ -static int aff_chunk_absorb(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) { - DB((env->dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1->id)); - DBG_AFF_CHUNK(env, LEVEL_4, c1); - DB((env->dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2->id)); - DBG_AFF_CHUNK(env, LEVEL_4, c2); - DB((env->dbg, LEVEL_4, "\n")); +static int aff_chunk_absorb(co_mst_env_t *env, ir_node *src, ir_node *tgt) { + aff_chunk_t *c1 = get_aff_chunk(env, src); + aff_chunk_t *c2 = get_aff_chunk(env, tgt); - if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) { - int idx; + DEBUG_ONLY( + DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1)); + 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)); + if (c2) { + DBG_AFF_CHUNK(env, LEVEL_4, c2); + } else { + DB((dbg, LEVEL_4, "{%+F}", tgt)); + } + DB((dbg, LEVEL_4, "\n")); + ) - bitset_or(c1->nodes, c2->nodes); - c1->weight_consistent = 0; + if (c1 == NULL) { + if (c2 == NULL) { + /* no chunk exists */ + co_mst_irn_t *mirn = get_co_mst_irn(env, src); + int i; + + for (i = mirn->n_neighs - 1; i >= 0; --i) { + if (mirn->int_neighs[i] == tgt) + break; + } + if (i < 0) { + /* create one containing both nodes */ + c1 = new_aff_chunk(env); + aff_chunk_add_node(c1, get_co_mst_irn(env, src)); + aff_chunk_add_node(c1, get_co_mst_irn(env, tgt)); + goto absorbed; + } + } else { + /* c2 already exists */ + if (! aff_chunk_interferes(env, c2, src)) { + aff_chunk_add_node(c2, get_co_mst_irn(env, src)); + goto absorbed; + } + } + } else if (c2 == NULL) { + /* c1 already exists */ + if (! aff_chunk_interferes(env, c1, tgt)) { + aff_chunk_add_node(c1, get_co_mst_irn(env, tgt)); + goto absorbed; + } + } else if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) { + int idx, len; - bitset_foreach(c2->nodes, idx) { - ir_node *n = get_idx_irn(env->co->irg, idx); + for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx) { + ir_node *n = c2->n[idx]; co_mst_irn_t *mn = get_co_mst_irn(env, n); + mn->chunk = c1; + + if (! bitset_is_set(c1->nodes, get_irn_idx(n))) + ARR_APP1(ir_node *, c1->n, n); } - DB((env->dbg, LEVEL_4, " ... absorbed, c2 deleted\n")); + bitset_or(c1->nodes, c2->nodes); + bitset_or(c1->interfere, c2->interfere); + c1->weight_consistent = 0; + delete_aff_chunk(env, c2); - return 1; + goto absorbed; } - DB((env->dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n")); + DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n")); return 0; -} -/** - * 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, ir_node *irn) { - co_mst_irn_t *node = get_co_mst_irn(env, irn); - assert(node->chunk && "Node should have a chunk."); - return node->chunk; +absorbed: + DB((dbg, LEVEL_4, " ... absorbed\n")); + return 1; } /** * Assures that the weight of the given chunk is consistent. */ -static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) { +static void aff_chunk_assure_weight(const co_mst_env_t *env, aff_chunk_t *c) { if (! c->weight_consistent) { int w = 0; - int idx; + int idx, len; - bitset_foreach(c->nodes, idx) { - ir_node *n = get_idx_irn(env->co->irg, idx); - affinity_node_t *an = get_affinity_info(env->co, n); + for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { + ir_node *n = c->n[idx]; + const affinity_node_t *an = get_affinity_info(env->co, n); if (an != NULL) { neighb_t *neigh; co_gs_foreach_neighb(an, neigh) { - ir_node *m = neigh->irn; - int m_idx = get_irn_idx(m); + 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)) @@ -410,22 +480,22 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) { /** * Count the number of interfering affinity neighbours */ -static int count_interfering_aff_neighs(co_mst_env_t *env, affinity_node_t *an) { - neighb_t *neigh; - ir_node *irn = an->irn; - co_mst_irn_t *node = get_co_mst_irn(env, irn); - int res = 0; +static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) { + const neighb_t *neigh; + ir_node *irn = an->irn; + const co_mst_irn_t *node = get_co_mst_irn(env, irn); + int res = 0; co_gs_foreach_neighb(an, neigh) { - ir_node *n = neigh->irn; - int i; + const ir_node *n = neigh->irn; + int i; /* skip ignore nodes */ if (arch_irn_is(env->aenv, n, ignore)) continue; /* check if the affinity neighbour interfere */ - for (i = 0; i < ARR_LEN(node->int_neighs); ++i) { + for (i = 0; i < node->n_neighs; ++i) { if (node->int_neighs[i] == n) { ++res; break; @@ -449,7 +519,6 @@ static void build_affinity_chunks(co_mst_env_t *env) { ir_node *n; int i, len; aff_chunk_t *curr_chunk; - pset_new_iterator_t iter; /* at first we create the affinity edge objects */ be_ifg_foreach_node(env->ifg, nodes_it, n) { @@ -469,6 +538,8 @@ static void build_affinity_chunks(co_mst_env_t *env) { if (n1->int_aff_neigh < 0) n1->int_aff_neigh = count_interfering_aff_neighs(env, an); + + /* build the affinity edges */ co_gs_foreach_neighb(an, neigh) { ir_node *m = neigh->irn; int m_idx = get_irn_idx(m); @@ -501,25 +572,38 @@ static void build_affinity_chunks(co_mst_env_t *env) { len = ARR_LEN(edges); qsort(edges, len, sizeof(edges[0]), cmp_aff_edge); for (i = 0; i < len; ++i) { - aff_chunk_t *c1 = get_aff_chunk(env, edges[i].src); - aff_chunk_t *c2 = get_aff_chunk(env, edges[i].tgt); - - DBG((env->dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight)); + 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, c1, c2); + (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt); } /* now insert all chunks into a priority queue */ - foreach_pset_new(&env->chunkset, curr_chunk, iter) { + foreach_pset(env->chunkset, curr_chunk) { aff_chunk_assure_weight(env, curr_chunk); - DBG((env->dbg, LEVEL_1, "entry #%d", curr_chunk->id)); + DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id)); DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk); - DBG((env->dbg, LEVEL_1, "\n")); - + DBG((dbg, LEVEL_1, "\n")); 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); + + 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); + + aff_chunk_assure_weight(env, curr_chunk); + + DBG((dbg, LEVEL_1, "entry #%d", 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); + } + } DEL_ARR_F(edges); } @@ -532,13 +616,13 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v { waitq *nodes = new_waitq(); - DBG((env->dbg, LEVEL_1, "\nExpanding new chunk (id %d) from %+F:", chunk->id, node->irn)); + DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%d) from %+F, color %d:", chunk->id, node->irn, col)); /* init queue and chunk */ waitq_put(nodes, node); bitset_set(visited, get_irn_idx(node->irn)); aff_chunk_add_node(chunk, node); - DB((env->dbg, LEVEL_1, " %+F", node->irn)); + DB((dbg, LEVEL_1, " %+F", node->irn)); /* as long as there are nodes in the queue */ while (! waitq_empty(nodes)) { @@ -575,7 +659,7 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v */ bitset_set(visited, m_idx); aff_chunk_add_node(chunk, n2); - DB((env->dbg, LEVEL_1, " %+F", n2->irn)); + DB((dbg, LEVEL_1, " %+F", n2->irn)); /* enqueue for further search */ waitq_put(nodes, n2); } @@ -583,7 +667,7 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v } } - DB((env->dbg, LEVEL_1, "\n")); + DB((dbg, LEVEL_1, "\n")); del_waitq(nodes); } @@ -593,29 +677,31 @@ 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); - int idx; + int idx, len; aff_chunk_t *best = NULL; - bitset_foreach(c->nodes, idx) { + for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { ir_node *irn; co_mst_irn_t *node; aff_chunk_t *tmp_chunk; decide_func_t *decider; int check_for_best; - if (bitset_is_set(visited, idx)) + irn = c->n[idx]; + if (bitset_is_set(visited, get_irn_idx(irn))) continue; - irn = get_idx_irn(env->co->irg, idx); node = get_co_mst_irn(env, irn); if (get_mst_irn_col(node) == col) { decider = decider_has_color; check_for_best = 1; + DBG((dbg, LEVEL_4, "\tcolor %d wanted", col)); } else { decider = decider_hasnot_color; check_for_best = 0; + DBG((dbg, LEVEL_4, "\tcolor %d forbidden", col)); } /* create a new chunk starting at current node */ @@ -668,10 +754,13 @@ static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int * ATTENTION: the queue is empty after calling this function! */ static INLINE void reject_coloring(waitq *nodes) { + DB((dbg, LEVEL_4, "\treject coloring for")); while (! waitq_empty(nodes)) { co_mst_irn_t *n = waitq_get(nodes); + DB((dbg, LEVEL_4, " %+F", n->irn)); n->tmp_fixed = 0; } + DB((dbg, LEVEL_4, "\n")); } /** @@ -680,7 +769,8 @@ static INLINE void reject_coloring(waitq *nodes) { static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) { affinity_node_t *an = get_affinity_info(env->co, node->irn); neighb_t *aff_neigh; - int idx, i; + bitset_pos_t idx; + int i; col_cost_init(env, costs, 0.0); @@ -707,7 +797,7 @@ static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cos } /* calculate (positive) costs for interfering neighbours */ - for (i = 0; i < ARR_LEN(node->int_neighs); ++i) { + for (i = 0; i < node->n_neighs; ++i) { co_mst_irn_t *neigh; int col, col_cnt; ir_node *int_neigh; @@ -793,9 +883,9 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost waitq *local_changed = new_waitq(); waitq *tmp = new_waitq(); - DBG((env->dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn)); + DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn)); DBG_COL_COST(env, LEVEL_1, costs); - DB((env->dbg, LEVEL_1, "\n")); + DB((dbg, LEVEL_1, "\n")); for (i = 0; i < env->n_regs; ++i) { int tgt_col = costs[i].col; @@ -814,12 +904,13 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost assert(! node->tmp_fixed && "Node must not have been temporary fixed."); node->tmp_fixed = 1; node->tmp_col = tgt_col; + DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col)); assert(waitq_empty(local_changed) && "Node queue should be empty here."); waitq_put(local_changed, node); /* try to color all interfering neighbours with current color forbidden */ - for (j = 0; j < ARR_LEN(node->int_neighs); ++j) { + for (j = 0; j < node->n_neighs; ++j) { co_mst_irn_t *nn; ir_node *neigh; @@ -830,6 +921,8 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost continue; nn = get_co_mst_irn(env, neigh); + DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_fixed: %d, tmp_col: %d, col: %d)\n", + neigh, j, nn->fixed, nn->tmp_fixed, nn->tmp_col, nn->col)); /* Try to change the color of the neighbor and record all nodes which @@ -882,7 +975,7 @@ static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, /* if node already has the target color -> good, temporary fix it */ if (col == tgt_col) { - DBG((env->dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col)); + DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col)); if (! node->tmp_fixed) { node->tmp_fixed = 1; node->tmp_col = tgt_col; @@ -901,24 +994,24 @@ static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, col_cost_init_single(env, costs, tgt_col); - DBG((env->dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn)); + DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn)); res = recolor_nodes(env, node, costs, changed_ones); - DBG((env->dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed")); + DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed")); return res; } - DEBUG_ONLY( - if (firm_dbg_get_mask(env->dbg) & LEVEL_4) { +#ifndef NDEBUG + if (firm_dbg_get_mask(dbg) & LEVEL_4) { if (node->fixed || node->tmp_fixed) - DB((env->dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col)); + DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col)); else { - DB((env->dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn)); + DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn)); dbg_admissible_colors(env, node); - DB((env->dbg, LEVEL_4, ")\n")); + DB((dbg, LEVEL_4, ")\n")); } } - ) +#endif return 0; } @@ -930,33 +1023,60 @@ static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { aff_chunk_t *best_chunk = NULL; int best_color = -1; + int did_all = 0; waitq *changed_ones = new_waitq(); waitq *tmp_chunks = new_waitq(); + waitq *best_starts = NULL; bitset_t *visited; - int col, idx; + int col, idx, len; - DB((env->dbg, LEVEL_2, "fragmentizing chunk #%d", c->id)); + DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id)); DBG_AFF_CHUNK(env, LEVEL_2, c); - DB((env->dbg, LEVEL_2, "\n")); + DB((dbg, LEVEL_2, "\n")); + + + /* check which color is the "best" for the given chunk. + * if we found a color which was ok for all nodes, we take it + * and do not look further. (see did_all flag usage below.) + * If we have many colors which fit all nodes it is hard to decide + * which one to take anyway. + * TODO Sebastian: Perhaps we should at all nodes and figure out + * a suitable color using costs as done above (determine_color_costs). + */ + for (col = 0; col < env->n_regs && !did_all; ++col) { + int one_good = 0; + waitq *good_starts = new_waitq(); + aff_chunk_t *local_best; + /* skip ignore colors */ + if (bitset_is_set(env->ignore_regs, col)) + continue; - /* check which color is the "best" for the given chunk */ - for (col = 0; col < env->k; ++col) { - int one_good = 0; - aff_chunk_t *local_best; + DB((dbg, LEVEL_3, "\ttrying color %d\n", col)); - DB((env->dbg, LEVEL_3, "\ttrying color %d\n", col)); + /* suppose we can color all nodes to the same color */ + did_all = 1; /* try to bring all nodes of given chunk to the current color. */ - bitset_foreach(c->nodes, idx) { - ir_node *irn = get_idx_irn(env->co->irg, idx); + for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { + ir_node *irn = c->n[idx]; co_mst_irn_t *node = get_co_mst_irn(env, irn); + int good = 0; assert(! node->fixed && "Node must not have a fixed color."); + DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col)); - DB((env->dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col)); - one_good |= change_node_color(env, node, col, changed_ones); - DB((env->dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed")); + /* + The order of the colored nodes is important, so we record the successfully + colored ones in the order they appeared. + */ + good = change_node_color(env, node, col, changed_ones); + if (good) + waitq_put(good_starts, node); + one_good |= good; + did_all &= good; + + DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed")); } /* try next color when failed */ @@ -971,17 +1091,24 @@ 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((env->dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col)); + DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col)); DBG_AFF_CHUNK(env, LEVEL_4, local_best); if (! best_chunk || best_chunk->weight < local_best->weight) { best_chunk = local_best; best_color = col; - DB((env->dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color)); + if (best_starts) + del_waitq(best_starts); + best_starts = good_starts; + DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color)); } else { - DB((env->dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n")); + DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n")); + del_waitq(good_starts); } } + else { + del_waitq(good_starts); + } /* reject the coloring and bring the coloring to the initial state */ reject_coloring(changed_ones); @@ -997,23 +1124,40 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { /* return if coloring failed */ if (! best_chunk) { - delete_aff_chunk(env, c); del_waitq(changed_ones); + if (best_starts) + del_waitq(best_starts); return; } - DB((env->dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id)); + DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id)); DBG_AFF_CHUNK(env, LEVEL_2, best_chunk); - DB((env->dbg, LEVEL_2, "using color %d\n", best_color)); + DB((dbg, LEVEL_2, "using color %d\n", best_color)); /* get the best fragment from the best list and color it */ - bitset_foreach(best_chunk->nodes, idx) { - ir_node *irn = get_idx_irn(env->co->irg, idx); + while (! waitq_empty(best_starts)) { + co_mst_irn_t *node = waitq_get(best_starts); + int res; + + if (! bitset_is_set(best_chunk->nodes, get_irn_idx(node->irn))) + continue; + + res = change_node_color(env, node, best_color, changed_ones); + if (! res) + panic("Color manifesting failed for %+F, color %d in chunk %d\n", node->irn, best_color, best_chunk->id); + node->fixed = 1; + node->chunk = best_chunk; + } + /* we colored the successful start nodes, now color the rest of the chunk */ + for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) { + ir_node *irn = best_chunk->n[idx]; co_mst_irn_t *node = get_co_mst_irn(env, irn); int res; res = change_node_color(env, node, best_color, changed_ones); - assert(res && "color manifesting failed"); + if (! res) + panic("Color manifesting failed for %+F, color %d in chunk %d\n", irn, best_color, best_chunk->id); + DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, irn, best_chunk->id)); node->fixed = 1; node->chunk = best_chunk; } @@ -1027,10 +1171,21 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { /* remove the nodes in best chunk from original chunk */ bitset_andnot(c->nodes, best_chunk->nodes); + for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { + ir_node *irn = c->n[idx]; + + if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) { + int last = ARR_LEN(c->n) - 1; + + c->n[idx] = c->n[last]; + ARR_SHRINKLEN(c->n, last); + len--; + } + } /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */ - bitset_foreach(c->nodes, idx) { - ir_node *n = get_idx_irn(env->co->irg, idx); + for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { + ir_node *n = c->n[idx]; co_mst_irn_t *nn = get_co_mst_irn(env, n); nn->chunk = c; } @@ -1038,10 +1193,10 @@ 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); bitset_or(visited, best_chunk->nodes); - bitset_foreach(c->nodes, idx) { - if (! bitset_is_set(visited, idx)) { + for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { + ir_node *irn = c->n[idx]; + if (! bitset_is_set(visited, get_irn_idx(irn))) { aff_chunk_t *new_chunk = new_aff_chunk(env); - ir_node *irn = get_idx_irn(env->co->irg, idx); co_mst_irn_t *node = get_co_mst_irn(env, irn); expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0); @@ -1054,13 +1209,14 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { delete_aff_chunk(env, best_chunk); bitset_free(visited); del_waitq(changed_ones); + if (best_starts) + del_waitq(best_starts); } /** * Main driver for mst safe coalescing algorithm. */ -int co_solve_heuristic_mst(copy_opt_t *co) -{ +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 k; @@ -1073,7 +1229,6 @@ int co_solve_heuristic_mst(copy_opt_t *co) k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs); k = n_regs - k; - FIRM_DBG_REGISTER(mst_env.dbg, "firm.be.co.heur4"); mst_env.n_regs = n_regs; mst_env.k = k; mst_env.chunks = new_pqueue(); @@ -1081,9 +1236,9 @@ int co_solve_heuristic_mst(copy_opt_t *co) mst_env.ignore_regs = ignore_regs; mst_env.ifg = co->cenv->ifg; mst_env.aenv = co->aenv; - pset_new_init(&mst_env.chunkset); + mst_env.chunkset = pset_new_ptr(512); - DBG((mst_env.dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name)); + DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name)); /* build affinity chunks */ build_affinity_chunks(&mst_env); @@ -1093,7 +1248,7 @@ int co_solve_heuristic_mst(copy_opt_t *co) aff_chunk_t *chunk = pqueue_get(mst_env.chunks); color_aff_chunk(&mst_env, chunk); - DB((mst_env.dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id)); + DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id)); delete_aff_chunk(&mst_env, chunk); } @@ -1113,13 +1268,19 @@ int co_solve_heuristic_mst(copy_opt_t *co) reg = arch_register_for_index(co->cls, mirn->col); arch_set_irn_register(co->aenv, irn, reg); - DB((mst_env.dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col)); + DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col)); } /* free allocated memory */ del_pqueue(mst_env.chunks); phase_free(&mst_env.ph); - pset_new_destroy(&mst_env.chunkset); + del_pset(mst_env.chunkset); return 0; } + +void be_init_copyheur4(void) { + FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4"); +} + +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);