/*
- * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
+ * Copyright (C) 1995-2010 University of Karlsruhe. All right reserved.
*
* This file is part of libFirm.
*
#include "pqueue.h"
#include "xmalloc.h"
#include "pdeq.h"
-#include "pset.h"
#include "irprintf.h"
#include "irbitset.h"
#include "error.h"
static int recolor_limit = 7;
static real_t dislike_influence = REAL(0.1);
-typedef struct _col_cost_t {
+typedef struct col_cost_t {
int col;
real_t cost;
} col_cost_t;
/**
* An affinity chunk.
*/
-typedef struct _aff_chunk_t {
- const ir_node **n; /**< An ARR_F containing all nodes of the chunk. */
+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. */
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;
+ list_head list;
col_cost_t color_affinity[1];
} aff_chunk_t;
/**
* An affinity edge.
*/
-typedef struct _aff_edge_t {
+typedef struct aff_edge_t {
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 */
-typedef struct _co_mst_env_t {
+typedef struct co_mst_env_t {
int n_regs; /**< number of regs in class */
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_t *chunks; /**< priority queue for chunks */
- pset *chunkset; /**< set holding all chunks */
+ list_head chunklist; /**< list holding all chunks */
be_ifg_t *ifg; /**< the interference graph */
copy_opt_t *co; /**< the copy opt object */
unsigned chunk_visited;
} co_mst_env_t;
/* stores coalescing related information for a node */
-typedef struct _co_mst_irn_t {
+typedef struct co_mst_irn_t {
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 */
*/
static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node)
{
- bitset_pos_t idx;
+ unsigned idx;
(void) env;
- if (bitset_popcnt(node->adm_colors) < 1)
+ if (bitset_popcount(node->adm_colors) < 1)
fprintf(stderr, "no admissible colors?!?");
else {
bitset_foreach(node->adm_colors, idx) {
const col_cost_t *c1 = a;
const col_cost_t *c2 = b;
real_t diff = c2->cost - c1->cost;
+
+ if (diff == 0.0)
+ return QSORT_CMP(c1->col, c2->col);
+
return (diff > 0) - (diff < 0);
}
c->deleted = 0;
c->id = ++last_chunk_id;
c->visited = 0;
- pset_insert(env->chunkset, c, c->id);
+ list_add(&c->list, &env->chunklist);
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)
+static inline void delete_aff_chunk(aff_chunk_t *c)
{
- pset_remove(env->chunkset, c, c->id);
+ list_del(&c->list);
DEL_ARR_F(c->interfere);
DEL_ARR_F(c->n);
c->deleted = 1;
/**
* In case there is no phase information for irn, initialize it.
*/
-static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old)
+static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn)
{
- co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
+ co_mst_irn_t *res = phase_alloc(ph, sizeof(res[0]));
co_mst_env_t *env = ph->priv;
- if (!old) {
- const arch_register_req_t *req;
- void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
- ir_node *neigh;
- unsigned len;
-
- res->irn = irn;
- res->chunk = NULL;
- res->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(irn));
- res->init_col = res->col;
- INIT_LIST_HEAD(&res->list);
-
- DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
-
- /* set admissible registers */
- res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
-
- /* Exclude colors not assignable to the irn */
- req = arch_get_register_req_out(irn);
- if (arch_register_req_is(req, limited))
- rbitset_copy_to_bitset(req->limited, res->adm_colors);
- else
- bitset_set_all(res->adm_colors);
-
- /* 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;
-
- /* build list of interfering neighbours */
- len = 0;
- be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
- if (!arch_irn_is_ignore(neigh)) {
- obstack_ptr_grow(phase_obst(ph), neigh);
- ++len;
- }
+ const arch_register_req_t *req;
+ neighbours_iter_t nodes_it;
+ ir_node *neigh;
+ unsigned len;
+
+ res->irn = irn;
+ res->chunk = NULL;
+ res->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(irn));
+ res->init_col = res->col;
+ INIT_LIST_HEAD(&res->list);
+
+ DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
+
+ /* set admissible registers */
+ res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
+
+ /* Exclude colors not assignable to the irn */
+ req = arch_get_register_req_out(irn);
+ if (arch_register_req_is(req, limited))
+ rbitset_copy_to_bitset(req->limited, res->adm_colors);
+ else
+ bitset_set_all(res->adm_colors);
+
+ /* 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_popcount(res->adm_colors)) / env->n_regs;
+
+ /* set the number of interfering affinity neighbours to -1, they are calculated later */
+ res->int_aff_neigh = -1;
+
+ /* build list of interfering neighbours */
+ len = 0;
+ be_ifg_foreach_neighbour(env->ifg, &nodes_it, irn, neigh) {
+ if (!arch_irn_is_ignore(neigh)) {
+ obstack_ptr_grow(phase_obst(ph), neigh);
+ ++len;
}
- res->int_neighs = obstack_finish(phase_obst(ph));
- res->n_neighs = len;
}
+ res->int_neighs = obstack_finish(phase_obst(ph));
+ res->n_neighs = len;
return res;
}
c1->weight_consistent = 0;
- delete_aff_chunk(env, c2);
+ delete_aff_chunk(c2);
goto absorbed;
}
DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
node->chunk = c;
if (node->constr_factor > REAL(0.0)) {
- bitset_pos_t col;
+ unsigned col;
bitset_foreach (node->adm_colors, col)
c->color_affinity[col].cost += node->constr_factor;
}
c->color_affinity[i].cost *= (REAL(1.0) / ARR_LEN(c->n));
c->weight = w;
- // c->weight = bitset_popcnt(c->nodes);
+ // c->weight = bitset_popcount(c->nodes);
c->weight_consistent = 1;
}
}
*/
static void build_affinity_chunks(co_mst_env_t *env)
{
- void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
+ nodes_iter_t nodes_it;
aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
ir_node *n;
int i, len;
aff_chunk_t *curr_chunk;
/* at first we create the affinity edge objects */
- be_ifg_foreach_node(env->ifg, nodes_it, n) {
+ be_ifg_foreach_node(env->ifg, &nodes_it, n) {
int n_idx = get_irn_idx(n);
co_mst_irn_t *n1;
affinity_node_t *an;
}
/* now insert all chunks into a priority queue */
- foreach_pset(env->chunkset, curr_chunk) {
+ list_for_each_entry(aff_chunk_t, curr_chunk, &env->chunklist, list) {
aff_chunk_assure_weight(env, curr_chunk);
DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id));
while (! waitq_empty(tmp_chunks)) {
aff_chunk_t *tmp = waitq_get(tmp_chunks);
if (tmp != best_chunk)
- delete_aff_chunk(env, tmp);
+ delete_aff_chunk(tmp);
}
del_waitq(tmp_chunks);
}
/* clear obsolete chunks and free some memory */
- delete_aff_chunk(env, best_chunk);
+ delete_aff_chunk(best_chunk);
bitset_free(visited);
if (best_starts)
del_waitq(best_starts);
stat_ev_tim_push();
/* init phase */
- phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
+ phase_init(&mst_env.ph, co->irg, co_mst_irn_init);
+ phase_set_private(&mst_env.ph, &mst_env);
- k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
+ k = be_put_ignore_regs(co->cenv->irg, co->cls, ignore_regs);
k = n_regs - k;
mst_env.n_regs = n_regs;
mst_env.co = co;
mst_env.ignore_regs = ignore_regs;
mst_env.ifg = co->cenv->ifg;
- mst_env.chunkset = pset_new_ptr(512);
+ INIT_LIST_HEAD(&mst_env.chunklist);
mst_env.chunk_visited = 0;
mst_env.single_cols = phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs);
color_aff_chunk(&mst_env, chunk);
DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%u) done\n", chunk->id));
- delete_aff_chunk(&mst_env, chunk);
+ delete_aff_chunk(chunk);
}
/* apply coloring */
/* free allocated memory */
del_pqueue(mst_env.chunks);
- phase_free(&mst_env.ph);
- del_pset(mst_env.chunkset);
+ phase_deinit(&mst_env.ph);
stat_ev_tim_pop("heur4_total");
projects / libfirm / blobdiff