bespill.c 21.8 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 */
61
	decide_irn_t is_spilled_phi;/**< callback func to decide if a phi needs special spilling */
Daniel Grund's avatar
Daniel Grund committed
62
	void *data;					/**< data passed to all callbacks */
63
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
Sebastian Hack's avatar
Sebastian Hack committed
64
65
};

Christian Würdig's avatar
Christian Würdig committed
66
67
68
69
70
71
72
73
74
/* associated Phi -> Spill*/
typedef struct _phi_spill_assoc_t {
	ir_node *phi;
	ir_node *spill;
} phi_spill_assoc_t;

/**
 * Compare two Phi->Spill associations.
 */
75
static int cmp_phi_spill_assoc(const void *a, const void *b, size_t n) {
Christian Würdig's avatar
Christian Würdig committed
76
77
78
79
80
	const phi_spill_assoc_t *p1 = a;
	const phi_spill_assoc_t *p2 = b;
	return p1->phi != p2->phi;
}

81
82
83
/**
 * compare two spill contexts.
 */
Sebastian Hack's avatar
Sebastian Hack committed
84
static int cmp_spillctx(const void *a, const void *b, size_t n) {
Daniel Grund's avatar
Daniel Grund committed
85
86
	const spill_ctx_t *p = a;
	const spill_ctx_t *q = b;
87
	return p->user != q->user || p->spilled != q->spilled;
Daniel Grund's avatar
Daniel Grund committed
88
89
}

90
91
92
/**
 * Compare two spill infos.
 */
Sebastian Hack's avatar
Sebastian Hack committed
93
94
95
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;
96
	return xx->spilled_node != yy->spilled_node;
Sebastian Hack's avatar
Sebastian Hack committed
97
98
}

99
DEBUG_ONLY(
100
/* Sets the debug module of a spill environment. */
101
102
103
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
104
)
105

106
/* Creates a new spill environment. */
107
108
109
110
111
112
113
114
spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env, decide_irn_t is_spilled_phi, void *data) {
	spill_env_t *env	= xmalloc(sizeof(env[0]));
	env->spill_ctxs		= new_set(cmp_spillctx, 1024);
	env->spills			= new_set(cmp_spillinfo, 1024);
	env->cls			= chordal_env->cls;
	env->is_spilled_phi	= is_spilled_phi;
	env->data			= data;
	env->chordal_env	= chordal_env;
Sebastian Hack's avatar
Sebastian Hack committed
115
116
117
118
	obstack_init(&env->obst);
	return env;
}

119
120
121
122
123
void be_set_is_spilled_phi(spill_env_t *env, decide_irn_t is_spilled_phi, void *data) {
	env->is_spilled_phi	= is_spilled_phi;
	env->data			= data;
}

124
/* Deletes a spill environment. */
Daniel Grund's avatar
Daniel Grund committed
125
void be_delete_spill_env(spill_env_t *senv) {
Sebastian Hack's avatar
Sebastian Hack committed
126
127
128
129
130
131
	del_set(senv->spill_ctxs);
	del_set(senv->spills);
	obstack_free(&senv->obst, NULL);
	free(senv);
}

132
133
134
135
136
137
138
139
140
/**
 * 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
141
142
143
144
145
146
147
148
149
150
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)));
}

151
152
153
154
155
156
157
158
159
/**
 * 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
160
161
static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *ctx_irn) {
	spill_ctx_t *ctx;
162
	const be_main_env_t *env = senv->chordal_env->birg->main_env;
163
	DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", irn, ctx_irn));
Daniel Grund's avatar
Daniel Grund committed
164

165
	// Has the value already been spilled?
Daniel Grund's avatar
Daniel Grund committed
166
	ctx = be_get_spill_ctx(senv->spill_ctxs, irn, ctx_irn);
167
168
169
170
171
172
173
174
	if(ctx->spill)
		return ctx->spill;

	/* Trying to spill an already spilled value, no need for a new spill
	 * node then, we can simply connect to the same one for this reload
	 */
	if(be_is_Reload(irn)) {
		return get_irn_n(irn, be_pos_Reload_mem);
Daniel Grund's avatar
Daniel Grund committed
175
176
	}

177
	ctx->spill = be_spill(env->arch_env, irn, ctx_irn);
Daniel Grund's avatar
Daniel Grund committed
178
179
180
181
	return ctx->spill;
}

/**
182
 * If the first usage of a Phi result would be out of memory
Daniel Grund's avatar
Daniel Grund committed
183
184
185
 * 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
186
187
188
189
190
191
 *
 * @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
192
 */
193
static ir_node *be_spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn, set *already_visited_phis, bitset_t *bs) {
Christian Würdig's avatar
Christian Würdig committed
194
195
196
197
198
	int         i, n      = get_irn_arity(phi);
	ir_graph    *irg      = senv->chordal_env->irg;
	ir_node     *bl       = get_nodes_block(phi);
	ir_node     **ins, *phi_spill;
	phi_spill_assoc_t key;
Daniel Grund's avatar
Daniel Grund committed
199
200
201
	spill_ctx_t *ctx;

	assert(is_Phi(phi));
202
	DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", phi, ctx_irn));
Daniel Grund's avatar
Daniel Grund committed
203

Christian Würdig's avatar
Christian Würdig committed
204
205
206
	/* build a new PhiM */
	NEW_ARR_A(ir_node *, ins, n);
	for (i = 0; i < n; ++i) {
207
		ins[i] = new_r_Bad(irg);
Christian Würdig's avatar
Christian Würdig committed
208
209
210
211
	}
	phi_spill = new_r_Phi(senv->chordal_env->irg, bl, n, ins, mode_M);
	key.phi   = phi;
	key.spill = phi_spill;
212
	set_insert(already_visited_phis, &key, sizeof(key), HASH_PTR(phi));
213
	bitset_set(bs, get_irn_idx(phi));
Christian Würdig's avatar
Christian Würdig committed
214

Daniel Grund's avatar
Daniel Grund committed
215
216
217
218
	/* search an existing spill for this context */
	ctx = be_get_spill_ctx(senv->spill_ctxs, phi, ctx_irn);

	/* if not found spill the phi */
Christian Würdig's avatar
Christian Würdig committed
219
220
221
	if (! ctx->spill) {
		/* collect all arguments of the phi */
		for (i = 0; i < n; ++i) {
Daniel Grund's avatar
Daniel Grund committed
222
223
			ir_node *arg = get_irn_n(phi, i);
			ir_node *sub_res;
Christian Würdig's avatar
Christian Würdig committed
224
225
226
			phi_spill_assoc_t *entry;

			if(is_Phi(arg) && pset_find_ptr(senv->mem_phis, arg)) {
227
228
				if (! bitset_is_set(bs, get_irn_idx(arg)))
					sub_res = be_spill_phi(senv, arg, ctx_irn, already_visited_phis, bs);
Christian Würdig's avatar
Christian Würdig committed
229
230
231
232
				else {
					/* we already visited the argument phi: get it's spill */
					key.phi   = arg;
					key.spill = NULL;
233
					entry     = set_find(already_visited_phis, &key, sizeof(key), HASH_PTR(arg));
Christian Würdig's avatar
Christian Würdig committed
234
235
					assert(entry && "argument phi already visited, but no spill found?!?");
					sub_res   = entry->spill;
236
					assert(sub_res && "spill missing?!?");
Christian Würdig's avatar
Christian Würdig committed
237
238
				}
			}
Daniel Grund's avatar
Daniel Grund committed
239
240
			else
				sub_res = be_spill_irn(senv, arg, ctx_irn);
Christian Würdig's avatar
Christian Würdig committed
241
242

			set_irn_n(phi_spill, i, sub_res);
Daniel Grund's avatar
Daniel Grund committed
243
		}
Christian Würdig's avatar
Christian Würdig committed
244
245

		ctx->spill = phi_spill;
Daniel Grund's avatar
Daniel Grund committed
246
247
248
249
	}
	return ctx->spill;
}

250
251
252
253
/**
 * Spill a node.
 *
 * @param senv      the spill environment
254
 * @param to_spill  the node that should be spilled
255
256
257
 *
 * @return a be_Spill node
 */
258
static ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill) {
Christian Würdig's avatar
Christian Würdig committed
259
	ir_graph *irg                  = get_irn_irg(to_spill);
260
	ir_node  *res;
Christian Würdig's avatar
Christian Würdig committed
261

Matthias Braun's avatar
Matthias Braun committed
262
263
264
	if (pset_find_ptr(senv->mem_phis, to_spill)) {
		set *already_visited_phis = new_set(cmp_phi_spill_assoc, 10);
		bitset_t *bs = bitset_alloca(get_irg_last_idx(irg));
265
		res = be_spill_phi(senv, to_spill, to_spill, already_visited_phis, bs);
Matthias Braun's avatar
Matthias Braun committed
266
267
		del_set(already_visited_phis);
	} else {
Daniel Grund's avatar
Daniel Grund committed
268
		res = be_spill_irn(senv, to_spill, to_spill);
Matthias Braun's avatar
Matthias Braun committed
269
	}
Daniel Grund's avatar
Daniel Grund committed
270
271
272
273

	return res;
}

Daniel Grund's avatar
Daniel Grund committed
274
#ifdef REMAT
275
276
277

#ifdef BUGGY_REMAT

278
279
280
281
282
283
284
285
/**
 * 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
 */
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
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
338
339
#else /* BUGGY_REMAT */

340
341
342
343
344
345
346
347
/**
 * 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
348
349
350
351
352
353
354
355
356
357
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 */

358
359
360
#endif /* REMAT */

/**
361
 * Re-materialize a node.
362
363
364
365
366
 *
 * @param senv      the spill environment
 * @param spilled   the node that was spilled
 * @param reloader  a irn that requires a reload
 */
367
368
369
370
371
372
373
374
375
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),
376
		get_irn_in(spilled) + 1);
Daniel Grund's avatar
Daniel Grund committed
377
	copy_node_attr(spilled, res);
378
379
380
381
382
383
384
385
386
387
388
389
390
391

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

392
393
/**
 * Walker: fills the mem_phis set by evaluating Phi nodes
394
 * using the is_spilled_phi() callback.
395
396
397
398
399
400
401
 */
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) &&
402
			senv->is_spilled_phi(irn, senv->data)) {
403
404
405
406
407
408
			DBG((senv->dbg, LEVEL_1, "  %+F\n", irn));
			pset_insert_ptr(senv->mem_phis, irn);
		}
	}
}

409
void be_insert_spills_reloads(spill_env_t *senv) {
410
	const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env;
Daniel Grund's avatar
Daniel Grund committed
411
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
412
413
	spill_info_t *si;

Daniel Grund's avatar
Daniel Grund committed
414
	/* get all special spilled phis */
Daniel Grund's avatar
Daniel Grund committed
415
416
	DBG((senv->dbg, LEVEL_1, "Mem-phis:\n"));
	senv->mem_phis = pset_new_ptr_default();
Sebastian Hack's avatar
Sebastian Hack committed
417
	irg_walk_graph(senv->chordal_env->irg, phi_walker, NULL, senv);
Daniel Grund's avatar
Daniel Grund committed
418
419

	/* Add reloads for mem_phis */
420
	/* BETTER: These reloads (1) should only be inserted, if they are really needed */
Daniel Grund's avatar
Daniel Grund committed
421
422
423
424
425
426
427
	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
428
429
430
					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
431
432
			}
		}
Daniel Grund's avatar
Daniel Grund committed
433
434
	}

Sebastian Hack's avatar
Sebastian Hack committed
435
	/* process each spilled node */
Daniel Grund's avatar
Daniel Grund committed
436
	DBG((senv->dbg, LEVEL_1, "Insert spills and reloads:\n"));
Sebastian Hack's avatar
Sebastian Hack committed
437
438
439
	for(si = set_first(senv->spills); si; si = set_next(senv->spills)) {
		reloader_t *rld;
		ir_mode *mode = get_irn_mode(si->spilled_node);
440
		//ir_node *value;
441
		pset *values = pset_new_ptr(16);
Sebastian Hack's avatar
Sebastian Hack committed
442
443
444

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

Sebastian Hack's avatar
Sebastian Hack committed
447
			/* the spill for this reloader */
448
			ir_node *spill   = be_spill_node(senv, si->spilled_node);
Sebastian Hack's avatar
Sebastian Hack committed
449

Daniel Grund's avatar
Daniel Grund committed
450
#ifdef REMAT
451
			if (check_remat_conditions(senv, spill, si->spilled_node, rld->reloader)) {
452
				new_val = do_remat(senv, si->spilled_node, rld->reloader);
453
				//pdeq_putl(possibly_dead, spill);
454
			}
455
456
457
458
			else
#endif
				/* do a reload */
				new_val = be_reload(aenv, senv->cls, rld->reloader, mode, spill);
Sebastian Hack's avatar
Sebastian Hack committed
459

460
461
			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
462
463
		}

464
465
466
467
		/* 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
468

469
470
		del_pset(values);
	}
Sebastian Hack's avatar
Sebastian Hack committed
471

Daniel Grund's avatar
Daniel Grund committed
472
	del_pset(senv->mem_phis);
473
474
475
476

	// reloads are placed now, but we might reuse the spill environment for further spilling decisions
	del_set(senv->spills);
	senv->spills = new_set(cmp_spillinfo, 1024);
Daniel Grund's avatar
Daniel Grund committed
477
}
Sebastian Hack's avatar
Sebastian Hack committed
478

Daniel Grund's avatar
Daniel Grund committed
479
void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before) {
Sebastian Hack's avatar
Sebastian Hack committed
480
481
482
483
484
485
486
487
488
489
490
491
492
	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
493
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
494
	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
495
	be_add_reload(senv, to_spill, insert_bl);
Sebastian Hack's avatar
Sebastian Hack committed
496
}
497
498
499



Daniel Grund's avatar
Daniel Grund committed
500
/****************************************
501

Daniel Grund's avatar
Daniel Grund committed
502
	SPILL SLOT MANAGEMENT AND OPTS
503

Daniel Grund's avatar
Daniel Grund committed
504
****************************************/
505
506
507

typedef struct _spill_slot_t {
	unsigned size;
508
	unsigned align;
509
	pset *members;
510
	ir_mode *largest_mode;	/* the mode of all members with largest size */
511
512
513
514
515
516
} spill_slot_t;

typedef struct _ss_env_t {
	struct obstack ob;
	be_chordal_env_t *cenv;
	pmap *slots;		/* maps spill_contexts to spill_slots */
517
518
	pmap *types;    /* maps modes to types */
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
519
520
} ss_env_t;

521

522
523
524
/**
 * Walker: compute the spill slots
 */
525
526
527
528
529
530
531
532
533
534
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
535
	ctx = be_get_Spill_context(spill);
536
537
538
	entry = pmap_find(ssenv->slots, ctx);

	if (!entry) {
539
		struct _arch_env_t *arch_env     = ssenv->cenv->birg->main_env->arch_env;
540
		const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val);
541
542
		ir_mode *largest_mode            = arch_register_class_mode(cls);

543
544
		/* this is a new spill context */
		ss = obstack_alloc(&ssenv->ob, sizeof(*ss));
545
546
547
548
		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);
549
550
551
552
		pmap_insert(ssenv->slots, ctx, ss);
	} else {
		/* values with the same spill_ctx must go into the same spill slot */
		ss = entry->value;
553
554
555
556
557
558
559
560

#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));
561
			assert((int) ss->size == size && "Different sizes for the same spill slot are not allowed.");
562
563
564
565
566
			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!");
			}
567
		}
568
#endif /* NDEBUG */
569
570
571
572
573
	}

	pset_insert_ptr(ss->members, spill);
}

574
575
576
/**
 * qsort compare function, sort spill slots by size.
 */
577
static int ss_sorter(const void *v1, const void *v2) {
578
579
	const spill_slot_t **ss1 = (const spill_slot_t **)v1;
	const spill_slot_t **ss2 = (const spill_slot_t **)v2;
580
	return ((int) (*ss2)->size) - ((int) (*ss1)->size);
581
582
583
}


584
585
586
587
588
589
590
591
592
593
594
/**
 * 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
 **/
595
static void optimize_slots(ss_env_t *ssenv, int size, spill_slot_t *ass[]) {
596
597
598
599
600
601
602
603
604
	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 */
605
	qsort(ass, size, sizeof(ass[0]), ss_sorter);
606
607
608
609
610

	/* For each spill slot:
		- assign a new offset to this slot
	    - xor find another slot to coalesce with */
	used_slots = 0;
611
	for (i=0; i<size; ++i) { /* for each spill slot */
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
		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 */
654
655
656
657
		/* 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);
658
	}
659
660
661
662
663
}

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

664
665
666
/**
 * Returns a spill type for a mode. Keep them in a map to reduce
 * the number of types.
667
668
669
670
671
672
673
 *
 * @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.
674
 */
675
676
static ir_type *get_spill_type(pmap *types, spill_slot_t *ss) {
  pmap_entry *e = pmap_find(types, ss->largest_mode);
677
678
679
680
  ir_type *res;

  if (! e) {
		char buf[64];
681
682
683
684
    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);
685
  }
686
  else {
687
    res = e->value;
688
689
		assert(get_type_alignment_bytes(res) == (int)ss->align);
	}
690
691
692
  return res;
}

693
694
695
696
697
698
699
700
701
/**
 * 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;
702
	ir_type *frame = get_irg_frame_type(ssenv->cenv->irg);
703

704
705
706
707
	/* 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);
708

709
	/* create entities and assign offsets according to size and alignment*/
710
	for (i = 0; i < n_slots; ++i) {
711
		char buf[64];
712
		ident *name;
713
714
715
716
717
718
719
		entity *spill_ent;
		ir_node *irn;

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

720
		spill_ent = new_entity(frame, name, get_spill_type(ssenv->types, ss[i]));
721
722
723
724
725
726

		/* align */
		offset = round_up2(offset, ss[i]->align);
		/* set */
		set_entity_offset_bytes(spill_ent, offset);
		/* next possible offset */
727
		offset += round_up2(ss[i]->size, ss[i]->align);
728
729
730
731
732
733

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

	/* set final size of stack frame */
734
735
	frame_align = get_type_alignment_bytes(frame);
	set_type_size_bytes(frame, round_up2(offset, frame_align));
736
737
738
739
}

void be_compute_spill_offsets(be_chordal_env_t *cenv) {
	ss_env_t ssenv;
740
741
742
	spill_slot_t **ss;
	int ss_size;
	pmap_entry *pme;
743
744
745
746

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

750
	/* Get initial spill slots */
751
752
	irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv);

753
754
755
756
757
758
759
760
761
762
	/* 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)
763
	del_pset(((spill_slot_t *)pme->value)->members);
764
	pmap_destroy(ssenv.slots);
765
	pmap_destroy(ssenv.types);
766
	obstack_free(&ssenv.ob, NULL);
767
768

	be_copy_entities_to_reloads(cenv->irg);
769
}