becopyheur4.c 41.6 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 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.
 */
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.
 */
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
	int              n_regs;         /**< number of regs in class */
	int              k;              /**< number of non-ignore registers in class */
120
	bitset_t         *allocatable_regs; /**< set containing all global ignore registers */
Christian Würdig's avatar
Christian Würdig committed
121
	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
} co_mst_irn_t;

146
147
148
149
static co_mst_irn_t *get_co_mst_irn(co_mst_env_t *env, const ir_node *node)
{
	return (co_mst_irn_t*)phase_get_or_set_irn_data(&env->ph, node);
}
150

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

Christian Würdig's avatar
Christian Würdig committed
153
154
#ifdef DEBUG_libfirm

Michael Beck's avatar
BugFix:    
Michael Beck committed
155
156
157
/**
 * Write a chunk to stderr for debugging.
 */
158
159
static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c)
{
160
	int i, l;
161
	(void) env;
Michael Beck's avatar
BugFix:    
Michael Beck committed
162
163
164
	if (c->weight_consistent)
		ir_fprintf(stderr, " $%d ", c->weight);
	ir_fprintf(stderr, "{");
165
166
	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
167
		ir_fprintf(stderr, " %+F,", n);
Christian Würdig's avatar
Christian Würdig committed
168
	}
Michael Beck's avatar
BugFix:    
Michael Beck committed
169
	ir_fprintf(stderr, "}");
Christian Würdig's avatar
Christian Würdig committed
170
171
}

172
173
174
/**
 * Dump all admissible colors to stderr.
 */
175
176
static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node)
{
177
	size_t idx;
178
179
	(void) env;

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

189
190
191
/**
 * Dump color-cost pairs to stderr.
 */
192
193
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
194
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
195
196
	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
197
198
199
200
}

#endif /* DEBUG_libfirm */

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

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

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

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

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

Michael Beck's avatar
BugFix:    
Michael Beck committed
238
239
240
241
242
243
	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
244
	/* sort in descending order */
245
	return QSORT_CMP(e2->weight, e1->weight);
246
247
}

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

257
258
static int cmp_col_cost_gt(const void *a, const void *b)
{
259
260
	const col_cost_t *c1 = (const col_cost_t*)a;
	const col_cost_t *c2 = (const col_cost_t*)b;
Michael Beck's avatar
Michael Beck committed
261
262
263
	real_t diff = c2->cost - c1->cost;

	if (diff == 0.0)
264
265
		return QSORT_CMP(c1->col, c2->col);

Sebastian Hack's avatar
Sebastian Hack committed
266
267
268
	return (diff > 0) - (diff < 0);
}

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

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

298
299
300
301
302
303
/**
 * binary search of sorted nodes.
 *
 * @return the position where n is found in the array arr or ~pos
 * if the nodes is not here.
 */
304
305
static inline int nodes_bsearch(const ir_node **arr, const ir_node *n)
{
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
	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. */
324
325
static int node_contains(const ir_node **arr, const ir_node *n)
{
326
327
328
329
330
331
332
333
334
	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
 */
335
336
static int nodes_insert(const ir_node ***arr, const ir_node *irn)
{
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
	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
356
357
358
/**
 * Adds a node to an affinity chunk
 */
359
360
static inline void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node)
{
361
362
	int i;

363
	if (! nodes_insert(&c->n, node->irn))
364
365
		return;

Christian Würdig's avatar
Christian Würdig committed
366
367
	c->weight_consistent = 0;
	node->chunk          = c;
368

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

Christian Würdig's avatar
Christian Würdig committed
375
376
377
/**
 * In case there is no phase information for irn, initialize it.
 */
378
static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn)
379
{
380
381
	co_mst_irn_t *res = (co_mst_irn_t*)phase_alloc(ph, sizeof(res[0]));
	co_mst_env_t *env = (co_mst_env_t*)ph->priv;
Christian Würdig's avatar
Christian Würdig committed
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
	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 */
411
	bitset_and(res->adm_colors, env->allocatable_regs);
412
413
414
415
416
417
418
419
420
421
422
423
424

	/* 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;
425
		}
Christian Würdig's avatar
Christian Würdig committed
426
	}
427
	res->int_neighs = (ir_node**)obstack_finish(phase_obst(ph));
428
	res->n_neighs   = len;
Christian Würdig's avatar
Christian Würdig committed
429
430
431
	return res;
}

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

440
441
442
443
444
445
/**
 * 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.
 */
446
447
static inline int aff_chunks_interfere(const aff_chunk_t *c1, const aff_chunk_t *c2)
{
448
449
	int i;

Christian Würdig's avatar
Christian Würdig committed
450
451
	if (c1 == c2)
		return 0;
Christian Würdig's avatar
Christian Würdig committed
452
453

	/* check if there is a node in c2 having an interfering neighbor in c1 */
454
455
456
457
458
459
460
	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;
461
462
463
}

/**
464
465
466
 * Returns the affinity chunk of @p irn or creates a new
 * one with @p irn as element if there is none assigned.
 */
467
468
static inline aff_chunk_t *get_aff_chunk(co_mst_env_t *env, const ir_node *irn)
{
469
470
471
472
473
474
475
	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)).
476
477
 * @return 1 if successful, 0 if not possible
 */
478
479
static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node *tgt)
{
480
481
482
	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
483
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
484
		DB((dbg, LEVEL_4, "Attempt to let c1 (id %u): ", c1 ? c1->id : 0));
485
486
487
488
489
		if (c1) {
			DBG_AFF_CHUNK(env, LEVEL_4, c1);
		} else {
			DB((dbg, LEVEL_4, "{%+F}", src));
		}
Michael Beck's avatar
Michael Beck committed
490
		DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %u): ", c2 ? c2->id : 0));
491
492
493
494
495
496
		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
497
#endif
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517

	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 */
518
			if (! aff_chunk_interferes(c2, src)) {
519
520
521
522
523
524
				aff_chunk_add_node(c2, get_co_mst_irn(env, src));
				goto absorbed;
			}
		}
	} else if (c2 == NULL) {
		/* c1 already exists */
525
		if (! aff_chunk_interferes(c1, tgt)) {
526
527
528
			aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
			goto absorbed;
		}
529
	} else if (c1 != c2 && ! aff_chunks_interfere(c1, c2)) {
Christian Würdig's avatar
Christian Würdig committed
530
		int idx, len;
Christian Würdig's avatar
Christian Würdig committed
531

Sebastian Hack's avatar
Sebastian Hack committed
532
533
		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
534

535
536
537
538
539
		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
540
541
		c1->weight_consistent = 0;

542
		delete_aff_chunk(c2);
543
		goto absorbed;
544
	}
545
	DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
546
547
	return 0;

548
549
550
absorbed:
	DB((dbg, LEVEL_4, " ... absorbed\n"));
	return 1;
551
552
553
554
555
}

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

Sebastian Hack's avatar
Sebastian Hack committed
562
		for (i = 0; i < env->n_regs; ++i) {
563
			c->color_affinity[i].col = i;
564
			c->color_affinity[i].cost = REAL(0.0);
565
		}
566

Christian Würdig's avatar
Christian Würdig committed
567
		for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
568
			const ir_node         *n       = c->n[idx];
569
570
571
			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
572
			node->chunk = c;
573
			if (node->constr_factor > REAL(0.0)) {
574
				size_t col;
575
				bitset_foreach (node->adm_colors, col)
Sebastian Hack's avatar
Sebastian Hack committed
576
					c->color_affinity[col].cost += node->constr_factor;
577
			}
578
579
580
581

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

584
					if (arch_irn_is_ignore(m))
585
586
						continue;

587
					w += node_contains(c->n, m) ? neigh->costs : 0;
588
589
590
591
				}
			}
		}

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

595
		c->weight            = w;
596
		// c->weight            = bitset_popcount(c->nodes);
597
598
599
600
		c->weight_consistent = 1;
	}
}

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

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

615
		if (arch_irn_is_ignore(n))
Michael Beck's avatar
BugFix:    
Michael Beck committed
616
617
			continue;

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


Christian Würdig's avatar
Christian Würdig committed
630
631
632
633
634
635
636
/**
 * 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.
 */
637
638
static void build_affinity_chunks(co_mst_env_t *env)
{
639
	nodes_iter_t nodes_it;
640
641
	aff_edge_t  *edges    = NEW_ARR_F(aff_edge_t, 0);
	ir_node     *n;
642
	int         i, len;
643
	aff_chunk_t *curr_chunk;
Christian Würdig's avatar
Christian Würdig committed
644
645

	/* at first we create the affinity edge objects */
646
	be_ifg_foreach_node(env->ifg, &nodes_it, n) {
647
648
649
		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
650

651
		if (arch_irn_is_ignore(n))
Christian Würdig's avatar
Christian Würdig committed
652
653
			continue;

654
655
		n1 = get_co_mst_irn(env, n);
		an = get_affinity_info(env->co, n);
Christian Würdig's avatar
Christian Würdig committed
656
657
658

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

660
661
			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
662
663

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

668
				/* record the edge in only one direction */
Christian Würdig's avatar
Christian Würdig committed
669
				if (n_idx < m_idx) {
670
					co_mst_irn_t *n2;
671
					aff_edge_t   edge;
Christian Würdig's avatar
Christian Würdig committed
672

673
					/* skip ignore nodes */
674
					if (arch_irn_is_ignore(m))
675
676
						continue;

Michael Beck's avatar
BugFix:    
Michael Beck committed
677
678
679
					edge.src = n;
					edge.tgt = m;

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

696
	/* now: sort edges and build the affinity chunks */
697
698
699
	len = ARR_LEN(edges);
	qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
	for (i = 0; i < len; ++i) {
700
		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
701

702
		(void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
703
	}
Christian Würdig's avatar
Christian Würdig committed
704

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

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

713
		pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
Christian Würdig's avatar
Christian Würdig committed
714
	}
715

716
717
718
719
720
721
722
723
724
725
	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);

726
			DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id));
727
728
729
730
731
732
			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
733
734
735
736

	DEL_ARR_F(edges);
}

Sebastian Hack's avatar
Sebastian Hack committed
737
static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
Sebastian Hack's avatar
Sebastian Hack committed
738
{
739
740
741
742
	pqueue_t      *grow       = new_pqueue();
	ir_node const *max_node   = NULL;
	int            max_weight = 0;
	size_t         i;
Sebastian Hack's avatar
Sebastian Hack committed
743

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

750
		if (arch_irn_is_ignore(irn))
Sebastian Hack's avatar
Sebastian Hack committed
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
			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);

767
768
		for (i = ARR_LEN(chunk->n); i != 0;)
			bitset_add_irn(visited, chunk->n[--i]);
Sebastian Hack's avatar
Sebastian Hack committed
769

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

778
			if (arch_irn_is_ignore(irn))
Sebastian Hack's avatar
Sebastian Hack committed
779
780
781
782
783
784
785
786
787
788
789
790
				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)) {
791
					pqueue_put(grow, (void *) neigh->irn, neigh->costs);
Sebastian Hack's avatar
Sebastian Hack committed
792
793
794
795
796
797
798
799
800
801
					bitset_remv_irn(visited, node->irn);
				}
			}
		}

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

802
803
804
805
806
807
808
809
/**
 * 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();

810
	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
811

812
813
814
815
	/* init queue and chunk */
	waitq_put(nodes, node);
	bitset_set(visited, get_irn_idx(node->irn));
	aff_chunk_add_node(chunk, node);
816
	DB((dbg, LEVEL_1, " %+F", node->irn));
817
818
819

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

		/* check all affinity neighbors */
		if (an != NULL) {
			neighb_t *neigh;
			co_gs_foreach_neighb(an, neigh) {
827
828
				const ir_node *m    = neigh->irn;
				int            m_idx = get_irn_idx(m);
829
830
				co_mst_irn_t *n2;

831
				if (arch_irn_is_ignore(m))
832
833
834
835
					continue;

				n2 = get_co_mst_irn(env, m);

836
837
838
839
840
				if (! bitset_is_set(visited, m_idx)  &&
					decider(n2, col)                 &&
					! n2->fixed                      &&
					! aff_chunk_interferes(chunk, m) &&
					node_contains(orig_chunk->n, m))
841
842
843
844
845
846
				{
					/*
						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
847
						- the new chunk doesn't interfere with the neighbour
848
849
850
851
						- neighbour belongs or belonged once to the original chunk
					*/
					bitset_set(visited, m_idx);
					aff_chunk_add_node(chunk, n2);
852
					DB((dbg, LEVEL_1, " %+F", n2->irn));
853
854
855
856
857
858
859
					/* enqueue for further search */
					waitq_put(nodes, n2);
				}
			}
		}
	}

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

862
863
864
865
866
867
	del_waitq(nodes);
}

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

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

Christian Würdig's avatar
Christian Würdig committed
881
		irn = c->n[idx];
882
		if (bitset_is_set(visited, get_irn_idx(irn)))
883
884
885
886
			continue;

		node = get_co_mst_irn(env, irn);

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

898
899
900
901
		/* 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);
902
		assert(ARR_LEN(tmp_chunk->n) > 0 && "No nodes added to chunk");
903
904
905

		/* remember the local best */
		aff_chunk_assure_weight(env, tmp_chunk);
Christian Würdig's avatar
Christian Würdig committed
906
		if (check_for_best && (! best || best->weight < tmp_chunk->weight))
907
908
909
910
911
912
913
914
915
916
917
918
			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!
 */
919
920
static inline void reject_coloring(struct list_head *nodes)
{
921
	co_mst_irn_t *n, *temp;
922
	DB((dbg, LEVEL_4, "\treject coloring for"));
923
	list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
924
		DB((dbg, LEVEL_4, " %+F", n->irn));
925
926
927
		assert(n->tmp_col >= 0);
		n->tmp_col = -1;
		list_del_init(&n->list);
928
	}
929
	DB((dbg, LEVEL_4, "\n"));
930
931
}

932
933
static inline void materialize_coloring(struct list_head *nodes)
{
934
935
936
937
938
939
940
941
942
	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);
	}
}

943
static inline void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed)
944
945
946
947
948
{
	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
949
	assert(bitset_is_set(node->adm_colors, col));
950
951
952
953
954

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

955
static inline int is_loose(co_mst_irn_t *node)
956
957
958
959
{
	return !node->fixed && node->tmp_col < 0;
}

960
961
962
/**
 * Determines the costs for each color if it would be assigned to node @p node.
 */
963
964
965
966
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;
967
	real_t coeff;
968
	int    i;
Christian Würdig's avatar
Christian Würdig committed
969

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

976
	for (i = 0; i < node->n_neighs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
977
978
979
980
981
		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];
982
983
		} else
			costs[col].cost = REAL(0.0);
984
985
	}