X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal.c;h=2a71e7967724d033add4bc3c5086971e499ba8f5;hb=df2faee01a5832057bb3ca0ba5f67e979c916e19;hp=221974288bc4c6a5c5d630b3e10ff69007508db2;hpb=d41c19052b32c747b6baf7399bdb7447a9f88810;p=libfirm

diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c
index 221974288..2a71e7967 100644
--- a/ir/be/bechordal.c
+++ b/ir/be/bechordal.c
@@ -25,137 +25,71 @@
  */
 #include "config.h"
 
-#include <ctype.h>
-
-#include "obst.h"
-#include "pset.h"
-#include "list.h"
-#include "bitset.h"
-#include "raw_bitset.h"
-#include "iterator.h"
-#include "bipartite.h"
-#include "hungarian.h"
-
-#include "irmode_t.h"
-#include "irgraph_t.h"
-#include "irprintf_t.h"
-#include "irgwalk.h"
-#include "irdump.h"
-#include "irdom.h"
-#include "irtools.h"
-#include "debug.h"
-#include "iredges.h"
-
-#include "beutil.h"
-#include "besched.h"
-#include "besched.h"
-#include "belive_t.h"
-#include "benode.h"
-#include "bearch.h"
-#include "beirgmod.h"
-#include "beifg.h"
+#include "bechordal_common.h"
+#include "bechordal_draw.h"
+#include "bechordal_t.h"
 #include "beinsn_t.h"
-#include "bestatevent.h"
-#include "beirg.h"
 #include "beintlive_t.h"
-#include "bera.h"
-#include "bechordal_t.h"
-#include "bechordal_draw.h"
+#include "beirg.h"
 #include "bemodule.h"
-#include "bearch.h"
-#include "bechordal_common.h"
-
-DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
+#include "debug.h"
+#include "irdump.h"
 
-#define DUMP_INTERVALS
+#define USE_HUNGARIAN 0
 
-typedef struct be_chordal_alloc_env_t {
-	be_chordal_env_t *chordal_env;
+#if USE_HUNGARIAN
+#include "hungarian.h"
+#else
+#include "bipartite.h"
+#endif
 
-	pset *pre_colored;     /**< Set of precolored nodes. */
-	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. */
-} be_chordal_alloc_env_t;
+DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 
-static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
+static int get_next_free_reg(bitset_t *const available)
 {
-	bitset_t *tmp = alloc_env->tmp_colors;
-	bitset_copy(tmp, colors);
-	bitset_flip_all(tmp);
-	bitset_and(tmp, alloc_env->chordal_env->allocatable_regs);
-	return bitset_next_set(tmp, 0);
+	return bitset_next_set(available, 0);
 }
 
-static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
+static unsigned const *get_decisive_partner_regs(be_operand_t const *const o1, size_t const n_regs)
 {
-	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);
-
-	if (bitset_contains(o1->regs, o2->regs)) {
-		bitset_copy(bs, o1->regs);
-	} else if (bitset_contains(o2->regs, o1->regs)) {
-		bitset_copy(bs, o2->regs);
+	be_operand_t const *const o2 = o1->partner;
+	if (!o2 || rbitset_contains(o1->regs, o2->regs, n_regs)) {
+		return o1->regs;
+	} else if (rbitset_contains(o2->regs, o1->regs, n_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)
+static void pair_up_operands(be_chordal_env_t const *const env, be_insn_t *const insn)
 {
-	const be_chordal_env_t *env = alloc_env->chordal_env;
-	bitset_t               *bs  = bitset_alloca(env->cls->n_regs);
-	int                     i;
-	int                     j;
-
-	/*
-	 * 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) {
-		be_operand_t *smallest        = NULL;
-		int           smallest_n_regs = env->cls->n_regs + 1;
-		be_operand_t *out_op          = &insn->ops[j];
-
+	/* For each out operand, try to find an in operand which can be assigned the
+	 * same register as the out operand. */
+	int       const n_regs = env->cls->n_regs;
+	unsigned *const bs     = rbitset_alloca(n_regs);
+	be_lv_t  *const lv     = be_get_irg_liveness(env->irg);
+	for (int j = 0; j < insn->use_start; ++j) {
 		/* Try to find an in operand which has ... */
-		for (i = insn->use_start; i < insn->n_ops; ++i) {
-			int           n_total;
-			be_operand_t *op = &insn->ops[i];
-			be_lv_t      *lv;
-
-			if (op->partner != NULL)
-				continue;
-			lv = be_get_irg_liveness(env->irg);
-			if (be_values_interfere(lv, op->irn, op->carrier))
+		be_operand_t       *smallest        = NULL;
+		int                 smallest_n_regs = n_regs + 1;
+		be_operand_t *const out_op          = &insn->ops[j];
+		for (int i = insn->use_start; i < insn->n_ops; ++i) {
+			be_operand_t *const op = &insn->ops[i];
+			if (op->partner || be_values_interfere(lv, insn->irn, op->carrier))
 				continue;
 
-			bitset_copy(bs, op->regs);
-			bitset_and(bs, out_op->regs);
-			n_total = bitset_popcount(op->regs);
-
-			if (!bitset_is_empty(bs) && n_total < smallest_n_regs) {
+			rbitset_copy(bs, op->regs, n_regs);
+			rbitset_and(bs, out_op->regs, n_regs);
+			int const n_total = rbitset_popcount(op->regs, n_regs);
+			if (!rbitset_is_empty(bs, n_regs) && n_total < smallest_n_regs) {
 				smallest        = op;
 				smallest_n_regs = n_total;
 			}
 		}
 
 		if (smallest != NULL) {
-			for (i = insn->use_start; i < insn->n_ops; ++i) {
+			for (int i = insn->use_start; i < insn->n_ops; ++i) {
 				if (insn->ops[i].carrier == smallest->carrier)
 					insn->ops[i].partner = out_op;
 			}
@@ -166,141 +100,110 @@ static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t
 	}
 }
 
-static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
-                                   ir_node *irn)
+static bool list_contains_irn(ir_node *const *const list, size_t const n, ir_node *const irn)
 {
-	int n_regs;
-	bitset_t *bs;
-	ir_node **alloc_nodes;
-	//hungarian_problem_t *bp;
-	int *assignment;
-	pmap *partners;
-	int i, n_alloc;
-	size_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;
-	bipartite_t *bp;
-
-	if (insn->pre_colored) {
-		int i;
-		for (i = 0; i < insn->use_start; ++i)
-			pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
+	for (ir_node *const *i = list; i != list + n; ++i) {
+		if (*i == irn)
+			return true;
 	}
+	return false;
+}
 
-	/*
-	 * 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 || is_Phi(irn))
-		goto end;
+static void handle_constraints(be_chordal_env_t *const env, ir_node *const irn)
+{
+	void *const base = obstack_base(&env->obst);
+	be_insn_t  *insn = be_scan_insn(env, irn);
 
-	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);
-	assignment  = ALLOCAN(int, n_regs);
-	partners    = pmap_create();
+	/* Perms inserted before the constraint handling phase are considered to be
+	 * correctly precolored. These Perms arise during the ABI handling phase. */
+	if (!insn || is_Phi(irn))
+		goto end;
 
-	/*
-	 * prepare the constraint handling of this node.
+	/* Prepare the constraint handling of this node.
 	 * Perms are constructed and Copies are created for constrained values
-	 * interfering with the instruction.
-	 */
-	perm = pre_process_constraints(alloc_env->chordal_env, &insn);
+	 * interfering with the instruction. */
+	ir_node *const perm = pre_process_constraints(env, &insn);
 
 	/* find suitable in operands to the out operands of the node. */
-	pair_up_operands(alloc_env, insn);
-
-	/*
-	 * look at the in/out operands and add each operand (and its possible partner)
-	 * to a bipartite graph (left: nodes with partners, right: admissible colors).
-	 */
-	for (i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
-		be_operand_t *op = &insn->ops[i];
-
-		/*
-		 * If the operand has no partner or the partner has not been marked
+	pair_up_operands(env, insn);
+
+	/* Look at the in/out operands and add each operand (and its possible partner)
+	 * to a bipartite graph (left: nodes with partners, right: admissible colors). */
+	int                        n_alloc     = 0;
+	int                  const n_regs      = env->cls->n_regs;
+	ir_node            **const alloc_nodes = ALLOCAN(ir_node*, n_regs);
+	pmap                *const partners    = pmap_create();
+#if USE_HUNGARIAN
+	hungarian_problem_t *const bp          = hungarian_new(n_regs, n_regs, HUNGARIAN_MATCH_PERFECT);
+#else
+	bipartite_t         *const bp          = bipartite_new(n_regs, n_regs);
+#endif
+	for (int i = 0; i < insn->n_ops; ++i) {
+		/* If the operand has no partner or the partner has not been marked
 		 * for allocation, determine the admissible registers and mark it
 		 * for allocation by associating the node and its partner with the
-		 * set of admissible registers via a bipartite graph.
-		 */
-		if (!op->partner || !pmap_contains(partners, op->partner->carrier)) {
-			ir_node *partner = op->partner ? op->partner->carrier : NULL;
-			int i;
-
-			pmap_insert(partners, op->carrier, partner);
-			if (partner != NULL)
-				pmap_insert(partners, partner, op->carrier);
-
-			/* don't insert a node twice */
-			for (i = 0; i < n_alloc; ++i) {
-				if (alloc_nodes[i] == op->carrier) {
-					break;
-				}
-			}
-			if (i < n_alloc)
-				continue;
+		 * set of admissible registers via a bipartite graph. */
+		be_operand_t *const op = &insn->ops[i];
+		if (op->partner && pmap_contains(partners, op->partner->carrier))
+			continue;
+
+		ir_node *const partner = op->partner ? op->partner->carrier : NULL;
+		pmap_insert(partners, op->carrier, partner);
+		if (partner != NULL)
+			pmap_insert(partners, partner, op->carrier);
 
-			alloc_nodes[n_alloc] = op->carrier;
+		/* Don't insert a node twice. */
+		if (list_contains_irn(alloc_nodes, n_alloc, op->carrier))
+			continue;
 
-			DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
-			     partner));
+		alloc_nodes[n_alloc] = op->carrier;
 
-			bitset_clear_all(bs);
-			get_decisive_partner_regs(bs, op, op->partner);
+		DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, partner));
 
-			DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
-			     bs));
+		unsigned const *const bs = get_decisive_partner_regs(op, n_regs);
+		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);
+			rbitset_foreach(bs, n_regs, col) {
+#if USE_HUNGARIAN
+				hungarian_add(bp, n_alloc, col, 1);
+#else
 				bipartite_add(bp, n_alloc, col);
+#endif
 			}
-
-			n_alloc++;
+		} else {
+			DBG((dbg, LEVEL_2, "\tallowed registers for %+F: none\n", op->carrier));
 		}
+
+		n_alloc++;
 	}
 
-	/*
-	 * Put all nodes which live through the constrained instruction also to the
-	 * allocation bipartite graph. They are considered unconstrained.
-	 */
+	/* Put all nodes which live through the constrained instruction also to the
+	 * allocation bipartite graph. They are considered unconstrained. */
 	if (perm != NULL) {
+		be_lv_t *const lv = be_get_irg_liveness(env->irg);
 		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);
-
+			ir_node *const proj = get_edge_src_irn(edge);
 			assert(is_Proj(proj));
 
-			if (!be_values_interfere(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 */
-			for (i = 0; i < n_alloc; ++i) {
-				if (alloc_nodes[i] == proj) {
-					break;
-				}
-			}
-			if (i < n_alloc)
+			/* Don't insert a node twice. */
+			if (list_contains_irn(alloc_nodes, n_alloc, proj))
 				continue;
 
-
 			assert(n_alloc < n_regs);
 
 			alloc_nodes[n_alloc] = proj;
 			pmap_insert(partners, proj, NULL);
 
 			bitset_foreach(env->allocatable_regs, col) {
-				//hungarian_add(bp, n_alloc, col, 1);
+#if USE_HUNGARIAN
+				hungarian_add(bp, n_alloc, col, 1);
+#else
 				bipartite_add(bp, n_alloc, col);
+#endif
 			}
 
 			n_alloc++;
@@ -308,76 +211,72 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 	}
 
 	/* Compute a valid register allocation. */
-#if 0
+	int *const assignment = ALLOCAN(int, n_regs);
+#if USE_HUNGARIAN
 	hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
-	match_res = hungarian_solve(bp, assignment, &cost, 1);
+	int const match_res = hungarian_solve(bp, assignment, NULL, 1);
 	assert(match_res == 0 && "matching failed");
 #else
-	/*bipartite_dump_f(stderr, bp);*/
 	bipartite_matching(bp, assignment);
 #endif
 
 	/* Assign colors obtained from the matching. */
-	for (i = 0; i < n_alloc; ++i) {
-		const arch_register_t *reg;
-		ir_node *irn;
-
+	for (int i = 0; i < n_alloc; ++i) {
 		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]);
+		arch_register_t const *const reg = arch_register_for_index(env->cls, assignment[i]);
 
-		irn = alloc_nodes[i];
+		ir_node *const irn = alloc_nodes[i];
 		if (irn != NULL) {
 			arch_set_irn_register(irn, reg);
-			(void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
 			DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
 		}
 
-		irn = (ir_node*)pmap_get(partners, alloc_nodes[i]);
-		if (irn != NULL) {
-			arch_set_irn_register(irn, reg);
-			(void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
-			DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
+		ir_node *const partner = pmap_get(ir_node, partners, alloc_nodes[i]);
+		if (partner != NULL) {
+			arch_set_irn_register(partner, reg);
+			DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", partner, reg->name));
 		}
 	}
 
 	/* Allocate the non-constrained Projs of the Perm. */
 	if (perm != NULL) {
-		bitset_clear_all(bs);
+		bitset_t *const available = bitset_alloca(n_regs);
+		bitset_copy(available, env->allocatable_regs);
 
 		/* Put the colors of all Projs in a bitset. */
 		foreach_out_edge(perm, edge) {
-			ir_node *proj              = get_edge_src_irn(edge);
-			const arch_register_t *reg = arch_get_irn_register(proj);
-
+			ir_node               *const proj = get_edge_src_irn(edge);
+			arch_register_t const *const reg  = arch_get_irn_register(proj);
 			if (reg != NULL)
-				bitset_set(bs, reg->index);
+				bitset_clear(available, reg->index);
 		}
 
 		/* Assign the not yet assigned Projs of the Perm a suitable color. */
 		foreach_out_edge(perm, edge) {
-			ir_node *proj              = get_edge_src_irn(edge);
-			const arch_register_t *reg = arch_get_irn_register(proj);
+			ir_node               *const proj = get_edge_src_irn(edge);
+			arch_register_t const *const reg  = arch_get_irn_register(proj);
 
 			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);
-				reg = arch_register_for_index(env->cls, col);
-				bitset_set(bs, reg->index);
-				arch_set_irn_register(proj, reg);
-				pset_insert_ptr(alloc_env->pre_colored, proj);
-				DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
+				size_t const col = get_next_free_reg(available);
+				arch_register_t const *const new_reg = arch_register_for_index(env->cls, col);
+				bitset_clear(available, new_reg->index);
+				arch_set_irn_register(proj, new_reg);
+				DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, new_reg->name));
 			}
 		}
 	}
 
+#if USE_HUNGARIAN
+	hungarian_free(bp);
+#else
 	bipartite_free(bp);
-	//hungarian_free(bp);
+#endif
 	pmap_destroy(partners);
 
 end:
-	obstack_free(env->obst, base);
-	return res;
+	obstack_free(&env->obst, base);
 }
 
 /**
@@ -387,174 +286,108 @@ end:
  * of the constrained node. These Perms signal a constrained node.
  * For further comments, refer to handle_constraints().
  */
-static void constraints(ir_node *bl, void *data)
+static void constraints(ir_node *const bl, void *const data)
 {
-	be_chordal_alloc_env_t *env    = (be_chordal_alloc_env_t*)data;
-	ir_node                *irn;
-
-	for (irn = sched_first(bl); !sched_is_end(irn);) {
-		irn = handle_constraints(env, irn);
+	be_chordal_env_t *const env = (be_chordal_env_t*)data;
+	for (ir_node *irn = sched_first(bl); !sched_is_end(irn);) {
+		ir_node *const next = sched_next(irn);
+		handle_constraints(env, irn);
+		irn = next;
 	}
 }
 
-static void assign(ir_node *block, void *env_ptr)
+static void assign(ir_node *const block, void *const 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                 = be_get_irg_liveness(env->irg);
-
-	const ir_node *irn;
-	border_t *b;
-	int idx;
-
-	bitset_clear_all(colors);
-	bitset_clear_all(live);
-	bitset_clear_all(in_colors);
+	be_chordal_env_t *const env  = (be_chordal_env_t*)env_ptr;
+	struct list_head *const head = get_block_border_head(env, block);
+	be_lv_t          *const lv   = be_get_irg_liveness(env->irg);
 
 	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)));
 	}
 
-	/*
-	 * Add initial defs for all values live in.
-	 * 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)) {
-			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);
+	bitset_t *const available = bitset_alloca(env->allocatable_regs->size);
+	bitset_copy(available, env->allocatable_regs);
 
-			DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
+	/* Add initial defs for all values live in.
+	 * Since their colors have already been assigned (The dominators were
+	 * allocated before), we have to mark their colors as used also. */
+	be_lv_foreach_cls(lv, block, be_lv_state_in, env->cls, irn) {
+		arch_register_t const *const reg = arch_get_irn_register(irn);
 
-			/* Mark the color of the live in value as used. */
-			bitset_set(colors, col);
-			bitset_set(in_colors, col);
+		assert(reg && "Node must have been assigned a register");
+		DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
 
-			/* Mark the value live in. */
-			bitset_set(live, get_irn_idx(irn));
-		}
+		/* Mark the color of the live in value as used. */
+		bitset_clear(available, reg->index);
 	}
 
-	/*
-	 * Mind that the sequence of defs from back to front defines a perfect
+	/* Mind that the sequence of defs from back to front defines a perfect
 	 * elimination order. So, coloring the definitions from first to last
-	 * will work.
-	 */
-	list_for_each_entry_reverse(border_t, b, head, list) {
-		ir_node *irn = b->irn;
-		int nr       = get_irn_idx(irn);
-		int ignore   = arch_irn_is_ignore(irn);
-
-		/*
-		 * Assign a color, if it is a local def. Global defs already have a
-		 * color.
-		 */
-		if (b->is_def && !be_is_live_in(lv, block, irn)) {
-			const arch_register_t *reg;
-			int col;
-
-			if (ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
-				reg = arch_get_irn_register(irn);
+	 * will work. */
+	foreach_border_head(head, b) {
+		ir_node *const irn = b->irn;
+
+		/* Assign a color, if it is a local def. Global defs already have a
+		 * color. */
+		if (!b->is_def) {
+			/* Make the color available upon a use. */
+			arch_register_t const *const reg = arch_get_irn_register(irn);
+			assert(reg && "Register must have been assigned");
+			bitset_set(available, reg->index);
+		} else if (!be_is_live_in(lv, block, irn)) {
+			int                    col;
+			arch_register_t const *reg = arch_get_irn_register(irn);
+			if (reg) {
 				col = reg->index;
-				assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
+				assert(bitset_is_set(available, col) && "pre-colored register must be free");
 			} else {
-				col = get_next_free_reg(alloc_env, colors);
+				assert(!arch_irn_is_ignore(irn));
+				col = get_next_free_reg(available);
 				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");
+				arch_set_irn_register(irn, reg);
 			}
+			bitset_clear(available, col);
 
-			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));
-
-			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);
-
-			bitset_clear(colors, col);
-			bitset_clear(live, nr);
+			DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", reg->name, col, irn));
 		}
 	}
 }
 
-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];
-	const arch_register_class_t *cls = chordal_env->cls;
-
-	int       colors_n = arch_register_class_n_regs(cls);
-	ir_graph *irg      = chordal_env->irg;
-
+	char            buf[256];
+	ir_graph *const 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_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);
+	dom_tree_walk_irg(irg, constraints, NULL, chordal_env);
 
 	if (chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
 		snprintf(buf, sizeof(buf), "%s-constr", chordal_env->cls->name);
-		dump_ir_graph(chordal_env->irg, buf);
+		dump_ir_graph(irg, buf);
 	}
 
 	be_timer_pop(T_CONSTR);
 
-	env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
-
 	/* First, determine the pressure */
-	dom_tree_walk_irg(irg, create_borders, NULL, env.chordal_env);
+	dom_tree_walk_irg(irg, create_borders, NULL, chordal_env);
 
 	/* Assign the colors */
-	dom_tree_walk_irg(irg, assign, NULL, &env);
+	dom_tree_walk_irg(irg, assign, NULL, chordal_env);
 
 	if (chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
-		plotter_t *plotter;
 		ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
-		plotter = new_plotter_ps(buf);
+		plotter_t *const plotter = new_plotter_ps(buf);
 		draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
 		plotter_free(plotter);
 	}
-
-	bitset_free(env.live);
-	del_pset(env.pre_colored);
 }
 
 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal)