X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur4.c;h=c95106b7f907e3efbdd2ee0b075bccbbd6bf8166;hb=505d3662efed6efbca2c43eea2fe23b87816b285;hp=ee2926d99485331f23878514438746148528c070;hpb=89af99b9c92c524c11d3d8f297f4f3277af9b8d5;p=libfirm diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c index ee2926d99..c95106b7f 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. * @@ -47,6 +47,10 @@ #include "irprintf.h" #include "irbitset.h" #include "error.h" +#include "list.h" +#include "statev.h" + +#include "irbitset.h" #include "bearch.h" #include "beifg.h" @@ -59,45 +63,53 @@ #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0 #define NEIGHBOUR_CONSTR_COSTS 64.0 -#ifdef NDEBUG - -#define DBG_AFF_CHUNK(env, level, chunk) -#define DBG_COL_COST(env, level, cost) -#else +#ifdef DEBUG_libfirm -static firm_dbg_module_t *dbg = NULL; #define DBG_AFF_CHUNK(env, level, chunk) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while(0) #define DBG_COL_COST(env, level, cost) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while(0) +static firm_dbg_module_t *dbg = NULL; + +#else + +#define DBG_AFF_CHUNK(env, level, chunk) +#define DBG_COL_COST(env, level, cost) + #endif -static int last_chunk_id = 0; +typedef float real_t; +#define REAL(C) (C ## f) + +static int last_chunk_id = 0; +static int recolor_limit = 4; +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. */ + int id; /**< An id of this chunk. */ + int 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. */ + const ir_node *src; /**< Source node. */ + const ir_node *tgt; /**< Target node. */ double weight; /**< The weight of this edge. */ } aff_edge_t; @@ -112,21 +124,24 @@ typedef struct _co_mst_env_t { 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; + 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 */ - 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) */ - 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 */ - int tmp_col; /**< a temporary assigned color */ - unsigned fixed : 1; /**< the color is fixed */ - unsigned tmp_fixed : 1; /**< the color is temporary fixed */ + 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) */ + 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 */ + 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))) @@ -139,12 +154,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, "}"); @@ -160,8 +176,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); + } } } @@ -170,18 +187,14 @@ 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 */ static INLINE int get_mst_irn_col(const co_mst_irn_t *node) { - return node->tmp_fixed ? node->tmp_col : node->col; + return node->tmp_col >= 0 ? node->tmp_col : node->col; } /** @@ -223,24 +236,32 @@ 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; + real_t diff = c1->cost - c2->cost; + return (diff > 0) - (diff < 0); +} - return c1->cost < c2->cost ? -1 : 1; +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); } /** * 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; } @@ -250,42 +271,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; @@ -294,12 +366,12 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) { res->irn = irn; res->chunk = NULL; res->fixed = 0; - res->tmp_fixed = 0; res->tmp_col = -1; res->int_neighs = NULL; res->int_aff_neigh = 0; res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn)); res->init_col = res->col; + INIT_LIST_HEAD(&res->list); DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn)); @@ -316,6 +388,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; @@ -336,37 +411,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) { - bitset_t *tmp; +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 */ - tmp = bitset_alloca(get_irg_last_idx(env->co->irg)); - tmp = bitset_copy(tmp, c1->interfere); - tmp = bitset_and(tmp, c2->nodes); + for (i = ARR_LEN(c2->n) - 1; i >= 0; --i) { + const ir_node *irn = c2->n[i]; - return bitset_popcnt(tmp) > 0; + 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; } @@ -376,11 +451,11 @@ 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); -#ifndef NDEBUG +#ifdef DEBUG_libfirm DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1)); if (c1) { DBG_AFF_CHUNK(env, LEVEL_4, c1); @@ -415,32 +490,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); - - mn->chunk = c1; + for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx) + aff_chunk_add_node(c1, get_co_mst_irn(env, c2->n[idx])); - 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); @@ -457,31 +528,47 @@ absorbed: /** * Assures that the weight of the given chunk is consistent. */ -static void aff_chunk_assure_weight(const co_mst_env_t *env, aff_chunk_t *c) { +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; + 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 affinity_node_t *an = get_affinity_info(env->co, n); + 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); + + 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; } } } + 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; } } @@ -491,7 +578,7 @@ static void aff_chunk_assure_weight(const 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; @@ -550,8 +637,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) { @@ -574,7 +661,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); } } @@ -600,6 +687,7 @@ static void build_affinity_chunks(co_mst_env_t *env) { pqueue_put(env->chunks, curr_chunk, curr_chunk->weight); } + foreach_phase_irn(&env->ph, n) { co_mst_irn_t *mirn = get_co_mst_irn(env, n); @@ -621,6 +709,71 @@ static void build_affinity_chunks(co_mst_env_t *env) { DEL_ARR_F(edges); } +static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk) +{ + pqueue *grow = new_pqueue(); + const ir_node *max_node = NULL; + int max_weight = 0; + int i; + + for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) { + const ir_node *irn = chunk->n[i]; + affinity_node_t *an = get_affinity_info(env->co, irn); + int w = 0; + neighb_t *neigh; + + if (arch_irn_is(env->aenv, irn, ignore)) + continue; + + if (an) { + co_gs_foreach_neighb(an, neigh) + w += neigh->costs; + + if (w > max_weight) { + max_weight = w; + max_node = irn; + } + } + } + + if (max_node) { + bitset_t *visited = bitset_irg_malloc(env->co->irg); + + for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i) + bitset_add_irn(visited, chunk->n[i]); + + 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); + affinity_node_t *an = get_affinity_info(env->co, irn); + neighb_t *neigh; + + if (arch_irn_is(env->aenv, irn, ignore)) + continue; + + assert(i <= ARR_LEN(chunk->n)); + chunk->n[i++] = irn; + + assert(an); + + /* build the affinity edges */ + co_gs_foreach_neighb(an, neigh) { + co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn); + + if (bitset_contains_irn(visited, node->irn)) { + pqueue_put(grow, (void *) neigh->irn, neigh->costs); + bitset_remv_irn(visited, node->irn); + } + } + } + + del_pqueue(grow); + bitset_free(visited); + } +} + /** * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node. */ @@ -646,8 +799,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 */ @@ -656,11 +809,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: @@ -694,7 +847,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; @@ -721,7 +874,7 @@ static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, w 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); @@ -734,153 +887,114 @@ 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! */ -static INLINE void reject_coloring(waitq *nodes) { +static INLINE void reject_coloring(struct list_head *nodes) { + co_mst_irn_t *n, *temp; DB((dbg, LEVEL_4, "\treject coloring for")); - while (! waitq_empty(nodes)) { - co_mst_irn_t *n = waitq_get(nodes); + list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) { DB((dbg, LEVEL_4, " %+F", n->irn)); - n->tmp_fixed = 0; + assert(n->tmp_col >= 0); + n->tmp_col = -1; + list_del_init(&n->list); } DB((dbg, LEVEL_4, "\n")); } +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); + n->col = n->tmp_col; + n->tmp_col = -1; + list_del_init(&n->list); + } +} + +static INLINE void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed) +{ + assert(col >= 0); + 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; +} + +static INLINE int is_loose(co_mst_irn_t *node) +{ + return !node->fixed && node->tmp_col < 0; +} + /** * 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 (neigh->tmp_fixed || neigh->fixed) { - 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]; - - /* skip ignore nodes */ - if (arch_irn_is(env->aenv, int_neigh, ignore)) - continue; - - neigh = get_co_mst_irn(env, int_neigh); - col = get_mst_irn_col(neigh); - col_cnt = bitset_popcnt(neigh->adm_colors); - - if (neigh->tmp_fixed || neigh->fixed) { - /* 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; - } - } - } + 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, waitq *changed_ones); +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, waitq *changed_ones) { +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) { - node->tmp_fixed = 1; - node->tmp_col = col; - waitq_put(changed_ones, node); + if (is_loose(node)) + set_temp_color(node, col, changed); return 1; } /* The node has the color it should not have _and_ has not been visited yet. */ - if (! (node->tmp_fixed || node->fixed)) { + if (is_loose(node)) { col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0])); /* Get the costs for giving the node a specific color. */ 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); + res = recolor_nodes(env, node, costs, changed, depth + 1, max_depth, trip); } return res; @@ -891,14 +1005,20 @@ 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, waitq *changed_ones) { +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; - waitq *local_changed = new_waitq(); - waitq *tmp = new_waitq(); + struct list_head local_changed; - DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn)); - DBG_COL_COST(env, LEVEL_1, costs); - DB((dbg, LEVEL_1, "\n")); + ++*trip; + 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")); for (i = 0; i < env->n_regs; ++i) { int tgt_col = costs[i].col; @@ -906,22 +1026,15 @@ 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) { - node->tmp_fixed = 0; - del_waitq(local_changed); - del_waitq(tmp); + if (costs[i].cost == REAL(0.0)) return 0; - } /* Set the new color of the node and mark the node as temporarily fixed. */ - assert(! node->tmp_fixed && "Node must not have been temporary fixed."); - node->tmp_fixed = 1; - node->tmp_col = tgt_col; + assert(node->tmp_col < 0 && "Node must not have been temporary fixed."); + INIT_LIST_HEAD(&local_changed); + set_temp_color(node, tgt_col, &local_changed); 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 < node->n_neighs; ++j) { co_mst_irn_t *nn; @@ -934,8 +1047,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)); + DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_col: %d, col: %d)\n", + neigh, j, nn->fixed, nn->tmp_col, nn->col)); /* Try to change the color of the neighbor and record all nodes which @@ -945,13 +1058,9 @@ 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, tmp); + neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed, depth + 1, max_depth, trip); - /* join lists of changed nodes */ - while (! waitq_empty(tmp)) - waitq_put(local_changed, waitq_get(tmp)); - - if (! neigh_ok) + if (!neigh_ok) break; } } @@ -962,20 +1071,15 @@ 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 */ - while (! waitq_empty(local_changed)) - waitq_put(changed_ones, waitq_get(local_changed)); - del_waitq(local_changed); - del_waitq(tmp); + list_splice(&local_changed, changed); return 1; } else { /* coloring of neighbours failed, so we try next color */ - reject_coloring(local_changed); + reject_coloring(&local_changed); } } - del_waitq(local_changed); - del_waitq(tmp); return 0; } @@ -983,17 +1087,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, waitq *changed_ones) { +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 (! node->tmp_fixed) { - node->tmp_fixed = 1; - node->tmp_col = tgt_col; - waitq_put(changed_ones, node); - } + if (is_loose(node)) + set_temp_color(node, tgt_col, changed); return 1; } @@ -1001,22 +1102,26 @@ static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, Node has not yet a fixed color and target color is admissible -> try to recolor node and it's affinity neighbours */ - if (! (node->fixed || node->tmp_fixed) && bitset_is_set(node->adm_colors, tgt_col)) { - col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0])); - int res; + if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) { + 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); + 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; } -#ifndef NDEBUG +#ifdef DEBUG_libfirm if (firm_dbg_get_mask(dbg) & LEVEL_4) { - if (node->fixed || node->tmp_fixed) + if (!is_loose(node)) DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col)); else { DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn)); @@ -1035,18 +1140,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; - waitq *changed_ones = new_waitq(); + 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; + int idx, len, i, nidx, pos; + struct list_head changed; DB((dbg, LEVEL_2, "fragmentizing chunk #%d", 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); + + ++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 @@ -1056,25 +1196,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)); + DB((dbg, LEVEL_2, "\ttrying color %d\n", col)); - /* suppose we can color all nodes to the same color */ - did_all = 1; + 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)); @@ -1083,17 +1223,31 @@ 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); - if (good) + 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); - one_good |= good; - did_all &= good; + materialize_coloring(&changed); + node->fixed = 1; + } + + else + reject_coloring(&changed); + + n_succeeded += good; + DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, good ? "succeeded" : "failed")); + } - DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_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) + if (n_succeeded == 0) continue; /* fragment the chunk according to the coloring */ @@ -1104,8 +1258,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 %d) 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; @@ -1113,9 +1267,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 %d), 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); } } @@ -1123,10 +1277,13 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { del_waitq(good_starts); } - /* reject the coloring and bring the coloring to the initial state */ - 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); @@ -1137,7 +1294,6 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { /* return if coloring failed */ if (! best_chunk) { - del_waitq(changed_ones); if (best_starts) del_waitq(best_starts); return; @@ -1147,67 +1303,58 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) { DBG_AFF_CHUNK(env, LEVEL_2, best_chunk); DB((dbg, LEVEL_2, "using color %d\n", best_color)); - /* get the best fragment from the best list and color it */ - 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); - 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; - } - - /* materialize colors on changed nodes */ - while (! waitq_empty(changed_ones)) { - co_mst_irn_t *n = waitq_get(changed_ones); - n->tmp_fixed = 0; - n->col = n->tmp_col; + 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); + stat_ev_tim_push(); + res = change_node_color(env, node, best_color, &changed); + stat_ev_tim_pop("heur4_recolor"); + if (res) { + 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); @@ -1218,12 +1365,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); - del_waitq(changed_ones); if (best_starts) del_waitq(best_starts); + + stat_ev_ctx_pop("heur4_color_chunk"); } /** @@ -1232,29 +1386,48 @@ 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; + 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)) { @@ -1267,13 +1440,14 @@ int co_solve_heuristic_mst(copy_opt_t *co) { /* 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; - assert(mirn->fixed && "Node should have fixed color"); + mirn = get_co_mst_irn(&mst_env, irn); + // assert(mirn->fixed && "Node should have fixed color"); /* skip nodes where color hasn't changed */ if (mirn->init_col == mirn->col) @@ -1289,11 +1463,28 @@ 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_DBL ("di", "dislike influence", &dislike_influence), + LC_OPT_LAST +}; + + void be_init_copyheur4(void) { + lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); + lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra"); + lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal"); + lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co"); + lc_opt_entry_t *heur4_grp = lc_opt_get_grp(co_grp, "heur4"); + + lc_opt_add_table(heur4_grp, options); FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4"); } + BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);