becopyheur2.c 27.9 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

6
/**
Christian Würdig's avatar
Christian Würdig committed
7
8
9
10
 * @file
 * @brief       More experiments on coalescing.
 * @author      Sebastian Hack
 * @date        14.04.2006
11
 */
Matthias Braun's avatar
Matthias Braun committed
12
13
#include "lc_opts.h"
#include "lc_opts_enum.h"
14

15
16
17
#include <stdlib.h>
#include <limits.h>

Matthias Braun's avatar
Matthias Braun committed
18
#include "belive_t.h"
19
#include "beirg.h"
20
#include "list.h"
21
#include "pdeq.h"
Matthias Braun's avatar
Matthias Braun committed
22
#include "raw_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

#include "irgraph_t.h"
#include "irnode_t.h"
29
#include "util.h"
Sebastian Hack's avatar
Sebastian Hack committed
30
#include "irtools.h"
31
#include "irnodemap.h"
32
#include "be_t.h"
33
#include "bemodule.h"
34
#include "beabi.h"
35
#include "benode.h"
36
37
38
39
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"

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

Matthias Braun's avatar
Matthias Braun committed
45
46
47
48
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
49
50
51

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

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

static const lc_opt_table_entry_t options[] = {
63
64
	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
65
	LC_OPT_ENT_DBL      ("cf",   "factor of constraint importance (between 0.0 and 1.0)",  &constr_factor),
66
	LC_OPT_ENT_INT      ("max",  "maximum recursion depth",                                &max_depth),
67
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
68
69
70
71
72
73
74
75
76
77
78
};

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

*/

Sebastian Hack's avatar
Sebastian Hack committed
79
80
#define INFEASIBLE(cost) ((cost) == INT_MAX)

81
82
typedef unsigned col_t;

83
84
85
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
86
87
88
89
90

typedef struct {
	col_t col;
	int costs;
} col_cost_pair_t;
91
92

typedef struct {
93
94
95
96
97
98
99
	ir_nodemap       map;
	struct obstack   obst;
	copy_opt_t      *co;
	unsigned const  *allocatable_regs;
	co2_irn_t       *touched;
	int              visited;
	int              n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
100
	struct list_head cloud_head;
101
102
103
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
} co2_t;

104
struct co2_irn_t {
105
	const ir_node   *irn;
106
	affinity_node_t *aff;
Sebastian Hack's avatar
Sebastian Hack committed
107
	co2_irn_t       *touched_next;
108
109
	col_t            tmp_col;
	col_t            orig_col;
110
	unsigned const  *admissible;
Sebastian Hack's avatar
Sebastian Hack committed
111
112
	unsigned         fixed          : 1;
	unsigned         tmp_fixed      : 1;
113
	struct list_head changed_list;
Sebastian Hack's avatar
Sebastian Hack committed
114
115
};

116
117
struct co2_cloud_irn_t {
	struct co2_irn_t   inh;
Sebastian Hack's avatar
Sebastian Hack committed
118
119
120
121
122
123
124
125
126
127
	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;
128
	int               *color_badness;
Sebastian Hack's avatar
Sebastian Hack committed
129
130
131
	col_cost_pair_t   *tmp_coloring;
	struct list_head   cloud_list;
	struct list_head   mst_list;
132
133
};

134
struct co2_cloud_t {
Sebastian Hack's avatar
Sebastian Hack committed
135
136
137
138
139
140
141
	co2_t            *env;
	struct obstack    obst;
	int               costs;
	int               mst_costs;
	int               inevit;
	int               best_costs;
	int               n_memb;
142
	int               ticks;
Sebastian Hack's avatar
Sebastian Hack committed
143
	double            freedom;
Sebastian Hack's avatar
Sebastian Hack committed
144
145
146
147
148
	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;
149
150
};

151
152
153
154
155
typedef struct {
	co2_cloud_irn_t *src, *tgt;
	int costs;
} edge_t;

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

158
159
static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node)
{
160
	co2_irn_t *ci = ir_nodemap_get(co2_irn_t, &env->map, node);
161
162
163
164
165
166
167
168
169
170
	if (ci == NULL) {
		ci = OALLOCZ(&env->obst, co2_irn_t);

		INIT_LIST_HEAD(&ci->changed_list);
		ci->touched_next = env->touched;
		ci->orig_col     = get_irn_col(node);
		env->touched     = ci;
		ci->irn          = node;
		ci->aff          = NULL;

171
		arch_register_req_t const *const req = arch_get_irn_register_req(node);
172
		ci->admissible = arch_register_req_is(req, limited) ? req->limited : env->allocatable_regs;
173

174
175
176
177
		ir_nodemap_insert(&env->map, node, ci);
	}
	return ci;
}
178

179
static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
180
{
181
	co2_cloud_irn_t *ci = ir_nodemap_get(co2_cloud_irn_t, &env->map, node);
182
183
	if (ci == NULL) {
		ci = OALLOCZ(&env->obst, co2_cloud_irn_t);
184

185
186
187
188
189
190
		INIT_LIST_HEAD(&ci->inh.changed_list);
		ci->inh.touched_next = env->touched;
		ci->inh.orig_col     = get_irn_col(node);
		env->touched         = &ci->inh;
		ci->inh.irn          = node;
		ci->inh.aff          = get_affinity_info(env->co, node);
191

192
193
194
195
196
		INIT_LIST_HEAD(&ci->cloud_list);
		ci->mst_parent = ci;

		ir_nodemap_insert(&env->map, node, ci);
	}
Sebastian Hack's avatar
Sebastian Hack committed
197
	return ci;
198
199
}

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

static int cmp_clouds_gt(const void *a, const void *b)
203
{
204
205
	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
206
207
	double c = CLOUD_WEIGHT(*p);
	double d = CLOUD_WEIGHT(*q);
208
	return QSORT_CMP(d, c);
209
210
}

211
212
213
214
215
216
/**
 * 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)
{
217
218
	const col_cost_pair_t *p = (const col_cost_pair_t*)a;
	const col_cost_pair_t *q = (const col_cost_pair_t*)b;
219
220
	int c = p->costs;
	int d = q->costs;
221
	return QSORT_CMP(c, d);
222
223
}

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

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

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

243
static inline int is_color_admissible(co2_irn_t *const ci, col_t const col)
244
{
245
	unsigned const *const bs = ci->admissible;
246
	return rbitset_is_set(bs, col);
247
248
}

249
static void incur_constraint_costs(ir_node const *const irn, col_cost_pair_t *const col_costs, int const costs)
250
{
251
	const arch_register_req_t *req = arch_get_irn_register_req(irn);
252

253
	if (arch_register_req_is(req, limited)) {
254
255
256
		unsigned const n_regs   = req->cls->n_regs;
		unsigned const n_constr = rbitset_popcount(req->limited, n_regs);
		for (unsigned i = 0; i < n_regs; ++i) {
257
258
			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
259
			}
260
		}
261
262
263
264
265
266
267
268
269
270
271
272
273
	}
}

/**
 * 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.
 */
274
static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
275
{
276
	const ir_node *irn = ci->irn;
277
278
	be_ifg_t *ifg      = env->co->cenv->ifg;
	int n_regs         = env->co->cls->n_regs;
279
	affinity_node_t *a = ci->aff;
280

281
	neighbours_iter_t it;
282
283
	int i;

284
	for (i = 0; i < n_regs; ++i) {
285
286
287
288
		col_costs[i].col   = i;
		col_costs[i].costs = 0;
	}

289
	if (a) {
290
		co_gs_foreach_neighb(a, n) {
291
			if (color_is_fix(env, n->irn)) {
292
				col_t col = get_col(env, n->irn);
Sebastian Hack's avatar
Sebastian Hack committed
293
				col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
294
295
			}

296
			incur_constraint_costs(n->irn, col_costs, -n->costs);
297
298
299
		}
	}

300
	be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
301
		col_t col = get_col(env, pos);
302
		if (color_is_fix(env, pos)) {
303
			col_costs[col].costs  = INT_MAX;
304
		} else {
305
			incur_constraint_costs(pos, col_costs, INT_MAX);
Sebastian Hack's avatar
Sebastian Hack committed
306
			col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
307
308
309
310
		}
	}

	/* Set the costs to infinity for each color which is not allowed at this node. */
311
	unsigned const *const admissible = ci->admissible;
312
	rbitset_foreach_clear(admissible, n_regs, elm) {
313
314
315
316
		col_costs[elm].costs  = INT_MAX;
	}
}

317
static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
318
319
320
{
	int n_regs = env->co->cls->n_regs;
	int i;
321

322
	for (i = 0; i < n_regs; ++i) {
323
324
325
326
		seq[i].col   = i;
		seq[i].costs = INT_MAX;
	}

327
	(void) ci;
328
	assert(is_color_admissible(ci, col));
329
330
331
332
333
	seq[col].col = 0;
	seq[0].col   = col;
	seq[0].costs = 0;
}

334
335
336
337
338
339
static void reject_coloring(struct list_head *h)
{
	list_for_each_entry(co2_irn_t, pos, h, changed_list)
		pos->tmp_fixed = 0;
}

340
static void materialize_coloring(struct list_head *h)
341
342
{
	list_for_each_entry(co2_irn_t, pos, h, changed_list) {
Sebastian Hack's avatar
Sebastian Hack committed
343
		pos->orig_col  = pos->tmp_col;
344
345
346
347
		pos->tmp_fixed = 0;
	}
}

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

350
static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
351
{
352
353
354
355
	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;
356
357
358

	int i;

359
	if (depth >= max_depth)
Adam Szalkowski's avatar
Adam Szalkowski committed
360
361
	  return 0;

362
	for (i = 0; i < n_regs; ++i) {
363
364
365
366
367
		col_t tgt_col  = col_list[i].col;
		unsigned costs = col_list[i].costs;
		int neigh_ok   = 1;

		struct list_head changed;
368
		neighbours_iter_t it;
369

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

		/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
373
		if (INFEASIBLE(costs)) {
Sebastian Hack's avatar
Sebastian Hack committed
374
			DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
375
376
377
378
379
			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
380
381
		ci->tmp_col     = tgt_col;
		ci->tmp_fixed   = 1;
382
383
384
385
386
387
388
389

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

390
		be_ifg_foreach_neighbour(ifg, &it, irn, n) {
391
392

			/* try to re-color the neighbor if it has the target color. */
393
			if (get_col(env, n) == tgt_col) {
394
395
396
397
398
399
400
401
402
403
404
				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);
405
406
				if (!neigh_ok) {
					be_ifg_neighbours_break(&it);
407
					break;
408
				}
409
410
411
412
413
414
415
			}
		}

		/*
		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.
		*/
416
		if (neigh_ok) {
Sebastian Hack's avatar
Sebastian Hack committed
417
			DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
			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;
}

434
static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
435
436
437
438
439
{
	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
440
	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
441
442

	/* the node does not have to forbidden color. That's fine, mark it as visited and return. */
443
444
	if (col != not_col) {
		if (!ci->tmp_fixed) {
Sebastian Hack's avatar
Sebastian Hack committed
445
446
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
447
448
449
450
451
452
453
		}

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

	/* The node has the color it should not have _and_ has not been visited yet. */
454
	if (!color_is_fix(env, irn)) {
455
		int n_regs            = env->co->cls->n_regs;
456
		col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
457
458

		/* Get the costs for giving the node a specific color. */
459
		determine_color_costs(env, ci, csts);
460
461
462
463
464

		/* 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. */
465
		QSORT(csts, n_regs, col_cost_pair_lt);
466
467

		/* Try recoloring the node using the color list. */
468
		res = recolor(env, irn, csts, parent_changed, depth);
469
470
471
472
473
474
	}

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

475
static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
476
477
{
	co2_irn_t *ci = get_co2_irn(env, irn);
478
479
	col_t col     = get_col(env, irn);
	int res       = 0;
480

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

483
	/* the node has the wanted color. That's fine, mark it as visited and return. */
484
485
	if (col == tgt_col) {
		if (!ci->tmp_fixed) {
Sebastian Hack's avatar
Sebastian Hack committed
486
487
488
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
			list_add(&ci->changed_list, parent_changed);
489
		}
490

491
492
		res = 1;
		goto end;
493
494
	}

495
	if (!color_is_fix(env, irn) && is_color_admissible(ci, tgt_col)) {
496
		int n_regs           = env->co->cls->n_regs;
497
		col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
498

499
		/* Get the costs for giving the node a specific color. */
500
		single_color_cost(env, ci, tgt_col, seq);
501
502
503
504
505
506

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

	}

507
508
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));
509
	return res;
510
511
}

512
513
514
515
516
517
/**
 * 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
518
519
520
521
522
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
523

524
	for (i = 0; i < ci->mst_n_childs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
525
526
		co2_cloud_irn_t *chld = ci->mst_childs[i];
		col_t chld_col        = front[i];
527

Sebastian Hack's avatar
Sebastian Hack committed
528
529
530
		cost += examine_subtree_coloring(chld, chld_col);
		cost += col != chld_col ? chld->mst_costs : 0;
	}
531

Sebastian Hack's avatar
Sebastian Hack committed
532
533
	return cost;
}
534

535
536
537
538
539
540
541
542
543
/**
 * 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
544
static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
545
{
546
547
	co2_t *const env    = ci->cloud->env;
	size_t const n_regs = env->n_regs;
548

549
	neighbours_iter_t it;
550

551
	{
552
		unsigned const *const bs = ci->inh.admissible;
553
		rbitset_foreach_clear(bs, n_regs, elm)
554
555
			badness[elm] = ci->costs;
	}
556
557

	/* Use constrained/fixed interfering neighbors to influence the color badness */
558
	be_ifg_foreach_neighbour(env->co->cenv->ifg, &it, ci->inh.irn, irn) {
559
560
		co2_irn_t *ni = get_co2_irn(env, irn);

561
		unsigned const *const bs = ni->admissible;
562
563
		if (rbitset_popcount(bs, n_regs) == 1) {
			size_t const c = rbitset_next_max(bs, 0, n_regs, true);
Sebastian Hack's avatar
Sebastian Hack committed
564
			badness[c] += ci->costs;
565
		} else if (ni->fixed) {
566
			col_t c = get_col(env, ni->irn);
Sebastian Hack's avatar
Sebastian Hack committed
567
			badness[c] += ci->costs;
568
569
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
570
571
}

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

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

591
		for (j = 0; j < env->n_regs; ++j)
592
593
594
			ci->color_badness[j] += child->color_badness[j];
	}

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

599
600
601
/**
 * Unfix all nodes in a MST subtree.
 */
Sebastian Hack's avatar
Sebastian Hack committed
602
603
604
static void unfix_subtree(co2_cloud_irn_t *ci)
{
	int i;
605

Sebastian Hack's avatar
Sebastian Hack committed
606
	ci->inh.fixed = 0;
607
	for (i = 0; i < ci->mst_n_childs; ++i)
Sebastian Hack's avatar
Sebastian Hack committed
608
609
		unfix_subtree(ci->mst_childs[i]);
}
610

Sebastian Hack's avatar
Sebastian Hack committed
611
static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
612
613
{
	co2_t *env           = ci->cloud->env;
614
	col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
615
	int is_root          = ci->mst_parent == ci;
Matthias Braun's avatar
Matthias Braun committed
616
	col_t parent_col     = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
617
618
619
	int min_badness      = INT_MAX;
	int best_col_costs   = INT_MAX;
	int best_col         = -1;
Sebastian Hack's avatar
Sebastian Hack committed
620
621
	int n_regs           = env->n_regs;
	int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
622
623
624
625

	struct list_head changed;
	int ok, i, j;

626
	for (i = 0; i < n_regs; ++i) {
627
628
629
		int badness = ci->color_badness[i];

		seq[i].col   = i;
630
		seq[i].costs = is_color_admissible(&ci->inh, i) ? badness : INT_MAX;
631
632
633
634
635

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

Sebastian Hack's avatar
Sebastian Hack committed
639
	/* Sort the colors. The will be processed in that ordering. */
640
	QSORT(seq, env->n_regs, col_cost_pair_lt);
641

Sebastian Hack's avatar
Sebastian Hack committed
642
	DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
643
	INIT_LIST_HEAD(&changed);
644
	for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
645
646
647
648
649
650
		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
651
652

		unfix_subtree(ci);
653
654
		INIT_LIST_HEAD(&changed);
		ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
655
		if (ok) {
Sebastian Hack's avatar
Sebastian Hack committed
656
657
658
659
660
661
			materialize_coloring(&changed);
			ci->inh.fixed = 1;
		}

		else
			continue;
662

663
		for (j = 0; j < ci->mst_n_childs; ++j) {
Sebastian Hack's avatar
Sebastian Hack committed
664
665
			co2_cloud_irn_t *child = ci->mst_childs[j];
			ok = coalesce_top_down(child, j, depth + 1) >= 0;
666
			if (ok)
Sebastian Hack's avatar
Sebastian Hack committed
667
668
669
				child->inh.fixed = 1;
			else
				break;
670
671
672
		}

		/* If the subtree could not be colored, we have to try another color. */
673
		if (!ok)
674
675
676
677
678
679
			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));

680
		if (sum_costs < best_col_costs) {
681
682
683
684
685
			best_col           = col;
			best_col_costs     = sum_costs;
			ci->col_costs[col] = subtree_costs;
		}

686
		if (sum_costs == 0)
687
688
689
			break;
	}

690
	if (!is_root) {
691
692
693
694
695
696
697
		int *front = FRONT_BASE(ci->mst_parent, parent_col);
		front[child_nr] = best_col;
	}

	return best_col;
}

698
699
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
700
701
	co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
	int costs           = 0;
702

703
	if (ci->cloud)
704
705
706
707
708
709
		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
710
	DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
711

712
713
714
	/* determine the nodes costs */
	co_gs_foreach_neighb(a, n) {
		costs += n->costs;
Sebastian Hack's avatar
Sebastian Hack committed
715
		DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
716
		if (be_values_interfere(a->irn, n->irn))
717
718
			cloud->inevit += n->costs;
	}
719

720
	/* add the node's cost to the total costs of the cloud. */
721
722
	ci->costs        = costs;
	cloud->costs    += costs;
723
	cloud->freedom  += rbitset_popcount(ci->inh.admissible, env->n_regs);
724
	cloud->n_memb   += 1;
725

726
	/* If this is the heaviest node in the cloud, set it as the cloud's master. */
727
	if (costs >= curr_costs) {
728
		curr_costs    = costs;
Sebastian Hack's avatar
Sebastian Hack committed
729
		cloud->master = ci;
730
	}
731

732
733
734
735
736
	/* 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);
737
738
739
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
740
static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
741
{
742
	co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
Sebastian Hack's avatar
Sebastian Hack committed
743
744
745
	int i;

	DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
Sebastian Hack's avatar
Sebastian Hack committed
746
747
748
749
750
751
	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;
752
753
	env->visited++;
	populate_cloud(env, cloud, a, 0);
Sebastian Hack's avatar
Sebastian Hack committed
754
	cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
755

Sebastian Hack's avatar
Sebastian Hack committed
756
	/* Also allocate space for the node sequence and compute that sequence. */
757
	cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
Sebastian Hack's avatar
Sebastian Hack committed
758

Sebastian Hack's avatar
Sebastian Hack committed
759
760
761
762
	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
763
	}
Sebastian Hack's avatar
Sebastian Hack committed
764
	DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
Sebastian Hack's avatar
Sebastian Hack committed
765

Sebastian Hack's avatar
Sebastian Hack committed
766
	return cloud;
767
}
768

Sebastian Hack's avatar
Sebastian Hack committed
769
static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
770
{
771
	const ir_node *irn = ci->inh.irn;
Sebastian Hack's avatar
Sebastian Hack committed
772
	int *front   = FRONT_BASE(ci, col);
773
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
774
775
776
	struct list_head changed;

	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
777
778

	DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
779
	change_color_single(ci->cloud->env, irn, col, &changed, depth);
Sebastian Hack's avatar
Sebastian Hack committed
780
	materialize_coloring(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
781

782
	for (i = 0; i < ci->mst_n_childs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
783
		apply_coloring(ci->mst_childs[i], front[i], depth + 1);
Sebastian Hack's avatar
Sebastian Hack committed
784
785
786
	}
}

787
788
static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
{
789
	while (ci != ci->mst_parent)
790
791
792
793
794
		ci = ci->mst_parent;
	return ci;
}


Sebastian Hack's avatar
Sebastian Hack committed
795
796
797
static void process_cloud(co2_cloud_t *cloud)
{
	co2_t *env  = cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
798
	int n_regs  = env->n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
799
	int n_edges = 0;
800
	int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
Sebastian Hack's avatar
Sebastian Hack committed
801
	pdeq *q;
Sebastian Hack's avatar
Sebastian Hack committed
802
803

	edge_t *edges;
804
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
805
	int best_col;
806

Sebastian Hack's avatar
Sebastian Hack committed
807
808
	/* Collect all edges in the cloud on an obstack and sort the increasingly */
	obstack_init(&cloud->obst);
809
	for (i = 0; i < cloud->n_memb; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
810
811
812
813
		co2_cloud_irn_t *ci = cloud->seq[i];

		co_gs_foreach_neighb(ci->inh.aff, n) {
			co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
814
			if (ci->index < ni->index) {
Sebastian Hack's avatar
Sebastian Hack committed
815
816
817
818
819
820
821
822
823
				edge_t e;
				e.src   = ci;
				e.tgt   = ni;
				e.costs = n->costs;
				obstack_grow(&cloud->obst, &e, sizeof(e));
				n_edges++;
			}
		}
	}
824
	edges = (edge_t*)obstack_finish(&cloud->obst);
825
	QSORT(edges, n_edges, cmp_edges);
Sebastian Hack's avatar
Sebastian Hack committed
826
827
828

	/* 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));
829
	for (i = 0; i < n_edges; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
830
		edge_t *e        = &edges[i];
Sebastian Hack's avatar
Sebastian Hack committed
831
832
		co2_cloud_irn_t *rs = find_mst_root(e->src);
		co2_cloud_irn_t *rt = find_mst_root(e->tgt);
833

Sebastian Hack's avatar
Sebastian Hack committed
834
		/* if the union/find roots are different */
835
		if (rs != rt) {
Sebastian Hack's avatar
Sebastian Hack committed
836
837
			int si = e->src->index;
			int ti = e->tgt->index;
Sebastian Hack's avatar
Sebastian Hack committed
838

Sebastian Hack's avatar
Sebastian Hack committed
839
840
841
842
843
844
845
			/* 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
846
		}
847
	}
Sebastian Hack's avatar
Sebastian Hack committed
848
	obstack_free(&cloud->obst, edges);
849

Sebastian Hack's avatar
Sebastian Hack committed
850
851
852
	cloud->master->mst_parent = cloud->master;
	cloud->mst_root = cloud->master;
	q = new_pdeq1(cloud->master);
853
	while (!pdeq_empty(q)) {
854
		co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
Sebastian Hack's avatar
Sebastian Hack committed
855
856
857
858
859
		int ofs    = ci->index * cloud->n_memb;
		int end    = ofs + cloud->n_memb;
		int i;

		ci->mst_n_childs = 0;
860
861
		for (i = ofs; i < end; ++i) {
			if (mst_edges[i] != 0) {
Sebastian Hack's avatar
Sebastian Hack committed
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
				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);
880
		ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
Sebastian Hack's avatar
Sebastian Hack committed
881
882
883
884
885
886
	}
	del_pdeq(q);
	free(mst_edges);


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

892
	for (i = 0; i < cloud->n_memb; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
893
		co2_cloud_irn_t *ci = cloud->seq[i];
Sebastian Hack's avatar
Sebastian Hack committed
894
		int n_childs = ci->mst_n_childs;
895
896
		int j;

897
898
899
900
		ci->col_costs       = OALLOCNZ(&cloud->obst, int,             n_regs);
		ci->tmp_coloring    = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
		ci->fronts          = OALLOCNZ(&cloud->obst, int,             n_regs * n_childs);
		ci->color_badness   = OALLOCNZ(&cloud->obst, int,             n_regs);
Sebastian Hack's avatar
Sebastian Hack committed
901

902
		for (j = 0; j < env->n_regs; j++)
903
			ci->col_costs[j] = INT_MAX;
Sebastian Hack's avatar
Sebastian Hack committed
904
	}
905

906
	determine_color_badness(cloud->mst_root, 0);
Sebastian Hack's avatar
Sebastian Hack committed
907
908
909
	best_col = coalesce_top_down(cloud->mst_root, -1, 0);
	unfix_subtree(cloud->mst_root);
	apply_coloring(cloud->mst_root, best_col, 0);
910
911

	/* The coloring should represent the one with the best costs. */
Sebastian Hack's avatar
Sebastian Hack committed
912
	//materialize_coloring(&changed);
913
914
915
916
	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. */
917
	for (i = 0; i < cloud->n_memb; ++i)
Sebastian Hack's avatar
Sebastian Hack committed
918
		cloud->seq[i]->inh.fixed = 1;
919

920
	/* Free all space used while optimizing this cloud. */
Sebastian Hack's avatar
Sebastian Hack committed
921
922
	obstack_free(&cloud->obst, NULL);
}
Sebastian Hack's avatar
Sebastian Hack committed
923

yb9976's avatar
yb9976 committed
924
#ifdef DEBUG_libfirm
Sebastian Hack's avatar
Sebastian Hack committed
925
926
927
static int cloud_costs(co2_cloud_t *cloud)
{
	int i, costs = 0;
Sebastian Hack's avatar
Sebastian Hack committed
928

929
	for (i = 0; i < cloud->n_memb; ++i) {