bespill.c 22.5 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
};

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
spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env, decide_irn_t is_mem_phi, void *data) {
108
	spill_env_t *env = xmalloc(sizeof(env[0]));
Sebastian Hack's avatar
Sebastian Hack committed
109
110
111
112
113
114
	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
115
116
117
118
	obstack_init(&env->obst);
	return env;
}

119
/* Deletes a spill environment. */
Daniel Grund's avatar
Daniel Grund committed
120
void be_delete_spill_env(spill_env_t *senv) {
Sebastian Hack's avatar
Sebastian Hack committed
121
122
123
124
125
126
	del_set(senv->spill_ctxs);
	del_set(senv->spills);
	obstack_free(&senv->obst, NULL);
	free(senv);
}

127
128
129
130
131
132
133
134
135
/**
 * 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
136
137
138
139
140
141
142
143
144
145
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)));
}

146
147
148
149
150
151
152
153
154
/**
 * 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
155
156
static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *ctx_irn) {
	spill_ctx_t *ctx;
157
	DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", irn, ctx_irn));
Daniel Grund's avatar
Daniel Grund committed
158
159
160

	ctx = be_get_spill_ctx(senv->spill_ctxs, irn, ctx_irn);
	if(!ctx->spill) {
Sebastian Hack's avatar
Sebastian Hack committed
161
		const be_main_env_t *env = senv->chordal_env->birg->main_env;
Sebastian Hack's avatar
Sebastian Hack committed
162
		ctx->spill = be_spill(env->arch_env, irn, ctx_irn);
Daniel Grund's avatar
Daniel Grund committed
163
164
165
166
167
168
	}

	return ctx->spill;
}

/**
169
 * If the first usage of a Phi result would be out of memory
Daniel Grund's avatar
Daniel Grund committed
170
171
172
 * 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
173
174
175
176
177
178
 *
 * @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
179
 */
180
static ir_node *be_spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn, unsigned visited_nr, set *already_visited_phis) {
Christian Würdig's avatar
Christian Würdig committed
181
182
183
184
185
	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
186
187
188
	spill_ctx_t *ctx;

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

Christian Würdig's avatar
Christian Würdig committed
191
192
193
	/* build a new PhiM */
	NEW_ARR_A(ir_node *, ins, n);
	for (i = 0; i < n; ++i) {
194
		ins[i]    = new_r_Bad(irg);
Christian Würdig's avatar
Christian Würdig committed
195
196
197
198
	}
	phi_spill = new_r_Phi(senv->chordal_env->irg, bl, n, ins, mode_M);
	key.phi   = phi;
	key.spill = phi_spill;
199
	set_insert(already_visited_phis, &key, sizeof(key), HASH_PTR(phi));
Christian Würdig's avatar
Christian Würdig committed
200

Daniel Grund's avatar
Daniel Grund committed
201
202
203
204
	/* 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
205
206
207
208
209
	if (! ctx->spill) {
        set_irn_visited(phi, visited_nr);

		/* collect all arguments of the phi */
		for (i = 0; i < n; ++i) {
Daniel Grund's avatar
Daniel Grund committed
210
211
			ir_node *arg = get_irn_n(phi, i);
			ir_node *sub_res;
Christian Würdig's avatar
Christian Würdig committed
212
213
214
215
216
217
218
219
220
			phi_spill_assoc_t *entry;

			if(is_Phi(arg) && pset_find_ptr(senv->mem_phis, arg)) {
				if (get_irn_visited(arg) < visited_nr)
					sub_res = be_spill_phi(senv, arg, ctx_irn, visited_nr, already_visited_phis);
				else {
					/* we already visited the argument phi: get it's spill */
					key.phi   = arg;
					key.spill = NULL;
221
					entry     = set_find(already_visited_phis, &key, sizeof(key), HASH_PTR(arg));
Christian Würdig's avatar
Christian Würdig committed
222
223
					assert(entry && "argument phi already visited, but no spill found?!?");
					sub_res   = entry->spill;
224
					assert(sub_res && "spill missing?!?");
Christian Würdig's avatar
Christian Würdig committed
225
226
				}
			}
Daniel Grund's avatar
Daniel Grund committed
227
228
			else
				sub_res = be_spill_irn(senv, arg, ctx_irn);
Christian Würdig's avatar
Christian Würdig committed
229
230

			set_irn_n(phi_spill, i, sub_res);
Daniel Grund's avatar
Daniel Grund committed
231
		}
Christian Würdig's avatar
Christian Würdig committed
232
233

		ctx->spill = phi_spill;
Daniel Grund's avatar
Daniel Grund committed
234
235
236
237
	}
	return ctx->spill;
}

238
239
240
241
242
243
244
245
246
/**
 * 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
 */
Christian Würdig's avatar
Christian Würdig committed
247
248
249
250
static ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill, unsigned visited_nr) {
	ir_graph *irg                  = get_irn_irg(to_spill);
	int      save_optimize         = get_optimize();
	int      save_normalize        = get_opt_normalize();
251
	set      *already_visited_phis = new_set(cmp_phi_spill_assoc, 10);
Daniel Grund's avatar
Daniel Grund committed
252
	ir_node *res;
Christian Würdig's avatar
Christian Würdig committed
253
254
255
256
257
258
259
260

	/*
	 * Disable optimization so that the phi functions do not
	 * disappear.
	 */
	set_optimize(0);
	set_opt_normalize(0);

Daniel Grund's avatar
Daniel Grund committed
261
	if (pset_find_ptr(senv->mem_phis, to_spill))
Christian Würdig's avatar
Christian Würdig committed
262
		res = be_spill_phi(senv, to_spill, to_spill, visited_nr, already_visited_phis);
Daniel Grund's avatar
Daniel Grund committed
263
264
265
	else
		res = be_spill_irn(senv, to_spill, to_spill);

266
	del_set(already_visited_phis);
Christian Würdig's avatar
Christian Würdig committed
267
268
269
270
271

	/* reset the optimizations */
	set_optimize(save_optimize);
	set_opt_normalize(save_normalize);

Daniel Grund's avatar
Daniel Grund committed
272
273
274
	return res;
}

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

#ifdef BUGGY_REMAT

279
280
281
282
283
284
285
286
/**
 * 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
 */
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
338
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
339
340
#else /* BUGGY_REMAT */

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

359
360
361
#endif /* REMAT */

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

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

393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
/**
 * 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
410
void be_insert_spills_reloads(spill_env_t *senv, pset *reload_set) {
411
412
	const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env;
	ir_graph *irg          = senv->chordal_env->irg;
Christian Würdig's avatar
Christian Würdig committed
413
	unsigned visited_nr;
Daniel Grund's avatar
Daniel Grund committed
414
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
415
	spill_info_t *si;
416
	pdeq *possibly_dead;
Sebastian Hack's avatar
Sebastian Hack committed
417

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

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

Christian Würdig's avatar
Christian Würdig committed
439
440
441
	visited_nr = get_irg_visited(irg) + 1;
	set_irg_visited(irg, visited_nr);

Sebastian Hack's avatar
Sebastian Hack committed
442
	/* process each spilled node */
Daniel Grund's avatar
Daniel Grund committed
443
	DBG((senv->dbg, LEVEL_1, "Insert spills and reloads:\n"));
444
	possibly_dead = new_pdeq();
Sebastian Hack's avatar
Sebastian Hack committed
445
446
447
	for(si = set_first(senv->spills); si; si = set_next(senv->spills)) {
		reloader_t *rld;
		ir_mode *mode = get_irn_mode(si->spilled_node);
448
		pset *values = pset_new_ptr(16);
Sebastian Hack's avatar
Sebastian Hack committed
449
450
451

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

Sebastian Hack's avatar
Sebastian Hack committed
454
			/* the spill for this reloader */
Christian Würdig's avatar
Christian Würdig committed
455
			ir_node *spill   = be_spill_node(senv, si->spilled_node, visited_nr);
Sebastian Hack's avatar
Sebastian Hack committed
456

Daniel Grund's avatar
Daniel Grund committed
457
#ifdef REMAT
458
			if (check_remat_conditions(senv, spill, si->spilled_node, rld->reloader)) {
459
				new_val = do_remat(senv, si->spilled_node, rld->reloader);
460
461
				pdeq_putl(possibly_dead, spill);
			}
462
463
464
465
			else
#endif
				/* do a reload */
				new_val = be_reload(aenv, senv->cls, rld->reloader, mode, spill);
Sebastian Hack's avatar
Sebastian Hack committed
466

467
468
			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
469
			if(reload_set)
470
				pset_insert_ptr(reload_set, new_val);
Sebastian Hack's avatar
Sebastian Hack committed
471
472
		}

473
474
475
476
		/* 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
477

478
479
		del_pset(values);
	}
Sebastian Hack's avatar
Sebastian Hack committed
480

481
	foreach_pset(senv->mem_phis, irn) {
Daniel Grund's avatar
Daniel Grund committed
482
		int i, n;
483
484
		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
485
			set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg));
486
		}
Daniel Grund's avatar
Daniel Grund committed
487
488
		sched_remove(irn);
	}
Daniel Grund's avatar
Daniel Grund committed
489

490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
	/* 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
505
	del_pset(senv->mem_phis);
Daniel Grund's avatar
Daniel Grund committed
506
}
Sebastian Hack's avatar
Sebastian Hack committed
507

Daniel Grund's avatar
Daniel Grund committed
508
void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before) {
Sebastian Hack's avatar
Sebastian Hack committed
509
510
511
512
513
514
515
516
517
518
519
520
521
	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
522
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
523
	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
524
	be_add_reload(senv, to_spill, insert_bl);
Sebastian Hack's avatar
Sebastian Hack committed
525
}
526
527
528



Daniel Grund's avatar
Daniel Grund committed
529
/****************************************
530

Daniel Grund's avatar
Daniel Grund committed
531
	SPILL SLOT MANAGEMENT AND OPTS
532

Daniel Grund's avatar
Daniel Grund committed
533
****************************************/
534
535
536

typedef struct _spill_slot_t {
	unsigned size;
537
	unsigned align;
538
	pset *members;
539
	ir_mode *largest_mode;	/* the mode of all members with largest size */
540
541
542
543
544
545
} spill_slot_t;

typedef struct _ss_env_t {
	struct obstack ob;
	be_chordal_env_t *cenv;
	pmap *slots;		/* maps spill_contexts to spill_slots */
546
547
	pmap *types;    /* maps modes to types */
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
548
549
} ss_env_t;

550

551
552
553
/**
 * Walker: compute the spill slots
 */
554
555
556
557
558
559
560
561
562
563
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
564
	ctx = be_get_Spill_context(spill);
565
566
567
	entry = pmap_find(ssenv->slots, ctx);

	if (!entry) {
568
		struct _arch_env_t *arch_env     = ssenv->cenv->birg->main_env->arch_env;
569
		const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val);
570
571
		ir_mode *largest_mode            = arch_register_class_mode(cls);

572
573
		/* this is a new spill context */
		ss = obstack_alloc(&ssenv->ob, sizeof(*ss));
574
575
576
577
		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);
578
579
580
581
		pmap_insert(ssenv->slots, ctx, ss);
	} else {
		/* values with the same spill_ctx must go into the same spill slot */
		ss = entry->value;
582
583
584
585
586
587
588
589
590
591
592
593
594
595

#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!");
			}
596
		}
597
#endif /* NDEBUG */
598
599
600
601
602
	}

	pset_insert_ptr(ss->members, spill);
}

603
604
605
/**
 * qsort compare function, sort spill slots by size.
 */
606
static int ss_sorter(const void *v1, const void *v2) {
607
608
	const spill_slot_t **ss1 = (const spill_slot_t **)v1;
	const spill_slot_t **ss2 = (const spill_slot_t **)v2;
609
	return ((int) (*ss2)->size) - ((int) (*ss1)->size);
610
611
612
}


613
614
615
616
617
618
619
620
621
622
623
/**
 * 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
 **/
624
static void optimize_slots(ss_env_t *ssenv, int size, spill_slot_t *ass[]) {
625
626
627
628
629
630
631
632
633
	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 */
634
	qsort(ass, size, sizeof(ass[0]), ss_sorter);
635
636
637
638
639

	/* For each spill slot:
		- assign a new offset to this slot
	    - xor find another slot to coalesce with */
	used_slots = 0;
640
	for (i=0; i<size; ++i) { /* for each spill slot */
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
		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 */
683
684
685
686
		/* 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);
687
	}
688
689
690
691
692
}

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

693
694
695
/**
 * Returns a spill type for a mode. Keep them in a map to reduce
 * the number of types.
696
697
698
699
700
701
702
 *
 * @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.
703
 */
704
705
static ir_type *get_spill_type(pmap *types, spill_slot_t *ss) {
  pmap_entry *e = pmap_find(types, ss->largest_mode);
706
707
708
709
  ir_type *res;

  if (! e) {
		char buf[64];
710
711
712
713
    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);
714
  }
715
  else {
716
    res = e->value;
717
718
		assert(get_type_alignment_bytes(res) == (int)ss->align);
	}
719
720
721
  return res;
}

722
723
724
725
726
727
728
729
730
/**
 * 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;
731
	ir_type *frame = get_irg_frame_type(ssenv->cenv->irg);
732

733
734
735
736
	/* 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);
737

738
	/* create entities and assign offsets according to size and alignment*/
739
	for (i = 0; i < n_slots; ++i) {
740
		char buf[64];
741
		ident *name;
742
743
744
745
746
747
748
		entity *spill_ent;
		ir_node *irn;

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

749
		spill_ent = new_entity(frame, name, get_spill_type(ssenv->types, ss[i]));
750
751
752
753
754
755

		/* align */
		offset = round_up2(offset, ss[i]->align);
		/* set */
		set_entity_offset_bytes(spill_ent, offset);
		/* next possible offset */
756
		offset += round_up2(ss[i]->size, ss[i]->align);
757
758
759
760
761
762

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

	/* set final size of stack frame */
763
764
	frame_align = get_type_alignment_bytes(frame);
	set_type_size_bytes(frame, round_up2(offset, frame_align));
765
766
767
768
}

void be_compute_spill_offsets(be_chordal_env_t *cenv) {
	ss_env_t ssenv;
769
770
771
	spill_slot_t **ss;
	int ss_size;
	pmap_entry *pme;
772
773
774
775

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

779
	/* Get initial spill slots */
780
781
	irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv);

782
783
784
785
786
787
788
789
790
791
	/* 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)
792
	del_pset(((spill_slot_t *)pme->value)->members);
793
	pmap_destroy(ssenv.slots);
794
	pmap_destroy(ssenv.types);
795
	obstack_free(&ssenv.ob, NULL);
796
797

	be_copy_entities_to_reloads(cenv->irg);
798
}