-static void *appel_clique_walker_irn_init(phase_t *phase, ir_node *irn, void *old)
-{
- appel_block_info_t *res = NULL;
-
- 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, pset *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;
-
- n_live = 0;
- foreach_pset(live, irn)
- 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);
- pset *live = pset_new_ptr_default();
- 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 = malloc(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((env->co->cenv->dbg, LEVEL_2, "%+F\n", bl));
- 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_pset(live, irn) {
- 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;
- int k;
- int nr;
-
- if(!insn->ops[j].has_constraints)
- continue;
-
- nr = 0;
- foreach_pset(live, irn) {
- if(irn == op) {
- pset_break(live);
- break;
- }
- ++nr;
- }
-
- assert(nr < pset_count(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)
- pset_remove_ptr(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)
- pset_insert_ptr(live, insn->ops[j].carrier);
- }
-
- /* print the start clique. */
- curr_nr = appel_dump_clique(env, live, bl, curr_nr, start_nr);
-
- i = 0;
- foreach_pset(live, irn) {
- bli->live_in[i] = irn;
- bli->live_in_nr[i] = PTR_TO_INT(get_irn_link(irn));
- ++i;
- }
- bli->n_live_in = i;
-
- del_pset(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)
-{
- int i;
- int 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);
- 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 : 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) {
- int 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);
-}
-
-/*
- ___ _____ ____ ____ ___ _____ ____ _
- |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
- | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
- | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
- |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
- |_| |___/
-*/
-
-static const char *get_dot_color_name(int col)
-{
- static const char *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";
-}
-
-typedef struct _co_ifg_dump_t {
- const copy_opt_t *co;
- unsigned flags;
-} co_ifg_dump_t;
-
-static void ifg_dump_graph_attr(FILE *f, void *self)
-{
- fprintf(f, "overlap=scale");
-}
-
-static int ifg_is_dump_node(void *self, ir_node *irn)
-{
- co_ifg_dump_t *cod = self;
- return !arch_irn_is(cod->co->aenv, irn, ignore);
-}
-
-static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
-{
- co_ifg_dump_t *env = self;
- const arch_register_t *reg = arch_get_irn_register(env->co->aenv, irn);
- arch_register_req_t req;
- int limited;
-
- arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
- limited = arch_register_req_is(&req, limited);
-
- if(env->flags & CO_IFG_DUMP_LABELS) {
- ir_fprintf(f, "label=\"%+F", irn);
-
- if((env->flags & CO_IFG_DUMP_CONSTR) && limited) {
- bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
- req.limited(req.limited_env, bs);
- ir_fprintf(f, "\\n%B", bs);
- }
- ir_fprintf(f, "\" ");
- }
-
- else
- fprintf(f, "label=\"\" shape=point " );
-
- if(env->flags & CO_IFG_DUMP_SHAPE)
- fprintf(f, "shape=%s ", limited ? "diamond" : "ellipse");
-
- if(env->flags & CO_IFG_DUMP_COLORS)
- fprintf(f, "style=filled color=%s ", get_dot_color_name(reg->index));
-}
-
-static void ifg_dump_at_end(FILE *file, void *self)
-{
- co_ifg_dump_t *env = self;
- affinity_node_t *a;
-
- co_gs_foreach_aff_node(env->co, a) {
- const arch_register_t *ar = arch_get_irn_register(env->co->aenv, a->irn);
- unsigned aidx = get_irn_idx(a->irn);
- neighb_t *n;
-
- co_gs_foreach_neighb(a, n) {
- const arch_register_t *nr = arch_get_irn_register(env->co->aenv, n->irn);
- unsigned nidx = get_irn_idx(n->irn);
-
- if(aidx < nidx) {
- const char *color = nr == ar ? "blue" : "red";
- fprintf(file, "\tn%d -- n%d [weight=0.01 ", aidx, nidx);
- if(env->flags & CO_IFG_DUMP_LABELS)
- fprintf(file, "label=\"%d\" ", n->costs);
- if(env->flags & CO_IFG_DUMP_COLORS)
- fprintf(file, "color=%s ", color);
- else
- fprintf(file, "style=dotted");
- fprintf(file, "];\n");
- }
- }
- }
-}
-
-
-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
-};
-
-
-
-void co_dump_ifg_dot(const copy_opt_t *co, FILE *f, unsigned flags)
-{
- co_ifg_dump_t cod;
-
- cod.co = co;
- cod.flags = flags;
- be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &cod);
-}
-
-
-void co_solve_park_moon(copy_opt_t *opt)
-{
-
-}
-
-static int void_algo(copy_opt_t *co)
-{
- return 0;
-}
-
-/*
- _ _ _ _ _
- / \ | | __ _ ___ _ __(_) |_| |__ _ __ ___ ___
- / _ \ | |/ _` |/ _ \| '__| | __| '_ \| '_ ` _ \/ __|
- / ___ \| | (_| | (_) | | | | |_| | | | | | | | \__ \
- /_/ \_\_|\__, |\___/|_| |_|\__|_| |_|_| |_| |_|___/
- |___/
-*/
-
-typedef struct {
- co_algo_t *algo;
- const char *name;
- int can_improve_existing;
-} co_algo_info_t;
-
-static co_algo_info_t algos[] = {
- { void_algo, "none", 0 },
- { co_solve_heuristic, "heur1", 0 },
- { co_solve_heuristic_new, "heur2", 0 },
- { co_solve_heuristic_java, "heur3", 0 },
-#ifdef WITH_ILP
- { co_solve_ilp2, "ilp", 1 },
-#endif
- { NULL, "", 0 }
-};
-
-/*
- __ __ _ ____ _
- | \/ | __ _(_)_ __ | _ \ _ __(_)_ _____ _ __
- | |\/| |/ _` | | '_ \ | | | | '__| \ \ / / _ \ '__|
- | | | | (_| | | | | | | |_| | | | |\ V / __/ |
- |_| |_|\__,_|_|_| |_| |____/|_| |_| \_/ \___|_|
-
-*/
-
-static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)