fehler109
[libfirm] / ir / be / becopyheur4.c
index d08819f..c95106b 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
  *
  * This file is part of libFirm.
  *
@@ -78,36 +78,38 @@ static firm_dbg_module_t *dbg = NULL;
 
 #endif
 
+typedef float real_t;
+#define REAL(C)   (C ## f)
+
 static int last_chunk_id        = 0;
 static int recolor_limit        = 4;
-static double dislike_influence = 0.1;
+static real_t dislike_influence = REAL(0.1);
 
 typedef struct _col_cost_t {
-       int    col;
-       double cost;
+       int     col;
+       real_t  cost;
 } col_cost_t;
 
 /**
  * An affinity chunk.
  */
 typedef struct _aff_chunk_t {
-       ir_node    **n;                   /**< An ARR_F containing all nodes of the chunk. */
-       bitset_t   *nodes;                /**< A bitset containing all nodes inside this chunk. */
-       bitset_t   *interfere;            /**< A bitset containing all interfering neighbours of the nodes in this chunk. */
-       int        weight;                /**< Weight of this chunk */
-       unsigned   weight_consistent : 1; /**< Set if the weight is consistent. */
-       unsigned   deleted           : 1; /**< Set if the was deleted. */
-       int        id;                    /**< For debugging: An id of this chunk. */
-       int        visited;
-       col_cost_t *color_affinity;
+       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. */
+       int              id;                    /**< An id of this chunk. */
+       int              visited;
+       col_cost_t       color_affinity[1];
 } aff_chunk_t;
 
 /**
  * An affinity edge.
  */
 typedef struct _aff_edge_t {
-       ir_node *src;                   /**< Source node. */
-       ir_node *tgt;                   /**< Target node. */
+       const ir_node *src;                   /**< Source node. */
+       const ir_node *tgt;                   /**< Target node. */
        double  weight;                 /**< The weight of this edge. */
 } aff_edge_t;
 
@@ -128,7 +130,7 @@ typedef struct _co_mst_env_t {
 
 /* stores coalescing related information for a node */
 typedef struct _co_mst_irn_t {
-       ir_node          *irn;              /**< the irn this information belongs to */
+       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 */
        ir_node          **int_neighs;      /**< array of all interfering neighbours (cached for speed reasons) */
@@ -139,7 +141,7 @@ typedef struct _co_mst_irn_t {
        int              tmp_col;           /**< a temporary assigned color */
        unsigned         fixed     : 1;     /**< the color is fixed */
        struct list_head list;              /**< Queue for coloring undo. */
-       double           constr_factor;
+       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)))
@@ -152,12 +154,13 @@ typedef int decide_func_t(const co_mst_irn_t *node, int col);
  * Write a chunk to stderr for debugging.
  */
 static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) {
-       bitset_pos_t idx;
+       int i, l;
+       (void) env;
        if (c->weight_consistent)
                ir_fprintf(stderr, " $%d ", c->weight);
        ir_fprintf(stderr, "{");
-       bitset_foreach(c->nodes, idx) {
-               ir_node *n = get_idx_irn(env->co->irg, idx);
+       for (i = 0, l = ARR_LEN(c->n); i < l; ++i) {
+               const ir_node *n = c->n[i];
                ir_fprintf(stderr, " %+F,", n);
        }
        ir_fprintf(stderr, "}");
@@ -173,8 +176,9 @@ static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *n
        if (bitset_popcnt(node->adm_colors) < 1)
                fprintf(stderr, "no admissible colors?!?");
        else {
-               bitset_foreach(node->adm_colors, idx)
+               bitset_foreach(node->adm_colors, idx) {
                        fprintf(stderr, " %d", idx);
+               }
        }
 }
 
@@ -235,14 +239,14 @@ static int cmp_aff_edge(const void *a, const void *b) {
 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;
-       double diff = c1->cost - c2->cost;
+       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;
-       double diff = c2->cost - c1->cost;
+       real_t diff = c2->cost - c1->cost;
        return (diff > 0) - (diff < 0);
 }
 
@@ -250,14 +254,13 @@ static int cmp_col_cost_gt(const void *a, const void *b) {
  * Creates a new affinity chunk
  */
 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
-       aff_chunk_t *c = xmalloc(sizeof(*c));
+       aff_chunk_t *c = xmalloc(sizeof(*c) + (env->n_regs - 1) * sizeof(c->color_affinity[0]));
+       c->n                 = NEW_ARR_F(const ir_node *, 0);
+       c->interfere         = NEW_ARR_F(const ir_node *, 0);
        c->weight            = -1;
        c->weight_consistent = 0;
-       c->n                 = NEW_ARR_F(ir_node *, 0);
-       c->nodes             = bitset_irg_malloc(env->co->irg);
-       c->interfere         = bitset_irg_malloc(env->co->irg);
-       c->color_affinity    = xmalloc(env->n_regs * sizeof(c->color_affinity[0]));
-       c->id                = last_chunk_id++;
+       c->deleted           = 0;
+       c->id                = ++last_chunk_id;
        c->visited           = 0;
        pset_insert(env->chunkset, c, c->id);
        return c;
@@ -268,39 +271,89 @@ static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
  */
 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
        pset_remove(env->chunkset, c, c->id);
-       bitset_free(c->nodes);
-       bitset_free(c->interfere);
-       xfree(c->color_affinity);
+       DEL_ARR_F(c->interfere);
        DEL_ARR_F(c->n);
        c->deleted = 1;
        free(c);
 }
 
+/**
+ * binary search of sorted nodes.
+ *
+ * @return the position where n is found in the array arr or ~pos
+ * if the nodes is not here.
+ */
+static INLINE int nodes_bsearch(const ir_node **arr, const ir_node *n) {
+       int hi = ARR_LEN(arr);
+       int lo = 0;
+
+       while (lo < hi) {
+               int md = lo + ((hi - lo) >> 1);
+
+               if (arr[md] == n)
+                       return md;
+               if (arr[md] < n)
+                       lo = md + 1;
+               else
+                       hi = md;
+       }
+
+       return ~lo;
+}
+
+/** Check if a node n can be found inside arr. */
+static int node_contains(const ir_node **arr, const ir_node *n) {
+       int i = nodes_bsearch(arr, n);
+       return i >= 0;
+}
+
+/**
+ * Insert a node into the sorted nodes list.
+ *
+ * @return 1 if the node was inserted, 0 else
+ */
+static int nodes_insert(const ir_node ***arr, const ir_node *irn) {
+       int idx = nodes_bsearch(*arr, irn);
+
+       if (idx < 0) {
+               int i, n = ARR_LEN(*arr);
+               const ir_node **l;
+
+               ARR_APP1(const ir_node *, *arr, irn);
+
+               /* move it */
+               idx = ~idx;
+               l = *arr;
+               for (i = n - 1; i >= idx; --i)
+                       l[i + 1] = l[i];
+               l[idx] = irn;
+               return 1;
+       }
+       return 0;
+}
+
 /**
  * Adds a node to an affinity chunk
  */
 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
        int i;
 
-       if (bitset_is_set(c->nodes, get_irn_idx(node->irn)))
+       if (! nodes_insert(&c->n, node->irn))
                return;
 
        c->weight_consistent = 0;
        node->chunk          = c;
-       bitset_set(c->nodes, get_irn_idx(node->irn));
-
-       ARR_APP1(ir_node *, c->n, node->irn);
 
        for (i = node->n_neighs - 1; i >= 0; --i) {
                ir_node *neigh = node->int_neighs[i];
-               bitset_set(c->interfere, get_irn_idx(neigh));
+               nodes_insert(&c->interfere, neigh);
        }
 }
 
 /**
  * In case there is no phase information for irn, initialize it.
  */
-static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
+static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old) {
        co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
        co_mst_env_t *env = ph->priv;
 
@@ -336,7 +389,7 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
                bitset_andnot(res->adm_colors, env->ignore_regs);
 
                /* compute the constraint factor */
-               res->constr_factor = (double) (1 + env->n_regs - bitset_popcnt(res->adm_colors)) / env->n_regs;
+               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;
@@ -358,32 +411,37 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
 /**
  * Check if affinity chunk @p chunk interferes with node @p irn.
  */
-static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, ir_node *irn) {
-       (void) env;
-       return bitset_is_set(chunk->interfere, get_irn_idx(irn));
+static INLINE int aff_chunk_interferes(const aff_chunk_t *chunk, const ir_node *irn) {
+       return node_contains(chunk->interfere, irn);
 }
 
 /**
  * Check if there are interference edges from c1 to c2.
- * @param env   The global co_mst environment
  * @param c1    A chunk
  * @param c2    Another chunk
  * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
  */
-static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) {
-       (void) env;
+static INLINE int aff_chunks_interfere(const aff_chunk_t *c1, const aff_chunk_t *c2) {
+       int i;
+
        if (c1 == c2)
                return 0;
 
        /* check if there is a node in c2 having an interfering neighbor in c1 */
-       return bitset_intersect(c1->interfere, c2->nodes);
+       for (i = ARR_LEN(c2->n) - 1; i >= 0; --i) {
+               const ir_node *irn = c2->n[i];
+
+               if (node_contains(c1->interfere, irn))
+                       return 1;
+       }
+       return 0;
 }
 
 /**
  * Returns the affinity chunk of @p irn or creates a new
  * one with @p irn as element if there is none assigned.
  */
-static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
+static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, const ir_node *irn) {
        co_mst_irn_t *node = get_co_mst_irn(env, irn);
        return node->chunk;
 }
@@ -393,7 +451,7 @@ static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
  * are no interference edges from chunk(src) to chunk(tgt)).
  * @return 1 if successful, 0 if not possible
  */
-static int aff_chunk_absorb(co_mst_env_t *env, ir_node *src, ir_node *tgt) {
+static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node *tgt) {
        aff_chunk_t *c1 = get_aff_chunk(env, src);
        aff_chunk_t *c2 = get_aff_chunk(env, tgt);
 
@@ -432,24 +490,28 @@ static int aff_chunk_absorb(co_mst_env_t *env, ir_node *src, ir_node *tgt) {
                        }
                } else {
                        /* c2 already exists */
-                       if (! aff_chunk_interferes(env, c2, src)) {
+                       if (! aff_chunk_interferes(c2, src)) {
                                aff_chunk_add_node(c2, get_co_mst_irn(env, src));
                                goto absorbed;
                        }
                }
        } else if (c2 == NULL) {
                /* c1 already exists */
-               if (! aff_chunk_interferes(env, c1, tgt)) {
+               if (! aff_chunk_interferes(c1, tgt)) {
                        aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
                        goto absorbed;
                }
-       } else if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
+       } else if (c1 != c2 && ! aff_chunks_interfere(c1, c2)) {
                int idx, len;
 
                for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx)
                        aff_chunk_add_node(c1, get_co_mst_irn(env, c2->n[idx]));
 
-               bitset_or(c1->interfere, c2->interfere);
+               for (idx = 0, len = ARR_LEN(c2->interfere); idx < len; ++idx) {
+                       const ir_node *irn = c2->interfere[idx];
+                       nodes_insert(&c1->interfere, irn);
+               }
+
                c1->weight_consistent = 0;
 
                delete_aff_chunk(env, c2);
@@ -473,16 +535,16 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
 
                for (i = 0; i < env->n_regs; ++i) {
                        c->color_affinity[i].col = i;
-                       c->color_affinity[i].cost = 0.0;
+                       c->color_affinity[i].cost = REAL(0.0);
                }
 
                for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
-                       ir_node               *n       = c->n[idx];
+                       const ir_node         *n       = c->n[idx];
                        const affinity_node_t *an      = get_affinity_info(env->co, n);
                        co_mst_irn_t          *node    = get_co_mst_irn(env, n);
 
                        node->chunk = c;
-                       if (node->constr_factor > 0.0) {
+                       if (node->constr_factor > REAL(0.0)) {
                                bitset_pos_t col;
                                bitset_foreach (node->adm_colors, col)
                                        c->color_affinity[col].cost += node->constr_factor;
@@ -492,19 +554,18 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
                                neighb_t *neigh;
                                co_gs_foreach_neighb(an, neigh) {
                                        const ir_node *m    = neigh->irn;
-                                       const int     m_idx = get_irn_idx(m);
 
                                        /* skip ignore nodes */
                                        if (arch_irn_is(env->aenv, m, ignore))
                                                continue;
 
-                                       w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
+                                       w += node_contains(c->n, m) ? neigh->costs : 0;
                                }
                        }
                }
 
                for (i = 0; i < env->n_regs; ++i)
-                       c->color_affinity[i].cost *= (1.0 / ARR_LEN(c->n));
+                       c->color_affinity[i].cost *= (REAL(1.0) / ARR_LEN(c->n));
 
                c->weight            = w;
                // c->weight            = bitset_popcnt(c->nodes);
@@ -517,7 +578,7 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
  */
 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
        const neighb_t     *neigh;
-       ir_node            *irn  = an->irn;
+       const ir_node      *irn  = an->irn;
        const co_mst_irn_t *node = get_co_mst_irn(env, irn);
        int                res   = 0;
 
@@ -576,8 +637,8 @@ static void build_affinity_chunks(co_mst_env_t *env) {
 
                        /* build the affinity edges */
                        co_gs_foreach_neighb(an, neigh) {
-                               ir_node *m    = neigh->irn;
-                               int     m_idx = get_irn_idx(m);
+                               const ir_node *m     = neigh->irn;
+                               int            m_idx = get_irn_idx(m);
 
                                /* record the edge in only one direction */
                                if (n_idx < m_idx) {
@@ -626,6 +687,7 @@ static void build_affinity_chunks(co_mst_env_t *env) {
 
                pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
        }
+
        foreach_phase_irn(&env->ph, n) {
                co_mst_irn_t *mirn = get_co_mst_irn(env, n);
 
@@ -650,13 +712,13 @@ static void build_affinity_chunks(co_mst_env_t *env) {
 static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
 {
        pqueue *grow = new_pqueue();
-       int i;
+       const ir_node *max_node = NULL;
        int max_weight = 0;
-       ir_node *max_node = NULL;
+       int i;
 
        for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) {
-               ir_node *irn        = chunk->n[i];
-               affinity_node_t *an = get_affinity_info(env->co, irn);
+               const ir_node   *irn = chunk->n[i];
+               affinity_node_t *an  = get_affinity_info(env->co, irn);
                int w = 0;
                neighb_t *neigh;
 
@@ -680,7 +742,7 @@ static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chu
                for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i)
                        bitset_add_irn(visited, chunk->n[i]);
 
-               pqueue_put(grow, max_node, max_weight);
+               pqueue_put(grow, (void *) max_node, max_weight);
                bitset_remv_irn(visited, max_node);
                i = 0;
                while (!pqueue_empty(grow)) {
@@ -701,7 +763,7 @@ static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chu
                                co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn);
 
                                if (bitset_contains_irn(visited, node->irn)) {
-                                       pqueue_put(grow, neigh->irn, neigh->costs);
+                                       pqueue_put(grow, (void *) neigh->irn, neigh->costs);
                                        bitset_remv_irn(visited, node->irn);
                                }
                        }
@@ -737,8 +799,8 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v
                if (an != NULL) {
                        neighb_t *neigh;
                        co_gs_foreach_neighb(an, neigh) {
-                               ir_node      *m    = neigh->irn;
-                               int          m_idx = get_irn_idx(m);
+                               const ir_node *m    = neigh->irn;
+                               int            m_idx = get_irn_idx(m);
                                co_mst_irn_t *n2;
 
                                /* skip ignore nodes */
@@ -747,11 +809,11 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v
 
                                n2 = get_co_mst_irn(env, m);
 
-                               if (! bitset_is_set(visited, m_idx)       &&
-                                       decider(n2, col)                      &&
-                                       ! n2->fixed                           &&
-                                       ! aff_chunk_interferes(env, chunk, m) &&
-                                       bitset_is_set(orig_chunk->nodes, m_idx))
+                               if (! bitset_is_set(visited, m_idx)  &&
+                                       decider(n2, col)                 &&
+                                       ! n2->fixed                      &&
+                                       ! aff_chunk_interferes(chunk, m) &&
+                                       node_contains(orig_chunk->n, m))
                                {
                                        /*
                                                following conditions are met:
@@ -785,7 +847,7 @@ static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, w
        aff_chunk_t *best = NULL;
 
        for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
-               ir_node       *irn;
+               const ir_node *irn;
                co_mst_irn_t  *node;
                aff_chunk_t   *tmp_chunk;
                decide_func_t *decider;
@@ -812,7 +874,7 @@ static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, w
                tmp_chunk = new_aff_chunk(env);
                waitq_put(tmp, tmp_chunk);
                expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
-               assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
+               assert(ARR_LEN(tmp_chunk->n) > 0 && "No nodes added to chunk");
 
                /* remember the local best */
                aff_chunk_assure_weight(env, tmp_chunk);
@@ -874,13 +936,13 @@ static INLINE int is_loose(co_mst_irn_t *node)
 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
        int *neigh_cols = alloca(env->n_regs * sizeof(*neigh_cols));
        int n_loose = 0;
-       double coeff;
+       real_t coeff;
        int i;
 
        for (i = 0; i < env->n_regs; ++i) {
                neigh_cols[i] = 0;
                costs[i].col = i;
-               costs[i].cost = bitset_is_set(node->adm_colors, i) ? node->constr_factor : 0.0;
+               costs[i].cost = bitset_is_set(node->adm_colors, i) ? node->constr_factor : REAL(0.0);
        }
 
        for (i = 0; i < node->n_neighs; ++i) {
@@ -889,16 +951,14 @@ static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cos
                if (is_loose(n)) {
                        ++n_loose;
                        ++neigh_cols[col];
-               }
-
-               else
-                       costs[col].cost = 0.0;
+               } else
+                       costs[col].cost = REAL(0.0);
        }
 
        if (n_loose > 0) {
-               coeff = 1.0 / n_loose;
+               coeff = REAL(1.0) / n_loose;
                for (i = 0; i < env->n_regs; ++i)
-                       costs[i].cost *= 1.0 - coeff * neigh_cols[i];
+                       costs[i].cost *= REAL(1.0) - coeff * neigh_cols[i];
        }
 }
 
@@ -928,7 +988,7 @@ static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int
                determine_color_costs(env, node, costs);
 
                /* Since the node must not have the not_col, set the costs for that color to "infinity" */
-               costs[exclude_col].cost = 0.0;
+               costs[exclude_col].cost = REAL(0.0);
 
                /* sort the colors according costs, cheapest first. */
                qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost_gt);
@@ -966,7 +1026,7 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost
                int j;
 
                /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
-               if (costs[i].cost == 0.0)
+               if (costs[i].cost == REAL(0.0))
                        return 0;
 
                /* Set the new color of the node and mark the node as temporarily fixed. */
@@ -1087,9 +1147,8 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
        waitq       *best_starts  = NULL;
        col_cost_t  *order        = alloca(env->n_regs * sizeof(order[0]));
        bitset_t    *visited;
-       int         idx, len, i;
+       int         idx, len, i, nidx, pos;
        struct list_head changed;
-       bitset_pos_t pos;
 
        DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
        DBG_AFF_CHUNK(env, LEVEL_2, c);
@@ -1102,12 +1161,13 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
        /* compute color preference */
        memset(order, 0, env->n_regs * sizeof(order[0]));
 
-       bitset_foreach (c->interfere, pos) {
-               ir_node      *n    = get_idx_irn(env->co->irg, pos);
+       for (pos = 0, len = ARR_LEN(c->interfere); pos < len; ++pos) {
+               const ir_node *n = c->interfere[pos];
                co_mst_irn_t *node = get_co_mst_irn(env, n);
                aff_chunk_t *chunk = node->chunk;
 
-               if (is_loose(node) && chunk && chunk->visited < env->chunk_visited && !chunk->deleted) {
+               if (is_loose(node) && chunk && chunk->visited < env->chunk_visited) {
+                       assert(!chunk->deleted);
                        chunk->visited = env->chunk_visited;
                        ++n_int_chunks;
 
@@ -1118,9 +1178,9 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
        }
 
        for (i = 0; i < env->n_regs; ++i) {
-               double dislike = n_int_chunks > 0 ? 1.0 - order[i].cost / n_int_chunks : 0.0;
+               real_t dislike = n_int_chunks > 0 ? REAL(1.0) - order[i].cost / n_int_chunks : REAL(0.0);
                order[i].col  = i;
-               order[i].cost = (1.0 - dislike_influence) * c->color_affinity[i].cost + dislike_influence * dislike;
+               order[i].cost = (REAL(1.0) - dislike_influence) * c->color_affinity[i].cost + dislike_influence * dislike;
        }
 
        qsort(order, env->n_regs, sizeof(order[0]), cmp_col_cost_gt);
@@ -1152,7 +1212,7 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 
                /* try to bring all nodes of given chunk to the current color. */
                for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
-                       ir_node         *irn  = c->n[idx];
+                       const ir_node   *irn  = c->n[idx];
                        co_mst_irn_t    *node = get_co_mst_irn(env, irn);
                        int              good;
 
@@ -1244,8 +1304,8 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
        DB((dbg, LEVEL_2, "using color %d\n", best_color));
 
        for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
-               ir_node      *irn  = best_chunk->n[idx];
-               co_mst_irn_t *node = get_co_mst_irn(env, irn);
+               const ir_node *irn  = best_chunk->n[idx];
+               co_mst_irn_t  *node = get_co_mst_irn(env, irn);
                int res;
 
                /* bring the node to the color. */
@@ -1262,31 +1322,39 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
        }
 
        /* remove the nodes in best chunk from original chunk */
-       bitset_andnot(c->nodes, best_chunk->nodes);
-       for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
-               ir_node *irn = c->n[idx];
+       len = ARR_LEN(best_chunk->n);
+       for (idx = 0; idx < len; ++idx) {
+               const ir_node *irn = best_chunk->n[idx];
+               int pos = nodes_bsearch(c->n, irn);
 
-               if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) {
-                       int last = ARR_LEN(c->n) - 1;
+               if (pos > 0)
+                       c->n[pos] = NULL;
+       }
+       len = ARR_LEN(c->n);
+       for (idx = nidx = 0; idx < len; ++idx) {
+               const ir_node *irn = c->n[idx];
 
-                       c->n[idx] = c->n[last];
-                       ARR_SHRINKLEN(c->n, last);
-                       len--;
+               if (irn != NULL) {
+                       c->n[nidx++] = irn;
                }
        }
+       ARR_SHRINKLEN(c->n, nidx);
+
 
        /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
        for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
-               ir_node      *n  = c->n[idx];
-               co_mst_irn_t *nn = get_co_mst_irn(env, n);
+               const ir_node *n  = c->n[idx];
+               co_mst_irn_t  *nn = get_co_mst_irn(env, n);
                nn->chunk = c;
        }
 
        /* fragment the remaining chunk */
        visited = bitset_irg_malloc(env->co->irg);
-       bitset_or(visited, best_chunk->nodes);
+       for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx)
+               bitset_set(visited, get_irn_idx(best_chunk->n[idx]));
+
        for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
-               ir_node *irn = c->n[idx];
+               const ir_node *irn = c->n[idx];
                if (! bitset_is_set(visited, get_irn_idx(irn))) {
                        aff_chunk_t  *new_chunk = new_aff_chunk(env);
                        co_mst_irn_t *node      = get_co_mst_irn(env, irn);
@@ -1298,8 +1366,8 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
        }
 
        for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
-               ir_node      *n  = best_chunk->n[idx];
-               co_mst_irn_t *nn = get_co_mst_irn(env, n);
+               const ir_node *n  = best_chunk->n[idx];
+               co_mst_irn_t  *nn = get_co_mst_irn(env, n);
                nn->chunk = NULL;
        }
 
@@ -1347,11 +1415,11 @@ int co_solve_heuristic_mst(copy_opt_t *co) {
                mst_env.single_cols[i] = vec;
                for (j = 0; j < n_regs; ++j) {
                        vec[j].col  = j;
-                       vec[j].cost = 0.0;
+                       vec[j].cost = REAL(0.0);
                }
                vec[i].col  = 0;
                vec[0].col  = i;
-               vec[0].cost = 1.0;
+               vec[0].cost = REAL(1.0);
        }
 
        DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
@@ -1372,12 +1440,13 @@ int co_solve_heuristic_mst(copy_opt_t *co) {
 
        /* apply coloring */
        foreach_phase_irn(&mst_env.ph, irn) {
-               co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
+               co_mst_irn_t *mirn;
                const arch_register_t *reg;
 
                if (arch_irn_is(mst_env.aenv, irn, ignore))
                        continue;
 
+               mirn = get_co_mst_irn(&mst_env, irn);
                // assert(mirn->fixed && "Node should have fixed color");
 
                /* skip nodes where color hasn't changed */
@@ -1417,4 +1486,5 @@ void be_init_copyheur4(void) {
        FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
 }
 
+
 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);