+
+void co_complete_stats(const copy_opt_t *co, co_complete_stats_t *stat)
+{
+ bitset_t *seen = bitset_irg_malloc(co->irg);
+ affinity_node_t *an;
+
+ memset(stat, 0, sizeof(stat[0]));
+
+ /* count affinity edges. */
+ co_gs_foreach_aff_node(co, an) {
+ neighb_t *neigh;
+ stat->aff_nodes += 1;
+ bitset_add_irn(seen, an->irn);
+ co_gs_foreach_neighb(an, neigh) {
+ if (!bitset_contains_irn(seen, neigh->irn)) {
+ stat->aff_edges += 1;
+ stat->max_costs += neigh->costs;
+
+ if (get_irn_col(an->irn) != get_irn_col(neigh->irn)) {
+ stat->costs += neigh->costs;
+ stat->unsatisfied_edges += 1;
+ }
+
+ if (nodes_interfere(co->cenv, an->irn, neigh->irn)) {
+ stat->aff_int += 1;
+ stat->inevit_costs += neigh->costs;
+ }
+
+ }
+ }
+ }
+
+ bitset_free(seen);
+}
+
+/******************************************************************************
+ _____ _ _____ _
+ / ____| | | / ____| |
+ | | __ _ __ __ _ _ __ | |__ | (___ | |_ ___ _ __ __ _ __ _ ___
+ | | |_ | '__/ _` | '_ \| '_ \ \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
+ | |__| | | | (_| | |_) | | | | ____) | || (_) | | | (_| | (_| | __/
+ \_____|_| \__,_| .__/|_| |_| |_____/ \__\___/|_| \__,_|\__, |\___|
+ | | __/ |
+ |_| |___/
+ ******************************************************************************/
+
+static int compare_affinity_node_t(const void *k1, const void *k2, size_t size)
+{
+ const affinity_node_t *n1 = (const affinity_node_t*)k1;
+ const affinity_node_t *n2 = (const affinity_node_t*)k2;
+ (void) size;
+
+ return (n1->irn != n2->irn);
+}
+
+static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs)
+{
+ affinity_node_t new_node, *node;
+ neighb_t *nbr;
+ int allocnew = 1;
+
+ new_node.irn = n1;
+ new_node.degree = 0;
+ new_node.neighbours = NULL;
+ node = (affinity_node_t*)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) {
+ allocnew = 0;
+ break;
+ }
+
+ /* if we did not find n2 in n1's neighbourhood insert it */
+ if (allocnew) {
+ nbr = OALLOC(&co->obst, neighb_t);
+ nbr->irn = n2;
+ nbr->costs = 0;
+ nbr->next = node->neighbours;
+
+ node->neighbours = nbr;
+ node->degree++;
+ }
+
+ /* now nbr points to n1's neighbour-entry of n2 */
+ nbr->costs += costs;
+}
+
+static inline void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs)
+{
+ if (! be_ifg_connected(co->cenv->ifg, n1, n2)) {
+ add_edge(co, n1, n2, costs);
+ add_edge(co, n2, n1, costs);
+ }
+}
+
+static void build_graph_walker(ir_node *irn, void *env)
+{
+ const arch_register_req_t *req;
+ copy_opt_t *co = (copy_opt_t*)env;
+ int pos, max;
+
+ if (get_irn_mode(irn) == mode_T)
+ return;
+ req = arch_get_register_req_out(irn);
+ if (req->cls != co->cls || arch_irn_is_ignore(irn))
+ return;
+
+ if (is_Reg_Phi(irn)) { /* Phis */
+ for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
+ ir_node *arg = get_irn_n(irn, pos);
+ add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
+ }
+ } else if (is_Perm_Proj(irn)) { /* Perms */
+ ir_node *arg = get_Perm_src(irn);
+ add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
+ } else { /* 2-address code */
+ if (is_2addr_code(req)) {
+ const unsigned other = req->other_same;
+ int i;
+
+ for (i = 0; 1U << i <= other; ++i) {
+ if (other & (1U << i)) {
+ ir_node *other = get_irn_n(skip_Proj(irn), i);
+ if (!arch_irn_is_ignore(other))
+ add_edges(co, irn, other, co->get_costs(co, irn, other, 0));
+ }
+ }
+ }
+ }
+}
+
+void co_build_graph_structure(copy_opt_t *co)
+{
+ obstack_init(&co->obst);
+ co->nodes = new_set(compare_affinity_node_t, 32);
+
+ irg_walk_graph(co->irg, build_graph_walker, NULL, co);
+}
+
+void co_free_graph_structure(copy_opt_t *co)
+{
+ ASSERT_GS_AVAIL(co);
+
+ del_set(co->nodes);
+ obstack_free(&co->obst, NULL);
+ co->nodes = NULL;
+}
+
+int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn)
+{
+ affinity_node_t new_node, *n;
+
+ ASSERT_GS_AVAIL(co);
+
+ new_node.irn = irn;
+ n = (affinity_node_t*)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 };
+ int j;
+
+ constr[0] = bitset_alloca(co->cls->n_regs);
+ constr[1] = bitset_alloca(co->cls->n_regs);
+
+ for (j = 0; j < 2; ++j) {
+ const arch_register_req_t *req = arch_get_register_req_out(nodes[j]);
+ 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 = ALLOCAN(int, co->cls->n_regs);
+ int *node_map = XMALLOCN(int, get_irg_last_idx(co->irg) + 1);
+ ir_graph *irg = co->irg;
+ be_irg_t *birg = be_birg_from_irg(irg);
+
+ ir_node *irn;
+ nodes_iter_t it;
+ neighbours_iter_t nit;
+ int n, n_regs;
+ unsigned i;
+
+ n_regs = 0;
+ for (i = 0; i < co->cls->n_regs; ++i) {
+ const arch_register_t *reg = &co->cls->regs[i];
+ if (rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
+ color_map[i] = n_regs++;
+ } else {
+ color_map[i] = -1;
+ }
+ }
+
+ /*
+ * n contains the first node number.
+ * the values below n are the pre-colored register nodes
+ */
+
+ n = n_regs;
+ be_ifg_foreach_node(ifg, &it, irn) {
+ if (arch_irn_is_ignore(irn))
+ continue;
+ 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_ignore(irn)) {
+ int idx = node_map[get_irn_idx(irn)];
+ affinity_node_t *a = get_affinity_info(co, irn);
+ const arch_register_req_t *req = arch_get_register_req_out(irn);
+ ir_node *adj;
+
+ if (arch_register_req_is(req, limited)) {
+ for (i = 0; i < co->cls->n_regs; ++i) {
+ if (!rbitset_is_set(req->limited, i) && color_map[i] >= 0)
+ fprintf(f, "%d %d -1\n", color_map[i], idx);
+ }
+ }
+
+ be_ifg_foreach_neighbour(ifg, &nit, irn, adj) {
+ if (!arch_irn_is_ignore(adj) &&
+ !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);
+ }
+ }
+
+ if (a) {
+ neighb_t *n;
+
+ co_gs_foreach_neighb(a, n) {
+ if (!arch_irn_is_ignore(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);
+ }
+ }
+ }
+ }
+ }
+
+ xfree(node_map);
+}
+
+/*
+ ___ _____ ____ ____ ___ _____ ____ _
+ |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
+ | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
+ | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
+ |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
+ |_| |___/
+*/
+
+static const char *get_dot_color_name(size_t 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)
+{
+ (void) self;
+ fprintf(f, "overlap=scale");
+}
+
+static int ifg_is_dump_node(void *self, ir_node *irn)
+{
+ (void)self;
+ return !arch_irn_is_ignore(irn);
+}
+
+static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
+{
+ co_ifg_dump_t *env = (co_ifg_dump_t*)self;
+ const arch_register_t *reg = arch_get_irn_register(irn);
+ const arch_register_req_t *req = arch_get_register_req_out(irn);
+ int 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);
+ rbitset_copy_to_bitset(req->limited, 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 = (co_ifg_dump_t*)self;
+ affinity_node_t *a;
+
+ co_gs_foreach_aff_node(env->co, a) {
+ const arch_register_t *ar = arch_get_irn_register(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(n->irn);
+ unsigned nidx = get_irn_idx(n->irn);
+
+ if (aidx < nidx) {
+ const char *color = nr == ar ? "blue" : "red";
+ fprintf(file, "\tn%u -- n%u [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)
+{
+ (void) opt;
+}
+
+/*
+ __ __ _ ____ _
+ | \/ | __ _(_)_ __ | _ \ _ __(_)_ _____ _ __
+ | |\/| |/ _` | | '_ \ | | | | '__| \ \ / / _ \ '__|
+ | | | | (_| | | | | | | |_| | | | |\ V / __/ |
+ |_| |_|\__,_|_|_| |_| |____/|_| |_| \_/ \___|_|
+
+*/
+
+static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
+{
+ FILE *result;
+ char buf[1024];
+ size_t i, n;
+ char *tu_name;
+ const char *cup_name = be_get_irg_main_env(env->irg)->cup_name;
+
+ n = strlen(cup_name);
+ tu_name = XMALLOCN(char, n + 1);
+ strcpy(tu_name, cup_name);
+ for (i = 0; i < n; ++i)
+ if (tu_name[i] == '.')
+ tu_name[i] = '_';
+
+
+ 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);
+ }
+
+ return result;
+}
+
+void co_driver(be_chordal_env_t *cenv)
+{
+ ir_timer_t *timer = ir_timer_new();
+ co_complete_stats_t before, after;
+ copy_opt_t *co;
+ int was_optimal = 0;
+
+ assert(selected_copyopt);
+
+ /* skip copymin if algo is 'none' */
+ if (selected_copyopt->copyopt == void_algo)
+ return;
+
+ be_liveness_assure_chk(be_get_irg_liveness(cenv->irg));
+
+ co = new_copy_opt(cenv, cost_func);
+ co_build_ou_structure(co);
+ co_build_graph_structure(co);
+
+ co_complete_stats(co, &before);
+
+ be_stat_ev_ull("co_aff_nodes", before.aff_nodes);
+ be_stat_ev_ull("co_aff_edges", before.aff_edges);
+ be_stat_ev_ull("co_max_costs", before.max_costs);
+ be_stat_ev_ull("co_inevit_costs", before.inevit_costs);
+ be_stat_ev_ull("co_aff_int", before.aff_int);
+
+ be_stat_ev_ull("co_init_costs", before.costs);
+ be_stat_ev_ull("co_init_unsat", before.unsatisfied_edges);
+
+ if (dump_flags & DUMP_BEFORE) {
+ FILE *f = my_open(cenv, "", "-before.dot");
+ co_dump_ifg_dot(co, f, style_flags);
+ fclose(f);
+ }
+
+ /* if the algo can improve results, provide an initial solution with heur1 */
+ if (improve && selected_copyopt->can_improve_existing) {
+ co_complete_stats_t stats;
+
+ /* produce a heuristic solution */
+ co_solve_heuristic(co);
+
+ /* do the stats and provide the current costs */
+ co_complete_stats(co, &stats);
+ be_stat_ev_ull("co_prepare_costs", stats.costs);
+ }
+
+ /* perform actual copy minimization */
+ ir_timer_reset_and_start(timer);
+ was_optimal = selected_copyopt->copyopt(co);
+ ir_timer_stop(timer);
+
+ be_stat_ev("co_time", ir_timer_elapsed_msec(timer));
+ be_stat_ev_ull("co_optimal", was_optimal);
+ ir_timer_free(timer);
+
+ if (dump_flags & DUMP_AFTER) {
+ FILE *f = my_open(cenv, "", "-after.dot");
+ co_dump_ifg_dot(co, f, style_flags);
+ fclose(f);
+ }
+
+ co_complete_stats(co, &after);
+
+ if (do_stats) {
+ ulong64 optimizable_costs = after.max_costs - after.inevit_costs;
+ ulong64 evitable = after.costs - after.inevit_costs;
+
+ ir_printf("%30F ", cenv->irg);
+ printf("%10s %10" ULL_FMT "%10" ULL_FMT "%10" ULL_FMT, cenv->cls->name, after.max_costs, before.costs, after.inevit_costs);
+
+ if (optimizable_costs > 0)
+ printf("%10" ULL_FMT " %5.2f\n", after.costs, (evitable * 100.0) / optimizable_costs);
+ else
+ 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, "# %llu %llu\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);
+
+ co_free_graph_structure(co);
+ co_free_ou_structure(co);
+ free_copy_opt(co);
+}