* (also known as "heur3" :)
* Performs simple copy minimization.
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif /* HAVE_CONFIG_H */
+
+#define DISABLE_STATEV
#include <float.h>
typedef float real_t;
#define REAL(C) (C ## f)
-static int last_chunk_id = 0;
-static int recolor_limit = 4;
+static unsigned last_chunk_id = 0;
+static int recolor_limit = 7;
static real_t dislike_influence = REAL(0.1);
typedef struct _col_cost_t {
*/
typedef struct _aff_chunk_t {
const ir_node **n; /**< An ARR_F containing all nodes of the chunk. */
- const ir_node **interfere; /**< An ARR_F containing all inference. */
+ 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;
+ unsigned id; /**< An id of this chunk. */
+ unsigned visited;
col_cost_t color_affinity[1];
} aff_chunk_t;
typedef struct _aff_edge_t {
const ir_node *src; /**< Source node. */
const ir_node *tgt; /**< Target node. */
- double weight; /**< The weight of this edge. */
+ int weight; /**< The weight of this edge. */
} aff_edge_t;
/* main coalescing environment */
int k; /**< number of non-ignore registers in class */
bitset_t *ignore_regs; /**< set containing all global ignore registers */
ir_phase ph; /**< phase object holding data for nodes */
- pqueue *chunks; /**< priority queue for chunks */
+ pqueue_t *chunks; /**< priority queue for chunks */
pset *chunkset; /**< set holding all chunks */
be_ifg_t *ifg; /**< the interference graph */
- const arch_env_t *aenv; /**< the arch environment */
copy_opt_t *co; /**< the copy opt object */
- int chunk_visited;
+ unsigned chunk_visited;
col_cost_t **single_cols;
} co_mst_env_t;
static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) {
int i, l;
(void) env;
-
if (c->weight_consistent)
ir_fprintf(stderr, " $%d ", c->weight);
ir_fprintf(stderr, "{");
* Creates a new affinity chunk
*/
static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
- aff_chunk_t *c = xmalloc(sizeof(*c) + (env->n_regs - 1) * sizeof(c->color_affinity[0]));
+ aff_chunk_t *c = XMALLOCF(aff_chunk_t, color_affinity, env->n_regs);
c->n = NEW_ARR_F(const ir_node *, 0);
- c->interfere = NEW_ARR_F(ir_node *, 0);
+ c->interfere = NEW_ARR_F(const ir_node *, 0);
c->weight = -1;
c->weight_consistent = 0;
c->deleted = 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->col = arch_register_get_index(arch_get_irn_register(irn));
res->init_col = res->col;
INIT_LIST_HEAD(&res->list);
res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
/* Exclude colors not assignable to the irn */
- req = arch_get_register_req(env->aenv, irn, -1);
+ req = arch_get_register_req(irn, -1);
if (arch_register_req_is(req, limited))
rbitset_copy_to_bitset(req->limited, res->adm_colors);
else
/* build list of interfering neighbours */
len = 0;
be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
- if (! arch_irn_is(env->aenv, neigh, ignore)) {
+ if (!arch_irn_is(neigh, ignore)) {
obstack_ptr_grow(phase_obst(ph), neigh);
++len;
}
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 {
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))
+ if (arch_irn_is(m, ignore))
continue;
w += node_contains(c->n, m) ? neigh->costs : 0;
int i;
/* skip ignore nodes */
- if (arch_irn_is(env->aenv, n, ignore))
+ if (arch_irn_is(n, ignore))
continue;
/* check if the affinity neighbour interfere */
affinity_node_t *an;
/* skip ignore nodes */
- if (arch_irn_is(env->aenv, n, ignore))
+ if (arch_irn_is(n, ignore))
continue;
n1 = get_co_mst_irn(env, n);
aff_edge_t edge;
/* skip ignore nodes */
- if (arch_irn_is(env->aenv, m, ignore))
+ if (arch_irn_is(m, ignore))
continue;
edge.src = n;
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"));
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"));
static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
{
- pqueue *grow = new_pqueue();
+ pqueue_t *grow = new_pqueue();
const ir_node *max_node = NULL;
int max_weight = 0;
int i;
int w = 0;
neighb_t *neigh;
- if (arch_irn_is(env->aenv, irn, ignore))
+ if (arch_irn_is(irn, ignore))
continue;
if (an) {
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;
- if (arch_irn_is(env->aenv, irn, ignore))
+ if (arch_irn_is(irn, ignore))
continue;
assert(i <= ARR_LEN(chunk->n));
{
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);
co_mst_irn_t *n2;
/* skip ignore nodes */
- if (arch_irn_is(env->aenv, m, ignore))
+ if (arch_irn_is(m, ignore))
continue;
n2 = get_co_mst_irn(env, m);
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 */
if (depth > *max_depth)
*max_depth = depth;
- if (depth >= recolor_limit)
- return 0;
-
DBG((dbg, LEVEL_4, "\tRecoloring %+F with color-costs", node->irn));
DBG_COL_COST(env, LEVEL_4, costs);
DB((dbg, LEVEL_4, "\n"));
+ if (depth >= recolor_limit) {
+ DBG((dbg, LEVEL_4, "\tHit recolor limit\n"));
+ return 0;
+ }
+
for (i = 0; i < env->n_regs; ++i) {
int tgt_col = costs[i].col;
int neigh_ok = 1;
int j;
/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
- if (costs[i].cost == REAL(0.0))
+ if (costs[i].cost == REAL(0.0)) {
+ DBG((dbg, LEVEL_4, "\tAll further colors forbidden\n"));
return 0;
+ }
/* Set the new color of the node and mark the node as temporarily fixed. */
assert(node->tmp_col < 0 && "Node must not have been temporary fixed.");
neigh = node->int_neighs[j];
/* skip ignore nodes */
- if (arch_irn_is(env->aenv, neigh, ignore))
+ if (arch_irn_is(neigh, ignore))
continue;
nn = get_co_mst_irn(env, neigh);
}
}
+ DBG((dbg, LEVEL_4, "\tAll colors failed\n"));
return 0;
}
int idx, len, i, nidx, pos;
struct list_head changed;
- DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
+ DB((dbg, LEVEL_2, "fragmentizing chunk #%u", c->id));
DBG_AFF_CHUNK(env, LEVEL_2, c);
DB((dbg, LEVEL_2, "\n"));
- stat_ev_ctx_push_fmt("heur4_color_chunk", "%d", c->id);
+ stat_ev_ctx_push_fmt("heur4_color_chunk", "%u", c->id);
++env->chunk_visited;
if (local_best) {
aff_chunk_assure_weight(env, local_best);
- DB((dbg, LEVEL_3, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
+ DB((dbg, LEVEL_3, "\t\tlocal best chunk (id %u) for color %d: ", local_best->id, col));
DBG_AFF_CHUNK(env, LEVEL_3, local_best);
if (! best_chunk || best_chunk->weight < local_best->weight) {
if (best_starts)
del_waitq(best_starts);
best_starts = good_starts;
- DB((dbg, LEVEL_3, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
+ DB((dbg, LEVEL_3, "\n\t\t... setting global best chunk (id %u), color %d\n", best_chunk->id, best_color));
} else {
DB((dbg, LEVEL_3, "\n\t\t... omitting, global best is better\n"));
del_waitq(good_starts);
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));
int res;
/* bring the node to the color. */
- DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, node->irn, best_chunk->id));
+ DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%u\n", best_color, node->irn, best_chunk->id));
INIT_LIST_HEAD(&changed);
stat_ev_tim_push();
res = change_node_color(env, node, best_color, &changed);
ir_node *irn;
co_mst_env_t mst_env;
+ last_chunk_id = 0;
+
stat_ev_tim_push();
/* init phase */
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);
/* 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);
}
co_mst_irn_t *mirn;
const arch_register_t *reg;
- if (arch_irn_is(mst_env.aenv, irn, ignore))
+ if (arch_irn_is(irn, ignore))
continue;
mirn = get_co_mst_irn(&mst_env, irn);
continue;
reg = arch_register_for_index(co->cls, mirn->col);
- arch_set_irn_register(co->aenv, irn, reg);
+ arch_set_irn_register(irn, reg);
DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
}
projects / libfirm / blobdiff