+/*
+ * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
/**
- * More experiments on coalescing.
- * @author Sebastian Hack
- * @date 14.04.2006
+ * @file
+ * @brief More experiments on coalescing.
+ * @author Sebastian Hack
+ * @date 14.04.2006
*/
+#include "config.h"
+
+#include "lc_opts.h"
+#include "lc_opts_enum.h"
#include <stdlib.h>
#include <limits.h>
#include "list.h"
#include "pdeq.h"
#include "bitset.h"
+#include "raw_bitset.h"
+
#include "debug.h"
+#include "bitfiddle.h"
-#include "irphase_t.h"
#include "irgraph_t.h"
#include "irnode_t.h"
#include "irprintf.h"
-
+#include "util.h"
+#include "irtools.h"
+#include "irnodemap.h"
+#include "be_t.h"
+#include "bemodule.h"
#include "beabi.h"
-#include "benode_t.h"
+#include "benode.h"
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"
-#define INFEASIBLE(col) ((col) > (INT_MAX - 10))
+#define DUMP_BEFORE 1
+#define DUMP_AFTER 2
+#define DUMP_CLOUD 4
+#define DUMP_ALL 2 * DUMP_CLOUD - 1
+
+static unsigned dump_flags = 0;
+static int subtree_iter = 4;
+static int max_depth = 20;
+static double constr_factor = 0.9;
+
+static const lc_opt_enum_mask_items_t dump_items[] = {
+ { "before", DUMP_BEFORE },
+ { "after", DUMP_AFTER },
+ { "cloud", DUMP_CLOUD },
+ { "all", DUMP_ALL },
+ { NULL, 0 }
+};
+
+static lc_opt_enum_mask_var_t dump_var = {
+ &dump_flags, dump_items
+};
+
+static const lc_opt_table_entry_t options[] = {
+ LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
+ LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
+ LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
+ LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
+ LC_OPT_LAST
+};
+
+/*
+ ____ _ _
+ / ___|| |_ __ _ _ __| |_
+ \___ \| __/ _` | '__| __|
+ ___) | || (_| | | | |_
+ |____/ \__\__,_|_| \__|
+
+*/
+
+#define INFEASIBLE(cost) ((cost) == INT_MAX)
typedef unsigned col_t;
-typedef struct _co2_irn_t co2_irn_t;
-typedef struct _co2_cloud_t co2_cloud_t;
+typedef struct co2_irn_t co2_irn_t;
+typedef struct co2_cloud_t co2_cloud_t;
+typedef struct co2_cloud_irn_t co2_cloud_irn_t;
+
+typedef struct {
+ col_t col;
+ int costs;
+} col_cost_pair_t;
typedef struct {
- phase_t ph;
+ ir_nodemap map;
+ struct obstack obst;
copy_opt_t *co;
- bitset_t *ignore_regs;
- co2_irn_t *touched;
- int visited;
+ bitset_t *allocatable_regs;
+ co2_irn_t *touched;
+ int visited;
+ int n_regs;
+ struct list_head cloud_head;
DEBUG_ONLY(firm_dbg_module_t *dbg;)
} co2_t;
-struct _co2_irn_t {
- ir_node *irn;
- co2_cloud_t *cloud;
- co2_irn_t *touched_next;
+struct co2_irn_t {
+ const ir_node *irn;
affinity_node_t *aff;
- int costs;
+ co2_irn_t *touched_next;
col_t tmp_col;
col_t orig_col;
- int visited;
- int rank;
- unsigned fixed : 1;
- unsigned tmp_fixed : 1;
+ int last_color_change;
+ bitset_t *adm_cache;
+ unsigned fixed : 1;
+ unsigned tmp_fixed : 1;
+ unsigned is_constrained : 1;
struct list_head changed_list;
- struct list_head cloud_list;
};
-struct _co2_cloud_t {
- int costs;
- int inevit;
- int best_costs;
- int n_memb;
- int max_degree;
- co2_irn_t *master;
- co2_irn_t **seq;
- col_t *best_cols;
- struct list_head members_head;
- struct list_head list;
+struct co2_cloud_irn_t {
+ struct co2_irn_t inh;
+ co2_cloud_t *cloud;
+ int visited;
+ int index;
+ co2_cloud_irn_t *mst_parent;
+ int mst_costs;
+ int mst_n_childs;
+ co2_cloud_irn_t **mst_childs;
+ int *col_costs;
+ int costs;
+ int *fronts;
+ int *color_badness;
+ col_cost_pair_t *tmp_coloring;
+ struct list_head cloud_list;
+ struct list_head mst_list;
};
-#define NEIGHBOR_FIXED 1
-#define NEIGHBOR_CONSTR 2
-#define SELF_CONSTR 4
-#define DONT_WANT 8
+struct co2_cloud_t {
+ co2_t *env;
+ struct obstack obst;
+ int costs;
+ int mst_costs;
+ int inevit;
+ int best_costs;
+ int n_memb;
+ int n_constr;
+ int max_degree;
+ int ticks;
+ double freedom;
+ co2_cloud_irn_t *master;
+ co2_cloud_irn_t *mst_root;
+ co2_cloud_irn_t **seq;
+ struct list_head members_head;
+ struct list_head list;
+};
typedef struct {
- col_t col;
+ co2_cloud_irn_t *src, *tgt;
int costs;
- unsigned flags;
-} col_cost_pair_t;
+} edge_t;
-#define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
+#define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
-static void co2_irn_init(phase_t *ph, ir_node *irn, void *data)
+static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node)
{
- co2_t *env = (co2_t *) ph;
- co2_irn_t *ci = data;
-
- memset(ci, 0, sizeof(ci[0]));
- INIT_LIST_HEAD(&ci->changed_list);
- INIT_LIST_HEAD(&ci->cloud_list);
- ci->irn = irn;
- ci->touched_next = env->touched;
- ci->orig_col = get_irn_col(env->co, irn);
- ci->aff = get_affinity_info(env->co, irn);
- env->touched = ci;
+ co2_irn_t *ci = ir_nodemap_get(co2_irn_t, &env->map, node);
+ if (ci == NULL) {
+ ci = OALLOCZ(&env->obst, co2_irn_t);
+
+ INIT_LIST_HEAD(&ci->changed_list);
+ ci->touched_next = env->touched;
+ ci->orig_col = get_irn_col(node);
+ env->touched = ci;
+ ci->irn = node;
+ ci->aff = NULL;
+
+ ir_nodemap_insert(&env->map, node, ci);
+ }
+ return ci;
}
-
-static int co2_irn_cmp(const void *a, const void *b)
+static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
{
- const co2_irn_t **p = a;
- const co2_irn_t **q = b;
- return (*q)->costs - (*p)->costs;
-}
+ co2_cloud_irn_t *ci = ir_nodemap_get(co2_cloud_irn_t, &env->map, node);
+ if (ci == NULL) {
+ ci = OALLOCZ(&env->obst, co2_cloud_irn_t);
-static int cmp_clouds(const void *a, const void *b)
-{
- const co2_cloud_t **p = a;
- const co2_cloud_t **q = b;
- return (*q)->costs - (*p)->costs;
+ INIT_LIST_HEAD(&ci->inh.changed_list);
+ ci->inh.touched_next = env->touched;
+ ci->inh.orig_col = get_irn_col(node);
+ env->touched = &ci->inh;
+ ci->inh.irn = node;
+ ci->inh.aff = get_affinity_info(env->co, node);
+
+ INIT_LIST_HEAD(&ci->cloud_list);
+ ci->mst_parent = ci;
+
+ ir_nodemap_insert(&env->map, node, ci);
+ }
+ return ci;
}
-static co2_cloud_t *new_cloud(co2_t *env)
+#define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
+
+static int cmp_clouds_gt(const void *a, const void *b)
{
- co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
- memset(cloud, 0, sizeof(cloud[0]));
- INIT_LIST_HEAD(&cloud->members_head);
- INIT_LIST_HEAD(&cloud->list);
- cloud->best_costs = INT_MAX;
- return cloud;
+ const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
+ const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
+ double c = CLOUD_WEIGHT(*p);
+ double d = CLOUD_WEIGHT(*q);
+ return QSORT_CMP(d, c);
}
/**
*/
static int col_cost_pair_lt(const void *a, const void *b)
{
- const col_cost_pair_t *p = a;
- const col_cost_pair_t *q = b;
+ const col_cost_pair_t *p = (const col_cost_pair_t*)a;
+ const col_cost_pair_t *q = (const col_cost_pair_t*)b;
int c = p->costs;
int d = q->costs;
-
- if(c > d)
- return 1;
- if(c < d)
- return -1;
-
- return 0;
+ return QSORT_CMP(c, d);
}
-const char *flag_str(unsigned int fl)
+static int cmp_edges(const void *a, const void *b)
{
- static char buf[10];
-
- buf[0] = fl & NEIGHBOR_CONSTR ? 'c' : '-';
- buf[1] = fl & NEIGHBOR_FIXED ? 'n' : '-';
- buf[2] = fl & SELF_CONSTR ? 'C' : '-';
- buf[3] = fl & DONT_WANT ? 'd' : '-';
- buf[4] = '\0';
- return buf;
+ const edge_t *p = (const edge_t*)a;
+ const edge_t *q = (const edge_t*)b;
+ return QSORT_CMP(q->costs, p->costs);
}
-static col_t get_col(co2_t *env, ir_node *irn)
+static col_t get_col(co2_t *env, const ir_node *irn)
{
co2_irn_t *ci = get_co2_irn(env, irn);
return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
}
-static INLINE color_is_fix(co2_t *env, ir_node *irn)
+static inline int color_is_fix(co2_t *env, const ir_node *irn)
{
co2_irn_t *ci = get_co2_irn(env, irn);
return ci->fixed || ci->tmp_fixed;
}
-static bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
+static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
{
- arch_register_req_t req;
-
- arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
- if(arch_register_req_is(&req, limited))
- req.limited(req.limited_env, bs);
- else {
- bitset_copy(bs, env->ignore_regs);
- bitset_flip_all(bs);
+ if (ci->adm_cache == NULL) {
+ const arch_register_req_t *req;
+ ci->adm_cache = bitset_obstack_alloc(&env->obst, env->n_regs);
+ req = arch_get_irn_register_req(ci->irn);
+
+ if (arch_register_req_is(req, limited)) {
+ int i, n;
+
+ n = env->n_regs;
+ for (i = 0; i < n; ++i) {
+ if (rbitset_is_set(req->limited, i))
+ bitset_set(ci->adm_cache, i);
+ }
+ ci->is_constrained = 1;
+ } else {
+ bitset_copy(ci->adm_cache, env->allocatable_regs);
+ }
}
+ return ci->adm_cache;
+}
+
+static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
+{
+ bitset_copy(bs, get_adm(env, ci));
return bs;
}
-static int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
+static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
{
- bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
- admissible_colors(env, ci, bs);
+ bitset_t *bs = get_adm(env, ci);
return bitset_is_set(bs, col);
}
-static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
+static inline int is_constrained(co2_t *env, co2_irn_t *ci)
{
- bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
- arch_register_req_t req;
+ if (!ci->adm_cache)
+ get_adm(env, ci);
+ return ci->is_constrained;
+}
- arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
+static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
+{
+ const arch_register_req_t *req = arch_get_irn_register_req(irn);
- if(arch_register_req_is(&req, limited)) {
- bitset_pos_t elm;
- int n_constr;
+ if (arch_register_req_is(req, limited)) {
+ unsigned n_regs = env->co->cls->n_regs;
+ unsigned n_constr = 0;
+ unsigned i;
- req.limited(req.limited_env, aux);
- n_constr = bitset_popcnt(aux);
- bitset_foreach(aux, elm) {
- col_costs[elm].costs += costs / n_constr;
- col_costs[elm].flags |= NEIGHBOR_CONSTR;
+ n_constr = rbitset_popcount(req->limited, n_regs);
+ for (i = 0; i < n_regs; ++i) {
+ if (rbitset_is_set(req->limited, i)) {
+ col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
+ }
}
}
}
*/
static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
{
- ir_node *irn = ci->irn;
+ const ir_node *irn = ci->irn;
be_ifg_t *ifg = env->co->cenv->ifg;
int n_regs = env->co->cls->n_regs;
- bitset_t *forb = bitset_alloca(n_regs);
- affinity_node_t *a = get_affinity_info(env->co, irn);
+ affinity_node_t *a = ci->aff;
- bitset_pos_t elm;
- ir_node *pos;
- void *it;
+ const ir_node *pos;
+ neighbours_iter_t it;
int i;
- if(get_irn_node_nr(irn) == 2040) {
- printf("Hallo");
- }
-
/* Put all forbidden colors into the aux bitset. */
- admissible_colors(env, ci, forb);
- bitset_flip_all(forb);
+ bitset_t *const admissible = bitset_alloca(n_regs);
+ admissible_colors(env, ci, admissible);
- for(i = 0; i < n_regs; ++i) {
+ for (i = 0; i < n_regs; ++i) {
col_costs[i].col = i;
col_costs[i].costs = 0;
- col_costs[i].flags = 0;
}
- if(a) {
- neighb_t *n;
-
+ if (a) {
co_gs_foreach_neighb(a, n) {
- if(color_is_fix(env, n->irn)) {
+ if (color_is_fix(env, n->irn)) {
col_t col = get_col(env, n->irn);
- col_costs[col].costs -= 100 * n->costs;
+ col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
}
incur_constraint_costs(env, n->irn, col_costs, -n->costs);
}
}
- it = be_ifg_neighbours_iter_alloca(ifg);
- be_ifg_foreach_neighbour(ifg, it, irn, pos) {
+ be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
col_t col = get_col(env, pos);
- if(color_is_fix(env, pos)) {
+ if (color_is_fix(env, pos)) {
col_costs[col].costs = INT_MAX;
- col_costs[col].flags |= NEIGHBOR_FIXED;
}
else {
incur_constraint_costs(env, pos, col_costs, INT_MAX);
- col_costs[col].costs += 10 * be_ifg_degree(ifg, pos);
+ col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
}
}
+ be_ifg_neighbours_break(&it);
/* Set the costs to infinity for each color which is not allowed at this node. */
- bitset_foreach(forb, elm) {
+ bitset_foreach_clear(admissible, elm) {
col_costs[elm].costs = INT_MAX;
- col_costs[elm].flags |= SELF_CONSTR;
}
}
-static void single_color_cost(co2_t *env, col_t col, col_cost_pair_t *seq)
+static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
{
int n_regs = env->co->cls->n_regs;
int i;
- for(i = 0; i < n_regs; ++i) {
+ for (i = 0; i < n_regs; ++i) {
seq[i].col = i;
seq[i].costs = INT_MAX;
- seq[i].flags = 0;
- seq[i].flags = DONT_WANT;
}
+ (void) ci;
+ assert(is_color_admissible(env, ci, col));
seq[col].col = 0;
seq[0].col = col;
seq[0].costs = 0;
- seq[0].flags = 0;
-}
-
-static int curr_costs(co2_t *env, affinity_node_t *a)
-{
- col_t a_col = get_col(env, a->irn);
- int costs = 0;
- neighb_t *n;
-
- co_gs_foreach_neighb(a, n) {
- col_t n_col = get_col(env, n->irn);
- costs += n_col != a_col ? n->costs : 0;
- }
-
- return costs;
-}
-
-static int cloud_costs(co2_t *env, co2_cloud_t *cloud)
-{
- int costs = 0;
- co2_irn_t *ci;
-
- list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
- affinity_node_t *a = get_affinity_info(env->co, ci->irn);
- costs += curr_costs(env, a);
- }
-
- return costs;
}
static void reject_coloring(struct list_head *h)
{
- co2_irn_t *pos;
-
list_for_each_entry(co2_irn_t, pos, h, changed_list)
pos->tmp_fixed = 0;
}
static void materialize_coloring(struct list_head *h)
{
- co2_irn_t *pos;
-
list_for_each_entry(co2_irn_t, pos, h, changed_list) {
- pos->orig_col = pos->tmp_col;
+ pos->orig_col = pos->tmp_col;
pos->tmp_fixed = 0;
}
}
-typedef struct {
- co2_irn_t *ci;
- col_t col;
-} col_entry_t;
+static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
-static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed)
-{
- co2_irn_t *pos;
- col_entry_t ent;
-
- list_for_each_entry(co2_irn_t, pos, changed, changed_list) {
- ent.ci = pos;
- ent.col = pos->tmp_col;
- pos->tmp_col = 0;
- obstack_grow(obst, &ent, sizeof(ent));
- }
- memset(&ent, 0, sizeof(ent));
- obstack_grow(obst, &ent, sizeof(ent));
- return obstack_finish(obst);
-}
-
-static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
-static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth);
-
-static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
+static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
{
int n_regs = env->co->cls->n_regs;
be_ifg_t *ifg = env->co->cenv->ifg;
co2_irn_t *ci = get_co2_irn(env, irn);
int res = 0;
- int n_aff = 0;
int i;
- for(i = 0; i < n_regs; ++i) {
+ if (depth >= max_depth)
+ return 0;
+
+ for (i = 0; i < n_regs; ++i) {
col_t tgt_col = col_list[i].col;
unsigned costs = col_list[i].costs;
int neigh_ok = 1;
struct list_head changed;
- ir_node *n;
- void *it;
+ const ir_node *n;
+ neighbours_iter_t it;
- DBG((env->dbg, LEVEL_3, "\t\t%2Ntrying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
+ DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
- if(INFEASIBLE(costs)) {
- DB((env->dbg, LEVEL_4, "\t\t%2Ncolor %d infeasible due to %s\n", depth, tgt_col, flag_str(col_list[i].flags)));
+ if (INFEASIBLE(costs)) {
+ DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
ci->tmp_fixed = 0;
return 0;
}
/* Set the new color of the node and mark the node as temporarily fixed. */
- ci->tmp_col = tgt_col;
- ci->tmp_fixed = 1;
+ ci->tmp_col = tgt_col;
+ ci->tmp_fixed = 1;
/*
If that color has costs > 0, there's at least one neighbor having that color,
INIT_LIST_HEAD(&changed);
list_add(&ci->changed_list, &changed);
- it = be_ifg_neighbours_iter_alloca(ifg);
- be_ifg_foreach_neighbour(ifg, it, irn, n) {
+ be_ifg_foreach_neighbour(ifg, &it, irn, n) {
/* try to re-color the neighbor if it has the target color. */
- if(get_col(env, n) == tgt_col) {
+ if (get_col(env, n) == tgt_col) {
struct list_head tmp;
/*
INIT_LIST_HEAD(&tmp);
neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
list_splice(&tmp, &changed);
- if(!neigh_ok)
+ if (!neigh_ok)
break;
}
}
+ be_ifg_neighbours_break(&it);
/*
We managed to assign the target color to all neighbors, so from the perspective
of the current node, every thing was ok and we can return safely.
*/
- if(neigh_ok) {
- DBG((env->dbg, LEVEL_3, "\t\t%2Ncolor %d(%d) was ok\n", depth, tgt_col, costs));
+ if (neigh_ok) {
+ DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
list_splice(&changed, parent_changed);
res = 1;
break;
return res;
}
-static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
+static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
{
co2_irn_t *ci = get_co2_irn(env, irn);
int res = 0;
col_t col = get_col(env, irn);
- DBG((env->dbg, LEVEL_3, "\t\t%2Nclearing %+F(%d) of color %d\n", depth, irn, col, not_col));
+ DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
/* the node does not have to forbidden color. That's fine, mark it as visited and return. */
- if(col != not_col) {
- if(!ci->tmp_fixed) {
- ci->tmp_col = col;
- ci->tmp_fixed = 1;
+ if (col != not_col) {
+ if (!ci->tmp_fixed) {
+ ci->tmp_col = col;
+ ci->tmp_fixed = 1;
}
list_add(&ci->changed_list, parent_changed);
}
/* The node has the color it should not have _and_ has not been visited yet. */
- if(!color_is_fix(env, irn)) {
+ if (!color_is_fix(env, irn)) {
int n_regs = env->co->cls->n_regs;
- col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
+ col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
/* Get the costs for giving the node a specific color. */
determine_color_costs(env, ci, csts);
return res;
}
-static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
+static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
{
co2_irn_t *ci = get_co2_irn(env, irn);
col_t col = get_col(env, irn);
int res = 0;
- DBG((env->dbg, LEVEL_3, "\t\t%2Ntrying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
-
- /* If the color is already fix, bail out. */
- if(color_is_fix(env, irn))
- return 0;
+ DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
/* the node has the wanted color. That's fine, mark it as visited and return. */
- if(col == tgt_col) {
- if(!ci->tmp_fixed) {
- ci->tmp_col = col;
- ci->tmp_fixed = 1;
+ if (col == tgt_col) {
+ if (!ci->tmp_fixed) {
+ ci->tmp_col = col;
+ ci->tmp_fixed = 1;
+ list_add(&ci->changed_list, parent_changed);
}
- list_add(&ci->changed_list, parent_changed);
- DB((env->dbg, LEVEL_3, "\t\tok\n"));
- return 1;
+ res = 1;
+ goto end;
}
- else {
+ if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
int n_regs = env->co->cls->n_regs;
- col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
+ col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
/* Get the costs for giving the node a specific color. */
- single_color_cost(env, tgt_col, seq);
+ single_color_cost(env, ci, tgt_col, seq);
/* Try recoloring the node using the color list. */
res = recolor(env, irn, seq, parent_changed, depth);
- DB((env->dbg, LEVEL_3, "\t\tcolor %d %s for %+F\n", tgt_col, res ? "was ok" : "failed", irn));
}
+end:
+ DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
return res;
}
-
-#if 0
-static void try_color(co2_t *env, co2_irn_t *ci, col_t col, struct list_head *parent_changed)
+/**
+ * Examine the costs of the current coloring concerning a MST subtree.
+ * @param ci The subtree root.
+ * @param col The color of @p ci.
+ * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
+ */
+static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
{
- be_ifg_t *ifg = env->co->cenv->ifg;
- int n_regs = env->co->cls->n_regs;
- col_cost_pair_t *col_seq = alloca(n_regs * sizeof(col_seq[0]));
- affinity_node_t *a = get_affinity_info(env->co, ci->irn);
- co2_irn_t **nbs = alloca(a->degree * sizeof(nbs[0]));
- int ok = 0;
-
- col_t new_col;
- neighb_t *n;
+ int *front = FRONT_BASE(ci, col);
+ int cost = 0;
+ int i;
- assert(a != NULL && "This node must be an affinity node");
+ for (i = 0; i < ci->mst_n_childs; ++i) {
+ co2_cloud_irn_t *chld = ci->mst_childs[i];
+ col_t chld_col = front[i];
- /* If that node has already been fixed, leave it alone. */
- if(color_is_fix(env, ci->irn) || !is_color_admissible(env, ci, col)) {
- // DB((env->dbg, LEVEL_2, "\t-> color is already fix: %d\n", get_col(env, ci->irn)));
- return;
+ cost += examine_subtree_coloring(chld, chld_col);
+ cost += col != chld_col ? chld->mst_costs : 0;
}
- DB((env->dbg, LEVEL_1, "\taffinity node %+F cost %d trying color %d\n", ci->irn, ci->costs, col));
-
- single_color_cost(env, col, col_seq);
- recolor(env, ci->irn, col_seq, parent_changed, 0);
- new_col = get_col(env, ci->irn);
-
- ci->tmp_fixed = 1;
- ci->tmp_col = new_col;
-
- DB((env->dbg, LEVEL_2, "\t-> has color %d now. %d wanted\n", new_col, col));
-
- i = 0;
- co_gs_foreach_neighb(a, n)
- nbs[i++] = get_co2_irn(env, n->irn);
-
- co_gs_foreach_neighb(a, n) {
- co2_irn_t *ni = get_co2_irn(env, n->irn);
- col_t tgt_col = be_ifg_connected(ifg, ci->irn, ni->irn) ? get_col(env, ni->irn) : new_col;
- try_color(env, ni, tgt_col, parent_changed);
- }
+ return cost;
}
-
-static void process_cloud(co2_t *env, co2_cloud_t *cloud)
+/**
+ * Determine color badnesses of a node.
+ * Badness means that it is unlikely that the node in question can
+ * obtain a color. The higher the badness, the more unlikely it is that
+ * the node can be assigned that color.
+ * @param ci The node.
+ * @param badness An integer array as long as there are registers.
+ * @note The array <code>badness</code> is not cleared.
+ */
+static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
{
- int n_regs = env->co->cls->n_regs;
- col_cost_pair_t *cols = alloca(n_regs * sizeof(cols[0]));
- int best_costs = cloud_costs(env, cloud);
- int best_col = 0;
-
- struct list_head changed;
- co2_irn_t *ci;
- int i;
-
-
- i = 0;
- DB((env->dbg, LEVEL_2, "processing cloud with costs %d and master %+F containing:\n", cloud->costs, cloud->master->irn));
- list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
- DB((env->dbg, LEVEL_2, "\t%+F %d\n", ci->irn, ci->costs));
- }
-
- determine_color_costs(env, cloud->master, cols);
- qsort(cols, n_regs, sizeof(cols[0]), col_cost_pair_lt);
-
- best_col = cols[0].col;
- for(i = 0; i < n_regs; ++i) {
- col_t col = cols[i].col;
- int reject = 1;
- int costs;
-
- INIT_LIST_HEAD(&changed);
- DBG((env->dbg, LEVEL_2, "\n\ttrying color %d. current costs: %d\n", col, best_costs));
-
- /* try to recolor all the cloud members. */
- try_color(env, cloud->master, col, &changed);
-
- /* recoloring of all nodes did succeed. measure the costs and decide if the coloring shall be kept. */
- costs = cloud_costs(env, cloud);
-
- /* materialize the new coloring. */
- if(costs < best_costs) {
- materialize_coloring(&changed);
- best_costs = costs;
- best_col = col;
- reject = 0;
+ co2_t *env = ci->cloud->env;
+ co2_irn_t *ir = &ci->inh;
+ int n_regs = env->n_regs;
+ be_ifg_t *ifg = env->co->cenv->ifg;
+ bitset_t *bs = bitset_alloca(n_regs);
+
+ const ir_node *irn;
+ neighbours_iter_t it;
+
+ admissible_colors(env, &ci->inh, bs);
+ bitset_foreach_clear(bs, elm)
+ badness[elm] = ci->costs;
+
+ /* Use constrained/fixed interfering neighbors to influence the color badness */
+ be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
+ co2_irn_t *ni = get_co2_irn(env, irn);
+
+ admissible_colors(env, ni, bs);
+ if (bitset_popcount(bs) == 1) {
+ size_t c = bitset_next_set(bs, 0);
+ badness[c] += ci->costs;
}
- /* We won't get the cloud any better so stop it. */
- if(costs == 0)
- break;
-
- if(reject)
- reject_coloring(&changed);
- }
-
- DB((env->dbg, LEVEL_2, "\tfinished cloud with costs %d\n", best_costs));
-
- /* fix all cloud members */
- list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
- ci->fixed = 1;
+ else if (ni->fixed) {
+ col_t c = get_col(env, ni->irn);
+ badness[c] += ci->costs;
+ }
}
-
+ be_ifg_neighbours_break(&it);
}
-static void try_affinity_node(co2_t *env, co2_irn_t *ci, col_t preferred, struct list_head *parent_changed)
+/**
+ * Determine the badness of a MST subtree.
+ * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
+ * @see node_color_badness() for a definition of badness.
+ * @param ci The root of the subtree.
+ * @param depth Depth for debugging purposes.
+ */
+static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
{
- ir_node *irn = ci->irn;
-
- if(!color_is_fix(env, irn)) {
- int n_regs = env->co->cls->n_regs;
- bitset_t *tried = bitset_alloca(n_regs);
- bitset_t *adm = bitset_alloca(n_regs);
- col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
-
- affinity_node_t *a = get_affinity_info(env->co, irn);
- int best_costs = cloud_costs(env, ci->cloud);
- int best_col = get_col(env, ci->irn);
-
- int i;
-
- determine_color_costs(env, ci, seq);
- if(!INFEASIBLE(seq[preferred].costs))
- seq[preferred].costs = INT_MIN;
-
- qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
-
- for(i = 0; i < n_regs; ++i) {
- col_t col = seq[i].col;
-
- struct list_head changed;
- int ok, costs;
-
- INIT_LIST_HEAD(&changed);
- ok = change_color_single(env, irn, col, &changed, 0);
- col = get_col(env, irn);
-
- if(!bitset_is_set(tried, col)) {
- neighb_t *n;
-
- if(!ci->tmp_col) {
- ci->tmp_col = col;
- ci->tmp_fixed = 1;
- list_add(&ci->changed_list, &changed);
- }
+ co2_t *env = ci->cloud->env;
+ int i, j;
- co_gs_foreach_neighb(a, n) {
- co2_irn_t *ni = get_co2_irn(env, n->irn);
- try_affinity_node(env, ni, col, &changed);
- }
+ node_color_badness(ci, ci->color_badness);
- examine_coloring(env, ci->cloud);
- reject_coloring(&changed);
+ /* Collect the color badness for the whole subtree */
+ for (i = 0; i < ci->mst_n_childs; ++i) {
+ co2_cloud_irn_t *child = ci->mst_childs[i];
+ determine_color_badness(child, depth + 1);
- bitset_set(tried, col);
- }
- }
+ for (j = 0; j < env->n_regs; ++j)
+ ci->color_badness[j] += child->color_badness[j];
}
+
+ for (j = 0; j < env->n_regs; ++j)
+ DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
}
-#endif
-static void examine_cloud_coloring(co2_t *env, co2_cloud_t *cloud)
+/**
+ * Unfix all nodes in a MST subtree.
+ */
+static void unfix_subtree(co2_cloud_irn_t *ci)
{
- int costs = cloud_costs(env, cloud);
-
- if(costs < cloud->best_costs) {
- int i;
-
- for(i = 0; i < cloud->n_memb; ++i)
- cloud->best_cols[i] = get_col(env, cloud->seq[i]->irn);
+ int i;
- cloud->best_costs = costs;
- }
+ ci->inh.fixed = 0;
+ for (i = 0; i < ci->mst_n_childs; ++i)
+ unfix_subtree(ci->mst_childs[i]);
}
-static int color_change_balance(co2_t *env, co2_irn_t *ci, bitset_t *tried_colors)
+static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
{
- col_t col = get_col(env, ci->irn);
- neighb_t *n;
- int balance = 0;
-
- co_gs_foreach_neighb(ci->aff, n) {
- col_t nc = get_col(env, n->irn);
- int fixed = color_is_fix(env, n->irn);
-
- if(nc == col)
- balance -= n->costs;
- else if(!fixed || !bitset_is_set(tried_colors, nc))
- balance += n->costs;
- }
+ co2_t *env = ci->cloud->env;
+ col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
+ int is_root = ci->mst_parent == ci;
+ col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
+ int min_badness = INT_MAX;
+ int best_col_costs = INT_MAX;
+ int best_col = -1;
+ int n_regs = env->n_regs;
+ int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
- DBG((env->dbg, LEVEL_4, "\t\tbalance for changing %+F color %d\n", ci->irn, balance));
- return balance;
-}
+ struct list_head changed;
+ int ok, i, j;
-static void keep_sensible_colors(co2_t *env, co2_irn_t *ci, col_cost_pair_t *seq)
-{
- bitset_t *fixed_cols = bitset_alloca(env->co->cls->n_regs);
- int all_fixed = 1;
- neighb_t *n;
+ for (i = 0; i < n_regs; ++i) {
+ int badness = ci->color_badness[i];
- co_gs_foreach_neighb(ci->aff, n) {
- all_fixed &= color_is_fix(env, n->irn);
- bitset_set(fixed_cols, get_col(env, n->irn));
- }
+ seq[i].col = i;
+ seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
- if(all_fixed) {
- bitset_pos_t i;
- bitset_flip_all(fixed_cols);
- bitset_foreach(fixed_cols, i)
- seq[i].costs = INT_MAX;
+ min_badness = MIN(min_badness, badness);
}
-}
-static int process_node(co2_t *env, co2_cloud_t *cloud, int index)
-{
- struct list_head changed;
- int res = 0;
+ /* If we are not the root and the parent's color is allowed for this node give it top prio. */
+ if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
+ seq[parent_col].costs = min_badness - 1;
- if(index < cloud->n_memb) {
- co2_irn_t *ci = cloud->seq[index];
- int n_regs = env->co->cls->n_regs;
- col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
- bitset_t *cols_tried = bitset_alloca(n_regs);
- int done = 0;
- //col_cost_pair_t *single = alloca(n_regs * sizeof(seq[0]));
-
- int i;
+ /* Sort the colors. The will be processed in that ordering. */
+ qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
- determine_color_costs(env, ci, seq);
+ DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
+ INIT_LIST_HEAD(&changed);
+ for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
+ col_t col = seq[i].col;
+ int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
- if(index == 0) {
- col_t col = get_col(env, ci->irn);
- int min_costs = INT_MAX;
- int i;
+ int subtree_costs, sum_costs;
- for(i = 0; i < n_regs; ++i)
- min_costs = MIN(min_costs, seq[i].costs);
+ DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
- seq[col].costs = min_costs - 1;
+ unfix_subtree(ci);
+ INIT_LIST_HEAD(&changed);
+ ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
+ if (ok) {
+ materialize_coloring(&changed);
+ ci->inh.fixed = 1;
}
- //keep_sensible_colors(env, ci, seq);
- qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
-
-#if 0
- if(index == cloud->n_memb - 1) {
- for(i = 0; i < n_regs; ++i)
- if(seq[i].costs >= 0)
- seq[i].costs = INT_MAX;
+ else
+ continue;
+
+ for (j = 0; j < ci->mst_n_childs; ++j) {
+ co2_cloud_irn_t *child = ci->mst_childs[j];
+ ok = coalesce_top_down(child, j, depth + 1) >= 0;
+ if (ok)
+ child->inh.fixed = 1;
+ else
+ break;
}
-#endif
-
-
- for(i = 0; i < n_regs && !done; ++i) {
- col_t col = seq[i].col;
- int costs = seq[i].costs;
- int ok;
- /*
- if all affinity neighbors fixed,
- try only color changes to affinity colors.
- all other colors do no good.
- */
+ /* If the subtree could not be colored, we have to try another color. */
+ if (!ok)
+ continue;
- DB((env->dbg, LEVEL_2, "\t%2Ntrying %+F index %d for color %d\n", index, ci->irn, index, col));
- if(INFEASIBLE(costs)) {
- DBG((env->dbg, LEVEL_2, "\t%2N-> color is infeasible due to %s\n", index, flag_str(seq[i].flags)));
- break;
- }
-
- bitset_set(cols_tried, col);
- INIT_LIST_HEAD(&changed);
- ok = change_color_single(env, ci->irn, col, &changed, 0);
- DB((env->dbg, LEVEL_2, "\t%2N-> %s\n", index, ok ? "ok" : "failed"));
-
- /* if we succeeded changing the color, we will figure out the next node. */
- if(ok) {
- int finish;
-
- /* materialize the coloring and fix the node's color. */
- ci->fixed = 1;
-
- /* process the next nodes. if the function returns one, we found an optimal coloring already, so get out. */
- finish = process_node(env, cloud, index + 1);
-
- /* if this is the last node in the coloring sequence, examine the coloring */
- if(index == cloud->n_memb - 1) {
- examine_cloud_coloring(env, cloud);
- DB((env->dbg, LEVEL_2, "\t%2N-> current best coloring %d\n", index, cloud->best_costs));
- if(cloud->best_costs == cloud->inevit) {
- done = 1;
- res = 1;
- }
- }
-
- /* unfix the node. */
- reject_coloring(&changed);
- ci->fixed = 0;
-
- if(finish || color_change_balance(env, ci, cols_tried) <= 0) {
- res = finish;
- done = 1;
- }
- }
+ subtree_costs = examine_subtree_coloring(ci, col);
+ sum_costs = subtree_costs + add_cost;
+ DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
+ if (sum_costs < best_col_costs) {
+ best_col = col;
+ best_col_costs = sum_costs;
+ ci->col_costs[col] = subtree_costs;
}
- }
- return res;
-}
-
-static co2_irn_t **get_neighb_arr(co2_t *env, co2_irn_t *ci, co2_irn_t **nbs)
-{
- int i;
- neighb_t *n;
-
- i = 0;
- co_gs_foreach_neighb(ci->aff, n) {
- nbs[i++] = get_co2_irn(env, n->irn);
+ if (sum_costs == 0)
+ break;
}
- qsort(nbs, ci->aff->degree, sizeof(nbs[0]), co2_irn_cmp);
- return nbs;
-}
-
-static void determine_coloring_sequence(co2_t *env, co2_cloud_t *cloud)
-{
- pdeq *q = new_pdeq1(cloud->master);
- bitset_t *seen = bitset_malloc(get_irg_last_idx(env->co->irg));
- co2_irn_t **nbs = alloca(cloud->max_degree * sizeof(nbs[0]));
- int i, j;
-
- j = 0;
- bitset_set(seen, get_irn_idx(cloud->master->irn));
- while(!pdeq_empty(q)) {
- co2_irn_t *curr = pdeq_getl(q);
-
- cloud->seq[j++] = curr;
- get_neighb_arr(env, curr, nbs);
-
- for(i = 0; i < curr->aff->degree; ++i) {
- co2_irn_t *ni = nbs[i];
- int idx = get_irn_idx(ni->irn);
- if(!bitset_is_set(seen, idx)) {
- pdeq_putr(q, ni);
- bitset_set(seen, idx);
- }
- }
+ if (!is_root) {
+ int *front = FRONT_BASE(ci->mst_parent, parent_col);
+ front[child_nr] = best_col;
}
- del_pdeq(q);
- bitset_free(seen);
+ return best_col;
}
static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
{
- be_ifg_t *ifg = env->co->cenv->ifg;
- co2_irn_t *ci = get_co2_irn(env, a->irn);
- int costs = 0;
- neighb_t *n;
+ be_ifg_t *ifg = env->co->cenv->ifg;
+ co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
+ int costs = 0;
- if(ci->visited >= env->visited)
+ if (ci->cloud)
return;
/* mark the node as visited and add it to the cloud. */
- ci->visited = env->visited;
ci->cloud = cloud;
list_add(&ci->cloud_list, &cloud->members_head);
- DB((env->dbg, LEVEL_3, "%+F\n", ci->irn));
+ DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
/* determine the nodes costs */
co_gs_foreach_neighb(a, n) {
costs += n->costs;
- DB((env->dbg, LEVEL_3, "\t%+F\n", n->irn));
- if(be_ifg_connected(ifg, a->irn, n->irn))
+ DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
+ if (be_ifg_connected(ifg, a->irn, n->irn))
cloud->inevit += n->costs;
}
/* add the node's cost to the total costs of the cloud. */
ci->costs = costs;
cloud->costs += costs;
- cloud->max_degree = MAX(cloud->max_degree, ci->aff->degree);
+ cloud->n_constr += is_constrained(env, &ci->inh);
+ cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
+ cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
cloud->n_memb++;
/* If this is the heaviest node in the cloud, set it as the cloud's master. */
- if(costs >= curr_costs) {
- cloud->master = ci;
+ if (costs >= curr_costs) {
curr_costs = costs;
+ cloud->master = ci;
}
/* add all the neighbors of the node to the cloud. */
}
}
-static void init_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a)
+static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
{
+ co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
+ int i;
+
+ DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
+ memset(cloud, 0, sizeof(cloud[0]));
+ INIT_LIST_HEAD(&cloud->members_head);
+ INIT_LIST_HEAD(&cloud->list);
+ list_add(&cloud->list, &env->cloud_head);
+ cloud->best_costs = INT_MAX;
+ cloud->env = env;
env->visited++;
populate_cloud(env, cloud, a, 0);
+ cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
- cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
- cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
- env->visited++;
- cloud->seq[0] = cloud->master;
- determine_coloring_sequence(env, cloud);
+ /* Also allocate space for the node sequence and compute that sequence. */
+ cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
+
+ i = 0;
+ list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
+ ci->index = i;
+ cloud->seq[i++] = ci;
+ }
+ DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
+
+ return cloud;
}
-static void process_cloud(co2_t *env, co2_cloud_t *cloud)
+static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
{
- struct list_head changed;
+ const ir_node *irn = ci->inh.irn;
+ int *front = FRONT_BASE(ci, col);
int i;
+ struct list_head changed;
- /* initialize the best coloring. */
- examine_cloud_coloring(env, cloud);
+ INIT_LIST_HEAD(&changed);
- DB((env->dbg, LEVEL_1, "\nnew cloud\nall costs %d, initial costs %d, inevit %d\n", cloud->costs, cloud->best_costs, cloud->inevit));
- for(i = 0; i < cloud->n_memb; ++i) {
- co2_irn_t *ci = cloud->seq[i];
- DB((env->dbg, LEVEL_1, "\tmember %+F cost %d col %d\n", ci->irn, ci->costs, get_col(env, ci->irn)));
+ DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
+ change_color_single(ci->cloud->env, irn, col, &changed, depth);
+ materialize_coloring(&changed);
+
+ for (i = 0; i < ci->mst_n_childs; ++i) {
+ apply_coloring(ci->mst_childs[i], front[i], depth + 1);
}
+}
- process_node(env, cloud, 0);
- DB((env->dbg, LEVEL_1, "final coloring costs %d\n", cloud->best_costs));
+static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
+{
+ while (ci != ci->mst_parent)
+ ci = ci->mst_parent;
+ return ci;
+}
- /* re-try the best coloring. */
- INIT_LIST_HEAD(&changed);
- for(i = 0; i < cloud->n_memb; ++i) {
- co2_irn_t *ci = cloud->seq[i];
- col_t col = cloud->best_cols[i];
- int ok;
+static void process_cloud(co2_cloud_t *cloud)
+{
+ co2_t *env = cloud->env;
+ int n_regs = env->n_regs;
+ int n_edges = 0;
+ int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
+ pdeq *q;
- DB((env->dbg, LEVEL_2, "\tsetting %+F to %d\n", ci->irn, col));
- ok = change_color_single(env, ci->irn, col, &changed, 0);
- assert(ok);
- ci->fixed = 1;
+ edge_t *edges;
+ int i;
+ int best_col;
+
+ /* Collect all edges in the cloud on an obstack and sort the increasingly */
+ obstack_init(&cloud->obst);
+ for (i = 0; i < cloud->n_memb; ++i) {
+ co2_cloud_irn_t *ci = cloud->seq[i];
+
+ co_gs_foreach_neighb(ci->inh.aff, n) {
+ co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
+ if (ci->index < ni->index) {
+ edge_t e;
+ e.src = ci;
+ e.tgt = ni;
+ e.costs = n->costs;
+ obstack_grow(&cloud->obst, &e, sizeof(e));
+ n_edges++;
+ }
+ }
}
- materialize_coloring(&changed);
+ edges = (edge_t*)obstack_finish(&cloud->obst);
+ qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
+
+ /* Compute the maximum spanning tree using Kruskal/Union-Find */
+ DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
+ for (i = 0; i < n_edges; ++i) {
+ edge_t *e = &edges[i];
+ co2_cloud_irn_t *rs = find_mst_root(e->src);
+ co2_cloud_irn_t *rt = find_mst_root(e->tgt);
+
+ /* if the union/find roots are different */
+ if (rs != rt) {
+ int si = e->src->index;
+ int ti = e->tgt->index;
+
+ /* unify the sets */
+ rs->mst_parent = rt;
+ DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
+
+ /* this edge is in the MST, so set it in the bitset. */
+ mst_edges[si * cloud->n_memb + ti] = e->costs;
+ mst_edges[ti * cloud->n_memb + si] = e->costs;
+ }
+ }
+ obstack_free(&cloud->obst, edges);
+
+ cloud->master->mst_parent = cloud->master;
+ cloud->mst_root = cloud->master;
+ q = new_pdeq1(cloud->master);
+ while (!pdeq_empty(q)) {
+ co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
+ int ofs = ci->index * cloud->n_memb;
+ int end = ofs + cloud->n_memb;
+ int i;
+
+ ci->mst_n_childs = 0;
+ for (i = ofs; i < end; ++i) {
+ if (mst_edges[i] != 0) {
+ int other = i - ofs;
+ co2_cloud_irn_t *child = cloud->seq[i - ofs];
- {
- co2_irn_t *ci;
- int some_fixed = 0;
- for(ci = env->touched; ci; ci = ci->touched_next) {
- if(ci->tmp_fixed) {
- some_fixed = 1;
- ir_printf("%+F is still temp fixed\n", ci->irn);
+ /* put the child to the worklist */
+ pdeq_putr(q, child);
+
+ /* make ci the parent of the child and add the child to the children array of the parent */
+ child->mst_parent = ci;
+ child->mst_costs = mst_edges[i];
+ ci->mst_n_childs++;
+ obstack_ptr_grow(&cloud->obst, child);
+
+ mst_edges[other * cloud->n_memb + ci->index] = 0;
+ mst_edges[i] = 0;
}
}
- assert(!some_fixed);
+
+ obstack_ptr_grow(&cloud->obst, NULL);
+ ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
+ }
+ del_pdeq(q);
+ free(mst_edges);
+
+
+ DBG((env->dbg, LEVEL_3, "mst:\n"));
+ for (i = 0; i < cloud->n_memb; ++i) {
+ DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
+ DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
+ }
+
+ for (i = 0; i < cloud->n_memb; ++i) {
+ co2_cloud_irn_t *ci = cloud->seq[i];
+ int n_childs = ci->mst_n_childs;
+ int j;
+
+ ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
+ ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
+ ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
+ ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
+
+ for (j = 0; j < env->n_regs; j++)
+ ci->col_costs[j] = INT_MAX;
+ }
+
+ determine_color_badness(cloud->mst_root, 0);
+ best_col = coalesce_top_down(cloud->mst_root, -1, 0);
+ unfix_subtree(cloud->mst_root);
+ apply_coloring(cloud->mst_root, best_col, 0);
+
+ /* The coloring should represent the one with the best costs. */
+ //materialize_coloring(&changed);
+ DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
+ cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
+
+ /* Fix all nodes in the cloud. */
+ for (i = 0; i < cloud->n_memb; ++i)
+ cloud->seq[i]->inh.fixed = 1;
+
+ /* Free all space used while optimizing this cloud. */
+ obstack_free(&cloud->obst, NULL);
+}
+
+static int cloud_costs(co2_cloud_t *cloud)
+{
+ int i, costs = 0;
+
+ for (i = 0; i < cloud->n_memb; ++i) {
+ co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
+ col_t col = get_col(cloud->env, ci->irn);
+ co_gs_foreach_neighb(ci->aff, n) {
+ col_t n_col = get_col(cloud->env, n->irn);
+ costs += col != n_col ? n->costs : 0;
+ }
+ }
+
+ return costs / 2;
+}
+
+static void writeback_colors(co2_t *env)
+{
+ co2_irn_t *irn;
+
+ for (irn = env->touched; irn; irn = irn->touched_next) {
+ const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
+ arch_set_irn_register((ir_node*)irn->irn, reg);
}
}
static void process(co2_t *env)
{
- affinity_node_t *a;
- struct list_head cloud_head;
- co2_cloud_t *pos;
co2_cloud_t **clouds;
int n_clouds;
int i;
int all_costs = 0;
int final_costs = 0;
-
- INIT_LIST_HEAD(&cloud_head);
-
n_clouds = 0;
co_gs_foreach_aff_node(env->co, a) {
- co2_irn_t *ci = get_co2_irn(env, a->irn);
+ co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
- if(!ci->cloud) {
- co2_cloud_t *cloud = new_cloud(env);
-
- init_cloud(env, cloud, a);
- list_add(&cloud->list, &cloud_head);
+ if (!ci->cloud) {
+ new_cloud(env, a);
n_clouds++;
}
}
i = 0;
- clouds = xmalloc(n_clouds * sizeof(clouds[0]));
- list_for_each_entry(co2_cloud_t, pos, &cloud_head, list)
+ clouds = XMALLOCN(co2_cloud_t*, n_clouds);
+ list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
clouds[i++] = pos;
- qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds);
+ qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
+
+ for (i = 0; i < n_clouds; ++i) {
+ init_costs += cloud_costs(clouds[i]);
+
+ /* Process the cloud. */
+ process_cloud(clouds[i]);
- for(i = 0; i < n_clouds; ++i) {
- init_costs += cloud_costs(env, clouds[i]);
- process_cloud(env, clouds[i]);
all_costs += clouds[i]->costs;
- final_costs += clouds[i]->best_costs;
+ final_costs += cloud_costs(clouds[i]);
}
DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
xfree(clouds);
}
-static void writeback_colors(co2_t *env)
-{
- const arch_env_t *aenv = env->co->aenv;
- co2_irn_t *irn;
-
- for(irn = env->touched; irn; irn = irn->touched_next) {
- const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
- arch_set_irn_register(aenv, irn->irn, reg);
- }
-}
-
-void co_solve_heuristic_new(copy_opt_t *co)
+static int co_solve_heuristic_new(copy_opt_t *co)
{
co2_t env;
- phase_init(&env.ph, "co2", co->cenv->birg->irg, sizeof(co2_irn_t), PHASE_DEFAULT_GROWTH, co2_irn_init);
+ ir_nodemap_init(&env.map, co->irg);
+ obstack_init(&env.obst);
env.touched = NULL;
env.visited = 0;
env.co = co;
- env.ignore_regs = bitset_alloca(co->cls->n_regs);
- arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
- bitset_flip_all(env.ignore_regs);
- be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
+ env.n_regs = co->cls->n_regs;
+ env.allocatable_regs = bitset_alloca(co->cls->n_regs);
+ be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
+ INIT_LIST_HEAD(&env.cloud_head);
process(&env);
+
writeback_colors(&env);
- phase_free(&env.ph);
+ obstack_free(&env.obst, NULL);
+ ir_nodemap_destroy(&env.map);
+ return 0;
+}
+
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
+void be_init_copyheur2(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");
+ lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
+
+ static co_algo_info copyheur = {
+ co_solve_heuristic_new, 0
+ };
+
+ lc_opt_add_table(co2_grp, options);
+ be_register_copyopt("heur2", ©heur);
}
projects / libfirm / blobdiff