+ 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))
+
+static inline edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, size_t *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(edge_t, 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(edge_t, edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+}
+
+static inline void remove_edge(set *edges, ir_node *n1, ir_node *n2, size_t *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(edge_t, edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+ if (e) {
+ e->n1 = NULL;
+ e->n2 = NULL;
+ (*counter)--;
+ }
+}
+
+#define pset_foreach(pset, irn) foreach_pset((pset), ir_node, (irn))
+
+/**
+ * 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)
+{
+ /* for each node with affinity edges */
+ co_gs_foreach_aff_node(ienv->co, aff) {
+ struct obstack ob;
+ const ir_node *center = aff->irn;
+ ir_node **nodes;
+ set *edges;
+ int i, o, n_nodes;
+ size_t n_edges;
+
+ if (arch_irn_is_ignore(aff->irn))
+ continue;
+
+ obstack_init(&ob);
+ edges = new_set(compare_edge_t, 8);
+
+ /* get all affinity neighbours */
+ n_nodes = 0;
+ co_gs_foreach_neighb(aff, nbr) {
+ if (!arch_irn_is_ignore(nbr->irn)) {
+ obstack_ptr_grow(&ob, nbr->irn);
+ ++n_nodes;
+ }
+ }
+ nodes = (ir_node**)obstack_finish(&ob);
+
+ /* get all interference edges between these */
+ n_edges = 0;
+ for (i=0; i<n_nodes; ++i) {
+ for (o=0; o<i; ++o) {
+ if (be_ifg_connected(ienv->co->cenv->ifg, nodes[i], nodes[o]))
+ add_edge(edges, nodes[i], nodes[o], &n_edges);
+ }
+ }
+
+ /* cover all these interference edges with maximal cliques */
+ while (n_edges) {
+ edge_t *e;
+ pset *clique = pset_new_ptr(8);
+ bool growed;
+
+ /* get 2 starting nodes to form a clique */
+ for (e = set_first(edge_t, edges); !e->n1; e = set_next(edge_t, edges)) {}
+
+ /* we could be stepped out of the loop before the set iterated to the end */
+ set_break(edges);
+
+ pset_insert_ptr(clique, e->n1);
+ pset_insert_ptr(clique, e->n2);
+ remove_edge(edges, e->n1, e->n2, &n_edges);
+
+ /* while the clique is growing */
+ do {
+ growed = false;
+
+ /* search for a candidate to extend the clique */
+ for (i=0; i<n_nodes; ++i) {
+ ir_node *cand = nodes[i];
+ bool is_cand;
+
+ /* if its already in the clique try the next */
+ if (pset_find_ptr(clique, cand))
+ continue;
+
+ /* are there all necessary interferences? */
+ is_cand = true;
+ pset_foreach(clique, member) {
+ if (!find_edge(edges, cand, member)) {
+ is_cand = false;
+ pset_break(clique);
+ break;
+ }
+ }
+
+ /* now we know if we have a clique extender */
+ if (is_cand) {
+ /* first remove all covered edges */
+ pset_foreach(clique, member)
+ remove_edge(edges, cand, member, &n_edges);
+
+ /* insert into clique */
+ pset_insert_ptr(clique, cand);
+ growed = true;
+ break;
+ }
+ }
+ } while (growed);
+
+ /* now the clique is maximal. Finally add the constraint */
+ {
+ int var_idx;
+ int cst_idx;
+ char buf[32];
+
+ cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater_equal, pset_count(clique)-1);
+
+ pset_foreach(clique, member) {
+ make_affinity_var_name(buf, sizeof(buf), center, member);
+ var_idx = lpp_get_var_idx(ienv->lp, buf);
+ lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1.0);
+ }