bespill.c 20.6 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"
23
#include "pdeq.h"
Daniel Grund's avatar
Daniel Grund committed
24

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

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

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

66
67
68
/**
 * compare two spill contexts.
 */
Sebastian Hack's avatar
Sebastian Hack committed
69
static int cmp_spillctx(const void *a, const void *b, size_t n) {
Daniel Grund's avatar
Daniel Grund committed
70
71
	const spill_ctx_t *p = a;
	const spill_ctx_t *q = b;
72
	return p->user != q->user || p->spilled != q->spilled;
Daniel Grund's avatar
Daniel Grund committed
73
74
}

75
76
77
/**
 * Compare two spill infos.
 */
Sebastian Hack's avatar
Sebastian Hack committed
78
79
80
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;
81
	return xx->spilled_node != yy->spilled_node;
Sebastian Hack's avatar
Sebastian Hack committed
82
83
}

84
DEBUG_ONLY(
85
/* Sets the debug module of a spill environment. */
86
87
88
void be_set_spill_env_dbg_module(spill_env_t *env, firm_dbg_module_t *dbg) {
	env->dbg = dbg;
}
Christian Würdig's avatar
Christian Würdig committed
89
)
90

91
/* Creates a new spill environment. */
92
spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env, decide_irn_t is_mem_phi, void *data) {
93
	spill_env_t *env = xmalloc(sizeof(env[0]));
Sebastian Hack's avatar
Sebastian Hack committed
94
95
96
97
98
99
	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
100
101
102
103
	obstack_init(&env->obst);
	return env;
}

104
/* Deletes a spill environment. */
Daniel Grund's avatar
Daniel Grund committed
105
void be_delete_spill_env(spill_env_t *senv) {
Sebastian Hack's avatar
Sebastian Hack committed
106
107
108
109
110
111
	del_set(senv->spill_ctxs);
	del_set(senv->spills);
	obstack_free(&senv->obst, NULL);
	free(senv);
}

112
113
114
115
116
117
118
119
120
/**
 * Returns a spill context. If the context did not exists, create one.
 *
 * @param sc        the set containing all spill contexts
 * @param to_spill  the node that should be spilled
 * @param ctx_irn   an user of the spilled node
 *
 * @return a spill context.
 */
Daniel Grund's avatar
Daniel Grund committed
121
122
123
124
125
126
127
128
129
130
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)));
}

131
132
133
134
135
136
137
138
139
/**
 * Creates a spill.
 *
 * @param senv      the spill environment
 * @param irn       the node that should be spilled
 * @param ctx_irn   an user of the spilled node
 *
 * @return a be_Spill node
 */
Daniel Grund's avatar
Daniel Grund committed
140
141
static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *ctx_irn) {
	spill_ctx_t *ctx;
142
	DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", irn, ctx_irn));
Daniel Grund's avatar
Daniel Grund committed
143
144
145

	ctx = be_get_spill_ctx(senv->spill_ctxs, irn, ctx_irn);
	if(!ctx->spill) {
Sebastian Hack's avatar
Sebastian Hack committed
146
		const be_main_env_t *env = senv->chordal_env->birg->main_env;
Sebastian Hack's avatar
Sebastian Hack committed
147
		ctx->spill = be_spill(env->arch_env, irn, ctx_irn);
Daniel Grund's avatar
Daniel Grund committed
148
149
150
151
152
153
	}

	return ctx->spill;
}

/**
154
 * If the first usage of a Phi result would be out of memory
Daniel Grund's avatar
Daniel Grund committed
155
156
157
 * 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
158
159
160
161
162
163
 *
 * @param senv      the spill environment
 * @param phi       the Phi node that should be spilled
 * @param ctx_irn   an user of the spilled node
 *
 * @return a be_Spill node
Daniel Grund's avatar
Daniel Grund committed
164
 */
Daniel Grund's avatar
Daniel Grund committed
165
static ir_node *be_spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn) {
Daniel Grund's avatar
Daniel Grund committed
166
167
	int i, n = get_irn_arity(phi);
	ir_node **ins, *bl = get_nodes_block(phi);
Sebastian Hack's avatar
Sebastian Hack committed
168
	ir_graph *irg = senv->chordal_env->irg;
Daniel Grund's avatar
Daniel Grund committed
169
170
171
	spill_ctx_t *ctx;

	assert(is_Phi(phi));
172
	DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", phi, ctx_irn));
Daniel Grund's avatar
Daniel Grund committed
173
174
175
176
177
178

	/* 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) {
179
		/* build a new PhiM */
Christian Würdig's avatar
Christian Würdig committed
180
		NEW_ARR_A(ir_node *, ins, n);
181
		for (i=0; i<n; ++i) {
Daniel Grund's avatar
Daniel Grund committed
182
183
184
			ir_node *arg = get_irn_n(phi, i);
			ir_node *sub_res;

Daniel Grund's avatar
Daniel Grund committed
185
186
			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
187
188
			else
				sub_res = be_spill_irn(senv, arg, ctx_irn);
189
			ins[i] = sub_res;
Daniel Grund's avatar
Daniel Grund committed
190
		}
191
		ctx->spill = new_r_Phi(senv->chordal_env->irg, bl, n, ins, mode_M);
Daniel Grund's avatar
Daniel Grund committed
192
193
194
195
	}
	return ctx->spill;
}

196
197
198
199
200
201
202
203
204
/**
 * Spill a node.
 *
 * @param senv      the spill environment
 * @param irn       the node that should be spilled
 * @param ctx_irn   an user of the spilled node
 *
 * @return a be_Spill node
 */
Daniel Grund's avatar
Daniel Grund committed
205
static ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill) {
Daniel Grund's avatar
Daniel Grund committed
206
	ir_node *res;
Daniel Grund's avatar
Daniel Grund committed
207
208
	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
209
210
211
212
213
214
	else
		res = be_spill_irn(senv, to_spill, to_spill);

	return res;
}

Daniel Grund's avatar
Daniel Grund committed
215
#ifdef REMAT
216
217
218

#ifdef BUGGY_REMAT

219
220
221
222
223
224
225
226
/**
 * Check if a spilled node could be rematerialized.
 *
 * @param senv      the spill environment
 * @param spill     the Spill node
 * @param spilled   the node that was spilled
 * @param reloader  a irn that requires a reload
 */
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
266
267
268
269
270
271
272
273
274
275
276
277
278
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
279
280
#else /* BUGGY_REMAT */

281
282
283
284
285
286
287
288
/**
 * A very simple rematerialization checker.
 *
 * @param senv      the spill environment
 * @param spill     the Spill node
 * @param spilled   the node that was spilled
 * @param reloader  a irn that requires a reload
 */
Daniel Grund's avatar
Daniel Grund committed
289
290
291
292
293
294
295
296
297
298
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 */

299
300
301
#endif /* REMAT */

/**
302
 * Re-materialize a node.
303
304
305
306
307
 *
 * @param senv      the spill environment
 * @param spilled   the node that was spilled
 * @param reloader  a irn that requires a reload
 */
308
309
310
311
312
313
314
315
316
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),
317
		get_irn_in(spilled) + 1);
Daniel Grund's avatar
Daniel Grund committed
318
	copy_node_attr(spilled, res);
319
320
321
322
323
324
325
326
327
328
329
330
331
332

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

333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
/**
 * Walker: fills the mem_phis set by evaluating Phi nodes
 * using the is_mem_phi() callback.
 */
static void phi_walker(ir_node *irn, void *env) {
	spill_env_t *senv = env;

	if (is_Phi(irn)) {
		const arch_env_t *arch = senv->chordal_env->birg->main_env->arch_env;
		if (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
350
void be_insert_spills_reloads(spill_env_t *senv, pset *reload_set) {
351
352
	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
353
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
354
	spill_info_t *si;
355
	pdeq *possibly_dead;
Sebastian Hack's avatar
Sebastian Hack committed
356

Daniel Grund's avatar
Daniel Grund committed
357
	/* get all special spilled phis */
Daniel Grund's avatar
Daniel Grund committed
358
359
	DBG((senv->dbg, LEVEL_1, "Mem-phis:\n"));
	senv->mem_phis = pset_new_ptr_default();
Sebastian Hack's avatar
Sebastian Hack committed
360
	irg_walk_graph(senv->chordal_env->irg, phi_walker, NULL, senv);
Daniel Grund's avatar
Daniel Grund committed
361
362

	/* Add reloads for mem_phis */
363
	/* BETTER: These reloads (1) should only be inserted, if they are really needed */
Daniel Grund's avatar
Daniel Grund committed
364
365
366
367
368
369
370
	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
371
372
373
					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
374
375
			}
		}
Daniel Grund's avatar
Daniel Grund committed
376
377
	}

Sebastian Hack's avatar
Sebastian Hack committed
378
	/* process each spilled node */
Daniel Grund's avatar
Daniel Grund committed
379
	DBG((senv->dbg, LEVEL_1, "Insert spills and reloads:\n"));
380
	possibly_dead = new_pdeq();
Sebastian Hack's avatar
Sebastian Hack committed
381
382
383
	for(si = set_first(senv->spills); si; si = set_next(senv->spills)) {
		reloader_t *rld;
		ir_mode *mode = get_irn_mode(si->spilled_node);
384
		pset *values = pset_new_ptr(16);
Sebastian Hack's avatar
Sebastian Hack committed
385
386
387

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

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

Daniel Grund's avatar
Daniel Grund committed
393
#ifdef REMAT
394
			if (check_remat_conditions(senv, spill, si->spilled_node, rld->reloader)) {
395
				new_val = do_remat(senv, si->spilled_node, rld->reloader);
396
397
				pdeq_putl(possibly_dead, spill);
			}
398
399
400
401
			else
#endif
				/* do a reload */
				new_val = be_reload(aenv, senv->cls, rld->reloader, mode, spill);
Sebastian Hack's avatar
Sebastian Hack committed
402

403
404
			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
405
			if(reload_set)
406
				pset_insert_ptr(reload_set, new_val);
Sebastian Hack's avatar
Sebastian Hack committed
407
408
		}

409
410
411
412
		/* 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
413

414
415
		del_pset(values);
	}
Sebastian Hack's avatar
Sebastian Hack committed
416

417
	foreach_pset(senv->mem_phis, irn) {
Daniel Grund's avatar
Daniel Grund committed
418
		int i, n;
419
420
		for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
			pdeq_putl(possibly_dead, get_irn_n(irn, i));
Sebastian Hack's avatar
Sebastian Hack committed
421
			set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg));
422
		}
Daniel Grund's avatar
Daniel Grund committed
423
424
		sched_remove(irn);
	}
Daniel Grund's avatar
Daniel Grund committed
425

426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
	/* check if possibly dead nodes are really dead yet */
	while (! pdeq_empty(possibly_dead)) {
		ir_node *irn = pdeq_getr(possibly_dead);
		const ir_edge_t *edge = get_irn_out_edge_first(irn);

		if (! edge) {
			int i;
			for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
				pdeq_putl(possibly_dead, get_irn_n(irn, i));
				set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg));
			}
			sched_remove(irn);
		}
	}
	del_pdeq(possibly_dead);
Daniel Grund's avatar
Daniel Grund committed
441
	del_pset(senv->mem_phis);
Daniel Grund's avatar
Daniel Grund committed
442
}
Sebastian Hack's avatar
Sebastian Hack committed
443

Daniel Grund's avatar
Daniel Grund committed
444
void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before) {
Sebastian Hack's avatar
Sebastian Hack committed
445
446
447
448
449
450
451
452
453
454
455
456
457
	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
458
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
459
	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
460
	be_add_reload(senv, to_spill, insert_bl);
Sebastian Hack's avatar
Sebastian Hack committed
461
}
462
463
464



Daniel Grund's avatar
Daniel Grund committed
465
/****************************************
466

Daniel Grund's avatar
Daniel Grund committed
467
	SPILL SLOT MANAGEMENT AND OPTS
468

Daniel Grund's avatar
Daniel Grund committed
469
****************************************/
470
471
472

typedef struct _spill_slot_t {
	unsigned size;
473
	unsigned align;
474
	pset *members;
475
	ir_mode *largest_mode;	/* the mode of all members with largest size */
476
477
478
479
480
481
} spill_slot_t;

typedef struct _ss_env_t {
	struct obstack ob;
	be_chordal_env_t *cenv;
	pmap *slots;		/* maps spill_contexts to spill_slots */
482
483
	pmap *types;    /* maps modes to types */
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
484
485
} ss_env_t;

486

487
488
489
/**
 * Walker: compute the spill slots
 */
490
491
492
493
494
495
496
497
498
499
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
500
	ctx = be_get_Spill_context(spill);
501
502
503
	entry = pmap_find(ssenv->slots, ctx);

	if (!entry) {
504
		struct _arch_env_t *arch_env     = ssenv->cenv->birg->main_env->arch_env;
505
		const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val);
506
507
		ir_mode *largest_mode            = arch_register_class_mode(cls);

508
509
		/* this is a new spill context */
		ss = obstack_alloc(&ssenv->ob, sizeof(*ss));
510
511
512
513
		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);
514
515
516
517
		pmap_insert(ssenv->slots, ctx, ss);
	} else {
		/* values with the same spill_ctx must go into the same spill slot */
		ss = entry->value;
518
519
520
521
522
523
524
525
526
527
528
529
530
531

#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!");
			}
532
		}
533
#endif /* NDEBUG */
534
535
536
537
538
	}

	pset_insert_ptr(ss->members, spill);
}

539
540
541
/**
 * qsort compare function, sort spill slots by size.
 */
542
static int ss_sorter(const void *v1, const void *v2) {
543
544
545
	const spill_slot_t **ss1 = v1;
	const spill_slot_t **ss2 = v2;
	return ((int) (*ss2)->size) - ((int) (*ss1)->size);
546
547
548
}


549
550
551
552
553
554
555
556
557
558
559
/**
 * 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
 **/
560
static void optimize_slots(ss_env_t *ssenv, int size, spill_slot_t *ass[]) {
561
562
563
564
565
566
567
568
569
	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 */
570
	qsort(ass, size, sizeof(ass[0]), ss_sorter);
571
572
573
574
575

	/* For each spill slot:
		- assign a new offset to this slot
	    - xor find another slot to coalesce with */
	used_slots = 0;
576
	for (i=0; i<size; ++i) { /* for each spill slot */
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
		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 */
619
620
621
622
		/* 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);
623
	}
624
625
626
627
628
}

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

629
630
631
/**
 * Returns a spill type for a mode. Keep them in a map to reduce
 * the number of types.
632
633
634
635
636
637
638
 *
 * @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.
639
 */
640
641
static ir_type *get_spill_type(pmap *types, spill_slot_t *ss) {
  pmap_entry *e = pmap_find(types, ss->largest_mode);
642
643
644
645
  ir_type *res;

  if (! e) {
		char buf[64];
646
647
648
649
    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);
650
  }
651
  else {
652
    res = e->value;
653
654
		assert(get_type_alignment_bytes(res) == (int)ss->align);
	}
655
656
657
  return res;
}

658
659
660
661
662
663
664
665
666
/**
 * 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;
667
	ir_type *frame = get_irg_frame_type(ssenv->cenv->irg);
668

669
670
671
672
	/* 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);
673

674
	/* create entities and assign offsets according to size and alignment*/
675
	for (i = 0; i < n_slots; ++i) {
676
		char buf[64];
677
		ident *name;
678
679
680
681
682
683
684
		entity *spill_ent;
		ir_node *irn;

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

685
		spill_ent = new_entity(frame, name, get_spill_type(ssenv->types, ss[i]));
686
687
688
689
690
691

		/* align */
		offset = round_up2(offset, ss[i]->align);
		/* set */
		set_entity_offset_bytes(spill_ent, offset);
		/* next possible offset */
692
		offset += round_up2(ss[i]->size, ss[i]->align);
693
694
695
696
697
698

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

	/* set final size of stack frame */
699
700
	frame_align = get_type_alignment_bytes(frame);
	set_type_size_bytes(frame, round_up2(offset, frame_align));
701
702
703
704
}

void be_compute_spill_offsets(be_chordal_env_t *cenv) {
	ss_env_t ssenv;
705
706
707
	spill_slot_t **ss;
	int ss_size;
	pmap_entry *pme;
708
709
710
711

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

715
	/* Get initial spill slots */
716
717
	irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv);

718
719
720
721
722
723
724
725
726
727
	/* 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)
728
	del_pset(((spill_slot_t *)pme->value)->members);
729
	pmap_destroy(ssenv.slots);
730
	pmap_destroy(ssenv.types);
731
	obstack_free(&ssenv.ob, NULL);
732
733

	be_copy_entities_to_reloads(cenv->irg);
734
}