becopyheur4.c 41.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.
 */

Christian Würdig's avatar
Christian Würdig committed
20
/**
Christian Würdig's avatar
Christian Würdig committed
21
22
23
24
25
 * @file
 * @brief       Simple copy minimization heuristics.
 * @author      Christian Wuerdig
 * @date        27.04.2007
 * @version     $Id$
Michael Beck's avatar
BugFix:    
Michael Beck committed
26
 *
Christian Würdig's avatar
Christian Würdig committed
27
 * This is the C implementation of the mst algorithm
Christian Würdig's avatar
Christian Würdig committed
28
 * originally written in Java by Sebastian Hack.
Christian Würdig's avatar
Christian Würdig committed
29
30
 * (also known as "heur3" :)
 * Performs simple copy minimization.
Christian Würdig's avatar
Christian Würdig committed
31
 */
yb9976's avatar
yb9976 committed
32
#include "config.h"
Christian Würdig's avatar
Christian Würdig committed
33

34
35
#define DISABLE_STATEV

36
37
#include <float.h>

Christian Würdig's avatar
Christian Würdig committed
38
#include "array.h"
Michael Beck's avatar
BugFix:    
Michael Beck committed
39
#include "irnode_t.h"
Christian Würdig's avatar
Christian Würdig committed
40
41
42
#include "bitset.h"
#include "raw_bitset.h"
#include "irphase_t.h"
43
44
45
#include "pqueue.h"
#include "xmalloc.h"
#include "pdeq.h"
Christian Würdig's avatar
Christian Würdig committed
46
#include "irprintf.h"
Christian Würdig's avatar
Christian Würdig committed
47
#include "irbitset.h"
48
#include "error.h"
49
#include "list.h"
Sebastian Hack's avatar
Sebastian Hack committed
50
#include "statev.h"
Christian Würdig's avatar
Christian Würdig committed
51

Sebastian Hack's avatar
Sebastian Hack committed
52
53
#include "irbitset.h"

Christian Würdig's avatar
Christian Würdig committed
54
55
56
#include "bearch.h"
#include "beifg.h"
#include "be_t.h"
57
#include "becopyopt_t.h"
58
59
#include "bemodule.h"

60
61
62
63
64

#define COL_COST_INFEASIBLE       DBL_MAX
#define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
#define NEIGHBOUR_CONSTR_COSTS    64.0

Michael Beck's avatar
Michael Beck committed
65

Michael Beck's avatar
Michael Beck committed
66
#ifdef DEBUG_libfirm
Sebastian Hack's avatar
Sebastian Hack committed
67

68
69
#define DBG_AFF_CHUNK(env, level, chunk) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while (0)
#define DBG_COL_COST(env, level, cost)   do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while (0)
Michael Beck's avatar
Michael Beck committed
70
71

static firm_dbg_module_t *dbg = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
72
73
74

#else

Michael Beck's avatar
Michael Beck committed
75
76
#define DBG_AFF_CHUNK(env, level, chunk)
#define DBG_COL_COST(env, level, cost)
Sebastian Hack's avatar
Sebastian Hack committed
77
78

#endif
Christian Würdig's avatar
Christian Würdig committed
79

80
81
82
typedef float real_t;
#define REAL(C)   (C ## f)

83
static unsigned last_chunk_id   = 0;
84
static int recolor_limit        = 7;
85
static real_t dislike_influence = REAL(0.1);
Christian Würdig's avatar
Christian Würdig committed
86

87
typedef struct _col_cost_t {
88
89
	int     col;
	real_t  cost;
90
} col_cost_t;
Christian Würdig's avatar
Christian Würdig committed
91

Michael Beck's avatar
Michael Beck committed
92
93
94
/**
 * An affinity chunk.
 */
Christian Würdig's avatar
Christian Würdig committed
95
typedef struct _aff_chunk_t {
96
	const ir_node  **n;                     /**< An ARR_F containing all nodes of the chunk. */
Matthias Braun's avatar
Matthias Braun committed
97
	const ir_node  **interfere;             /**< An ARR_F containing all inference. */
98
99
	int              weight;                /**< Weight of this chunk */
	unsigned         weight_consistent : 1; /**< Set if the weight is consistent. */
Michael Beck's avatar
Michael Beck committed
100
	unsigned         deleted           : 1; /**< For debugging: Set if the was deleted. */
101
102
	unsigned         id;                    /**< An id of this chunk. */
	unsigned         visited;
103
	list_head        list;
104
	col_cost_t       color_affinity[1];
Christian Würdig's avatar
Christian Würdig committed
105
106
} aff_chunk_t;

Michael Beck's avatar
Michael Beck committed
107
108
109
/**
 * An affinity edge.
 */
Christian Würdig's avatar
Christian Würdig committed
110
typedef struct _aff_edge_t {
111
112
	const ir_node *src;                   /**< Source node. */
	const ir_node *tgt;                   /**< Target node. */
113
	int           weight;                 /**< The weight of this edge. */
Christian Würdig's avatar
Christian Würdig committed
114
115
} aff_edge_t;

116
/* main coalescing environment */
117
typedef struct _co_mst_env_t {
Christian Würdig's avatar
Christian Würdig committed
118
119
120
121
	int              n_regs;         /**< number of regs in class */
	int              k;              /**< number of non-ignore registers in class */
	bitset_t         *ignore_regs;   /**< set containing all global ignore registers */
	ir_phase         ph;             /**< phase object holding data for nodes */
Matthias Braun's avatar
Matthias Braun committed
122
	pqueue_t         *chunks;        /**< priority queue for chunks */
123
	list_head         chunklist;     /**< list holding all chunks */
Christian Würdig's avatar
Christian Würdig committed
124
	be_ifg_t         *ifg;           /**< the interference graph */
125
	copy_opt_t       *co;            /**< the copy opt object */
126
	unsigned         chunk_visited;
Sebastian Hack's avatar
Sebastian Hack committed
127
	col_cost_t      **single_cols;
128
} co_mst_env_t;
Christian Würdig's avatar
Christian Würdig committed
129
130

/* stores coalescing related information for a node */
131
typedef struct _co_mst_irn_t {
132
	const ir_node    *irn;              /**< the irn this information belongs to */
133
134
135
136
137
138
139
140
141
142
	aff_chunk_t      *chunk;            /**< the chunk this irn belongs to */
	bitset_t         *adm_colors;       /**< set of admissible colors for this irn */
	ir_node          **int_neighs;      /**< array of all interfering neighbours (cached for speed reasons) */
	int              n_neighs;          /**< length of the interfering neighbours array. */
	int              int_aff_neigh;     /**< number of interfering affinity neighbours */
	int              col;               /**< color currently assigned */
	int              init_col;          /**< the initial color */
	int              tmp_col;           /**< a temporary assigned color */
	unsigned         fixed     : 1;     /**< the color is fixed */
	struct list_head list;              /**< Queue for coloring undo. */
143
	real_t           constr_factor;
144
145
146
147
} co_mst_irn_t;

#define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))

Christoph Mallon's avatar
Christoph Mallon committed
148
typedef int decide_func_t(const co_mst_irn_t *node, int col);
149

Christian Würdig's avatar
Christian Würdig committed
150
151
#ifdef DEBUG_libfirm

Michael Beck's avatar
BugFix:    
Michael Beck committed
152
153
154
/**
 * Write a chunk to stderr for debugging.
 */
155
156
static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c)
{
157
	int i, l;
158
	(void) env;
Michael Beck's avatar
BugFix:    
Michael Beck committed
159
160
161
	if (c->weight_consistent)
		ir_fprintf(stderr, " $%d ", c->weight);
	ir_fprintf(stderr, "{");
162
163
	for (i = 0, l = ARR_LEN(c->n); i < l; ++i) {
		const ir_node *n = c->n[i];
Michael Beck's avatar
BugFix:    
Michael Beck committed
164
		ir_fprintf(stderr, " %+F,", n);
Christian Würdig's avatar
Christian Würdig committed
165
	}
Michael Beck's avatar
BugFix:    
Michael Beck committed
166
	ir_fprintf(stderr, "}");
Christian Würdig's avatar
Christian Würdig committed
167
168
}

169
170
171
/**
 * Dump all admissible colors to stderr.
 */
172
173
static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node)
{
174
	unsigned idx;
175
176
	(void) env;

177
	if (bitset_popcount(node->adm_colors) < 1)
Christian Würdig's avatar
Christian Würdig committed
178
179
		fprintf(stderr, "no admissible colors?!?");
	else {
180
		bitset_foreach(node->adm_colors, idx) {
Christian Würdig's avatar
Christian Würdig committed
181
			fprintf(stderr, " %d", idx);
182
		}
Christian Würdig's avatar
Christian Würdig committed
183
184
185
	}
}

186
187
188
/**
 * Dump color-cost pairs to stderr.
 */
189
190
static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost)
{
Christian Würdig's avatar
Christian Würdig committed
191
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
192
193
	for (i = 0; i < env->n_regs; ++i)
		fprintf(stderr, " (%d, %.4f)", cost[i].col, cost[i].cost);
Christian Würdig's avatar
Christian Würdig committed
194
195
196
197
}

#endif /* DEBUG_libfirm */

198
199
static inline int get_mst_irn_col(const co_mst_irn_t *node)
{
200
	return node->tmp_col >= 0 ? node->tmp_col : node->col;
201
202
203
204
205
}

/**
 * @return 1 if node @p node has color @p col, 0 otherwise.
 */
206
207
static int decider_has_color(const co_mst_irn_t *node, int col)
{
208
209
210
211
212
213
	return get_mst_irn_col(node) == col;
}

/**
 * @return 1 if node @p node has not color @p col, 0 otherwise.
 */
214
215
static int decider_hasnot_color(const co_mst_irn_t *node, int col)
{
216
217
	return get_mst_irn_col(node) != col;
}
Christian Würdig's avatar
Christian Würdig committed
218

219
220
221
/**
 * Always returns true.
 */
222
223
static int decider_always_yes(const co_mst_irn_t *node, int col)
{
224
225
	(void) node;
	(void) col;
226
227
	return 1;
}
Christian Würdig's avatar
Christian Würdig committed
228

Michael Beck's avatar
Michael Beck committed
229
/** compares two affinity edges by its weight */
230
231
static int cmp_aff_edge(const void *a, const void *b)
{
232
233
	const aff_edge_t *e1 = a;
	const aff_edge_t *e2 = b;
Christian Würdig's avatar
Christian Würdig committed
234

Michael Beck's avatar
BugFix:    
Michael Beck committed
235
236
237
238
239
240
	if (e2->weight == e1->weight) {
		if (e2->src->node_idx == e1->src->node_idx)
			return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
		else
			return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
	}
Christian Würdig's avatar
Christian Würdig committed
241
	/* sort in descending order */
242
	return QSORT_CMP(e2->weight, e1->weight);
243
244
}

Michael Beck's avatar
Michael Beck committed
245
/** compares to color-cost pairs */
246
247
static __attribute__((unused)) int cmp_col_cost_lt(const void *a, const void *b)
{
248
249
	const col_cost_t *c1 = a;
	const col_cost_t *c2 = b;
250
	real_t diff = c1->cost - c2->cost;
251
	return (diff > 0) - (diff < 0);
Christian Würdig's avatar
Christian Würdig committed
252
253
}

254
255
static int cmp_col_cost_gt(const void *a, const void *b)
{
Sebastian Hack's avatar
Sebastian Hack committed
256
257
	const col_cost_t *c1 = a;
	const col_cost_t *c2 = b;
258
259
260
	if (c2->cost == c1->cost)
		return QSORT_CMP(c1->col, c2->col);

261
	real_t diff = c2->cost - c1->cost;
Sebastian Hack's avatar
Sebastian Hack committed
262
263
264
	return (diff > 0) - (diff < 0);
}

Christian Würdig's avatar
Christian Würdig committed
265
266
267
/**
 * Creates a new affinity chunk
 */
268
269
static inline aff_chunk_t *new_aff_chunk(co_mst_env_t *env)
{
270
	aff_chunk_t *c = XMALLOCF(aff_chunk_t, color_affinity, env->n_regs);
271
	c->n                 = NEW_ARR_F(const ir_node *, 0);
Matthias Braun's avatar
Matthias Braun committed
272
	c->interfere         = NEW_ARR_F(const ir_node *, 0);
273
274
	c->weight            = -1;
	c->weight_consistent = 0;
Michael Beck's avatar
Michael Beck committed
275
	c->deleted           = 0;
276
	c->id                = ++last_chunk_id;
Sebastian Hack's avatar
Sebastian Hack committed
277
	c->visited           = 0;
278
	list_add(&c->list, &env->chunklist);
Christian Würdig's avatar
Christian Würdig committed
279
280
281
282
283
284
	return c;
}

/**
 * Frees all memory allocated by an affinity chunk.
 */
285
static inline void delete_aff_chunk(aff_chunk_t *c)
286
{
287
	list_del(&c->list);
288
	DEL_ARR_F(c->interfere);
289
290
	DEL_ARR_F(c->n);
	c->deleted = 1;
291
	free(c);
Christian Würdig's avatar
Christian Würdig committed
292
293
}

294
295
296
297
298
299
/**
 * binary search of sorted nodes.
 *
 * @return the position where n is found in the array arr or ~pos
 * if the nodes is not here.
 */
300
301
static inline int nodes_bsearch(const ir_node **arr, const ir_node *n)
{
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
	int hi = ARR_LEN(arr);
	int lo = 0;

	while (lo < hi) {
		int md = lo + ((hi - lo) >> 1);

		if (arr[md] == n)
			return md;
		if (arr[md] < n)
			lo = md + 1;
		else
			hi = md;
	}

	return ~lo;
}

/** Check if a node n can be found inside arr. */
320
321
static int node_contains(const ir_node **arr, const ir_node *n)
{
322
323
324
325
326
327
328
329
330
	int i = nodes_bsearch(arr, n);
	return i >= 0;
}

/**
 * Insert a node into the sorted nodes list.
 *
 * @return 1 if the node was inserted, 0 else
 */
331
332
static int nodes_insert(const ir_node ***arr, const ir_node *irn)
{
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
	int idx = nodes_bsearch(*arr, irn);

	if (idx < 0) {
		int i, n = ARR_LEN(*arr);
		const ir_node **l;

		ARR_APP1(const ir_node *, *arr, irn);

		/* move it */
		idx = ~idx;
		l = *arr;
		for (i = n - 1; i >= idx; --i)
			l[i + 1] = l[i];
		l[idx] = irn;
		return 1;
	}
	return 0;
}

Christian Würdig's avatar
Christian Würdig committed
352
353
354
/**
 * Adds a node to an affinity chunk
 */
355
356
static inline void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node)
{
357
358
	int i;

359
	if (! nodes_insert(&c->n, node->irn))
360
361
		return;

Christian Würdig's avatar
Christian Würdig committed
362
363
	c->weight_consistent = 0;
	node->chunk          = c;
364

365
366
	for (i = node->n_neighs - 1; i >= 0; --i) {
		ir_node *neigh = node->int_neighs[i];
367
		nodes_insert(&c->interfere, neigh);
368
	}
Christian Würdig's avatar
Christian Würdig committed
369
370
}

Christian Würdig's avatar
Christian Würdig committed
371
372
373
/**
 * In case there is no phase information for irn, initialize it.
 */
374
static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn)
375
{
376
	co_mst_irn_t *res = phase_alloc(ph, sizeof(res[0]));
377
	co_mst_env_t *env = ph->priv;
Christian Würdig's avatar
Christian Würdig committed
378

379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
	const arch_register_req_t *req;
	neighbours_iter_t nodes_it;
	ir_node  *neigh;
	unsigned len;

	res->irn           = irn;
	res->chunk         = NULL;
	res->fixed         = 0;
	res->tmp_col       = -1;
	res->int_neighs    = NULL;
	res->int_aff_neigh = 0;
	res->col           = arch_register_get_index(arch_get_irn_register(irn));
	res->init_col      = res->col;
	INIT_LIST_HEAD(&res->list);

	DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));

	/* set admissible registers */
	res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);

	/* Exclude colors not assignable to the irn */
	req = arch_get_register_req_out(irn);
	if (arch_register_req_is(req, limited))
		rbitset_copy_to_bitset(req->limited, res->adm_colors);
	else
		bitset_set_all(res->adm_colors);

	/* exclude global ignore registers as well */
	bitset_andnot(res->adm_colors, env->ignore_regs);

	/* compute the constraint factor */
	res->constr_factor = (real_t) (1 + env->n_regs - bitset_popcount(res->adm_colors)) / env->n_regs;

	/* set the number of interfering affinity neighbours to -1, they are calculated later */
	res->int_aff_neigh = -1;

	/* build list of interfering neighbours */
	len = 0;
	be_ifg_foreach_neighbour(env->ifg, &nodes_it, irn, neigh) {
		if (!arch_irn_is_ignore(neigh)) {
			obstack_ptr_grow(phase_obst(ph), neigh);
			++len;
421
		}
Christian Würdig's avatar
Christian Würdig committed
422
	}
423
424
	res->int_neighs = obstack_finish(phase_obst(ph));
	res->n_neighs   = len;
Christian Würdig's avatar
Christian Würdig committed
425
426
427
	return res;
}

Christian Würdig's avatar
Christian Würdig committed
428
429
430
/**
 * Check if affinity chunk @p chunk interferes with node @p irn.
 */
431
432
static inline int aff_chunk_interferes(const aff_chunk_t *chunk, const ir_node *irn)
{
433
	return node_contains(chunk->interfere, irn);
Christian Würdig's avatar
Christian Würdig committed
434
435
}

436
437
438
439
440
441
/**
 * Check if there are interference edges from c1 to c2.
 * @param c1    A chunk
 * @param c2    Another chunk
 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
 */
442
443
static inline int aff_chunks_interfere(const aff_chunk_t *c1, const aff_chunk_t *c2)
{
444
445
	int i;

Christian Würdig's avatar
Christian Würdig committed
446
447
	if (c1 == c2)
		return 0;
Christian Würdig's avatar
Christian Würdig committed
448
449

	/* check if there is a node in c2 having an interfering neighbor in c1 */
450
451
452
453
454
455
456
	for (i = ARR_LEN(c2->n) - 1; i >= 0; --i) {
		const ir_node *irn = c2->n[i];

		if (node_contains(c1->interfere, irn))
			return 1;
	}
	return 0;
457
458
459
}

/**
460
461
462
 * Returns the affinity chunk of @p irn or creates a new
 * one with @p irn as element if there is none assigned.
 */
463
464
static inline aff_chunk_t *get_aff_chunk(co_mst_env_t *env, const ir_node *irn)
{
465
466
467
468
469
470
471
	co_mst_irn_t *node = get_co_mst_irn(env, irn);
	return node->chunk;
}

/**
 * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
 * are no interference edges from chunk(src) to chunk(tgt)).
472
473
 * @return 1 if successful, 0 if not possible
 */
474
475
static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node *tgt)
{
476
477
478
	aff_chunk_t *c1 = get_aff_chunk(env, src);
	aff_chunk_t *c2 = get_aff_chunk(env, tgt);

Michael Beck's avatar
Michael Beck committed
479
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
480
		DB((dbg, LEVEL_4, "Attempt to let c1 (id %u): ", c1 ? c1->id : 0));
481
482
483
484
485
		if (c1) {
			DBG_AFF_CHUNK(env, LEVEL_4, c1);
		} else {
			DB((dbg, LEVEL_4, "{%+F}", src));
		}
Michael Beck's avatar
Michael Beck committed
486
		DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %u): ", c2 ? c2->id : 0));
487
488
489
490
491
492
		if (c2) {
			DBG_AFF_CHUNK(env, LEVEL_4, c2);
		} else {
			DB((dbg, LEVEL_4, "{%+F}", tgt));
		}
		DB((dbg, LEVEL_4, "\n"));
Sebastian Hack's avatar
Sebastian Hack committed
493
#endif
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513

	if (c1 == NULL) {
		if (c2 == NULL) {
			/* no chunk exists */
			co_mst_irn_t *mirn = get_co_mst_irn(env, src);
			int i;

			for (i = mirn->n_neighs - 1; i >= 0; --i) {
				if (mirn->int_neighs[i] == tgt)
					break;
			}
			if (i < 0) {
				/* create one containing both nodes */
				c1 = new_aff_chunk(env);
				aff_chunk_add_node(c1, get_co_mst_irn(env, src));
				aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
				goto absorbed;
			}
		} else {
			/* c2 already exists */
514
			if (! aff_chunk_interferes(c2, src)) {
515
516
517
518
519
520
				aff_chunk_add_node(c2, get_co_mst_irn(env, src));
				goto absorbed;
			}
		}
	} else if (c2 == NULL) {
		/* c1 already exists */
521
		if (! aff_chunk_interferes(c1, tgt)) {
522
523
524
			aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
			goto absorbed;
		}
525
	} else if (c1 != c2 && ! aff_chunks_interfere(c1, c2)) {
Christian Würdig's avatar
Christian Würdig committed
526
		int idx, len;
Christian Würdig's avatar
Christian Würdig committed
527

Sebastian Hack's avatar
Sebastian Hack committed
528
529
		for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx)
			aff_chunk_add_node(c1, get_co_mst_irn(env, c2->n[idx]));
Christian Würdig's avatar
Christian Würdig committed
530

531
532
533
534
535
		for (idx = 0, len = ARR_LEN(c2->interfere); idx < len; ++idx) {
			const ir_node *irn = c2->interfere[idx];
			nodes_insert(&c1->interfere, irn);
		}

Christian Würdig's avatar
Christian Würdig committed
536
537
		c1->weight_consistent = 0;

538
		delete_aff_chunk(c2);
539
		goto absorbed;
540
	}
541
	DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
542
543
	return 0;

544
545
546
absorbed:
	DB((dbg, LEVEL_4, " ... absorbed\n"));
	return 1;
547
548
549
550
551
}

/**
 * Assures that the weight of the given chunk is consistent.
 */
552
553
static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c)
{
554
	if (! c->weight_consistent) {
Christian Würdig's avatar
Christian Würdig committed
555
		int w = 0;
556
557
		int idx, len, i;

Sebastian Hack's avatar
Sebastian Hack committed
558
		for (i = 0; i < env->n_regs; ++i) {
559
			c->color_affinity[i].col = i;
560
			c->color_affinity[i].cost = REAL(0.0);
561
		}
562

Christian Würdig's avatar
Christian Würdig committed
563
		for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
564
			const ir_node         *n       = c->n[idx];
565
566
567
			const affinity_node_t *an      = get_affinity_info(env->co, n);
			co_mst_irn_t          *node    = get_co_mst_irn(env, n);

Sebastian Hack's avatar
Sebastian Hack committed
568
			node->chunk = c;
569
			if (node->constr_factor > REAL(0.0)) {
570
				unsigned col;
571
				bitset_foreach (node->adm_colors, col)
Sebastian Hack's avatar
Sebastian Hack committed
572
					c->color_affinity[col].cost += node->constr_factor;
573
			}
574
575
576
577

			if (an != NULL) {
				neighb_t *neigh;
				co_gs_foreach_neighb(an, neigh) {
578
					const ir_node *m = neigh->irn;
579

580
					if (arch_irn_is_ignore(m))
581
582
						continue;

583
					w += node_contains(c->n, m) ? neigh->costs : 0;
584
585
586
587
				}
			}
		}

Sebastian Hack's avatar
Sebastian Hack committed
588
		for (i = 0; i < env->n_regs; ++i)
589
			c->color_affinity[i].cost *= (REAL(1.0) / ARR_LEN(c->n));
Sebastian Hack's avatar
Sebastian Hack committed
590

591
		c->weight            = w;
592
		// c->weight            = bitset_popcount(c->nodes);
593
594
595
596
		c->weight_consistent = 1;
	}
}

Michael Beck's avatar
BugFix:    
Michael Beck committed
597
/**
598
 * Count the number of interfering affinity neighbours
Michael Beck's avatar
BugFix:    
Michael Beck committed
599
 */
600
601
static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an)
{
Christoph Mallon's avatar
Christoph Mallon committed
602
	const neighb_t     *neigh;
603
	const ir_node      *irn  = an->irn;
Christoph Mallon's avatar
Christoph Mallon committed
604
605
	const co_mst_irn_t *node = get_co_mst_irn(env, irn);
	int                res   = 0;
Michael Beck's avatar
BugFix:    
Michael Beck committed
606
607

	co_gs_foreach_neighb(an, neigh) {
Christoph Mallon's avatar
Christoph Mallon committed
608
609
		const ir_node *n = neigh->irn;
		int           i;
Michael Beck's avatar
BugFix:    
Michael Beck committed
610

611
		if (arch_irn_is_ignore(n))
Michael Beck's avatar
BugFix:    
Michael Beck committed
612
613
			continue;

614
		/* check if the affinity neighbour interfere */
615
		for (i = 0; i < node->n_neighs; ++i) {
616
			if (node->int_neighs[i] == n) {
Michael Beck's avatar
BugFix:    
Michael Beck committed
617
618
619
620
621
622
623
624
625
				++res;
				break;
			}
		}
	}
	return res;
}


Christian Würdig's avatar
Christian Würdig committed
626
627
628
629
630
631
632
/**
 * Build chunks of nodes connected by affinity edges.
 * We start at the heaviest affinity edge.
 * The chunks of the two edge-defining nodes will be
 * merged if there are no interference edges from one
 * chunk to the other.
 */
633
634
static void build_affinity_chunks(co_mst_env_t *env)
{
635
	nodes_iter_t nodes_it;
636
637
	aff_edge_t  *edges    = NEW_ARR_F(aff_edge_t, 0);
	ir_node     *n;
638
	int         i, len;
639
	aff_chunk_t *curr_chunk;
Christian Würdig's avatar
Christian Würdig committed
640
641

	/* at first we create the affinity edge objects */
642
	be_ifg_foreach_node(env->ifg, &nodes_it, n) {
643
644
645
		int             n_idx = get_irn_idx(n);
		co_mst_irn_t    *n1;
		affinity_node_t *an;
Christian Würdig's avatar
Christian Würdig committed
646

647
		if (arch_irn_is_ignore(n))
Christian Würdig's avatar
Christian Würdig committed
648
649
			continue;

650
651
		n1 = get_co_mst_irn(env, n);
		an = get_affinity_info(env->co, n);
Christian Würdig's avatar
Christian Würdig committed
652
653
654

		if (an != NULL) {
			neighb_t *neigh;
Michael Beck's avatar
BugFix:    
Michael Beck committed
655

656
657
			if (n1->int_aff_neigh < 0)
				n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
Christian Würdig's avatar
Christian Würdig committed
658
659

			/* build the affinity edges */
Christian Würdig's avatar
Christian Würdig committed
660
			co_gs_foreach_neighb(an, neigh) {
661
662
				const ir_node *m     = neigh->irn;
				int            m_idx = get_irn_idx(m);
Christian Würdig's avatar
Christian Würdig committed
663

664
				/* record the edge in only one direction */
Christian Würdig's avatar
Christian Würdig committed
665
				if (n_idx < m_idx) {
666
					co_mst_irn_t *n2;
667
					aff_edge_t   edge;
Christian Würdig's avatar
Christian Würdig committed
668

669
					/* skip ignore nodes */
670
					if (arch_irn_is_ignore(m))
671
672
						continue;

Michael Beck's avatar
BugFix:    
Michael Beck committed
673
674
675
					edge.src = n;
					edge.tgt = m;

676
					n2 = get_co_mst_irn(env, m);
677
					if (n2->int_aff_neigh < 0) {
Michael Beck's avatar
BugFix:    
Michael Beck committed
678
						affinity_node_t *am = get_affinity_info(env->co, m);
679
						n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
Michael Beck's avatar
BugFix:    
Michael Beck committed
680
					}
Sebastian Hack's avatar
Sebastian Hack committed
681
682
683
684
					/*
					 * these weights are pure hackery ;-).
					 * It's not chriswue's fault but mine.
					 */
Sebastian Hack's avatar
Sebastian Hack committed
685
					edge.weight = neigh->costs;
686
					ARR_APP1(aff_edge_t, edges, edge);
Christian Würdig's avatar
Christian Würdig committed
687
688
689
690
691
				}
			}
		}
	}

692
	/* now: sort edges and build the affinity chunks */
693
694
695
	len = ARR_LEN(edges);
	qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
	for (i = 0; i < len; ++i) {
696
		DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
Michael Beck's avatar
BugFix:    
Michael Beck committed
697

698
		(void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
699
	}
Christian Würdig's avatar
Christian Würdig committed
700

701
	/* now insert all chunks into a priority queue */
702
	list_for_each_entry(aff_chunk_t, curr_chunk, &env->chunklist, list) {
703
		aff_chunk_assure_weight(env, curr_chunk);
Christian Würdig's avatar
Christian Würdig committed
704

705
		DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id));
Christian Würdig's avatar
Christian Würdig committed
706
		DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
707
		DBG((dbg, LEVEL_1, "\n"));
Michael Beck's avatar
BugFix:    
Michael Beck committed
708

709
		pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
Christian Würdig's avatar
Christian Würdig committed
710
	}
711

712
713
714
715
716
717
718
719
720
721
	foreach_phase_irn(&env->ph, n) {
		co_mst_irn_t *mirn = get_co_mst_irn(env, n);

		if (mirn->chunk == NULL) {
			/* no chunk is allocated so far, do it now */
			aff_chunk_t *curr_chunk = new_aff_chunk(env);
			aff_chunk_add_node(curr_chunk, mirn);

			aff_chunk_assure_weight(env, curr_chunk);

722
			DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id));
723
724
725
726
727
728
			DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
			DBG((dbg, LEVEL_1, "\n"));

			pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
		}
	}
Christian Würdig's avatar
Christian Würdig committed
729
730
731
732

	DEL_ARR_F(edges);
}

Sebastian Hack's avatar
Sebastian Hack committed
733
static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
Sebastian Hack's avatar
Sebastian Hack committed
734
{
Matthias Braun's avatar
Matthias Braun committed
735
	pqueue_t *grow = new_pqueue();
736
	const ir_node *max_node = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
737
	int max_weight = 0;
738
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
739
740

	for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) {
741
742
		const ir_node   *irn = chunk->n[i];
		affinity_node_t *an  = get_affinity_info(env->co, irn);
Sebastian Hack's avatar
Sebastian Hack committed
743
744
745
		int w = 0;
		neighb_t *neigh;

746
		if (arch_irn_is_ignore(irn))
Sebastian Hack's avatar
Sebastian Hack committed
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
			continue;

		if (an) {
			co_gs_foreach_neighb(an, neigh)
				w += neigh->costs;

			if (w > max_weight) {
				max_weight = w;
				max_node   = irn;
			}
		}
	}

	if (max_node) {
		bitset_t *visited = bitset_irg_malloc(env->co->irg);

		for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i)
			bitset_add_irn(visited, chunk->n[i]);

766
		pqueue_put(grow, (void *) max_node, max_weight);
Sebastian Hack's avatar
Sebastian Hack committed
767
768
769
		bitset_remv_irn(visited, max_node);
		i = 0;
		while (!pqueue_empty(grow)) {
Matthias Braun's avatar
Matthias Braun committed
770
			ir_node *irn = pqueue_pop_front(grow);
Sebastian Hack's avatar
Sebastian Hack committed
771
			affinity_node_t *an = get_affinity_info(env->co, irn);
772
			neighb_t        *neigh;
Sebastian Hack's avatar
Sebastian Hack committed
773

774
			if (arch_irn_is_ignore(irn))
Sebastian Hack's avatar
Sebastian Hack committed
775
776
777
778
779
780
781
782
783
784
785
786
				continue;

			assert(i <= ARR_LEN(chunk->n));
			chunk->n[i++] = irn;

			assert(an);

			/* build the affinity edges */
			co_gs_foreach_neighb(an, neigh) {
				co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn);

				if (bitset_contains_irn(visited, node->irn)) {
787
					pqueue_put(grow, (void *) neigh->irn, neigh->costs);
Sebastian Hack's avatar
Sebastian Hack committed
788
789
790
791
792
793
794
795
796
797
					bitset_remv_irn(visited, node->irn);
				}
			}
		}

		del_pqueue(grow);
		bitset_free(visited);
	}
}

798
799
800
801
802
803
804
805
/**
 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
 */
static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
	aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
{
	waitq *nodes = new_waitq();

806
	DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%u) from %+F, color %d:", chunk->id, node->irn, col));
Christian Würdig's avatar
Christian Würdig committed
807

808
809
810
811
	/* init queue and chunk */
	waitq_put(nodes, node);
	bitset_set(visited, get_irn_idx(node->irn));
	aff_chunk_add_node(chunk, node);
812
	DB((dbg, LEVEL_1, " %+F", node->irn));
813
814
815

	/* as long as there are nodes in the queue */
	while (! waitq_empty(nodes)) {
Christian Würdig's avatar
Christian Würdig committed
816
817
		co_mst_irn_t    *n  = waitq_get(nodes);
		affinity_node_t *an = get_affinity_info(env->co, n->irn);
818
819
820
821
822

		/* check all affinity neighbors */
		if (an != NULL) {
			neighb_t *neigh;
			co_gs_foreach_neighb(an, neigh) {
823
824
				const ir_node *m    = neigh->irn;
				int            m_idx = get_irn_idx(m);
825
826
				co_mst_irn_t *n2;

827
				if (arch_irn_is_ignore(m))
828
829
830
831
					continue;

				n2 = get_co_mst_irn(env, m);

832
833
834
835
836
				if (! bitset_is_set(visited, m_idx)  &&
					decider(n2, col)                 &&
					! n2->fixed                      &&
					! aff_chunk_interferes(chunk, m) &&
					node_contains(orig_chunk->n, m))
837
838
839
840
841
842
				{
					/*
						following conditions are met:
						- neighbour is not visited
						- neighbour likes the color
						- neighbour has not yet a fixed color
Christian Würdig's avatar
Christian Würdig committed
843
						- the new chunk doesn't interfere with the neighbour
844
845
846
847
						- neighbour belongs or belonged once to the original chunk
					*/
					bitset_set(visited, m_idx);
					aff_chunk_add_node(chunk, n2);
848
					DB((dbg, LEVEL_1, " %+F", n2->irn));
849
850
851
852
853
854
855
					/* enqueue for further search */
					waitq_put(nodes, n2);
				}
			}
		}
	}

856
	DB((dbg, LEVEL_1, "\n"));
Christian Würdig's avatar
Christian Würdig committed
857

858
859
860
861
862
863
	del_waitq(nodes);
}

/**
 * Fragment the given chunk into chunks having given color and not having given color.
 */
864
865
static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp)
{
866
	bitset_t    *visited = bitset_irg_malloc(env->co->irg);
Christian Würdig's avatar
Christian Würdig committed
867
	int         idx, len;
868
869
	aff_chunk_t *best = NULL;

Christian Würdig's avatar
Christian Würdig committed
870
	for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
871
		const ir_node *irn;
872
873
874
		co_mst_irn_t  *node;
		aff_chunk_t   *tmp_chunk;
		decide_func_t *decider;
Christian Würdig's avatar
Christian Würdig committed
875
		int           check_for_best;
876

Christian Würdig's avatar
Christian Würdig committed
877
		irn = c->n[idx];
878
		if (bitset_is_set(visited, get_irn_idx(irn)))
879
880
881
882
			continue;

		node = get_co_mst_irn(env, irn);

Christian Würdig's avatar
Christian Würdig committed
883
884
885
		if (get_mst_irn_col(node) == col) {
			decider        = decider_has_color;
			check_for_best = 1;
886
			DBG((dbg, LEVEL_4, "\tcolor %d wanted\n", col));
Christian Würdig's avatar
Christian Würdig committed
887
888
889
890
		}
		else {
			decider        = decider_hasnot_color;
			check_for_best = 0;
891
			DBG((dbg, LEVEL_4, "\tcolor %d forbidden\n", col));
Christian Würdig's avatar
Christian Würdig committed
892
893
		}

894
895
896
897
		/* create a new chunk starting at current node */
		tmp_chunk = new_aff_chunk(env);
		waitq_put(tmp, tmp_chunk);
		expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
898
		assert(ARR_LEN(tmp_chunk->n) > 0 && "No nodes added to chunk");
899
900
901

		/* remember the local best */
		aff_chunk_assure_weight(env, tmp_chunk);
Christian Würdig's avatar
Christian Würdig committed
902
		if (check_for_best && (! best || best->weight < tmp_chunk->weight))
903
904
905
906
907
908
909
910
911
912
913
914
			best = tmp_chunk;
	}

	assert(best && "No chunk found?");
	bitset_free(visited);
	return best;
}

/**
 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
 * ATTENTION: the queue is empty after calling this function!
 */
915
916
static inline void reject_coloring(struct list_head *nodes)
{
917
	co_mst_irn_t *n, *temp;
918
	DB((dbg, LEVEL_4, "\treject coloring for"));
919
	list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
920
		DB((dbg, LEVEL_4, " %+F", n->irn));
921
922
923
		assert(n->tmp_col >= 0);
		n->tmp_col = -1;
		list_del_init(&n->list);
924
	}
925
	DB((dbg, LEVEL_4, "\n"));
926
927
}

928
929
static inline void materialize_coloring(struct list_head *nodes)
{
930
931
932
933
934
935
936
937
938
	co_mst_irn_t *n, *temp;
	list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
		assert(n->tmp_col >= 0);
		n->col     = n->tmp_col;
		n->tmp_col = -1;
		list_del_init(&n->list);
	}
}

939
static inline void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed)
940
941
942
943
944
{
	assert(col >= 0);
	assert(!node->fixed);
	assert(node->tmp_col < 0);
	assert(node->list.next == &node->list && node->list.prev == &node->list);
Sebastian Hack's avatar
Sebastian Hack committed
945
	assert(bitset_is_set(node->adm_colors, col));
946
947
948
949
950

	list_add_tail(&node->list, changed);
	node->tmp_col = col;
}

951
static inline int is_loose(co_mst_irn_t *node)
952
953
954
955
{
	return !node->fixed && node->tmp_col < 0;
}

956
957
958
/**
 * Determines the costs for each color if it would be assigned to node @p node.
 */
959
960
961
962
static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs)
{
	int   *neigh_cols = ALLOCAN(int, env->n_regs);
	int    n_loose    = 0;
963
	real_t coeff;
964
	int    i;
Christian Würdig's avatar
Christian Würdig committed
965

Sebastian Hack's avatar
Sebastian Hack committed
966
967
968
	for (i = 0; i < env->n_regs; ++i) {
		neigh_cols[i] = 0;
		costs[i].col = i;
969
		costs[i].cost = bitset_is_set(node->adm_colors, i) ? node->constr_factor : REAL(0.0);
970
971
	}

972
	for (i = 0; i < node->n_neighs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
973
974
975
976
977
		co_mst_irn_t *n = get_co_mst_irn(env, node->int_neighs[i]);
		int col = get_mst_irn_col(n);
		if (is_loose(n)) {
			++n_loose;
			++neigh_cols[col];
978
979
		} else
			costs[col].cost = REAL(0.0);
980
981
	}

Sebastian Hack's avatar
Sebastian Hack committed
982
	if (n_loose > 0) {
983
		coeff = REAL(1.0) / n_loose;
Sebastian Hack's avatar
Sebastian Hack committed
984
		for (i = 0; i < env->n_regs; ++i)
985
			costs[i].cost *= REAL(1.0) - coeff * neigh_cols[i];
Sebastian Hack's avatar
Sebastian Hack committed
986
	}
987
988
989
}

/* need forward declaration due to recursive call */
Sebastian Hack's avatar
Sebastian Hack committed
990
static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones, int depth, int *max_depth, int *trip);