X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyopt.c;h=818bbf0910a055261becd5b6dda2c0af600c37c4;hb=65f6cc39305e6880fe45709a8a2e1c24445395e3;hp=5c5e169849aebdb768840cdceea6e96d63e49ebf;hpb=4d5c3365a58cba59993045a9e08e686d8ae079a7;p=libfirm

diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c
index 5c5e16984..818bbf091 100644
--- a/ir/be/becopyopt.c
+++ b/ir/be/becopyopt.c
@@ -18,10 +18,16 @@
  */
 
 /**
- * Author:      Daniel Grund
- * Date:		12.04.2005
- * Copyright:   (c) Universitaet Karlsruhe
- * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
+ * @file
+ * @brief       Copy minimization driver.
+ * @author      Daniel Grund
+ * @date        12.04.2005
+ * @version     $Id$
+ *
+ * Main file for the optimization reducing the copies needed for:
+ * - Phi coalescing
+ * - Register-constrained nodes
+ * - Two-address code instructions
  */
 #ifdef HAVE_CONFIG_H
 #include "config.h"
@@ -32,6 +38,7 @@
 #include "debug.h"
 #include "pmap.h"
 #include "raw_bitset.h"
+#include "irnode.h"
 #include "irgraph.h"
 #include "irgwalk.h"
 #include "irprog.h"
@@ -47,6 +54,7 @@
 #include "benode_t.h"
 #include "beutil.h"
 #include "beifg_t.h"
+#include "beintlive_t.h"
 #include "becopyopt_t.h"
 #include "becopystat.h"
 #include "belive_t.h"
@@ -75,7 +83,7 @@ static unsigned   dump_flags  = 0;
 static unsigned   style_flags = 0;
 static unsigned   do_stats    = 0;
 static cost_fct_t cost_func   = co_get_costs_exec_freq;
-static unsigned   algo        = CO_ALGO_HEUR;
+static unsigned   algo        = CO_ALGO_HEUR4;
 static int        improve     = 1;
 
 static const lc_opt_enum_mask_items_t dump_items[] = {
@@ -141,7 +149,7 @@ static const lc_opt_table_entry_t options[] = {
 	LC_OPT_ENT_ENUM_MASK     ("style",   "dump style for ifg dumping",                              &style_var),
 	LC_OPT_ENT_BOOL          ("stats",   "dump statistics after each optimization",                 &do_stats),
 	LC_OPT_ENT_BOOL          ("improve", "run heur3 before if algo can exploit start solutions",    &improve),
-	{ NULL }
+	LC_OPT_LAST
 };
 
 /* Insert additional options registration functions here. */
@@ -168,7 +176,7 @@ static int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const
 	if (env->ifg)
 		return be_ifg_connected(env->ifg, a, b);
 	else
-		return values_interfere(env->birg->lv, a, b);
+		return values_interfere(env->birg, a, b);
 }
 
 
@@ -233,43 +241,12 @@ int co_is_optimizable_root(const copy_opt_t *co, ir_node *irn) {
 	return 0;
 }
 
-int co_is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
-	const ir_edge_t *edge;
-	const arch_register_t *reg;
-
-	assert(0 && "Is buggy and obsolete. Do not use");
-
-	if (arch_irn_is(co->aenv, irn, ignore))
-		return 0;
-
-	reg = arch_get_irn_register(co->aenv, irn);
-	if (arch_register_type_is(reg, ignore))
-		return 0;
-
-	foreach_out_edge(irn, edge) {
-		ir_node *n = edge->src;
-
-		if (!nodes_interfere(co->cenv, irn, n) || irn == n) {
-			const arch_register_req_t *req;
-			req = arch_get_register_req(co->aenv, n, -1);
-
-			if(is_Reg_Phi(n) ||
-			   is_Perm(co->aenv, n) ||
-			   (arch_register_req_is(req, should_be_same))) {
-				ir_node *other = get_irn_n(irn, req->other_same);
-				if(other == irn)
-					return 1;
-			}
-		}
-	}
-
-	return 0;
-}
-
 int co_get_costs_loop_depth(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 	int cost = 0;
 	ir_loop *loop;
 	ir_node *root_block = get_nodes_block(root);
+	(void) co;
+	(void) arg;
 
 	if (is_Phi(root)) {
 		/* for phis the copies are placed in the corresponding pred-block */
@@ -289,6 +266,7 @@ int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, in
 	int res;
 	ir_node *root_bl = get_nodes_block(root);
 	ir_node *copy_bl = is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
+	(void) arg;
 	res = get_block_execfreq_ulong(co->cenv->birg->exec_freq, copy_bl);
 
 	/* don't allow values smaller than one. */
@@ -297,6 +275,10 @@ int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, in
 
 
 int co_get_costs_all_one(const copy_opt_t *co, ir_node *root, ir_node *arg, int pos) {
+	(void) co;
+	(void) root;
+	(void) arg;
+	(void) pos;
 	return 1;
 }
 
@@ -320,7 +302,8 @@ static int ou_max_ind_set_costs(unit_t *ou) {
 	ir_node **safe, **unsafe;
 	int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
 	bitset_t *curr;
-	int max, pos, curr_weight, best_weight = 0;
+	bitset_pos_t pos;
+	int max, curr_weight, best_weight = 0;
 
 	/* assign the nodes into two groups.
 	 * safe: node has no interference, hence it is in every max stable set.
@@ -454,7 +437,7 @@ static void co_collect_units(ir_node *irn, void *env) {
 					unit->nodes[unit->node_count] = arg;
 					unit->costs[unit->node_count] = co->get_costs(co, irn, arg, i);
 					unit->node_count++;
-				} else { /* arg has occured before in same phi */
+				} else { /* arg has occurred before in same phi */
 					/* increase costs for existing arg */
 					unit->costs[arg_pos] += co->get_costs(co, irn, arg, i);
 				}
@@ -462,10 +445,8 @@ static void co_collect_units(ir_node *irn, void *env) {
 		}
 		unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
 		unit->costs = xrealloc(unit->costs, unit->node_count * sizeof(*unit->costs));
-	} else
-
-	/* Proj of a perm with corresponding arg */
-	if (is_Perm_Proj(co->aenv, irn)) {
+	} else if (is_Perm_Proj(co->aenv, irn)) {
+		/* Proj of a perm with corresponding arg */
 		assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
 		unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
 		unit->costs = xmalloc(2 * sizeof(*unit->costs));
@@ -479,15 +460,44 @@ static void co_collect_units(ir_node *irn, void *env) {
 
 		/* Src == Tgt of a 2-addr-code instruction */
 		if (is_2addr_code(req)) {
-			ir_node *other = get_irn_n(irn, req->other_same);
-			if (!arch_irn_is(co->aenv, other, ignore) &&
-					!nodes_interfere(co->cenv, irn, other)) {
-				unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
-				unit->costs = xmalloc(2 * sizeof(*unit->costs));
-				unit->node_count = 2;
-				unit->nodes[0] = irn;
-				unit->nodes[1] = other;
-				unit->costs[1] = co->get_costs(co, irn, other, -1);
+			ir_node *other  = get_irn_n(skip_Proj(irn), req->other_same[0]);
+			ir_node *other2 = NULL;
+			int      count;
+
+			if (arch_irn_is(co->aenv, other, ignore) ||
+					nodes_interfere(co->cenv, irn, other)) {
+				other = NULL;
+			}
+			if (req->other_same[1] != -1) {
+				other2 = get_irn_n(skip_Proj(irn), req->other_same[1]);
+				if (arch_irn_is(co->aenv, other2, ignore) ||
+						nodes_interfere(co->cenv, irn, other2)) {
+					other2 = NULL;
+				}
+			}
+			count = 1 + (other != NULL) + (other2 != NULL && other != other2);
+
+			if (count > 1) {
+				int i = 0;
+
+				unit->nodes = xmalloc(count * sizeof(*unit->nodes));
+				unit->costs = xmalloc(count * sizeof(*unit->costs));
+				unit->node_count = count;
+				unit->nodes[i] = irn;
+				if (other != NULL) {
+					++i;
+					unit->nodes[i] = other;
+					unit->costs[i] = co->get_costs(co, irn, other, -1);
+				}
+				if (other2 != NULL) {
+					if (other == other2) {
+						unit->costs[i] += co->get_costs(co, irn, other2, -1);
+					} else {
+						++i;
+						unit->nodes[i] = other2;
+						unit->costs[i] = co->get_costs(co, irn, other2, -1);
+					}
+				}
 			}
 		} else {
 			assert(0 && "This is not an optimizable node!");
@@ -727,21 +737,21 @@ void co_complete_stats(const copy_opt_t *co, co_complete_stats_t *stat)
 static int compare_affinity_node_t(const void *k1, const void *k2, size_t size) {
 	const affinity_node_t *n1 = k1;
 	const affinity_node_t *n2 = k2;
+	(void) size;
 
 	return (n1->irn != n2->irn);
 }
 
 static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 	affinity_node_t new_node, *node;
-	neighb_t new_nbr, *nbr;
-	int allocnew;
+	neighb_t        *nbr;
+	int             allocnew = 1;
 
 	new_node.irn        = n1;
 	new_node.degree     = 0;
 	new_node.neighbours = NULL;
 	node = set_insert(co->nodes, &new_node, sizeof(new_node), nodeset_hash(new_node.irn));
 
-	allocnew = 1;
 	for (nbr = node->neighbours; nbr; nbr = nbr->next)
 		if (nbr->irn == n2) {
 			allocnew = 0;
@@ -750,11 +760,11 @@ static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 
 	/* if we did not find n2 in n1's neighbourhood insert it */
 	if (allocnew) {
-		obstack_grow(&co->obst, &new_nbr, sizeof(new_nbr));
-		nbr = obstack_finish(&co->obst);
+		nbr        = obstack_alloc(&co->obst, sizeof(*nbr));
 		nbr->irn   = n2;
 		nbr->costs = 0;
 		nbr->next  = node->neighbours;
+
 		node->neighbours = nbr;
 		node->degree++;
 	}
@@ -782,27 +792,29 @@ static void build_graph_walker(ir_node *irn, void *env) {
 	if (arch_register_type_is(reg, ignore))
 		return;
 
-	/* Phis */
-	if (is_Reg_Phi(irn))
+	if (is_Reg_Phi(irn)) { /* Phis */
 		for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
 			ir_node *arg = get_irn_n(irn, pos);
 			add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
 		}
-
-	/* Perms */
-	else if (is_Perm_Proj(co->aenv, irn)) {
+	}
+	else if (is_Perm_Proj(co->aenv, irn)) { /* Perms */
 		ir_node *arg = get_Perm_src(irn);
 		add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
 	}
-
-	/* 2-address code */
-	else {
-		const arch_register_req_t *req =
-			arch_get_register_req(co->aenv, irn, -1);
+	else { /* 2-address code */
+		const arch_register_req_t *req = arch_get_register_req(co->aenv, irn, -1);
 		if (is_2addr_code(req)) {
-			ir_node *other = get_irn_n(irn, req->other_same);
-			if(!arch_irn_is(co->aenv, other, ignore))
-				add_edges(co, irn, other, co->get_costs(co, irn, other, 0));
+			const int *i;
+			for (i = req->other_same; i != ENDOF(req->other_same); ++i) {
+				ir_node *other;
+
+				if (*i == -1) break;
+
+				other = get_irn_n(skip_Proj(irn), *i);
+				if (! arch_irn_is(co->aenv, other, ignore))
+					add_edges(co, irn, other, co->get_costs(co, irn, other, 0));
+			}
 		}
 	}
 }
@@ -939,6 +951,7 @@ static int appel_aff_weight(const appel_clique_walker_t *env, ir_node *bl)
 	return res == 0 ? 1 : res;
 #else
 	ir_loop *loop = get_irn_loop(bl);
+	(void) env;
 	if(loop) {
 		int d = get_loop_depth(loop);
 		return 1 + d * d;
@@ -950,6 +963,7 @@ static int appel_aff_weight(const appel_clique_walker_t *env, ir_node *bl)
 static void *appel_clique_walker_irn_init(ir_phase *phase, ir_node *irn, void *old)
 {
 	appel_block_info_t *res = NULL;
+	(void) old;
 
 	if(is_Block(irn)) {
 		appel_clique_walker_t *d = (void *) phase;
@@ -982,15 +996,16 @@ static int appel_get_live_end_nr(appel_clique_walker_t *env, ir_node *bl, ir_nod
 	return -1;
 }
 
-static int appel_dump_clique(appel_clique_walker_t *env, pset *live, ir_node *bl, int curr_nr, int start_nr)
+static int appel_dump_clique(appel_clique_walker_t *env, const ir_nodeset_t *live, ir_node *bl, int curr_nr, int start_nr)
 {
 	ir_node **live_arr = alloca(env->co->cls->n_regs * sizeof(live_arr[0]));
 	ir_node *irn;
 	int n_live;
 	int j;
+	ir_nodeset_iterator_t iter;
 
 	n_live = 0;
-	foreach_pset(live, irn)
+	foreach_ir_nodeset(live, irn, iter)
 		live_arr[n_live++] = irn;
 
 	/* dump the live after clique */
@@ -1032,7 +1047,8 @@ static void appel_walker(ir_node *bl, void *data)
 	appel_block_info_t *bli    = phase_get_or_set_irn_data(&env->ph, bl);
 	struct obstack *obst       = &env->obst;
 	void *base                 = obstack_base(obst);
-	pset *live                 = pset_new_ptr_default();
+	ir_nodeset_t live;
+	ir_nodeset_iterator_t iter;
 	be_lv_t *lv                = env->co->cenv->birg->lv;
 
 	int n_insns  = 0;
@@ -1055,7 +1071,7 @@ static void appel_walker(ir_node *bl, void *data)
 		n_nodes++;
 
 	bli->n_phi = 0;
-	insns = malloc(n_nodes * sizeof(insns[0]));
+	insns = xmalloc(n_nodes * sizeof(insns[0]));
 
 	/* Put all insns in an array. */
 	irn = sched_first(bl);
@@ -1067,7 +1083,8 @@ static void appel_walker(ir_node *bl, void *data)
 	}
 
 	DBG((dbg, LEVEL_2, "%+F\n", bl));
-	be_liveness_end_of_block(lv, env->co->aenv, env->co->cls, bl, live);
+	ir_nodeset_init(&live);
+	be_liveness_end_of_block(lv, env->co->aenv, env->co->cls, bl, &live);
 
 	/* Generate the bad and ugly. */
 	for(i = n_insns - 1; i >= 0; --i) {
@@ -1076,7 +1093,7 @@ static void appel_walker(ir_node *bl, void *data)
 		/* The first live set has to be saved in the block border set. */
 		if(i == n_insns - 1) {
 			j = 0;
-			foreach_pset(live, irn) {
+			foreach_ir_nodeset(&live, irn, iter) {
 				bli->live_end[j]    = irn;
 				bli->live_end_nr[j] = curr_nr + j;
 				++j;
@@ -1089,21 +1106,20 @@ static void appel_walker(ir_node *bl, void *data)
 				ir_node *op   = insn->ops[j].carrier;
 				bitset_t *adm = insn->ops[j].regs;
 				int k;
-				int nr;
+				size_t nr;
 
 				if(!insn->ops[j].has_constraints)
 					continue;
 
 				nr = 0;
-				foreach_pset(live, irn) {
+				foreach_ir_nodeset(&live, irn, iter) {
 					if(irn == op) {
-						pset_break(live);
 						break;
 					}
 					++nr;
 				}
 
-				assert(nr < pset_count(live));
+				assert(nr < ir_nodeset_size(&live));
 
 				for(k = 0; k < env->co->cls->n_regs; ++k) {
 					int mapped_col = env->color_map[k];
@@ -1114,11 +1130,11 @@ static void appel_walker(ir_node *bl, void *data)
 		}
 
 		/* dump the clique and update the stuff. */
-		curr_nr = appel_dump_clique(env, live, bl, curr_nr, start_nr);
+		curr_nr = appel_dump_clique(env, &live, bl, curr_nr, start_nr);
 
 		/* remove all defs. */
 		for(j = 0; j < insn->use_start; ++j)
-			pset_remove_ptr(live, insn->ops[j].carrier);
+			ir_nodeset_remove(&live, insn->ops[j].carrier);
 
 		if(is_Phi(insn->irn) && arch_irn_consider_in_reg_alloc(env->co->aenv, env->co->cls, insn->irn)) {
 			bli->phi[bli->n_phi]    = insn->irn;
@@ -1129,21 +1145,21 @@ static void appel_walker(ir_node *bl, void *data)
 		/* add all uses */
 		else
 			for(j = insn->use_start; j < insn->n_ops; ++j)
-				pset_insert_ptr(live, insn->ops[j].carrier);
+				ir_nodeset_insert(&live, insn->ops[j].carrier);
 	}
 
 	/* print the start clique. */
-	curr_nr = appel_dump_clique(env, live, bl, curr_nr, start_nr);
+	curr_nr = appel_dump_clique(env, &live, bl, curr_nr, start_nr);
 
 	i = 0;
-	foreach_pset(live, irn) {
+	foreach_ir_nodeset(&live, irn, iter) {
 		bli->live_in[i]    = irn;
 		bli->live_in_nr[i] = PTR_TO_INT(get_irn_link(irn));
 		++i;
 	}
 	bli->n_live_in = i;
 
-	del_pset(live);
+	ir_nodeset_destroy(&live);
 	free(insns);
 	obstack_free(obst, base);
 	env->curr_nr = curr_nr;
@@ -1240,7 +1256,7 @@ void co_dump_appel_graph_cliques(const copy_opt_t *co, FILE *f)
 	                                                          |_|            |___/
 */
 
-static const char *get_dot_color_name(int col)
+static const char *get_dot_color_name(size_t col)
 {
 	static const char *names[] = {
 		"blue",
@@ -1286,6 +1302,7 @@ typedef struct _co_ifg_dump_t {
 
 static void ifg_dump_graph_attr(FILE *f, void *self)
 {
+	(void) self;
 	fprintf(f, "overlap=scale");
 }
 
@@ -1381,11 +1398,12 @@ void co_dump_ifg_dot(const copy_opt_t *co, FILE *f, unsigned flags)
 
 void co_solve_park_moon(copy_opt_t *opt)
 {
-
+	(void) opt;
 }
 
 static int void_algo(copy_opt_t *co)
 {
+	(void) co;
 	return 0;
 }
 
@@ -1447,9 +1465,11 @@ void co_driver(be_chordal_env_t *cenv)
 	co_algo_t           *algo_func;
 	int                 was_optimal = 0;
 
-	if (algo < 0 || algo >= CO_ALGO_LAST)
+	if (algo >= CO_ALGO_LAST)
 		return;
 
+	be_liveness_assure_chk(be_get_birg_liveness(cenv->birg));
+
 	co = new_copy_opt(cenv, cost_func);
 	co_build_ou_structure(co);
 	co_build_graph_structure(co);