bespill.c 18.4 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

Daniel Grund's avatar
Daniel Grund committed
30
#undef REMAT
31
32
33
/* This enables re-computation of values. Current state: Unfinished and buggy. */
#undef BUGGY_REMAT

Sebastian Hack's avatar
Sebastian Hack committed
34
35
36
37
38
39
40
41
42
43
44
45
46
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
47
48
49
50
51
52
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
53
54
struct _spill_env_t {
	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
	set *spills;				/**< all spill_info_t's, which must be placed */
59
	pset *mem_phis;				/**< set of all special spilled phis. allocated and freed separately */
Daniel Grund's avatar
Daniel Grund committed
60
61
	decide_irn_t is_mem_phi;	/**< callback func to decide if a phi needs special spilling */
	void *data;					/**< data passed to all callbacks */
62
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
Sebastian Hack's avatar
Sebastian Hack committed
63
64
65
};

static int cmp_spillctx(const void *a, const void *b, size_t n) {
Daniel Grund's avatar
Daniel Grund committed
66
67
68
69
70
	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
71
72
73
74
75
76
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);
}

77
78
79
80
81
82
DEBUG_ONLY(
void be_set_spill_env_dbg_module(spill_env_t *env, firm_dbg_module_t *dbg) {
	env->dbg = dbg;
}
);

83
spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env, decide_irn_t is_mem_phi, void *data) {
84
	spill_env_t *env = xmalloc(sizeof(env[0]));
Sebastian Hack's avatar
Sebastian Hack committed
85
86
87
88
89
90
	env->spill_ctxs  = new_set(cmp_spillctx, 1024);
	env->spills      = new_set(cmp_spillinfo, 1024);
	env->cls         = chordal_env->cls;
	env->is_mem_phi  = is_mem_phi;
	env->data        = data;
	env->chordal_env = chordal_env;
Sebastian Hack's avatar
Sebastian Hack committed
91
92
93
94
	obstack_init(&env->obst);
	return env;
}

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

Daniel Grund's avatar
Daniel Grund committed
102
103
104
105
106
107
108
109
110
111
112
113
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;
114
	DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", irn, ctx_irn));
Daniel Grund's avatar
Daniel Grund committed
115
116
117

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

	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
131
static ir_node *be_spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn) {
Daniel Grund's avatar
Daniel Grund committed
132
133
	int i, n = get_irn_arity(phi);
	ir_node **ins, *bl = get_nodes_block(phi);
Sebastian Hack's avatar
Sebastian Hack committed
134
	ir_graph *irg = senv->chordal_env->irg;
Daniel Grund's avatar
Daniel Grund committed
135
136
137
	spill_ctx_t *ctx;

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

	/* 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 */
146
    NEW_ARR_A(ir_node *, ins, n);
Daniel Grund's avatar
Daniel Grund committed
147
148
		for(i=0; i<n; ++i)
			ins[i] = new_r_Unknown(irg, mode_M);
Sebastian Hack's avatar
Sebastian Hack committed
149
		ctx->spill = new_r_Phi(senv->chordal_env->irg, bl, n, ins, mode_M);
Daniel Grund's avatar
Daniel Grund committed
150
151
152
153
154
155

		/* 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
156
157
			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
158
159
160
161
162
163
164
165
166
			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
167
static ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill) {
Daniel Grund's avatar
Daniel Grund committed
168
	ir_node *res;
Daniel Grund's avatar
Daniel Grund committed
169
170
	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
171
172
173
174
175
176
	else
		res = be_spill_irn(senv, to_spill, to_spill);

	return res;
}

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

	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);
	}
}

Daniel Grund's avatar
Daniel Grund committed
188
#ifdef REMAT
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

#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;
}

Daniel Grund's avatar
Daniel Grund committed
244
245
246
247
248
249
250
251
252
253
254
255
#else /* BUGGY_REMAT */

static int check_remat_conditions(spill_env_t *senv, ir_node *spill, ir_node *spilled, ir_node *reloader) {
	const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env;

	return get_irn_arity(spilled) == 0 &&
		   be_is_Spill(spill) &&
		   arch_irn_is(aenv, spilled, rematerializable);
}

#endif /* BUGGY_REMAT */

256
257
258
259
260
261
262
263
264
265
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));
Daniel Grund's avatar
Daniel Grund committed
266
	copy_node_attr(spilled, res);
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282

	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
283
void be_insert_spills_reloads(spill_env_t *senv, pset *reload_set) {
284
285
	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
286
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
287
288
	spill_info_t *si;

Daniel Grund's avatar
Daniel Grund committed
289
	/* get all special spilled phis */
Daniel Grund's avatar
Daniel Grund committed
290
291
	DBG((senv->dbg, LEVEL_1, "Mem-phis:\n"));
	senv->mem_phis = pset_new_ptr_default();
Sebastian Hack's avatar
Sebastian Hack committed
292
	irg_walk_graph(senv->chordal_env->irg, phi_walker, NULL, senv);
Daniel Grund's avatar
Daniel Grund committed
293
294

	/* Add reloads for mem_phis */
295
	/* BETTER: These reloads (1) should only be inserted, if they are really needed */
Daniel Grund's avatar
Daniel Grund committed
296
297
298
299
300
301
302
	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
303
304
305
					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
306
307
			}
		}
Daniel Grund's avatar
Daniel Grund committed
308
309
	}

Sebastian Hack's avatar
Sebastian Hack committed
310
	/* process each spilled node */
Daniel Grund's avatar
Daniel Grund committed
311
	DBG((senv->dbg, LEVEL_1, "Insert spills and reloads:\n"));
Sebastian Hack's avatar
Sebastian Hack committed
312
313
314
	for(si = set_first(senv->spills); si; si = set_next(senv->spills)) {
		reloader_t *rld;
		ir_mode *mode = get_irn_mode(si->spilled_node);
315
		pset *values = pset_new_ptr(16);
Sebastian Hack's avatar
Sebastian Hack committed
316
317
318

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

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

Daniel Grund's avatar
Daniel Grund committed
324
#ifdef REMAT
325
326
327
328
329
330
			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
331

332
333
			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
334
			if(reload_set)
335
				pset_insert_ptr(reload_set, new_val);
Sebastian Hack's avatar
Sebastian Hack committed
336
337
		}

338
339
340
341
		/* 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
342

343
344
		del_pset(values);
	}
Sebastian Hack's avatar
Sebastian Hack committed
345

Daniel Grund's avatar
Daniel Grund committed
346
	for(irn = pset_first(senv->mem_phis); irn; irn = pset_next(senv->mem_phis)) {
Daniel Grund's avatar
Daniel Grund committed
347
348
		int i, n;
		for(i = 0, n = get_irn_arity(irn); i < n; ++i)
Sebastian Hack's avatar
Sebastian Hack committed
349
			set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg));
Daniel Grund's avatar
Daniel Grund committed
350
351
		sched_remove(irn);
	}
Daniel Grund's avatar
Daniel Grund committed
352

Daniel Grund's avatar
Daniel Grund committed
353
	del_pset(senv->mem_phis);
Daniel Grund's avatar
Daniel Grund committed
354
}
Sebastian Hack's avatar
Sebastian Hack committed
355

Daniel Grund's avatar
Daniel Grund committed
356
void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before) {
Sebastian Hack's avatar
Sebastian Hack committed
357
358
359
360
361
362
363
364
365
366
367
368
369
	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
370
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
371
	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
372
	be_add_reload(senv, to_spill, insert_bl);
Sebastian Hack's avatar
Sebastian Hack committed
373
}
374
375
376



Daniel Grund's avatar
Daniel Grund committed
377
/****************************************
378

Daniel Grund's avatar
Daniel Grund committed
379
	SPILL SLOT MANAGEMENT AND OPTS
380

Daniel Grund's avatar
Daniel Grund committed
381
****************************************/
382
383
384

typedef struct _spill_slot_t {
	unsigned size;
385
	unsigned align;
386
	pset *members;
387
	ir_mode *largest_mode;	/* the mode of all members with largest size */
388
389
390
391
392
393
} spill_slot_t;

typedef struct _ss_env_t {
	struct obstack ob;
	be_chordal_env_t *cenv;
	pmap *slots;		/* maps spill_contexts to spill_slots */
394
395
	pmap *types;    /* maps modes to types */
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
396
397
} ss_env_t;

398

399
400
401
/**
 * Walker: compute the spill slots
 */
402
403
404
405
406
407
408
409
410
411
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
412
	ctx = be_get_Spill_context(spill);
413
414
415
	entry = pmap_find(ssenv->slots, ctx);

	if (!entry) {
416
		struct _arch_env_t *arch_env     = ssenv->cenv->birg->main_env->arch_env;
417
		const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val);
418
419
		ir_mode *largest_mode            = arch_register_class_mode(cls);

420
421
		/* this is a new spill context */
		ss = obstack_alloc(&ssenv->ob, sizeof(*ss));
422
423
424
425
		ss->members      = pset_new_ptr(8);
		ss->largest_mode = largest_mode;
		ss->size         = get_mode_size_bytes(ss->largest_mode);
		ss->align        = arch_isa_get_reg_class_alignment(arch_env->isa, cls);
426
427
428
429
		pmap_insert(ssenv->slots, ctx, ss);
	} else {
		/* values with the same spill_ctx must go into the same spill slot */
		ss = entry->value;
430
431
432
433
434
435
436
437
438
439
440
441
442
443

#ifndef NDEBUG
		/* ugly mega assert :-) */
		{
			ir_node *irn;
			struct _arch_env_t *arch_env     = ssenv->cenv->birg->main_env->arch_env;
			const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val);
			int size = get_mode_size_bytes(arch_register_class_mode(cls));
			assert(ss->size == size && "Different sizes for the same spill slot are not allowed.");
			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!");
			}
444
		}
445
#endif /* NDEBUG */
446
447
448
449
450
	}

	pset_insert_ptr(ss->members, spill);
}

451
452
453
/**
 * qsort compare function, sort spill slots by size.
 */
454
455
456
457
458
459
460
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);
}


461
462
463
464
465
466
467
468
469
470
471
472
/**
 * 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) {
473
474
475
476
477
478
479
480
481
	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 */
482
	qsort(ass, size, sizeof(ass[0]), ss_sorter);
483
484
485
486
487

	/* For each spill slot:
		- assign a new offset to this slot
	    - xor find another slot to coalesce with */
	used_slots = 0;
488
	for (i=0; i<size; ++i) { /* for each spill slot */
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
		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 */
531
532
533
534
		/* 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);
535
	}
536
537
538
539
540
}

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

541
542
543
/**
 * Returns a spill type for a mode. Keep them in a map to reduce
 * the number of types.
544
545
546
547
548
549
550
 *
 * @param types  a map containing all created types
 * @param ss     the spill slot
 *
 * Note that type types should are identical for every mode.
 * This rule might break if two different register classes return the same
 * mode but different alignments.
551
 */
552
553
static ir_type *get_spill_type(pmap *types, spill_slot_t *ss) {
  pmap_entry *e = pmap_find(types, ss->largest_mode);
554
555
556
557
  ir_type *res;

  if (! e) {
		char buf[64];
558
559
560
561
    snprintf(buf, sizeof(buf), "spill_slot_type_%s", get_mode_name(ss->largest_mode));
    res = new_type_primitive(new_id_from_str(buf), ss->largest_mode);
		set_type_alignment_bytes(res, ss->align);
    pmap_insert(types, ss->largest_mode, res);
562
  }
563
  else {
564
    res = e->value;
565
566
		assert(get_type_alignment_bytes(res) == (int)ss->align);
	}
567
568
569
  return res;
}

570
571
572
573
574
575
576
577
578
/**
 * Create spill slot entities on the frame type.
 *
 * @param ssenv   the spill environment
 * @param n       number of spill slots
 * @param ss      array of spill slots
 */
static void assign_entities(ss_env_t *ssenv, int n_slots, spill_slot_t *ss[]) {
	int i, offset, frame_align;
579
	ir_type *frame = get_irg_frame_type(ssenv->cenv->irg);
580

581
582
583
584
	/* 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);
585

586
	/* create entities and assign offsets according to size and alignment*/
587
	for (i = 0; i < n_slots; ++i) {
588
		char buf[64];
589
		ident *name;
590
591
592
593
594
595
596
		entity *spill_ent;
		ir_node *irn;

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

597
		spill_ent = new_entity(frame, name, get_spill_type(ssenv->types, ss[i]));
598
599
600
601
602
603

		/* align */
		offset = round_up2(offset, ss[i]->align);
		/* set */
		set_entity_offset_bytes(spill_ent, offset);
		/* next possible offset */
604
		offset += round_up2(ss[i]->size, ss[i]->align);
605
606
607
608
609
610

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

	/* set final size of stack frame */
611
612
	frame_align = get_type_alignment_bytes(frame);
	set_type_size_bytes(frame, round_up2(offset, frame_align));
613
614
615
616
}

void be_compute_spill_offsets(be_chordal_env_t *cenv) {
	ss_env_t ssenv;
617
618
619
	spill_slot_t **ss;
	int ss_size;
	pmap_entry *pme;
620
621
622
623

	obstack_init(&ssenv.ob);
	ssenv.cenv  = cenv;
	ssenv.slots = pmap_create();
Daniel Grund's avatar
Daniel Grund committed
624
	ssenv.types = pmap_create();
625
	FIRM_DBG_REGISTER(ssenv.dbg, "ir.be.spillslots");
626

627
	/* Get initial spill slots */
628
629
	irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv);

630
631
632
633
634
635
636
637
638
639
	/* 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)
640
	del_pset(((spill_slot_t *)pme->value)->members);
641
	pmap_destroy(ssenv.slots);
642
	pmap_destroy(ssenv.types);
643
	obstack_free(&ssenv.ob, NULL);
644
645

	be_copy_entities_to_reloads(cenv->irg);
646
}