becopyheur2.c 33.8 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
/**
Christian Würdig's avatar
Christian Würdig committed
21
22
23
24
25
 * @file
 * @brief       More experiments on coalescing.
 * @author      Sebastian Hack
 * @date        14.04.2006
 * @version     $Id$
26
 */
27
#include "config.h"
Sebastian Hack's avatar
Sebastian Hack committed
28

Matthias Braun's avatar
Matthias Braun committed
29
30
#include "lc_opts.h"
#include "lc_opts_enum.h"
31

32
33
34
35
#include <stdlib.h>
#include <limits.h>

#include "list.h"
36
#include "pdeq.h"
37
#include "bitset.h"
Matthias Braun's avatar
Matthias Braun committed
38
#include "raw_bitset.h"
Sebastian Hack's avatar
Sebastian Hack committed
39

40
#include "debug.h"
Sebastian Hack's avatar
Sebastian Hack committed
41
#include "bitfiddle.h"
42
43
44
45
46

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

49
#include "bemodule.h"
50
51
52
53
54
#include "beabi.h"
#include "benode_t.h"
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"
55
#include "beirg.h"
56

Sebastian Hack's avatar
Sebastian Hack committed
57
58
59
#define DUMP_BEFORE 1
#define DUMP_AFTER  2
#define DUMP_CLOUD  4
60
#define DUMP_ALL    2 * DUMP_CLOUD - 1
Sebastian Hack's avatar
Sebastian Hack committed
61

Matthias Braun's avatar
Matthias Braun committed
62
63
64
65
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
66
67
68

static const lc_opt_enum_mask_items_t dump_items[] = {
	{ "before",  DUMP_BEFORE },
Adam Szalkowski's avatar
Adam Szalkowski committed
69
70
	{ "after",   DUMP_AFTER  },
	{ "cloud",   DUMP_CLOUD  },
71
	{ "all",     DUMP_ALL    },
Sebastian Hack's avatar
Sebastian Hack committed
72
73
74
75
76
77
78
79
	{ NULL,      0 }
};

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

static const lc_opt_table_entry_t options[] = {
80
81
	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
82
	LC_OPT_ENT_DBL      ("cf",   "factor of constraint importance (between 0.0 and 1.0)",  &constr_factor),
83
	LC_OPT_ENT_INT      ("max",  "maximum recursion depth",                                &max_depth),
84
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
85
86
87
88
89
90
91
92
93
94
95
};

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

*/

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

static be_ifg_dump_dot_cb_t ifg_dot_cb;
99

100
101
typedef unsigned col_t;

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

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

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

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

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

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
190
	memset(ci, 0, size);
191
192
	INIT_LIST_HEAD(&ci->changed_list);
	ci->touched_next = env->touched;
193
	ci->orig_col     = get_irn_col(irn);
194
	env->touched     = ci;
Sebastian Hack's avatar
Sebastian Hack committed
195
196
	ci->irn          = irn;
	ci->aff          = a;
197

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

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

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

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

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

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

238
static col_t get_col(co2_t *env, const ir_node *irn)
239
240
241
242
243
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
}

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

250
static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
251
{
Matthias Braun's avatar
Matthias Braun committed
252
253
	if(ci->adm_cache == NULL) {
		const arch_register_req_t *req;
254
		ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
255
		req = arch_get_register_req_out(ci->irn);
Matthias Braun's avatar
Matthias Braun committed
256
257
258
259
260
261
262
263
264

		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
265
			ci->is_constrained = 1;
Matthias Braun's avatar
Matthias Braun committed
266
		} else {
267
268
269
			bitset_copy(ci->adm_cache, env->ignore_regs);
			bitset_flip_all(ci->adm_cache);
		}
270
271
	}

272
273
274
	return ci->adm_cache;
}

275
static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
276
277
{
	bitset_copy(bs, get_adm(env, ci));
278
279
280
	return bs;
}

281
static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
282
{
283
	bitset_t *bs = get_adm(env, ci);
284
285
286
	return bitset_is_set(bs, col);
}

287
static inline int is_constrained(co2_t *env, co2_irn_t *ci)
Sebastian Hack's avatar
Sebastian Hack committed
288
289
290
291
292
293
{
	if(!ci->adm_cache)
		get_adm(env, ci);
	return ci->is_constrained;
}

294
static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
295
{
296
	const arch_register_req_t *req = arch_get_register_req_out(irn);
297

298
299
	if (arch_register_req_is(req, limited)) {
		unsigned n_regs   = env->co->cls->n_regs;
Matthias Braun's avatar
Matthias Braun committed
300
		unsigned n_constr = 0;
301
		unsigned i;
302

Matthias Braun's avatar
Matthias Braun committed
303
		n_constr = rbitset_popcnt(req->limited, n_regs);
304
305
306
		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);
Matthias Braun's avatar
Matthias Braun committed
307
			}
308
		}
309
310
311
312
313
314
315
316
317
318
319
320
321
	}
}

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

	bitset_pos_t elm;
331
	const ir_node *pos;
332
333
334
	void *it;
	int i;

335
336
337
	/* Put all forbidden colors into the aux bitset. */
	admissible_colors(env, ci, forb);
	bitset_flip_all(forb);
338
339
340
341
342
343
344
345
346
347

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

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

	/* Set the costs to infinity for each color which is not allowed at this node. */
371
372
373
374
375
376
	bitset_foreach(forb, elm) {
		col_costs[elm].costs  = INT_MAX;
	}

}

377
static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
378
379
380
{
	int n_regs = env->co->cls->n_regs;
	int i;
381

382
383
384
385
386
	for(i = 0; i < n_regs; ++i) {
		seq[i].col   = i;
		seq[i].costs = INT_MAX;
	}

387
	(void) ci;
388
	assert(is_color_admissible(env, ci, col));
389
390
391
392
393
	seq[col].col = 0;
	seq[0].col   = col;
	seq[0].costs = 0;
}

394
395
396
397
398
399
400
401
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;
}

402
static void materialize_coloring(struct list_head *h)
403
404
405
406
{
	co2_irn_t *pos;

	list_for_each_entry(co2_irn_t, pos, h, changed_list) {
Sebastian Hack's avatar
Sebastian Hack committed
407
		pos->orig_col  = pos->tmp_col;
408
409
410
411
		pos->tmp_fixed = 0;
	}
}

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

414
static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
415
{
416
417
418
419
	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;
420
421
422

	int i;

Adam Szalkowski's avatar
Adam Szalkowski committed
423
424
425
	if(depth >= max_depth)
	  return 0;

426
427
428
429
430
431
	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;
432
		const ir_node *n;
433
434
		void *it;

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

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

		/*
		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
475
		be_ifg_neighbours_break(ifg, it);
476
477
478
479
480
481

		/*
		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
482
			DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
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;
}

499
static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
500
501
502
503
504
{
	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
505
	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
506
507
508
509

	/* 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
510
511
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
512
513
514
515
516
517
518
519
520
		}

		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;
521
		col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
522
523

		/* Get the costs for giving the node a specific color. */
524
		determine_color_costs(env, ci, csts);
525
526
527
528
529
530
531
532

		/* 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. */
533
		res = recolor(env, irn, csts, parent_changed, depth);
534
535
536
537
538
539
	}

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

540
static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
541
542
{
	co2_irn_t *ci = get_co2_irn(env, irn);
543
544
	col_t col     = get_col(env, irn);
	int res       = 0;
545

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

548
549
550
	/* 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
551
552
553
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
			list_add(&ci->changed_list, parent_changed);
554
		}
555

556
557
		res = 1;
		goto end;
558
559
	}

560
	if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
561
		int n_regs           = env->co->cls->n_regs;
562
		col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
563

564
		/* Get the costs for giving the node a specific color. */
565
		single_color_cost(env, ci, tgt_col, seq);
566
567
568
569
570
571

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

	}

572
573
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));
574
	return res;
575
576
}

577
578
579
580
581
582
/**
 * 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
583
584
585
586
587
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
588

Sebastian Hack's avatar
Sebastian Hack committed
589
590
591
	for(i = 0; i < ci->mst_n_childs; ++i) {
		co2_cloud_irn_t *chld = ci->mst_childs[i];
		col_t chld_col        = front[i];
592

Sebastian Hack's avatar
Sebastian Hack committed
593
594
595
		cost += examine_subtree_coloring(chld, chld_col);
		cost += col != chld_col ? chld->mst_costs : 0;
	}
596

Sebastian Hack's avatar
Sebastian Hack committed
597
598
	return cost;
}
599

600
601
602
603
604
605
606
607
608
/**
 * 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
609
static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
610
611
{
	co2_t *env     = ci->cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
612
	co2_irn_t *ir  = &ci->inh;
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;
618
	const ir_node *irn;
619
620
621
622
623
	void *it;

	admissible_colors(env, &ci->inh, bs);
	bitset_flip_all(bs);
	bitset_foreach(bs, elm)
Sebastian Hack's avatar
Sebastian Hack committed
624
		badness[elm] = ci->costs;
625
626
627
628
629
630
631

	/* 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
632
633
634
635
		if(bitset_popcnt(bs) == 1) {
			bitset_pos_t c = bitset_next_set(bs, 0);
			badness[c] += ci->costs;
		}
636

Sebastian Hack's avatar
Sebastian Hack committed
637
		else if(ni->fixed) {
638
			col_t c = get_col(env, ni->irn);
Sebastian Hack's avatar
Sebastian Hack committed
639
			badness[c] += ci->costs;
640
641
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
642
643
644
	be_ifg_neighbours_break(ifg, it);
}

645
646
647
648
649
650
651
/**
 * 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
652
653
654
655
656
657
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);
658
659
660
661
662
663

	/* 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
664
		for(j = 0; j < env->n_regs; ++j)
665
666
667
			ci->color_badness[j] += child->color_badness[j];
	}

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

672
673
674
/**
 * Unfix all nodes in a MST subtree.
 */
Sebastian Hack's avatar
Sebastian Hack committed
675
676
677
static void unfix_subtree(co2_cloud_irn_t *ci)
{
	int i;
678

Sebastian Hack's avatar
Sebastian Hack committed
679
680
681
682
	ci->inh.fixed = 0;
	for(i = 0; i < ci->mst_n_childs; ++i)
		unfix_subtree(ci->mst_childs[i]);
}
683

Sebastian Hack's avatar
Sebastian Hack committed
684
static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
685
686
{
	co2_t *env           = ci->cloud->env;
687
	col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
688
	int is_root          = ci->mst_parent == ci;
Matthias Braun's avatar
Matthias Braun committed
689
	col_t parent_col     = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
690
691
692
	int min_badness      = INT_MAX;
	int best_col_costs   = INT_MAX;
	int best_col         = -1;
Sebastian Hack's avatar
Sebastian Hack committed
693
694
	int n_regs           = env->n_regs;
	int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
695
696
697
698

	struct list_head changed;
	int ok, i, j;

Sebastian Hack's avatar
Sebastian Hack committed
699
	for(i = 0; i < n_regs; ++i) {
700
701
702
		int badness = ci->color_badness[i];

		seq[i].col   = i;
Sebastian Hack's avatar
Sebastian Hack committed
703
		seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
704
705
706
707
708
709
710
711

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

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

		unfix_subtree(ci);
726
727
		INIT_LIST_HEAD(&changed);
		ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
Sebastian Hack's avatar
Sebastian Hack committed
728
729
730
731
732
733
734
		if(ok) {
			materialize_coloring(&changed);
			ci->inh.fixed = 1;
		}

		else
			continue;
735

Sebastian Hack's avatar
Sebastian Hack committed
736
737
738
739
740
741
742
		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;
743
744
745
		}

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

771
772
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
773
774
775
	be_ifg_t *ifg       = env->co->cenv->ifg;
	co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
	int costs           = 0;
776
777
	neighb_t *n;

Sebastian Hack's avatar
Sebastian Hack committed
778
	if(ci->cloud)
779
780
781
782
783
784
		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
785
	DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
786

787
788
789
	/* determine the nodes costs */
	co_gs_foreach_neighb(a, n) {
		costs += n->costs;
Sebastian Hack's avatar
Sebastian Hack committed
790
		DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
791
792
793
		if(be_ifg_connected(ifg, a->irn, n->irn))
			cloud->inevit += n->costs;
	}
794

795
796
797
	/* 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
798
799
	cloud->n_constr   += is_constrained(env, &ci->inh);
	cloud->freedom    += bitset_popcnt(get_adm(env, &ci->inh));
Sebastian Hack's avatar
Sebastian Hack committed
800
	cloud->max_degree  = MAX(cloud->max_degree, ci->inh.aff->degree);
801
	cloud->n_memb++;
802

803
804
805
	/* 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
806
		cloud->master = ci;
807
	}
808

809
810
811
812
813
	/* 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);
814
815
816
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
817
static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
818
{
Sebastian Hack's avatar
Sebastian Hack committed
819
	co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
Sebastian Hack's avatar
Sebastian Hack committed
820
821
822
823
	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
824
825
826
827
828
829
	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;
830
831
	env->visited++;
	populate_cloud(env, cloud, a, 0);
Sebastian Hack's avatar
Sebastian Hack committed
832
	cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
833

Sebastian Hack's avatar
Sebastian Hack committed
834
835
836
	/* 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
837
838
839
840
	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
841
	}
Sebastian Hack's avatar
Sebastian Hack committed
842
	DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
Sebastian Hack's avatar
Sebastian Hack committed
843

Sebastian Hack's avatar
Sebastian Hack committed
844
	return cloud;
845
}
846

Sebastian Hack's avatar
Sebastian Hack committed
847
static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
848
{
849
	const ir_node *irn = ci->inh.irn;
Sebastian Hack's avatar
Sebastian Hack committed
850
851
	int *front   = FRONT_BASE(ci, col);
	int i, ok;
Sebastian Hack's avatar
Sebastian Hack committed
852
853
854
	struct list_head changed;

	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
855
856

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

861
 	for(i = 0; i < ci->mst_n_childs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
862
		apply_coloring(ci->mst_childs[i], front[i], depth + 1);
Sebastian Hack's avatar
Sebastian Hack committed
863
864
865
	}
}

866
867
868
869
870
871
872
873
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
874
875
876
static void process_cloud(co2_cloud_t *cloud)
{
	co2_t *env  = cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
877
	int n_regs  = env->n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
878
	int n_edges = 0;
879
	int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
Sebastian Hack's avatar
Sebastian Hack committed
880
	pdeq *q;
Sebastian Hack's avatar
Sebastian Hack committed
881
882

	edge_t *edges;
883
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
884
	int best_col;
885

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

Sebastian Hack's avatar
Sebastian Hack committed
914
915
916
917
		/* 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
918

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

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

Sebastian Hack's avatar
Sebastian Hack committed
972
973
	for(i = 0; i < cloud->n_memb; ++i) {
		co2_cloud_irn_t *ci = cloud->seq[i];
Sebastian Hack's avatar
Sebastian Hack committed
974
		int n_childs = ci->mst_n_childs;
975
976
		int j;

977
978
979
980
		ci->col_costs       = OALLOCNZ(&cloud->obst, int,             n_regs);
		ci->tmp_coloring    = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
		ci->fronts          = OALLOCNZ(&cloud->obst, int,             n_regs * n_childs);
		ci->color_badness   = OALLOCNZ(&cloud->obst, int,             n_regs);
Sebastian Hack's avatar
Sebastian Hack committed
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