/*
- * 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.
*
#include "belive_t.h"
#include "beinsn_t.h"
#include "besched_t.h"
-#include "benodesets.h"
#include "bejavacoal.h"
#include "bestatevent.h"
#include "beirg_t.h"
#include "error.h"
-#include <libcore/lc_timing.h>
-#include <libcore/lc_opts.h>
-#include <libcore/lc_opts_enum.h>
+#include "lc_opts.h"
+#include "lc_opts_enum.h"
#define DUMP_BEFORE 1
#define DUMP_AFTER 2
new_node.irn = n1;
new_node.degree = 0;
new_node.neighbours = NULL;
- node = set_insert(co->nodes, &new_node, sizeof(new_node), nodeset_hash(new_node.irn));
+ node = set_insert(co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
for (nbr = node->neighbours; nbr; nbr = nbr->next)
if (nbr->irn == n2) {
ASSERT_GS_AVAIL(co);
new_node.irn = irn;
- n = set_find(co->nodes, &new_node, sizeof(new_node), nodeset_hash(new_node.irn));
+ n = set_find(co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
if (n) {
return (n->degree > 0);
} else
return 0;
}
+static int co_dump_appel_disjoint_constraints(const copy_opt_t *co, ir_node *a, ir_node *b)
+{
+ ir_node *nodes[] = { a, b };
+ bitset_t *constr[] = { NULL, NULL };
+ const arch_register_req_t *req;
+ int j;
+
+ constr[0] = bitset_alloca(co->cls->n_regs);
+ constr[1] = bitset_alloca(co->cls->n_regs);
+
+ for (j = 0; j < 2; ++j) {
+ req = arch_get_register_req(co->aenv, nodes[j], BE_OUT_POS(0));
+ if(arch_register_req_is(req, limited))
+ rbitset_copy_to_bitset(req->limited, constr[j]);
+ else
+ bitset_set_all(constr[j]);
+
+ }
+
+ return !bitset_intersect(constr[0], constr[1]);
+}
+
void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
{
be_ifg_t *ifg = co->cenv->ifg;
int *color_map = alloca(co->cls->n_regs * sizeof(color_map[0]));
+ int *node_map = xmalloc((get_irg_last_idx(co->irg) + 1) * sizeof(node_map[0]));
ir_node *irn;
void *it, *nit;
n = n_regs;
be_ifg_foreach_node(ifg, it, irn) {
if(!arch_irn_is(co->aenv, irn, ignore))
- set_irn_link(irn, INT_TO_PTR(n++));
+ node_map[get_irn_idx(irn)] = n++;
}
fprintf(f, "%d %d\n", n, n_regs);
be_ifg_foreach_node(ifg, it, irn) {
if(!arch_irn_is(co->aenv, irn, ignore)) {
- int idx = PTR_TO_INT(get_irn_link(irn));
+ int idx = node_map[get_irn_idx(irn)];
affinity_node_t *a = get_affinity_info(co, irn);
const arch_register_req_t *req;
}
}
-
be_ifg_foreach_neighbour(ifg, nit, irn, adj) {
- if(!arch_irn_is(co->aenv, adj, ignore)) {
- int adj_idx = PTR_TO_INT(get_irn_link(adj));
+ if(!arch_irn_is(co->aenv, adj, ignore) && !co_dump_appel_disjoint_constraints(co, irn, adj)) {
+ int adj_idx = node_map[get_irn_idx(adj)];
if(idx < adj_idx)
fprintf(f, "%d %d -1\n", idx, adj_idx);
}
co_gs_foreach_neighb(a, n) {
if(!arch_irn_is(co->aenv, n->irn, ignore)) {
- int n_idx = PTR_TO_INT(get_irn_link(n->irn));
+ int n_idx = node_map[get_irn_idx(n->irn)];
if(idx < n_idx)
fprintf(f, "%d %d %d\n", idx, n_idx, (int) n->costs);
}
}
}
}
-}
-
-typedef struct _appel_clique_walker_t {
- ir_phase ph;
- const copy_opt_t *co;
- int curr_nr;
- int node_count;
- FILE *f;
- int dumb;
- int *color_map;
- struct obstack obst;
-} appel_clique_walker_t;
-
-typedef struct _appel_block_info_t {
- int *live_end_nr;
- int *live_in_nr;
- int *phi_nr;
- ir_node **live_end;
- ir_node **live_in;
- ir_node **phi;
- int n_live_end;
- int n_live_in;
- int n_phi;
-} appel_block_info_t;
-
-static int appel_aff_weight(const appel_clique_walker_t *env, ir_node *bl)
-{
-#if 0
- double freq = get_block_execfreq(env->co->cenv->execfreq, bl);
- int res = (int) freq;
- return res == 0 ? 1 : res;
-#else
- ir_loop *loop = get_irn_loop(bl);
- (void) env;
- if(loop) {
- int d = get_loop_depth(loop);
- return 1 + d * d;
- }
- return 1;
-#endif
-}
-
-static void *appel_clique_walker_irn_init(ir_phase *phase, ir_node *irn, void *old)
-{
- appel_block_info_t *res = NULL;
- (void) old;
-
- if(is_Block(irn)) {
- appel_clique_walker_t *d = (void *) phase;
- res = phase_alloc(phase, sizeof(res[0]));
- res->phi_nr = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end_nr));
- res->live_end_nr = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end_nr));
- res->live_in_nr = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in_nr));
- res->live_end = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end));
- res->live_in = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in));
- res->phi = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in));
- }
-
- return res;
-}
-
-typedef struct _insn_list_t {
- be_insn_t *insn;
- struct list_head list;
-} insn_list_t;
-
-static int appel_get_live_end_nr(appel_clique_walker_t *env, ir_node *bl, ir_node *irn)
-{
- appel_block_info_t *bli = phase_get_irn_data(&env->ph, bl);
- int i;
-
- for(i = 0; i < bli->n_live_end; ++i)
- if(bli->live_end[i] == irn)
- return bli->live_end_nr[i];
-
- return -1;
-}
-
-static int appel_dump_clique(appel_clique_walker_t *env, const ir_nodeset_t *live, ir_node *bl, int curr_nr, int start_nr)
-{
- ir_node **live_arr = alloca(env->co->cls->n_regs * sizeof(live_arr[0]));
- ir_node *irn;
- int n_live;
- int j;
- ir_nodeset_iterator_t iter;
-
- n_live = 0;
- foreach_ir_nodeset(live, irn, iter)
- live_arr[n_live++] = irn;
-
- /* dump the live after clique */
- if(!env->dumb) {
- for(j = 0; j < n_live; ++j) {
- int k;
-
- for(k = j + 1; k < n_live; ++k) {
- fprintf(env->f, "%d %d -1 ", curr_nr + j, curr_nr + k);
- }
- fprintf(env->f, "\n");
- }
- }
-
- /* dump the affinities */
- for(j = 0; !env->dumb && j < n_live; ++j) {
- ir_node *irn = live_arr[j];
- int old_nr = PTR_TO_INT(get_irn_link(irn));
-
- /* if the node was already live in the last insn dump the affinity */
- if(old_nr > start_nr) {
- int weight = appel_aff_weight(env, bl);
- fprintf(env->f, "%d %d %d\n", old_nr, curr_nr + j, weight);
- }
- }
-
- /* set the current numbers into the link field. */
- for(j = 0; j < n_live; ++j) {
- ir_node *irn = live_arr[j];
- set_irn_link(irn, INT_TO_PTR(curr_nr + j));
- }
-
- return curr_nr + n_live;
-}
-
-static void appel_walker(ir_node *bl, void *data)
-{
- appel_clique_walker_t *env = data;
- appel_block_info_t *bli = phase_get_or_set_irn_data(&env->ph, bl);
- struct obstack *obst = &env->obst;
- void *base = obstack_base(obst);
- ir_nodeset_t live;
- ir_nodeset_iterator_t iter;
- be_lv_t *lv = env->co->cenv->birg->lv;
-
- int n_insns = 0;
- int n_nodes = 0;
- int start_nr = env->curr_nr;
- int curr_nr = start_nr;
-
- be_insn_env_t insn_env;
- int i, j;
- ir_node *irn;
- be_insn_t **insns;
-
- insn_env.aenv = env->co->aenv;
- insn_env.cls = env->co->cls;
- insn_env.obst = obst;
- insn_env.ignore_colors = env->co->cenv->ignore_colors;
-
- /* Guess how many insns will be in this block. */
- sched_foreach(bl, irn)
- n_nodes++;
-
- bli->n_phi = 0;
- insns = xmalloc(n_nodes * sizeof(insns[0]));
-
- /* Put all insns in an array. */
- irn = sched_first(bl);
- while(!sched_is_end(irn)) {
- be_insn_t *insn;
- insn = be_scan_insn(&insn_env, irn);
- insns[n_insns++] = insn;
- irn = insn->next_insn;
- }
-
- DBG((dbg, LEVEL_2, "%+F\n", bl));
- ir_nodeset_init(&live);
- be_liveness_end_of_block(lv, env->co->aenv, env->co->cls, bl, &live);
-
- /* Generate the bad and ugly. */
- for(i = n_insns - 1; i >= 0; --i) {
- be_insn_t *insn = insns[i];
-
- /* The first live set has to be saved in the block border set. */
- if(i == n_insns - 1) {
- j = 0;
- foreach_ir_nodeset(&live, irn, iter) {
- bli->live_end[j] = irn;
- bli->live_end_nr[j] = curr_nr + j;
- ++j;
- }
- bli->n_live_end = j;
- }
-
- if(!env->dumb) {
- for(j = 0; j < insn->use_start; ++j) {
- ir_node *op = insn->ops[j].carrier;
- bitset_t *adm = insn->ops[j].regs;
- unsigned k;
- size_t nr;
-
- if(!insn->ops[j].has_constraints)
- continue;
-
- nr = 0;
- foreach_ir_nodeset(&live, irn, iter) {
- if(irn == op) {
- break;
- }
- ++nr;
- }
-
- assert(nr < ir_nodeset_size(&live));
-
- for(k = 0; k < env->co->cls->n_regs; ++k) {
- int mapped_col = env->color_map[k];
- if(mapped_col >= 0 && !bitset_is_set(adm, k) && !bitset_is_set(env->co->cenv->ignore_colors, k))
- fprintf(env->f, "%d %d -1\n", curr_nr + nr, mapped_col);
- }
- }
- }
-
- /* dump the clique and update the stuff. */
- curr_nr = appel_dump_clique(env, &live, bl, curr_nr, start_nr);
-
- /* remove all defs. */
- for(j = 0; j < insn->use_start; ++j)
- ir_nodeset_remove(&live, insn->ops[j].carrier);
-
- if(is_Phi(insn->irn) && arch_irn_consider_in_reg_alloc(env->co->aenv, env->co->cls, insn->irn)) {
- bli->phi[bli->n_phi] = insn->irn;
- bli->phi_nr[bli->n_phi] = PTR_TO_INT(get_irn_link(insn->irn));
- bli->n_phi++;
- }
-
- /* add all uses */
- else
- for(j = insn->use_start; j < insn->n_ops; ++j)
- ir_nodeset_insert(&live, insn->ops[j].carrier);
- }
-
- /* print the start clique. */
- curr_nr = appel_dump_clique(env, &live, bl, curr_nr, start_nr);
-
- i = 0;
- foreach_ir_nodeset(&live, irn, iter) {
- bli->live_in[i] = irn;
- bli->live_in_nr[i] = PTR_TO_INT(get_irn_link(irn));
- ++i;
- }
- bli->n_live_in = i;
- ir_nodeset_destroy(&live);
- free(insns);
- obstack_free(obst, base);
- env->curr_nr = curr_nr;
-}
-
-static void appel_inter_block_aff(ir_node *bl, void *data)
-{
- appel_clique_walker_t *env = data;
- appel_block_info_t *bli = phase_get_irn_data(&env->ph, bl);
-
- int i, j, n;
-
- for(i = 0; i < bli->n_live_in; ++i) {
- ir_node *irn = bli->live_in[i];
-
- for(j = 0, n = get_Block_n_cfgpreds(bl); j < n; ++j) {
- ir_node *pred = get_Block_cfgpred_block(bl, j);
-
- int nr = appel_get_live_end_nr(env, pred, irn);
- assert(nr >= 0);
- fprintf(env->f, "%d %d 1\n", bli->live_in_nr[i], nr);
- }
- }
-
- for(i = 0; i < bli->n_phi; ++i) {
- ir_node *irn = bli->phi[i];
-
- for(j = 0, n = get_Block_n_cfgpreds(bl); j < n; ++j) {
- ir_node *pred = get_Block_cfgpred_block(bl, j);
- ir_node *op = get_irn_n(irn, j);
-
- int nr = appel_get_live_end_nr(env, pred, op);
- assert(nr >= 0);
- fprintf(env->f, "%d %d 1\n", bli->phi_nr[i], nr);
- }
- }
-
-}
-
-void co_dump_appel_graph_cliques(const copy_opt_t *co, FILE *f)
-{
- unsigned i;
- unsigned n_colors;
- appel_clique_walker_t env;
- bitset_t *adm = bitset_alloca(co->cls->n_regs);
- be_lv_t *lv = co->cenv->birg->lv;
-
- be_liveness_recompute(lv);
- obstack_init(&env.obst);
- phase_init(&env.ph, "appel_clique_dumper", co->irg, PHASE_DEFAULT_GROWTH, appel_clique_walker_irn_init, NULL);
- env.curr_nr = co->cls->n_regs;
- env.co = co;
- env.f = f;
-
- bitset_copy(adm, co->cenv->ignore_colors);
- bitset_flip_all(adm);
-
- /* Make color map. */
- env.color_map = alloca(co->cls->n_regs * sizeof(env.color_map[0]));
- for(i = 0, n_colors = 0; i < co->cls->n_regs; ++i) {
- const arch_register_t *reg = &co->cls->regs[i];
- env.color_map[i] = arch_register_type_is(reg, ignore) ? -1 : (int) n_colors++;
- }
-
- env.dumb = 1;
- env.curr_nr = n_colors;
- irg_block_walk_graph(co->irg, firm_clear_link, NULL, NULL);
- irg_block_walk_graph(co->irg, appel_walker, NULL, &env);
-
- fprintf(f, "%d %d\n", env.curr_nr, n_colors);
-
- /* make the first k nodes interfere */
- for(i = 0; i < n_colors; ++i) {
- unsigned j;
- for(j = i + 1; j < n_colors; ++j)
- fprintf(f, "%d %d -1 ", i, j);
- fprintf(f, "\n");
- }
-
- env.dumb = 0;
- env.curr_nr = n_colors;
- irg_block_walk_graph(co->irg, firm_clear_link, NULL, NULL);
- irg_block_walk_graph(co->irg, appel_walker, NULL, &env);
- irg_block_walk_graph(co->irg, appel_inter_block_aff, NULL, &env);
- obstack_free(&env.obst, NULL);
+ xfree(node_map);
}
/*
if(env->flags & CO_IFG_DUMP_LABELS) {
ir_fprintf(f, "label=\"%+F", irn);
-#if 0
- // TODO fix this...
if((env->flags & CO_IFG_DUMP_CONSTR) && limited) {
bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
- req.limited(req.limited_env, bs);
+ rbitset_copy_to_bitset(req->limited, bs);
ir_fprintf(f, "\\n%B", bs);
}
-#endif
ir_fprintf(f, "\" ");
} else {
fprintf(f, "label=\"\" shape=point " );
{
FILE *result;
char buf[1024];
+ size_t i, n;
+ char *tu_name;
+
+ n = strlen(env->birg->main_env->cup_name);
+ tu_name = xmalloc((n + 1) * sizeof(*tu_name));
+ strcpy(tu_name, env->birg->main_env->cup_name);
+ for (i = 0; i < n; ++i)
+ if (tu_name[i] == '.')
+ tu_name[i] = '_';
- ir_snprintf(buf, sizeof(buf), "%s%F_%s%s", prefix, env->irg, env->cls->name, suffix);
+
+ ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
+ xfree(tu_name);
result = fopen(buf, "wt");
if(result == NULL) {
panic("Couldn't open '%s' for writing.", buf);
void co_driver(be_chordal_env_t *cenv)
{
- lc_timer_t *timer = lc_timer_register("firm.be.copyopt", "runtime");
+ ir_timer_t *timer = ir_timer_register("firm.be.copyopt", "runtime");
co_complete_stats_t before, after;
copy_opt_t *co;
co_algo_t *algo_func;
be_stat_ev_ull("co_init_costs", before.costs);
be_stat_ev_ull("co_init_unsat", before.unsatisfied_edges);
- /* Dump the interference graph in Appel's format. */
- if (dump_flags & DUMP_APPEL) {
- FILE *f = my_open(cenv, "", ".apl");
- co_dump_appel_graph(co, f);
- fclose(f);
- }
-
if (dump_flags & DUMP_BEFORE) {
FILE *f = my_open(cenv, "", "-before.dot");
co_dump_ifg_dot(co, f, style_flags);
algo_func = algos[algo].algo;
/* perform actual copy minimization */
- lc_timer_reset_and_start(timer);
+ ir_timer_reset_and_start(timer);
was_optimal = algo_func(co);
- lc_timer_stop(timer);
+ ir_timer_stop(timer);
- be_stat_ev("co_time", lc_timer_elapsed_msec(timer));
+ be_stat_ev("co_time", ir_timer_elapsed_msec(timer));
be_stat_ev_ull("co_optimal", was_optimal);
if (dump_flags & DUMP_AFTER) {
printf("%10" ULL_FMT " %5s\n", after.costs, "-");
}
+ /* Dump the interference graph in Appel's format. */
+ if (dump_flags & DUMP_APPEL) {
+ FILE *f = my_open(cenv, "", ".apl");
+ fprintf(f, "# %lld %lld\n", after.costs, after.unsatisfied_edges);
+ co_dump_appel_graph(co, f);
+ fclose(f);
+ }
+
be_stat_ev_ull("co_after_costs", after.costs);
be_stat_ev_ull("co_after_unsat", after.unsatisfied_edges);
projects / libfirm / blobdiff