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

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

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

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

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

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

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

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

33
#include "bemodule.h"
34
35
36
37
38
39
#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
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
52
53
54

/* Options using libcore */
#ifdef WITH_LIBCORE

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

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

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

73
void be_init_copyheur2(void)
Sebastian Hack's avatar
Sebastian Hack committed
74
{
75
76
77
78
79
	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
80
81
	lc_opt_add_table(co2_grp, options);
}
82
83

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
Sebastian Hack's avatar
Sebastian Hack committed
84
85
86
87
88
89
90
91
92
93
94
#endif

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

*/

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

static be_ifg_dump_dot_cb_t ifg_dot_cb;
98

99
100
typedef unsigned col_t;

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

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

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

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;
147
	int               *color_badness;
Sebastian Hack's avatar
Sebastian Hack committed
148
149
150
	col_cost_pair_t   *tmp_coloring;
	struct list_head   cloud_list;
	struct list_head   mst_list;
151
152
153
};

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
182
static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
183
{
Sebastian Hack's avatar
Sebastian Hack committed
184
185
186
187
	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);
188

Sebastian Hack's avatar
Sebastian Hack committed
189
	memset(ci, 0, size);
190
191
192
193
	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
194
195
	ci->irn          = irn;
	ci->aff          = a;
196

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

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

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

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

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

230
231
232
233
234
235
236
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);
}

237
238
239
240
241
242
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;
}

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

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

265
266
267
	return ci->adm_cache;
}

Sebastian Hack's avatar
Sebastian Hack committed
268
static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
269
270
{
	bitset_copy(bs, get_adm(env, ci));
271
272
273
	return bs;
}

Sebastian Hack's avatar
Sebastian Hack committed
274
static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
275
{
276
	bitset_t *bs = get_adm(env, ci);
277
278
279
	return bitset_is_set(bs, col);
}

Sebastian Hack's avatar
Sebastian Hack committed
280
281
282
283
284
285
286
static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
{
	if(!ci->adm_cache)
		get_adm(env, ci);
	return ci->is_constrained;
}

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

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

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

329
330
331
	/* Put all forbidden colors into the aux bitset. */
	admissible_colors(env, ci, forb);
	bitset_flip_all(forb);
332
333
334
335
336
337
338
339
340
341

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

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

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

}

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

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

381
	assert(is_color_admissible(env, ci, col));
382
383
384
385
386
	seq[col].col = 0;
	seq[0].col   = col;
	seq[0].costs = 0;
}

387
388
389
390
391
392
393
394
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;
}

395
static void materialize_coloring(struct list_head *h)
396
397
398
399
{
	co2_irn_t *pos;

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

405
406
407
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)
408
{
409
410
411
412
	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;
413
414
415

	int i;

Adam Szalkowski's avatar
Adam Szalkowski committed
416
417
418
	if(depth >= max_depth)
	  return 0;

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

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

		/*
		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
468
		be_ifg_neighbours_break(ifg, it);
469
470
471
472
473
474

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

	/* 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
503
504
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
505
506
507
508
509
510
511
512
513
514
515
516
		}

		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. */
517
		determine_color_costs(env, ci, csts);
518
519
520
521
522
523
524
525

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

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

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

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

541
542
543
	/* 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
544
545
546
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
			list_add(&ci->changed_list, parent_changed);
547
		}
548

549
550
		res = 1;
		goto end;
551
552
	}

553
	if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
554
555
		int n_regs           = env->co->cls->n_regs;
		col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
556

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

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

	}

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
590
591
	return cost;
}
592

593
594
595
596
597
598
599
600
601
/**
 * 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
602
static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
603
604
{
	co2_t *env     = ci->cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
605
	co2_irn_t *ir  = &ci->inh;
606
607
608
609
610
611
612
613
614
615
616
	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
617
		badness[elm] = ci->costs;
618
619
620
621
622
623
624

	/* 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
625
626
627
628
		if(bitset_popcnt(bs) == 1) {
			bitset_pos_t c = bitset_next_set(bs, 0);
			badness[c] += ci->costs;
		}
629

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

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

	/* 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
657
		for(j = 0; j < env->n_regs; ++j)
658
659
660
			ci->color_badness[j] += child->color_badness[j];
	}

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

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

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

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

	struct list_head changed;
	int ok, i, j;

Sebastian Hack's avatar
Sebastian Hack committed
692
	for(i = 0; i < n_regs; ++i) {
693
694
695
		int badness = ci->color_badness[i];

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

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

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

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

		else
			continue;
728

Sebastian Hack's avatar
Sebastian Hack committed
729
730
731
732
733
734
735
		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;
736
737
738
		}

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

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

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

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

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

796
797
798
	/* 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
799
		cloud->master = ci;
800
	}
801

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

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

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

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

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

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

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

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

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
909
910
911
912
		/* 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
913

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

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

Sebastian Hack's avatar
Sebastian Hack committed
967
968
	for(i = 0; i < cloud->n_memb; ++i) {
		co2_cloud_irn_t *ci = cloud->seq[i];
Sebastian Hack's avatar
Sebastian Hack committed
969
		int n_childs = ci->mst_n_childs;
970
971
		int j;

Sebastian Hack's avatar
Sebastian Hack committed
972
973
974
975
976
977
978
979
		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
980

981
982
983
		for(j = 0; j < env->n_regs; j++)
			ci->col_costs[j] = INT_MAX;

Sebastian Hack's avatar
Sebastian Hack committed
984
	}
985

986
	determine_color_badness(cloud->mst_root, 0);
Sebastian Hack's avatar
Sebastian Hack committed
987
988
989
	best_col = coalesce_top_down(cloud->mst_root, -1, 0);
	unfix_subtree(cloud->mst_root);
	apply_coloring(cloud->mst_root, best_col, 0);
990
991

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

1000
	/* Free all space used while optimizing this cloud. */
For faster browsing, not all history is shown. View entire blame