/*
- * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
+ * Copyright (C) 1995-2011 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 */
+ bitset_t *allocatable_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 */
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)))
+static co_mst_irn_t *get_co_mst_irn(co_mst_env_t *env, const ir_node *node)
+{
+ return (co_mst_irn_t*)phase_get_or_set_irn_data(&env->ph, node);
+}
typedef int decide_func_t(const co_mst_irn_t *node, int col);
*/
static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node)
{
- bitset_pos_t idx;
+ size_t 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) {
- fprintf(stderr, " %d", idx);
+ ir_fprintf(stderr, " %zu", idx);
}
}
}
/** compares two affinity edges by its weight */
static int cmp_aff_edge(const void *a, const void *b)
{
- const aff_edge_t *e1 = a;
- const aff_edge_t *e2 = b;
+ const aff_edge_t *e1 = (const aff_edge_t*)a;
+ const aff_edge_t *e2 = (const aff_edge_t*)b;
if (e2->weight == e1->weight) {
if (e2->src->node_idx == e1->src->node_idx)
/** compares to color-cost pairs */
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;
+ const col_cost_t *c1 = (const col_cost_t*)a;
+ const col_cost_t *c2 = (const col_cost_t*)b;
real_t diff = c1->cost - c2->cost;
return (diff > 0) - (diff < 0);
}
static int cmp_col_cost_gt(const void *a, const void *b)
{
- const col_cost_t *c1 = a;
- const col_cost_t *c2 = b;
+ const col_cost_t *c1 = (const col_cost_t*)a;
+ const col_cost_t *c2 = (const col_cost_t*)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_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;
- }
+ co_mst_irn_t *res = (co_mst_irn_t*)phase_alloc(ph, sizeof(res[0]));
+ co_mst_env_t *env = (co_mst_env_t*)ph->priv;
+
+ 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_and(res->adm_colors, env->allocatable_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 = (ir_node**)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;
+ size_t 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));
bitset_remv_irn(visited, max_node);
i = 0;
while (!pqueue_empty(grow)) {
- ir_node *irn = pqueue_pop_front(grow);
+ ir_node *irn = (ir_node*)pqueue_pop_front(grow);
affinity_node_t *an = get_affinity_info(env->co, irn);
neighb_t *neigh;
/* as long as there are nodes in the queue */
while (! waitq_empty(nodes)) {
- co_mst_irn_t *n = waitq_get(nodes);
+ co_mst_irn_t *n = (co_mst_irn_t*)waitq_get(nodes);
affinity_node_t *an = get_affinity_info(env->co, n->irn);
/* check all affinity neighbors */
int n_succeeded;
/* skip ignore colors */
- if (bitset_is_set(env->ignore_regs, col))
+ if (!bitset_is_set(env->allocatable_regs, col))
continue;
DB((dbg, LEVEL_2, "\ttrying color %d\n", col));
/* free all intermediate created chunks except best one */
while (! waitq_empty(tmp_chunks)) {
- aff_chunk_t *tmp = waitq_get(tmp_chunks);
+ aff_chunk_t *tmp = (aff_chunk_t*)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);
*/
static 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 i, j, k;
+ unsigned n_regs = co->cls->n_regs;
+ bitset_t *allocatable_regs = bitset_alloca(n_regs);
+ unsigned i, j;
+ size_t k;
ir_node *irn;
co_mst_env_t 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 = n_regs - k;
+ be_put_allocatable_regs(co->cenv->irg, co->cls, allocatable_regs);
+ k = bitset_popcount(allocatable_regs);
- 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.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);
+ mst_env.n_regs = n_regs;
+ mst_env.k = k;
+ mst_env.chunks = new_pqueue();
+ mst_env.co = co;
+ mst_env.allocatable_regs = allocatable_regs;
+ mst_env.ifg = co->cenv->ifg;
+ INIT_LIST_HEAD(&mst_env.chunklist);
+ mst_env.chunk_visited = 0;
+ mst_env.single_cols = (col_cost_t**)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);
+ col_cost_t *vec = (col_cost_t*)phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs);
mst_env.single_cols[i] = vec;
for (j = 0; j < n_regs; ++j) {
/* color chunks as long as there are some */
while (! pqueue_empty(mst_env.chunks)) {
- aff_chunk_t *chunk = pqueue_pop_front(mst_env.chunks);
+ aff_chunk_t *chunk = (aff_chunk_t*)pqueue_pop_front(mst_env.chunks);
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_deinit(&mst_env.ph);
- del_pset(mst_env.chunkset);
stat_ev_tim_pop("heur4_total");
projects / libfirm / blobdiff