X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur4.c;h=e9d20a3f5d55b3c46a5d47db7da098d15b6422c9;hb=15f5fef710e24321a27905b26a5dc1fcbabd9b1f;hp=f29518bb8703b2d7e844d3060715024f145b28f6;hpb=d0e3ab9bf6e64126fb173cbfed6f29a6be171053;p=libfirm diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c index f29518bb8..e9d20a3f5 100644 --- a/ir/be/becopyheur4.c +++ b/ir/be/becopyheur4.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -33,6 +33,8 @@ #include "config.h" #endif /* HAVE_CONFIG_H */ +#define DISABLE_STATEV + #include #include "array.h" @@ -48,6 +50,7 @@ #include "irbitset.h" #include "error.h" #include "list.h" +#include "statev.h" #include "irbitset.h" @@ -77,34 +80,39 @@ static firm_dbg_module_t *dbg = NULL; #endif -static int last_chunk_id = 0; -static int recolor_limit = 4; +typedef float real_t; +#define REAL(C) (C ## f) + +static unsigned last_chunk_id = 0; +static int recolor_limit = 7; +static real_t dislike_influence = REAL(0.1); typedef struct _col_cost_t { - int col; - double cost; + int col; + real_t cost; } col_cost_t; /** * An affinity chunk. */ typedef struct _aff_chunk_t { - 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. */ + const ir_node **n; /**< An ARR_F containing all nodes of the chunk. */ + 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. */ + unsigned id; /**< An id of this chunk. */ + unsigned visited; + col_cost_t color_affinity[1]; } aff_chunk_t; /** * An affinity edge. */ typedef struct _aff_edge_t { - ir_node *src; /**< Source node. */ - ir_node *tgt; /**< Target node. */ - double weight; /**< The weight of this edge. */ + const ir_node *src; /**< Source node. */ + const ir_node *tgt; /**< Target node. */ + int weight; /**< The weight of this edge. */ } aff_edge_t; /* main coalescing environment */ @@ -113,16 +121,18 @@ 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 */ + unsigned chunk_visited; + col_cost_t **single_cols; } co_mst_env_t; /* stores coalescing related information for a node */ typedef struct _co_mst_irn_t { - ir_node *irn; /**< the irn this information belongs to */ + const 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; /**< array of all interfering neighbours (cached for speed reasons) */ @@ -133,6 +143,7 @@ typedef struct _co_mst_irn_t { int tmp_col; /**< a temporary assigned color */ unsigned fixed : 1; /**< the color is fixed */ struct list_head list; /**< Queue for coloring undo. */ + real_t constr_factor; } co_mst_irn_t; #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn))) @@ -145,12 +156,13 @@ typedef int decide_func_t(const co_mst_irn_t *node, int col); * Write a chunk to stderr for debugging. */ static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) { - bitset_pos_t idx; + int i, l; + (void) env; if (c->weight_consistent) ir_fprintf(stderr, " $%d ", c->weight); ir_fprintf(stderr, "{"); - bitset_foreach(c->nodes, idx) { - ir_node *n = get_idx_irn(env->co->irg, idx); + for (i = 0, l = ARR_LEN(c->n); i < l; ++i) { + const ir_node *n = c->n[i]; ir_fprintf(stderr, " %+F,", n); } ir_fprintf(stderr, "}"); @@ -166,8 +178,9 @@ static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *n if (bitset_popcnt(node->adm_colors) < 1) fprintf(stderr, "no admissible colors?!?"); else { - bitset_foreach(node->adm_colors, idx) + bitset_foreach(node->adm_colors, idx) { fprintf(stderr, " %d", idx); + } } } @@ -176,12 +189,8 @@ static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *n */ 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) - fprintf(stderr, " (%d, INF)", cost[i].col); - else - fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost); - } + for (i = 0; i < env->n_regs; ++i) + fprintf(stderr, " (%d, %.4f)", cost[i].col, cost[i].cost); } #endif /* DEBUG_libfirm */ @@ -229,10 +238,17 @@ static int cmp_aff_edge(const void *a, const void *b) { } /** compares to color-cost pairs */ -static int cmp_col_cost(const void *a, const void *b) { +static __attribute__((unused)) int cmp_col_cost_lt(const void *a, const void *b) { const col_cost_t *c1 = a; const col_cost_t *c2 = b; - double diff = c1->cost - c2->cost; + real_t diff = c1->cost - c2->cost; + return (diff > 0) - (diff < 0); +} + +static int cmp_col_cost_gt(const void *a, const void *b) { + const col_cost_t *c1 = a; + const col_cost_t *c2 = b; + real_t diff = c2->cost - c1->cost; return (diff > 0) - (diff < 0); } @@ -240,13 +256,14 @@ static int cmp_col_cost(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)); + aff_chunk_t *c = xmalloc(sizeof(*c) + (env->n_regs - 1) * sizeof(c->color_affinity[0])); + c->n = NEW_ARR_F(const ir_node *, 0); + c->interfere = NEW_ARR_F(const ir_node *, 0); 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++; + c->deleted = 0; + c->id = ++last_chunk_id; + c->visited = 0; pset_insert(env->chunkset, c, c->id); return c; } @@ -256,42 +273,93 @@ static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) { */ static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { pset_remove(env->chunkset, c, c->id); - bitset_free(c->nodes); - bitset_free(c->interfere); + DEL_ARR_F(c->interfere); DEL_ARR_F(c->n); c->deleted = 1; free(c); } +/** + * binary search of sorted nodes. + * + * @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) { + int hi = ARR_LEN(arr); + int lo = 0; + + while (lo < hi) { + int md = lo + ((hi - lo) >> 1); + + if (arr[md] == n) + return md; + if (arr[md] < n) + lo = md + 1; + else + hi = md; + } + + return ~lo; +} + +/** Check if a node n can be found inside arr. */ +static int node_contains(const ir_node **arr, const ir_node *n) { + int i = nodes_bsearch(arr, n); + return i >= 0; +} + +/** + * Insert a node into the sorted nodes list. + * + * @return 1 if the node was inserted, 0 else + */ +static int nodes_insert(const ir_node ***arr, const ir_node *irn) { + int idx = nodes_bsearch(*arr, irn); + + if (idx < 0) { + int i, n = ARR_LEN(*arr); + const ir_node **l; + + ARR_APP1(const ir_node *, *arr, irn); + + /* move it */ + idx = ~idx; + l = *arr; + for (i = n - 1; i >= idx; --i) + l[i + 1] = l[i]; + l[idx] = irn; + return 1; + } + return 0; +} + /** * 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))) + if (! nodes_insert(&c->n, 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)); + nodes_insert(&c->interfere, neigh); } } /** * In case there is no phase information for irn, initialize it. */ -static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) { +static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old) { co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0])); co_mst_env_t *env = ph->priv; - if (res != old) { + if (!old) { const arch_register_req_t *req; void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg); ir_node *neigh; @@ -322,6 +390,9 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) { /* exclude global ignore registers as well */ bitset_andnot(res->adm_colors, env->ignore_regs); + /* compute the constraint factor */ + res->constr_factor = (real_t) (1 + env->n_regs - bitset_popcnt(res->adm_colors)) / env->n_regs; + /* set the number of interfering affinity neighbours to -1, they are calculated later */ res->int_aff_neigh = -1; @@ -342,32 +413,37 @@ 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, const aff_chunk_t *chunk, ir_node *irn) { - (void) env; - return bitset_is_set(chunk->interfere, get_irn_idx(irn)); +static INLINE int aff_chunk_interferes(const aff_chunk_t *chunk, const ir_node *irn) { + return node_contains(chunk->interfere, irn); } /** * Check if there are interference edges from c1 to c2. - * @param env The global co_mst environment * @param c1 A chunk * @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, const aff_chunk_t *c1, const aff_chunk_t *c2) { - (void) env; +static INLINE int aff_chunks_interfere(const aff_chunk_t *c1, const aff_chunk_t *c2) { + int i; + if (c1 == c2) return 0; /* check if there is a node in c2 having an interfering neighbor in c1 */ - return bitset_intersect(c1->interfere, c2->nodes); + for (i = ARR_LEN(c2->n) - 1; i >= 0; --i) { + const ir_node *irn = c2->n[i]; + + if (node_contains(c1->interfere, irn)) + return 1; + } + 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) { +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; } @@ -377,18 +453,18 @@ static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) { * 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, ir_node *src, ir_node *tgt) { +static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node *tgt) { aff_chunk_t *c1 = get_aff_chunk(env, src); 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 { @@ -416,32 +492,28 @@ static int aff_chunk_absorb(co_mst_env_t *env, ir_node *src, ir_node *tgt) { } } else { /* c2 already exists */ - if (! aff_chunk_interferes(env, c2, src)) { + if (! aff_chunk_interferes(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)) { + if (! aff_chunk_interferes(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)) { + } else if (c1 != c2 && ! aff_chunks_interfere(c1, c2)) { int idx, len; - 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); + for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx) + aff_chunk_add_node(c1, get_co_mst_irn(env, c2->n[idx])); - mn->chunk = c1; - - if (! bitset_is_set(c1->nodes, get_irn_idx(n))) - ARR_APP1(ir_node *, c1->n, n); + for (idx = 0, len = ARR_LEN(c2->interfere); idx < len; ++idx) { + const ir_node *irn = c2->interfere[idx]; + nodes_insert(&c1->interfere, irn); } - bitset_or(c1->nodes, c2->nodes); - bitset_or(c1->interfere, c2->interfere); c1->weight_consistent = 0; delete_aff_chunk(env, c2); @@ -461,40 +533,44 @@ absorbed: static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) { if (! c->weight_consistent) { int w = 0; - int idx, len; - double ratio = 0.0; - int n_constr = 0; + int idx, len, i; + + for (i = 0; i < env->n_regs; ++i) { + c->color_affinity[i].col = i; + c->color_affinity[i].cost = REAL(0.0); + } for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { - ir_node *n = c->n[idx]; + const ir_node *n = c->n[idx]; const affinity_node_t *an = get_affinity_info(env->co, n); co_mst_irn_t *node = get_co_mst_irn(env, n); - int col_cnt = bitset_popcnt(node->adm_colors); - if (col_cnt < env->k) { - /* calculate costs for constrained interfering neighbors */ - ratio += 1.0 - (double) col_cnt / env->k; - n_constr += 1; + node->chunk = c; + if (node->constr_factor > REAL(0.0)) { + bitset_pos_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; - const int m_idx = get_irn_idx(m); /* skip ignore nodes */ if (arch_irn_is(env->aenv, m, ignore)) continue; - w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0; + w += node_contains(c->n, m) ? neigh->costs : 0; } } } - w *= 1.0 + (double) n_constr / ARR_LEN(c->n) * ratio; + for (i = 0; i < env->n_regs; ++i) + c->color_affinity[i].cost *= (REAL(1.0) / ARR_LEN(c->n)); c->weight = w; + // c->weight = bitset_popcnt(c->nodes); c->weight_consistent = 1; } } @@ -504,7 +580,7 @@ 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; - ir_node *irn = an->irn; + const ir_node *irn = an->irn; const co_mst_irn_t *node = get_co_mst_irn(env, irn); int res = 0; @@ -563,8 +639,8 @@ static void build_affinity_chunks(co_mst_env_t *env) { /* build the affinity edges */ co_gs_foreach_neighb(an, neigh) { - ir_node *m = neigh->irn; - int m_idx = get_irn_idx(m); + const ir_node *m = neigh->irn; + int m_idx = get_irn_idx(m); /* record the edge in only one direction */ if (n_idx < m_idx) { @@ -587,7 +663,7 @@ static void build_affinity_chunks(co_mst_env_t *env) { * these weights are pure hackery ;-). * It's not chriswue's fault but mine. */ - edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh); + edge.weight = neigh->costs; ARR_APP1(aff_edge_t, edges, edge); } } @@ -607,12 +683,13 @@ 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")); 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); @@ -623,7 +700,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")); @@ -634,16 +711,16 @@ static void build_affinity_chunks(co_mst_env_t *env) { DEL_ARR_F(edges); } -static void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk) +static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk) { - pqueue *grow = new_pqueue(); - int i; + pqueue_t *grow = new_pqueue(); + const ir_node *max_node = NULL; int max_weight = 0; - ir_node *max_node = NULL; + int i; for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) { - ir_node *irn = chunk->n[i]; - affinity_node_t *an = get_affinity_info(env->co, irn); + const ir_node *irn = chunk->n[i]; + affinity_node_t *an = get_affinity_info(env->co, irn); int w = 0; neighb_t *neigh; @@ -667,11 +744,11 @@ static void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk) for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i) bitset_add_irn(visited, chunk->n[i]); - pqueue_put(grow, max_node, max_weight); + pqueue_put(grow, (void *) max_node, max_weight); 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; @@ -688,7 +765,7 @@ static void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk) co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn); if (bitset_contains_irn(visited, node->irn)) { - pqueue_put(grow, neigh->irn, neigh->costs); + pqueue_put(grow, (void *) neigh->irn, neigh->costs); bitset_remv_irn(visited, node->irn); } } @@ -707,7 +784,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); @@ -724,8 +801,8 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v 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; + int m_idx = get_irn_idx(m); co_mst_irn_t *n2; /* skip ignore nodes */ @@ -734,11 +811,11 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v n2 = get_co_mst_irn(env, m); - if (! bitset_is_set(visited, m_idx) && - decider(n2, col) && - ! n2->fixed && - ! aff_chunk_interferes(env, chunk, m) && - bitset_is_set(orig_chunk->nodes, m_idx)) + if (! bitset_is_set(visited, m_idx) && + decider(n2, col) && + ! n2->fixed && + ! aff_chunk_interferes(chunk, m) && + node_contains(orig_chunk->n, m)) { /* following conditions are met: @@ -772,7 +849,7 @@ static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, w aff_chunk_t *best = NULL; for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { - ir_node *irn; + const ir_node *irn; co_mst_irn_t *node; aff_chunk_t *tmp_chunk; decide_func_t *decider; @@ -787,19 +864,19 @@ 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 */ tmp_chunk = new_aff_chunk(env); waitq_put(tmp, tmp_chunk); expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col); - assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk"); + assert(ARR_LEN(tmp_chunk->n) > 0 && "No nodes added to chunk"); /* remember the local best */ aff_chunk_assure_weight(env, tmp_chunk); @@ -812,34 +889,6 @@ static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, w return best; } -/** - * Initializes an array of color-cost pairs. - * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c. - */ -static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) { - int i; - - for (i = 0; i < env->n_regs; ++i) { - cost[i].col = i; - if (bitset_is_set(env->ignore_regs, i)) - cost[i].cost = COL_COST_INFEASIBLE; - else - cost[i].cost = c; - } -} - -/** - * Initializes an array of color-cost pairs. - * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0 - */ -static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) { - assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color."); - col_cost_init(env, cost, COL_COST_INFEASIBLE); - cost[col].col = 0; - cost[0].col = col; - cost[0].cost = 0.0; -} - /** * Resets the temporary fixed color of all nodes within wait queue @p nodes. * ATTENTION: the queue is empty after calling this function! @@ -872,6 +921,7 @@ static INLINE void set_temp_color(co_mst_irn_t *node, int col, struct list_head assert(!node->fixed); assert(node->tmp_col < 0); assert(node->list.next == &node->list && node->list.prev == &node->list); + assert(bitset_is_set(node->adm_colors, col)); list_add_tail(&node->list, changed); node->tmp_col = col; @@ -886,88 +936,49 @@ 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) { - affinity_node_t *an = get_affinity_info(env->co, node->irn); - neighb_t *aff_neigh; - bitset_pos_t idx; - int i; - - col_cost_init(env, costs, 0.0); - - /* calculate (negative) costs for affinity neighbours */ - if (an != NULL) { - co_gs_foreach_neighb(an, aff_neigh) { - ir_node *m = aff_neigh->irn; - co_mst_irn_t *neigh; - double c; - - /* skip ignore nodes */ - if (arch_irn_is(env->aenv, m, ignore)) - continue; - - neigh = get_co_mst_irn(env, m); - c = (double)aff_neigh->costs; + int *neigh_cols = alloca(env->n_regs * sizeof(*neigh_cols)); + int n_loose = 0; + real_t coeff; + int i; - /* calculate costs for fixed affinity neighbours */ - if (!is_loose(neigh)) { - int col = get_mst_irn_col(neigh); - costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT; - } - } + for (i = 0; i < env->n_regs; ++i) { + neigh_cols[i] = 0; + costs[i].col = i; + costs[i].cost = bitset_is_set(node->adm_colors, i) ? node->constr_factor : REAL(0.0); } - /* calculate (positive) costs for interfering neighbours */ for (i = 0; i < node->n_neighs; ++i) { - co_mst_irn_t *neigh; - int col, col_cnt; - ir_node *int_neigh; - - int_neigh = node->int_neighs[i]; - - assert(!arch_irn_is(env->aenv, int_neigh, ignore)); - - neigh = get_co_mst_irn(env, int_neigh); - col = get_mst_irn_col(neigh); - col_cnt = bitset_popcnt(neigh->adm_colors); - - if (!is_loose(neigh)) { - /* colors of fixed interfering neighbours are infeasible */ - costs[col].cost = COL_COST_INFEASIBLE; - } - else if (col_cnt < env->k) { - /* calculate costs for constrained interfering neighbours */ - double ratio = 1.0 - ((double)col_cnt / (double)env->k); - - bitset_foreach_clear(neigh->adm_colors, idx) { - /* check only explicitly forbidden colors (skip global forbidden ones) */ - if (! bitset_is_set(env->ignore_regs, idx)) { - costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS; - } - } - } - - DB((dbg, LEVEL_4, "\tneigh %+F, loose: %d, color: %d\n", int_neigh, is_loose(neigh), col)); + co_mst_irn_t *n = get_co_mst_irn(env, node->int_neighs[i]); + int col = get_mst_irn_col(n); + if (is_loose(n)) { + ++n_loose; + ++neigh_cols[col]; + } else + costs[col].cost = REAL(0.0); } - /* set all not admissible colors to COL_COST_INFEASIBLE */ - bitset_foreach_clear(node->adm_colors, idx) - costs[idx].cost = COL_COST_INFEASIBLE; + if (n_loose > 0) { + coeff = REAL(1.0) / n_loose; + for (i = 0; i < env->n_regs; ++i) + costs[i].cost *= REAL(1.0) - coeff * neigh_cols[i]; + } } /* need forward declaration due to recursive call */ -static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones, int depth); +static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones, int depth, int *max_depth, int *trip); /** * Tries to change node to a color but @p explude_col. * @return 1 if succeeded, 0 otherwise. */ -static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, struct list_head *changed_ones, int depth) { +static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, struct list_head *changed, int depth, int *max_depth, int *trip) { int col = get_mst_irn_col(node); int res = 0; /* neighbours has already a different color -> good, temporary fix it */ if (col != exclude_col) { if (is_loose(node)) - set_temp_color(node, col, changed_ones); + set_temp_color(node, col, changed); return 1; } @@ -979,13 +990,13 @@ static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int determine_color_costs(env, node, costs); /* Since the node must not have the not_col, set the costs for that color to "infinity" */ - costs[exclude_col].cost = COL_COST_INFEASIBLE; + costs[exclude_col].cost = REAL(0.0); /* sort the colors according costs, cheapest first. */ - qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost); + qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost_gt); /* Try recoloring the node using the color list. */ - res = recolor_nodes(env, node, costs, changed_ones, depth + 1); + res = recolor_nodes(env, node, costs, changed, depth + 1, max_depth, trip); } return res; @@ -996,16 +1007,22 @@ static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int * ATTENTION: Expect @p costs already sorted by increasing costs. * @return 1 if coloring could be applied, 0 otherwise. */ -static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones, int depth) { +static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed, int depth, int *max_depth, int *trip) { int i; struct list_head local_changed; - if (depth >= recolor_limit) - return 0; + ++*trip; + if (depth > *max_depth) + *max_depth = depth; - DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn)); - DBG_COL_COST(env, LEVEL_1, costs); - DB((dbg, LEVEL_1, "\n")); + 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; @@ -1013,7 +1030,8 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost 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 == COL_COST_INFEASIBLE) { + if (costs[i].cost == REAL(0.0)) { + DBG((dbg, LEVEL_4, "\tAll further colors forbidden\n")); return 0; } @@ -1046,7 +1064,7 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost */ if (get_mst_irn_col(nn) == tgt_col) { /* try to color neighbour with tgt_col forbidden */ - neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed, depth + 1); + neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed, depth + 1, max_depth, trip); if (!neigh_ok) break; @@ -1059,7 +1077,7 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost */ if (neigh_ok) { /* append the local_changed ones to global ones */ - list_splice(&local_changed, changed_ones); + list_splice(&local_changed, changed); return 1; } else { @@ -1068,6 +1086,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; } @@ -1075,14 +1094,14 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost * Tries to bring node @p node and all it's neighbours to color @p tgt_col. * @return 1 if color @p col could be applied, 0 otherwise */ -static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed_ones, int depth) { +static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed) { int col = get_mst_irn_col(node); /* if node already has the target color -> good, temporary fix it */ if (col == tgt_col) { DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col)); if (is_loose(node)) - set_temp_color(node, tgt_col, changed_ones); + set_temp_color(node, tgt_col, changed); return 1; } @@ -1091,14 +1110,18 @@ static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, -> try to recolor node and it's affinity neighbours */ if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) { - col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0])); - int res; + col_cost_t *costs = env->single_cols[tgt_col]; + int res, max_depth, trip; - col_cost_init_single(env, costs, tgt_col); + max_depth = 0; + trip = 0; DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn)); - res = recolor_nodes(env, node, costs, changed_ones, depth); + res = recolor_nodes(env, node, costs, changed, 0, &max_depth, &trip); DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed")); + stat_ev_int("heur4_recolor_depth_max", max_depth); + stat_ev_int("heur4_recolor_trip", trip); + return res; } @@ -1124,19 +1147,53 @@ 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 n_nodes = ARR_LEN(c->n); int best_color = -1; - int did_all = 0; + 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])); bitset_t *visited; - int col, idx, len; - struct list_head changed_ones; + 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")); - chunk_order_nodes(env, c); + 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); + aff_chunk_t *chunk = node->chunk; + + if (is_loose(node) && chunk && chunk->visited < env->chunk_visited) { + assert(!chunk->deleted); + chunk->visited = env->chunk_visited; + ++n_int_chunks; + + aff_chunk_assure_weight(env, chunk); + for (i = 0; i < env->n_regs; ++i) + order[i].cost += chunk->color_affinity[i].cost; + } + } + + for (i = 0; i < env->n_regs; ++i) { + real_t dislike = n_int_chunks > 0 ? REAL(1.0) - order[i].cost / n_int_chunks : REAL(0.0); + order[i].col = i; + order[i].cost = (REAL(1.0) - dislike_influence) * c->color_affinity[i].cost + dislike_influence * dislike; + } + + qsort(order, env->n_regs, sizeof(order[0]), cmp_col_cost_gt); + + DBG_COL_COST(env, LEVEL_2, order); + 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 @@ -1146,27 +1203,25 @@ 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 (col = 0; col < env->n_regs && !did_all; ++col) { - int one_good = 0; + for (i = 0; i < env->k; ++i) { + int col = order[i].col; waitq *good_starts = new_waitq(); aff_chunk_t *local_best; + int n_succeeded; /* skip ignore colors */ if (bitset_is_set(env->ignore_regs, col)) continue; - DB((dbg, LEVEL_3, "\ttrying color %d\n", col)); - - /* suppose we can color all nodes to the same color */ - did_all = 1; + DB((dbg, LEVEL_2, "\ttrying color %d\n", col)); - INIT_LIST_HEAD(&changed_ones); + n_succeeded = 0; /* try to bring all nodes of given chunk to the current color. */ 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; + const ir_node *irn = c->n[idx]; + co_mst_irn_t *node = get_co_mst_irn(env, irn); + int good; 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)); @@ -1175,22 +1230,32 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { 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, 0); + INIT_LIST_HEAD(&changed); + stat_ev_tim_push(); + good = change_node_color(env, node, col, &changed); + stat_ev_tim_pop("heur4_recolor"); if (good) { waitq_put(good_starts, node); + materialize_coloring(&changed); + node->fixed = 1; } - one_good |= good; - did_all &= good; + else + reject_coloring(&changed); - DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed")); + n_succeeded += good; + DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, good ? "succeeded" : "failed")); + } + + /* unfix all nodes */ + for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { + co_mst_irn_t *node = get_co_mst_irn(env, c->n[idx]); + node->fixed = 0; } /* try next color when failed */ - if (! one_good) { - reject_coloring(&changed_ones); + if (n_succeeded == 0) continue; - } /* fragment the chunk according to the coloring */ local_best = fragment_chunk(env, col, c, tmp_chunks); @@ -1200,8 +1265,8 @@ 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_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col)); - DBG_AFF_CHUNK(env, LEVEL_4, local_best); + 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) { best_chunk = local_best; @@ -1209,9 +1274,9 @@ 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_4, "\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_4, "\n\t\t... omitting, global best is better\n")); + DB((dbg, LEVEL_3, "\n\t\t... omitting, global best is better\n")); del_waitq(good_starts); } } @@ -1219,9 +1284,13 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { del_waitq(good_starts); } - reject_coloring(&changed_ones); + /* if all nodes were recolored, bail out */ + if (n_succeeded == n_nodes) + break; } + stat_ev_int("heur4_colors_tried", i); + /* free all intermediate created chunks except best one */ while (! waitq_empty(tmp_chunks)) { aff_chunk_t *tmp = waitq_get(tmp_chunks); @@ -1237,52 +1306,62 @@ 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)); - INIT_LIST_HEAD(&changed_ones); 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); + const ir_node *irn = best_chunk->n[idx]; + co_mst_irn_t *node = get_co_mst_irn(env, irn); 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)); - INIT_LIST_HEAD(&changed_ones); - res = change_node_color(env, node, best_color, &changed_ones, 0); + 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); + stat_ev_tim_pop("heur4_recolor"); if (res) { - materialize_coloring(&changed_ones); + materialize_coloring(&changed); node->fixed = 1; } + assert(list_empty(&changed)); } /* 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]; + len = ARR_LEN(best_chunk->n); + for (idx = 0; idx < len; ++idx) { + const ir_node *irn = best_chunk->n[idx]; + int pos = nodes_bsearch(c->n, irn); - if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) { - int last = ARR_LEN(c->n) - 1; + if (pos > 0) + c->n[pos] = NULL; + } + len = ARR_LEN(c->n); + for (idx = nidx = 0; idx < len; ++idx) { + const ir_node *irn = c->n[idx]; - c->n[idx] = c->n[last]; - ARR_SHRINKLEN(c->n, last); - len--; + if (irn != NULL) { + c->n[nidx++] = irn; } } + ARR_SHRINKLEN(c->n, nidx); + /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */ 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); + const ir_node *n = c->n[idx]; + co_mst_irn_t *nn = get_co_mst_irn(env, n); nn->chunk = c; } /* fragment the remaining chunk */ visited = bitset_irg_malloc(env->co->irg); - bitset_or(visited, best_chunk->nodes); + for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) + bitset_set(visited, get_irn_idx(best_chunk->n[idx])); + for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) { - ir_node *irn = c->n[idx]; + const ir_node *irn = c->n[idx]; if (! bitset_is_set(visited, get_irn_idx(irn))) { aff_chunk_t *new_chunk = new_aff_chunk(env); co_mst_irn_t *node = get_co_mst_irn(env, irn); @@ -1293,11 +1372,19 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { } } + for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) { + const ir_node *n = best_chunk->n[idx]; + co_mst_irn_t *nn = get_co_mst_irn(env, n); + nn->chunk = NULL; + } + /* clear obsolete chunks and free some memory */ delete_aff_chunk(env, best_chunk); bitset_free(visited); if (best_starts) del_waitq(best_starts); + + stat_ev_ctx_pop("heur4_color_chunk"); } /** @@ -1306,47 +1393,69 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { 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; + unsigned i, j, k; ir_node *irn; co_mst_env_t mst_env; + last_chunk_id = 0; + + stat_ev_tim_push(); + /* init phase */ phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env); k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs); k = n_regs - k; - mst_env.n_regs = n_regs; - mst_env.k = k; - mst_env.chunks = new_pqueue(); - 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.n_regs = n_regs; + mst_env.k = k; + mst_env.chunks = new_pqueue(); + 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); + + for (i = 0; i < n_regs; ++i) { + col_cost_t *vec = phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs); + + mst_env.single_cols[i] = vec; + for (j = 0; j < n_regs; ++j) { + vec[j].col = j; + vec[j].cost = REAL(0.0); + } + vec[i].col = 0; + vec[0].col = i; + vec[0].cost = REAL(1.0); + } DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name)); /* build affinity chunks */ + stat_ev_tim_push(); build_affinity_chunks(&mst_env); + stat_ev_tim_pop("heur4_initial_chunk"); /* 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 = get_co_mst_irn(&mst_env, irn); + co_mst_irn_t *mirn; const arch_register_t *reg; if (arch_irn_is(mst_env.aenv, irn, ignore)) continue; + mirn = get_co_mst_irn(&mst_env, irn); // assert(mirn->fixed && "Node should have fixed color"); /* skip nodes where color hasn't changed */ @@ -1363,11 +1472,14 @@ int co_solve_heuristic_mst(copy_opt_t *co) { phase_free(&mst_env.ph); del_pset(mst_env.chunkset); + stat_ev_tim_pop("heur4_total"); + return 0; } static const lc_opt_table_entry_t options[] = { - LC_OPT_ENT_INT ("limit", "limit recoloring", &recolor_limit), + LC_OPT_ENT_INT ("limit", "limit recoloring", &recolor_limit), + LC_OPT_ENT_DBL ("di", "dislike influence", &dislike_influence), LC_OPT_LAST }; @@ -1383,4 +1495,5 @@ void be_init_copyheur4(void) { FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4"); } + BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);