becopyheur2.c 34.2 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
/**
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
31
32
33
#endif

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

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

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

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

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

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

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

Matthias Braun's avatar
Matthias Braun committed
64
65
66
67
static unsigned dump_flags      = 0;
static int      subtree_iter    = 4;
static int      max_depth       = 20;
static double   constr_factor   = 0.9;
Sebastian Hack's avatar
Sebastian Hack committed
68
69
70
71

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

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

static const lc_opt_table_entry_t options[] = {
83
84
	LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud",                                         &dump_var),
	LC_OPT_ENT_INT      ("iter", "iterations for subtree nodes",                           &subtree_iter),
Sebastian Hack's avatar
Sebastian Hack committed
85
	LC_OPT_ENT_DBL      ("cf",   "factor of constraint importance (between 0.0 and 1.0)",  &constr_factor),
86
	LC_OPT_ENT_INT      ("max",  "maximum recursion depth",                                &max_depth),
87
	LC_OPT_ENT_NULL
Sebastian Hack's avatar
Sebastian Hack committed
88
89
};

90
void be_init_copyheur2(void)
Sebastian Hack's avatar
Sebastian Hack committed
91
{
92
93
94
95
96
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
	lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
	lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");

Sebastian Hack's avatar
Sebastian Hack committed
97
98
	lc_opt_add_table(co2_grp, options);
}
99
100

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

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

*/

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

static be_ifg_dump_dot_cb_t ifg_dot_cb;
114

115
116
typedef unsigned col_t;

Sebastian Hack's avatar
Sebastian Hack committed
117
118
119
120
121
122
123
124
typedef struct _co2_irn_t       co2_irn_t;
typedef struct _co2_cloud_t     co2_cloud_t;
typedef struct _co2_cloud_irn_t co2_cloud_irn_t;

typedef struct {
	col_t col;
	int costs;
} col_cost_pair_t;
125
126

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

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

struct _co2_cloud_irn_t {
	struct _co2_irn_t  inh;
	co2_cloud_t       *cloud;
	int                visited;
	int                index;
	co2_cloud_irn_t   *mst_parent;
	int                mst_costs;
	int                mst_n_childs;
	co2_cloud_irn_t  **mst_childs;
	int               *col_costs;
	int                costs;
	int               *fronts;
163
	int               *color_badness;
Sebastian Hack's avatar
Sebastian Hack committed
164
165
166
	col_cost_pair_t   *tmp_coloring;
	struct list_head   cloud_list;
	struct list_head   mst_list;
167
168
169
};

struct _co2_cloud_t {
Sebastian Hack's avatar
Sebastian Hack committed
170
171
172
173
174
175
176
	co2_t            *env;
	struct obstack    obst;
	int               costs;
	int               mst_costs;
	int               inevit;
	int               best_costs;
	int               n_memb;
Sebastian Hack's avatar
Sebastian Hack committed
177
	int               n_constr;
Sebastian Hack's avatar
Sebastian Hack committed
178
179
	int               max_degree;
	int			      ticks;
Sebastian Hack's avatar
Sebastian Hack committed
180
	double            freedom;
Sebastian Hack's avatar
Sebastian Hack committed
181
182
183
184
185
	co2_cloud_irn_t  *master;
	co2_cloud_irn_t  *mst_root;
	co2_cloud_irn_t **seq;
	struct list_head  members_head;
	struct list_head  list;
186
187
};

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

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

Sebastian Hack's avatar
Sebastian Hack committed
195
196
#define get_co2_irn(co2, irn)         ((co2_irn_t *)       phase_get_or_set_irn_data(&co2->ph, irn))
#define get_co2_cloud_irn(co2, irn)   ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
197

Michael Beck's avatar
Michael Beck committed
198
static void *co2_irn_init(ir_phase *ph, ir_node *irn, void *data)
199
{
Sebastian Hack's avatar
Sebastian Hack committed
200
201
202
203
	co2_t *env         = (co2_t *) ph;
	affinity_node_t *a = get_affinity_info(env->co, irn);
	size_t size        = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
	co2_irn_t *ci      = data ? data : phase_alloc(ph, size);
204

Sebastian Hack's avatar
Sebastian Hack committed
205
	memset(ci, 0, size);
206
207
208
209
	INIT_LIST_HEAD(&ci->changed_list);
	ci->touched_next = env->touched;
	ci->orig_col     = get_irn_col(env->co, irn);
	env->touched     = ci;
Sebastian Hack's avatar
Sebastian Hack committed
210
211
	ci->irn          = irn;
	ci->aff          = a;
212

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

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

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

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

233
234
235
236
237
238
239
240
/**
 * An order on color/costs pairs.
 * If the costs are equal, we use the color as a kind of normalization.
 */
static int col_cost_pair_lt(const void *a, const void *b)
{
	const col_cost_pair_t *p = a;
	const col_cost_pair_t *q = b;
241
242
	int c = p->costs;
	int d = q->costs;
243
	return QSORT_CMP(c, d);
244
245
}

246
247
248
249
250
251
252
int cmp_edges(const void *a, const void *b)
{
	const edge_t *p = a;
	const edge_t *q = b;
	return QSORT_CMP(q->costs, p->costs);
}

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

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

265
static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
266
{
Matthias Braun's avatar
Matthias Braun committed
267
268
	if(ci->adm_cache == NULL) {
		const arch_register_req_t *req;
269
		ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
Matthias Braun's avatar
Matthias Braun committed
270
271
272
273
274
275
276
277
278
279
		req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));

		if(arch_register_req_is(req, limited)) {
			int i, n;

			n = env->n_regs;
			for(i = 0; i < n; ++i) {
				if(rbitset_is_set(req->limited, i))
					bitset_set(ci->adm_cache, i);
			}
Sebastian Hack's avatar
Sebastian Hack committed
280
			ci->is_constrained = 1;
Matthias Braun's avatar
Matthias Braun committed
281
		} else {
282
283
284
			bitset_copy(ci->adm_cache, env->ignore_regs);
			bitset_flip_all(ci->adm_cache);
		}
285
286
	}

287
288
289
	return ci->adm_cache;
}

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

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

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

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

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

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

Matthias Braun's avatar
Matthias Braun committed
320
		n_constr = rbitset_popcnt(req->limited, n_regs);
321
322
323
		for (i = 0; i < n_regs; ++i) {
			if (rbitset_is_set(req->limited, i)) {
				col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
Matthias Braun's avatar
Matthias Braun committed
324
			}
325
		}
326
327
328
329
330
331
332
333
334
335
336
337
338
	}
}

/**
 * Determine costs which shall indicate how cheap/expensive it is to try
 * to assign a node some color.
 * The costs are computed for all colors. INT_MAX means that it is impossible
 * to give the node that specific color.
 *
 * @param env       The co2 this pointer.
 * @param irn       The node.
 * @param col_costs An array of colors x costs where the costs are written to.
 */
339
static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
340
{
341
	ir_node *irn       = ci->irn;
342
343
344
	be_ifg_t *ifg      = env->co->cenv->ifg;
	int n_regs         = env->co->cls->n_regs;
	bitset_t *forb     = bitset_alloca(n_regs);
345
	affinity_node_t *a = ci->aff;
346
347
348
349
350
351

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

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

	for(i = 0; i < n_regs; ++i) {
		col_costs[i].col   = i;
		col_costs[i].costs = 0;
	}

	if(a) {
		neighb_t *n;

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

			incur_constraint_costs(env, n->irn, col_costs, -n->costs);
		}
	}

	it = be_ifg_neighbours_iter_alloca(ifg);
	be_ifg_foreach_neighbour(ifg, it, irn, pos) {
		col_t col = get_col(env, pos);
377
378
379
		if(color_is_fix(env, pos)) {
			col_costs[col].costs  = INT_MAX;
		}
380
381
		else {
			incur_constraint_costs(env, pos, col_costs, INT_MAX);
Sebastian Hack's avatar
Sebastian Hack committed
382
			col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
383
384
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
385
	be_ifg_neighbours_break(ifg, it);
386
387

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

}

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

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

404
	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
429
430
static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);

static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
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
448
449
450
	for(i = 0; i < n_regs; ++i) {
		col_t tgt_col  = col_list[i].col;
		unsigned costs = col_list[i].costs;
		int neigh_ok   = 1;

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

Sebastian Hack's avatar
Sebastian Hack committed
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
515
516
517
518
519
520
			list_splice(&changed, parent_changed);
			res = 1;
			break;
		}

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

	return res;
}

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

Sebastian Hack's avatar
Sebastian Hack committed
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, 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
634
635
636
637
638
639
	int n_regs     = env->n_regs;
	be_ifg_t *ifg  = env->co->cenv->ifg;
	bitset_t *bs   = bitset_alloca(n_regs);

	bitset_pos_t elm;
	ir_node *irn;
	void *it;

	admissible_colors(env, &ci->inh, bs);
	bitset_flip_all(bs);
	bitset_foreach(bs, elm)
Sebastian Hack's avatar
Sebastian Hack committed
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
705
706
707
708
{
	co2_t *env           = ci->cloud->env;
	col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
	int is_root          = ci->mst_parent == ci;
	col_t parent_col     = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
	int min_badness      = INT_MAX;
	int best_col_costs   = INT_MAX;
	int best_col         = -1;
Sebastian Hack's avatar
Sebastian Hack committed
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
{
Sebastian Hack's avatar
Sebastian Hack committed
865
866
867
	ir_node *irn = ci->inh.irn;
	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;
Michael Beck's avatar
Michael Beck committed
895
	int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
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
	memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));

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

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

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

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

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

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