bespill.c 16.7 KB
Newer Older
Daniel Grund's avatar
Daniel Grund committed
1
/**
Daniel Grund's avatar
Daniel Grund committed
2
 * Author:      Daniel Grund, Sebastian Hack
Daniel Grund's avatar
Daniel Grund committed
3
4
5
6
 * Date:		29.09.2005
 * Copyright:   (c) Universitaet Karlsruhe
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 */
Christian Würdig's avatar
Christian Würdig committed
7
8
9
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
Daniel Grund's avatar
Daniel Grund committed
10

11
12
#include <stdlib.h>

Daniel Grund's avatar
Daniel Grund committed
13
14
15
#include "pset.h"
#include "irnode_t.h"
#include "ircons_t.h"
Daniel Grund's avatar
Daniel Grund committed
16
#include "iredges_t.h"
17
18
19
#include "ident_t.h"
#include "type_t.h"
#include "entity_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
20
#include "debug.h"
Michael Beck's avatar
Michael Beck committed
21
#include "irgwalk.h"
22
#include "array.h"
Daniel Grund's avatar
Daniel Grund committed
23

24
25
#include "belive_t.h"
#include "besched_t.h"
Daniel Grund's avatar
Daniel Grund committed
26
27
#include "bespill.h"
#include "benode_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
28
#include "bechordal_t.h"
Daniel Grund's avatar
Daniel Grund committed
29

30
31
32
/* This enables re-computation of values. Current state: Unfinished and buggy. */
#undef BUGGY_REMAT

Sebastian Hack's avatar
Sebastian Hack committed
33
34
35
36
37
38
39
40
41
42
43
44
45
typedef struct _reloader_t reloader_t;
typedef struct _spill_info_t spill_info_t;

struct _reloader_t {
	reloader_t *next;
	ir_node *reloader;
};

struct _spill_info_t {
	ir_node *spilled_node;
	reloader_t *reloaders;
};

Daniel Grund's avatar
Daniel Grund committed
46
47
48
49
50
51
typedef struct _spill_ctx_t {
	ir_node *spilled;  /**< The spilled node. */
	ir_node *user;     /**< The node this spill is for. */
	ir_node *spill;    /**< The spill itself. */
} spill_ctx_t;

Sebastian Hack's avatar
Sebastian Hack committed
52
53
54
struct _spill_env_t {
	firm_dbg_module_t *dbg;
	const arch_register_class_t *cls;
Sebastian Hack's avatar
Sebastian Hack committed
55
	const be_chordal_env_t *chordal_env;
Sebastian Hack's avatar
Sebastian Hack committed
56
57
	struct obstack obst;
	set *spill_ctxs;
Daniel Grund's avatar
Daniel Grund committed
58
59
60
61
	set *spills;				/**< all spill_info_t's, which must be placed */
	pset *mem_phis;				/**< set of all special spilled phis. allocated and freed seperately */
	decide_irn_t is_mem_phi;	/**< callback func to decide if a phi needs special spilling */
	void *data;					/**< data passed to all callbacks */
Sebastian Hack's avatar
Sebastian Hack committed
62
63
64
};

static int cmp_spillctx(const void *a, const void *b, size_t n) {
Daniel Grund's avatar
Daniel Grund committed
65
66
67
68
69
	const spill_ctx_t *p = a;
	const spill_ctx_t *q = b;
	return !(p->user == q->user && p->spilled == q->spilled);
}

Sebastian Hack's avatar
Sebastian Hack committed
70
71
72
73
74
75
static int cmp_spillinfo(const void *x, const void *y, size_t size) {
	const spill_info_t *xx = x;
	const spill_info_t *yy = y;
	return ! (xx->spilled_node == yy->spilled_node);
}

Sebastian Hack's avatar
Sebastian Hack committed
76
77
78
79
spill_env_t *be_new_spill_env(firm_dbg_module_t *dbg,
							  const be_chordal_env_t *chordal_env,
							  decide_irn_t is_mem_phi, void *data) {

80
	spill_env_t *env = xmalloc(sizeof(env[0]));
Sebastian Hack's avatar
Sebastian Hack committed
81
82
83
84
85
86
87
	env->spill_ctxs  = new_set(cmp_spillctx, 1024);
	env->spills      = new_set(cmp_spillinfo, 1024);
	env->cls         = chordal_env->cls;
	env->dbg         = dbg;
	env->is_mem_phi  = is_mem_phi;
	env->data        = data;
	env->chordal_env = chordal_env;
Sebastian Hack's avatar
Sebastian Hack committed
88
89
90
91
	obstack_init(&env->obst);
	return env;
}

Daniel Grund's avatar
Daniel Grund committed
92
void be_delete_spill_env(spill_env_t *senv) {
Sebastian Hack's avatar
Sebastian Hack committed
93
94
95
96
97
98
	del_set(senv->spill_ctxs);
	del_set(senv->spills);
	obstack_free(&senv->obst, NULL);
	free(senv);
}

Daniel Grund's avatar
Daniel Grund committed
99
100
101
102
103
104
105
106
107
108
109
110
static spill_ctx_t *be_get_spill_ctx(set *sc, ir_node *to_spill, ir_node *ctx_irn) {
	spill_ctx_t templ;

	templ.spilled = to_spill;
	templ.user    = ctx_irn;
	templ.spill   = NULL;

	return set_insert(sc, &templ, sizeof(templ), HASH_COMBINE(HASH_PTR(to_spill), HASH_PTR(ctx_irn)));
}

static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *ctx_irn) {
	spill_ctx_t *ctx;
111
	DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", irn, ctx_irn));
Daniel Grund's avatar
Daniel Grund committed
112
113
114

	ctx = be_get_spill_ctx(senv->spill_ctxs, irn, ctx_irn);
	if(!ctx->spill) {
Sebastian Hack's avatar
Sebastian Hack committed
115
		const be_main_env_t *env = senv->chordal_env->birg->main_env;
Sebastian Hack's avatar
Sebastian Hack committed
116
		ctx->spill = be_spill(env->arch_env, irn, ctx_irn);
Daniel Grund's avatar
Daniel Grund committed
117
118
119
120
121
122
123
124
125
126
127
	}

	return ctx->spill;
}

/**
 * If the first usage of a phi result would be out of memory
 * there is no sense in allocating a register for it.
 * Thus we spill it and all its operands to the same spill slot.
 * Therefore the phi/dataB becomes a phi/Memory
 */
Daniel Grund's avatar
Daniel Grund committed
128
static ir_node *be_spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn) {
Daniel Grund's avatar
Daniel Grund committed
129
130
	int i, n = get_irn_arity(phi);
	ir_node **ins, *bl = get_nodes_block(phi);
Sebastian Hack's avatar
Sebastian Hack committed
131
	ir_graph *irg = senv->chordal_env->irg;
Daniel Grund's avatar
Daniel Grund committed
132
133
134
	spill_ctx_t *ctx;

	assert(is_Phi(phi));
135
	DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", phi, ctx_irn));
Daniel Grund's avatar
Daniel Grund committed
136
137
138
139
140
141
142

	/* search an existing spill for this context */
	ctx = be_get_spill_ctx(senv->spill_ctxs, phi, ctx_irn);

	/* if not found spill the phi */
	if(!ctx->spill) {
		/* build a new PhiM with dummy in-array */
143
    NEW_ARR_A(ir_node *, ins, n);
Daniel Grund's avatar
Daniel Grund committed
144
145
		for(i=0; i<n; ++i)
			ins[i] = new_r_Unknown(irg, mode_M);
Sebastian Hack's avatar
Sebastian Hack committed
146
		ctx->spill = new_r_Phi(senv->chordal_env->irg, bl, n, ins, mode_M);
Daniel Grund's avatar
Daniel Grund committed
147
148
149
150
151
152

		/* re-wire the phiM */
		for(i=0; i<n; ++i) {
			ir_node *arg = get_irn_n(phi, i);
			ir_node *sub_res;

Daniel Grund's avatar
Daniel Grund committed
153
154
			if(is_Phi(arg) && pset_find_ptr(senv->mem_phis, arg))
				sub_res = be_spill_phi(senv, arg, ctx_irn);
Daniel Grund's avatar
Daniel Grund committed
155
156
157
158
159
160
161
162
163
			else
				sub_res = be_spill_irn(senv, arg, ctx_irn);

			set_irn_n(ctx->spill, i, sub_res);
		}
	}
	return ctx->spill;
}

Daniel Grund's avatar
Daniel Grund committed
164
static ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill) {
Daniel Grund's avatar
Daniel Grund committed
165
	ir_node *res;
Daniel Grund's avatar
Daniel Grund committed
166
167
	if (pset_find_ptr(senv->mem_phis, to_spill))
		res = be_spill_phi(senv, to_spill, to_spill);
Daniel Grund's avatar
Daniel Grund committed
168
169
170
171
172
173
	else
		res = be_spill_irn(senv, to_spill, to_spill);

	return res;
}

Daniel Grund's avatar
Daniel Grund committed
174
175
static void phi_walker(ir_node *irn, void *env) {
	spill_env_t *senv = env;
Sebastian Hack's avatar
Sebastian Hack committed
176
	const arch_env_t *arch = senv->chordal_env->birg->main_env->arch_env;
Daniel Grund's avatar
Daniel Grund committed
177
178
179
180
181
182
183
184

	if (is_Phi(irn) && arch_irn_has_reg_class(arch, irn, 0, senv->cls)
			&& senv->is_mem_phi(irn, senv->data)) {
		DBG((senv->dbg, LEVEL_1, "  %+F\n", irn));
		pset_insert_ptr(senv->mem_phis, irn);
	}
}

185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265

#ifdef BUGGY_REMAT

static int check_remat_conditions(spill_env_t *senv, ir_node *spill, ir_node *spilled, ir_node *reloader) {
	int pos, max;

	/* check for 'normal' spill and general remat condition */
	if (!be_is_Spill(spill) || !arch_irn_is(senv->chordal_env->birg->main_env->arch_env, spilled, rematerializable))
		return 0;

	/* check availability of original arguments */
	if (is_Block(reloader)) {

		/* we want to remat at the end of a block.
		 * thus all arguments must be alive at the end of the block
		 */
		for (pos=0, max=get_irn_arity(spilled); pos<max; ++pos) {
			ir_node *arg = get_irn_n(spilled, pos);
			if (!is_live_end(reloader, arg))
				return 0;
		}

	} else {

		/* we want to remat before the insn reloader
		 * thus an arguments is alive if
		 *   - it interferes with the reloaders result
		 * or
		 *   - or it is (last-) used by reloader itself
		 */
		for (pos=0, max=get_irn_arity(spilled); pos<max; ++pos) {
			ir_node *arg = get_irn_n(spilled, pos);
			int i, m;

			if (values_interfere(reloader, arg))
				goto is_alive;

			for (i=0, m=get_irn_arity(reloader); i<m; ++i) {
				ir_node *rel_arg = get_irn_n(reloader, i);
				if (rel_arg == arg)
					goto is_alive;
			}

			/* arg is not alive before reloader */
			return 0;

is_alive:	;

		}

	}

	return 1;
}

static ir_node *do_remat(spill_env_t *senv, ir_node *spilled, ir_node *reloader) {
	ir_node *res;
	ir_node *bl = (is_Block(reloader)) ? reloader : get_nodes_block(reloader);

	/* recompute the value */
	res = new_ir_node(get_irn_dbg_info(spilled), senv->chordal_env->irg, bl,
		get_irn_op(spilled),
		get_irn_mode(spilled),
		get_irn_arity(spilled),
		get_irn_in(spilled));

	DBG((senv->dbg, LEVEL_1, "Insert remat %+F before reloader %+F\n", res, reloader));

	/* insert in schedule */
	if (is_Block(reloader)) {
		ir_node *insert = sched_skip(reloader, 0, sched_skip_cf_predicator, (void *) senv->chordal_env->birg->main_env->arch_env);
		sched_add_after(insert, res);
	} else {
		sched_add_before(reloader, res);
	}

	return res;
}

#endif

Daniel Grund's avatar
Daniel Grund committed
266
void be_insert_spills_reloads(spill_env_t *senv, pset *reload_set) {
267
268
	const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env;
	ir_graph *irg          = senv->chordal_env->irg;
Daniel Grund's avatar
Daniel Grund committed
269
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
270
271
	spill_info_t *si;

Daniel Grund's avatar
Daniel Grund committed
272
	/* get all special spilled phis */
Daniel Grund's avatar
Daniel Grund committed
273
274
	DBG((senv->dbg, LEVEL_1, "Mem-phis:\n"));
	senv->mem_phis = pset_new_ptr_default();
Sebastian Hack's avatar
Sebastian Hack committed
275
	irg_walk_graph(senv->chordal_env->irg, phi_walker, NULL, senv);
Daniel Grund's avatar
Daniel Grund committed
276
277

	/* Add reloads for mem_phis */
278
	/* BETTER: These reloads (1) should only be inserted, if they are really needed */
Daniel Grund's avatar
Daniel Grund committed
279
280
281
282
283
284
285
	DBG((senv->dbg, LEVEL_1, "Reloads for mem-phis:\n"));
	for(irn = pset_first(senv->mem_phis); irn; irn = pset_next(senv->mem_phis)) {
		const ir_edge_t *e;
		DBG((senv->dbg, LEVEL_1, " Mem-phi %+F\n", irn));
		foreach_out_edge(irn, e) {
			ir_node *user = e->src;
			if (is_Phi(user) && !pset_find_ptr(senv->mem_phis, user)) {
Sebastian Hack's avatar
Sebastian Hack committed
286
287
288
					ir_node *use_bl = get_nodes_block(user);
					DBG((senv->dbg, LEVEL_1, " non-mem-phi user %+F\n", user));
					be_add_reload_on_edge(senv, irn, use_bl, e->pos); /* (1) */
Daniel Grund's avatar
Daniel Grund committed
289
290
			}
		}
Daniel Grund's avatar
Daniel Grund committed
291
292
	}

Sebastian Hack's avatar
Sebastian Hack committed
293
	/* process each spilled node */
Daniel Grund's avatar
Daniel Grund committed
294
	DBG((senv->dbg, LEVEL_1, "Insert spills and reloads:\n"));
Sebastian Hack's avatar
Sebastian Hack committed
295
296
297
	for(si = set_first(senv->spills); si; si = set_next(senv->spills)) {
		reloader_t *rld;
		ir_mode *mode = get_irn_mode(si->spilled_node);
298
		pset *values = pset_new_ptr(16);
Sebastian Hack's avatar
Sebastian Hack committed
299
300
301

		/* go through all reloads for this spill */
		for(rld = si->reloaders; rld; rld = rld->next) {
302
303
			ir_node *new_val;

Sebastian Hack's avatar
Sebastian Hack committed
304
			/* the spill for this reloader */
Daniel Grund's avatar
Daniel Grund committed
305
			ir_node *spill   = be_spill_node(senv, si->spilled_node);
Sebastian Hack's avatar
Sebastian Hack committed
306

307
308
309
310
311
312
313
#ifdef BUGGY_REMAT
			if (check_remat_conditions(senv, spill, si->spilled_node, rld->reloader))
				new_val = do_remat(senv, si->spilled_node, rld->reloader);
			else
#endif
				/* do a reload */
				new_val = be_reload(aenv, senv->cls, rld->reloader, mode, spill);
Sebastian Hack's avatar
Sebastian Hack committed
314

315
316
			DBG((senv->dbg, LEVEL_1, " %+F of %+F before %+F\n", new_val, si->spilled_node, rld->reloader));
			pset_insert_ptr(values, new_val);
Sebastian Hack's avatar
Sebastian Hack committed
317
			if(reload_set)
318
				pset_insert_ptr(reload_set, new_val);
Sebastian Hack's avatar
Sebastian Hack committed
319
320
		}

321
322
323
324
		/* introduce copies, rewire the uses */
		assert(pset_count(values) > 0 && "???");
		pset_insert_ptr(values, si->spilled_node);
		be_ssa_constr_set_ignore(senv->chordal_env->dom_front, values, senv->mem_phis);
Sebastian Hack's avatar
Sebastian Hack committed
325

326
327
		del_pset(values);
	}
Sebastian Hack's avatar
Sebastian Hack committed
328

Daniel Grund's avatar
Daniel Grund committed
329
	for(irn = pset_first(senv->mem_phis); irn; irn = pset_next(senv->mem_phis)) {
Daniel Grund's avatar
Daniel Grund committed
330
331
		int i, n;
		for(i = 0, n = get_irn_arity(irn); i < n; ++i)
Sebastian Hack's avatar
Sebastian Hack committed
332
			set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg));
Daniel Grund's avatar
Daniel Grund committed
333
334
		sched_remove(irn);
	}
Daniel Grund's avatar
Daniel Grund committed
335

Daniel Grund's avatar
Daniel Grund committed
336
	del_pset(senv->mem_phis);
Daniel Grund's avatar
Daniel Grund committed
337
}
Sebastian Hack's avatar
Sebastian Hack committed
338

Daniel Grund's avatar
Daniel Grund committed
339
void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before) {
Sebastian Hack's avatar
Sebastian Hack committed
340
341
342
343
344
345
346
347
348
349
350
351
352
	spill_info_t templ, *res;
	reloader_t *rel;

	templ.spilled_node = to_spill;
	templ.reloaders    = NULL;
	res = set_insert(senv->spills, &templ, sizeof(templ), HASH_PTR(to_spill));

	rel           = obstack_alloc(&senv->obst, sizeof(rel[0]));
	rel->reloader = before;
	rel->next     = res->reloaders;
	res->reloaders = rel;
}

Daniel Grund's avatar
Daniel Grund committed
353
void be_add_reload_on_edge(spill_env_t *senv, ir_node *to_spill, ir_node *bl, int pos) {
Daniel Grund's avatar
Daniel Grund committed
354
	ir_node *insert_bl = get_irn_arity(bl) == 1 ? sched_first(bl) : get_Block_cfgpred_block(bl, pos);
Daniel Grund's avatar
Daniel Grund committed
355
	be_add_reload(senv, to_spill, insert_bl);
Sebastian Hack's avatar
Sebastian Hack committed
356
}
357
358
359



Daniel Grund's avatar
Daniel Grund committed
360
/****************************************
361

Daniel Grund's avatar
Daniel Grund committed
362
	SPILL SLOT MANAGEMENT AND OPTS
363

Daniel Grund's avatar
Daniel Grund committed
364
****************************************/
365
366
367

typedef struct _spill_slot_t {
	unsigned size;
368
	unsigned align;
369
	pset *members;
370
	ir_mode *largest_mode;	/* the mode of all members with largest size */
371
372
373
374
375
376
377
} spill_slot_t;

typedef struct _ss_env_t {
	firm_dbg_module_t *dbg;
	struct obstack ob;
	be_chordal_env_t *cenv;
	pmap *slots;		/* maps spill_contexts to spill_slots */
378
  pmap *types;    /* maps modes to types */
379
380
381
382
383
384
385
386
387
388
389
390
391
} ss_env_t;


static void compute_spill_slots_walker(ir_node *spill, void *env) {
	ss_env_t *ssenv = env;
	ir_node *ctx;
	pmap_entry *entry;
	spill_slot_t *ss;

	if (!be_is_Spill(spill))
		return;

	/* check, if this spill is for a context already known */
Sebastian Hack's avatar
Sebastian Hack committed
392
	ctx = be_get_Spill_context(spill);
393
394
395
396
397
398
	entry = pmap_find(ssenv->slots, ctx);

	if (!entry) {
		/* this is a new spill context */
		ss = obstack_alloc(&ssenv->ob, sizeof(*ss));
		ss->members = pset_new_ptr(8);
399
		ss->largest_mode = get_irn_mode(get_irn_n(spill, be_pos_Spill_val));
400
401
		ss->size = get_mode_size_bytes(ss->largest_mode);
		ss->align = ss->size; /* TODO Assumed for now */
402
403
404
405
406
		pmap_insert(ssenv->slots, ctx, ss);
	} else {
		ir_node *irn;
		/* values with the same spill_ctx must go into the same spill slot */
		ss = entry->value;
407
		assert(ss->size == (unsigned)get_mode_size_bytes(get_irn_mode(get_irn_n(spill, be_pos_Spill_val))) && "Different sizes for the same spill slot are not allowed yet.");
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
		for (irn = pset_first(ss->members); irn; irn = pset_next(ss->members)) {
			/* use values_interfere here, because it uses the dominance check,
			   which does work for values in memory */
			assert(!values_interfere(spill, irn) && "Spills for the same spill slot must not interfere!");
		}
	}

	pset_insert_ptr(ss->members, spill);
}

static int ss_sorter(const void *v1, const void *v2) {
	const spill_slot_t *ss1 = v1;
	const spill_slot_t *ss2 = v2;
	return ((int) ss2->size) - ((int) ss1->size);
}


425
426
427
428
429
430
431
432
433
434
435
436
/**
 * This function should optimize the spill slots.
 *  - Coalescing of multiple slots
 *  - Ordering the slots
 *
 * Input slots are in @p ssenv->slots
 * @p size The count of initial spill slots in @p ssenv->slots
 *         This also is the size of the preallocated array @p ass
 *
 * @return An array of spill slots @p ass in specific order
 **/
static void optimize_slots(ss_env_t *ssenv, int size, spill_slot_t **ass) {
437
438
439
440
441
442
443
444
445
	int i, o, used_slots;
	pmap_entry *entr;

	i=0;
	pmap_foreach(ssenv->slots, entr)
		ass[i++] = entr->value;

	/* Sort the array to minimize fragmentation and cache footprint.
	   Large slots come first */
446
	qsort(ass, size, sizeof(ass[0]), ss_sorter);
447
448
449
450
451

	/* For each spill slot:
		- assign a new offset to this slot
	    - xor find another slot to coalesce with */
	used_slots = 0;
452
	for (i=0; i<size; ++i) { /* for each spill slot */
453
454
455
456
457
458
459
460
461
462
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
491
492
493
494
		ir_node *n1;
		int tgt_slot = -1;

		DBG((ssenv->dbg, LEVEL_1, "Spill slot %d members:\n", i));
		for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members))
			DBG((ssenv->dbg, LEVEL_1, "  %+F\n", n1));


		for (o=0; o < used_slots && tgt_slot == -1; ++o) { /* for each offset-assigned spill slot */
			/* check inter-slot-pairs for interference */
			ir_node *n2;
			for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members))
				for(n2 = pset_first(ass[o]->members); n2; n2 = pset_next(ass[o]->members))
					if(values_interfere(n1, n2)) {
						pset_break(ass[i]->members);
						pset_break(ass[o]->members);
						DBG((ssenv->dbg, LEVEL_1, "    Interf %+F -- %+F\n", n1, n2));
						goto interf_detected;
					}

			/* if we are here, there is no interference between ass[i] and ass[o] */
			tgt_slot = o;

interf_detected: /*nothing*/ ;
		}

		/* now the members of ass[i] join the members of ass[tgt_slot] */

		/* do we need a new slot? */
		if (tgt_slot == -1) {
			tgt_slot = used_slots;
			used_slots++;

			/* init slot */
			if (tgt_slot != i) {
				ass[tgt_slot]->size = ass[i]->size;
				del_pset(ass[tgt_slot]->members);
				ass[tgt_slot]->members = pset_new_ptr(8);
			}
		}

		/* copy the members to the target pset */
495
496
497
498
		/* NOTE: If src and tgt pset are the same, inserting while iterating is not allowed */
		if (tgt_slot != i)
			for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members))
					pset_insert_ptr(ass[tgt_slot]->members, n1);
499
	}
500
501
502
503
504
}

#define ALIGN_SPILL_AREA 16
#define pset_foreach(pset, elm)  for(elm=pset_first(pset); elm; elm=pset_next(pset))

505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
/**
 * Returns a spill type for a mode. Keep them in a map to reduce
 * the number of types.
 */
static ir_type *get_spill_type(pmap *types, ir_mode *mode) {
  pmap_entry *e = pmap_find(types, mode);
  ir_type *res;

  if (! e) {
		char buf[64];
    snprintf(buf, sizeof(buf), "spill_slot_type_%s", get_mode_name(mode));
    res = new_type_primitive(new_id_from_str(buf), mode);
    pmap_insert(types, mode, res);
  }
  else
    res = e->value;
  return res;
}

524
525
526
static void assign_entities(ss_env_t *ssenv, int n, spill_slot_t **ss) {
	int i, offset;
	ir_type *frame = get_irg_frame_type(ssenv->cenv->irg);
527

528
529
530
531
	/* aligning by increasing frame size */
	offset = get_type_size_bits(frame) / 8;
	offset = round_up2(offset, ALIGN_SPILL_AREA);
	set_type_size_bytes(frame, -1);
532

533
534
535
	/* create entities and assign offsets according to size and alignment*/
	for (i=0; i<n; ++i) {
		char buf[64];
536
		ident *name;
537
538
539
540
541
542
543
		entity *spill_ent;
		ir_node *irn;

		/* build entity */
		snprintf(buf, sizeof(buf), "spill_slot_%d", i);
		name = new_id_from_str(buf);

544
		spill_ent = new_entity(frame, name, get_spill_type(ssenv->types, ss[i]->largest_mode));
545
546
547
548
549
550
551
552
553
554
555
556
557
558

		/* align */
		offset = round_up2(offset, ss[i]->align);
		/* set */
		set_entity_offset_bytes(spill_ent, offset);
		/* next possible offset */
		offset += ss[i]->size;

		pset_foreach(ss[i]->members, irn)
			be_set_Spill_entity(irn, spill_ent);
	}

	/* set final size of stack frame */
	set_type_size_bytes(frame, offset);
559
560
561
562
}

void be_compute_spill_offsets(be_chordal_env_t *cenv) {
	ss_env_t ssenv;
563
564
565
	spill_slot_t **ss;
	int ss_size;
	pmap_entry *pme;
566
567
568
569

	obstack_init(&ssenv.ob);
	ssenv.cenv  = cenv;
	ssenv.slots = pmap_create();
Daniel Grund's avatar
Daniel Grund committed
570
	ssenv.types = pmap_create();
571
572
	ssenv.dbg   = firm_dbg_register("ir.be.spillslots");

573
	/* Get initial spill slots */
574
575
	irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv);

576
577
578
579
580
581
582
583
584
585
	/* Build an empty array for optimized spill slots */
	ss_size = pmap_count(ssenv.slots);
	ss = obstack_alloc(&ssenv.ob, ss_size * sizeof(*ss));
	optimize_slots(&ssenv, ss_size, ss);

	/* Integrate slots into the stack frame entity */
	assign_entities(&ssenv, ss_size, ss);

	/* Clean up */
	pmap_foreach(ssenv.slots, pme)
586
	del_pset(((spill_slot_t *)pme->value)->members);
587
	pmap_destroy(ssenv.slots);
588
	pmap_destroy(ssenv.types);
589
	obstack_free(&ssenv.ob, NULL);
590
591

	be_copy_entities_to_reloads(cenv->irg);
592
}