+#include "beifg_t.h"
+#include "besched_t.h"
+#include "benodesets.h"
+
+#define DEBUG_LVL 1
+
+typedef struct _local_env_t {
+ double time_limit;
+ int first_x_var, last_x_var;
+ pmap *nr_2_irn;
+ DEBUG_ONLY(firm_dbg_module_t *dbg;)
+} local_env_t;
+
+static void build_coloring_cstr(ilp_env_t *ienv) {
+ be_ifg_t *ifg = ienv->co->cenv->ifg;
+ void *iter = be_ifg_nodes_iter_alloca(ifg);
+ bitset_t *colors;
+ ir_node *irn;
+ char buf[16];
+
+ colors = bitset_alloca(arch_register_class_n_regs(ienv->co->cls));
+
+ be_ifg_foreach_node(ifg, iter, irn)
+ if (!sr_is_removed(ienv->sr, irn)) {
+ bitset_pos_t col;
+ int cst_idx;
+ const arch_register_req_t *req;
+ int curr_node_color = get_irn_col(ienv->co, irn);
+ int node_nr = (int)get_irn_node_nr(irn);
+ local_env_t *lenv = ienv->env;
+
+ pmap_insert(lenv->nr_2_irn, INT_TO_PTR(node_nr), irn);
+
+ req = arch_get_register_req(ienv->co->aenv, irn, -1);
+
+ /* get assignable colors */
+ if (arch_register_req_is(req, limited)) {
+ rbitset_copy_to_bitset(req->limited, colors);
+ } else {
+ arch_register_class_put(req->cls, colors);
+ // bitset_andnot(colors, ienv->co->cenv->ignore_colors);
+ }
+
+ /* add the coloring constraint */
+ cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 1.0);
+
+ bitset_foreach(colors, col) {
+ int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, col), lpp_binary, 0.0);
+ lpp_set_start_value(ienv->lp, var_idx, (col == (unsigned) curr_node_color) ? 1.0 : 0.0);
+ lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1);
+
+ lenv->last_x_var = var_idx;
+ if (lenv->first_x_var == -1)
+ lenv->first_x_var = var_idx;
+ }
+
+ /* add register constraint constraints */
+ bitset_foreach_clear(colors, col) {
+ int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 0.0);
+ int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, col), 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;
+ be_ifg_t *ifg = ienv->co->cenv->ifg;
+ int n_colors = arch_register_class_n_regs(ienv->co->cls);
+ int i, col;
+
+ void *iter = be_ifg_cliques_iter_alloca(ifg);
+ ir_node **clique = alloca(sizeof(*clique) * n_colors);
+ int size;
+
+ char buf[16];
+
+ /* for each maximal clique */
+ be_ifg_foreach_clique(ifg, iter, clique, &size) {
+ int 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 = lpp_add_cst(lpp, NULL, lpp_less, 1.0);
+
+ /* for each member of this clique */
+ for (i=0; i<size; ++i) {
+ ir_node *irn = clique[i];
+
+ if (!sr_is_removed(ienv->sr, irn)) {
+ int var_idx = lpp_get_var_idx(lpp, name_cdd(buf, 'x', (int)get_irn_node_nr(irn), col));
+ lpp_set_factor_fast(lpp, cst_idx, var_idx, 1);
+ }
+ }
+ }
+ }
+}
+
+
+/**
+ * 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) {
+ unit_t *curr;
+ int 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, *arg;
+ int root_nr, arg_nr, i, col, y_idx, root_idx, arg_idx;
+ char buf[16];
+ int root_col, arg_col;
+
+ root = curr->nodes[0];
+ root_nr = (int) get_irn_node_nr(root);
+ root_col = get_irn_col(ienv->co, root);
+
+ for (i = 1; i < curr->node_count; ++i) {
+ arg = curr->nodes[i];
+ arg_nr = (int) get_irn_node_nr(arg);
+ arg_col = get_irn_col(ienv->co, arg);
+
+ /* add a new affinity variable */
+ y_idx = lpp_add_var(ienv->lp, name_cdd_sorted(buf, 'y', root_nr, arg_nr), lpp_binary, curr->costs[i]);
+ lpp_set_start_value(ienv->lp, y_idx, (root_col==arg_col) ? 0.0 : 1.0);
+
+ /* 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, 0.0);
+ root_idx = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', root_nr, col));
+ arg_idx = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', arg_nr, col));
+
+ 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, *n2;
+} edge_t;
+
+static int compare_edge_t(const void *k1, const void *k2, size_t size) {
+ const edge_t *e1 = k1;
+ const edge_t *e2 = k2;
+ (void) size;
+
+ return ! (e1->n1 == e2->n1 && e1->n2 == e2->n2);
+}
+
+#define HASH_EDGE(e) (nodeset_hash((e)->n1) ^ nodeset_hash((e)->n2))
+
+static INLINE edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) {
+ edge_t new_edge;
+
+ if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
+ new_edge.n1 = n1;
+ new_edge.n2 = n2;
+ } else {
+ new_edge.n1 = n2;
+ new_edge.n2 = n1;
+ }
+ (*counter)++;
+ return set_insert(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+}
+
+static INLINE edge_t *find_edge(set *edges, ir_node *n1, ir_node *n2) {
+ edge_t new_edge;
+
+ if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
+ new_edge.n1 = n1;
+ new_edge.n2 = n2;
+ } else {
+ new_edge.n1 = n2;
+ new_edge.n2 = n1;
+ }
+ return set_find(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+}
+
+static INLINE void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) {
+ edge_t new_edge, *e;
+
+ if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
+ new_edge.n1 = n1;
+ new_edge.n2 = n2;
+ } else {
+ new_edge.n1 = n2;
+ new_edge.n2 = n1;
+ }
+ e = set_find(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+ if (e) {
+ e->n1 = NULL;
+ e->n2 = NULL;
+ (*counter)--;
+ }
+}
+
+#define pset_foreach(pset, irn) for(irn=pset_first(pset); irn; irn=pset_next(pset))
+
+/**
+ * Search for an interference clique and an external node
+ * with affinity edges to all nodes of the clique.
+ * At most 1 node of the clique can be colored equally with the external node.
+ */
+static void build_clique_star_cstr(ilp_env_t *ienv) {
+ affinity_node_t *aff;
+
+ /* for each node with affinity edges */
+ co_gs_foreach_aff_node(ienv->co, aff) {
+ struct obstack ob;
+ neighb_t *nbr;
+ ir_node *center = aff->irn;
+ ir_node **nodes;
+ set *edges;
+ int i, o, n_nodes, n_edges;
+
+ obstack_init(&ob);
+ edges = new_set(compare_edge_t, 8);
+
+ /* get all affinity neighbours */
+ n_nodes = 0;
+ co_gs_foreach_neighb(aff, nbr) {
+ obstack_ptr_grow(&ob, nbr->irn);
+ ++n_nodes;
+ }
+ nodes = obstack_finish(&ob);