bechordal.c 27.1 KB
Newer Older
Sebastian Hack's avatar
Sebastian Hack committed
1
2
3
/**
 * Chordal register allocation.
 * @author Sebastian Hack
4
5
 * @date   8.12.2004
 * @cvs-id $Id$
Sebastian Hack's avatar
Sebastian Hack committed
6
7
8
 *
 * Copyright (C) Universitaet Karlsruhe
 * Released under the GPL
Sebastian Hack's avatar
Sebastian Hack committed
9
 */
Sebastian Hack's avatar
Sebastian Hack committed
10

Michael Beck's avatar
Michael Beck committed
11
12
13
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
Sebastian Hack's avatar
Sebastian Hack committed
14

15
16
17
18
19
20
21
22
#ifdef HAVE_MALLOC_H
#include <malloc.h>
#endif

#ifdef HAVE_ALLOCA_H
#include <alloca.h>
#endif

Sebastian Hack's avatar
Sebastian Hack committed
23
24
25
#include <ctype.h>

#include "obst.h"
26
#include "pset.h"
Sebastian Hack's avatar
Sebastian Hack committed
27
28
29
#include "list.h"
#include "bitset.h"
#include "iterator.h"
30
#include "bipartite.h"
31
#include "hungarian.h"
Sebastian Hack's avatar
Sebastian Hack committed
32
33

#include "irmode_t.h"
34
#include "irgraph_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
35
36
37
38
#include "irprintf_t.h"
#include "irgwalk.h"
#include "irdump.h"
#include "irdom.h"
39
#include "irtools.h"
40
#include "debug.h"
Michael Beck's avatar
Michael Beck committed
41
#include "xmalloc.h"
Sebastian Hack's avatar
Sebastian Hack committed
42
43
44
45
46

#include "beutil.h"
#include "besched.h"
#include "besched_t.h"
#include "belive_t.h"
47
#include "benode_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
48
#include "bearch.h"
Sebastian Hack's avatar
Sebastian Hack committed
49
#include "beirgmod.h"
Sebastian Hack's avatar
Sebastian Hack committed
50
#include "beifg.h"
51
#include "beinsn_t.h"
52
#include "bestatevent.h"
53
#include "beirg_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
54

55
56
57
#include "bechordal_t.h"
#include "bechordal_draw.h"

Daniel Grund's avatar
Daniel Grund committed
58
#define DBG_LEVEL SET_LEVEL_0
Daniel Grund's avatar
Daniel Grund committed
59
60
#define DBG_LEVEL_CHECK SET_LEVEL_0

61
62
#define NO_COLOR (-1)

Sebastian Hack's avatar
Sebastian Hack committed
63
#define DUMP_INTERVALS
Sebastian Hack's avatar
Sebastian Hack committed
64

Sebastian Hack's avatar
Sebastian Hack committed
65
66
typedef struct _be_chordal_alloc_env_t {
	be_chordal_env_t *chordal_env;
67

Sebastian Hack's avatar
Sebastian Hack committed
68
69
	pset *pre_colored;              /**< Set of precolored nodes. */
	bitset_t *live;				    /**< A liveness bitset. */
Sebastian Hack's avatar
Sebastian Hack committed
70
	bitset_t *tmp_colors;           /**< An auxiliary bitset which is as long as the number of colors in the class. */
Sebastian Hack's avatar
Sebastian Hack committed
71
72
73
	bitset_t *colors;			    /**< The color mask. */
	bitset_t *in_colors;            /**< Colors used by live in values. */
	int colors_n;                   /**< The number of colors. */
74
	DEBUG_ONLY(firm_dbg_module_t *constr_dbg;)  /**< Debug output for the constraint handler. */
Sebastian Hack's avatar
Sebastian Hack committed
75
} be_chordal_alloc_env_t;
76

77
78
79
80
81
#include "fourcc.h"

/* Make a fourcc for border checking. */
#define BORDER_FOURCC				FOURCC('B', 'O', 'R', 'D')

Matthias Braun's avatar
Matthias Braun committed
82
#if 0
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
static void check_border_list(struct list_head *head)
{
  border_t *x;
  list_for_each_entry(border_t, x, head, list) {
    assert(x->magic == BORDER_FOURCC);
  }
}

static void check_heads(be_chordal_env_t *env)
{
  pmap_entry *ent;
  for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
    /* ir_printf("checking border list of block %+F\n", ent->key); */
    check_border_list(ent->value);
  }
}
Matthias Braun's avatar
Matthias Braun committed
99
#endif
Sebastian Hack's avatar
Sebastian Hack committed
100

101
102
103
104
105
106
107
108
109
110
111
112
/**
 * Add an interval border to the list of a block's list
 * of interval border.
 * @note You always have to create the use before the def.
 * @param env The environment.
 * @param head The list head to enqueue the borders.
 * @param irn The node (value) the border belongs to.
 * @param pressure The pressure at this point in time.
 * @param step A time step for the border.
 * @param is_def Is the border a use or a def.
 * @return The created border.
 */
113
static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
114
115
			ir_node *irn, unsigned step, unsigned pressure,
			unsigned is_def, unsigned is_real)
Sebastian Hack's avatar
Sebastian Hack committed
116
{
117
118
119
120
121
122
123
124
125
	border_t *b;

	if(!is_def) {
		border_t *def;

		b = obstack_alloc(&env->obst, sizeof(*b));

		/* also allocate the def and tie it to the use. */
		def = obstack_alloc(&env->obst, sizeof(*def));
Sebastian Hack's avatar
Sebastian Hack committed
126
		memset(def, 0, sizeof(*def));
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
		b->other_end = def;
		def->other_end = b;

		/*
		 * Set the link field of the irn to the def.
		 * This strongly relies on the fact, that the use is always
		 * made before the def.
		 */
		set_irn_link(irn, def);

		b->magic = BORDER_FOURCC;
		def->magic = BORDER_FOURCC;
	}

	/*
	 * If the def is encountered, the use was made and so was the
	 * the def node (see the code above). It was placed into the
	 * link field of the irn, so we can get it there.
	 */
	else {
		b = get_irn_link(irn);

		assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
	}

Daniel Grund's avatar
Daniel Grund committed
152
	b->pressure = pressure;
Sebastian Hack's avatar
Sebastian Hack committed
153
	b->is_def = is_def;
154
	b->is_real = is_real;
Sebastian Hack's avatar
Sebastian Hack committed
155
156
157
	b->irn = irn;
	b->step = step;
	list_add_tail(&b->list, head);
Sebastian Hack's avatar
Sebastian Hack committed
158
	DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
159

160

Sebastian Hack's avatar
Sebastian Hack committed
161
162
163
	return b;
}

Sebastian Hack's avatar
Sebastian Hack committed
164
165
166
167
168
169
/**
 * Check, if an irn is of the register class currently under processing.
 * @param env The chordal environment.
 * @param irn The node.
 * @return 1, if the node is of that register class, 0 if not.
 */
170
171
static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
{
Sebastian Hack's avatar
Sebastian Hack committed
172
173
	return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
	// return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
174
175
}

176
177
#define has_limited_constr(req, irn) \
	(arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
178

Sebastian Hack's avatar
Sebastian Hack committed
179
180
static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
{
Sebastian Hack's avatar
Sebastian Hack committed
181
182
	bitset_t *tmp = alloc_env->tmp_colors;
	bitset_copy(tmp, colors);
183
	bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
Sebastian Hack's avatar
Sebastian Hack committed
184
	return bitset_next_clear(tmp, 0);
Sebastian Hack's avatar
Sebastian Hack committed
185
186
}

187
static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
188
{
Sebastian Hack's avatar
Sebastian Hack committed
189
	bitset_t *res = bs;
190

Sebastian Hack's avatar
Sebastian Hack committed
191
192
193
194
	if(!o1) {
		bitset_copy(bs, o2->regs);
		return bs;
	}
195

Sebastian Hack's avatar
Sebastian Hack committed
196
197
198
	if(!o2) {
		bitset_copy(bs, o1->regs);
		return bs;
199
	}
Sebastian Hack's avatar
Sebastian Hack committed
200
201
202
203
204
205
206
207
208
209
210

	assert(o1->req.cls == o2->req.cls);

	if(bitset_contains(o1->regs, o2->regs))
		bitset_copy(bs, o1->regs);
	else if(bitset_contains(o2->regs, o1->regs))
		bitset_copy(bs, o2->regs);
	else
		res = NULL;

	return res;
211
}
Sebastian Hack's avatar
Sebastian Hack committed
212

Sebastian Hack's avatar
Sebastian Hack committed
213
static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
214
215
216
{
	be_insn_env_t ie;

Sebastian Hack's avatar
Sebastian Hack committed
217
218
219
220
	ie.ignore_colors = env->ignore_colors;
	ie.aenv          = env->birg->main_env->arch_env;
	ie.obst          = &env->obst;
	ie.cls           = env->cls;
221
222
223
	return be_scan_insn(&ie, irn);
}

Sebastian Hack's avatar
Sebastian Hack committed
224
225
static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
{
226
227
228
229
	const arch_env_t *aenv = env->birg->main_env->arch_env;
	bitset_t *def_constr   = bitset_alloca(env->cls->n_regs);
	bitset_t *tmp          = bitset_alloca(env->cls->n_regs);
	ir_node *bl            = get_nodes_block(irn);
230
	be_lv_t *lv            = env->birg->lv;
231
232

	be_insn_t *insn;
233
	int i, j;
Sebastian Hack's avatar
Sebastian Hack committed
234

235
	for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
236
237
238
239
240
		ir_node *op = get_irn_n(irn, i);

		const arch_register_t *reg;
		arch_register_req_t req;

241
242
		if (arch_get_irn_reg_class(aenv, irn, i) == env->cls) {
			reg = arch_get_irn_register(aenv, op);
243

244
245
246
247
248
249
250
251
252
253
			if (reg && arch_register_type_is(reg, ignore)) {
				arch_get_register_req(aenv, &req, irn, i);

				if (arch_register_req_is(&req, limited)) {
					bitset_clear_all(tmp);
					req.limited(req.limited_env, tmp);

					if (! bitset_is_set(tmp, reg->index)) {
						ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op);
						be_stat_ev("constr_copy", 1);
254

255
256
257
258
						sched_add_before(irn, copy);
						set_irn_n(irn, i, copy);
						DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
					}
259
260
261
262
263
264
265
				}
			}
		}
	}

    insn = chordal_scan_insn(env, irn);

Sebastian Hack's avatar
Sebastian Hack committed
266
267
268
	if(!insn->has_constraints)
		goto end;

269
270
271
272
273
274
275
276
277
278
	/* insert copies for nodes that occur constrained more than once. */
	for(i = insn->use_start; i < insn->n_ops; ++i) {
		be_operand_t *op = &insn->ops[i];

		if(op->has_constraints) {
			for(j = i + 1; j < insn->n_ops; ++j) {
				be_operand_t *a_op = &insn->ops[j];

				if(a_op->carrier == op->carrier && a_op->has_constraints) {
					ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
279
					be_stat_ev("constr_copy", 1);
280
281
282
283
284
285
286
287
288

					sched_add_before(insn->irn, copy);
					set_irn_n(insn->irn, a_op->pos, copy);
					DBG((env->dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
				}
			}
		}
	}

289
290
291
292
293
294
295
296
297
298
299
	/* collect all registers occuring in out constraints. */
	for(i = 0; i < insn->use_start; ++i) {
		be_operand_t *op = &insn->ops[i];
		if(op->has_constraints)
			bitset_or(def_constr, op->regs);
	}

	/*
		insert copies for all constrained arguments living through the node
		and being constrained to a register which also occurs in out constraints.
	*/
Sebastian Hack's avatar
Sebastian Hack committed
300
301
	for(i = insn->use_start; i < insn->n_ops; ++i) {
		be_operand_t *op = &insn->ops[i];
302
303
304
305
306
307
308
309
310
311

		bitset_copy(tmp, op->regs);
		bitset_and(tmp, def_constr);

		/*
			Check, if
			1) the operand is constrained.
			2) lives through the node.
			3) is constrained to a register occuring in out constraints.
		*/
312
		if(op->has_constraints && values_interfere(lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) {
313
314
315
316
317
318
319
320
321
322
323
324
			/*
				only create the copy if the operand is no copy.
				this is necessary since the assure constraints phase inserts
				Copies and Keeps for operands which must be different from the results.
				Additional copies here would destroy this.
			*/
			if(!be_is_Copy(op->carrier)) {
				ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);

				sched_add_before(insn->irn, copy);
				set_irn_n(insn->irn, op->pos, copy);
				DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
325
				be_liveness_update(lv, op->carrier);
326
			}
Sebastian Hack's avatar
Sebastian Hack committed
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
		}
	}

end:
	obstack_free(&env->obst, insn);
	return insn->next_insn;
}

static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
{
	be_chordal_env_t *env = data;
	ir_node *irn;
	for(irn = sched_first(bl); !sched_is_end(irn);) {
		irn = prepare_constr_insn(env, irn);
	}
}

void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
	irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
}

348
static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
Sebastian Hack's avatar
Sebastian Hack committed
349
{
Sebastian Hack's avatar
Sebastian Hack committed
350
	const be_chordal_env_t *env = alloc_env->chordal_env;
Sebastian Hack's avatar
Sebastian Hack committed
351

Christian Würdig's avatar
Christian Würdig committed
352
353
354
355
	int n_uses   = be_insn_n_uses(insn);
	int n_defs   = be_insn_n_defs(insn);
	bitset_t *bs = bitset_alloca(env->cls->n_regs);
	int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
356
	be_lv_t *lv  = env->birg->lv;
Sebastian Hack's avatar
Sebastian Hack committed
357

Sebastian Hack's avatar
Sebastian Hack committed
358
	int i, j;
Sebastian Hack's avatar
Sebastian Hack committed
359

Sebastian Hack's avatar
Sebastian Hack committed
360
361
362
363
	/*
		For each out operand, try to find an in operand which can be assigned the
		same register as the out operand.
	*/
Christian Würdig's avatar
Christian Würdig committed
364
365
366
	for (j = 0; j < insn->use_start; ++j) {
		int smallest         = -1;
		int smallest_n_regs  = 2 * env->cls->n_regs + 1;
367
		be_operand_t *out_op = &insn->ops[j];
Sebastian Hack's avatar
Sebastian Hack committed
368
369
370

		/* Try to find an in operand which has ... */
		for(i = insn->use_start; i < insn->n_ops; ++i) {
Christian Würdig's avatar
Christian Würdig committed
371
			int n_total;
372
			const be_operand_t *op = &insn->ops[i];
Sebastian Hack's avatar
Sebastian Hack committed
373

374
			if (! values_interfere(lv, op->irn, op->carrier) && ! op->partner) {
Christian Würdig's avatar
Christian Würdig committed
375
376
377
378
379
380
381
382
383
				bitset_clear_all(bs);
				bitset_copy(bs, op->regs);
				bitset_and(bs, out_op->regs);
				n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);

				if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
					smallest = i;
					smallest_n_regs = n_total;
				}
Sebastian Hack's avatar
Sebastian Hack committed
384
			}
Sebastian Hack's avatar
Sebastian Hack committed
385
		}
Sebastian Hack's avatar
Sebastian Hack committed
386

Christian Würdig's avatar
Christian Würdig committed
387
388
389
390
		if (smallest >= 0) {
			be_operand_t *partner = &insn->ops[smallest];
			out_op->partner  = partner;
			partner->partner = out_op;
Sebastian Hack's avatar
Sebastian Hack committed
391
392
393
394
		}
	}
}

395

396
static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
Sebastian Hack's avatar
Sebastian Hack committed
397
398
399
{
	be_chordal_env_t *env       = alloc_env->chordal_env;
	const arch_env_t *aenv      = env->birg->main_env->arch_env;
400
	be_insn_t *insn             = *the_insn;
Sebastian Hack's avatar
Sebastian Hack committed
401
402
403
404
405
	ir_node *bl                 = get_nodes_block(insn->irn);
	ir_node *copy               = NULL;
	ir_node *perm               = NULL;
	bitset_t *out_constr        = bitset_alloca(env->cls->n_regs);
	bitset_t *bs                = bitset_alloca(env->cls->n_regs);
406
	be_lv_t *lv                 = env->birg->lv;
407
	DEBUG_ONLY(firm_dbg_module_t *dbg      = alloc_env->constr_dbg;)
Sebastian Hack's avatar
Sebastian Hack committed
408

Sebastian Hack's avatar
Sebastian Hack committed
409
410
	int i;

Sebastian Hack's avatar
Sebastian Hack committed
411
412
413
414
415
416
417
418
	assert(insn->has_constraints && "only do this for constrained nodes");

	/*
		Collect all registers that occur in output constraints.
		This is necessary, since if the insn has one of these as an input constraint
		and the corresponding operand interferes with the insn, the operand must
		be copied.
	*/
Sebastian Hack's avatar
Sebastian Hack committed
419
	for(i = 0; i < insn->use_start; ++i) {
420
		be_operand_t *op = &insn->ops[i];
Sebastian Hack's avatar
Sebastian Hack committed
421
422
		if(op->has_constraints)
			bitset_or(out_constr, op->regs);
Sebastian Hack's avatar
Sebastian Hack committed
423
424
	}

Matthias Braun's avatar
Matthias Braun committed
425
426
427
	(void) bl;
	(void) copy;
	(void) bs;
428
	DEBUG_ONLY((void) dbg;)
Sebastian Hack's avatar
Sebastian Hack committed
429

Sebastian Hack's avatar
Sebastian Hack committed
430
431
432
433
	/*
		Make the Perm, recompute liveness and re-scan the insn since the
		in operands are now the Projs of the Perm.
	*/
434
	perm = insert_Perm_after(aenv, lv, env->cls, env->birg->dom_front, sched_prev(insn->irn));
Sebastian Hack's avatar
Sebastian Hack committed
435
436
437
438
439

	/* Registers are propagated by insert_Perm_after(). Clean them here! */
	if(perm) {
		const ir_edge_t *edge;

Sebastian Hack's avatar
Sebastian Hack committed
440
		be_stat_ev("constr_perm", get_irn_arity(perm));
Sebastian Hack's avatar
Sebastian Hack committed
441
442
443
444
445
446
447
448
449
450
		foreach_out_edge(perm, edge) {
			ir_node *proj = get_edge_src_irn(edge);
			arch_set_irn_register(aenv, proj, NULL);
		}

		/*
			We also have to re-build the insn since the input operands are now the Projs of
			the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
			the live sets may change.
		*/
451
		// be_liveness_recompute(lv);
Sebastian Hack's avatar
Sebastian Hack committed
452
		obstack_free(&env->obst, insn);
Sebastian Hack's avatar
Sebastian Hack committed
453
		*the_insn = insn = chordal_scan_insn(env, insn->irn);
Sebastian Hack's avatar
Sebastian Hack committed
454
455
456
457
458
459

		/*
			Copy the input constraints of the insn to the Perm as output
			constraints. Succeeding phases (coalescing will need that).
		*/
		for(i = insn->use_start; i < insn->n_ops; ++i) {
460
			be_operand_t *op = &insn->ops[i];
Christian Würdig's avatar
Christian Würdig committed
461
			ir_node *proj = op->carrier;
Sebastian Hack's avatar
Sebastian Hack committed
462
463
464
465
			/*
				Note that the predecessor must not be a Proj of the Perm,
				since ignore-nodes are not Perm'ed.
			*/
Christian Würdig's avatar
Christian Würdig committed
466
467
			if(op->has_constraints &&  is_Proj(proj) && get_Proj_pred(proj) == perm) {
				be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
Sebastian Hack's avatar
Sebastian Hack committed
468
			}
Sebastian Hack's avatar
Sebastian Hack committed
469
470
471
		}
	}

Sebastian Hack's avatar
Sebastian Hack committed
472
	return perm;
Sebastian Hack's avatar
Sebastian Hack committed
473
}
474

475
static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
476
477
478
{
	be_chordal_env_t *env  = alloc_env->chordal_env;
	void *base             = obstack_base(&env->obst);
Sebastian Hack's avatar
Sebastian Hack committed
479
	be_insn_t *insn        = chordal_scan_insn(env, irn);
480
	ir_node *res           = insn->next_insn;
481
	int be_silent          = *silent;
482
	be_lv_t *lv            = env->birg->lv;
483

Sebastian Hack's avatar
Sebastian Hack committed
484
485
486
487
488
489
	if(insn->pre_colored) {
		int i;
		for(i = 0; i < insn->use_start; ++i)
			pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
	}

490
491
492
493
494
495
496
497
498
499
500
	/*
		If the current node is a barrier toggle the silent flag.
		If we are in the start block, we are ought to be silent at the beginning,
		so the toggling activates the constraint handling but skips the barrier.
		If we are in the end block we handle the in requirements of the barrier
		and set the rest to silent.
	*/
	if(be_is_Barrier(irn))
		*silent = !*silent;

	if(be_silent)
501
502
		goto end;

Sebastian Hack's avatar
Sebastian Hack committed
503
504
505
506
	/*
		Perms inserted before the constraint handling phase are considered to be
		correctly precolored. These Perms arise during the ABI handling phase.
	*/
507
	if(insn->has_constraints) {
Sebastian Hack's avatar
Sebastian Hack committed
508
		const arch_env_t *aenv = env->birg->main_env->arch_env;
509
510
511
		int n_regs             = env->cls->n_regs;
		bitset_t *bs           = bitset_alloca(n_regs);
		ir_node **alloc_nodes  = alloca(n_regs * sizeof(alloc_nodes[0]));
512
513
		hungarian_problem_t *bp= hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
//		bipartite_t *bp        = bipartite_new(n_regs, n_regs);
514
515
		int *assignment        = alloca(n_regs * sizeof(assignment[0]));
		pmap *partners         = pmap_create();
516
		DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
517
518
519
520

		int i, n_alloc;
		long col;
		const ir_edge_t *edge;
521
		ir_node *perm = NULL;
522
		int match_res, cost;
523

524
		/*
Sebastian Hack's avatar
Sebastian Hack committed
525
526
527
528
529
			prepare the constraint handling of this node.
			Perms are constructed and Copies are created for constrained values
			interfering with the instruction.
		*/
		perm = pre_process_constraints(alloc_env, &insn);
530

Sebastian Hack's avatar
Sebastian Hack committed
531
532
		/* find suitable in operands to the out operands of the node. */
		pair_up_operands(alloc_env, insn);
533

Sebastian Hack's avatar
Sebastian Hack committed
534
535
536
537
		/*
			look at the in/out operands and add each operand (and its possible partner)
			to a bipartite graph (left: nodes with partners, right: admissible colors).
		*/
538
		for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
539
			be_operand_t *op = &insn->ops[i];
Sebastian Hack's avatar
Sebastian Hack committed
540
541
542
543
544
545
546
547

			/*
				If the operand has no partner or the partner has not been marked
				for allocation, determine the admissible registers and mark it
				for allocation by associating the node and its partner with the
				set of admissible registers via a bipartite graph.
			*/
			if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
548

549
550
				pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
				alloc_nodes[n_alloc] = op->carrier;
551

Sebastian Hack's avatar
Sebastian Hack committed
552
				DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
553

554
 				bitset_clear_all(bs);
Sebastian Hack's avatar
Sebastian Hack committed
555
				get_decisive_partner_regs(bs, op, op->partner);
556

Sebastian Hack's avatar
Sebastian Hack committed
557
				DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
558

559
				bitset_foreach(bs, col)
560
561
					hungarian_add(bp, n_alloc, col, 1);
//					bipartite_add(bp, n_alloc, col);
562

563
				n_alloc++;
564
			}
565
566
		}

Sebastian Hack's avatar
Sebastian Hack committed
567
		/*
568
			Put all nodes which live through the constrained instruction also to the
Sebastian Hack's avatar
Sebastian Hack committed
569
570
			allocation bipartite graph. They are considered unconstrained.
		*/
571
572
573
		if(perm) {
			foreach_out_edge(perm, edge) {
				ir_node *proj = get_edge_src_irn(edge);
574

575
				assert(is_Proj(proj));
576

577
				if(values_interfere(lv, proj, irn) && !pmap_contains(partners, proj)) {
578
579
580
581
582
					assert(n_alloc < n_regs);
					alloc_nodes[n_alloc] = proj;
					pmap_insert(partners, proj, NULL);

					bitset_clear_all(bs);
Sebastian Hack's avatar
Sebastian Hack committed
583
					arch_put_non_ignore_regs(aenv, env->cls, bs);
Sebastian Hack's avatar
Sebastian Hack committed
584
					bitset_andnot(bs, env->ignore_colors);
585
					bitset_foreach(bs, col)
586
587
						hungarian_add(bp, n_alloc, col, 1);
//						bipartite_add(bp, n_alloc, col);
588
589
590
591

					n_alloc++;
				}
			}
Sebastian Hack's avatar
Sebastian Hack committed
592
		}
593

Sebastian Hack's avatar
Sebastian Hack committed
594
		/* Compute a valid register allocation. */
595
596
597
598
		hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
		match_res = hungarian_solve(bp, assignment, &cost, 1);
		assert(match_res == 0 && "matching failed");
		//bipartite_matching(bp, assignment);
599

600
		/* Assign colors obtained from the matching. */
601
		for(i = 0; i < n_alloc; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
602
			const arch_register_t *reg;
Sebastian Hack's avatar
Sebastian Hack committed
603
604
			ir_node *nodes[2];
			int j;
Sebastian Hack's avatar
Sebastian Hack committed
605
606
607

			assert(assignment[i] >= 0 && "there must have been a register assigned");
			reg = arch_register_for_index(env->cls, assignment[i]);
608
609
610
611
612
613
614
615
616

			nodes[0] = alloc_nodes[i];
			nodes[1] = pmap_get(partners, alloc_nodes[i]);

			for(j = 0; j < 2; ++j) {
				if(!nodes[j])
					continue;

				arch_set_irn_register(aenv, nodes[j], reg);
617
				(void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
618
619
620
621
622
				DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
			}
		}


623
		/* Allocate the non-constrained Projs of the Perm. */
624
		if(perm) {
625

626
			bitset_clear_all(bs);
627
628

			/* Put the colors of all Projs in a bitset. */
629
630
631
632
633
634
635
636
			foreach_out_edge(perm, edge) {
				ir_node *proj              = get_edge_src_irn(edge);
				const arch_register_t *reg = arch_get_irn_register(aenv, proj);

				if(reg != NULL)
					bitset_set(bs, reg->index);
			}

637
			/* Assign the not yet assigned Projs of the Perm a suitable color. */
638
639
640
			foreach_out_edge(perm, edge) {
				ir_node *proj              = get_edge_src_irn(edge);
				const arch_register_t *reg = arch_get_irn_register(aenv, proj);
Sebastian Hack's avatar
Sebastian Hack committed
641

642
				DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
Sebastian Hack's avatar
Sebastian Hack committed
643

644
				if(reg == NULL) {
Sebastian Hack's avatar
Sebastian Hack committed
645
					col = get_next_free_reg(alloc_env, bs);
646
647
648
649
650
651
652
653
654
					reg = arch_register_for_index(env->cls, col);
					bitset_set(bs, reg->index);
					arch_set_irn_register(aenv, proj, reg);
					pset_insert_ptr(alloc_env->pre_colored, proj);
					DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
				}
			}
		}

655
656
		//bipartite_free(bp);
		hungarian_free(bp);
657
658
659
		pmap_destroy(partners);
	}

660
end:
661
662
	obstack_free(&env->obst, base);
	return res;
663
664
665
666
}

/**
 * Handle constraint nodes in each basic block.
667
 * handle_constraints() inserts Perm nodes which perm
668
669
 * over all values live at the constrained node right in front
 * of the constrained node. These Perms signal a constrained node.
670
 * For further comments, refer to handle_constraints().
671
672
673
674
 */
static void constraints(ir_node *bl, void *data)
{
	be_chordal_alloc_env_t *env = data;
675
676
677
678
679
680
681

	/*
		Start silent in the start block.
		The silence remains until the first barrier is seen.
		Each other block is begun loud.
	*/
	int silent                  = bl == get_irg_start_block(get_irn_irg(bl));
682
683
	ir_node *irn;

684
685
686
687
688
	/*
		If the block is the start block search the barrier and
		start handling constraints from there.
	*/

689
	for(irn = sched_first(bl); !sched_is_end(irn);) {
690
		irn = handle_constraints(env, irn, &silent);
691
	}
692
693
}

694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
/**
 * Annotate the register pressure to the nodes and compute
 * the liveness intervals.
 * @param block The block to do it for.
 * @param env_ptr The environment.
 */
static void pressure(ir_node *block, void *env_ptr)
{
/* Convenience macro for a def */
#define border_def(irn, step, real) \
	border_add(env, head, irn, step, pressure--, 1, real)

/* Convenience macro for a use */
#define border_use(irn, step, real) \
	border_add(env, head, irn, step, ++pressure, 0, real)

Sebastian Hack's avatar
Sebastian Hack committed
710
711
712
	be_chordal_alloc_env_t *alloc_env = env_ptr;
	be_chordal_env_t *env             = alloc_env->chordal_env;
	bitset_t *live                    = alloc_env->live;
713
	ir_node *irn;
714
	be_lv_t *lv                       = env->birg->lv;
715
	DEBUG_ONLY(firm_dbg_module_t *dbg            = env->dbg;)
716
717
718
719
720

	int i, n;
	unsigned step = 0;
	unsigned pressure = 0;
	struct list_head *head;
721
722
	pset *live_in  = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
	pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
723

724
	DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
725
726
727
	bitset_clear_all(live);

	/* Set up the border list in the block info */
728
	head = obstack_alloc(&env->obst, sizeof(*head));
729
	INIT_LIST_HEAD(head);
Sebastian Hack's avatar
Sebastian Hack committed
730
	assert(pmap_get(env->border_heads, block) == NULL);
731
	pmap_insert(env->border_heads, block, head);
732
733
734

	/*
	 * Make final uses of all values live out of the block.
Michael Beck's avatar
Michael Beck committed
735
	 * They are necessary to build up real intervals.
736
	 */
737
	foreach_pset(live_end, irn) {
Sebastian Hack's avatar
Sebastian Hack committed
738
		if(has_reg_class(env, irn)) {
Sebastian Hack's avatar
Sebastian Hack committed
739
740
			DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
			bitset_set(live, get_irn_idx(irn));
741
			border_use(irn, step, 0);
Sebastian Hack's avatar
Sebastian Hack committed
742
		}
743
744
745
746
747
748
749
750
	}
	++step;

	/*
	 * Determine the last uses of a value inside the block, since they are
	 * relevant for the interval borders.
	 */
	sched_foreach_reverse(block, irn) {
751
		DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
Sebastian Hack's avatar
Sebastian Hack committed
752
		DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
753

754
755
756
757
		/*
		 * If the node defines some value, which can put into a
		 * register of the current class, make a border for it.
		 */
758
		if(has_reg_class(env, irn)) {
Sebastian Hack's avatar
Sebastian Hack committed
759
			int nr = get_irn_idx(irn);
760
761
762
763
764
765
766
767
768
769
770
771

			bitset_clear(live, nr);
			border_def(irn, step, 1);
		}

		/*
		 * If the node is no phi node we can examine the uses.
		 */
		if(!is_Phi(irn)) {
			for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
				ir_node *op = get_irn_n(irn, i);

772
				if(has_reg_class(env, op)) {
Sebastian Hack's avatar
Sebastian Hack committed
773
774
					int nr = get_irn_idx(op);
					const char *msg = "-";
775
776
777
778

					if(!bitset_is_set(live, nr)) {
						border_use(op, step, 1);
						bitset_set(live, nr);
Sebastian Hack's avatar
Sebastian Hack committed
779
						msg = "X";
780
					}
Sebastian Hack's avatar
Sebastian Hack committed
781
782

					DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
783
784
785
786
787
788
789
790
791
				}
			}
		}
		++step;
	}

	/*
	 * Add initial defs for all values live in.
	 */
792
	foreach_pset(live_in, irn) {
793
		if(has_reg_class(env, irn)) {
794
795

			/* Mark the value live in. */
Sebastian Hack's avatar
Sebastian Hack committed
796
			bitset_set(live, get_irn_idx(irn));
797
798
799
800
801

			/* Add the def */
			border_def(irn, step, 0);
		}
	}
802

803
804
	del_pset(live_in);
	del_pset(live_end);
805
806
807
808
}

static void assign(ir_node *block, void *env_ptr)
{
Sebastian Hack's avatar
Sebastian Hack committed
809
810
811
812
813
	be_chordal_alloc_env_t *alloc_env = env_ptr;
	be_chordal_env_t *env       = alloc_env->chordal_env;
	bitset_t *live              = alloc_env->live;
	bitset_t *colors            = alloc_env->colors;
	bitset_t *in_colors         = alloc_env->in_colors;
Sebastian Hack's avatar
Sebastian Hack committed
814
	const arch_env_t *arch_env  = env->birg->main_env->arch_env;
Sebastian Hack's avatar
Sebastian Hack committed
815
	struct list_head *head      = get_block_border_head(env, block);
816
817
	be_lv_t *lv                 = env->birg->lv;
	pset *live_in               = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
818
819
820

	const ir_node *irn;
	border_t *b;
Sebastian Hack's avatar
Sebastian Hack committed
821
	DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
822

Sebastian Hack's avatar
Sebastian Hack committed
823
	bitset_clear_all(colors);
824
825
826
	bitset_clear_all(live);
	bitset_clear_all(in_colors);

827
	DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
828
829
	DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
	list_for_each_entry(border_t, b, head, list) {
830
		DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
Sebastian Hack's avatar
Sebastian Hack committed
831
					b->irn, get_irn_idx(b->irn)));
832
833
834
835
836
837
838
	}

	/*
	 * Add initial defs for all values live in.
	 * Since their colors have already been assigned (The dominators were
	 * allocated before), we have to mark their colors as used also.
	 */
839
	foreach_pset(live_in, irn) {
840
		if(has_reg_class(env, irn)) {
Sebastian Hack's avatar
Sebastian Hack committed
841
			const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
Daniel Grund's avatar
Daniel Grund committed
842
			int col;
Sebastian Hack's avatar
Sebastian Hack committed
843

Daniel Grund's avatar
Daniel Grund committed
844
			assert(reg && "Node must have been assigned a register");
Sebastian Hack's avatar
Sebastian Hack committed
845
			col = arch_register_get_index(reg);
846

Sebastian Hack's avatar
Sebastian Hack committed
847
848
			DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));

849
850
851
852
853
			/* Mark the color of the live in value as used. */
			bitset_set(colors, col);
			bitset_set(in_colors, col);

			/* Mark the value live in. */
Sebastian Hack's avatar
Sebastian Hack committed
854
			bitset_set(live, get_irn_idx(irn));
855
856
857
858
		}
	}

	/*
Sebastian Hack's avatar
Sebastian Hack committed
859
860
	 * Mind that the sequence
	 * of defs from back to front defines a perfect
861
862
863
864
	 * elimination order. So, coloring the definitions from first to last
	 * will work.
	 */
	list_for_each_entry_reverse(border_t, b, head, list) {
Sebastian Hack's avatar
Sebastian Hack committed
865
		ir_node *irn = b->irn;
Sebastian Hack's avatar
Sebastian Hack committed
866
867
		int nr       = get_irn_idx(irn);
		int ignore   = arch_irn_is(arch_env, irn, ignore);
868
869
870
871
872

		/*
		 * Assign a color, if it is a local def. Global defs already have a
		 * color.
		 */
873
		if(b->is_def && !be_is_live_in(lv, block, irn)) {
Daniel Grund's avatar
Daniel Grund committed
874
			const arch_register_t *reg;
875
876
			int col = NO_COLOR;

Sebastian Hack's avatar
Sebastian Hack committed
877
			if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
878
879
880
881
				reg = arch_get_irn_register(arch_env, irn);
				col = reg->index;
				assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
			}
882

883
			else {
Sebastian Hack's avatar
Sebastian Hack committed
884
				col = get_next_free_reg(alloc_env, colors);
885
886
				reg = arch_register_for_index(env->cls, col);
				assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
887
				assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
888
			}
889
890

			bitset_set(colors, col);
Sebastian Hack's avatar
Sebastian Hack committed
891
			arch_set_irn_register(arch_env, irn, reg);
892

Sebastian Hack's avatar
Sebastian Hack committed
893
			DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
894
895
896

			assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
			bitset_set(live, nr);
897
898
899
900
		}

		/* Clear the color upon a use. */
		else if(!b->is_def) {
Sebastian Hack's avatar
Sebastian Hack committed
901
			const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
Sebastian Hack's avatar
Sebastian Hack committed
902
903
			int col;

Daniel Grund's avatar
Daniel Grund committed
904
			assert(reg && "Register must have been assigned");
905

Daniel Grund's avatar
Daniel Grund committed
906
			col = arch_register_get_index(reg);
907
908
909
910
911
912
913
			assert(bitset_is_set(live, nr) && "Cannot have a non live use");

			bitset_clear(colors, col);
			bitset_clear(live, nr);
		}
	}

Daniel Grund's avatar
Daniel Grund committed
914
	del_pset(live_in);
915
916
}

Sebastian Hack's avatar
Sebastian Hack committed
917
void be_ra_chordal_color(be_chordal_env_t *chordal_env)
918
{
Sebastian Hack's avatar
Sebastian Hack committed
919
920
	be_chordal_alloc_env_t env;
	char buf[256];
921
	be_irg_t *birg = chordal_env->birg;
Sebastian Hack's avatar
Sebastian Hack committed
922

Sebastian Hack's avatar
Sebastian Hack committed
923
924
	int colors_n          = arch_register_class_n_regs(chordal_env->cls);
	ir_graph *irg         = chordal_env->irg;
Sebastian Hack's avatar
Sebastian Hack committed
925
926


927
928
	be_assure_dom_front(birg);
	be_assure_liveness(birg);
Michael Beck's avatar
Michael Beck committed
929
	assure_doms(irg);
Sebastian Hack's avatar
Sebastian Hack committed
930

931
932
	env.chordal_env   = chordal_env;
	env.colors_n      = colors_n;
Sebastian Hack's avatar
Sebastian Hack committed
933
934
935
	env.colors        = bitset_alloca(colors_n);
	env.tmp_colors    = bitset_alloca(colors_n);
	env.in_colors     = bitset_alloca(colors_n);
936
	env.pre_colored   = pset_new_ptr_default();
937
	FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
Sebastian Hack's avatar
Sebastian Hack committed
938

939

940
941
	/* Handle register targeting constraints */
	dom_tree_walk_irg(irg, constraints, NULL, &env);
Sebastian Hack's avatar
Sebastian Hack committed
942

Sebastian Hack's avatar
Sebastian Hack committed
943
	if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
944
		snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
Christian Würdig's avatar
Christian Würdig committed
945
		be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
946
947
	}

Sebastian Hack's avatar
Sebastian Hack committed
948
	env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
949

950
	/* First, determine the pressure */
Sebastian Hack's avatar
Sebastian Hack committed
951
	dom_tree_walk_irg(irg, pressure, NULL, &env);
952
953

	/* Assign the colors */
Sebastian Hack's avatar
Sebastian Hack committed
954
	dom_tree_walk_irg(irg, assign, NULL, &env);
955

Sebastian Hack's avatar
Sebastian Hack committed
956
	if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
957
		plotter_t *plotter;
Sebastian Hack's avatar
Sebastian Hack committed
958
		ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
959
960
961
		plotter = new_plotter_ps(buf);
		draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
		plotter_free(plotter);
962
	}
Sebastian Hack's avatar
Sebastian Hack committed
963

Sebastian Hack's avatar
Sebastian Hack committed
964
	bitset_free(env.live);
965
	del_pset(env.pre_colored);
Sebastian Hack's avatar
Sebastian Hack committed
966
}