becopyheur2.c 33.3 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
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>

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

#include "list.h"
19
#include "pdeq.h"
20
#include "bitset.h"
Sebastian Hack's avatar
Sebastian Hack committed
21

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

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

31
#include "bemodule.h"
32
33
34
35
36
37
#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
38
39
40
#define DUMP_BEFORE 1
#define DUMP_AFTER  2
#define DUMP_CLOUD  4
41
#define DUMP_ALL    2 * DUMP_CLOUD - 1
Sebastian Hack's avatar
Sebastian Hack committed
42

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

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

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

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

69
void be_init_copyheur2(void)
Sebastian Hack's avatar
Sebastian Hack committed
70
{
71
72
73
74
75
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
	lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
	lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");

Sebastian Hack's avatar
Sebastian Hack committed
76
77
	lc_opt_add_table(co2_grp, options);
}
78
79

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
Sebastian Hack's avatar
Sebastian Hack committed
80
81
82
83
84
85
86
87
88
89

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

*/

Sebastian Hack's avatar
Sebastian Hack committed
90
91
92
#define INFEASIBLE(cost) ((cost) == INT_MAX)

static be_ifg_dump_dot_cb_t ifg_dot_cb;
93

94
95
typedef unsigned col_t;

Sebastian Hack's avatar
Sebastian Hack committed
96
97
98
99
100
101
102
103
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;
104
105

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

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

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;
142
	int               *color_badness;
Sebastian Hack's avatar
Sebastian Hack committed
143
144
145
	col_cost_pair_t   *tmp_coloring;
	struct list_head   cloud_list;
	struct list_head   mst_list;
146
147
148
};

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
174
175
#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))
176

Sebastian Hack's avatar
Sebastian Hack committed
177
static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
178
{
Sebastian Hack's avatar
Sebastian Hack committed
179
180
181
182
	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);
183

Sebastian Hack's avatar
Sebastian Hack committed
184
	memset(ci, 0, size);
185
186
187
188
	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
189
190
	ci->irn          = irn;
	ci->aff          = a;
191

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

Sebastian Hack's avatar
Sebastian Hack committed
198
	return ci;
199
200
}

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

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

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

225
226
227
228
229
230
231
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);
}

232
233
234
235
236
237
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;
}

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

244
static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
245
{
246
247
248
249
	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
250
		if(arch_register_req_is(&req, limited)) {
251
			req.limited(req.limited_env, ci->adm_cache);
Sebastian Hack's avatar
Sebastian Hack committed
252
253
			ci->is_constrained = 1;
		}
254
255
256
257
		else {
			bitset_copy(ci->adm_cache, env->ignore_regs);
			bitset_flip_all(ci->adm_cache);
		}
258
259
	}

260
261
262
	return ci->adm_cache;
}

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

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

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

282
283
284
285
286
287
288
289
290
291
292
293
294
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);
295
		bitset_foreach(aux, elm) {
Sebastian Hack's avatar
Sebastian Hack committed
296
			col_costs[elm].costs  = add_saturated(col_costs[elm].costs, costs / n_constr);
297
		}
298
299
300
301
302
303
304
305
306
307
308
309
310
	}
}

/**
 * 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.
 */
311
static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
312
{
313
	ir_node *irn       = ci->irn;
314
315
316
	be_ifg_t *ifg      = env->co->cenv->ifg;
	int n_regs         = env->co->cls->n_regs;
	bitset_t *forb     = bitset_alloca(n_regs);
317
	affinity_node_t *a = ci->aff;
318
319
320
321
322
323

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

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

	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) {
337
			if(color_is_fix(env, n->irn)) {
338
				col_t col = get_col(env, n->irn);
Sebastian Hack's avatar
Sebastian Hack committed
339
				col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
340
341
342
343
344
345
346
347
348
			}

			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);
349
350
351
		if(color_is_fix(env, pos)) {
			col_costs[col].costs  = INT_MAX;
		}
352
353
		else {
			incur_constraint_costs(env, pos, col_costs, INT_MAX);
Sebastian Hack's avatar
Sebastian Hack committed
354
			col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
355
356
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
357
	be_ifg_neighbours_break(ifg, it);
358
359

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

}

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

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

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

382
383
384
385
386
387
388
389
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;
}

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

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

400
401
402
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)
403
{
404
405
406
407
	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;
408
409
410

	int i;

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

414
415
416
417
418
419
420
421
422
	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
423
		DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
424
425

		/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
426
		if(INFEASIBLE(costs)) {
Sebastian Hack's avatar
Sebastian Hack committed
427
			DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
428
429
430
431
432
			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
433
434
		ci->tmp_col     = tgt_col;
		ci->tmp_fixed   = 1;
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
461
462

		/*
		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
463
		be_ifg_neighbours_break(ifg, it);
464
465
466
467
468
469

		/*
		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
470
			DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
			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
493
	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
494
495
496
497

	/* 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
498
499
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
500
501
502
503
504
505
506
507
508
509
510
511
		}

		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. */
512
		determine_color_costs(env, ci, csts);
513
514
515
516
517
518
519
520

		/* 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. */
521
		res = recolor(env, irn, csts, parent_changed, depth);
522
523
524
525
526
527
	}

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

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

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

536
537
538
	/* 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
539
540
541
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
			list_add(&ci->changed_list, parent_changed);
542
		}
543

544
545
		res = 1;
		goto end;
546
547
	}

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

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

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

	}

560
561
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));
562
	return res;
563
564
}

565
566
567
568
569
570
/**
 * 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
571
572
573
574
575
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
576

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

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

Sebastian Hack's avatar
Sebastian Hack committed
585
586
	return cost;
}
587

588
589
590
591
592
593
594
595
596
/**
 * 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
597
static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
598
599
{
	co2_t *env     = ci->cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
600
	co2_irn_t *ir  = &ci->inh;
601
602
603
604
605
606
607
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);

	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
612
		badness[elm] = ci->costs;
613
614
615
616
617
618
619

	/* 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
620
621
622
623
		if(bitset_popcnt(bs) == 1) {
			bitset_pos_t c = bitset_next_set(bs, 0);
			badness[c] += ci->costs;
		}
624

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

633
634
635
636
637
638
639
/**
 * 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
640
641
642
643
644
645
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);
646
647
648
649
650
651

	/* 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
652
		for(j = 0; j < env->n_regs; ++j)
653
654
655
			ci->color_badness[j] += child->color_badness[j];
	}

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
672
static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
673
674
675
676
677
678
679
680
{
	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
681
682
	int n_regs           = env->n_regs;
	int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
683
684
685
686

	struct list_head changed;
	int ok, i, j;

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

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

		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
700
	/* Sort the colors. The will be processed in that ordering. */
701
702
	qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);

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

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

		else
			continue;
723

Sebastian Hack's avatar
Sebastian Hack committed
724
725
726
727
728
729
730
		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;
731
732
733
		}

		/* If the subtree could not be colored, we have to try another color. */
Sebastian Hack's avatar
Sebastian Hack committed
734
		if(!ok)
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
			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;
}

759
760
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
761
762
763
	be_ifg_t *ifg       = env->co->cenv->ifg;
	co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
	int costs           = 0;
764
765
	neighb_t *n;

Sebastian Hack's avatar
Sebastian Hack committed
766
	if(ci->cloud)
767
768
769
770
771
772
		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
773
	DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
774

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

783
784
785
	/* 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
786
787
	cloud->n_constr   += is_constrained(env, &ci->inh);
	cloud->freedom    += bitset_popcnt(get_adm(env, &ci->inh));
Sebastian Hack's avatar
Sebastian Hack committed
788
	cloud->max_degree  = MAX(cloud->max_degree, ci->inh.aff->degree);
789
	cloud->n_memb++;
790

791
792
793
	/* 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
794
		cloud->master = ci;
795
	}
796

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

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

Sebastian Hack's avatar
Sebastian Hack committed
822
823
824
	/* 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
825
826
827
828
	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
829
	}
Sebastian Hack's avatar
Sebastian Hack committed
830
	DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
Sebastian Hack's avatar
Sebastian Hack committed
831

Sebastian Hack's avatar
Sebastian Hack committed
832
	return cloud;
833
}
834

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

	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
843
844

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

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

854
855
856
857
858
859
860
861
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
862
863
864
static void process_cloud(co2_cloud_t *cloud)
{
	co2_t *env  = cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
865
	int n_regs  = env->n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
866
	int n_edges = 0;
Michael Beck's avatar
Michael Beck committed
867
	int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
Sebastian Hack's avatar
Sebastian Hack committed
868
	pdeq *q;
Sebastian Hack's avatar
Sebastian Hack committed
869
870

	edge_t *edges;
871
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
872
	int best_col;
873

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

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

Sebastian Hack's avatar
Sebastian Hack committed
904
905
906
907
		/* 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
908

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

Sebastian Hack's avatar
Sebastian Hack committed
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
956
957
	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
958
		DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
Sebastian Hack's avatar
Sebastian Hack committed
959
960
961
		DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
	}

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

Sebastian Hack's avatar
Sebastian Hack committed
967
968
969
970
971
972
973
974
		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
975

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

Sebastian Hack's avatar
Sebastian Hack committed
979
	}
980

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

	/* The coloring should represent the one with the best costs. */
Sebastian Hack's avatar
Sebastian Hack committed
987
	//materialize_coloring(&changed);
988
989
990
991
	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
992
993
	for(i = 0; i < cloud->n_memb; ++i)
		cloud->seq[i]->inh.fixed = 1;
994

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

Sebastian Hack's avatar
Sebastian Hack committed
999
1000
static int cloud_costs(co2_cloud_t *cloud)
{
For faster browsing, not all history is shown. View entire blame