bespill.c 14.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"
Daniel Grund's avatar
Daniel Grund committed
22
23
24
25

#include "besched.h"
#include "bespill.h"
#include "benode_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
26
#include "bechordal_t.h"
Daniel Grund's avatar
Daniel Grund committed
27

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

static int cmp_spillctx(const void *a, const void *b, size_t n) {
Daniel Grund's avatar
Daniel Grund committed
60
61
62
63
64
	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
65
66
67
68
69
70
static int cmp_spillinfo(const void *x, const void *y, size_t size) {
	const spill_info_t *xx = x;
	const spill_info_t *yy = y;
	return ! (xx->spilled_node == yy->spilled_node);
}

Sebastian Hack's avatar
Sebastian Hack committed
71
72
73
74
spill_env_t *be_new_spill_env(firm_dbg_module_t *dbg,
							  const be_chordal_env_t *chordal_env,
							  decide_irn_t is_mem_phi, void *data) {

Sebastian Hack's avatar
Sebastian Hack committed
75
	spill_env_t *env = malloc(sizeof(env[0]));
Sebastian Hack's avatar
Sebastian Hack committed
76
77
78
79
80
81
82
	env->spill_ctxs  = new_set(cmp_spillctx, 1024);
	env->spills      = new_set(cmp_spillinfo, 1024);
	env->cls         = chordal_env->cls;
	env->dbg         = dbg;
	env->is_mem_phi  = is_mem_phi;
	env->data        = data;
	env->chordal_env = chordal_env;
Sebastian Hack's avatar
Sebastian Hack committed
83
84
85
86
	obstack_init(&env->obst);
	return env;
}

Daniel Grund's avatar
Daniel Grund committed
87
void be_delete_spill_env(spill_env_t *senv) {
Sebastian Hack's avatar
Sebastian Hack committed
88
89
90
91
92
93
	del_set(senv->spill_ctxs);
	del_set(senv->spills);
	obstack_free(&senv->obst, NULL);
	free(senv);
}

Daniel Grund's avatar
Daniel Grund committed
94
95
96
97
98
99
100
101
102
103
104
105
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;
106
	DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", irn, ctx_irn));
Daniel Grund's avatar
Daniel Grund committed
107
108
109

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

	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
123
static ir_node *be_spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn) {
Daniel Grund's avatar
Daniel Grund committed
124
125
	int i, n = get_irn_arity(phi);
	ir_node **ins, *bl = get_nodes_block(phi);
Sebastian Hack's avatar
Sebastian Hack committed
126
	ir_graph *irg = senv->chordal_env->irg;
Daniel Grund's avatar
Daniel Grund committed
127
128
129
	spill_ctx_t *ctx;

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

	/* 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 */
		ins  = malloc(n * sizeof(ins[0]));
		for(i=0; i<n; ++i)
			ins[i] = new_r_Unknown(irg, mode_M);
Sebastian Hack's avatar
Sebastian Hack committed
141
		ctx->spill = new_r_Phi(senv->chordal_env->irg, bl, n, ins, mode_M);
Daniel Grund's avatar
Daniel Grund committed
142
143
144
145
146
147
148
		free(ins);

		/* 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
149
150
			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
151
152
153
154
155
156
157
158
159
			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
160
static ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill) {
Daniel Grund's avatar
Daniel Grund committed
161
	ir_node *res;
Daniel Grund's avatar
Daniel Grund committed
162
163
	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
164
165
166
167
168
169
	else
		res = be_spill_irn(senv, to_spill, to_spill);

	return res;
}

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

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

void be_insert_spills_reloads(spill_env_t *senv, pset *reload_set) {
Sebastian Hack's avatar
Sebastian Hack committed
182
	ir_graph *irg = senv->chordal_env->irg;
Daniel Grund's avatar
Daniel Grund committed
183
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
184
185
186
187
188
	spill_info_t *si;
	struct obstack ob;

	obstack_init(&ob);

Daniel Grund's avatar
Daniel Grund committed
189
	/* get all special spilled phis */
Daniel Grund's avatar
Daniel Grund committed
190
191
	DBG((senv->dbg, LEVEL_1, "Mem-phis:\n"));
	senv->mem_phis = pset_new_ptr_default();
Sebastian Hack's avatar
Sebastian Hack committed
192
	irg_walk_graph(senv->chordal_env->irg, phi_walker, NULL, senv);
Daniel Grund's avatar
Daniel Grund committed
193
194

	/* Add reloads for mem_phis */
195
	/* BETTER: These reloads (1) should only be inserted, if they are really needed */
Daniel Grund's avatar
Daniel Grund committed
196
197
198
199
200
201
202
	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
203
204
205
					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
206
207
			}
		}
Daniel Grund's avatar
Daniel Grund committed
208
209
	}

Sebastian Hack's avatar
Sebastian Hack committed
210
	/* process each spilled node */
Daniel Grund's avatar
Daniel Grund committed
211
	DBG((senv->dbg, LEVEL_1, "Insert spills and reloads:\n"));
Sebastian Hack's avatar
Sebastian Hack committed
212
213
214
215
216
217
218
219
220
	for(si = set_first(senv->spills); si; si = set_next(senv->spills)) {
		reloader_t *rld;
		ir_node **reloads;
		int n_reloads = 0;
		ir_mode *mode = get_irn_mode(si->spilled_node);

		/* go through all reloads for this spill */
		for(rld = si->reloaders; rld; rld = rld->next) {
			/* the spill for this reloader */
Daniel Grund's avatar
Daniel Grund committed
221
			ir_node *spill   = be_spill_node(senv, si->spilled_node);
Sebastian Hack's avatar
Sebastian Hack committed
222
223
224

			/* the reload */
			ir_node *bl      = is_Block(rld->reloader) ? rld->reloader : get_nodes_block(rld->reloader);
Sebastian Hack's avatar
Sebastian Hack committed
225
			ir_node *reload  = be_new_Reload(senv->cls, irg, bl, mode, spill);
Sebastian Hack's avatar
Sebastian Hack committed
226

Daniel Grund's avatar
Daniel Grund committed
227
			DBG((senv->dbg, LEVEL_1, " %+F of %+F before %+F\n", reload, si->spilled_node, rld->reloader));
Sebastian Hack's avatar
Sebastian Hack committed
228
229
230
231
232
233
234
235
236
237
			if(reload_set)
				pset_insert_ptr(reload_set, reload);

			/* remember the reaload */
			obstack_ptr_grow(&ob, reload);
			sched_add_before(rld->reloader, reload);
			n_reloads++;
		}

		assert(n_reloads > 0);
238
		obstack_ptr_grow(&ob, si->spilled_node);
Sebastian Hack's avatar
Sebastian Hack committed
239
		reloads = obstack_finish(&ob);
Sebastian Hack's avatar
Sebastian Hack committed
240
		be_ssa_constr_ignore(senv->chordal_env->dom_front, n_reloads + 1, reloads, senv->mem_phis);
Sebastian Hack's avatar
Sebastian Hack committed
241
242
243
244
245
		obstack_free(&ob, reloads);
	}

	obstack_free(&ob, NULL);

Daniel Grund's avatar
Daniel Grund committed
246
	for(irn = pset_first(senv->mem_phis); irn; irn = pset_next(senv->mem_phis)) {
Daniel Grund's avatar
Daniel Grund committed
247
248
		int i, n;
		for(i = 0, n = get_irn_arity(irn); i < n; ++i)
Sebastian Hack's avatar
Sebastian Hack committed
249
			set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg));
Daniel Grund's avatar
Daniel Grund committed
250
251
		sched_remove(irn);
	}
Daniel Grund's avatar
Daniel Grund committed
252

Daniel Grund's avatar
Daniel Grund committed
253
	del_pset(senv->mem_phis);
Daniel Grund's avatar
Daniel Grund committed
254
}
Sebastian Hack's avatar
Sebastian Hack committed
255

Daniel Grund's avatar
Daniel Grund committed
256
void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before) {
Sebastian Hack's avatar
Sebastian Hack committed
257
258
259
260
261
262
263
264
265
266
267
268
269
	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
270
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
271
	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
272
	be_add_reload(senv, to_spill, insert_bl);
Sebastian Hack's avatar
Sebastian Hack committed
273
}
274
275
276



Daniel Grund's avatar
Daniel Grund committed
277
/****************************************
278

Daniel Grund's avatar
Daniel Grund committed
279
	SPILL SLOT MANAGEMENT AND OPTS
280

Daniel Grund's avatar
Daniel Grund committed
281
****************************************/
282
283
284

typedef struct _spill_slot_t {
	unsigned size;
285
	unsigned align;
286
	pset *members;
287
	ir_mode *largest_mode;	/* the mode of all members with largest size */
288
289
290
291
292
293
294
} spill_slot_t;

typedef struct _ss_env_t {
	firm_dbg_module_t *dbg;
	struct obstack ob;
	be_chordal_env_t *cenv;
	pmap *slots;		/* maps spill_contexts to spill_slots */
295
  pmap *types;    /* maps modes to types */
296
297
298
299
300
301
302
303
304
305
306
307
308
} ss_env_t;


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

	if (!be_is_Spill(spill))
		return;

	/* check, if this spill is for a context already known */
Sebastian Hack's avatar
Sebastian Hack committed
309
	ctx = be_get_Spill_context(spill);
310
311
312
313
314
315
	entry = pmap_find(ssenv->slots, ctx);

	if (!entry) {
		/* this is a new spill context */
		ss = obstack_alloc(&ssenv->ob, sizeof(*ss));
		ss->members = pset_new_ptr(8);
316
317
318
		ss->largest_mode = get_irn_mode(get_irn_n(spill, 0));
		ss->size = get_mode_size_bytes(ss->largest_mode);
		ss->align = ss->size; /* TODO Assumed for now */
319
320
321
322
323
		pmap_insert(ssenv->slots, ctx, ss);
	} else {
		ir_node *irn;
		/* values with the same spill_ctx must go into the same spill slot */
		ss = entry->value;
324
		assert(ss->size == (unsigned)get_mode_size_bytes(get_irn_mode(get_irn_n(spill, 0))) && "Different sizes for the same spill slot are not allowed yet.");
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
		for (irn = pset_first(ss->members); irn; irn = pset_next(ss->members)) {
			/* use values_interfere here, because it uses the dominance check,
			   which does work for values in memory */
			assert(!values_interfere(spill, irn) && "Spills for the same spill slot must not interfere!");
		}
	}

	pset_insert_ptr(ss->members, spill);
}

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


342
343
344
345
346
347
348
349
350
351
352
353
/**
 * 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) {
354
355
356
357
358
359
360
361
362
	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 */
363
	qsort(ass, size, sizeof(ass[0]), ss_sorter);
364
365
366
367
368

	/* For each spill slot:
		- assign a new offset to this slot
	    - xor find another slot to coalesce with */
	used_slots = 0;
369
	for (i=0; i<size; ++i) { /* for each spill slot */
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
		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 */
412
413
414
415
		/* 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);
416
	}
417
418
419
420
421
}

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

422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
/**
 * Returns a spill type for a mode. Keep them in a map to reduce
 * the number of types.
 */
static ir_type *get_spill_type(pmap *types, ir_mode *mode) {
  pmap_entry *e = pmap_find(types, mode);
  ir_type *res;

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

441
442
443
static void assign_entities(ss_env_t *ssenv, int n, spill_slot_t **ss) {
	int i, offset;
	ir_type *frame = get_irg_frame_type(ssenv->cenv->irg);
444

445
446
447
448
	/* 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);
449

450
451
452
	/* create entities and assign offsets according to size and alignment*/
	for (i=0; i<n; ++i) {
		char buf[64];
453
		ident *name;
454
455
456
457
458
459
460
		entity *spill_ent;
		ir_node *irn;

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

461
		spill_ent = new_entity(frame, name, get_spill_type(ssenv->types, ss[i]->largest_mode));
462
463
464
465
466
467
468
469
470
471
472
473
474
475

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

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

	/* set final size of stack frame */
	set_type_size_bytes(frame, offset);
476
477
478
479
}

void be_compute_spill_offsets(be_chordal_env_t *cenv) {
	ss_env_t ssenv;
480
481
482
	spill_slot_t **ss;
	int ss_size;
	pmap_entry *pme;
483
484
485
486

	obstack_init(&ssenv.ob);
	ssenv.cenv  = cenv;
	ssenv.slots = pmap_create();
487
  ssenv.types = pmap_create();
488
489
	ssenv.dbg   = firm_dbg_register("ir.be.spillslots");

490
	/* Get initial spill slots */
491
492
	irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv);

493
494
495
496
497
498
499
500
501
502
503
	/* 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)
		del_pset(((spill_slot_t *)pme->value)->members);
504
	pmap_destroy(ssenv.slots);
505
  pmap_destroy(ssenv.types);
506
507
	obstack_free(&ssenv.ob, NULL);
}