becopyheur2.c 34.2 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * 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
21
22
23
24
/**
 * More experiments on coalescing.
 * @author Sebastian Hack
 * @date   14.04.2006
 */
Sebastian Hack's avatar
Sebastian Hack committed
25
#ifdef HAVE_CONFIG_H
26
#include "config.h"
Sebastian Hack's avatar
Sebastian Hack committed
27
28
29
30
31
#endif

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

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
55
#include "beabi.h"
#include "benode_t.h"
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"

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

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

/* Options using libcore */
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),
Sebastian Hack's avatar
Sebastian Hack committed
84
85
86
	{ NULL }
};

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
136
	ir_node         *irn;
	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

Michael Beck's avatar
Michael Beck committed
195
static void *co2_irn_init(ir_phase *ph, 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
205
206
	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
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
251
252
253
254
255
static col_t get_col(co2_t *env, ir_node *irn)
{
	co2_irn_t *ci = get_co2_irn(env, irn);
	return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
}

256
static INLINE int color_is_fix(co2_t *env, 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);
Matthias Braun's avatar
Matthias Braun committed
267
268
269
270
271
272
273
274
275
276
		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
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;
}

Sebastian Hack's avatar
Sebastian Hack committed
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;
}

Sebastian Hack's avatar
Sebastian Hack committed
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);
}

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

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

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

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

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

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

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

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

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

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

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

}

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

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

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

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

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

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

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

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

	int i;

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

439
440
441
442
443
444
445
446
447
	for(i = 0; i < n_regs; ++i) {
		col_t tgt_col  = col_list[i].col;
		unsigned costs = col_list[i].costs;
		int neigh_ok   = 1;

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

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

		/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
451
		if(INFEASIBLE(costs)) {
Sebastian Hack's avatar
Sebastian Hack committed
452
			DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
453
454
455
456
457
			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
458
459
		ci->tmp_col     = tgt_col;
		ci->tmp_fixed   = 1;
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
487

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

		/*
		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
495
			DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
			list_splice(&changed, parent_changed);
			res = 1;
			break;
		}

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

	return res;
}

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

Sebastian Hack's avatar
Sebastian Hack committed
518
	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
519
520
521
522

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

		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. */
537
		determine_color_costs(env, ci, csts);
538
539
540
541
542
543
544
545

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

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

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

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

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

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

573
	if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
574
575
		int n_regs           = env->co->cls->n_regs;
		col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
576

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

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

	}

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

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

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

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

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

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

	bitset_pos_t elm;
	ir_node *irn;
	void *it;

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

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

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

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

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
697
static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
698
699
700
701
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;
	col_t parent_col     = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
	int min_badness      = INT_MAX;
	int best_col_costs   = INT_MAX;
	int best_col         = -1;
Sebastian Hack's avatar
Sebastian Hack committed
706
707
	int n_regs           = env->n_regs;
	int n_iter           = is_root ? MIN(n_regs, subtree_iter) : 1;
708
709
710
711

	struct list_head changed;
	int ok, i, j;

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

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

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

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

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

		else
			continue;
748

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
929
930
931
932
		/* 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
933

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
992
993
994
995
996
997
998
999
		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
1000

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