* @brief More experiments on coalescing.
* @author Sebastian Hack
* @date 14.04.2006
- * @version $Id$
*/
#include "config.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.h"
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"
-#include "beirg.h"
#define DUMP_BEFORE 1
#define DUMP_AFTER 2
} col_cost_pair_t;
typedef struct {
- ir_phase ph;
+ ir_nodemap map;
+ struct obstack obst;
copy_opt_t *co;
bitset_t *allocatable_regs;
co2_irn_t *touched;
#define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
-#define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
-#define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
+static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node)
+{
+ 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 void *co2_irn_init(ir_phase *ph, const ir_node *irn)
+static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
{
- co2_t *env = (co2_t *) ph;
- affinity_node_t *a = get_affinity_info(env->co, irn);
- size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
- co2_irn_t *ci = (co2_irn_t*)phase_alloc(ph, size);
-
- memset(ci, 0, size);
- INIT_LIST_HEAD(&ci->changed_list);
- ci->touched_next = env->touched;
- ci->orig_col = get_irn_col(irn);
- env->touched = ci;
- ci->irn = irn;
- ci->aff = a;
+ 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);
- if (a) {
- co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
- INIT_LIST_HEAD(&cci->cloud_list);
- cci->mst_parent = cci;
- }
+ 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;
}
{
if (ci->adm_cache == NULL) {
const arch_register_req_t *req;
- ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
- req = arch_get_register_req_out(ci->irn);
+ 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;
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_register_req_out(irn);
+ const arch_register_req_t *req = arch_get_irn_register_req(irn);
if (arch_register_req_is(req, limited)) {
unsigned n_regs = env->co->cls->n_regs;
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 = ci->aff;
- size_t elm;
const ir_node *pos;
neighbours_iter_t it;
int i;
/* 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) {
col_costs[i].col = i;
}
if (a) {
- neighb_t *n;
-
co_gs_foreach_neighb(a, n) {
if (color_is_fix(env, n->irn)) {
col_t col = get_col(env, n->irn);
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;
}
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->tmp_fixed = 0;
be_ifg_t *ifg = env->co->cenv->ifg;
bitset_t *bs = bitset_alloca(n_regs);
- size_t elm;
const ir_node *irn;
neighbours_iter_t it;
admissible_colors(env, &ci->inh, bs);
- bitset_flip_all(bs);
- bitset_foreach(bs, elm)
+ bitset_foreach_clear(bs, elm)
badness[elm] = ci->costs;
/* Use constrained/fixed interfering neighbors to influence the color badness */
be_ifg_t *ifg = env->co->cenv->ifg;
co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
int costs = 0;
- neighb_t *n;
if (ci->cloud)
return;
static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
{
- co2_cloud_t *cloud = (co2_cloud_t*)phase_alloc(&env->ph, sizeof(cloud[0]));
- co2_cloud_irn_t *ci;
+ co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
int i;
DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
/* Also allocate space for the node sequence and compute that sequence. */
- cloud->seq = (co2_cloud_irn_t**)phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
+ 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) {
{
const ir_node *irn = ci->inh.irn;
int *front = FRONT_BASE(ci, col);
- int i, ok;
+ int i;
struct list_head changed;
INIT_LIST_HEAD(&changed);
DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
- ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
- // assert(ok && "Color changing may not fail while committing the coloring");
+ change_color_single(ci->cloud->env, irn, col, &changed, depth);
materialize_coloring(&changed);
for (i = 0; i < ci->mst_n_childs; ++i) {
obstack_init(&cloud->obst);
for (i = 0; i < cloud->n_memb; ++i) {
co2_cloud_irn_t *ci = cloud->seq[i];
- neighb_t *n;
co_gs_foreach_neighb(ci->inh.aff, n) {
co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
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]);
+ 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));
}
static int cloud_costs(co2_cloud_t *cloud)
{
int i, costs = 0;
- neighb_t *n;
for (i = 0; i < cloud->n_memb; ++i) {
co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
}
}
-
-/*
- ___ _____ ____ ____ ___ _____ ____ _
- |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
- | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
- | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
- |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
- |_| |___/
-*/
-
-static const char *get_dot_color_name(size_t col)
-{
- static const char *const names[] = {
- "blue",
- "red",
- "green",
- "yellow",
- "cyan",
- "magenta",
- "orange",
- "chocolate",
- "beige",
- "navy",
- "darkgreen",
- "darkred",
- "lightPink",
- "chartreuse",
- "lightskyblue",
- "linen",
- "pink",
- "lightslateblue",
- "mintcream",
- "red",
- "darkolivegreen",
- "mediumblue",
- "mistyrose",
- "salmon",
- "darkseagreen",
- "mediumslateblue"
- "moccasin",
- "tomato",
- "forestgreen",
- "darkturquoise",
- "palevioletred"
- };
-
- return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
-}
-
-static const char *get_dot_shape_name(co2_irn_t *ci)
-{
- const arch_register_req_t *req = arch_get_register_req_out(ci->irn);
-
- if (arch_register_req_is(req, limited))
- return "diamond";
-
- if (ci->fixed)
- return "rectangle";
-
- if (ci->tmp_fixed)
- return "hexagon";
-
- return "ellipse";
-}
-
-static void ifg_dump_graph_attr(FILE *f, void *self)
-{
- (void) self;
- fprintf(f, "overlay=false");
-}
-
-static int ifg_is_dump_node(void *self, ir_node *irn)
-{
- const arch_register_req_t *req = arch_get_register_req_out(irn);
- (void)self;
- return !(req->type & arch_register_req_type_ignore);
-}
-
-static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
-{
- co2_t *env = (co2_t*)self;
- co2_irn_t *ci = get_co2_irn(env, irn);
- int peri = 1;
-
- char buf[128] = "";
-
- if (ci->aff) {
- co2_cloud_irn_t *cci = (co2_cloud_irn_t*) ci;
- if (cci->cloud && cci->cloud->mst_root == cci)
- peri = 2;
-
- if (cci->cloud && cci->cloud->mst_root)
- ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
- }
-
- ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
- get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
-}
-
-static void ifg_dump_at_end(FILE *file, void *self)
-{
- co2_t *env = (co2_t*)self;
- affinity_node_t *a;
-
- co_gs_foreach_aff_node(env->co, a) {
- co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
- int idx = get_irn_idx(a->irn);
- neighb_t *n;
-
- if (ai->mst_parent != ai)
- fprintf(file, "\tn%d -- n%u [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
-
- co_gs_foreach_neighb(a, n) {
- int nidx = get_irn_idx(n->irn);
- co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
-
- if (idx < nidx) {
- const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
- const char *arr = "arrowhead=dot arrowtail=dot";
-
- if (ci->mst_parent == ai)
- arr = "arrowtail=normal";
- else if (ai->mst_parent == ci)
- arr = "arrowhead=normal";
-
- fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
- }
- }
- }
-}
-
-static be_ifg_dump_dot_cb_t ifg_dot_cb = {
- ifg_is_dump_node,
- ifg_dump_graph_attr,
- ifg_dump_node_attr,
- NULL,
- NULL,
- ifg_dump_at_end
-};
-
static void process(co2_t *env)
{
- affinity_node_t *a;
- co2_cloud_t *pos;
co2_cloud_t **clouds;
int n_clouds;
int i;
all_costs += clouds[i]->costs;
final_costs += cloud_costs(clouds[i]);
-
- /* Dump the IFG if the user demanded it. */
- if (dump_flags & DUMP_CLOUD) {
- char buf[256];
- FILE *f;
-
- ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
- f = fopen(buf, "wt");
- if (f != NULL) {
- be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
- fclose(f);
- }
- }
}
DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
xfree(clouds);
}
-int co_solve_heuristic_new(copy_opt_t *co)
+static int co_solve_heuristic_new(copy_opt_t *co)
{
- char buf[256];
co2_t env;
- FILE *f;
- phase_init(&env.ph, co->cenv->irg, co2_irn_init);
+ ir_nodemap_init(&env.map, co->irg);
+ obstack_init(&env.obst);
env.touched = NULL;
env.visited = 0;
env.co = co;
FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
INIT_LIST_HEAD(&env.cloud_head);
- if (dump_flags & DUMP_BEFORE) {
- ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
- f = fopen(buf, "wt");
- if (f != NULL) {
- be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
- fclose(f);
- }
- }
-
process(&env);
- if (dump_flags & DUMP_AFTER) {
- ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
- f = fopen(buf, "wt");
- if (f != NULL) {
- be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
- fclose(f);
- }
- }
-
writeback_colors(&env);
- phase_deinit(&env.ph);
+ obstack_free(&env.obst, NULL);
+ ir_nodemap_destroy(&env.map);
return 0;
}
projects / libfirm / blobdiff