X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fbe%2Fbechordal.c;h=d2b414cb1a0b501a4d839783d04505cb62323f27;hb=91f9fd8a65f0db8bcf956cfe54ac4cca394c45e8;hp=5a119e7975e0fb0a3f235936fdb7e937dfae2a3b;hpb=61ca019f49b71d23c4c55f3c47d7868480269fc0;p=libfirm

diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c
index 5a119e797..d2b414cb1 100644
--- a/ir/be/bechordal.c
+++ b/ir/be/bechordal.c
@@ -22,7 +22,6 @@
  * @brief       Chordal register allocation.
  * @author      Sebastian Hack
  * @date        08.12.2004
- * @version     $Id$
  */
 #include "config.h"
 
@@ -33,7 +32,6 @@
 #include "list.h"
 #include "bitset.h"
 #include "raw_bitset.h"
-#include "iterator.h"
 #include "bipartite.h"
 #include "hungarian.h"
 
@@ -44,7 +42,6 @@
 #include "irdump.h"
 #include "irdom.h"
 #include "irtools.h"
-#include "irbitset.h"
 #include "debug.h"
 #include "iredges.h"
 
@@ -57,7 +54,7 @@
 #include "beirgmod.h"
 #include "beifg.h"
 #include "beinsn_t.h"
-#include "bestatevent.h"
+#include "statev_t.h"
 #include "beirg.h"
 #include "beintlive_t.h"
 #include "bera.h"
@@ -69,73 +66,36 @@
 
 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 
-#define NO_COLOR (-1)
-
-#define DUMP_INTERVALS
-
-typedef struct _be_chordal_alloc_env_t {
+typedef struct be_chordal_alloc_env_t {
 	be_chordal_env_t *chordal_env;
 
 	pset *pre_colored;     /**< Set of precolored nodes. */
-	bitset_t *live;		   /**< A liveness bitset. */
+	bitset_t *live;        /**< A liveness bitset. */
 	bitset_t *tmp_colors;  /**< An auxiliary bitset which is as long as the number of colors in the class. */
-	bitset_t *colors;	   /**< The color mask. */
-	bitset_t *in_colors;   /**< Colors used by live in values. */
-	int colors_n;          /**< The number of colors. */
+	bitset_t *colors;      /**< The color mask. */
 } be_chordal_alloc_env_t;
 
-#if 0
-static void check_border_list(struct list_head *head)
-{
-	border_t *x;
-	list_for_each_entry(border_t, x, head, list) {
-		assert(x->magic == BORDER_FOURCC);
-	}
-}
-
-static void check_heads(be_chordal_env_t *env)
-{
-	pmap_entry *ent;
-	for (ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
-		/* ir_printf("checking border list of block %+F\n", ent->key); */
-		check_border_list(ent->value);
-	}
-}
-#endif
-
 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
 {
 	bitset_t *tmp = alloc_env->tmp_colors;
 	bitset_copy(tmp, colors);
-	bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
-	return bitset_next_clear(tmp, 0);
+	bitset_flip_all(tmp);
+	bitset_and(tmp, alloc_env->chordal_env->allocatable_regs);
+	return bitset_next_set(tmp, 0);
 }
 
-static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
+static bitset_t const *get_decisive_partner_regs(be_operand_t const *const o1)
 {
-	bitset_t *res = bs;
-
-	if (!o1) {
-		bitset_copy(bs, o2->regs);
-		return bs;
-	}
-
-	if (!o2) {
-		bitset_copy(bs, o1->regs);
-		return bs;
-	}
-
-	assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
+	be_operand_t const *const o2 = o1->partner;
+	assert(!o2 || o1->req->cls == o2->req->cls);
 
-	if (bitset_contains(o1->regs, o2->regs)) {
-		bitset_copy(bs, o1->regs);
+	if (!o2 || bitset_contains(o1->regs, o2->regs)) {
+		return o1->regs;
 	} else if (bitset_contains(o2->regs, o1->regs)) {
-		bitset_copy(bs, o2->regs);
+		return o2->regs;
 	} else {
-		res = NULL;
+		return NULL;
 	}
-
-	return res;
 }
 
 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
@@ -148,65 +108,60 @@ static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t
 	/*
 	 * For each out operand, try to find an in operand which can be assigned the
 	 * same register as the out operand.
-	*/
+	 */
 	for (j = 0; j < insn->use_start; ++j) {
-		int smallest         = -1;
-		int smallest_n_regs  = 2 * env->cls->n_regs + 1;
-		be_operand_t *out_op = &insn->ops[j];
+		be_operand_t *smallest        = NULL;
+		int           smallest_n_regs = env->cls->n_regs + 1;
+		be_operand_t *out_op          = &insn->ops[j];
 
 		/* Try to find an in operand which has ... */
 		for (i = insn->use_start; i < insn->n_ops; ++i) {
-			int n_total;
-			const be_operand_t *op = &insn->ops[i];
+			int           n_total;
+			be_operand_t *op = &insn->ops[i];
+			be_lv_t      *lv;
 
 			if (op->partner != NULL)
 				continue;
-			if (be_values_interfere(env->birg->lv, op->irn, op->carrier))
+			lv = be_get_irg_liveness(env->irg);
+			if (be_values_interfere(lv, op->irn, op->carrier))
 				continue;
 
-			bitset_clear_all(bs);
 			bitset_copy(bs, op->regs);
 			bitset_and(bs, out_op->regs);
-			n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
+			n_total = bitset_popcount(op->regs);
 
 			if (!bitset_is_empty(bs) && n_total < smallest_n_regs) {
-				smallest = i;
+				smallest        = op;
 				smallest_n_regs = n_total;
 			}
 		}
 
-		if (smallest >= 0) {
-			be_operand_t *partner = &insn->ops[smallest];
+		if (smallest != NULL) {
 			for (i = insn->use_start; i < insn->n_ops; ++i) {
-				if (insn->ops[i].carrier == partner->carrier)
+				if (insn->ops[i].carrier == smallest->carrier)
 					insn->ops[i].partner = out_op;
 			}
 
-			out_op->partner  = partner;
-			partner->partner = out_op;
+			out_op->partner   = smallest;
+			smallest->partner = out_op;
 		}
 	}
 }
 
-static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
-                                   ir_node *irn, int *silent)
+static void handle_constraints(be_chordal_alloc_env_t *alloc_env,
+                                   ir_node *irn)
 {
 	int n_regs;
-	bitset_t *bs;
 	ir_node **alloc_nodes;
 	//hungarian_problem_t *bp;
 	int *assignment;
 	pmap *partners;
 	int i, n_alloc;
-	bitset_pos_t col;
-	const ir_edge_t *edge;
 	ir_node *perm = NULL;
 	//int match_res, cost;
 	be_chordal_env_t *env  = alloc_env->chordal_env;
 	void *base             = obstack_base(env->obst);
-	be_insn_t *insn        = chordal_scan_insn(env, irn);
-	ir_node *res           = insn->next_insn;
-	int be_silent          = *silent;
+	be_insn_t *insn        = be_scan_insn(env, irn);
 	bipartite_t *bp;
 
 	if (insn->pre_colored) {
@@ -215,28 +170,14 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 			pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
 	}
 
-	/*
-	 * If the current node is a barrier toggle the silent flag.
-	 * If we are in the start block, we are ought to be silent at the beginning,
-	 * so the toggling activates the constraint handling but skips the barrier.
-	 * If we are in the end block we handle the in requirements of the barrier
-	 * and set the rest to silent.
-	 */
-	if (be_is_Barrier(irn))
-		*silent = !*silent;
-
-	if (be_silent)
-		goto end;
-
 	/*
 	 * Perms inserted before the constraint handling phase are considered to be
 	 * correctly precolored. These Perms arise during the ABI handling phase.
 	 */
-	if (!insn->has_constraints)
+	if (!insn->has_constraints || is_Phi(irn))
 		goto end;
 
 	n_regs      = env->cls->n_regs;
-	bs          = bitset_alloca(n_regs);
 	alloc_nodes = ALLOCAN(ir_node*, n_regs);
 	//bp          = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
 	bp          = bipartite_new(n_regs, n_regs);
@@ -288,15 +229,16 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 			DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
 			     partner));
 
-			bitset_clear_all(bs);
-			get_decisive_partner_regs(bs, op, op->partner);
-
-			DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
-			     bs));
+			bitset_t const *const bs = get_decisive_partner_regs(op);
+			if (bs) {
+				DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
 
-			bitset_foreach(bs, col) {
-				//hungarian_add(bp, n_alloc, col, 1);
-				bipartite_add(bp, n_alloc, col);
+				bitset_foreach(bs, col) {
+					//hungarian_add(bp, n_alloc, col, 1);
+					bipartite_add(bp, n_alloc, col);
+				}
+			} else {
+				DBG((dbg, LEVEL_2, "\tallowed registers for %+F: none\n", op->carrier));
 			}
 
 			n_alloc++;
@@ -311,11 +253,12 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 		foreach_out_edge(perm, edge) {
 			int i;
 			ir_node *proj = get_edge_src_irn(edge);
+			be_lv_t *lv   = be_get_irg_liveness(env->irg);
 
 			assert(is_Proj(proj));
 
-			if (!be_values_interfere(env->birg->lv, proj, irn)
-					|| pmap_contains(partners, proj))
+			if (!be_values_interfere(lv, proj, irn)
+			    || pmap_contains(partners, proj))
 				continue;
 
 			/* don't insert a node twice */
@@ -333,10 +276,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 			alloc_nodes[n_alloc] = proj;
 			pmap_insert(partners, proj, NULL);
 
-			bitset_clear_all(bs);
-			arch_put_non_ignore_regs(env->cls, bs);
-			bitset_andnot(bs, env->ignore_colors);
-			bitset_foreach(bs, col) {
+			bitset_foreach(env->allocatable_regs, col) {
 				//hungarian_add(bp, n_alloc, col, 1);
 				bipartite_add(bp, n_alloc, col);
 			}
@@ -351,6 +291,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 	match_res = hungarian_solve(bp, assignment, &cost, 1);
 	assert(match_res == 0 && "matching failed");
 #else
+	/*bipartite_dump_f(stderr, bp);*/
 	bipartite_matching(bp, assignment);
 #endif
 
@@ -359,9 +300,8 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 		const arch_register_t *reg;
 		ir_node *irn;
 
-		assert(assignment[i] >= 0 && "there must have been a register assigned");
+		assert(assignment[i] >= 0 && "there must have been a register assigned (node not register pressure faithful?)");
 		reg = arch_register_for_index(env->cls, assignment[i]);
-		assert(! (reg->type & arch_register_type_ignore));
 
 		irn = alloc_nodes[i];
 		if (irn != NULL) {
@@ -370,7 +310,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 			DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
 		}
 
-		irn = pmap_get(partners, alloc_nodes[i]);
+		irn = pmap_get(ir_node, partners, alloc_nodes[i]);
 		if (irn != NULL) {
 			arch_set_irn_register(irn, reg);
 			(void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
@@ -380,9 +320,8 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 
 	/* Allocate the non-constrained Projs of the Perm. */
 	if (perm != NULL) {
-		bitset_clear_all(bs);
-
 		/* Put the colors of all Projs in a bitset. */
+		bitset_t *const bs = bitset_alloca(n_regs);
 		foreach_out_edge(perm, edge) {
 			ir_node *proj              = get_edge_src_irn(edge);
 			const arch_register_t *reg = arch_get_irn_register(proj);
@@ -399,7 +338,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 			DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
 
 			if (reg == NULL) {
-				col = get_next_free_reg(alloc_env, bs);
+				size_t const col = get_next_free_reg(alloc_env, bs);
 				reg = arch_register_for_index(env->cls, col);
 				bitset_set(bs, reg->index);
 				arch_set_irn_register(proj, reg);
@@ -415,7 +354,6 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 
 end:
 	obstack_free(env->obst, base);
-	return res;
 }
 
 /**
@@ -427,45 +365,31 @@ end:
  */
 static void constraints(ir_node *bl, void *data)
 {
-	/*
-	 * Start silent in the start block.
-	 * The silence remains until the first barrier is seen.
-	 * Each other block is begun loud.
-	 */
-	int                     silent = bl == get_irg_start_block(get_irn_irg(bl));
-	be_chordal_alloc_env_t *env    = data;
+	be_chordal_alloc_env_t *env    = (be_chordal_alloc_env_t*)data;
 	ir_node                *irn;
 
-	/*
-	 * If the block is the start block search the barrier and
-	 * start handling constraints from there.
-	 */
 	for (irn = sched_first(bl); !sched_is_end(irn);) {
-		irn = handle_constraints(env, irn, &silent);
+		ir_node *const next = sched_next(irn);
+		handle_constraints(env, irn);
+		irn = next;
 	}
 }
 
 static void assign(ir_node *block, void *env_ptr)
 {
-	be_chordal_alloc_env_t *alloc_env = env_ptr;
+	be_chordal_alloc_env_t *alloc_env = (be_chordal_alloc_env_t*)env_ptr;
 	be_chordal_env_t *env       = alloc_env->chordal_env;
 	bitset_t *live              = alloc_env->live;
 	bitset_t *colors            = alloc_env->colors;
-	bitset_t *in_colors         = alloc_env->in_colors;
 	struct list_head *head      = get_block_border_head(env, block);
-	be_lv_t *lv                 = env->birg->lv;
-
-	const ir_node *irn;
-	border_t *b;
-	int idx;
+	be_lv_t *lv                 = be_get_irg_liveness(env->irg);
 
 	bitset_clear_all(colors);
 	bitset_clear_all(live);
-	bitset_clear_all(in_colors);
 
 	DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
 	DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
-	list_for_each_entry(border_t, b, head, list) {
+	foreach_border_head(head, b) {
 		DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
 					b->irn, get_irn_idx(b->irn)));
 	}
@@ -475,20 +399,16 @@ static void assign(ir_node *block, void *env_ptr)
 	 * Since their colors have already been assigned (The dominators were
 	 * allocated before), we have to mark their colors as used also.
 	 */
-	be_lv_foreach(lv, block, be_lv_state_in, idx) {
-		irn = be_lv_get_irn(lv, block, idx);
-		if (has_reg_class(env, irn)) {
+	be_lv_foreach(lv, block, be_lv_state_in, irn) {
+		if (arch_irn_consider_in_reg_alloc(env->cls, irn)) {
 			const arch_register_t *reg = arch_get_irn_register(irn);
-			int col;
 
 			assert(reg && "Node must have been assigned a register");
-			col = arch_register_get_index(reg);
-
 			DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
 
 			/* Mark the color of the live in value as used. */
+			int const col = reg->index;
 			bitset_set(colors, col);
-			bitset_set(in_colors, col);
 
 			/* Mark the value live in. */
 			bitset_set(live, get_irn_idx(irn));
@@ -500,7 +420,7 @@ static void assign(ir_node *block, void *env_ptr)
 	 * elimination order. So, coloring the definitions from first to last
 	 * will work.
 	 */
-	list_for_each_entry_reverse(border_t, b, head, list) {
+	foreach_border_head(head, b) {
 		ir_node *irn = b->irn;
 		int nr       = get_irn_idx(irn);
 		int ignore   = arch_irn_is_ignore(irn);
@@ -511,7 +431,7 @@ static void assign(ir_node *block, void *env_ptr)
 		 */
 		if (b->is_def && !be_is_live_in(lv, block, irn)) {
 			const arch_register_t *reg;
-			int col = NO_COLOR;
+			int col;
 
 			if (ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
 				reg = arch_get_irn_register(irn);
@@ -521,71 +441,64 @@ static void assign(ir_node *block, void *env_ptr)
 				col = get_next_free_reg(alloc_env, colors);
 				reg = arch_register_for_index(env->cls, col);
 				assert(arch_get_irn_register(irn) == NULL && "This node must not have been assigned a register yet");
-				assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
 			}
 
 			bitset_set(colors, col);
 			arch_set_irn_register(irn, reg);
 
-			DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
+			DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", reg->name, col, irn));
 
 			assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 			bitset_set(live, nr);
 		} else if (!b->is_def) {
 			/* Clear the color upon a use. */
 			const arch_register_t *reg = arch_get_irn_register(irn);
-			int col;
 
 			assert(reg && "Register must have been assigned");
 
-			col = arch_register_get_index(reg);
-#ifndef NDEBUG
-			if (!arch_register_type_is(reg, ignore)) {
-				assert(bitset_is_set(live, nr) && "Cannot have a non live use");
-			}
-#endif
-
-			bitset_clear(colors, col);
+			bitset_clear(colors, reg->index);
 			bitset_clear(live, nr);
 		}
 	}
 }
 
-void be_ra_chordal_color(be_chordal_env_t *chordal_env)
+static void be_ra_chordal_color(be_chordal_env_t *const chordal_env)
 {
 	be_chordal_alloc_env_t env;
 	char buf[256];
-	be_lv_t *lv;
-	be_irg_t *birg = chordal_env->birg;
 	const arch_register_class_t *cls = chordal_env->cls;
 
-	int colors_n          = arch_register_class_n_regs(cls);
-	ir_graph *irg         = chordal_env->irg;
-
-	lv = be_assure_liveness(birg);
-	be_liveness_assure_sets(lv);
-	be_liveness_assure_chk(lv);
+	int       colors_n = arch_register_class_n_regs(cls);
+	ir_graph *irg      = chordal_env->irg;
 
+	be_assure_live_sets(irg);
 	assure_doms(irg);
 
 	env.chordal_env   = chordal_env;
-	env.colors_n      = colors_n;
 	env.colors        = bitset_alloca(colors_n);
 	env.tmp_colors    = bitset_alloca(colors_n);
-	env.in_colors     = bitset_alloca(colors_n);
 	env.pre_colored   = pset_new_ptr_default();
 
-	BE_TIMER_PUSH(t_constr);
+	be_timer_push(T_SPLIT);
+
+	if (chordal_env->opts->dump_flags & BE_CH_DUMP_SPLIT) {
+		snprintf(buf, sizeof(buf), "%s-split", chordal_env->cls->name);
+		dump_ir_graph(chordal_env->irg, buf);
+	}
+
+	be_timer_pop(T_SPLIT);
+
+	be_timer_push(T_CONSTR);
 
 	/* Handle register targeting constraints */
 	dom_tree_walk_irg(irg, constraints, NULL, &env);
 
 	if (chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
-		snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
-		be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
+		snprintf(buf, sizeof(buf), "%s-constr", chordal_env->cls->name);
+		dump_ir_graph(chordal_env->irg, buf);
 	}
 
-	BE_TIMER_POP(t_constr);
+	be_timer_pop(T_CONSTR);
 
 	env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
 
@@ -607,15 +520,13 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env)
 	del_pset(env.pre_colored);
 }
 
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal)
 void be_init_chordal(void)
 {
-	FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
-
 	static be_ra_chordal_coloring_t coloring = {
 		be_ra_chordal_color
 	};
+	FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
 
 	be_register_chordal_coloring("default", &coloring);
 }
-
-BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);