X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbepbqpcoloring.c;h=2a9dd326a3d871f1657eef734a877d0602464cb7;hb=8a907f80824671f3ff21569442566dceca8d4f5f;hp=dc9fe03607f91bc7c155174f5ed56af1db38217d;hpb=7cff44bc4b54d6b93f947e708cf893d85574b399;p=libfirm

diff --git a/ir/be/bepbqpcoloring.c b/ir/be/bepbqpcoloring.c
index dc9fe0360..2a9dd326a 100644
--- a/ir/be/bepbqpcoloring.c
+++ b/ir/be/bepbqpcoloring.c
@@ -61,7 +61,7 @@
 #include "matrix.h"
 #include "vector.h"
 #include "vector_t.h"
-#include "heuristical.h"
+#include "heuristical_co.h"
 #include "pbqp_t.h"
 #include "html_dumper.h"
 #include "pbqp_node_t.h"
@@ -83,6 +83,7 @@ typedef struct _be_pbqp_alloc_env_t {
 	pbqp_matrix					*aff_matrix_template;
 	plist_t						*rpeo;
 	unsigned					*restr_nodes;
+	unsigned					*ife_edge_num;
 	be_chordal_env_t			*env;
 } be_pbqp_alloc_env_t;
 
@@ -121,7 +122,7 @@ static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char
 	ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
 	xfree(tu_name);
 	result = fopen(buf, "wt");
-	if(result == NULL) {
+	if (result == NULL) {
 		panic("Couldn't open '%s' for writing.", buf);
 	}
 
@@ -130,7 +131,8 @@ static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char
 #endif
 
 
-static void create_pbqp_node(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *irn) {
+static void create_pbqp_node(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *irn)
+{
 	const arch_register_class_t *cls = pbqp_alloc_env->cls;
 	pbqp     *pbqp_inst              = pbqp_alloc_env->pbqp_inst;
 	bitset_t *ignored_regs           = pbqp_alloc_env->ignored_regs;
@@ -142,8 +144,8 @@ static void create_pbqp_node(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *irn)
 
 	/* set costs depending on register constrains */
 	unsigned idx;
-	for(idx = 0; idx < colors_n; idx++) {
-		if(bitset_is_set(ignored_regs, idx) || !arch_reg_out_is_allocatable(irn, arch_register_for_index(cls, idx))) {
+	for (idx = 0; idx < colors_n; idx++) {
+		if (bitset_is_set(ignored_regs, idx) || !arch_reg_out_is_allocatable(irn, arch_register_for_index(cls, idx))) {
 			vector_set(costs_vector, idx, INF_COSTS);
 			cntConstrains++;
 		}
@@ -154,23 +156,28 @@ static void create_pbqp_node(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *irn)
 	pbqp_alloc_env->restr_nodes[get_irn_idx(irn)] = cntConstrains;
 }
 
-static void insert_ife_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_node, ir_node *trg_node) {
+static void insert_ife_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_node, ir_node *trg_node)
+{
 	pbqp 						*pbqp                = pbqp_alloc_env->pbqp_inst;
 	const arch_register_class_t *cls                 = pbqp_alloc_env->cls;
 	pbqp_matrix 				*ife_matrix_template = pbqp_alloc_env->ife_matrix_template;
 	unsigned 					*restr_nodes         = pbqp_alloc_env->restr_nodes;
 
-	if(get_edge(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node)) == NULL) {
+	if (get_edge(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node)) == NULL) {
+
+		/* increase ife edge counter */
+		pbqp_alloc_env->ife_edge_num[get_irn_idx(src_node)]++;
+		pbqp_alloc_env->ife_edge_num[get_irn_idx(trg_node)]++;
 
 		/* do useful optimization to speed up pbqp solving (we can do this because we know our matrix) */
-		if(get_free_regs(restr_nodes, cls, src_node) == 1 && get_free_regs(restr_nodes, cls, trg_node) == 1) {
+		if (get_free_regs(restr_nodes, cls, src_node) == 1 && get_free_regs(restr_nodes, cls, trg_node) == 1) {
 			unsigned src_idx = vector_get_min_index(get_node(pbqp, get_irn_idx(src_node))->costs);
 			unsigned trg_idx = vector_get_min_index(get_node(pbqp, get_irn_idx(trg_node))->costs);
 			assert(src_idx != trg_idx && "Interfering nodes could not have the same register!");
 			return;
 		}
-		if(get_free_regs(restr_nodes, cls, src_node) == 1 || get_free_regs(restr_nodes, cls, trg_node) == 1) {
-			if(get_free_regs(restr_nodes, cls, src_node) == 1) {
+		if (get_free_regs(restr_nodes, cls, src_node) == 1 || get_free_regs(restr_nodes, cls, trg_node) == 1) {
+			if (get_free_regs(restr_nodes, cls, src_node) == 1) {
 				unsigned idx = vector_get_min_index(get_node(pbqp, get_irn_idx(src_node))->costs);
 				vector_set(get_node(pbqp, get_irn_idx(trg_node))->costs, idx, INF_COSTS);
 			}
@@ -186,15 +193,16 @@ static void insert_ife_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_no
 	}
 }
 
-static void inser_afe_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_node, ir_node *trg_node, int pos) {
+static void inser_afe_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_node, ir_node *trg_node, int pos)
+{
 	pbqp 						*pbqp             = pbqp_alloc_env->pbqp_inst;
 	const arch_register_class_t *cls              = pbqp_alloc_env->cls;
 	unsigned 					*restr_nodes      = pbqp_alloc_env->restr_nodes;
 	pbqp_matrix					*afe_matrix       = pbqp_matrix_alloc(pbqp, arch_register_class_n_regs(cls), arch_register_class_n_regs(cls));
 	unsigned 					 colors_n		  = arch_register_class_n_regs(cls);
 
-	if(get_edge(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node)) == NULL) {
-		if(use_exec_freq) {
+	if (get_edge(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node)) == NULL) {
+		if (use_exec_freq) {
 			/* get exec_freq for copy_block */
 			ir_node *root_bl = get_nodes_block(src_node);
 			ir_node *copy_bl = is_Phi(src_node) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
@@ -202,9 +210,9 @@ static void inser_afe_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_nod
 
 			/* create afe-matrix */
 			unsigned row, col;
-			for(row = 0; row < colors_n; row++) {
-				for(col = 0; col < colors_n; col++) {
-					if(row != col)
+			for (row = 0; row < colors_n; row++) {
+				for (col = 0; col < colors_n; col++) {
+					if (row != col)
 						pbqp_matrix_set(afe_matrix, row, col, (num)res);
 				}
 			}
@@ -214,11 +222,11 @@ static void inser_afe_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_nod
 		}
 
 		/* do useful optimization to speed up pbqp solving */
-		if(get_free_regs(restr_nodes, cls, src_node) == 1 && get_free_regs(restr_nodes, cls, trg_node) == 1) {
+		if (get_free_regs(restr_nodes, cls, src_node) == 1 && get_free_regs(restr_nodes, cls, trg_node) == 1) {
 			return;
 		}
-		if(get_free_regs(restr_nodes, cls, src_node) == 1 || get_free_regs(restr_nodes, cls, trg_node) == 1) {
-			if(get_free_regs(restr_nodes, cls, src_node) == 1) {
+		if (get_free_regs(restr_nodes, cls, src_node) == 1 || get_free_regs(restr_nodes, cls, trg_node) == 1) {
+			if (get_free_regs(restr_nodes, cls, src_node) == 1) {
 				unsigned regIdx = vector_get_min_index(get_node(pbqp, get_irn_idx(src_node))->costs);
 				vector_add_matrix_col(get_node(pbqp, get_irn_idx(trg_node))->costs, afe_matrix, regIdx);
 			}
@@ -234,7 +242,8 @@ static void inser_afe_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_nod
 	}
 }
 
-static void create_affinity_edges(ir_node *irn, void *env) {
+static void create_affinity_edges(ir_node *irn, void *env)
+{
 	be_pbqp_alloc_env_t         *pbqp_alloc_env   = env;
 	const arch_register_class_t *cls              = pbqp_alloc_env->cls;
 	const arch_register_req_t   *req              = arch_get_register_req_out(irn);
@@ -248,7 +257,7 @@ static void create_affinity_edges(ir_node *irn, void *env) {
 				continue;
 
 			/* no edges to itself */
-			if(irn == arg) {
+			if (irn == arg) {
 				continue;
 			}
 
@@ -274,7 +283,7 @@ static void create_affinity_edges(ir_node *irn, void *env) {
 						continue;
 
 					/* no edges to itself */
-					if(irn == other) {
+					if (irn == other) {
 						continue;
 					}
 
@@ -285,7 +294,8 @@ static void create_affinity_edges(ir_node *irn, void *env) {
 	}
 }
 
-static void create_pbqp_coloring_instance(ir_node *block, void *data) {
+static void create_pbqp_coloring_instance(ir_node *block, void *data)
+{
 	be_pbqp_alloc_env_t         *pbqp_alloc_env    	= data;
 	be_lv_t                     *lv                	= pbqp_alloc_env->lv;
 	const arch_register_class_t *cls               	= pbqp_alloc_env->cls;
@@ -319,19 +329,19 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) {
 					continue;
 
 				/* create pbqp source node if it dosn't exist */
-				if(get_node(pbqp_inst, get_irn_idx(proj)) == NULL) {
+				if (get_node(pbqp_inst, get_irn_idx(proj)) == NULL) {
 					create_pbqp_node(pbqp_alloc_env, proj);
 				}
 
 				/* create nodes and interference edges */
 				foreach_ir_nodeset(&live_nodes, live, iter) {
 					/* create pbqp source node if it dosn't exist */
-					if(get_node(pbqp_inst, get_irn_idx(live)) == NULL) {
+					if (get_node(pbqp_inst, get_irn_idx(live)) == NULL) {
 						create_pbqp_node(pbqp_alloc_env, live);
 					}
 
 					/* no edges to itself */
-					if(proj == live) {
+					if (proj == live) {
 						continue;
 					}
 
@@ -342,19 +352,19 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) {
 		else {
 			if (arch_irn_consider_in_reg_alloc(cls, irn)) {
 				/* create pbqp source node if it dosn't exist */
-				if(get_node(pbqp_inst, get_irn_idx(irn)) == NULL) {
+				if (get_node(pbqp_inst, get_irn_idx(irn)) == NULL) {
 					create_pbqp_node(pbqp_alloc_env, irn);
 				}
 
 				/* create nodes and interference edges */
 				foreach_ir_nodeset(&live_nodes, live, iter) {
 					/* create pbqp source node if it dosn't exist */
-					if(get_node(pbqp_inst, get_irn_idx(live)) == NULL) {
+					if (get_node(pbqp_inst, get_irn_idx(live)) == NULL) {
 						create_pbqp_node(pbqp_alloc_env, live);
 					}
 
 					/* no edges to itself */
-					if(irn == live) {
+					if (irn == live) {
 						continue;
 					}
 
@@ -380,17 +390,17 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) {
 					continue;
 
 				// insert proj node into priority queue (descending by the number of interference edges)
-				if(get_free_regs(restr_nodes, cls, proj) <= 4/*bitset_is_set(restr_nodes, get_irn_idx(proj))*/) {
-					pqueue_put(restr_nodes_queue, proj, pbqp_node_get_degree(get_node(pbqp_inst, get_irn_idx(proj))));
+				if (get_free_regs(restr_nodes, cls, proj) <= 4/*bitset_is_set(restr_nodes, get_irn_idx(proj))*/) {
+					pqueue_put(restr_nodes_queue, proj, pbqp_alloc_env->ife_edge_num[get_irn_idx(proj)]);
 				}
 				else {
-					pqueue_put(queue,proj, pbqp_node_get_degree(get_node(pbqp_inst, get_irn_idx(proj))));
+					pqueue_put(queue,proj, pbqp_alloc_env->ife_edge_num[get_irn_idx(proj)]);
 				}
 			}
 
 			/* first insert all restricted nodes */
-			while(!pqueue_empty(restr_nodes_queue)) {
-				if(first == NULL) {
+			while (!pqueue_empty(restr_nodes_queue)) {
+				if (first == NULL) {
 					plist_insert_back(temp_list, get_node(pbqp_inst, get_irn_idx(pqueue_pop_front(restr_nodes_queue))));
 					first = plist_first(temp_list);
 				} else {
@@ -399,8 +409,8 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) {
 			}
 
 			/* insert proj nodes descending by their number of interference edges */
-			while(!pqueue_empty(queue)) {
-				if(first == NULL) {
+			while (!pqueue_empty(queue)) {
+				if (first == NULL) {
 					plist_insert_back(temp_list, get_node(pbqp_inst, get_irn_idx(pqueue_pop_front(queue))));
 					first = plist_first(temp_list);
 				} else {
@@ -428,7 +438,8 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) {
 	del_pqueue(restr_nodes_queue);
 }
 
-static void insert_perms(ir_node *block, void *data) {
+static void insert_perms(ir_node *block, void *data)
+{
 	/*
 	 * Start silent in the start block.
 	 * The silence remains until the first barrier is seen.
@@ -460,7 +471,8 @@ static void insert_perms(ir_node *block, void *data) {
 	}
 }
 
-void be_pbqp_coloring(be_chordal_env_t *env) {
+static void be_pbqp_coloring(be_chordal_env_t *env)
+{
 	ir_graph                      *irg  = env->irg;
 	be_irg_t                      *birg = env->birg;
 	const arch_register_class_t   *cls  = env->cls;
@@ -470,13 +482,12 @@ void be_pbqp_coloring(be_chordal_env_t *env) {
 	be_lv_t *lv;
 
 #if TIMER
-	ir_timer_t *t_ra_pbqp_alloc_create    = ir_timer_register("be_pbqp_alloc_create", "pbqp alloc create");
-	ir_timer_t *t_ra_pbqp_alloc_solve     = ir_timer_register("be_pbqp_alloc_solve", "pbqp alloc solve");
-	ir_timer_t *t_ra_pbqp_alloc_create_aff  = ir_timer_register("be_pbqp_alloc_create_aff", "pbqp alloc create aff");
+	ir_timer_t *t_ra_pbqp_alloc_create     = ir_timer_new();
+	ir_timer_t *t_ra_pbqp_alloc_solve      = ir_timer_new();
+	ir_timer_t *t_ra_pbqp_alloc_create_aff = ir_timer_new();
 
 	printf("#### ----- === Allocating registers of %s (%s) ===\n", cls->name, get_entity_name(get_irg_entity(irg)));
 #endif
-
 	lv = be_assure_liveness(birg);
 	be_liveness_assure_sets(lv);
 	be_liveness_assure_chk(lv);
@@ -502,6 +513,7 @@ void be_pbqp_coloring(be_chordal_env_t *env) {
 	pbqp_alloc_env.ignored_regs = bitset_malloc(colors_n);
 	pbqp_alloc_env.rpeo			= plist_new();
 	pbqp_alloc_env.restr_nodes  = XMALLOCNZ(unsigned, get_irg_last_idx(irg));
+	pbqp_alloc_env.ife_edge_num = XMALLOCNZ(unsigned, get_irg_last_idx(irg));
 	pbqp_alloc_env.env			= env;
 	be_put_ignore_regs(birg, cls, pbqp_alloc_env.ignored_regs);				/* get ignored registers */
 
@@ -509,19 +521,19 @@ void be_pbqp_coloring(be_chordal_env_t *env) {
 	/* create costs matrix template for interference edges */
 	struct pbqp_matrix *ife_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n);
 	/* set costs */
-	for(row = 0, col=0; row < colors_n; row++, col++)
+	for (row = 0, col=0; row < colors_n; row++, col++)
 		pbqp_matrix_set(ife_matrix, row, col, INF_COSTS);
 
 	pbqp_alloc_env.ife_matrix_template = ife_matrix;
 
 
-	if(!use_exec_freq) {
+	if (!use_exec_freq) {
 		/* create costs matrix template for affinity edges */
 		struct pbqp_matrix *afe_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n);
 		/* set costs */
-		for(row = 0; row < colors_n; row++) {
-			for(col = 0; col < colors_n; col++) {
-				if(row != col)
+		for (row = 0; row < colors_n; row++) {
+			for (col = 0; col < colors_n; col++) {
+				if (row != col)
 					pbqp_matrix_set(afe_matrix, row, col, 2);
 			}
 		}
@@ -589,9 +601,12 @@ void be_pbqp_coloring(be_chordal_env_t *env) {
 
 
 #if TIMER
-	printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_pbqp_alloc_create), (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_create) / 1000.0);
-	printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_pbqp_alloc_solve), (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_solve) / 1000.0);
-	printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_pbqp_alloc_create_aff), (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_create_aff) / 1000.0);
+	printf("%-20s: %8.3lf msec\n", "pbqp alloc create",
+	       (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_create) / 1000.0);
+	printf("%-20s: %8.3lf msec\n", "pbqp alloc solve",
+	       (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_solve) / 1000.0);
+	printf("%-20s: %8.3lf msec\n", "pbqp alloc create aff",
+	       (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_create_aff) / 1000.0);
 #endif
 
 
@@ -603,13 +618,16 @@ void be_pbqp_coloring(be_chordal_env_t *env) {
 	free_pbqp(pbqp_alloc_env.pbqp_inst);
 	plist_free(pbqp_alloc_env.rpeo);
 	xfree(pbqp_alloc_env.restr_nodes);
+	xfree(pbqp_alloc_env.ife_edge_num);
 }
 
 
 /**
  * Initializes this module.
  */
-void be_init_pbqp_coloring(void) {
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_pbqp_coloring);
+void be_init_pbqp_coloring(void)
+{
 	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 	lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
 	lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
@@ -624,6 +642,4 @@ void be_init_pbqp_coloring(void) {
 	be_register_chordal_coloring("pbqp", &coloring);
 }
 
-BE_REGISTER_MODULE_CONSTRUCTOR(be_pbqp_alloc);
-
 #endif