becopyheur2.c 33.5 KB
Newer Older
1
2
3
4
5
/**
 * More experiments on coalescing.
 * @author Sebastian Hack
 * @date   14.04.2006
 */
Sebastian Hack's avatar
Sebastian Hack committed
6
#ifdef HAVE_CONFIG_H
7
#include "config.h"
Sebastian Hack's avatar
Sebastian Hack committed
8
9
10
11
12
#endif

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

13
14
15
16
#include <stdlib.h>
#include <limits.h>

#include "list.h"
17
#include "pdeq.h"
18
#include "bitset.h"
Matthias Braun's avatar
Matthias Braun committed
19
#include "raw_bitset.h"
Sebastian Hack's avatar
Sebastian Hack committed
20

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

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

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

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

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

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

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

68
void be_init_copyheur2(void)
Sebastian Hack's avatar
Sebastian Hack committed
69
{
70
71
72
73
74
	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
75
76
	lc_opt_add_table(co2_grp, options);
}
77
78

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

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

*/

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

static be_ifg_dump_dot_cb_t ifg_dot_cb;
92

93
94
typedef unsigned col_t;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

243
static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
244
{
Matthias Braun's avatar
Matthias Braun committed
245
246
	if(ci->adm_cache == NULL) {
		const arch_register_req_t *req;
247
		ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
Matthias Braun's avatar
Matthias Braun committed
248
249
250
251
252
253
254
255
256
257
		req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));

		if(arch_register_req_is(req, limited)) {
			int i, n;

			n = env->n_regs;
			for(i = 0; i < n; ++i) {
				if(rbitset_is_set(req->limited, i))
					bitset_set(ci->adm_cache, i);
			}
Sebastian Hack's avatar
Sebastian Hack committed
258
			ci->is_constrained = 1;
Matthias Braun's avatar
Matthias Braun committed
259
		} else {
260
261
262
			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
static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
{
Matthias Braun's avatar
Matthias Braun committed
289
	const arch_register_req_t *req;
290

Matthias Braun's avatar
Matthias Braun committed
291
	req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0));
292

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

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

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

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

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

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

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

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

}

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

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

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

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

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

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

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

	int i;

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

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

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

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

		/*
		We managed to assign the target color to all neighbors, so from the perspective
		of the current node, every thing was ok and we can return safely.
		*/
		if(neigh_ok) {
Sebastian Hack's avatar
Sebastian Hack committed
476
			DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
			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
499
	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
500
501
502
503

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

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

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

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

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

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

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

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

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

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

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

	}

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

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

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

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

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

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

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

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

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

	node_color_badness(ci, ci->color_badness);
652
653
654
655
656
657

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

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

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

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

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

	struct list_head changed;
	int ok, i, j;

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
709
	DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
710
	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
711
	for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
712
713
714
715
716
717
		col_t col    = seq[i].col;
		int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;

		int subtree_costs, sum_costs;

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

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

		else
			continue;
729

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

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

765
766
static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
{
Sebastian Hack's avatar
Sebastian Hack committed
767
768
769
	be_ifg_t *ifg       = env->co->cenv->ifg;
	co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
	int costs           = 0;
770
771
	neighb_t *n;

Sebastian Hack's avatar
Sebastian Hack committed
772
	if(ci->cloud)
773
774
775
776
777
778
		return;

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

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

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

789
790
791
	/* add the node's cost to the total costs of the cloud. */
	ci->costs          = costs;
	cloud->costs      += costs;
Sebastian Hack's avatar
Sebastian Hack committed
792
793
	cloud->n_constr   += is_constrained(env, &ci->inh);
	cloud->freedom    += bitset_popcnt(get_adm(env, &ci->inh));
Sebastian Hack's avatar
Sebastian Hack committed
794
	cloud->max_degree  = MAX(cloud->max_degree, ci->inh.aff->degree);
795
	cloud->n_memb++;
796

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

803
804
805
806
807
	/* add all the neighbors of the node to the cloud. */
	co_gs_foreach_neighb(a, n) {
		affinity_node_t *an = get_affinity_info(env->co, n->irn);
		assert(an);
		populate_cloud(env, cloud, an, curr_costs);
808
809
810
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
811
static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
812
{
Sebastian Hack's avatar
Sebastian Hack committed
813
	co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
Sebastian Hack's avatar
Sebastian Hack committed
814
815
816
817
	co2_cloud_irn_t *ci;
	int i;

	DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
Sebastian Hack's avatar
Sebastian Hack committed
818
819
820
821
822
823
	memset(cloud, 0, sizeof(cloud[0]));
	INIT_LIST_HEAD(&cloud->members_head);
	INIT_LIST_HEAD(&cloud->list);
	list_add(&cloud->list, &env->cloud_head);
	cloud->best_costs = INT_MAX;
	cloud->env = env;
824
825
	env->visited++;
	populate_cloud(env, cloud, a, 0);
Sebastian Hack's avatar
Sebastian Hack committed
826
	cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
827

Sebastian Hack's avatar
Sebastian Hack committed
828
829
830
	/* 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
831
832
833
834
	i = 0;
	list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
		ci->index       = i;
		cloud->seq[i++] = ci;
Sebastian Hack's avatar
Sebastian Hack committed
835
	}
Sebastian Hack's avatar
Sebastian Hack committed
836
	DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
Sebastian Hack's avatar
Sebastian Hack committed
837

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
985
	}
986

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

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

For faster browsing, not all history is shown. View entire blame