+/******************************************************************************
+ _____ _ _____ _
+ / ____| | | / ____| |
+ | | __ _ __ __ _ _ __ | |__ | (___ | |_ ___ _ __ __ _ __ _ ___
+ | | |_ | '__/ _` | '_ \| '_ \ \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
+ | |__| | | | (_| | |_) | | | | ____) | || (_) | | | (_| | (_| | __/
+ \_____|_| \__,_| .__/|_| |_| |_____/ \__\___/|_| \__,_|\__, |\___|
+ | | __/ |
+ |_| |___/
+ ******************************************************************************/
+
+static int compare_affinity_node_t(const void *k1, const void *k2, size_t size)
+{
+ const affinity_node_t *n1 = k1;
+ const affinity_node_t *n2 = 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 = 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 = arch_get_register_req_out(irn);
+ copy_opt_t *co = env;
+ int pos, max;
+ const arch_register_t *reg;
+
+ if (req->cls != co->cls || arch_irn_is_ignore(irn))
+ return;
+
+ reg = arch_get_irn_register(irn);
+ if (arch_register_type_is(reg, ignore))
+ 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;
+}
+
+/* co_solve_ilp1() co_solve_ilp2() are implemented in becopyilpX.c */
+
+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 = 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_node *irn;
+ void *it, *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];
+ color_map[i] = arch_register_type_is(reg, ignore) ? -1 : n_regs++;
+ }
+
+ /*
+ * n contains the first node number.
+ * the values below n are the pre-colored register nodes
+ */
+
+ it = be_ifg_nodes_iter_alloca(ifg);
+ nit = be_ifg_neighbours_iter_alloca(ifg);
+
+ 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 = 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 = 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%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");