+static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
+{
+ be_ifg_t *ifg = env->co->cenv->ifg;
+ co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
+ int costs = 0;
+ neighb_t *n;
+
+ if(ci->cloud)
+ return;
+
+ /* mark the node as visited and add it to the cloud. */
+ ci->cloud = cloud;
+ list_add(&ci->cloud_list, &cloud->members_head);
+
+ DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
+
+ /* determine the nodes costs */
+ co_gs_foreach_neighb(a, n) {
+ costs += n->costs;
+ DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
+ if(be_ifg_connected(ifg, a->irn, n->irn))
+ cloud->inevit += n->costs;
+ }
+
+ /* add the node's cost to the total costs of the cloud. */
+ ci->costs = costs;
+ cloud->costs += costs;
+ cloud->n_constr += is_constrained(env, &ci->inh);
+ cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
+ cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
+ cloud->n_memb++;
+
+ /* If this is the heaviest node in the cloud, set it as the cloud's master. */
+ if(costs >= curr_costs) {
+ curr_costs = costs;
+ cloud->master = ci;
+ }
+
+ /* add all the neighbors of the node to the cloud. */
+ co_gs_foreach_neighb(a, n) {
+ affinity_node_t *an = get_affinity_info(env->co, n->irn);
+ assert(an);
+ populate_cloud(env, cloud, an, curr_costs);
+ }
+}
+
+static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
+{
+ co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
+ co2_cloud_irn_t *ci;
+ int i;
+
+ DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
+ memset(cloud, 0, sizeof(cloud[0]));
+ INIT_LIST_HEAD(&cloud->members_head);
+ INIT_LIST_HEAD(&cloud->list);
+ list_add(&cloud->list, &env->cloud_head);
+ cloud->best_costs = INT_MAX;
+ cloud->env = env;
+ env->visited++;
+ populate_cloud(env, cloud, a, 0);
+ cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
+
+ /* Also allocate space for the node sequence and compute that sequence. */
+ cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
+
+ i = 0;
+ list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
+ ci->index = i;
+ cloud->seq[i++] = ci;
+ }
+ DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
+
+ return cloud;
+}
+
+static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
+{
+ const ir_node *irn = ci->inh.irn;
+ int *front = FRONT_BASE(ci, col);
+ int i, ok;
+ struct list_head changed;
+
+ INIT_LIST_HEAD(&changed);
+
+ DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
+ ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
+ // assert(ok && "Color changing may not fail while committing the coloring");
+ materialize_coloring(&changed);
+
+ for(i = 0; i < ci->mst_n_childs; ++i) {
+ apply_coloring(ci->mst_childs[i], front[i], depth + 1);
+ }
+}
+
+static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
+{
+ while(ci != ci->mst_parent)
+ ci = ci->mst_parent;
+ return ci;
+}
+
+
+static void process_cloud(co2_cloud_t *cloud)
+{
+ co2_t *env = cloud->env;
+ int n_regs = env->n_regs;
+ int n_edges = 0;
+ int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
+ pdeq *q;
+
+ edge_t *edges;
+ int i;
+ int best_col;
+
+ memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
+
+ /* Collect all edges in the cloud on an obstack and sort the increasingly */
+ obstack_init(&cloud->obst);
+ for(i = 0; i < cloud->n_memb; ++i) {
+ co2_cloud_irn_t *ci = cloud->seq[i];
+ neighb_t *n;
+
+ co_gs_foreach_neighb(ci->inh.aff, n) {
+ co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
+ if(ci->index < ni->index) {
+ edge_t e;
+ e.src = ci;
+ e.tgt = ni;
+ e.costs = n->costs;
+ obstack_grow(&cloud->obst, &e, sizeof(e));
+ n_edges++;
+ }
+ }
+ }
+ edges = obstack_finish(&cloud->obst);
+ qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
+
+ /* Compute the maximum spanning tree using Kruskal/Union-Find */
+ DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
+ for(i = 0; i < n_edges; ++i) {
+ edge_t *e = &edges[i];
+ co2_cloud_irn_t *rs = find_mst_root(e->src);
+ co2_cloud_irn_t *rt = find_mst_root(e->tgt);
+
+ /* if the union/find roots are different */
+ if(rs != rt) {
+ int si = e->src->index;
+ int ti = e->tgt->index;
+
+ /* unify the sets */
+ rs->mst_parent = rt;
+ DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
+
+ /* this edge is in the MST, so set it in the bitset. */
+ mst_edges[si * cloud->n_memb + ti] = e->costs;
+ mst_edges[ti * cloud->n_memb + si] = e->costs;
+ }
+ }
+ obstack_free(&cloud->obst, edges);
+
+ cloud->master->mst_parent = cloud->master;
+ cloud->mst_root = cloud->master;
+ q = new_pdeq1(cloud->master);
+ while(!pdeq_empty(q)) {
+ co2_cloud_irn_t *ci = pdeq_getl(q);
+ int ofs = ci->index * cloud->n_memb;
+ int end = ofs + cloud->n_memb;
+ int i;
+
+ ci->mst_n_childs = 0;
+ for(i = ofs; i < end; ++i) {
+ if(mst_edges[i] != 0) {
+ int other = i - ofs;
+ co2_cloud_irn_t *child = cloud->seq[i - ofs];
+
+ /* put the child to the worklist */
+ pdeq_putr(q, child);
+
+ /* make ci the parent of the child and add the child to the children array of the parent */
+ child->mst_parent = ci;
+ child->mst_costs = mst_edges[i];
+ ci->mst_n_childs++;
+ obstack_ptr_grow(&cloud->obst, child);
+
+ mst_edges[other * cloud->n_memb + ci->index] = 0;
+ mst_edges[i] = 0;
+ }