becopyheur2.c 34 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
void be_init_copyheur2(void)
Sebastian Hack's avatar
Sebastian Hack committed
88
{
89
90
91
92
93
	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
94
95
	lc_opt_add_table(co2_grp, options);
}
96
97

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
Sebastian Hack's avatar
Sebastian Hack committed
98
99
100
101
102
103
104
105
106
107

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

*/

Sebastian Hack's avatar
Sebastian Hack committed
108
109
110
#define INFEASIBLE(cost) ((cost) == INT_MAX)

static be_ifg_dump_dot_cb_t ifg_dot_cb;
111

112
113
typedef unsigned col_t;

Sebastian Hack's avatar
Sebastian Hack committed
114
115
116
117
118
119
120
121
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;
122
123

typedef struct {
Michael Beck's avatar
Michael Beck committed
124
	ir_phase     ph;
125
	copy_opt_t *co;
Sebastian Hack's avatar
Sebastian Hack committed
126
127
128
129
	bitset_t   *ignore_regs;
	co2_irn_t  *touched;
	int         visited;
	int         n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
130
	struct list_head cloud_head;
131
132
133
134
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
} co2_t;

struct _co2_irn_t {
135
	const ir_node   *irn;
136
	affinity_node_t *aff;
Sebastian Hack's avatar
Sebastian Hack committed
137
	co2_irn_t       *touched_next;
138
139
	col_t            tmp_col;
	col_t            orig_col;
Sebastian Hack's avatar
Sebastian Hack committed
140
	int				 last_color_change;
141
	bitset_t        *adm_cache;
Sebastian Hack's avatar
Sebastian Hack committed
142
143
144
	unsigned         fixed          : 1;
	unsigned         tmp_fixed      : 1;
	unsigned         is_constrained : 1;
145
	struct list_head changed_list;
Sebastian Hack's avatar
Sebastian Hack committed
146
147
148
149
150
151
152
153
154
155
156
157
158
159
};

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;
160
	int               *color_badness;
Sebastian Hack's avatar
Sebastian Hack committed
161
162
163
	col_cost_pair_t   *tmp_coloring;
	struct list_head   cloud_list;
	struct list_head   mst_list;
164
165
166
};

struct _co2_cloud_t {
Sebastian Hack's avatar
Sebastian Hack committed
167
168
169
170
171
172
173
	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
174
	int               n_constr;
Sebastian Hack's avatar
Sebastian Hack committed
175
176
	int               max_degree;
	int			      ticks;
Sebastian Hack's avatar
Sebastian Hack committed
177
	double            freedom;
Sebastian Hack's avatar
Sebastian Hack committed
178
179
180
181
182
	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;
183
184
};

185
186
187
188
189
typedef struct {
	co2_cloud_irn_t *src, *tgt;
	int costs;
} edge_t;

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

Sebastian Hack's avatar
Sebastian Hack committed
192
193
#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))
194

195
static void *co2_irn_init(ir_phase *ph, const ir_node *irn, void *data)
196
{
Sebastian Hack's avatar
Sebastian Hack committed
197
198
199
200
	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);
201

Sebastian Hack's avatar
Sebastian Hack committed
202
	memset(ci, 0, size);
203
204
	INIT_LIST_HEAD(&ci->changed_list);
	ci->touched_next = env->touched;
205
	ci->orig_col     = get_irn_col(irn);
206
	env->touched     = ci;
Sebastian Hack's avatar
Sebastian Hack committed
207
208
	ci->irn          = irn;
	ci->aff          = a;
209

Sebastian Hack's avatar
Sebastian Hack committed
210
211
212
213
214
	if(a) {
		co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
		INIT_LIST_HEAD(&cci->cloud_list);
		cci->mst_parent   = cci;
	}
215

Sebastian Hack's avatar
Sebastian Hack committed
216
	return ci;
217
218
}

Sebastian Hack's avatar
Sebastian Hack committed
219
#define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
Sebastian Hack's avatar
Sebastian Hack committed
220
221

static int cmp_clouds_gt(const void *a, const void *b)
222
{
Christoph Mallon's avatar
Christoph Mallon committed
223
224
	const co2_cloud_t * const *p = a;
	const co2_cloud_t * const *q = b;
Sebastian Hack's avatar
Sebastian Hack committed
225
226
	double c = CLOUD_WEIGHT(*p);
	double d = CLOUD_WEIGHT(*q);
227
	return QSORT_CMP(d, c);
228
229
}

230
231
232
233
234
235
236
237
/**
 * 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;
238
239
	int c = p->costs;
	int d = q->costs;
240
	return QSORT_CMP(c, d);
241
242
}

243
244
245
246
247
248
249
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);
}

250
static col_t get_col(co2_t *env, const ir_node *irn)
251
252
253
254
255
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
}

256
static inline int color_is_fix(co2_t *env, const ir_node *irn)
257
258
259
260
261
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	return ci->fixed || ci->tmp_fixed;
}

262
static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
263
{
Matthias Braun's avatar
Matthias Braun committed
264
265
	if(ci->adm_cache == NULL) {
		const arch_register_req_t *req;
266
		ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
267
		req = arch_get_register_req_out(ci->irn);
Matthias Braun's avatar
Matthias Braun committed
268
269
270
271
272
273
274
275
276

		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
277
			ci->is_constrained = 1;
Matthias Braun's avatar
Matthias Braun committed
278
		} else {
279
280
281
			bitset_copy(ci->adm_cache, env->ignore_regs);
			bitset_flip_all(ci->adm_cache);
		}
282
283
	}

284
285
286
	return ci->adm_cache;
}

287
static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
288
289
{
	bitset_copy(bs, get_adm(env, ci));
290
291
292
	return bs;
}

293
static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
294
{
295
	bitset_t *bs = get_adm(env, ci);
296
297
298
	return bitset_is_set(bs, col);
}

299
static inline int is_constrained(co2_t *env, co2_irn_t *ci)
Sebastian Hack's avatar
Sebastian Hack committed
300
301
302
303
304
305
{
	if(!ci->adm_cache)
		get_adm(env, ci);
	return ci->is_constrained;
}

306
static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
307
{
308
	const arch_register_req_t *req = arch_get_register_req_out(irn);
309

310
311
	if (arch_register_req_is(req, limited)) {
		unsigned n_regs   = env->co->cls->n_regs;
Matthias Braun's avatar
Matthias Braun committed
312
		unsigned n_constr = 0;
313
		unsigned i;
314

Matthias Braun's avatar
Matthias Braun committed
315
		n_constr = rbitset_popcnt(req->limited, n_regs);
316
317
318
		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
319
			}
320
		}
321
322
323
324
325
326
327
328
329
330
331
332
333
	}
}

/**
 * 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.
 */
334
static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
335
{
336
	const ir_node *irn = ci->irn;
337
338
339
	be_ifg_t *ifg      = env->co->cenv->ifg;
	int n_regs         = env->co->cls->n_regs;
	bitset_t *forb     = bitset_alloca(n_regs);
340
	affinity_node_t *a = ci->aff;
341
342

	bitset_pos_t elm;
343
	const ir_node *pos;
344
345
346
	void *it;
	int i;

347
348
349
	/* Put all forbidden colors into the aux bitset. */
	admissible_colors(env, ci, forb);
	bitset_flip_all(forb);
350
351
352
353
354
355
356
357
358
359

	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) {
360
			if(color_is_fix(env, n->irn)) {
361
				col_t col = get_col(env, n->irn);
Sebastian Hack's avatar
Sebastian Hack committed
362
				col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
363
364
365
366
367
368
369
370
371
			}

			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);
372
373
374
		if(color_is_fix(env, pos)) {
			col_costs[col].costs  = INT_MAX;
		}
375
376
		else {
			incur_constraint_costs(env, pos, col_costs, INT_MAX);
Sebastian Hack's avatar
Sebastian Hack committed
377
			col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
378
379
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
380
	be_ifg_neighbours_break(ifg, it);
381
382

	/* Set the costs to infinity for each color which is not allowed at this node. */
383
384
385
386
387
388
	bitset_foreach(forb, elm) {
		col_costs[elm].costs  = INT_MAX;
	}

}

389
static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
390
391
392
{
	int n_regs = env->co->cls->n_regs;
	int i;
393

394
395
396
397
398
	for(i = 0; i < n_regs; ++i) {
		seq[i].col   = i;
		seq[i].costs = INT_MAX;
	}

399
	(void) ci;
400
	assert(is_color_admissible(env, ci, col));
401
402
403
404
405
	seq[col].col = 0;
	seq[0].col   = col;
	seq[0].costs = 0;
}

406
407
408
409
410
411
412
413
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;
}

414
static void materialize_coloring(struct list_head *h)
415
416
417
418
{
	co2_irn_t *pos;

	list_for_each_entry(co2_irn_t, pos, h, changed_list) {
Sebastian Hack's avatar
Sebastian Hack committed
419
		pos->orig_col  = pos->tmp_col;
420
421
422
423
		pos->tmp_fixed = 0;
	}
}

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

426
static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
427
{
428
429
430
431
	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;
432
433
434

	int i;

Adam Szalkowski's avatar
Adam Szalkowski committed
435
436
437
	if(depth >= max_depth)
	  return 0;

438
439
440
441
442
443
	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;
444
		const ir_node *n;
445
446
		void *it;

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

		/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
450
		if(INFEASIBLE(costs)) {
Sebastian Hack's avatar
Sebastian Hack committed
451
			DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
452
453
454
455
456
			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
457
458
		ci->tmp_col     = tgt_col;
		ci->tmp_fixed   = 1;
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486

		/*
		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
487
		be_ifg_neighbours_break(ifg, it);
488
489
490
491
492
493

		/*
		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
494
			DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
			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;
}

511
static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
512
513
514
515
516
{
	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
517
	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
518
519
520
521

	/* 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
522
523
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
524
525
526
527
528
529
530
531
532
		}

		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;
533
		col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
534
535

		/* Get the costs for giving the node a specific color. */
536
		determine_color_costs(env, ci, csts);
537
538
539
540
541
542
543
544

		/* 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. */
545
		res = recolor(env, irn, csts, parent_changed, depth);
546
547
548
549
550
551
	}

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

552
static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
553
554
{
	co2_irn_t *ci = get_co2_irn(env, irn);
555
556
	col_t col     = get_col(env, irn);
	int res       = 0;
557

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

560
561
562
	/* 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
563
564
565
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
			list_add(&ci->changed_list, parent_changed);
566
		}
567

568
569
		res = 1;
		goto end;
570
571
	}

572
	if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
573
		int n_regs           = env->co->cls->n_regs;
574
		col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
575

576
		/* Get the costs for giving the node a specific color. */
577
		single_color_cost(env, ci, tgt_col, seq);
578
579
580
581
582
583

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

	}

584
585
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));
586
	return res;
587
588
}

589
590
591
592
593
594
/**
 * 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
595
596
597
598
599
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
600

Sebastian Hack's avatar
Sebastian Hack committed
601
602
603
	for(i = 0; i < ci->mst_n_childs; ++i) {
		co2_cloud_irn_t *chld = ci->mst_childs[i];
		col_t chld_col        = front[i];
604

Sebastian Hack's avatar
Sebastian Hack committed
605
606
607
		cost += examine_subtree_coloring(chld, chld_col);
		cost += col != chld_col ? chld->mst_costs : 0;
	}
608

Sebastian Hack's avatar
Sebastian Hack committed
609
610
	return cost;
}
611

612
613
614
615
616
617
618
619
620
/**
 * 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
621
static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
622
623
{
	co2_t *env     = ci->cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
624
	co2_irn_t *ir  = &ci->inh;
625
626
627
628
629
	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;
630
	const ir_node *irn;
631
632
633
634
635
	void *it;

	admissible_colors(env, &ci->inh, bs);
	bitset_flip_all(bs);
	bitset_foreach(bs, elm)
Sebastian Hack's avatar
Sebastian Hack committed
636
		badness[elm] = ci->costs;
637
638
639
640
641
642
643

	/* 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
644
645
646
647
		if(bitset_popcnt(bs) == 1) {
			bitset_pos_t c = bitset_next_set(bs, 0);
			badness[c] += ci->costs;
		}
648

Sebastian Hack's avatar
Sebastian Hack committed
649
		else if(ni->fixed) {
650
			col_t c = get_col(env, ni->irn);
Sebastian Hack's avatar
Sebastian Hack committed
651
			badness[c] += ci->costs;
652
653
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
654
655
656
	be_ifg_neighbours_break(ifg, it);
}

657
658
659
660
661
662
663
/**
 * 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
664
665
666
667
668
669
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);
670
671
672
673
674
675

	/* 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
676
		for(j = 0; j < env->n_regs; ++j)
677
678
679
			ci->color_badness[j] += child->color_badness[j];
	}

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

684
685
686
/**
 * Unfix all nodes in a MST subtree.
 */
Sebastian Hack's avatar
Sebastian Hack committed
687
688
689
static void unfix_subtree(co2_cloud_irn_t *ci)
{
	int i;
690

Sebastian Hack's avatar
Sebastian Hack committed
691
692
693
694
	ci->inh.fixed = 0;
	for(i = 0; i < ci->mst_n_childs; ++i)
		unfix_subtree(ci->mst_childs[i]);
}
695

Sebastian Hack's avatar
Sebastian Hack committed
696
static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
697
698
{
	co2_t *env           = ci->cloud->env;
699
	col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
700
	int is_root          = ci->mst_parent == ci;
Matthias Braun's avatar
Matthias Braun committed
701
	col_t parent_col     = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
702
703
704
	int min_badness      = INT_MAX;
	int best_col_costs   = INT_MAX;
	int best_col         = -1;
Sebastian Hack's avatar
Sebastian Hack committed
705
706
	int n_regs           = env->n_regs;
	int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
707
708
709
710

	struct list_head changed;
	int ok, i, j;

Sebastian Hack's avatar
Sebastian Hack committed
711
	for(i = 0; i < n_regs; ++i) {
712
713
714
		int badness = ci->color_badness[i];

		seq[i].col   = i;
Sebastian Hack's avatar
Sebastian Hack committed
715
		seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
716
717
718
719
720
721
722
723

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

Sebastian Hack's avatar
Sebastian Hack committed
727
	DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
728
	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
729
	for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
730
731
732
733
734
735
		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
736
737

		unfix_subtree(ci);
738
739
		INIT_LIST_HEAD(&changed);
		ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
Sebastian Hack's avatar
Sebastian Hack committed
740
741
742
743
744
745
746
		if(ok) {
			materialize_coloring(&changed);
			ci->inh.fixed = 1;
		}

		else
			continue;
747

Sebastian Hack's avatar
Sebastian Hack committed
748
749
750
751
752
753
754
		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;
755
756
757
		}

		/* If the subtree could not be colored, we have to try another color. */
Sebastian Hack's avatar
Sebastian Hack committed
758
		if(!ok)
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
			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;
}

783
784
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
785
786
787
	be_ifg_t *ifg       = env->co->cenv->ifg;
	co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
	int costs           = 0;
788
789
	neighb_t *n;

Sebastian Hack's avatar
Sebastian Hack committed
790
	if(ci->cloud)
791
792
793
794
795
796
		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
797
	DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
798

799
800
801
	/* determine the nodes costs */
	co_gs_foreach_neighb(a, n) {
		costs += n->costs;
Sebastian Hack's avatar
Sebastian Hack committed
802
		DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
803
804
805
		if(be_ifg_connected(ifg, a->irn, n->irn))
			cloud->inevit += n->costs;
	}
806

807
808
809
	/* 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
810
811
	cloud->n_constr   += is_constrained(env, &ci->inh);
	cloud->freedom    += bitset_popcnt(get_adm(env, &ci->inh));
Sebastian Hack's avatar
Sebastian Hack committed
812
	cloud->max_degree  = MAX(cloud->max_degree, ci->inh.aff->degree);
813
	cloud->n_memb++;
814

815
816
817
	/* 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
818
		cloud->master = ci;
819
	}
820

821
822
823
824
825
	/* 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);
826
827
828
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
829
static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
830
{
Sebastian Hack's avatar
Sebastian Hack committed
831
	co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
Sebastian Hack's avatar
Sebastian Hack committed
832
833
834
835
	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
836
837
838
839
840
841
	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;
842
843
	env->visited++;
	populate_cloud(env, cloud, a, 0);
Sebastian Hack's avatar
Sebastian Hack committed
844
	cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
845

Sebastian Hack's avatar
Sebastian Hack committed
846
847
848
	/* 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
849
850
851
852
	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
853
	}
Sebastian Hack's avatar
Sebastian Hack committed
854
	DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
Sebastian Hack's avatar
Sebastian Hack committed
855

Sebastian Hack's avatar
Sebastian Hack committed
856
	return cloud;
857
}
858

Sebastian Hack's avatar
Sebastian Hack committed
859
static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
860
{
861
	const ir_node *irn = ci->inh.irn;
Sebastian Hack's avatar
Sebastian Hack committed
862
863
	int *front   = FRONT_BASE(ci, col);
	int i, ok;
Sebastian Hack's avatar
Sebastian Hack committed
864
865
866
	struct list_head changed;

	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
867
868

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

873
 	for(i = 0; i < ci->mst_n_childs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
874
		apply_coloring(ci->mst_childs[i], front[i], depth + 1);
Sebastian Hack's avatar
Sebastian Hack committed
875
876
877
	}
}

878
879
880
881
882
883
884
885
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
886
887
888
static void process_cloud(co2_cloud_t *cloud)
{
	co2_t *env  = cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
889
	int n_regs  = env->n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
890
	int n_edges = 0;
891
	int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
Sebastian Hack's avatar
Sebastian Hack committed
892
	pdeq *q;
Sebastian Hack's avatar
Sebastian Hack committed
893
894

	edge_t *edges;
895
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
896
	int best_col;
897

Sebastian Hack's avatar
Sebastian Hack committed
898
899
	/* Collect all edges in the cloud on an obstack and sort the increasingly */
	obstack_init(&cloud->obst);
900
	for(i = 0; i < cloud->n_memb; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
		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
923
924
		co2_cloud_irn_t *rs = find_mst_root(e->src);
		co2_cloud_irn_t *rt = find_mst_root(e->tgt);
925

Sebastian Hack's avatar
Sebastian Hack committed
926
927
928
929
		/* 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
930

Sebastian Hack's avatar
Sebastian Hack committed
931
932
933
934
935
936
937
			/* 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
938
		}
939
	}
Sebastian Hack's avatar
Sebastian Hack committed
940
	obstack_free(&cloud->obst, edges);
941

Sebastian Hack's avatar
Sebastian Hack committed
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
968
969
970
971
972
973
974
975
976
977
978
979
	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
980
		DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
Sebastian Hack's avatar
Sebastian Hack committed
981
982
983
		DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
	}

Sebastian Hack's avatar
Sebastian Hack committed
984
985
	for(i = 0; i < cloud->n_memb; ++i) {
		co2_cloud_irn_t *ci = cloud->seq[i];
Sebastian Hack's avatar
Sebastian Hack committed
986
		int n_childs = ci->mst_n_childs;
987
988
		int j;

Sebastian Hack's avatar
Sebastian Hack committed
989
990
991
992
993
994
995
996
		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
997

998
999
1000
		for(j = 0; j < env->n_regs; j++)
			ci->col_costs[j] = INT_MAX;

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