becopyheur2.c 34.1 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

Matthias Braun's avatar
Matthias Braun committed
31
32
#include "lc_opts.h"
#include "lc_opts_enum.h"
33

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

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

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

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

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

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

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

*/

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

static be_ifg_dump_dot_cb_t ifg_dot_cb;
113

114
115
typedef unsigned col_t;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

286
287
288
	return ci->adm_cache;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

}

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

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

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

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

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

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

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

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

	int i;

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

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;
448
		const ir_node *n;
449
450
		void *it;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	struct list_head changed;
	int ok, i, j;

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

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

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

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

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

		else
			continue;
751

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
993
994
995
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]));
		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]));
For faster browsing, not all history is shown. View entire blame