+#include "beifg.h"
+#include "besched.h"
+#include "bemodule.h"
+
+DEBUG_ONLY(static firm_dbg_module_t *dbg;)
+
+typedef struct local_env_t {
+ int first_x_var;
+ int last_x_var;
+ const unsigned *allocatable_colors;
+} local_env_t;
+
+static unsigned check_alignment_constraints(ir_node *node)
+{
+ const arch_register_req_t *req = arch_get_irn_register_req(node);
+ // For larger than 1 variables, support only aligned constraints
+ assert(((!(req->type & arch_register_req_type_aligned)
+ && req->width == 1)
+ || (req->type & arch_register_req_type_aligned))
+ && "Unaligned large (width > 1) variables not supported");
+ return (req->type & arch_register_req_type_aligned) && req->width > 1;
+}
+
+static void make_color_var_name(char *buf, size_t buf_size,
+ const ir_node *node, unsigned color)
+{
+ unsigned node_idx = get_irn_idx(node);
+ snprintf(buf, buf_size, "x_%u_%u", node_idx, color);
+}
+
+static void build_coloring_cstr(ilp_env_t *ienv)
+{
+ local_env_t *lenv = (local_env_t*)ienv->env;
+ be_ifg_t *ifg = ienv->co->cenv->ifg;
+ unsigned n_regs = arch_register_class_n_regs(ienv->co->cls);
+ const unsigned *allocatable_colors = lenv->allocatable_colors;
+ nodes_iter_t iter;
+ unsigned *colors;
+ ir_node *irn;
+ char buf[32];
+
+ rbitset_alloca(colors, n_regs);
+
+ be_ifg_foreach_node(ifg, &iter, irn) {
+ const arch_register_req_t *req;
+ unsigned col;
+ int cst_idx;
+ unsigned curr_node_color;
+ unsigned has_alignment_cstr;
+
+ if (sr_is_removed(ienv->sr, irn))
+ continue;
+
+ has_alignment_cstr = check_alignment_constraints(irn);
+
+ req = arch_get_irn_register_req(irn);
+
+ /* get assignable colors */
+ if (arch_register_req_is(req, limited)) {
+ rbitset_copy(colors, req->limited, n_regs);
+ } else {
+ rbitset_copy(colors, allocatable_colors, n_regs);
+ }
+
+ /* add the coloring constraint */
+ cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 1.0);
+
+ curr_node_color = get_irn_col(irn);
+ for (col = 0; col < n_regs; ++col) {
+ int var_idx;
+ double val;
+ if (!rbitset_is_set(colors, col)
+ || (has_alignment_cstr && ((col % req->width) != 0)))
+ continue;
+
+ make_color_var_name(buf, sizeof(buf), irn, col);
+ var_idx = lpp_add_var(ienv->lp, buf, lpp_binary, 0.0);
+ lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1);
+
+ val = (col == curr_node_color) ? 1.0 : 0.0;
+ lpp_set_start_value(ienv->lp, var_idx, val);
+
+ lenv->last_x_var = var_idx;
+ if (lenv->first_x_var == -1)
+ lenv->first_x_var = var_idx;
+ }
+
+ /* add register constraint constraints */
+ for (col = 0; col < n_regs; ++col) {
+ int cst_idx;
+ int var_idx;
+ if (rbitset_is_set(colors, col)
+ // for aligned variable, we set the unaligned part to 0
+ && (!has_alignment_cstr || ((col % req->width) == 0)))
+ continue;
+
+ make_color_var_name(buf, sizeof(buf), irn, col);
+ cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 0.0);
+ var_idx = lpp_add_var(ienv->lp, buf, lpp_binary, 0.0);
+ lpp_set_start_value(ienv->lp, var_idx, 0.0);
+ lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1);
+
+ lenv->last_x_var = var_idx;
+ }
+ }
+}
+
+static void build_interference_cstr(ilp_env_t *ienv)
+{
+ lpp_t *lpp = ienv->lp;
+ local_env_t *lenv = (local_env_t*)ienv->env;
+ be_ifg_t *ifg = ienv->co->cenv->ifg;
+ unsigned n_colors = arch_register_class_n_regs(ienv->co->cls);
+ ir_node **clique = ALLOCAN(ir_node*, n_colors);
+ const unsigned *allocatable_colors = lenv->allocatable_colors;
+ cliques_iter_t iter;
+ int size;
+ unsigned col;
+ int i;
+
+ /* for each maximal clique */
+ be_ifg_foreach_clique(ifg, &iter, clique, &size) {
+ unsigned realsize = 0;
+
+ for (i=0; i<size; ++i) {
+ if (!sr_is_removed(ienv->sr, clique[i]))
+ ++realsize;
+ }
+
+ if (realsize < 2)
+ continue;
+
+ /* for all colors */
+ for (col=0; col<n_colors; ++col) {
+ int cst_idx;
+ if (!rbitset_is_set(allocatable_colors, col))
+ continue;
+
+ cst_idx = lpp_add_cst(lpp, NULL, lpp_less_equal, 1.0);
+
+ /* for each member of this clique */
+ for (i=0; i<size; ++i) {
+ ir_node *irn = clique[i];
+ char buf[32];
+ int var_idx;
+ unsigned aligment_offset = 0;
+
+ if (sr_is_removed(ienv->sr, irn))
+ continue;
+
+ // Use the first part of the large registers for all
+ // interference, since it is the only colorable one.
+ if (check_alignment_constraints(irn)) {
+ const arch_register_req_t *req
+ = arch_get_irn_register_req(irn);
+ aligment_offset = col % req->width;
+ }
+
+ make_color_var_name(buf, sizeof(buf), irn,
+ col - aligment_offset);
+ var_idx = lpp_get_var_idx(lpp, buf);
+ lpp_set_factor_fast(lpp, cst_idx, var_idx, 1);
+ }
+ }
+ }
+}
+
+static void make_affinity_var_name(char *buf, size_t buf_size,
+ const ir_node *node1, const ir_node *node2)
+{
+ unsigned n1 = get_irn_idx(node1);
+ unsigned n2 = get_irn_idx(node2);
+ if (n1 < n2) {
+ snprintf(buf, buf_size, "y_%u_%u", n1, n2);
+ } else {
+ snprintf(buf, buf_size, "y_%u_%u", n2, n1);
+ }
+}
+
+
+/**
+ * TODO: Remove the dependency of the opt-units data structure
+ * by walking over all affinity edges. Graph structure
+ * does not provide this walker, yet.
+ */
+static void build_affinity_cstr(ilp_env_t *ienv)
+{
+ unsigned n_colors = arch_register_class_n_regs(ienv->co->cls);
+
+ /* for all optimization units */
+ list_for_each_entry(unit_t, curr, &ienv->co->units, units) {
+ ir_node *root = curr->nodes[0];
+ unsigned root_col = get_irn_col(root);
+ int i;
+
+ for (i = 1; i < curr->node_count; ++i) {
+ ir_node *arg = curr->nodes[i];
+ unsigned arg_col = get_irn_col(arg);
+ double val;
+ char buf[32];
+ unsigned col;
+ int y_idx;
+
+ /* add a new affinity variable */
+ make_affinity_var_name(buf, sizeof(buf), arg, root);
+ y_idx = lpp_add_var(ienv->lp, buf, lpp_binary, curr->costs[i]);
+ val = (root_col == arg_col) ? 0.0 : 1.0;
+ lpp_set_start_value(ienv->lp, y_idx, val);
+
+ /* add constraints relating the affinity var to the color vars */
+ for (col=0; col<n_colors; ++col) {
+ int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_less_equal, 0.0);
+ int root_idx;
+ int arg_idx;
+
+ make_color_var_name(buf, sizeof(buf), root, col);
+ root_idx = lpp_get_var_idx(ienv->lp, buf);
+ make_color_var_name(buf, sizeof(buf), arg, col);
+ arg_idx = lpp_get_var_idx(ienv->lp, buf);
+
+ lpp_set_factor_fast(ienv->lp, cst_idx, root_idx, 1.0);
+ lpp_set_factor_fast(ienv->lp, cst_idx, arg_idx, -1.0);
+ lpp_set_factor_fast(ienv->lp, cst_idx, y_idx, -1.0);
+ }
+ }
+ }
+}
+
+/**
+ * Helping stuff for build_clique_star_cstr
+ */
+typedef struct edge_t {
+ ir_node *n1;
+ ir_node *n2;
+} edge_t;
+
+static int compare_edge_t(const void *k1, const void *k2, size_t size)
+{
+ const edge_t *e1 = (const edge_t*)k1;
+ const edge_t *e2 = (const edge_t*)k2;
+ (void) size;
+
+ return ! (e1->n1 == e2->n1 && e1->n2 == e2->n2);
+}
+
+#define HASH_EDGE(e) (hash_irn((e)->n1) ^ hash_irn((e)->n2))