X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur4.c;h=4e341fd3d45277ba992ff692da58c7729038b7b2;hb=5244f95767968d8b59ef3f2031612b86474e2455;hp=59d39f6a498f9233567344de9d5fd70fa7bf53dc;hpb=1a26f4853c07d1ecd68a097409dd602edfe29eff;p=libfirm

diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c
index 59d39f6a4..4e341fd3d 100644
--- a/ir/be/becopyheur4.c
+++ b/ir/be/becopyheur4.c
@@ -1,5 +1,5 @@
 /*
- * 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.
  *
@@ -43,7 +43,6 @@
 #include "pqueue.h"
 #include "xmalloc.h"
 #include "pdeq.h"
-#include "pset.h"
 #include "irprintf.h"
 #include "irbitset.h"
 #include "error.h"
@@ -85,7 +84,7 @@ 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 col_cost_t {
 	int     col;
 	real_t  cost;
 } col_cost_t;
@@ -93,34 +92,35 @@ typedef struct _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;
@@ -128,7 +128,7 @@ typedef struct _co_mst_env_t {
 } 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 */
@@ -143,7 +143,10 @@ typedef struct _co_mst_irn_t {
 	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);
 
@@ -171,14 +174,14 @@ static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c)
  */
 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);
 		}
 	}
 }
@@ -229,8 +232,8 @@ static int decider_always_yes(const co_mst_irn_t *node, int col)
 /** 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)
@@ -245,17 +248,21 @@ static int cmp_aff_edge(const void *a, const void *b)
 /** 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);
 }
 
@@ -272,16 +279,16 @@ static inline aff_chunk_t *new_aff_chunk(co_mst_env_t *env)
 	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;
@@ -368,59 +375,57 @@ static inline void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node)
 /**
  * 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;
 }
 
@@ -534,7 +539,7 @@ static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node
 
 		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"));
@@ -566,7 +571,7 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c)
 
 			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;
 			}
@@ -588,7 +593,7 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c)
 			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;
 	}
 }
@@ -631,14 +636,14 @@ static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t
  */
 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;
@@ -698,7 +703,7 @@ static void build_affinity_chunks(co_mst_env_t *env)
 	}
 
 	/* 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));
@@ -766,7 +771,7 @@ static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chu
 		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;
 
@@ -812,7 +817,7 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v
 
 	/* 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 */
@@ -1232,7 +1237,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c)
 		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));
@@ -1315,9 +1320,9 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c)
 
 	/* 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);
 
@@ -1401,7 +1406,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c)
 	}
 
 	/* 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);
@@ -1414,9 +1419,10 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c)
  */
 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;
 
@@ -1425,23 +1431,24 @@ static int co_solve_heuristic_mst(copy_opt_t *co)
 	stat_ev_tim_push();
 
 	/* init phase */
-	phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
-
-	k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
-	k = n_regs - k;
-
-	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);
+	phase_init(&mst_env.ph, co->irg, co_mst_irn_init);
+	phase_set_private(&mst_env.ph, &mst_env);
+
+	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.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) {
@@ -1462,11 +1469,11 @@ static int co_solve_heuristic_mst(copy_opt_t *co)
 
 	/* 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 */
@@ -1491,8 +1498,7 @@ static int co_solve_heuristic_mst(copy_opt_t *co)
 
 	/* 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");
 
@@ -1505,7 +1511,7 @@ static const lc_opt_table_entry_t options[] = {
 	LC_OPT_LAST
 };
 
-
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);
 void be_init_copyheur4(void)
 {
 	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
@@ -1523,5 +1529,3 @@ void be_init_copyheur4(void)
 
 	FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
 }
-
-BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);