#include "pdeq.h"
#include "irprintf.h"
#include "irbitset.h"
-#include "list.h"
#include "bearch.h"
#include "beifg.h"
*/
typedef struct _aff_chunk_t {
bitset_t *nodes; /**< A bitset containing all nodes inside this chunk. */
- int weight; /**< The weight of this chunk. */
+ int weight; /**< Weight of this chunk */
unsigned weight_consistent : 1; /**< Set if the weight is consistent. */
- struct list_head list; /**< For linking into lists. */
- int id; /**< For debugging: An identifier. */
+ int id; /**< For debugging: An id of this chunk. */
} aff_chunk_t;
/**
* An affinity edge.
*/
typedef struct _aff_edge_t {
- ir_node *src; /**< The source node. */
- ir_node *tgt; /**< The target node. */
+ ir_node *src; /**< Source node. */
+ ir_node *tgt; /**< Target node. */
double weight; /**< The weight of this edge. */
} aff_edge_t;
-/** Main coalescing environment. */
+/* main coalescing environment */
typedef struct _co_mst_env_t {
int n_regs; /**< number of regs in class */
int k; /**< number of non-ignore registers in class */
int *map_regs; /**< map the available colors to the available registers */
ir_phase ph; /**< phase object holding data for nodes */
pqueue *chunks; /**< priority queue for chunks */
- struct list_head used_chunks; /**< The list of used chunks. */
- struct list_head free_chunks; /**< The list of free chunks. */
+ pset_new_t 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 */
#define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
-typedef int decide_func_t(co_mst_irn_t *node, int col);
+typedef int decide_func_t(const co_mst_irn_t *node, int col);
#ifdef DEBUG_libfirm
/**
* Write a chunk to stderr for debugging.
*/
-static void dbg_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
+static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) {
int idx;
if (c->weight_consistent)
ir_fprintf(stderr, " $%d ", c->weight);
/**
* Dump all admissible colors to stderr.
*/
-static void dbg_admissible_colors(co_mst_env_t *env, co_mst_irn_t *node) {
+static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node) {
int idx;
if (bitset_popcnt(node->adm_colors) < 1)
fprintf(stderr, "no admissible colors?!?");
/**
* Dump color-cost pairs to stderr.
*/
-static void dbg_col_cost(co_mst_env_t *env, col_cost_t *cost) {
+static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) {
int i;
for (i = 0; i < env->n_regs; ++i) {
if (cost[i].cost == COL_COST_INFEASIBLE)
#endif /* DEBUG_libfirm */
-static INLINE int get_mst_irn_col(co_mst_irn_t *node) {
+static INLINE int get_mst_irn_col(const co_mst_irn_t *node) {
return node->tmp_fixed ? node->tmp_col : node->col;
}
/**
* @return 1 if node @p node has color @p col, 0 otherwise.
*/
-static int decider_has_color(co_mst_irn_t *node, int col) {
+static int decider_has_color(const co_mst_irn_t *node, int col) {
return get_mst_irn_col(node) == col;
}
/**
* @return 1 if node @p node has not color @p col, 0 otherwise.
*/
-static int decider_hasnot_color(co_mst_irn_t *node, int col) {
+static int decider_hasnot_color(const co_mst_irn_t *node, int col) {
return get_mst_irn_col(node) != col;
}
/**
* Always returns true.
*/
-static int decider_always_yes(co_mst_irn_t *node, int col) {
+static int decider_always_yes(const co_mst_irn_t *node, int col) {
return 1;
}
* Creates a new affinity chunk
*/
static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
- aff_chunk_t *c;
-
- if (list_empty(&env->free_chunks)) {
- struct obstack *obst = phase_obst(&env->ph);
-
- c = obstack_alloc(obst, sizeof(*c));
- c->nodes = bitset_irg_obstack_alloc(obst, env->co->irg);
- INIT_LIST_HEAD(&c->list);
- list_add(&c->list, &env->used_chunks);
- } else {
- c = list_entry(env->free_chunks.next, aff_chunk_t, list);
- list_move(&c->list, &env->used_chunks);
- bitset_clear_all(c->nodes);
- }
+ aff_chunk_t *c = xmalloc(sizeof(*c));
c->weight = -1;
c->weight_consistent = 0;
+ c->nodes = bitset_irg_malloc(env->co->irg);
c->id = last_chunk_id++;
+ pset_new_insert(&env->chunkset, c);
return c;
}
* Frees all memory allocated by an affinity chunk.
*/
static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
- list_move(&c->list, &env->free_chunks);
+ pset_new_remove(&env->chunkset, c);
+ bitset_free(c->nodes);
+ free(c);
}
/**
const arch_register_req_t *req;
void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
ir_node *neigh;
- int len;
+ unsigned len;
res->irn = irn;
res->chunk = NULL;
/**
* Check if affinity chunk @p chunk interferes with node @p irn.
*/
-static INLINE int aff_chunk_interferes(co_mst_env_t *env, aff_chunk_t *chunk, ir_node *irn) {
- co_mst_irn_t *node = get_co_mst_irn(env, irn);
- ir_node *neigh;
- int i;
+static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, ir_node *irn) {
+ const co_mst_irn_t *node = get_co_mst_irn(env, irn);
+ const ir_node *neigh;
+ int i;
- for (i = node->n_neighs - 1; i >= 0; --i) {
+ for (i = 0; i < node->n_neighs; ++i) {
neigh = node->int_neighs[i];
if (! arch_irn_is(env->aenv, neigh, ignore) && bitset_is_set(chunk->nodes, get_irn_idx(neigh)))
return 1;
* @param c2 Another chunk
* @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
*/
-static INLINE int aff_chunks_interfere(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
+static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) {
int idx;
if (c1 == c2)
}
/**
-* Returns the affinity chunk of @p irn or creates a new
-* one with @p irn as element if there is none assigned.
-*/
+ * Returns the affinity chunk of @p irn or creates a new
+ * one with @p irn as element if there is none assigned.
+ */
static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
co_mst_irn_t *node = get_co_mst_irn(env, irn);
return node->chunk;
/**
* Assures that the weight of the given chunk is consistent.
*/
-static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
+static void aff_chunk_assure_weight(const co_mst_env_t *env, aff_chunk_t *c) {
if (! c->weight_consistent) {
int w = 0;
int idx;
bitset_foreach(c->nodes, idx) {
- ir_node *n = get_idx_irn(env->co->irg, idx);
- affinity_node_t *an = get_affinity_info(env->co, n);
+ ir_node *n = get_idx_irn(env->co->irg, idx);
+ const affinity_node_t *an = get_affinity_info(env->co, n);
if (an != NULL) {
neighb_t *neigh;
co_gs_foreach_neighb(an, neigh) {
- ir_node *m = neigh->irn;
- int m_idx = get_irn_idx(m);
+ const ir_node *m = neigh->irn;
+ const int m_idx = get_irn_idx(m);
/* skip ignore nodes */
if (arch_irn_is(env->aenv, m, ignore))
/**
* Count the number of interfering affinity neighbours
*/
-static int count_interfering_aff_neighs(co_mst_env_t *env, affinity_node_t *an) {
- neighb_t *neigh;
- ir_node *irn = an->irn;
- co_mst_irn_t *node = get_co_mst_irn(env, irn);
- int res = 0;
+static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
+ const neighb_t *neigh;
+ ir_node *irn = an->irn;
+ const co_mst_irn_t *node = get_co_mst_irn(env, irn);
+ int res = 0;
co_gs_foreach_neighb(an, neigh) {
- ir_node *n = neigh->irn;
- int i;
+ const ir_node *n = neigh->irn;
+ int i;
/* skip ignore nodes */
if (arch_irn_is(env->aenv, n, ignore))
continue;
- /* check if n interfere with the affinity neighbours */
- for (i = node->n_neighs - 1; i >= 0; --i) {
+ /* check if the affinity neighbour interfere */
+ for (i = 0; i < node->n_neighs; ++i) {
if (node->int_neighs[i] == n) {
++res;
break;
ir_node *n;
int i, len;
aff_chunk_t *curr_chunk;
+ pset_new_iterator_t iter;
/* at first we create the affinity edge objects */
be_ifg_foreach_node(env->ifg, nodes_it, n) {
}
/* now insert all chunks into a priority queue */
- list_for_each_entry(aff_chunk_t, curr_chunk, &env->used_chunks, list) {
+ foreach_pset_new(&env->chunkset, curr_chunk, iter) {
aff_chunk_assure_weight(env, curr_chunk);
DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
mst_env.ignore_regs = ignore_regs;
mst_env.ifg = co->cenv->ifg;
mst_env.aenv = co->aenv;
- INIT_LIST_HEAD(&mst_env.used_chunks);
- INIT_LIST_HEAD(&mst_env.free_chunks);
+ pset_new_init(&mst_env.chunkset);
DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
/* free allocated memory */
del_pqueue(mst_env.chunks);
phase_free(&mst_env.ph);
+ pset_new_destroy(&mst_env.chunkset);
return 0;
}
projects / libfirm / blobdiff