becopyheur2.c 33.1 KB
Newer Older
1
2
3
4
5
6
7

/**
 * More experiments on coalescing.
 * @author Sebastian Hack
 * @date   14.04.2006
 */

Sebastian Hack's avatar
Sebastian Hack committed
8
9
10
11
12
13
14
15
16
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#endif /* WITH_LIBCORE */

17
18
19
20
#include <stdlib.h>
#include <limits.h>

#include "list.h"
21
#include "pdeq.h"
22
#include "bitset.h"
Sebastian Hack's avatar
Sebastian Hack committed
23

24
#include "debug.h"
Sebastian Hack's avatar
Sebastian Hack committed
25
#include "bitfiddle.h"
26
27
28
29
30

#include "irphase_t.h"
#include "irgraph_t.h"
#include "irnode_t.h"
#include "irprintf.h"
Sebastian Hack's avatar
Sebastian Hack committed
31
#include "irtools.h"
32
33
34
35
36
37
38

#include "beabi.h"
#include "benode_t.h"
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"

Sebastian Hack's avatar
Sebastian Hack committed
39
40
41
#define DUMP_BEFORE 1
#define DUMP_AFTER  2
#define DUMP_CLOUD  4
42
#define DUMP_ALL    2 * DUMP_CLOUD - 1
Sebastian Hack's avatar
Sebastian Hack committed
43

Matthias Braun's avatar
Matthias Braun committed
44
45
46
47
static unsigned dump_flags      = 0;
static int      subtree_iter    = 4;
static int      max_depth       = 20;
static double   constr_factor   = 0.9;
Sebastian Hack's avatar
Sebastian Hack committed
48
49
50
51
52
53

/* Options using libcore */
#ifdef WITH_LIBCORE

static const lc_opt_enum_mask_items_t dump_items[] = {
	{ "before",  DUMP_BEFORE },
Adam Szalkowski's avatar
Adam Szalkowski committed
54
55
	{ "after",   DUMP_AFTER  },
	{ "cloud",   DUMP_CLOUD  },
56
	{ "all",     DUMP_ALL    },
Sebastian Hack's avatar
Sebastian Hack committed
57
58
59
60
61
62
63
64
	{ NULL,      0 }
};

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

static const lc_opt_table_entry_t options[] = {
65
66
	LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud",                                         &dump_var),
	LC_OPT_ENT_INT      ("iter", "iterations for subtree nodes",                           &subtree_iter),
Sebastian Hack's avatar
Sebastian Hack committed
67
	LC_OPT_ENT_DBL      ("cf",   "factor of constraint importance (between 0.0 and 1.0)",  &constr_factor),
68
	LC_OPT_ENT_INT      ("max",  "maximum recursion depth",                                &max_depth),
Sebastian Hack's avatar
Sebastian Hack committed
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
	{ NULL }
};

void be_co2_register_options(lc_opt_entry_t *grp)
{
	lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2");
	lc_opt_add_table(co2_grp, options);
}
#endif

/*
  ____  _             _
 / ___|| |_ __ _ _ __| |_
 \___ \| __/ _` | '__| __|
  ___) | || (_| | |  | |_
 |____/ \__\__,_|_|   \__|

*/

Sebastian Hack's avatar
Sebastian Hack committed
88
89
90
#define INFEASIBLE(cost) ((cost) == INT_MAX)

static be_ifg_dump_dot_cb_t ifg_dot_cb;
91

92
93
typedef unsigned col_t;

Sebastian Hack's avatar
Sebastian Hack committed
94
95
96
97
98
99
100
101
typedef struct _co2_irn_t       co2_irn_t;
typedef struct _co2_cloud_t     co2_cloud_t;
typedef struct _co2_cloud_irn_t co2_cloud_irn_t;

typedef struct {
	col_t col;
	int costs;
} col_cost_pair_t;
102
103

typedef struct {
Sebastian Hack's avatar
Sebastian Hack committed
104
	phase_t     ph;
105
	copy_opt_t *co;
Sebastian Hack's avatar
Sebastian Hack committed
106
107
108
109
	bitset_t   *ignore_regs;
	co2_irn_t  *touched;
	int         visited;
	int         n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
110
	struct list_head cloud_head;
111
112
113
114
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
} co2_t;

struct _co2_irn_t {
115
116
	ir_node         *irn;
	affinity_node_t *aff;
Sebastian Hack's avatar
Sebastian Hack committed
117
	co2_irn_t       *touched_next;
118
119
	col_t            tmp_col;
	col_t            orig_col;
Sebastian Hack's avatar
Sebastian Hack committed
120
	int				 last_color_change;
121
	bitset_t        *adm_cache;
Sebastian Hack's avatar
Sebastian Hack committed
122
123
124
	unsigned         fixed          : 1;
	unsigned         tmp_fixed      : 1;
	unsigned         is_constrained : 1;
125
	struct list_head changed_list;
Sebastian Hack's avatar
Sebastian Hack committed
126
127
128
129
130
131
132
133
134
135
136
137
138
139
};

struct _co2_cloud_irn_t {
	struct _co2_irn_t  inh;
	co2_cloud_t       *cloud;
	int                visited;
	int                index;
	co2_cloud_irn_t   *mst_parent;
	int                mst_costs;
	int                mst_n_childs;
	co2_cloud_irn_t  **mst_childs;
	int               *col_costs;
	int                costs;
	int               *fronts;
140
	int               *color_badness;
Sebastian Hack's avatar
Sebastian Hack committed
141
142
143
	col_cost_pair_t   *tmp_coloring;
	struct list_head   cloud_list;
	struct list_head   mst_list;
144
145
146
};

struct _co2_cloud_t {
Sebastian Hack's avatar
Sebastian Hack committed
147
148
149
150
151
152
153
	co2_t            *env;
	struct obstack    obst;
	int               costs;
	int               mst_costs;
	int               inevit;
	int               best_costs;
	int               n_memb;
Sebastian Hack's avatar
Sebastian Hack committed
154
	int               n_constr;
Sebastian Hack's avatar
Sebastian Hack committed
155
156
	int               max_degree;
	int			      ticks;
Sebastian Hack's avatar
Sebastian Hack committed
157
	double            freedom;
Sebastian Hack's avatar
Sebastian Hack committed
158
159
160
161
162
	co2_cloud_irn_t  *master;
	co2_cloud_irn_t  *mst_root;
	co2_cloud_irn_t **seq;
	struct list_head  members_head;
	struct list_head  list;
163
164
};

165
166
167
168
169
typedef struct {
	co2_cloud_irn_t *src, *tgt;
	int costs;
} edge_t;

Sebastian Hack's avatar
Sebastian Hack committed
170
#define FRONT_BASE(ci,col)  ((ci)->fronts + col * (ci)->mst_n_childs)
171

Sebastian Hack's avatar
Sebastian Hack committed
172
173
#define get_co2_irn(co2, irn)         ((co2_irn_t *)       phase_get_or_set_irn_data(&co2->ph, irn))
#define get_co2_cloud_irn(co2, irn)   ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
174

Sebastian Hack's avatar
Sebastian Hack committed
175
static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
176
{
Sebastian Hack's avatar
Sebastian Hack committed
177
178
179
180
	co2_t *env         = (co2_t *) ph;
	affinity_node_t *a = get_affinity_info(env->co, irn);
	size_t size        = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
	co2_irn_t *ci      = data ? data : phase_alloc(ph, size);
181

Sebastian Hack's avatar
Sebastian Hack committed
182
	memset(ci, 0, size);
183
184
185
186
	INIT_LIST_HEAD(&ci->changed_list);
	ci->touched_next = env->touched;
	ci->orig_col     = get_irn_col(env->co, irn);
	env->touched     = ci;
Sebastian Hack's avatar
Sebastian Hack committed
187
188
	ci->irn          = irn;
	ci->aff          = a;
189

Sebastian Hack's avatar
Sebastian Hack committed
190
191
192
193
194
	if(a) {
		co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
		INIT_LIST_HEAD(&cci->cloud_list);
		cci->mst_parent   = cci;
	}
195

Sebastian Hack's avatar
Sebastian Hack committed
196
	return ci;
197
198
}

Sebastian Hack's avatar
Sebastian Hack committed
199
#define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
Sebastian Hack's avatar
Sebastian Hack committed
200
201

static int cmp_clouds_gt(const void *a, const void *b)
202
{
Christoph Mallon's avatar
Christoph Mallon committed
203
204
	const co2_cloud_t * const *p = a;
	const co2_cloud_t * const *q = b;
Sebastian Hack's avatar
Sebastian Hack committed
205
206
	double c = CLOUD_WEIGHT(*p);
	double d = CLOUD_WEIGHT(*q);
207
	return QSORT_CMP(d, c);
208
209
}

210
211
212
213
214
215
216
217
/**
 * An order on color/costs pairs.
 * If the costs are equal, we use the color as a kind of normalization.
 */
static int col_cost_pair_lt(const void *a, const void *b)
{
	const col_cost_pair_t *p = a;
	const col_cost_pair_t *q = b;
218
219
	int c = p->costs;
	int d = q->costs;
220
	return QSORT_CMP(c, d);
221
222
}

223
224
225
226
227
228
229
int cmp_edges(const void *a, const void *b)
{
	const edge_t *p = a;
	const edge_t *q = b;
	return QSORT_CMP(q->costs, p->costs);
}

230
231
232
233
234
235
static col_t get_col(co2_t *env, ir_node *irn)
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
}

236
static INLINE int color_is_fix(co2_t *env, ir_node *irn)
237
238
239
240
241
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	return ci->fixed || ci->tmp_fixed;
}

242
static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
243
{
244
245
246
247
	if(!ci->adm_cache) {
		arch_register_req_t req;
		ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
		arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
Sebastian Hack's avatar
Sebastian Hack committed
248
		if(arch_register_req_is(&req, limited)) {
249
			req.limited(req.limited_env, ci->adm_cache);
Sebastian Hack's avatar
Sebastian Hack committed
250
251
			ci->is_constrained = 1;
		}
252
253
254
255
		else {
			bitset_copy(ci->adm_cache, env->ignore_regs);
			bitset_flip_all(ci->adm_cache);
		}
256
257
	}

258
259
260
	return ci->adm_cache;
}

Sebastian Hack's avatar
Sebastian Hack committed
261
static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
262
263
{
	bitset_copy(bs, get_adm(env, ci));
264
265
266
	return bs;
}

Sebastian Hack's avatar
Sebastian Hack committed
267
static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
268
{
269
	bitset_t *bs = get_adm(env, ci);
270
271
272
	return bitset_is_set(bs, col);
}

Sebastian Hack's avatar
Sebastian Hack committed
273
274
275
276
277
278
279
static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
{
	if(!ci->adm_cache)
		get_adm(env, ci);
	return ci->is_constrained;
}

280
281
282
283
284
285
286
287
288
289
290
291
292
static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
{
	bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
	arch_register_req_t req;

	arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));

	if(arch_register_req_is(&req, limited)) {
		bitset_pos_t elm;
		int n_constr;

		req.limited(req.limited_env, aux);
		n_constr = bitset_popcnt(aux);
293
		bitset_foreach(aux, elm) {
Sebastian Hack's avatar
Sebastian Hack committed
294
			col_costs[elm].costs  = add_saturated(col_costs[elm].costs, costs / n_constr);
295
		}
296
297
298
299
300
301
302
303
304
305
306
307
308
	}
}

/**
 * Determine costs which shall indicate how cheap/expensive it is to try
 * to assign a node some color.
 * The costs are computed for all colors. INT_MAX means that it is impossible
 * to give the node that specific color.
 *
 * @param env       The co2 this pointer.
 * @param irn       The node.
 * @param col_costs An array of colors x costs where the costs are written to.
 */
309
static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
310
{
311
	ir_node *irn       = ci->irn;
312
313
314
	be_ifg_t *ifg      = env->co->cenv->ifg;
	int n_regs         = env->co->cls->n_regs;
	bitset_t *forb     = bitset_alloca(n_regs);
315
	affinity_node_t *a = ci->aff;
316
317
318
319
320
321

	bitset_pos_t elm;
	ir_node *pos;
	void *it;
	int i;

322
323
324
	/* Put all forbidden colors into the aux bitset. */
	admissible_colors(env, ci, forb);
	bitset_flip_all(forb);
325
326
327
328
329
330
331
332
333
334

	for(i = 0; i < n_regs; ++i) {
		col_costs[i].col   = i;
		col_costs[i].costs = 0;
	}

	if(a) {
		neighb_t *n;

		co_gs_foreach_neighb(a, n) {
335
			if(color_is_fix(env, n->irn)) {
336
				col_t col = get_col(env, n->irn);
Sebastian Hack's avatar
Sebastian Hack committed
337
				col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
338
339
340
341
342
343
344
345
346
			}

			incur_constraint_costs(env, n->irn, col_costs, -n->costs);
		}
	}

	it = be_ifg_neighbours_iter_alloca(ifg);
	be_ifg_foreach_neighbour(ifg, it, irn, pos) {
		col_t col = get_col(env, pos);
347
348
349
		if(color_is_fix(env, pos)) {
			col_costs[col].costs  = INT_MAX;
		}
350
351
		else {
			incur_constraint_costs(env, pos, col_costs, INT_MAX);
Sebastian Hack's avatar
Sebastian Hack committed
352
			col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
353
354
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
355
	be_ifg_neighbours_break(ifg, it);
356
357

	/* Set the costs to infinity for each color which is not allowed at this node. */
358
359
360
361
362
363
	bitset_foreach(forb, elm) {
		col_costs[elm].costs  = INT_MAX;
	}

}

364
static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
365
366
367
{
	int n_regs = env->co->cls->n_regs;
	int i;
368

369
370
371
372
373
	for(i = 0; i < n_regs; ++i) {
		seq[i].col   = i;
		seq[i].costs = INT_MAX;
	}

374
	assert(is_color_admissible(env, ci, col));
375
376
377
378
379
	seq[col].col = 0;
	seq[0].col   = col;
	seq[0].costs = 0;
}

380
381
382
383
384
385
386
387
static void reject_coloring(struct list_head *h)
{
	co2_irn_t *pos;

	list_for_each_entry(co2_irn_t, pos, h, changed_list)
		pos->tmp_fixed = 0;
}

388
static void materialize_coloring(struct list_head *h)
389
390
391
392
{
	co2_irn_t *pos;

	list_for_each_entry(co2_irn_t, pos, h, changed_list) {
Sebastian Hack's avatar
Sebastian Hack committed
393
		pos->orig_col  = pos->tmp_col;
394
395
396
397
		pos->tmp_fixed = 0;
	}
}

398
399
400
static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);

static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
401
{
402
403
404
405
	int n_regs         = env->co->cls->n_regs;
	be_ifg_t *ifg      = env->co->cenv->ifg;
	co2_irn_t *ci      = get_co2_irn(env, irn);
	int res            = 0;
406
407
408

	int i;

Adam Szalkowski's avatar
Adam Szalkowski committed
409
410
411
	if(depth >= max_depth)
	  return 0;

412
413
414
415
416
417
418
419
420
	for(i = 0; i < n_regs; ++i) {
		col_t tgt_col  = col_list[i].col;
		unsigned costs = col_list[i].costs;
		int neigh_ok   = 1;

		struct list_head changed;
		ir_node *n;
		void *it;

Sebastian Hack's avatar
Sebastian Hack committed
421
		DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
422
423

		/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
424
		if(INFEASIBLE(costs)) {
Sebastian Hack's avatar
Sebastian Hack committed
425
			DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
426
427
428
429
430
			ci->tmp_fixed = 0;
			return 0;
		}

		/* Set the new color of the node and mark the node as temporarily fixed. */
Sebastian Hack's avatar
Sebastian Hack committed
431
432
		ci->tmp_col     = tgt_col;
		ci->tmp_fixed   = 1;
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460

		/*
		If that color has costs > 0, there's at least one neighbor having that color,
		so we will try to change the neighbors' colors, too.
		*/
		INIT_LIST_HEAD(&changed);
		list_add(&ci->changed_list, &changed);

		it = be_ifg_neighbours_iter_alloca(ifg);
		be_ifg_foreach_neighbour(ifg, it, irn, n) {

			/* try to re-color the neighbor if it has the target color. */
			if(get_col(env, n) == tgt_col) {
				struct list_head tmp;

				/*
				Try to change the color of the neighbor and record all nodes which
				get changed in the tmp list. Add this list to the "changed" list for
				that color. If we did not succeed to change the color of the neighbor,
				we bail out and try the next color.
				*/
				INIT_LIST_HEAD(&tmp);
				neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
				list_splice(&tmp, &changed);
				if(!neigh_ok)
					break;
			}
		}
Sebastian Hack's avatar
Sebastian Hack committed
461
		be_ifg_neighbours_break(ifg, it);
462
463
464
465
466
467

		/*
		We managed to assign the target color to all neighbors, so from the perspective
		of the current node, every thing was ok and we can return safely.
		*/
		if(neigh_ok) {
Sebastian Hack's avatar
Sebastian Hack committed
468
			DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
			list_splice(&changed, parent_changed);
			res = 1;
			break;
		}

		/*
		If not, that color did not succeed and we unfix all nodes we touched
		by traversing the changed list and setting tmp_fixed to 0 for these nodes.
		*/
		else
			reject_coloring(&changed);
	}

	return res;
}

static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	int res       = 0;
	col_t col     = get_col(env, irn);

Sebastian Hack's avatar
Sebastian Hack committed
491
	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
492
493
494
495

	/* the node does not have to forbidden color. That's fine, mark it as visited and return. */
	if(col != not_col) {
		if(!ci->tmp_fixed) {
Sebastian Hack's avatar
Sebastian Hack committed
496
497
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
498
499
500
501
502
503
504
505
506
507
508
509
		}

		list_add(&ci->changed_list, parent_changed);
		return 1;
	}

	/* The node has the color it should not have _and_ has not been visited yet. */
	if(!color_is_fix(env, irn)) {
		int n_regs            = env->co->cls->n_regs;
		col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));

		/* Get the costs for giving the node a specific color. */
510
		determine_color_costs(env, ci, csts);
511
512
513
514
515
516
517
518

		/* Since the node must not have the not_col, set the costs for that color to "infinity" */
		csts[not_col].costs = INT_MAX;

		/* sort the colors according costs, cheapest first. */
		qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);

		/* Try recoloring the node using the color list. */
519
		res = recolor(env, irn, csts, parent_changed, depth);
520
521
522
523
524
525
	}

	/* If we came here, everything went ok. */
	return res;
}

526
static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
527
528
{
	co2_irn_t *ci = get_co2_irn(env, irn);
529
530
	col_t col     = get_col(env, irn);
	int res       = 0;
531

Sebastian Hack's avatar
Sebastian Hack committed
532
	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
533

534
535
536
	/* the node has the wanted color. That's fine, mark it as visited and return. */
	if(col == tgt_col) {
		if(!ci->tmp_fixed) {
Sebastian Hack's avatar
Sebastian Hack committed
537
538
539
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
			list_add(&ci->changed_list, parent_changed);
540
		}
541

542
543
		res = 1;
		goto end;
544
545
	}

546
	if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
547
548
		int n_regs           = env->co->cls->n_regs;
		col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
549

550
		/* Get the costs for giving the node a specific color. */
551
		single_color_cost(env, ci, tgt_col, seq);
552
553
554
555
556
557

		/* Try recoloring the node using the color list. */
		res = recolor(env, irn, seq, parent_changed, depth);

	}

558
559
end:
	DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
560
	return res;
561
562
}

563
564
565
566
567
568
/**
 * Examine the costs of the current coloring concerning a MST subtree.
 * @param ci  The subtree root.
 * @param col The color of @p ci.
 * @return    The best coloring for that subtree under the assumption that @p ci has color @p col.
 */
Sebastian Hack's avatar
Sebastian Hack committed
569
570
571
572
573
static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
{
	int *front = FRONT_BASE(ci, col);
	int cost   = 0;
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
574

Sebastian Hack's avatar
Sebastian Hack committed
575
576
577
	for(i = 0; i < ci->mst_n_childs; ++i) {
		co2_cloud_irn_t *chld = ci->mst_childs[i];
		col_t chld_col        = front[i];
578

Sebastian Hack's avatar
Sebastian Hack committed
579
580
581
		cost += examine_subtree_coloring(chld, chld_col);
		cost += col != chld_col ? chld->mst_costs : 0;
	}
582

Sebastian Hack's avatar
Sebastian Hack committed
583
584
	return cost;
}
585

586
587
588
589
590
591
592
593
594
/**
 * Determine color badnesses of a node.
 * Badness means that it is unlikely that the node in question can
 * obtain a color. The higher the badness, the more unlikely it is that
 * the node can be assigned that color.
 * @param ci      The node.
 * @param badness An integer array as long as there are registers.
 * @note          The array <code>badness</code> is not cleared.
 */
Sebastian Hack's avatar
Sebastian Hack committed
595
static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
596
597
{
	co2_t *env     = ci->cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
598
	co2_irn_t *ir  = &ci->inh;
599
600
601
602
603
604
605
606
607
608
609
	int n_regs     = env->n_regs;
	be_ifg_t *ifg  = env->co->cenv->ifg;
	bitset_t *bs   = bitset_alloca(n_regs);

	bitset_pos_t elm;
	ir_node *irn;
	void *it;

	admissible_colors(env, &ci->inh, bs);
	bitset_flip_all(bs);
	bitset_foreach(bs, elm)
Sebastian Hack's avatar
Sebastian Hack committed
610
		badness[elm] = ci->costs;
611
612
613
614
615
616
617

	/* Use constrained/fixed interfering neighbors to influence the color badness */
	it = be_ifg_neighbours_iter_alloca(ifg);
	be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
		co2_irn_t *ni = get_co2_irn(env, irn);

		admissible_colors(env, ni, bs);
Sebastian Hack's avatar
Sebastian Hack committed
618
619
620
621
		if(bitset_popcnt(bs) == 1) {
			bitset_pos_t c = bitset_next_set(bs, 0);
			badness[c] += ci->costs;
		}
622

Sebastian Hack's avatar
Sebastian Hack committed
623
		else if(ni->fixed) {
624
			col_t c = get_col(env, ni->irn);
Sebastian Hack's avatar
Sebastian Hack committed
625
			badness[c] += ci->costs;
626
627
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
628
629
630
	be_ifg_neighbours_break(ifg, it);
}

631
632
633
634
635
636
637
/**
 * Determine the badness of a MST subtree.
 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
 * @see node_color_badness() for a definition of badness.
 * @param ci    The root of the subtree.
 * @param depth Depth for debugging purposes.
 */
Sebastian Hack's avatar
Sebastian Hack committed
638
639
640
641
642
643
static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
{
	co2_t *env     = ci->cloud->env;
	int i, j;

	node_color_badness(ci, ci->color_badness);
644
645
646
647
648
649

	/* Collect the color badness for the whole subtree */
	for(i = 0; i < ci->mst_n_childs; ++i) {
		co2_cloud_irn_t *child = ci->mst_childs[i];
		determine_color_badness(child, depth + 1);

Sebastian Hack's avatar
Sebastian Hack committed
650
		for(j = 0; j < env->n_regs; ++j)
651
652
653
			ci->color_badness[j] += child->color_badness[j];
	}

Sebastian Hack's avatar
Sebastian Hack committed
654
	for(j = 0; j < env->n_regs; ++j)
655
656
657
		DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
}

658
659
660
/**
 * Unfix all nodes in a MST subtree.
 */
Sebastian Hack's avatar
Sebastian Hack committed
661
662
663
static void unfix_subtree(co2_cloud_irn_t *ci)
{
	int i;
664

Sebastian Hack's avatar
Sebastian Hack committed
665
666
667
668
	ci->inh.fixed = 0;
	for(i = 0; i < ci->mst_n_childs; ++i)
		unfix_subtree(ci->mst_childs[i]);
}
669

Sebastian Hack's avatar
Sebastian Hack committed
670
static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
671
672
673
674
675
676
677
678
{
	co2_t *env           = ci->cloud->env;
	col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
	int is_root          = ci->mst_parent == ci;
	col_t parent_col     = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
	int min_badness      = INT_MAX;
	int best_col_costs   = INT_MAX;
	int best_col         = -1;
Sebastian Hack's avatar
Sebastian Hack committed
679
680
	int n_regs           = env->n_regs;
	int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
681
682
683
684

	struct list_head changed;
	int ok, i, j;

Sebastian Hack's avatar
Sebastian Hack committed
685
	for(i = 0; i < n_regs; ++i) {
686
687
688
		int badness = ci->color_badness[i];

		seq[i].col   = i;
Sebastian Hack's avatar
Sebastian Hack committed
689
		seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
690
691
692
693
694
695
696
697

		min_badness = MIN(min_badness, badness);
	}

	/* If we are not the root and the parent's color is allowed for this node give it top prio. */
	if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
		seq[parent_col].costs = min_badness - 1;

Sebastian Hack's avatar
Sebastian Hack committed
698
	/* Sort the colors. The will be processed in that ordering. */
699
700
	qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);

Sebastian Hack's avatar
Sebastian Hack committed
701
	DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
702
	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
703
	for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
704
705
706
707
708
709
		col_t col    = seq[i].col;
		int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;

		int subtree_costs, sum_costs;

		DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
Sebastian Hack's avatar
Sebastian Hack committed
710
711

		unfix_subtree(ci);
712
713
		INIT_LIST_HEAD(&changed);
		ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
Sebastian Hack's avatar
Sebastian Hack committed
714
715
716
717
718
719
720
		if(ok) {
			materialize_coloring(&changed);
			ci->inh.fixed = 1;
		}

		else
			continue;
721

Sebastian Hack's avatar
Sebastian Hack committed
722
723
724
725
726
727
728
		for(j = 0; j < ci->mst_n_childs; ++j) {
			co2_cloud_irn_t *child = ci->mst_childs[j];
			ok = coalesce_top_down(child, j, depth + 1) >= 0;
			if(ok)
				child->inh.fixed = 1;
			else
				break;
729
730
731
		}

		/* If the subtree could not be colored, we have to try another color. */
Sebastian Hack's avatar
Sebastian Hack committed
732
		if(!ok)
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
			continue;

		subtree_costs      = examine_subtree_coloring(ci, col);
		sum_costs          = subtree_costs + add_cost;
		DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));

		if(sum_costs < best_col_costs) {
			best_col           = col;
			best_col_costs     = sum_costs;
			ci->col_costs[col] = subtree_costs;
		}

		if(sum_costs == 0)
			break;
	}

	if(!is_root) {
		int *front = FRONT_BASE(ci->mst_parent, parent_col);
		front[child_nr] = best_col;
	}

	return best_col;
}

757
758
static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
{
Sebastian Hack's avatar
Sebastian Hack committed
759
760
761
	be_ifg_t *ifg       = env->co->cenv->ifg;
	co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
	int costs           = 0;
762
763
	neighb_t *n;

Sebastian Hack's avatar
Sebastian Hack committed
764
	if(ci->cloud)
765
766
767
768
769
770
		return;

	/* mark the node as visited and add it to the cloud. */
	ci->cloud   = cloud;
	list_add(&ci->cloud_list, &cloud->members_head);

Sebastian Hack's avatar
Sebastian Hack committed
771
	DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
772

773
774
775
	/* determine the nodes costs */
	co_gs_foreach_neighb(a, n) {
		costs += n->costs;
Sebastian Hack's avatar
Sebastian Hack committed
776
		DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
777
778
779
		if(be_ifg_connected(ifg, a->irn, n->irn))
			cloud->inevit += n->costs;
	}
780

781
782
783
	/* add the node's cost to the total costs of the cloud. */
	ci->costs          = costs;
	cloud->costs      += costs;
Sebastian Hack's avatar
Sebastian Hack committed
784
785
	cloud->n_constr   += is_constrained(env, &ci->inh);
	cloud->freedom    += bitset_popcnt(get_adm(env, &ci->inh));
Sebastian Hack's avatar
Sebastian Hack committed
786
	cloud->max_degree  = MAX(cloud->max_degree, ci->inh.aff->degree);
787
	cloud->n_memb++;
788

789
790
791
	/* If this is the heaviest node in the cloud, set it as the cloud's master. */
	if(costs >= curr_costs) {
		curr_costs    = costs;
Sebastian Hack's avatar
Sebastian Hack committed
792
		cloud->master = ci;
793
	}
794

795
796
797
798
799
	/* 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);
800
801
802
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
803
static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
804
{
Sebastian Hack's avatar
Sebastian Hack committed
805
	co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
Sebastian Hack's avatar
Sebastian Hack committed
806
807
808
809
	co2_cloud_irn_t *ci;
	int i;

	DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
Sebastian Hack's avatar
Sebastian Hack committed
810
811
812
813
814
815
	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;
816
817
	env->visited++;
	populate_cloud(env, cloud, a, 0);
Sebastian Hack's avatar
Sebastian Hack committed
818
	cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
819

Sebastian Hack's avatar
Sebastian Hack committed
820
821
822
	/* Also allocate space for the node sequence and compute that sequence. */
	cloud->seq    = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));

Sebastian Hack's avatar
Sebastian Hack committed
823
824
825
826
	i = 0;
	list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
		ci->index       = i;
		cloud->seq[i++] = ci;
Sebastian Hack's avatar
Sebastian Hack committed
827
	}
Sebastian Hack's avatar
Sebastian Hack committed
828
	DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
Sebastian Hack's avatar
Sebastian Hack committed
829

Sebastian Hack's avatar
Sebastian Hack committed
830
	return cloud;
831
}
832

Sebastian Hack's avatar
Sebastian Hack committed
833
static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
834
{
Sebastian Hack's avatar
Sebastian Hack committed
835
836
837
	ir_node *irn = ci->inh.irn;
	int *front   = FRONT_BASE(ci, col);
	int i, ok;
Sebastian Hack's avatar
Sebastian Hack committed
838
839
840
	struct list_head changed;

	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
841
842

	DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
Sebastian Hack's avatar
Sebastian Hack committed
843
	ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
Sebastian Hack's avatar
Sebastian Hack committed
844
	// assert(ok && "Color changing may not fail while committing the coloring");
Sebastian Hack's avatar
Sebastian Hack committed
845
	materialize_coloring(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
846

847
 	for(i = 0; i < ci->mst_n_childs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
848
		apply_coloring(ci->mst_childs[i], front[i], depth + 1);
Sebastian Hack's avatar
Sebastian Hack committed
849
850
851
	}
}

852
853
854
855
856
857
858
859
static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
{
	while(ci != ci->mst_parent)
		ci = ci->mst_parent;
	return ci;
}


Sebastian Hack's avatar
Sebastian Hack committed
860
861
862
static void process_cloud(co2_cloud_t *cloud)
{
	co2_t *env  = cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
863
	int n_regs  = env->n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
864
	int n_edges = 0;
Michael Beck's avatar
Michael Beck committed
865
	int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
Sebastian Hack's avatar
Sebastian Hack committed
866
	pdeq *q;
Sebastian Hack's avatar
Sebastian Hack committed
867
868

	edge_t *edges;
869
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
870
	int best_col;
871

Sebastian Hack's avatar
Sebastian Hack committed
872
873
	memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));

Sebastian Hack's avatar
Sebastian Hack committed
874
875
	/* Collect all edges in the cloud on an obstack and sort the increasingly */
	obstack_init(&cloud->obst);
876
	for(i = 0; i < cloud->n_memb; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
		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];
Sebastian Hack's avatar
Sebastian Hack committed
899
900
		co2_cloud_irn_t *rs = find_mst_root(e->src);
		co2_cloud_irn_t *rt = find_mst_root(e->tgt);
901

Sebastian Hack's avatar
Sebastian Hack committed
902
903
904
905
		/* if the union/find roots are different */
		if(rs != rt) {
			int si = e->src->index;
			int ti = e->tgt->index;
Sebastian Hack's avatar
Sebastian Hack committed
906

Sebastian Hack's avatar
Sebastian Hack committed
907
908
909
910
911
912
913
			/* 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;
Sebastian Hack's avatar
Sebastian Hack committed
914
		}
915
	}
Sebastian Hack's avatar
Sebastian Hack committed
916
	obstack_free(&cloud->obst, edges);
917

Sebastian Hack's avatar
Sebastian Hack committed
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
	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;
			}
		}

		obstack_ptr_grow(&cloud->obst, NULL);
		ci->mst_childs = obstack_finish(&cloud->obst);
	}
	del_pdeq(q);
	free(mst_edges);


	DBG((env->dbg, LEVEL_3, "mst:\n"));
	for(i = 0; i < cloud->n_memb; ++i) {
Matthias Braun's avatar
Matthias Braun committed
956
		DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
Sebastian Hack's avatar
Sebastian Hack committed
957
958
959
		DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
	}

Sebastian Hack's avatar
Sebastian Hack committed
960
961
	for(i = 0; i < cloud->n_memb; ++i) {
		co2_cloud_irn_t *ci = cloud->seq[i];
Sebastian Hack's avatar
Sebastian Hack committed
962
		int n_childs = ci->mst_n_childs;
963
964
		int j;

Sebastian Hack's avatar
Sebastian Hack committed
965
966
967
968
969
970
971
972
		ci->col_costs       = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
		ci->tmp_coloring    = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
		ci->fronts          = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
		ci->color_badness   = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
		memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
		memset(ci->col_costs,     0, n_regs * sizeof(ci->col_costs[0]));
		memset(ci->tmp_coloring,  0, n_regs * sizeof(ci->tmp_coloring[0]));
		memset(ci->fronts,        0, n_regs * n_childs * sizeof(ci->fronts[0]));
Sebastian Hack's avatar
Sebastian Hack committed
973

974
975
976
		for(j = 0; j < env->n_regs; j++)
			ci->col_costs[j] = INT_MAX;

Sebastian Hack's avatar
Sebastian Hack committed
977
	}
978

979
	determine_color_badness(cloud->mst_root, 0);
Sebastian Hack's avatar
Sebastian Hack committed
980
981
982
	best_col = coalesce_top_down(cloud->mst_root, -1, 0);
	unfix_subtree(cloud->mst_root);
	apply_coloring(cloud->mst_root, best_col, 0);
983
984

	/* The coloring should represent the one with the best costs. */
Sebastian Hack's avatar
Sebastian Hack committed
985
	//materialize_coloring(&changed);
986
987
988
989
	DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
		cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));

	/* Fix all nodes in the cloud. */
Sebastian Hack's avatar
Sebastian Hack committed
990
991
	for(i = 0; i < cloud->n_memb; ++i)
		cloud->seq[i]->inh.fixed = 1;
992

993
	/* Free all space used while optimizing this cloud. */
Sebastian Hack's avatar
Sebastian Hack committed
994
995
	obstack_free(&cloud->obst, NULL);
}
Sebastian Hack's avatar
Sebastian Hack committed
996

Sebastian Hack's avatar
Sebastian Hack committed
997
998
999
1000
static int cloud_costs(co2_cloud_t *cloud)
{
	int i, costs = 0;
	neighb_t *n;
Sebastian Hack's avatar
Sebastian Hack committed
1001

Sebastian Hack's avatar
Sebastian Hack committed
1002
1003
1004
1005
1006
1007
	for(i = 0; i < cloud->n_memb; ++i) {
		co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
		col_t col = get_col(cloud->env, ci->irn);
		co_gs_foreach_neighb(ci->aff, n) {
			col_t n_col = get_col(cloud->env, n->irn);
			costs += col != n_col ? n->costs : 0;
Sebastian Hack's avatar
Sebastian Hack committed
1008
1009
1010
		}
	}

Sebastian Hack's avatar
Sebastian Hack committed
1011
	return costs / 2;
1012
}
1013

1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
static void process(co2_t *env)
{
	affinity_node_t *a;
	co2_cloud_t *pos;
	co2_cloud_t **clouds;
	int n_clouds;
	int i;
	int init_costs  = 0;
	int all_costs   = 0;
	int final_costs = 0;
1024

1025
1026
	n_clouds = 0;
	co_gs_foreach_aff_node(env->co, a) {
Sebastian Hack's avatar
Sebastian Hack committed
1027
		co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1028
1029

		if(!ci->cloud) {
Matthias Braun's avatar
Matthias Braun committed
1030
			new_cloud(env, a);
1031
1032
			n_clouds++;
		}
1033
1034
	}

1035
1036
	i = 0;
	clouds = xmalloc(n_clouds * sizeof(clouds[0]));
Sebastian Hack's avatar
Sebastian Hack committed
1037
	list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1038
		clouds[i++] = pos;
Sebastian Hack's avatar
Sebastian Hack committed
1039
	qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1040
1041

	for(i = 0; i < n_clouds; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
1042
		init_costs  += cloud_costs(clouds[i]);
1043
1044

		/* Process the cloud. */
Sebastian Hack's avatar
Sebastian Hack committed
1045
		process_cloud(clouds[i]);
1046

1047
		all_costs   += clouds[i]->costs;
Sebastian Hack's avatar
Sebastian Hack committed
1048
1049
1050
1051
1052
1053
1054
1055
		final_costs += cloud_costs(clouds[i]);

		/* Dump the IFG if the user demanded it. */
		if (dump_flags & DUMP_CLOUD) {
			char buf[256];
			FILE *f;

			ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
Christoph Mallon's avatar
Christoph Mallon committed
1056
1057
			f = fopen(buf, "wt");
			if(f != NULL) {
Sebastian Hack's avatar
Sebastian Hack committed
1058
1059
1060
1061
				be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
				fclose(f);
			}
		}
1062
1063
1064
1065
1066
	}

	DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));

	xfree(clouds);
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
}

static void writeback_colors(co2_t *env)
{
	const arch_env_t *aenv = env->co->aenv;
	co2_irn_t *irn;

	for(irn = env->touched; irn; irn = irn->touched_next) {
		const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
		arch_set_irn_register(aenv, irn->irn, reg);
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
1080

Sebastian Hack's avatar
Sebastian Hack committed
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
/*
  ___ _____ ____   ____   ___ _____   ____                        _
 |_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
  | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
  | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
 |___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
                                                           |_|            |___/
*/

static const char *get_dot_color_name(int col)
{
	static const char *names[] = {
		"blue",
		"red",
		"green",
		"yellow",
		"cyan",
		"magenta",
		"orange",
		"chocolate",
		"beige",
		"navy",
		"darkgreen",
		"darkred",
		"lightPink",
		"chartreuse",
		"lightskyblue",
		"linen",
		"pink",
		"lightslateblue",
		"mintcream",
		"red",
		"darkolivegreen",
		"mediumblue",
		"mistyrose",
		"salmon",
		"darkseagreen",
		"mediumslateblue"
		"moccasin",
		"tomato",
		"forestgreen",
		"darkturquoise",
		"palevioletred"
	};

	return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
}

static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
{
	arch_register_req_t req;

	arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
	if(arch_register_req_is(&req, limited))
		return "diamond";

	if(ci->fixed)
		return "rectangle";

	if(ci->tmp_fixed)
		return "hexagon";

	return "ellipse";
}

static void ifg_dump_graph_attr(FILE *f, void *self)
{
	fprintf(f, "overlay=false");
}

static int ifg_is_dump_node(void *self, ir_node *irn)
{
	co2_t *env = self;
	return !arch_irn_is(env->co->aenv, irn, ignore);
}

static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
{
	co2_t *env    = self;
	co2_irn_t *ci = get_co2_irn(env, irn);
Sebastian Hack's avatar
Sebastian Hack committed
1161
1162
	int peri      = 1;

Sebastian Hack's avatar
Sebastian Hack committed
1163
1164
	char buf[128] = "";

Sebastian Hack's avatar
Sebastian Hack committed
1165
1166
1167
1168
	if(ci->aff) {
		co2_cloud_irn_t *cci = (void *) ci;
		if (cci->cloud && cci->cloud->mst_root == cci)
			peri = 2;
Sebastian Hack's avatar
Sebastian Hack committed
1169
1170

		if(cci->cloud && cci->cloud->mst_root)
Christoph Mallon's avatar
Christoph Mallon committed
1171
			ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
Sebastian Hack's avatar
Sebastian Hack committed
1172
	}
Sebastian Hack's avatar
Sebastian Hack committed
1173

Sebastian Hack's avatar
Sebastian Hack committed
1174
	ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
Sebastian Hack's avatar
Sebastian Hack committed
1175
1176
1177
1178
1179
1180
1181
1182
1183
		get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
}

static void ifg_dump_at_end(FILE *file, void *self)
{
	co2_t *env = self;
	affinity_node_t *a;

	co_gs_foreach_aff_node(env->co, a) {
Sebastian Hack's avatar
Sebastian Hack committed
1184
		co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
Sebastian Hack's avatar
Sebastian Hack committed
1185
1186
1187
		int idx = get_irn_idx(a->irn);
		neighb_t *n;

Sebastian Hack's avatar
Sebastian Hack committed
1188
1189
1190
		if(ai->mst_parent != ai)
			fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));

Sebastian Hack's avatar
Sebastian Hack committed
1191
1192
		co_gs_foreach_neighb(a, n) {
			int nidx = get_irn_idx(n->irn);
Sebastian Hack's avatar
Sebastian Hack committed
1193
			co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
Sebastian Hack's avatar
Sebastian Hack committed
1194
1195

			if(idx < nidx) {
Sebastian Hack's avatar
Sebastian Hack committed
1196
1197
1198
1199
1200
1201
1202
1203
1204
				const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
				const char *arr = "arrowhead=dot arrowtail=dot";

				if(ci->mst_parent == ai)
					arr = "arrowtail=normal";
				else if(ai->mst_parent == ci)
					arr = "arrowhead=normal";

				fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
Sebastian Hack's avatar
Sebastian Hack committed
1205
1206
1207
1208
1209
			}
		}
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
1210

Sebastian Hack's avatar
Sebastian Hack committed
1211
1212
1213
1214
1215
1216
1217
1218
1219
static be_ifg_dump_dot_cb_t ifg_dot_cb = {
	ifg_is_dump_node,
	ifg_dump_graph_attr,
	ifg_dump_node_attr,
	NULL,
	NULL,
	ifg_dump_at_end
};

Sebastian Hack's avatar