bespillslots.c 17.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Christian Würdig's avatar
Christian Würdig committed
6
7
8
9
10
/**
 * @file
 * @brief       Spillslot coalescer.
 * @author      Matthias Braun
 * @date        26.07.2006
Matthias Braun's avatar
Matthias Braun committed
11
12
13
 */
#include <stdlib.h>

Matthias Braun's avatar
Matthias Braun committed
14
#include "util.h"
Matthias Braun's avatar
Matthias Braun committed
15
#include "set.h"
Christian Würdig's avatar
Christian Würdig committed
16
#include "array.h"
Matthias Braun's avatar
Matthias Braun committed
17
18
19
20
21
22
#include "irgwalk.h"
#include "ircons.h"
#include "execfreq.h"
#include "unionfind.h"
#include "irdump_t.h"

23
#include "benode.h"
Matthias Braun's avatar
Matthias Braun committed
24
#include "besched.h"
25
#include "bespill.h"
Matthias Braun's avatar
Matthias Braun committed
26
27
#include "bespillslots.h"
#include "bechordal_t.h"
Matthias Braun's avatar
Matthias Braun committed
28
#include "statev_t.h"
Matthias Braun's avatar
Matthias Braun committed
29
#include "bemodule.h"
Matthias Braun's avatar
Matthias Braun committed
30
#include "belive.h"
31
32
#include "beirg.h"
#include "bearch.h"
33
#include "bespillutil.h"
Matthias Braun's avatar
Matthias Braun committed
34

35
36
#define DBG_COALESCING      1
#define DBG_INTERFERENCES   2
Matthias Braun's avatar
Matthias Braun committed
37

38
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
Matthias Braun's avatar
Matthias Braun committed
39

40
41
typedef struct spillweb_t spillweb_t;

42
typedef struct spill_t {
43
44
45
	ir_node    *spill;
	spillweb_t *web;
	int         spillslot;
Matthias Braun's avatar
Matthias Braun committed
46
47
} spill_t;

48
49
50
51
52
53
54
55
56
/**
 * A spillweb specifies the type of the values that a set of spills has to
 * prodcue. All spills that are joined through Phis form a spillweb.
 */
struct spillweb_t {
	spillweb_t    *merged_with;
	const ir_type *type;
};

57
typedef struct affinity_edge_t {
Matthias Braun's avatar
Matthias Braun committed
58
	double affinity;
59
60
	int    slot1;
	int    slot2;
Matthias Braun's avatar
Matthias Braun committed
61
62
} affinity_edge_t;

63
64
65
struct be_fec_env_t {
	struct obstack         obst;
	ir_graph              *irg;
66
67
	spill_t              **spills;
	unsigned              *spills_set;
68
69
70
71
	ir_node              **reloads;
	affinity_edge_t      **affinity_edges;
	set                   *memperms;
	set_frame_entity_func  set_frame_entity;
72
73
	bool                   at_begin;  /**< frame entities should be allocate at
	                                       the beginning of the stackframe */
74
	bool                   coalescing_forbidden;
75
};
Matthias Braun's avatar
Matthias Braun committed
76
77

/** Compare 2 affinity edges (used in quicksort) */
78
79
static int cmp_affinity(const void *d1, const void *d2)
{
80
81
82
83
	const affinity_edge_t *const *e1   = (const affinity_edge_t**)d1;
	const affinity_edge_t *const *e2   = (const affinity_edge_t**)d2;
	double                        aff1 = (*e1)->affinity;
	double                        aff2 = (*e2)->affinity;
Matthias Braun's avatar
Matthias Braun committed
84

85
	/* sort in descending order */
86
87
88
89
90
91
92
93
94
95
96
97
98
99
	if (aff1 < aff2) {
		return 1;
	} else if (aff1 > aff2) {
		return -1;
	} else {
		int slot11 = (*e1)->slot1;
		int slot21 = (*e2)->slot1;
		if (slot11 < slot21) {
			return 1;
		} else if (slot11 > slot21) {
			return -1;
		} else {
			int slot12 = (*e1)->slot2;
			int slot22 = (*e2)->slot2;
100
			return (slot12<slot22) - (slot12>slot22);
101
102
		}
	}
Matthias Braun's avatar
Matthias Braun committed
103
104
}

105
106
static spill_t *get_spill(be_fec_env_t *env, ir_node *node)
{
yb9976's avatar
yb9976 committed
107
	(void)env;
108
109
	assert(rbitset_is_set(env->spills_set, get_irn_idx(node)));
	return (spill_t*)get_irn_link(node);
Matthias Braun's avatar
Matthias Braun committed
110
111
}

112
static inline ir_node *get_memory_edge(const ir_node *node)
113
{
114
	foreach_irn_in_r(node, i, arg) {
115
		if (get_irn_mode(arg) == mode_M)
116
117
118
119
120
121
			return arg;
	}

	return NULL;
}

122
123
124
125
126
127
128
129
130
131
132
133
#ifndef NDEBUG
static bool modes_compatible(const ir_mode *mode0, const ir_mode *mode1)
{
	ir_mode_arithmetic arith0 = get_mode_arithmetic(mode0);
	ir_mode_arithmetic arith1 = get_mode_arithmetic(mode1);
	return arith0 == arith1
	   || (arith0 == irma_ieee754 && arith1 == irma_x86_extended_float)
	   || (arith1 == irma_ieee754 && arith0 == irma_x86_extended_float);
}
#endif

static void merge_spilltypes(spillweb_t *web, const ir_type *type1)
134
{
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
	assert(web->merged_with == NULL);
	assert(type1 != NULL);
	const ir_type *type0 = web->type;
	if (type0 == NULL) {
		web->type = type1;
		return;
	}
	assert(modes_compatible(get_type_mode(type0), get_type_mode(type1)));
	web->type
		= get_type_size_bytes(type1) > get_type_size_bytes(type0)
		? type1 : type0;
}

static spillweb_t *get_spill_web(spillweb_t *begin)
{
	spillweb_t *result = begin;
	while (result->merged_with != NULL) {
		result = result->merged_with;
	}
	/* path compression */
	for (spillweb_t *web = begin, *next; web != result;
	     web = next) {
		next = web->merged_with;
		web->merged_with = result;
	}
	return result;
}

static spillweb_t *merge_spillwebs(spillweb_t *web0, spillweb_t *web1)
{
	assert(web0 != web1);
	assert(web0->merged_with == NULL);
	assert(web1->merged_with == NULL);
	const ir_type *type1 = web1->type;
	if (type1 != NULL)
		merge_spilltypes(web0, type1);
	web1->merged_with = web0;
	return web0;
}

static spill_t *collect_spill(be_fec_env_t *env, ir_node *node, spillweb_t *web)
{
	assert(web == NULL || web->merged_with == NULL);

179
180
181
182
	/* already in spill set? */
	unsigned idx = get_irn_idx(node);
	if (rbitset_is_set(env->spills_set, idx)) {
		spill_t *spill = get_spill(env, node);
183
184
185
186
187
188
189
190
191
192
193
194
		/* create a new web if necesary */
		spillweb_t *new_web = spill->web;
		if (new_web == NULL) {
			new_web = web;
			if (new_web == NULL)
				new_web = OALLOCZ(&env->obst, spillweb_t);
		} else {
			new_web = get_spill_web(new_web);
			if (web != NULL && new_web != web)
				new_web = merge_spillwebs(new_web, web);
		}
		spill->web = new_web;
195
		return spill;
Matthias Braun's avatar
Matthias Braun committed
196
	}
197
	rbitset_set(env->spills_set, idx);
Matthias Braun's avatar
Matthias Braun committed
198

199
	spill_t *spill = OALLOC(&env->obst, spill_t);
200
201
202
	/* insert into set of spills if not already there */
	spill->spill     = node;
	spill->spillslot = (int)ARR_LEN(env->spills);
203
	spill->web       = web;
204
205
	ARR_APP1(spill_t*, env->spills, spill);
	set_irn_link(node, spill);
206
207
	DB((dbg, DBG_COALESCING, "Slot %d: %+F (%+F)\n", spill->spillslot,
	    skip_Proj(node), node));
208
209

	if (is_Phi(node)) {
210
		foreach_irn_in(node, i, arg) {
211
212
213
			/* ignore obvious self-loops */
			if (arg == node)
				continue;
214
215
			spill_t *arg_spill = collect_spill(env, arg, web);
			ir_node *block     = get_nodes_block(arg);
216
217

			/* add an affinity edge */
Manuel Mohr's avatar
Manuel Mohr committed
218
219
220
221
222
			affinity_edge_t *affinity_edge = OALLOC(&env->obst, affinity_edge_t);
			affinity_edge->affinity = get_block_execfreq(block);
			affinity_edge->slot1    = spill->spillslot;
			affinity_edge->slot2    = arg_spill->spillslot;
			ARR_APP1(affinity_edge_t*, env->affinity_edges, affinity_edge);
Manuel Mohr's avatar
Manuel Mohr committed
223
224
225
#ifndef NDEBUG
			spillweb_t *old_web = web;
#endif
226
227
228
229
230
			web = arg_spill->web;
			assert(web->merged_with == NULL);
			assert(web == old_web || old_web == NULL
			       || old_web->merged_with != NULL);
			spill->web = web;
Matthias Braun's avatar
Matthias Braun committed
231
		}
232
233
234
235
	} else if (web == NULL) {
		/* create new spillweb if necessary */
		web = OALLOCZ(&env->obst, spillweb_t);
		spill->web = web;
Matthias Braun's avatar
Matthias Braun committed
236
237
	}

238
	return spill;
Matthias Braun's avatar
Matthias Braun committed
239
240
}

241
242
void be_load_needs_frame_entity(be_fec_env_t *env, ir_node *node,
                                const ir_type *type)
243
{
244
245
246
247
248
249
	ir_node *mem   = get_memory_edge(node);
	spill_t *spill = collect_spill(env, mem, NULL);
	DB((dbg, DBG_COALESCING, "Slot %d: Reload: %+F Type %+F\n",
	    spill->spillslot, node, type));
	ARR_APP1(ir_node*, env->reloads, node);
	merge_spilltypes(spill->web, type);
Matthias Braun's avatar
Matthias Braun committed
250
251
}

252
253
static int merge_interferences(be_fec_env_t *env, bitset_t** interferences,
                               int* spillslot_unionfind, int s1, int s2)
Matthias Braun's avatar
Matthias Braun committed
254
{
255
	/* merge spillslots and interferences */
256
	int res = uf_union(spillslot_unionfind, s1, s2);
257
	/* we assume that we always merge s2 to s1 so swap s1, s2 if necessary */
258
	if (res != s1) {
Matthias Braun's avatar
Matthias Braun committed
259
260
261
262
263
264
265
		int t = s1;
		s1 = s2;
		s2 = t;
	}

	bitset_or(interferences[s1], interferences[s2]);

266
	/* update other interferences */
267
	for (size_t i = 0, n = ARR_LEN(env->spills); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
268
		bitset_t *intfs = interferences[i];
269
		if (bitset_is_set(intfs, s2))
Matthias Braun's avatar
Matthias Braun committed
270
271
272
273
274
275
276
277
278
279
280
281
			bitset_set(intfs, s1);
	}

	return res;
}

/**
 * A greedy coalescing algorithm for spillslots:
 *  1. Sort the list of affinity edges
 *  2. Try to merge slots with affinity edges (most expensive slots first)
 *  3. Try to merge everything else that is possible
 */
282
static void do_greedy_coalescing(be_fec_env_t *env)
Matthias Braun's avatar
Matthias Braun committed
283
{
284
285
	spill_t **spills     = env->spills;
	size_t    spillcount = ARR_LEN(spills);
286
	if (spillcount == 0)
Matthias Braun's avatar
Matthias Braun committed
287
288
		return;

Matthias Braun's avatar
Matthias Braun committed
289
	DB((dbg, DBG_COALESCING, "Coalescing %d spillslots\n", spillcount));
Matthias Braun's avatar
Matthias Braun committed
290

291
292
293
294
295
	struct obstack data;
	obstack_init(&data);

	bitset_t **interferences       = OALLOCN(&data, bitset_t*, spillcount);
	int       *spillslot_unionfind = OALLOCN(&data, int,       spillcount);
Matthias Braun's avatar
Matthias Braun committed
296

297
	uf_init(spillslot_unionfind, spillcount);
Matthias Braun's avatar
Matthias Braun committed
298

299
	for (size_t i = 0; i < spillcount; ++i) {
300
		interferences[i] = bitset_obstack_alloc(&data, spillcount);
Matthias Braun's avatar
Matthias Braun committed
301
302
	}

Christian Würdig's avatar
Christian Würdig committed
303
	/* construct interferences */
304
	for (size_t i = 0; i < spillcount; ++i) {
305
		ir_node *spill1 = spills[i]->spill;
Christian Würdig's avatar
Christian Würdig committed
306
		if (is_NoMem(spill1))
307
308
			continue;

309
		for (size_t i2 = i+1; i2 < spillcount; ++i2) {
310
			ir_node *spill2 = spills[i2]->spill;
Christian Würdig's avatar
Christian Würdig committed
311
			if (is_NoMem(spill2))
312
313
				continue;

314
			if (be_memory_values_interfere(spill1, spill2)) {
Matthias Braun's avatar
Matthias Braun committed
315
				DB((dbg, DBG_INTERFERENCES,
316
317
				     "Slot %d and %d interfere\n", i, i2));

Matthias Braun's avatar
Matthias Braun committed
318
319
320
321
322
323
				bitset_set(interferences[i], i2);
				bitset_set(interferences[i2], i);
			}
		}
	}

Christian Würdig's avatar
Christian Würdig committed
324
	/* sort affinity edges */
325
	QSORT_ARR(env->affinity_edges, cmp_affinity);
Matthias Braun's avatar
Matthias Braun committed
326

Christian Würdig's avatar
Christian Würdig committed
327
	/* try to merge affine nodes */
328
	for (size_t i = 0, n = ARR_LEN(env->affinity_edges); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
329
330
331
332
333
		const affinity_edge_t *edge = env->affinity_edges[i];
		int s1 = uf_find(spillslot_unionfind, edge->slot1);
		int s2 = uf_find(spillslot_unionfind, edge->slot2);

		/* test if values interfere */
Christian Würdig's avatar
Christian Würdig committed
334
		if (bitset_is_set(interferences[s1], s2)) {
Matthias Braun's avatar
Matthias Braun committed
335
336
337
338
			assert(bitset_is_set(interferences[s2], s1));
			continue;
		}

Matthias Braun's avatar
Matthias Braun committed
339
		DB((dbg, DBG_COALESCING,
340
		    "Merging %d and %d because of affinity edge\n", s1, s2));
Matthias Braun's avatar
Matthias Braun committed
341
342
343
344

		merge_interferences(env, interferences, spillslot_unionfind, s1, s2);
	}

345
	/* try to merge as much remaining spillslots as possible */
346
347
	for (size_t i = 0; i < spillcount; ++i) {
		int s1 = uf_find(spillslot_unionfind, i);
348
		if (s1 != (int)i)
Matthias Braun's avatar
Matthias Braun committed
349
350
			continue;

351
		for (size_t i2 = i+1; i2 < spillcount; ++i2) {
Matthias Braun's avatar
Matthias Braun committed
352
			int s2 = uf_find(spillslot_unionfind, i2);
353
			if (s2 != (int)i2)
Matthias Braun's avatar
Matthias Braun committed
354
355
356
357
358
359
				continue;

			/* test if values interfere
			 * we have to test n1-n2 and n2-n1, because only 1 side gets updated
			 * when node merging occurs
			 */
360
			if (bitset_is_set(interferences[s1], s2)) {
Matthias Braun's avatar
Matthias Braun committed
361
362
363
364
				assert(bitset_is_set(interferences[s2], s1));
				continue;
			}

Matthias Braun's avatar
Matthias Braun committed
365
			DB((dbg, DBG_COALESCING,
366
			     "Merging %d and %d because it is possible\n", s1, s2));
Matthias Braun's avatar
Matthias Braun committed
367

368
			if (merge_interferences(env, interferences, spillslot_unionfind, s1, s2) != 0) {
369
370
				/* we can break the loop here, because s2 is the new supernode
				 * now and we'll test s2 again later anyway */
Matthias Braun's avatar
Matthias Braun committed
371
372
373
374
375
				break;
			}
		}
	}

376
	/* assign spillslots to spills */
377
	for (size_t i = 0; i < spillcount; ++i) {
378
		spills[i]->spillslot = uf_find(spillslot_unionfind, i);
Matthias Braun's avatar
Matthias Braun committed
379
380
	}

381
	obstack_free(&data, 0);
Matthias Braun's avatar
Matthias Braun committed
382
383
}

384
typedef struct spill_slot_t {
385
386
	int        size;
	int        align;
387
	ir_entity *entity;
Matthias Braun's avatar
Matthias Braun committed
388
389
} spill_slot_t;

390
391
392
393
394
395
396
397
typedef struct memperm_entry_t memperm_entry_t;
struct memperm_entry_t {
	ir_node         *node;
	int              pos;
	ir_entity       *in;
	ir_entity       *out;
	memperm_entry_t *next;
};
Matthias Braun's avatar
Matthias Braun committed
398

399
typedef struct memperm_t {
400
401
	ir_node         *block;
	int              entrycount;
Matthias Braun's avatar
Matthias Braun committed
402
403
404
	memperm_entry_t *entries;
} memperm_t;

405
406
static int cmp_memperm(const void* d1, const void* d2, size_t size)
{
407
	(void)size;
408
409
	const memperm_t* e1 = (const memperm_t*)d1;
	const memperm_t* e2 = (const memperm_t*)d2;
Matthias Braun's avatar
Matthias Braun committed
410
411
412
	return e1->block != e2->block;
}

413
414
static memperm_t *get_memperm(be_fec_env_t *env, ir_node *block)
{
415
	memperm_t entry;
Matthias Braun's avatar
Matthias Braun committed
416
	entry.block = block;
417
418
419
	unsigned hash = hash_irn(block);
	memperm_t *res
		= set_find(memperm_t, env->memperms, &entry, sizeof(entry), hash);
Matthias Braun's avatar
Matthias Braun committed
420

421
	if (res == NULL) {
Matthias Braun's avatar
Matthias Braun committed
422
423
		entry.entrycount = 0;
		entry.entries = NULL;
424
		res = set_insert(memperm_t, env->memperms, &entry, sizeof(entry), hash);
Matthias Braun's avatar
Matthias Braun committed
425
426
427
428
	}
	return res;
}

429
430
static ir_entity* create_stack_entity(be_fec_env_t *env, spill_slot_t *slot)
{
431
432
433
434
	ir_graph  *irg   = env->irg;
	ir_type   *frame = get_irg_frame_type(irg);
	ir_entity *res   = frame_alloc_area(frame, slot->size, slot->align,
	                                    env->at_begin);
Matthias Braun's avatar
Matthias Braun committed
435
436
437
438
439
440
441
442
443
	slot->entity = res;

	return res;
}

/**
 * Enlarges a spillslot (if necessary) so that it can carry a value of size
 * @p othersize and alignment @p otheralign.
 */
444
445
static void enlarge_spillslot(spill_slot_t *slot, int otheralign, int othersize)
{
446
	if (othersize > slot->size) {
Matthias Braun's avatar
Matthias Braun committed
447
448
		slot->size = othersize;
	}
449
450
	if (otheralign > slot->align) {
		if (otheralign % slot->align != 0)
Matthias Braun's avatar
Matthias Braun committed
451
452
453
			slot->align *= otheralign;
		else
			slot->align = otheralign;
454
	} else if (slot->align % otheralign != 0) {
Matthias Braun's avatar
Matthias Braun committed
455
456
457
458
		slot->align *= otheralign;
	}
}

459
460
static void assign_spill_entity(be_fec_env_t *env, ir_node *node,
                                ir_entity *entity, const ir_type *type)
461
{
462
	if (is_NoMem(node))
463
		return;
464
	if (is_Sync(node)) {
465
		foreach_irn_in(node, i, in) {
466
			assert(!is_Phi(in));
467
			assign_spill_entity(env, in, entity, type);
468
469
470
471
		}
		return;
	}

472
	node = skip_Proj(node);
473
	env->set_frame_entity(node, entity, type);
474
475
}

Matthias Braun's avatar
Matthias Braun committed
476
477
478
479
/**
 * Create stack entities for the spillslots and assign them to the spill and
 * reload nodes.
 */
480
481
static void assign_spillslots(be_fec_env_t *env)
{
482
483
484
	spill_t     **spills     = env->spills;
	size_t        spillcount = ARR_LEN(spills);
	spill_slot_t *spillslots = ALLOCANZ(spill_slot_t, spillcount);
Matthias Braun's avatar
Matthias Braun committed
485

486
	/* construct spillslots */
487
	for (size_t s = 0; s < spillcount; ++s) {
488
489
490
491
		const spill_t    *spill  = spills[s];
		int               slotid = spill->spillslot;
		const spillweb_t *web    = get_spill_web(spill->web);
		const ir_type    *type   = web->type;
492
		int               size   = get_type_size_bytes(type);
493
		int               align  = get_type_alignment_bytes(type);
494
		spill_slot_t     *slot   = &spillslots[slotid];
Matthias Braun's avatar
Matthias Braun committed
495

496
		if (slot->align == 0 && slot->size == 0) {
Matthias Braun's avatar
Matthias Braun committed
497
498
499
500
501
502
503
			slot->align = align;
			slot->size = size;
		} else {
			enlarge_spillslot(slot, align, size);
		}
	}

504
	for (size_t s = 0; s < spillcount; ++s) {
505
506
507
508
		const spill_t *spill  = spills[s];
		ir_node       *node   = spill->spill;
		int            slotid = spill->spillslot;
		spill_slot_t  *slot   = &spillslots[slotid];
Matthias Braun's avatar
Matthias Braun committed
509

510
		if (slot->entity == NULL) {
Matthias Braun's avatar
Matthias Braun committed
511
512
513
			create_stack_entity(env, slot);
		}

514
		if (is_Phi(node)) {
515
			ir_node *block = get_nodes_block(node);
Matthias Braun's avatar
Matthias Braun committed
516

517
			/* should be a PhiM */
518
			assert(get_irn_mode(node) == mode_M);
Matthias Braun's avatar
Matthias Braun committed
519

520
			foreach_irn_in(node, i, arg) {
521
				ir_node *predblock = get_Block_cfgpred_block(block, i);
522
523
				spill_t *argspill  = get_spill(env, arg);
				int      argslotid = argspill->spillslot;
Matthias Braun's avatar
Matthias Braun committed
524

525
				if (slotid != argslotid) {
526
					memperm_t       *memperm;
Matthias Braun's avatar
Matthias Braun committed
527
					memperm_entry_t *entry;
528
					spill_slot_t    *argslot = &spillslots[argslotid];
529
					if (argslot->entity == NULL) {
Matthias Braun's avatar
Matthias Braun committed
530
531
532
						create_stack_entity(env, argslot);
					}

533
					memperm = get_memperm(env, predblock);
Matthias Braun's avatar
Matthias Braun committed
534

535
					entry = OALLOC(&env->obst, memperm_entry_t);
Matthias Braun's avatar
Matthias Braun committed
536
537
538
539
540
541
542
543
544
					entry->node = node;
					entry->pos = i;
					entry->in = argslot->entity;
					entry->out = slot->entity;
					entry->next = memperm->entries;
					memperm->entrycount++;
					memperm->entries = entry;
				}
			}
545
		} else {
546
547
			const spillweb_t *web = get_spill_web(spill->web);
			assign_spill_entity(env, node, slot->entity, web->type);
Matthias Braun's avatar
Matthias Braun committed
548
549
550
		}
	}

551
	for (size_t s = 0; s < ARR_LEN(env->reloads); ++s) {
552
		ir_node            *reload    = env->reloads[s];
553
		ir_node            *spillnode = get_memory_edge(reload);
554
555
		const spill_t      *spill     = get_spill(env, spillnode);
		const spill_slot_t *slot      = &spillslots[spill->spillslot];
556
		const spillweb_t   *web       = get_spill_web(spill->web);
Matthias Braun's avatar
Matthias Braun committed
557
558
559

		assert(slot->entity != NULL);

560
		env->set_frame_entity(reload, slot->entity, web->type);
Matthias Braun's avatar
Matthias Braun committed
561
562
563
	}
}

564
565
static void create_memperms(be_fec_env_t *env)
{
566
	foreach_set(env->memperms, memperm_t, memperm) {
Matthias Braun's avatar
Matthias Braun committed
567
568
		assert(memperm->entrycount > 0);

569
570
571
572
		ir_node **nodes = ALLOCAN(ir_node*, memperm->entrycount);
		int       i     = 0;
		for (memperm_entry_t *entry = memperm->entries; entry != NULL;
		     entry = entry->next, ++i) {
Matthias Braun's avatar
Matthias Braun committed
573
574
575
576
			ir_node* arg = get_irn_n(entry->node, entry->pos);
			nodes[i] = arg;
		}

577
578
		ir_node *mempermnode
			= be_new_MemPerm(memperm->block, memperm->entrycount, nodes);
Matthias Braun's avatar
Matthias Braun committed
579

580
		/* insert node into schedule */
581
582
		ir_node *const blockend
			= be_get_end_of_block_insertion_point(memperm->block);
583
		sched_add_before(blockend, mempermnode);
Sebastian Hack's avatar
Sebastian Hack committed
584
		stat_ev_dbl("mem_perm", memperm->entrycount);
585

586
		i = 0;
587
588
		for (memperm_entry_t *entry = memperm->entries; entry != NULL;
		     entry = entry->next, ++i) {
Matthias Braun's avatar
Matthias Braun committed
589
590
591
592
			ir_node* arg = get_irn_n(entry->node, entry->pos);

			be_set_MemPerm_in_entity(mempermnode, i, entry->in);
			be_set_MemPerm_out_entity(mempermnode, i, entry->out);
593
			ir_node *proj = new_r_Proj(mempermnode, get_irn_mode(arg), i);
594

595
			set_irn_n(entry->node, entry->pos, proj);
Matthias Braun's avatar
Matthias Braun committed
596
597
598
599
		}
	}
}

600
static unsigned count_spillslots(const be_fec_env_t *env)
601
{
602
603
604
605
	size_t          spillcount = ARR_LEN(env->spills);
	unsigned        slotcount  = 0;
	unsigned *const counted    = rbitset_alloca(spillcount);
	for (size_t s = 0; s < spillcount; ++s) {
606
607
608
609
610
		spill_t *spill     = env->spills[s];
		int      spillslot = spill->spillslot;
		if (!rbitset_is_set(counted, spillslot)) {
			++slotcount;
			rbitset_set(counted, spillslot);
611
612
613
614
615
616
		}
	}

	return slotcount;
}

617
be_fec_env_t *be_new_frame_entity_coalescer(ir_graph *irg)
618
{
619
	be_fec_env_t *env = XMALLOCZ(be_fec_env_t);
Matthias Braun's avatar
Matthias Braun committed
620

621
	be_assure_live_chk(irg);
622
623

	obstack_init(&env->obst);
624
	env->irg            = irg;
625
626
	env->spills         = NEW_ARR_F(spill_t*, 0);
	env->spills_set     = rbitset_malloc(get_irg_last_idx(irg));
Christian Würdig's avatar
Christian Würdig committed
627
	env->reloads        = NEW_ARR_F(ir_node*, 0);
628
	env->affinity_edges = NEW_ARR_F(affinity_edge_t*, 0);
Christian Würdig's avatar
Christian Würdig committed
629
	env->memperms       = new_set(cmp_memperm, 10);
Matthias Braun's avatar
Matthias Braun committed
630

631
632
	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);

633
634
635
636
637
	return env;
}

void be_free_frame_entity_coalescer(be_fec_env_t *env)
{
638
639
	ir_free_resources(env->irg, IR_RESOURCE_IRN_LINK);

640
641
642
	del_set(env->memperms);
	DEL_ARR_F(env->reloads);
	DEL_ARR_F(env->affinity_edges);
643
	DEL_ARR_F(env->spills);
644
	free(env->spills_set);
645
646
647
648
	obstack_free(&env->obst, NULL);

	free(env);
}
Matthias Braun's avatar
Matthias Braun committed
649

650
651
652
653
654
void be_forbid_coalescing(be_fec_env_t *env)
{
	env->coalescing_forbidden = true;
}

655
void be_assign_entities(be_fec_env_t *env,
656
                        set_frame_entity_func set_frame_entity,
657
                        bool alloc_entities_at_begin)
658
{
659
	env->set_frame_entity = set_frame_entity;
660
	env->at_begin         = alloc_entities_at_begin;
661

662
663
664
	if (stat_ev_enabled) {
		stat_ev_dbl("spillslots", ARR_LEN(env->spills));
	}
665

666
	if (be_coalesce_spill_slots && !env->coalescing_forbidden) {
667
668
669
		do_greedy_coalescing(env);
	}

670
671
672
	if (stat_ev_enabled) {
		stat_ev_dbl("spillslots_after_coalescing", count_spillslots(env));
	}
Matthias Braun's avatar
Matthias Braun committed
673

674
675
676
677
678
	assign_spillslots(env);

	create_memperms(env);
}

Matthias Braun's avatar
Matthias Braun committed
679
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillslots)
Matthias Braun's avatar
Matthias Braun committed
680
681
682
683
void be_init_spillslots(void)
{
	FIRM_DBG_REGISTER(dbg, "firm.be.spillslots");
}