#include "error.h"
#include "list.h"
+#include "irbitset.h"
+
#include "bearch.h"
#include "beifg.h"
#include "be_t.h"
#define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
#define NEIGHBOUR_CONSTR_COSTS 64.0
-DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
-#ifdef NDEBUG
+#ifdef DEBUG_libfirm
-#define DBG_AFF_CHUNK(env, level, chunk)
-#define DBG_COL_COST(env, level, cost)
+#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) 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)
+#define DBG_AFF_CHUNK(env, level, chunk)
+#define DBG_COL_COST(env, level, cost)
#endif
static int last_chunk_id = 0;
+static int recolor_limit = 4;
typedef struct _col_cost_t {
int col;
* 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. */
+ 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. */
+ col_cost_t *color_affinity;
} aff_chunk_t;
/**
int tmp_col; /**< a temporary assigned color */
unsigned fixed : 1; /**< the color is fixed */
struct list_head list; /**< Queue for coloring undo. */
+ double constr_factor;
} co_mst_irn_t;
#define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
static int cmp_col_cost(const void *a, const void *b) {
const col_cost_t *c1 = a;
const col_cost_t *c2 = b;
-
- return c1->cost < c2->cost ? -1 : 1;
+ double diff = c1->cost - c2->cost;
+ return (diff > 0) - (diff < 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->color_affinity = xmalloc(env->k * sizeof(c->color_affinity[0]));
c->id = last_chunk_id++;
pset_insert(env->chunkset, c, c->id);
return c;
pset_remove(env->chunkset, c, c->id);
bitset_free(c->nodes);
bitset_free(c->interfere);
+ xfree(c->color_affinity);
DEL_ARR_F(c->n);
c->deleted = 1;
free(c);
/* Exclude colors not assignable to the irn */
req = arch_get_register_req(env->aenv, irn, -1);
- if (arch_register_req_is(req, limited))
+ if (arch_register_req_is(req, limited)) {
rbitset_copy_to_bitset(req->limited, res->adm_colors);
+ res->constr_factor = 1.0 - (double) bitset_popcnt(res->adm_colors) / env->k;
+ }
else
bitset_set_all(res->adm_colors);
* @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;
-
+ (void) env;
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);
-
- return bitset_popcnt(tmp) > 0;
+ return bitset_intersect(c1->interfere, c2->nodes);
}
/**
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);
/**
* 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->k; ++i) {
+ c->color_affinity[i].col = i;
+ c->color_affinity[i].cost = 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);
+ 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);
+
+ if (node->constr_factor > 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;
DEL_ARR_F(edges);
}
+static void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
+{
+ pqueue *grow = new_pqueue();
+ int i;
+ int max_weight = 0;
+ ir_node *max_node = NULL;
+
+ 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);
+ 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, 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, 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.
*/
}
/* 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);
+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);
/**
* 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) {
+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) {
int col = get_mst_irn_col(node);
int res = 0;
qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
/* Try recoloring the node using the color list. */
- res = recolor_nodes(env, node, costs, changed_ones);
+ res = recolor_nodes(env, node, costs, changed_ones, depth + 1);
}
return res;
* 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) {
+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 i;
struct list_head local_changed;
+ if (depth >= recolor_limit)
+ return 0;
+
DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
DBG_COL_COST(env, LEVEL_1, costs);
DB((dbg, LEVEL_1, "\n"));
*/
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);
+ neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed, depth + 1);
if (!neigh_ok)
break;
* 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) {
+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) {
int col = get_mst_irn_col(node);
/* if node already has the target color -> good, temporary fix it */
col_cost_init_single(env, costs, tgt_col);
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_ones, depth);
DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
return res;
}
-#ifndef NDEBUG
+#ifdef DEBUG_libfirm
if (firm_dbg_get_mask(dbg) & LEVEL_4) {
if (!is_loose(node))
DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
int did_all = 0;
waitq *tmp_chunks = new_waitq();
waitq *best_starts = NULL;
+ col_cost_t *order = alloca(env->k * sizeof(order[0]));
bitset_t *visited;
- int col, idx, len;
+ int idx, len, i;
struct list_head changed_ones;
+ bitset_pos_t pos;
DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
DBG_AFF_CHUNK(env, LEVEL_2, c);
DB((dbg, LEVEL_2, "\n"));
+ /* compute color preference */
+ memcpy(order, c->color_affinity, env->k * sizeof(order[0]));
+
+ bitset_foreach (c->interfere, pos) {
+ ir_node *n = get_idx_irn(env->co->irg, pos);
+ co_mst_irn_t *node = get_co_mst_irn(env, n);
+ bitset_pos_t col;
+
+ if (node->constr_factor > 0.0 && is_loose(node)) {
+ bitset_foreach (node->adm_colors, col)
+ order[col].cost += node->constr_factor;
+ }
+ }
+
+ qsort(order, env->k, sizeof(order[0]), cmp_col_cost);
+
+ chunk_order_nodes(env, c);
/* check which color is the "best" for the given chunk.
* if we found a color which was ok for all nodes, we take it
* 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) {
+ for (i = 0; i < env->k && !did_all; ++i) {
+ int col = order[i].col;
int one_good = 0;
waitq *good_starts = new_waitq();
aff_chunk_t *local_best;
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;
+ 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));
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);
+ good = change_node_color(env, node, col, &changed_ones, 0);
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"));
+ DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, good ? "succeeded" : "failed"));
}
/* try next color when failed */
/* 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);
+ res = change_node_color(env, node, best_color, &changed_ones, 0);
if (res) {
materialize_coloring(&changed_ones);
node->fixed = 1;
return 0;
}
+static const lc_opt_table_entry_t options[] = {
+ LC_OPT_ENT_INT ("limit", "limit recoloring", &recolor_limit),
+ 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");
}
projects / libfirm / blobdiff