becopyheur2.c 34.3 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
 */
Sebastian Hack's avatar
Sebastian Hack committed
27
#ifdef HAVE_CONFIG_H
28
#include "config.h"
Sebastian Hack's avatar
Sebastian Hack committed
29
30
#endif

31
32
33
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>

34
35
36
37
#include <stdlib.h>
#include <limits.h>

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

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

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

51
#include "bemodule.h"
52
53
54
55
56
#include "beabi.h"
#include "benode_t.h"
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"
Christian Würdig's avatar
Christian Würdig committed
57
#include "beirg_t.h"
58

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

Matthias Braun's avatar
Matthias Braun committed
64
65
66
67
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
68
69
70
71

/* Options using libcore */
static const lc_opt_enum_mask_items_t dump_items[] = {
	{ "before",  DUMP_BEFORE },
Adam Szalkowski's avatar
Adam Szalkowski committed
72
73
	{ "after",   DUMP_AFTER  },
	{ "cloud",   DUMP_CLOUD  },
74
	{ "all",     DUMP_ALL    },
Sebastian Hack's avatar
Sebastian Hack committed
75
76
77
78
79
80
81
82
	{ NULL,      0 }
};

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

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

90
void be_init_copyheur2(void)
Sebastian Hack's avatar
Sebastian Hack committed
91
{
92
93
94
95
96
	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
97
98
	lc_opt_add_table(co2_grp, options);
}
99
100

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
Sebastian Hack's avatar
Sebastian Hack committed
101
102
103
104
105
106
107
108
109
110

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

*/

Sebastian Hack's avatar
Sebastian Hack committed
111
112
113
#define INFEASIBLE(cost) ((cost) == INT_MAX)

static be_ifg_dump_dot_cb_t ifg_dot_cb;
114

115
116
typedef unsigned col_t;

Sebastian Hack's avatar
Sebastian Hack committed
117
118
119
120
121
122
123
124
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;
125
126

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

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

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

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

188
189
190
191
192
typedef struct {
	co2_cloud_irn_t *src, *tgt;
	int costs;
} edge_t;

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

Sebastian Hack's avatar
Sebastian Hack committed
195
196
#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))
197

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

Sebastian Hack's avatar
Sebastian Hack committed
205
	memset(ci, 0, size);
206
207
208
209
	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
210
211
	ci->irn          = irn;
	ci->aff          = a;
212

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

Sebastian Hack's avatar
Sebastian Hack committed
219
	return ci;
220
221
}

Sebastian Hack's avatar
Sebastian Hack committed
222
#define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
Sebastian Hack's avatar
Sebastian Hack committed
223
224

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

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

246
247
248
249
250
251
252
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);
}

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

259
static INLINE int color_is_fix(co2_t *env, const ir_node *irn)
260
261
262
263
264
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	return ci->fixed || ci->tmp_fixed;
}

265
static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
266
{
Matthias Braun's avatar
Matthias Braun committed
267
268
	if(ci->adm_cache == NULL) {
		const arch_register_req_t *req;
269
		ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
Matthias Braun's avatar
Matthias Braun committed
270
271
272
273
274
275
276
277
278
279
		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
280
			ci->is_constrained = 1;
Matthias Braun's avatar
Matthias Braun committed
281
		} else {
282
283
284
			bitset_copy(ci->adm_cache, env->ignore_regs);
			bitset_flip_all(ci->adm_cache);
		}
285
286
	}

287
288
289
	return ci->adm_cache;
}

Sebastian Hack's avatar
Sebastian Hack committed
290
static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
291
292
{
	bitset_copy(bs, get_adm(env, ci));
293
294
295
	return bs;
}

Sebastian Hack's avatar
Sebastian Hack committed
296
static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
297
{
298
	bitset_t *bs = get_adm(env, ci);
299
300
301
	return bitset_is_set(bs, col);
}

Sebastian Hack's avatar
Sebastian Hack committed
302
303
304
305
306
307
308
static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
{
	if(!ci->adm_cache)
		get_adm(env, ci);
	return ci->is_constrained;
}

309
static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
310
{
Matthias Braun's avatar
Matthias Braun committed
311
	const arch_register_req_t *req;
312

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

315
316
	if (arch_register_req_is(req, limited)) {
		unsigned n_regs   = env->co->cls->n_regs;
Matthias Braun's avatar
Matthias Braun committed
317
		unsigned n_constr = 0;
318
		unsigned i;
319

Matthias Braun's avatar
Matthias Braun committed
320
		n_constr = rbitset_popcnt(req->limited, n_regs);
321
322
323
		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
324
			}
325
		}
326
327
328
329
330
331
332
333
334
335
336
337
338
	}
}

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

	bitset_pos_t elm;
348
	const ir_node *pos;
349
350
351
	void *it;
	int i;

352
353
354
	/* Put all forbidden colors into the aux bitset. */
	admissible_colors(env, ci, forb);
	bitset_flip_all(forb);
355
356
357
358
359
360
361
362
363
364

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

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

	/* Set the costs to infinity for each color which is not allowed at this node. */
388
389
390
391
392
393
	bitset_foreach(forb, elm) {
		col_costs[elm].costs  = INT_MAX;
	}

}

394
static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
395
396
397
{
	int n_regs = env->co->cls->n_regs;
	int i;
398

399
400
401
402
403
	for(i = 0; i < n_regs; ++i) {
		seq[i].col   = i;
		seq[i].costs = INT_MAX;
	}

404
	(void) ci;
405
	assert(is_color_admissible(env, ci, col));
406
407
408
409
410
	seq[col].col = 0;
	seq[0].col   = col;
	seq[0].costs = 0;
}

411
412
413
414
415
416
417
418
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;
}

419
static void materialize_coloring(struct list_head *h)
420
421
422
423
{
	co2_irn_t *pos;

	list_for_each_entry(co2_irn_t, pos, h, changed_list) {
Sebastian Hack's avatar
Sebastian Hack committed
424
		pos->orig_col  = pos->tmp_col;
425
426
427
428
		pos->tmp_fixed = 0;
	}
}

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

431
static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
432
{
433
434
435
436
	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;
437
438
439

	int i;

Adam Szalkowski's avatar
Adam Szalkowski committed
440
441
442
	if(depth >= max_depth)
	  return 0;

443
444
445
446
447
448
	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;
449
		const ir_node *n;
450
451
		void *it;

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

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

		/*
		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
492
		be_ifg_neighbours_break(ifg, it);
493
494
495
496
497
498

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

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

	/* 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
527
528
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
529
530
531
532
533
534
535
536
537
538
539
540
		}

		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. */
541
		determine_color_costs(env, ci, csts);
542
543
544
545
546
547
548
549

		/* 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. */
550
		res = recolor(env, irn, csts, parent_changed, depth);
551
552
553
554
555
556
	}

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

557
static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
558
559
{
	co2_irn_t *ci = get_co2_irn(env, irn);
560
561
	col_t col     = get_col(env, irn);
	int res       = 0;
562

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

565
566
567
	/* 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
568
569
570
			ci->tmp_col     = col;
			ci->tmp_fixed   = 1;
			list_add(&ci->changed_list, parent_changed);
571
		}
572

573
574
		res = 1;
		goto end;
575
576
	}

577
	if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
578
579
		int n_regs           = env->co->cls->n_regs;
		col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
580

581
		/* Get the costs for giving the node a specific color. */
582
		single_color_cost(env, ci, tgt_col, seq);
583
584
585
586
587
588

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

	}

589
590
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));
591
	return res;
592
593
}

594
595
596
597
598
599
/**
 * 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
600
601
602
603
604
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
605

Sebastian Hack's avatar
Sebastian Hack committed
606
607
608
	for(i = 0; i < ci->mst_n_childs; ++i) {
		co2_cloud_irn_t *chld = ci->mst_childs[i];
		col_t chld_col        = front[i];
609

Sebastian Hack's avatar
Sebastian Hack committed
610
611
612
		cost += examine_subtree_coloring(chld, chld_col);
		cost += col != chld_col ? chld->mst_costs : 0;
	}
613

Sebastian Hack's avatar
Sebastian Hack committed
614
615
	return cost;
}
616

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

	admissible_colors(env, &ci->inh, bs);
	bitset_flip_all(bs);
	bitset_foreach(bs, elm)
Sebastian Hack's avatar
Sebastian Hack committed
641
		badness[elm] = ci->costs;
642
643
644
645
646
647
648

	/* 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
649
650
651
652
		if(bitset_popcnt(bs) == 1) {
			bitset_pos_t c = bitset_next_set(bs, 0);
			badness[c] += ci->costs;
		}
653

Sebastian Hack's avatar
Sebastian Hack committed
654
		else if(ni->fixed) {
655
			col_t c = get_col(env, ni->irn);
Sebastian Hack's avatar
Sebastian Hack committed
656
			badness[c] += ci->costs;
657
658
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
659
660
661
	be_ifg_neighbours_break(ifg, it);
}

662
663
664
665
666
667
668
/**
 * 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
669
670
671
672
673
674
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);
675
676
677
678
679
680

	/* 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
681
		for(j = 0; j < env->n_regs; ++j)
682
683
684
			ci->color_badness[j] += child->color_badness[j];
	}

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

689
690
691
/**
 * Unfix all nodes in a MST subtree.
 */
Sebastian Hack's avatar
Sebastian Hack committed
692
693
694
static void unfix_subtree(co2_cloud_irn_t *ci)
{
	int i;
695

Sebastian Hack's avatar
Sebastian Hack committed
696
697
698
699
	ci->inh.fixed = 0;
	for(i = 0; i < ci->mst_n_childs; ++i)
		unfix_subtree(ci->mst_childs[i]);
}
700

Sebastian Hack's avatar
Sebastian Hack committed
701
static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
702
703
704
705
{
	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;
Matthias Braun's avatar
Matthias Braun committed
706
	col_t parent_col     = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
707
708
709
	int min_badness      = INT_MAX;
	int best_col_costs   = INT_MAX;
	int best_col         = -1;
Sebastian Hack's avatar
Sebastian Hack committed
710
711
	int n_regs           = env->n_regs;
	int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
712
713
714
715

	struct list_head changed;
	int ok, i, j;

Sebastian Hack's avatar
Sebastian Hack committed
716
	for(i = 0; i < n_regs; ++i) {
717
718
719
		int badness = ci->color_badness[i];

		seq[i].col   = i;
Sebastian Hack's avatar
Sebastian Hack committed
720
		seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
721
722
723
724
725
726
727
728

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

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

		unfix_subtree(ci);
743
744
		INIT_LIST_HEAD(&changed);
		ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
Sebastian Hack's avatar
Sebastian Hack committed
745
746
747
748
749
750
751
		if(ok) {
			materialize_coloring(&changed);
			ci->inh.fixed = 1;
		}

		else
			continue;
752

Sebastian Hack's avatar
Sebastian Hack committed
753
754
755
756
757
758
759
		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;
760
761
762
		}

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

788
789
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
790
791
792
	be_ifg_t *ifg       = env->co->cenv->ifg;
	co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
	int costs           = 0;
793
794
	neighb_t *n;

Sebastian Hack's avatar
Sebastian Hack committed
795
	if(ci->cloud)
796
797
798
799
800
801
		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
802
	DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
803

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

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

820
821
822
	/* 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
823
		cloud->master = ci;
824
	}
825

826
827
828
829
830
	/* 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);
831
832
833
	}
}

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

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

Sebastian Hack's avatar
Sebastian Hack committed
861
	return cloud;
862
}
863

Sebastian Hack's avatar
Sebastian Hack committed
864
static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
865
{
866
	const ir_node *irn = ci->inh.irn;
Sebastian Hack's avatar
Sebastian Hack committed
867
868
	int *front   = FRONT_BASE(ci, col);
	int i, ok;
Sebastian Hack's avatar
Sebastian Hack committed
869
870
871
	struct list_head changed;

	INIT_LIST_HEAD(&changed);
Sebastian Hack's avatar
Sebastian Hack committed
872
873

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

878
 	for(i = 0; i < ci->mst_n_childs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
879
		apply_coloring(ci->mst_childs[i], front[i], depth + 1);
Sebastian Hack's avatar
Sebastian Hack committed
880
881
882
	}
}

883
884
885
886
887
888
889
890
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
891
892
893
static void process_cloud(co2_cloud_t *cloud)
{
	co2_t *env  = cloud->env;
Sebastian Hack's avatar
Sebastian Hack committed
894
	int n_regs  = env->n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
895
	int n_edges = 0;
Michael Beck's avatar
Michael Beck committed
896
	int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
Sebastian Hack's avatar
Sebastian Hack committed
897
	pdeq *q;
Sebastian Hack's avatar
Sebastian Hack committed
898
899

	edge_t *edges;
900
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
901
	int best_col;
902

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

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

Sebastian Hack's avatar
Sebastian Hack committed
933
934
935
936
		/* 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
937

Sebastian Hack's avatar
Sebastian Hack committed
938
939
940
941
942
943
944
			/* 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
945
		}
946
	}
Sebastian Hack's avatar
Sebastian Hack committed
947
	obstack_free(&cloud->obst, edges);
948

Sebastian Hack's avatar
Sebastian Hack committed
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
980
981
982
983
984
985
986
	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
987
		DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
Sebastian Hack's avatar
Sebastian Hack committed
988
989
990
		DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
	}

Sebastian Hack's avatar
Sebastian Hack committed
991
992
	for(i = 0; i < cloud->n_memb; ++i) {
		co2_cloud_irn_t *ci = cloud->seq[i];
Sebastian Hack's avatar
Sebastian Hack committed
993
		int n_childs = ci->mst_n_childs;
994
995
		int j;

Sebastian Hack's avatar
Sebastian Hack committed
996
997
998
999
1000
		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]));
For faster browsing, not all history is shown. View entire blame