/*
- * 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.
*
#define INFEASIBLE(cost) ((cost) == INT_MAX)
-static be_ifg_dump_dot_cb_t ifg_dot_cb;
-
typedef unsigned col_t;
typedef struct co2_irn_t co2_irn_t;
typedef struct {
ir_phase ph;
copy_opt_t *co;
- bitset_t *ignore_regs;
+ bitset_t *allocatable_regs;
co2_irn_t *touched;
int visited;
int n_regs;
co2_irn_t *touched_next;
col_t tmp_col;
col_t orig_col;
- int last_color_change;
+ int last_color_change;
bitset_t *adm_cache;
unsigned fixed : 1;
unsigned tmp_fixed : 1;
int n_memb;
int n_constr;
int max_degree;
- int ticks;
+ int ticks;
double freedom;
co2_cloud_irn_t *master;
co2_cloud_irn_t *mst_root;
co2_t *env = (co2_t *) ph;
affinity_node_t *a = get_affinity_info(env->co, irn);
size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
- co2_irn_t *ci = phase_alloc(ph, size);
+ co2_irn_t *ci = (co2_irn_t*)phase_alloc(ph, size);
memset(ci, 0, size);
INIT_LIST_HEAD(&ci->changed_list);
static int cmp_clouds_gt(const void *a, const void *b)
{
- const co2_cloud_t * const *p = a;
- const co2_cloud_t * const *q = b;
+ const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
+ const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
double c = CLOUD_WEIGHT(*p);
double d = CLOUD_WEIGHT(*q);
return QSORT_CMP(d, c);
*/
static int col_cost_pair_lt(const void *a, const void *b)
{
- const col_cost_pair_t *p = a;
- const col_cost_pair_t *q = b;
+ const col_cost_pair_t *p = (const col_cost_pair_t*)a;
+ const col_cost_pair_t *q = (const col_cost_pair_t*)b;
int c = p->costs;
int d = q->costs;
return QSORT_CMP(c, d);
static int cmp_edges(const void *a, const void *b)
{
- const edge_t *p = a;
- const edge_t *q = b;
+ const edge_t *p = (const edge_t*)a;
+ const edge_t *q = (const edge_t*)b;
return QSORT_CMP(q->costs, p->costs);
}
if (ci->adm_cache == NULL) {
const arch_register_req_t *req;
ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
- req = arch_get_register_req_out(ci->irn);
+ req = arch_get_irn_register_req(ci->irn);
if (arch_register_req_is(req, limited)) {
int i, n;
}
ci->is_constrained = 1;
} else {
- bitset_copy(ci->adm_cache, env->ignore_regs);
- bitset_flip_all(ci->adm_cache);
+ bitset_copy(ci->adm_cache, env->allocatable_regs);
}
}
static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
{
- const arch_register_req_t *req = arch_get_register_req_out(irn);
+ const arch_register_req_t *req = arch_get_irn_register_req(irn);
if (arch_register_req_is(req, limited)) {
unsigned n_regs = env->co->cls->n_regs;
bitset_t *forb = bitset_alloca(n_regs);
affinity_node_t *a = ci->aff;
- unsigned elm;
+ size_t elm;
const ir_node *pos;
neighbours_iter_t it;
int i;
be_ifg_t *ifg = env->co->cenv->ifg;
bitset_t *bs = bitset_alloca(n_regs);
- unsigned elm;
+ size_t elm;
const ir_node *irn;
neighbours_iter_t it;
admissible_colors(env, ni, bs);
if (bitset_popcount(bs) == 1) {
- unsigned c = bitset_next_set(bs, 0);
+ size_t c = bitset_next_set(bs, 0);
badness[c] += ci->costs;
}
static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
{
- co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
+ co2_cloud_t *cloud = (co2_cloud_t*)phase_alloc(&env->ph, sizeof(cloud[0]));
co2_cloud_irn_t *ci;
int i;
cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
/* Also allocate space for the node sequence and compute that sequence. */
- cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
+ cloud->seq = (co2_cloud_irn_t**)phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
i = 0;
list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
{
const ir_node *irn = ci->inh.irn;
int *front = FRONT_BASE(ci, col);
- int i, ok;
+ int i;
struct list_head changed;
INIT_LIST_HEAD(&changed);
DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
- ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
- // assert(ok && "Color changing may not fail while committing the coloring");
+ change_color_single(ci->cloud->env, irn, col, &changed, depth);
materialize_coloring(&changed);
for (i = 0; i < ci->mst_n_childs; ++i) {
}
}
}
- edges = obstack_finish(&cloud->obst);
+ edges = (edge_t*)obstack_finish(&cloud->obst);
qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
/* Compute the maximum spanning tree using Kruskal/Union-Find */
cloud->mst_root = cloud->master;
q = new_pdeq1(cloud->master);
while (!pdeq_empty(q)) {
- co2_cloud_irn_t *ci = pdeq_getl(q);
+ co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
int ofs = ci->index * cloud->n_memb;
int end = ofs + cloud->n_memb;
int i;
}
obstack_ptr_grow(&cloud->obst, NULL);
- ci->mst_childs = obstack_finish(&cloud->obst);
+ ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
}
del_pdeq(q);
free(mst_edges);
return costs / 2;
}
-static void process(co2_t *env)
-{
- affinity_node_t *a;
- co2_cloud_t *pos;
- co2_cloud_t **clouds;
- int n_clouds;
- int i;
- int init_costs = 0;
- int all_costs = 0;
- int final_costs = 0;
-
- n_clouds = 0;
- co_gs_foreach_aff_node(env->co, a) {
- co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
-
- if (!ci->cloud) {
- new_cloud(env, a);
- n_clouds++;
- }
- }
-
- i = 0;
- clouds = XMALLOCN(co2_cloud_t*, n_clouds);
- list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
- clouds[i++] = pos;
- qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
-
- for (i = 0; i < n_clouds; ++i) {
- init_costs += cloud_costs(clouds[i]);
-
- /* Process the cloud. */
- process_cloud(clouds[i]);
-
- all_costs += clouds[i]->costs;
- final_costs += cloud_costs(clouds[i]);
-
- /* Dump the IFG if the user demanded it. */
- if (dump_flags & DUMP_CLOUD) {
- char buf[256];
- FILE *f;
-
- ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
- f = fopen(buf, "wt");
- if (f != NULL) {
- be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
- fclose(f);
- }
- }
- }
-
- DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
-
- xfree(clouds);
-}
-
static void writeback_colors(co2_t *env)
{
co2_irn_t *irn;
static const char *get_dot_shape_name(co2_irn_t *ci)
{
- const arch_register_req_t *req = arch_get_register_req_out(ci->irn);
+ const arch_register_req_t *req = arch_get_irn_register_req(ci->irn);
if (arch_register_req_is(req, limited))
return "diamond";
static int ifg_is_dump_node(void *self, ir_node *irn)
{
- const arch_register_req_t *req = arch_get_register_req_out(irn);
+ const arch_register_req_t *req = arch_get_irn_register_req(irn);
(void)self;
return !(req->type & arch_register_req_type_ignore);
}
static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
{
- co2_t *env = self;
+ co2_t *env = (co2_t*)self;
co2_irn_t *ci = get_co2_irn(env, irn);
int peri = 1;
char buf[128] = "";
if (ci->aff) {
- co2_cloud_irn_t *cci = (void *) ci;
+ co2_cloud_irn_t *cci = (co2_cloud_irn_t*) ci;
if (cci->cloud && cci->cloud->mst_root == cci)
peri = 2;
static void ifg_dump_at_end(FILE *file, void *self)
{
- co2_t *env = self;
+ co2_t *env = (co2_t*)self;
affinity_node_t *a;
co_gs_foreach_aff_node(env->co, a) {
neighb_t *n;
if (ai->mst_parent != ai)
- fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
+ fprintf(file, "\tn%d -- n%u [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
co_gs_foreach_neighb(a, n) {
int nidx = get_irn_idx(n->irn);
}
}
-
static be_ifg_dump_dot_cb_t ifg_dot_cb = {
ifg_is_dump_node,
ifg_dump_graph_attr,
ifg_dump_at_end
};
+static void process(co2_t *env)
+{
+ affinity_node_t *a;
+ co2_cloud_t *pos;
+ co2_cloud_t **clouds;
+ int n_clouds;
+ int i;
+ int init_costs = 0;
+ int all_costs = 0;
+ int final_costs = 0;
+
+ n_clouds = 0;
+ co_gs_foreach_aff_node(env->co, a) {
+ co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
+
+ if (!ci->cloud) {
+ new_cloud(env, a);
+ n_clouds++;
+ }
+ }
+
+ i = 0;
+ clouds = XMALLOCN(co2_cloud_t*, n_clouds);
+ list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
+ clouds[i++] = pos;
+ qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
+
+ for (i = 0; i < n_clouds; ++i) {
+ init_costs += cloud_costs(clouds[i]);
+
+ /* Process the cloud. */
+ process_cloud(clouds[i]);
+
+ all_costs += clouds[i]->costs;
+ final_costs += cloud_costs(clouds[i]);
+
+ /* Dump the IFG if the user demanded it. */
+ if (dump_flags & DUMP_CLOUD) {
+ char buf[256];
+ FILE *f;
+
+ ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
+ f = fopen(buf, "wt");
+ if (f != NULL) {
+ be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
+ fclose(f);
+ }
+ }
+ }
+
+ DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
+
+ xfree(clouds);
+}
+
int co_solve_heuristic_new(copy_opt_t *co)
{
char buf[256];
env.visited = 0;
env.co = co;
env.n_regs = co->cls->n_regs;
- env.ignore_regs = bitset_alloca(co->cls->n_regs);
- be_put_ignore_regs(co->cenv->irg, co->cls, env.ignore_regs);
+ env.allocatable_regs = bitset_alloca(co->cls->n_regs);
+ be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
INIT_LIST_HEAD(&env.cloud_head);
return 0;
}
-BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
void be_init_copyheur2(void)
{
lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");