becopyheur2.c 33.8 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
/**
Christian Würdig's avatar
Christian Würdig committed
21
22
23
24
25
 * @file
 * @brief       More experiments on coalescing.
 * @author      Sebastian Hack
 * @date        14.04.2006
 * @version     $Id$
26
 */
27
#include "config.h"
Sebastian Hack's avatar
Sebastian Hack committed
28

Matthias Braun's avatar
Matthias Braun committed
29
30
#include "lc_opts.h"
#include "lc_opts_enum.h"
31

32
33
34
35
#include <stdlib.h>
#include <limits.h>

#include "list.h"
36
#include "pdeq.h"
37
#include "bitset.h"
Matthias Braun's avatar
Matthias Braun committed
38
#include "raw_bitset.h"
Sebastian Hack's avatar
Sebastian Hack committed
39

40
#include "debug.h"
Sebastian Hack's avatar
Sebastian Hack committed
41
#include "bitfiddle.h"
42
43
44
45
46

#include "irphase_t.h"
#include "irgraph_t.h"
#include "irnode_t.h"
#include "irprintf.h"
Sebastian Hack's avatar
Sebastian Hack committed
47
#include "irtools.h"
48

49
#include "bemodule.h"
50
#include "beabi.h"
51
#include "benode.h"
52
53
54
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"
55
#include "beirg.h"
56

Sebastian Hack's avatar
Sebastian Hack committed
57
58
59
#define DUMP_BEFORE 1
#define DUMP_AFTER  2
#define DUMP_CLOUD  4
60
#define DUMP_ALL    2 * DUMP_CLOUD - 1
Sebastian Hack's avatar
Sebastian Hack committed
61

Matthias Braun's avatar
Matthias Braun committed
62
63
64
65
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
66
67
68

static const lc_opt_enum_mask_items_t dump_items[] = {
	{ "before",  DUMP_BEFORE },
Adam Szalkowski's avatar
Adam Szalkowski committed
69
70
	{ "after",   DUMP_AFTER  },
	{ "cloud",   DUMP_CLOUD  },
71
	{ "all",     DUMP_ALL    },
Sebastian Hack's avatar
Sebastian Hack committed
72
73
74
75
76
77
78
79
	{ NULL,      0 }
};

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

static const lc_opt_table_entry_t options[] = {
80
81
	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
82
	LC_OPT_ENT_DBL      ("cf",   "factor of constraint importance (between 0.0 and 1.0)",  &constr_factor),
83
	LC_OPT_ENT_INT      ("max",  "maximum recursion depth",                                &max_depth),
84
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
85
86
87
88
89
90
91
92
93
94
95
};

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

*/

Sebastian Hack's avatar
Sebastian Hack committed
96
97
#define INFEASIBLE(cost) ((cost) == INT_MAX)

98
99
typedef unsigned col_t;

100
101
102
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;
Sebastian Hack's avatar
Sebastian Hack committed
103
104
105
106
107

typedef struct {
	col_t col;
	int costs;
} col_cost_pair_t;
108
109

typedef struct {
Michael Beck's avatar
Michael Beck committed
110
	ir_phase     ph;
111
	copy_opt_t *co;
112
	bitset_t   *allocatable_regs;
Sebastian Hack's avatar
Sebastian Hack committed
113
114
115
	co2_irn_t  *touched;
	int         visited;
	int         n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
116
	struct list_head cloud_head;
117
118
119
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
} co2_t;

120
struct co2_irn_t {
121
	const ir_node   *irn;
122
	affinity_node_t *aff;
Sebastian Hack's avatar
Sebastian Hack committed
123
	co2_irn_t       *touched_next;
124
125
	col_t            tmp_col;
	col_t            orig_col;
126
	int              last_color_change;
127
	bitset_t        *adm_cache;
Sebastian Hack's avatar
Sebastian Hack committed
128
129
130
	unsigned         fixed          : 1;
	unsigned         tmp_fixed      : 1;
	unsigned         is_constrained : 1;
131
	struct list_head changed_list;
Sebastian Hack's avatar
Sebastian Hack committed
132
133
};

134
135
struct co2_cloud_irn_t {
	struct co2_irn_t   inh;
Sebastian Hack's avatar
Sebastian Hack committed
136
137
138
139
140
141
142
143
144
145
	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;
146
	int               *color_badness;
Sebastian Hack's avatar
Sebastian Hack committed
147
148
149
	col_cost_pair_t   *tmp_coloring;
	struct list_head   cloud_list;
	struct list_head   mst_list;
150
151
};

152
struct co2_cloud_t {
Sebastian Hack's avatar
Sebastian Hack committed
153
154
155
156
157
158
159
	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
160
	int               n_constr;
Sebastian Hack's avatar
Sebastian Hack committed
161
	int               max_degree;
162
	int               ticks;
Sebastian Hack's avatar
Sebastian Hack committed
163
	double            freedom;
Sebastian Hack's avatar
Sebastian Hack committed
164
165
166
167
168
	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;
169
170
};

171
172
173
174
175
typedef struct {
	co2_cloud_irn_t *src, *tgt;
	int costs;
} edge_t;

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

Sebastian Hack's avatar
Sebastian Hack committed
178
179
#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))
180

181
static void *co2_irn_init(ir_phase *ph, const ir_node *irn)
182
{
Sebastian Hack's avatar
Sebastian Hack committed
183
184
185
	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);
186
	co2_irn_t *ci      = (co2_irn_t*)phase_alloc(ph, size);
187

Sebastian Hack's avatar
Sebastian Hack committed
188
	memset(ci, 0, size);
189
190
	INIT_LIST_HEAD(&ci->changed_list);
	ci->touched_next = env->touched;
191
	ci->orig_col     = get_irn_col(irn);
192
	env->touched     = ci;
Sebastian Hack's avatar
Sebastian Hack committed
193
194
	ci->irn          = irn;
	ci->aff          = a;
195

196
	if (a) {
Sebastian Hack's avatar
Sebastian Hack committed
197
198
199
200
		co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
		INIT_LIST_HEAD(&cci->cloud_list);
		cci->mst_parent   = cci;
	}
201

Sebastian Hack's avatar
Sebastian Hack committed
202
	return ci;
203
204
}

Sebastian Hack's avatar
Sebastian Hack committed
205
#define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
Sebastian Hack's avatar
Sebastian Hack committed
206
207

static int cmp_clouds_gt(const void *a, const void *b)
208
{
209
210
	const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
	const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
Sebastian Hack's avatar
Sebastian Hack committed
211
212
	double c = CLOUD_WEIGHT(*p);
	double d = CLOUD_WEIGHT(*q);
213
	return QSORT_CMP(d, c);
214
215
}

216
217
218
219
220
221
/**
 * 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)
{
222
223
	const col_cost_pair_t *p = (const col_cost_pair_t*)a;
	const col_cost_pair_t *q = (const col_cost_pair_t*)b;
224
225
	int c = p->costs;
	int d = q->costs;
226
	return QSORT_CMP(c, d);
227
228
}

229
static int cmp_edges(const void *a, const void *b)
230
{
231
232
	const edge_t *p = (const edge_t*)a;
	const edge_t *q = (const edge_t*)b;
233
234
235
	return QSORT_CMP(q->costs, p->costs);
}

236
static col_t get_col(co2_t *env, const ir_node *irn)
237
238
239
240
241
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
}

242
static inline int color_is_fix(co2_t *env, const ir_node *irn)
243
244
245
246
247
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	return ci->fixed || ci->tmp_fixed;
}

248
static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
249
{
250
	if (ci->adm_cache == NULL) {
Matthias Braun's avatar
Matthias Braun committed
251
		const arch_register_req_t *req;
252
		ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
253
		req = arch_get_register_req_out(ci->irn);
Matthias Braun's avatar
Matthias Braun committed
254

255
		if (arch_register_req_is(req, limited)) {
Matthias Braun's avatar
Matthias Braun committed
256
257
258
			int i, n;

			n = env->n_regs;
259
260
			for (i = 0; i < n; ++i) {
				if (rbitset_is_set(req->limited, i))
Matthias Braun's avatar
Matthias Braun committed
261
262
					bitset_set(ci->adm_cache, i);
			}
Sebastian Hack's avatar
Sebastian Hack committed
263
			ci->is_constrained = 1;
Matthias Braun's avatar
Matthias Braun committed
264
		} else {
265
			bitset_copy(ci->adm_cache, env->allocatable_regs);
266
		}
267
268
	}

269
270
271
	return ci->adm_cache;
}

272
static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
273
274
{
	bitset_copy(bs, get_adm(env, ci));
275
276
277
	return bs;
}

278
static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
279
{
280
	bitset_t *bs = get_adm(env, ci);
281
282
283
	return bitset_is_set(bs, col);
}

284
static inline int is_constrained(co2_t *env, co2_irn_t *ci)
Sebastian Hack's avatar
Sebastian Hack committed
285
{
286
	if (!ci->adm_cache)
Sebastian Hack's avatar
Sebastian Hack committed
287
288
289
290
		get_adm(env, ci);
	return ci->is_constrained;
}

291
static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
292
{
293
	const arch_register_req_t *req = arch_get_register_req_out(irn);
294

295
296
	if (arch_register_req_is(req, limited)) {
		unsigned n_regs   = env->co->cls->n_regs;
Matthias Braun's avatar
Matthias Braun committed
297
		unsigned n_constr = 0;
298
		unsigned i;
299

300
		n_constr = rbitset_popcount(req->limited, n_regs);
301
302
303
		for (i = 0; i < n_regs; ++i) {
			if (rbitset_is_set(req->limited, i)) {
				col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
Matthias Braun's avatar
Matthias Braun committed
304
			}
305
		}
306
307
308
309
310
311
312
313
314
315
316
317
318
	}
}

/**
 * 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.
 */
319
static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
320
{
321
	const ir_node *irn = ci->irn;
322
323
324
	be_ifg_t *ifg      = env->co->cenv->ifg;
	int n_regs         = env->co->cls->n_regs;
	bitset_t *forb     = bitset_alloca(n_regs);
325
	affinity_node_t *a = ci->aff;
326

327
	size_t elm;
328
	const ir_node *pos;
329
	neighbours_iter_t it;
330
331
	int i;

332
333
334
	/* Put all forbidden colors into the aux bitset. */
	admissible_colors(env, ci, forb);
	bitset_flip_all(forb);
335

336
	for (i = 0; i < n_regs; ++i) {
337
338
339
340
		col_costs[i].col   = i;
		col_costs[i].costs = 0;
	}

341
	if (a) {
342
343
344
		neighb_t *n;

		co_gs_foreach_neighb(a, n) {
345
			if (color_is_fix(env, n->irn)) {
346
				col_t col = get_col(env, n->irn);
Sebastian Hack's avatar
Sebastian Hack committed
347
				col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
348
349
350
351
352
353
			}

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

354
	be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
355
		col_t col = get_col(env, pos);
356
		if (color_is_fix(env, pos)) {
357
358
			col_costs[col].costs  = INT_MAX;
		}
359
360
		else {
			incur_constraint_costs(env, pos, col_costs, INT_MAX);
Sebastian Hack's avatar
Sebastian Hack committed
361
			col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
362
363
		}
	}
364
	be_ifg_neighbours_break(&it);
365
366

	/* Set the costs to infinity for each color which is not allowed at this node. */
367
368
369
370
371
372
	bitset_foreach(forb, elm) {
		col_costs[elm].costs  = INT_MAX;
	}

}

373
static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
374
375
376
{
	int n_regs = env->co->cls->n_regs;
	int i;
377

378
	for (i = 0; i < n_regs; ++i) {
379
380
381
382
		seq[i].col   = i;
		seq[i].costs = INT_MAX;
	}

383
	(void) ci;
384
	assert(is_color_admissible(env, ci, col));
385
386
387
388
389
	seq[col].col = 0;
	seq[0].col   = col;
	seq[0].costs = 0;
}

390
391
392
393
394
395
396
397
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;
}

398
static void materialize_coloring(struct list_head *h)
399
400
401
402
{
	co2_irn_t *pos;

	list_for_each_entry(co2_irn_t, pos, h, changed_list) {
Sebastian Hack's avatar
Sebastian Hack committed
403
		pos->orig_col  = pos->tmp_col;
404
405
406
407
		pos->tmp_fixed = 0;
	}
}

408
static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
409

410
static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
411
{
412
413
414
415
	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;
416
417
418

	int i;

419
	if (depth >= max_depth)
Adam Szalkowski's avatar
Adam Szalkowski committed
420
421
	  return 0;

422
	for (i = 0; i < n_regs; ++i) {
423
424
425
426
427
		col_t tgt_col  = col_list[i].col;
		unsigned costs = col_list[i].costs;
		int neigh_ok   = 1;

		struct list_head changed;
428
		const ir_node *n;
429
		neighbours_iter_t it;
430

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

		/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
434
		if (INFEASIBLE(costs)) {
Sebastian Hack's avatar
Sebastian Hack committed
435
			DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
436
437
438
439
440
			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
441
442
		ci->tmp_col     = tgt_col;
		ci->tmp_fixed   = 1;
443
444
445
446
447
448
449
450

		/*
		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);

451
		be_ifg_foreach_neighbour(ifg, &it, irn, n) {
452
453

			/* try to re-color the neighbor if it has the target color. */
454
			if (get_col(env, n) == tgt_col) {
455
456
457
458
459
460
461
462
463
464
465
				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);
466
				if (!neigh_ok)
467
468
469
					break;
			}
		}
470
		be_ifg_neighbours_break(&it);
471
472
473
474
475

		/*
		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.
		*/
476
		if (neigh_ok) {
Sebastian Hack's avatar
Sebastian Hack committed
477
			DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
			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;
}

494
static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
495
496
497
498
499
{
	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
500
	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
501
502

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

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

	/* The node has the color it should not have _and_ has not been visited yet. */
514
	if (!color_is_fix(env, irn)) {
515
		int n_regs            = env->co->cls->n_regs;
516
		col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
517
518

		/* Get the costs for giving the node a specific color. */
519
		determine_color_costs(env, ci, csts);
520
521
522
523
524
525
526
527

		/* 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. */
528
		res = recolor(env, irn, csts, parent_changed, depth);
529
530
531
532
533
534
	}

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

535
static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
536
537
{
	co2_irn_t *ci = get_co2_irn(env, irn);
538
539
	col_t col     = get_col(env, irn);
	int res       = 0;
540

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

543
	/* the node has the wanted color. That's fine, mark it as visited and return. */
544
545
	if (col == tgt_col) {
		if (!ci->tmp_fixed) {
Sebastian Hack's avatar
Sebastian Hack committed
546
547
548
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
			list_add(&ci->changed_list, parent_changed);
549
		}
550

551
552
		res = 1;
		goto end;
553
554
	}

555
	if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
556
		int n_regs           = env->co->cls->n_regs;
557
		col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
558

559
		/* Get the costs for giving the node a specific color. */
560
		single_color_cost(env, ci, tgt_col, seq);
561
562
563
564
565
566

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

	}

567
568
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));
569
	return res;
570
571
}

572
573
574
575
576
577
/**
 * 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
578
579
580
581
582
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
583

584
	for (i = 0; i < ci->mst_n_childs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
585
586
		co2_cloud_irn_t *chld = ci->mst_childs[i];
		col_t chld_col        = front[i];
587

Sebastian Hack's avatar
Sebastian Hack committed
588
589
590
		cost += examine_subtree_coloring(chld, chld_col);
		cost += col != chld_col ? chld->mst_costs : 0;
	}
591

Sebastian Hack's avatar
Sebastian Hack committed
592
593
	return cost;
}
594

595
596
597
598
599
600
601
602
603
/**
 * 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
604
static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
605
606
{
	co2_t *env     = ci->cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
607
	co2_irn_t *ir  = &ci->inh;
608
609
610
611
	int n_regs     = env->n_regs;
	be_ifg_t *ifg  = env->co->cenv->ifg;
	bitset_t *bs   = bitset_alloca(n_regs);

612
	size_t elm;
613
	const ir_node *irn;
614
	neighbours_iter_t it;
615
616
617
618

	admissible_colors(env, &ci->inh, bs);
	bitset_flip_all(bs);
	bitset_foreach(bs, elm)
Sebastian Hack's avatar
Sebastian Hack committed
619
		badness[elm] = ci->costs;
620
621

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

		admissible_colors(env, ni, bs);
626
		if (bitset_popcount(bs) == 1) {
627
			size_t c = bitset_next_set(bs, 0);
Sebastian Hack's avatar
Sebastian Hack committed
628
629
			badness[c] += ci->costs;
		}
630

631
		else if (ni->fixed) {
632
			col_t c = get_col(env, ni->irn);
Sebastian Hack's avatar
Sebastian Hack committed
633
			badness[c] += ci->costs;
634
635
		}
	}
636
	be_ifg_neighbours_break(&it);
Sebastian Hack's avatar
Sebastian Hack committed
637
638
}

639
640
641
642
643
644
645
/**
 * 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
646
647
648
649
650
651
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);
652
653

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

658
		for (j = 0; j < env->n_regs; ++j)
659
660
661
			ci->color_badness[j] += child->color_badness[j];
	}

662
	for (j = 0; j < env->n_regs; ++j)
663
664
665
		DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
}

666
667
668
/**
 * Unfix all nodes in a MST subtree.
 */
Sebastian Hack's avatar
Sebastian Hack committed
669
670
671
static void unfix_subtree(co2_cloud_irn_t *ci)
{
	int i;
672

Sebastian Hack's avatar
Sebastian Hack committed
673
	ci->inh.fixed = 0;
674
	for (i = 0; i < ci->mst_n_childs; ++i)
Sebastian Hack's avatar
Sebastian Hack committed
675
676
		unfix_subtree(ci->mst_childs[i]);
}
677

Sebastian Hack's avatar
Sebastian Hack committed
678
static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
679
680
{
	co2_t *env           = ci->cloud->env;
681
	col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
682
	int is_root          = ci->mst_parent == ci;
Matthias Braun's avatar
Matthias Braun committed
683
	col_t parent_col     = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
684
685
686
	int min_badness      = INT_MAX;
	int best_col_costs   = INT_MAX;
	int best_col         = -1;
Sebastian Hack's avatar
Sebastian Hack committed
687
688
	int n_regs           = env->n_regs;
	int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
689
690
691
692

	struct list_head changed;
	int ok, i, j;

693
	for (i = 0; i < n_regs; ++i) {
694
695
696
		int badness = ci->color_badness[i];

		seq[i].col   = i;
Sebastian Hack's avatar
Sebastian Hack committed
697
		seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
698
699
700
701
702

		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. */
703
	if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
704
705
		seq[parent_col].costs = min_badness - 1;

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

Sebastian Hack's avatar
Sebastian Hack committed
709
	DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
710
	INIT_LIST_HEAD(&changed);
711
	for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
712
713
714
715
716
717
		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
718
719

		unfix_subtree(ci);
720
721
		INIT_LIST_HEAD(&changed);
		ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
722
		if (ok) {
Sebastian Hack's avatar
Sebastian Hack committed
723
724
725
726
727
728
			materialize_coloring(&changed);
			ci->inh.fixed = 1;
		}

		else
			continue;
729

730
		for (j = 0; j < ci->mst_n_childs; ++j) {
Sebastian Hack's avatar
Sebastian Hack committed
731
732
			co2_cloud_irn_t *child = ci->mst_childs[j];
			ok = coalesce_top_down(child, j, depth + 1) >= 0;
733
			if (ok)
Sebastian Hack's avatar
Sebastian Hack committed
734
735
736
				child->inh.fixed = 1;
			else
				break;
737
738
739
		}

		/* If the subtree could not be colored, we have to try another color. */
740
		if (!ok)
741
742
743
744
745
746
			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));

747
		if (sum_costs < best_col_costs) {
748
749
750
751
752
			best_col           = col;
			best_col_costs     = sum_costs;
			ci->col_costs[col] = subtree_costs;
		}

753
		if (sum_costs == 0)
754
755
756
			break;
	}

757
	if (!is_root) {
758
759
760
761
762
763
764
		int *front = FRONT_BASE(ci->mst_parent, parent_col);
		front[child_nr] = best_col;
	}

	return best_col;
}

765
766
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
767
768
769
	be_ifg_t *ifg       = env->co->cenv->ifg;
	co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
	int costs           = 0;
770
771
	neighb_t *n;

772
	if (ci->cloud)
773
774
775
776
777
778
		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
779
	DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
780

781
782
783
	/* determine the nodes costs */
	co_gs_foreach_neighb(a, n) {
		costs += n->costs;
Sebastian Hack's avatar
Sebastian Hack committed
784
		DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
785
		if (be_ifg_connected(ifg, a->irn, n->irn))
786
787
			cloud->inevit += n->costs;
	}
788

789
790
791
	/* 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
792
	cloud->n_constr   += is_constrained(env, &ci->inh);
793
	cloud->freedom    += bitset_popcount(get_adm(env, &ci->inh));
Sebastian Hack's avatar
Sebastian Hack committed
794
	cloud->max_degree  = MAX(cloud->max_degree, ci->inh.aff->degree);
795
	cloud->n_memb++;
796

797
	/* If this is the heaviest node in the cloud, set it as the cloud's master. */
798
	if (costs >= curr_costs) {
799
		curr_costs    = costs;
Sebastian Hack's avatar
Sebastian Hack committed
800
		cloud->master = ci;
801
	}
802

803
804
805
806
807
	/* 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);
808
809
810
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
811
static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
812
{
813
	co2_cloud_t *cloud = (co2_cloud_t*)phase_alloc(&env->ph, sizeof(cloud[0]));
Sebastian Hack's avatar
Sebastian Hack committed
814
815
816
817
	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
818
819
820
821
822
823
	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;
824
825
	env->visited++;
	populate_cloud(env, cloud, a, 0);
Sebastian Hack's avatar
Sebastian Hack committed
826
	cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
827

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

Sebastian Hack's avatar
Sebastian Hack committed
831
832
833
834
	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
835
	}
Sebastian Hack's avatar
Sebastian Hack committed
836
	DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
Sebastian Hack's avatar
Sebastian Hack committed
837

Sebastian Hack's avatar
Sebastian Hack committed
838
	return cloud;
839
}
840

Sebastian Hack's avatar
Sebastian Hack committed
841
static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
842
{
843
	const ir_node *irn = ci->inh.irn;
Sebastian Hack's avatar
Sebastian Hack committed
844
845
	int *front   = FRONT_BASE(ci, col);
	int i, ok;
Sebastian Hack's avatar
Sebastian Hack committed
846
847
848
	struct list_head changed;

	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
849
850

	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
851
	ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
Sebastian Hack's avatar
Sebastian Hack committed
852
	// assert(ok && "Color changing may not fail while committing the coloring");
Sebastian Hack's avatar
Sebastian Hack committed
853
	materialize_coloring(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
854

855
	for (i = 0; i < ci->mst_n_childs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
856
		apply_coloring(ci->mst_childs[i], front[i], depth + 1);
Sebastian Hack's avatar
Sebastian Hack committed
857
858
859
	}
}

860
861
static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
{
862
	while (ci != ci->mst_parent)
863
864
865
866
867
		ci = ci->mst_parent;
	return ci;
}


Sebastian Hack's avatar
Sebastian Hack committed
868
869
870
static void process_cloud(co2_cloud_t *cloud)
{
	co2_t *env  = cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
871
	int n_regs  = env->n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
872
	int n_edges = 0;
873
	int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
Sebastian Hack's avatar
Sebastian Hack committed
874
	pdeq *q;
Sebastian Hack's avatar
Sebastian Hack committed
875
876

	edge_t *edges;
877
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
878
	int best_col;
879

Sebastian Hack's avatar
Sebastian Hack committed
880
881
	/* Collect all edges in the cloud on an obstack and sort the increasingly */
	obstack_init(&cloud->obst);
882
	for (i = 0; i < cloud->n_memb; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
883
884
885
886
887
		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);
888
			if (ci->index < ni->index) {
Sebastian Hack's avatar
Sebastian Hack committed
889
890
891
892
893
894
895
896
897
				edge_t e;
				e.src   = ci;
				e.tgt   = ni;
				e.costs = n->costs;
				obstack_grow(&cloud->obst, &e, sizeof(e));
				n_edges++;
			}
		}
	}
898
	edges = (edge_t*)obstack_finish(&cloud->obst);
Sebastian Hack's avatar
Sebastian Hack committed
899
900
901
902
	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));
903
	for (i = 0; i < n_edges; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
904
		edge_t *e        = &edges[i];
Sebastian Hack's avatar
Sebastian Hack committed
905
906
		co2_cloud_irn_t *rs = find_mst_root(e->src);
		co2_cloud_irn_t *rt = find_mst_root(e->tgt);
907

Sebastian Hack's avatar
Sebastian Hack committed
908
		/* if the union/find roots are different */
909
		if (rs != rt) {
Sebastian Hack's avatar
Sebastian Hack committed
910
911
			int si = e->src->index;
			int ti = e->tgt->index;
Sebastian Hack's avatar
Sebastian Hack committed
912

Sebastian Hack's avatar
Sebastian Hack committed
913
914
915
916
917
918
919
			/* 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
920
		}
921
	}
Sebastian Hack's avatar
Sebastian Hack committed
922
	obstack_free(&cloud->obst, edges);
923

Sebastian Hack's avatar
Sebastian Hack committed
924
925
926
	cloud->master->mst_parent = cloud->master;
	cloud->mst_root = cloud->master;
	q = new_pdeq1(cloud->master);
927
	while (!pdeq_empty(q)) {
928
		co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
Sebastian Hack's avatar
Sebastian Hack committed
929
930
931
932
933
		int ofs    = ci->index * cloud->n_memb;
		int end    = ofs + cloud->n_memb;
		int i;

		ci->mst_n_childs = 0;
934
935
		for (i = ofs; i < end; ++i) {
			if (mst_edges[i] != 0) {
Sebastian Hack's avatar
Sebastian Hack committed
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951