+ const ir_node *irn = ci->inh.irn;
+ int *front = FRONT_BASE(ci, col);
+ int i;
+ 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));
+ change_color_single(ci->cloud->env, irn, col, &changed, depth);
+ 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 = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
+ pdeq *q;
+
+ edge_t *edges;
+ int i;
+ int best_col;
+
+ /* 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 = (edge_t*)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 = (co2_cloud_irn_t*)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;
+ }
+ }
+
+ obstack_ptr_grow(&cloud->obst, NULL);
+ ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
+ }
+ del_pdeq(q);
+ free(mst_edges);