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

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

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

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

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

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

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

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

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

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

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

/* Options using libcore */
#ifdef WITH_LIBCORE

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

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

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

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

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

*/

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

static be_ifg_dump_dot_cb_t ifg_dot_cb;
91

92
93
typedef unsigned col_t;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

258
259
260
	return ci->adm_cache;
}

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

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

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

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

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

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

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

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

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

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

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

	if(a) {
		neighb_t *n;

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

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

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

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

}

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

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

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

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

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

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

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

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

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

	int i;

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

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

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

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

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

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

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

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

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

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

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

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

	return res;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	}

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

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

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

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

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

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

	bitset_pos_t elm;
	ir_node *irn;
	void *it;

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

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

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

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

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

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

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

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

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

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

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

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

	struct list_head changed;
	int ok, i, j;

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

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

		min_badness = MIN(min_badness, badness);
	}

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

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

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

		int subtree_costs, sum_costs;

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

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

		else
			continue;
721

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

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

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

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

		if(sum_costs == 0)
			break;
	}

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

	return best_col;
}

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

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

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

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

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

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

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

795
796
797
798
799
	/* add all the neighbors of the node to the cloud. */
	co_gs_foreach_neighb(a, n) {
		affinity_node_t *an = get_affinity_info(env->co, n->irn);
		assert(an);
		populate_cloud(env, cloud, an, curr_costs);
800
801
802
	}
}

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

	DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
Sebastian Hack's avatar
Sebastian Hack committed
810
811
812
813
814
815
	memset(cloud, 0, sizeof(cloud[0]));
	INIT_LIST_HEAD(&cloud->members_head);
	INIT_LIST_HEAD(&cloud->list);
	list_add(&cloud->list, &env->cloud_head);
	cloud->best_costs = INT_MAX;
	cloud->env = env;
816
817
	env->visited++;
	populate_cloud(env, cloud, a, 0);
Sebastian Hack's avatar
Sebastian Hack committed
818
	cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
819

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

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

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

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

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

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

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

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


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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
874
875
	/* Collect all edges in the cloud on an obstack and sort the increasingly */
	obstack_init(&cloud->obst);
876
	for(i = 0; i < cloud->n_memb; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
		co2_cloud_irn_t *ci = cloud->seq[i];
		neighb_t *n;

		co_gs_foreach_neighb(ci->inh.aff, n) {
			co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
			if(ci->index < ni->index) {
				edge_t e;
				e.src   = ci;
				e.tgt   = ni;
				e.costs = n->costs;
				obstack_grow(&cloud->obst, &e, sizeof(e));
				n_edges++;
			}
		}
	}
	edges = obstack_finish(&cloud->obst);
	qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);

	/* Compute the maximum spanning tree using Kruskal/Union-Find */
	DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
	for(i = 0; i < n_edges; ++i) {
		edge_t *e        = &edges[i];
Sebastian Hack's avatar
Sebastian Hack committed
899
900
		co2_cloud_irn_t *rs = find_mst_root(e->src);
		co2_cloud_irn_t *rt = find_mst_root(e->tgt);
901

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

Sebastian Hack's avatar
Sebastian Hack committed
907
908
909
910
911
912
913
			/* unify the sets */
			rs->mst_parent = rt;
			DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));

			/* this edge is in the MST, so set it in the bitset. */
			mst_edges[si * cloud->n_memb + ti] = e->costs;
			mst_edges[ti * cloud->n_memb + si] = e->costs;
Sebastian Hack's avatar
Sebastian Hack committed
914
		}
915
	}
Sebastian Hack's avatar
Sebastian Hack committed
916
	obstack_free(&cloud->obst, edges);
917

Sebastian Hack's avatar
Sebastian Hack committed
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
	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) {
		co2_cloud_irn_t *ci = cloud->seq[i];
		DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
	}

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
977
	}
978

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
997
998
999
1000
static int cloud_costs(co2_cloud_t *cloud)
{
	int i, costs = 0;
	neighb_t *n;
For faster browsing, not all history is shown. View entire blame