bespill.c 26.3 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
21
/**
 * @file
Matthias Braun's avatar
Matthias Braun committed
22
 * @brief       implementation of the spill/reload placement abstraction layer
23
24
25
 * @author      Daniel Grund, Sebastian Hack, Matthias Braun
 * @date		29.09.2005
 * @version     $Id$
Daniel Grund's avatar
Daniel Grund committed
26
 */
Christian Würdig's avatar
Christian Würdig committed
27
#ifdef HAVE_CONFIG_H
28
#include "config.h"
Christian Würdig's avatar
Christian Würdig committed
29
#endif
Daniel Grund's avatar
Daniel Grund committed
30

31
32
#include <stdlib.h>

Daniel Grund's avatar
Daniel Grund committed
33
34
35
#include "pset.h"
#include "irnode_t.h"
#include "ircons_t.h"
Daniel Grund's avatar
Daniel Grund committed
36
#include "iredges_t.h"
37
#include "irbackedge_t.h"
Christian Würdig's avatar
Christian Würdig committed
38
#include "irprintf.h"
39
40
41
#include "ident_t.h"
#include "type_t.h"
#include "entity_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
42
#include "debug.h"
Michael Beck's avatar
Michael Beck committed
43
#include "irgwalk.h"
44
#include "array.h"
45
#include "pdeq.h"
Matthias Braun's avatar
Matthias Braun committed
46
#include "execfreq.h"
47
#include "irnodeset.h"
Daniel Grund's avatar
Daniel Grund committed
48

49
#include "bearch_t.h"
50
51
#include "belive_t.h"
#include "besched_t.h"
Daniel Grund's avatar
Daniel Grund committed
52
#include "bespill.h"
Matthias Braun's avatar
Matthias Braun committed
53
#include "belive_t.h"
Daniel Grund's avatar
Daniel Grund committed
54
#include "benode_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
55
#include "bechordal_t.h"
Matthias Braun's avatar
Matthias Braun committed
56
#include "bejavacoal.h"
57
#include "benodesets.h"
58
59
#include "bespilloptions.h"
#include "bestatevent.h"
60
#include "bessaconstr.h"
Christian Würdig's avatar
Christian Würdig committed
61
#include "beirg_t.h"
62
#include "beintlive_t.h"
63
64
65
#include "bemodule.h"

DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
Daniel Grund's avatar
Daniel Grund committed
66

67
#define REMAT_COST_INFINITE  1000
Sebastian Hack's avatar
Sebastian Hack committed
68

69
70
typedef struct reloader_t reloader_t;
struct reloader_t {
Sebastian Hack's avatar
Sebastian Hack committed
71
	reloader_t *next;
72
	ir_node    *can_spill_after;
73
74
	ir_node    *reloader;
	ir_node    *rematted_node;
75
76
	int         remat_cost_delta; /** costs needed for rematerialization,
	                                   compared to placing a reload */
Sebastian Hack's avatar
Sebastian Hack committed
77
78
};

79
80
typedef struct spill_info_t spill_info_t;
struct spill_info_t {
Matthias Braun's avatar
Matthias Braun committed
81
82
83
84
85
86
87
88
89
	ir_node    *to_spill;  /**< the value that should get spilled */
	reloader_t *reloaders; /**< list of places where the value should get
	                            reloaded */
	ir_node    *spill;     /**< the spill node, or a PhiM node */
	ir_node    *old_spill; /**< if we had the value of a phi spilled before but
	                            not the phi itself then this field contains the
	                            spill for the phi value */
	const arch_register_class_t *reload_cls; /** the register class in which the
	                                             reload should be placed */
90
};
Daniel Grund's avatar
Daniel Grund committed
91

92
struct spill_env_t {
93
	const arch_env_t *arch_env;
Matthias Braun's avatar
Matthias Braun committed
94
95
96
97
98
99
100
101
102
103
	ir_graph         *irg;
	struct obstack    obst;
	be_irg_t         *birg;
	int               spill_cost;     /**< the cost of a single spill node */
	int               reload_cost;    /**< the cost of a reload node */
	set              *spills;         /**< all spill_info_t's, which must be
	                                       placed */
	ir_nodeset_t      mem_phis;       /**< set of all spilled phis. */
	ir_exec_freq     *exec_freq;

104
#ifdef FIRM_STATISTICS
Matthias Braun's avatar
Matthias Braun committed
105
106
107
108
	unsigned          spill_count;
	unsigned          reload_count;
	unsigned          remat_count;
	unsigned          spilled_phi_count;
109
#endif
Sebastian Hack's avatar
Sebastian Hack committed
110
111
};

112
113
114
/**
 * Compare two spill infos.
 */
Matthias Braun's avatar
Matthias Braun committed
115
116
117
static
int cmp_spillinfo(const void *x, const void *y, size_t size)
{
Sebastian Hack's avatar
Sebastian Hack committed
118
119
	const spill_info_t *xx = x;
	const spill_info_t *yy = y;
120
121
	(void) size;

122
	return xx->to_spill != yy->to_spill;
Sebastian Hack's avatar
Sebastian Hack committed
123
124
}

Matthias Braun's avatar
Matthias Braun committed
125
126
127
/**
 * Returns spill info for a specific value (the value that is to be spilled)
 */
Matthias Braun's avatar
Matthias Braun committed
128
129
static
spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value)
130
{
Matthias Braun's avatar
Matthias Braun committed
131
	spill_info_t info, *res;
132
	int hash = nodeset_hash(value);
Matthias Braun's avatar
Matthias Braun committed
133

134
	info.to_spill = value;
Matthias Braun's avatar
Matthias Braun committed
135
136
137
138
139
	res = set_find(env->spills, &info, sizeof(info), hash);

	if (res == NULL) {
		info.reloaders = NULL;
		info.spill = NULL;
140
		info.old_spill = NULL;
141
		info.reload_cls = NULL;
Matthias Braun's avatar
Matthias Braun committed
142
143
144
145
146
147
		res = set_insert(env->spills, &info, sizeof(info), hash);
	}

	return res;
}

148
149
150
151
spill_env_t *be_new_spill_env(be_irg_t *birg)
{
	const arch_env_t *arch_env = birg->main_env->arch_env;

152
153
	spill_env_t *env	= xmalloc(sizeof(env[0]));
	env->spills			= new_set(cmp_spillinfo, 1024);
154
155
	env->irg            = be_get_birg_irg(birg);
	env->birg           = birg;
156
	env->arch_env       = arch_env;
157
	ir_nodeset_init(&env->mem_phis);
158
159
	env->spill_cost     = arch_env->isa->spill_cost;
	env->reload_cost    = arch_env->isa->reload_cost;
Matthias Braun's avatar
Matthias Braun committed
160
	env->exec_freq      = be_get_birg_exec_freq(birg);
Sebastian Hack's avatar
Sebastian Hack committed
161
	obstack_init(&env->obst);
Matthias Braun's avatar
Matthias Braun committed
162

163
164
165
166
167
168
169
#ifdef FIRM_STATISTICS
	env->spill_count       = 0;
	env->reload_count      = 0;
	env->remat_count       = 0;
	env->spilled_phi_count = 0;
#endif

Sebastian Hack's avatar
Sebastian Hack committed
170
171
172
	return env;
}

173
174
void be_delete_spill_env(spill_env_t *env)
{
175
	del_set(env->spills);
176
	ir_nodeset_destroy(&env->mem_phis);
177
178
	obstack_free(&env->obst, NULL);
	free(env);
Sebastian Hack's avatar
Sebastian Hack committed
179
180
}

181
/*
182
183
184
185
186
187
188
189
 *  ____  _                  ____      _                 _
 * |  _ \| | __ _  ___ ___  |  _ \ ___| | ___   __ _  __| |___
 * | |_) | |/ _` |/ __/ _ \ | |_) / _ \ |/ _ \ / _` |/ _` / __|
 * |  __/| | (_| | (_|  __/ |  _ <  __/ | (_) | (_| | (_| \__ \
 * |_|   |_|\__,_|\___\___| |_| \_\___|_|\___/ \__,_|\__,_|___/
 *
 */

190
191
192
void be_add_remat(spill_env_t *env, ir_node *to_spill, ir_node *before,
                  ir_node *rematted_node)
{
193
194
195
196
197
	spill_info_t *spill_info;
	reloader_t *reloader;

	spill_info = get_spillinfo(env, to_spill);

198
199
200
201
	/* add the remat information */
	reloader                = obstack_alloc(&env->obst, sizeof(reloader[0]));
	reloader->next          = spill_info->reloaders;
	reloader->reloader      = before;
202
	reloader->rematted_node = rematted_node;
Matthias Braun's avatar
Matthias Braun committed
203
204
205
	reloader->remat_cost_delta = 0; /* We will never have a cost win over a
	                                   reload since we're not even allowed to
	                                   create a reload */
206

207
	spill_info->reloaders  = reloader;
Christian Würdig's avatar
Christian Würdig committed
208

209
	DBG((dbg, LEVEL_1, "creating spillinfo for %+F, will be rematerialized before %+F\n",
Christian Würdig's avatar
Christian Würdig committed
210
		to_spill, before));
211
212
}

213
void be_add_reload2(spill_env_t *env, ir_node *to_spill, ir_node *before, ir_node *can_spill_after,
214
                   const arch_register_class_t *reload_cls, int allow_remat)
215
{
216
217
218
219
220
	spill_info_t *info;
	reloader_t *rel;

	info = get_spillinfo(env, to_spill);

221
	if (is_Phi(to_spill)) {
222
		int i, arity;
223
224
225

		/* create spillinfos for the phi arguments */
		for (i = 0, arity = get_irn_arity(to_spill); i < arity; ++i) {
226
227
228
			ir_node *arg = get_irn_n(to_spill, i);
			get_spillinfo(env, arg);
		}
229
230

#if 1
231
232
233
234
235
		/* hackery... sometimes the morgan algo spilled the value of a phi,
		 * the belady algo decides later to spill the whole phi, then sees the
		 * spill node and adds a reload for that spill node, problem is the
		 * reload gets attach to that same spill (and is totally unnecessary)
		 */
236
		if (info->old_spill != NULL &&
237
238
			(before == info->old_spill || value_dominates(before, info->old_spill)))
		{
239
240
241
242
			printf("spilledphi hack was needed...\n");
			before = sched_next(info->old_spill);
		}
#endif
243
244
	}

Matthias Braun's avatar
Matthias Braun committed
245
246
	assert(!is_Proj(before) && !be_is_Keep(before));

247
	/* put reload into list */
248
249
250
251
252
253
	rel                   = obstack_alloc(&env->obst, sizeof(rel[0]));
	rel->next             = info->reloaders;
	rel->reloader         = before;
	rel->rematted_node    = NULL;
	rel->can_spill_after  = can_spill_after;
	rel->remat_cost_delta = allow_remat ? 0 : REMAT_COST_INFINITE;
254
255

	info->reloaders  = rel;
256
	assert(info->reload_cls == NULL || info->reload_cls == reload_cls);
257
	info->reload_cls = reload_cls;
Christian Würdig's avatar
Christian Würdig committed
258

259
	DBG((dbg, LEVEL_1, "creating spillinfo for %+F, will be reloaded before %+F, may%s be rematerialized\n",
Christian Würdig's avatar
Christian Würdig committed
260
		to_spill, before, allow_remat ? "" : " not"));
261
262
}

263
264
265
266
267
268
269
void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before,
                   const arch_register_class_t *reload_cls, int allow_remat)
{
	be_add_reload2(senv, to_spill, before, to_spill, reload_cls, allow_remat);

}

Sebastian Hack's avatar
Sebastian Hack committed
270
ir_node *be_get_end_of_block_insertion_point(const ir_node *block)
Sebastian Hack's avatar
Sebastian Hack committed
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
{
	ir_node *last = sched_last(block);

	/* we might have projs and keepanys behind the jump... */
	while(is_Proj(last) || be_is_Keep(last)) {
		last = sched_prev(last);
		assert(!sched_is_end(last));
	}

	if(!is_cfop(last)) {
		last = sched_next(last);
		/* last node must be a cfop, only exception is the start block */
		assert(last	== get_irg_start_block(get_irn_irg(block)));
	}

	/* add the reload before the (cond-)jump */
	return last;
}

290
291
292
293
/**
 * Returns the point at which you can insert a node that should be executed
 * before block @p block when coming from pred @p pos.
 */
Matthias Braun's avatar
Matthias Braun committed
294
295
296
static
ir_node *get_block_insertion_point(ir_node *block, int pos)
{
Sebastian Hack's avatar
Sebastian Hack committed
297
	ir_node *predblock;
298

299
300
301
	/* simply add the reload to the beginning of the block if we only have 1
	 * predecessor. We don't need to check for phis as there can't be any in a
	 * block with only 1 pred. */
302
303
	if(get_Block_n_cfgpreds(block) == 1) {
		assert(!is_Phi(sched_first(block)));
304
		return sched_first(block);
305
306
307
308
	}

	/* We have to reload the value in pred-block */
	predblock = get_Block_cfgpred_block(block, pos);
Sebastian Hack's avatar
Sebastian Hack committed
309
	return be_get_end_of_block_insertion_point(predblock);
Sebastian Hack's avatar
Sebastian Hack committed
310
}
311

Sebastian Hack's avatar
Sebastian Hack committed
312
void be_add_reload_at_end(spill_env_t *env, ir_node *to_spill, const ir_node *block,
Sebastian Hack's avatar
Sebastian Hack committed
313
314
315
                          const arch_register_class_t *reload_cls,
                          int allow_remat)
{
Sebastian Hack's avatar
Sebastian Hack committed
316
	ir_node *before = be_get_end_of_block_insertion_point(block);
Sebastian Hack's avatar
Sebastian Hack committed
317
	be_add_reload(env, to_spill, before, reload_cls, allow_remat);
318
319
}

320
321
322
void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block,
                           int pos,	const arch_register_class_t *reload_cls,
                           int allow_remat)
323
{
324
	ir_node *before = get_block_insertion_point(block, pos);
325
	be_add_reload(env, to_spill, before, reload_cls, allow_remat);
326
327
}

328
329
void be_spill_phi(spill_env_t *env, ir_node *node)
{
Sebastian Hack's avatar
Sebastian Hack committed
330
	spill_info_t* spill;
331
332
333
334
	int i, arity;

	assert(is_Phi(node));

335
	ir_nodeset_insert(&env->mem_phis, node);
336

337
	/* create spillinfos for the phi arguments */
Sebastian Hack's avatar
Sebastian Hack committed
338
	spill = get_spillinfo(env, node);
339
340
341
342
	for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
		ir_node *arg = get_irn_n(node, i);
		get_spillinfo(env, arg);
	}
343

344
345
346
	/* if we had a spill for the phi value before, then remove this spill from
	 * schedule, as we will remove it in the insert spill/reload phase
	 */
347
	if(spill->spill != NULL && !is_Phi(spill->spill)) {
348
		assert(spill->old_spill == NULL);
349
350
351
		spill->old_spill = spill->spill;
		spill->spill = NULL;
	}
352
353
354
355
356
357
358
359
360
361
362
}

/*
 *   ____                _         ____        _ _ _
 *  / ___|_ __ ___  __ _| |_ ___  / ___| _ __ (_) | |___
 * | |   | '__/ _ \/ _` | __/ _ \ \___ \| '_ \| | | / __|
 * | |___| | |  __/ (_| | ||  __/  ___) | |_) | | | \__ \
 *  \____|_|  \___|\__,_|\__\___| |____/| .__/|_|_|_|___/
 *                                      |_|
 */

363
/**
364
365
366
 * Schedules a node after an instruction. That is the place after all projs and
 * phis that are scheduled after the instruction. This function also skips phi
 * nodes at the beginning of a block
367
 */
368
369
370
static
void sched_add_after_insn(ir_node *sched_after, ir_node *node)
{
371
	ir_node *next = sched_next(sched_after);
Matthias Braun's avatar
Matthias Braun committed
372
	while(is_Proj(next) || is_Phi(next) || be_is_Keep(next)) {
373
374
		next = sched_next(next);
	}
375
	assert(next != NULL);
376
377

	if(sched_is_end(next)) {
378
		sched_add_after(sched_last(get_nodes_block(sched_after)), node);
379
380
381
382
383
	} else {
		sched_add_before(next, node);
	}
}

384
385
386
387
388
389
390
391
392
/**
 * 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
 */
393
394
395
396
397
static
void spill_irn(spill_env_t *env, spill_info_t *spillinfo)
{
	optimization_state_t  opt;
	ir_node              *to_spill = spillinfo->to_spill;
Daniel Grund's avatar
Daniel Grund committed
398

399
	DBG((dbg, LEVEL_1, "spilling %+F ... ", to_spill));
400
401
402

	/* 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
403
	 *
404
405
	 * Normally reloads get simply rematerialized instead of spilled again; this
	 * can happen annyway when the reload is the pred of a phi to spill)
406
	 */
407
	if (be_is_Reload(to_spill)) {
Matthias Braun's avatar
Matthias Braun committed
408
		spillinfo->spill = get_irn_n(to_spill, be_pos_Reload_mem);
409
		DB((dbg, LEVEL_1, "skip reload, using existing spill %+F\n", spillinfo->spill));
Matthias Braun's avatar
Matthias Braun committed
410
		return;
Daniel Grund's avatar
Daniel Grund committed
411
412
	}

413
414
415
416
417
418
419
	assert(!(arch_irn_is(env->arch_env, to_spill, dont_spill)
				&& "Attempt to spill a node marked 'dont_spill'"));

	/* some backends have virtual noreg/unknown nodes that are not scheduled */
	if(!sched_is_scheduled(to_spill)) {
		spillinfo->spill = new_NoMem();
		return;
Christian Würdig's avatar
Christian Würdig committed
420
421
	}

422

423
	/*
424
425
426
427
	 * We switch on optimizations here to get CSE. This is needed as the STA
	 * backends has some extra spill phases and we want to make use of those
	 * spills instead of creating new ones.
	 */
428
429
	save_optimization_state(&opt);
	set_optimize(1);
430
	spillinfo->spill = be_spill(env->arch_env, to_spill);
431
432
	restore_optimization_state(&opt);
	if (! sched_is_scheduled(spillinfo->spill)) {
433
434
435
436
		DB((dbg, LEVEL_1, "add spill %+F after %+F\n", spillinfo->spill, to_spill));
#ifdef FIRM_STATISTICS
		env->spill_count++;
#endif
437
		sched_add_after_insn(to_spill, spillinfo->spill);
438
	} else {
439
		DB((dbg, LEVEL_1, "re-using spill %+F after %+F\n", spillinfo->spill, to_spill));
440
	}
Daniel Grund's avatar
Daniel Grund committed
441
442
}

443
444
static
void spill_node(spill_env_t *env, spill_info_t *spillinfo);
Matthias Braun's avatar
Matthias Braun committed
445

446
/**
Matthias Braun's avatar
Matthias Braun committed
447
448
449
450
451
452
453
454
 * 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
 *
 * @param senv      the spill environment
 * @param phi       the Phi node that should be spilled
 * @param ctx_irn   an user of the spilled node
455
 */
456
457
458
459
static
void spill_phi(spill_env_t *env, spill_info_t *spillinfo)
{
	ir_node *phi = spillinfo->to_spill;
460
	int i;
Matthias Braun's avatar
Matthias Braun committed
461
462
463
	int arity = get_irn_arity(phi);
	ir_node     *block    = get_nodes_block(phi);
	ir_node     **ins;
464

Matthias Braun's avatar
Matthias Braun committed
465
	assert(is_Phi(phi));
466

467
	DBG((dbg, LEVEL_1, "spilling Phi %+F:\n", phi));
Matthias Braun's avatar
Matthias Braun committed
468
469
470
	/* build a new PhiM */
	ins = alloca(sizeof(ir_node*) * arity);
	for(i = 0; i < arity; ++i) {
471
		ins[i] = get_irg_bad(env->irg);
Matthias Braun's avatar
Matthias Braun committed
472
	}
473
	spillinfo->spill = new_r_Phi(env->irg, block, arity, ins, mode_M);
474
475
476
#ifdef FIRM_STATISTICS
	env->spilled_phi_count++;
#endif
477

Matthias Braun's avatar
Matthias Braun committed
478
479
480
	for(i = 0; i < arity; ++i) {
		ir_node *arg = get_irn_n(phi, i);
		spill_info_t *arg_info = get_spillinfo(env, arg);
481

Matthias Braun's avatar
Matthias Braun committed
482
483
484
		spill_node(env, arg_info);

		set_irn_n(spillinfo->spill, i, arg_info->spill);
485
	}
486
	DBG((dbg, LEVEL_1, "... done spilling Phi %+F, created PhiM %+F\n", phi, spillinfo->spill));
487

488
	/* rewire reloads from old_spill to phi */
Christian Würdig's avatar
Christian Würdig committed
489
	if (spillinfo->old_spill != NULL) {
490
		const ir_edge_t *edge, *next;
491
492
		ir_node *old_spill = spillinfo->old_spill;

493
		DBG((dbg, LEVEL_1, "old spill found, rewiring reloads:\n"));
Christian Würdig's avatar
Christian Würdig committed
494

495
		foreach_out_edge_safe(old_spill, edge, next) {
Christian Würdig's avatar
Christian Würdig committed
496
497
498
			ir_node *reload = get_edge_src_irn(edge);
			int     pos     = get_edge_src_pos(edge);

499
			DBG((dbg, LEVEL_1, "\tset input %d of %+F to %+F\n", pos, reload, spillinfo->spill));
Christian Würdig's avatar
Christian Würdig committed
500

501
			assert(be_is_Reload(reload) || is_Phi(reload));
Christian Würdig's avatar
Christian Würdig committed
502
			set_irn_n(reload, pos, spillinfo->spill);
503
		}
504
		DBG((dbg, LEVEL_1, "\tset input of %+F to BAD\n", old_spill));
505
		set_irn_n(old_spill, be_pos_Spill_val, new_Bad());
506
		/* sched_remove(old_spill); */
507
508
		spillinfo->old_spill = NULL;
	}
Matthias Braun's avatar
Matthias Braun committed
509
510
511
512
513
514
515
516
}

/**
 * Spill a node.
 *
 * @param senv      the spill environment
 * @param to_spill  the node that should be spilled
 */
517
518
519
static
void spill_node(spill_env_t *env, spill_info_t *spillinfo)
{
Matthias Braun's avatar
Matthias Braun committed
520
521
	ir_node *to_spill;

522
	/* the node should be tagged for spilling already... */
Matthias Braun's avatar
Matthias Braun committed
523
524
	if(spillinfo->spill != NULL)
		return;
525

526
	to_spill = spillinfo->to_spill;
527

528
	if (is_Phi(to_spill) && ir_nodeset_contains(&env->mem_phis, to_spill)) {
Matthias Braun's avatar
Matthias Braun committed
529
530
531
532
		spill_phi(env, spillinfo);
	} else {
		spill_irn(env, spillinfo);
	}
533
534
}

535
536
537
538
539
540
541
542
543
/*
 *
 *  ____                      _            _       _ _
 * |  _ \ ___ _ __ ___   __ _| |_ ___ _ __(_) __ _| (_)_______
 * | |_) / _ \ '_ ` _ \ / _` | __/ _ \ '__| |/ _` | | |_  / _ \
 * |  _ <  __/ | | | | | (_| | ||  __/ |  | | (_| | | |/ /  __/
 * |_| \_\___|_| |_| |_|\__,_|\__\___|_|  |_|\__,_|_|_/___\___|
 *
 */
544

545
/**
546
547
 * Tests whether value @p arg is available before node @p reloader
 * @returns 1 if value is available, 0 otherwise
548
 */
549
static
Sebastian Hack's avatar
Sebastian Hack committed
550
int is_value_available(spill_env_t *env, const ir_node *arg, const ir_node *reloader)
551
{
552
553
	if(is_Unknown(arg) || arg == new_NoMem())
		return 1;
554

555
556
	if(be_is_Spill(arg))
		return 1;
557

558
	if(arg == get_irg_frame(env->irg))
559
560
		return 1;

561
	/* hack for now (happens when command should be inserted at end of block) */
562
563
564
565
	if(is_Block(reloader)) {
		return 0;
	}

566
567
568
569
570
571
572
	/*
	 * Ignore registers are always available
	 */
	if(arch_irn_is(env->arch_env, arg, ignore)) {
		return 1;
	}

573
574
575
 	/* the following test does not work while spilling,
	 * because the liveness info is not adapted yet to the effects of the
	 * additional spills/reloads.
576
	 */
Matthias Braun's avatar
Matthias Braun committed
577
#if 0
578
579
580
581
582
583
584
585
	/* we want to remat before the insn reloader
	 * thus an arguments is alive if
	 *   - it interferes with the reloaders result
	 *   - or it is (last-) used by reloader itself
	 */
	if (values_interfere(env->birg->lv, reloader, arg)) {
		return 1;
	}
586

587
588
589
590
591
	arity = get_irn_arity(reloader);
	for (i = 0; i < arity; ++i) {
		ir_node *rel_arg = get_irn_n(reloader, i);
		if (rel_arg == arg)
			return 1;
592
	}
593
#endif
Daniel Grund's avatar
Daniel Grund committed
594

595
 	return 0;
596
}
597

598
/**
599
 * Checks whether the node can principally be rematerialized
600
 */
601
static
Sebastian Hack's avatar
Sebastian Hack committed
602
int is_remat_node(spill_env_t *env, const ir_node *node)
603
{
604
	const arch_env_t *arch_env = env->arch_env;
605

606
	assert(!be_is_Spill(node));
607

Matthias Braun's avatar
Matthias Braun committed
608
	if(arch_irn_is(arch_env, node, rematerializable))
609
		return 1;
610

611
612
613
614
615
616
617
618
619
620
621
	return 0;
}

/**
 * Check if a node is rematerializable. This tests for the following conditions:
 *
 * - The node itself is rematerializable
 * - All arguments of the node are available or also rematerialisable
 * - The costs for the rematerialisation operation is less or equal a limit
 *
 * Returns the costs needed for rematerialisation or something
622
 * >= REMAT_COST_INFINITE if remat is not possible.
623
 */
624
static
Sebastian Hack's avatar
Sebastian Hack committed
625
626
int check_remat_conditions_costs(spill_env_t *env, const ir_node *spilled,
                                 const ir_node *reloader, int parentcosts)
627
{
628
629
630
	int i, arity;
	int argremats;
	int costs = 0;
631

632
	if(!is_remat_node(env, spilled))
633
		return REMAT_COST_INFINITE;
634

635
636
637
	if(be_is_Reload(spilled)) {
		costs += 2;
	} else {
638
		costs += arch_get_op_estimated_cost(env->arch_env, spilled);
639
	}
640
641
	if(parentcosts + costs >= env->reload_cost + env->spill_cost) {
		return REMAT_COST_INFINITE;
642
	}
643
644
645
646
647
648
649
650

	argremats = 0;
	for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) {
		ir_node *arg = get_irn_n(spilled, i);

		if(is_value_available(env, arg, reloader))
			continue;

651
		/* we have to rematerialize the argument as well */
652
653
654
655
		if(argremats >= 1) {
			/* we only support rematerializing 1 argument at the moment,
			 * so that we don't have to care about register pressure
			 */
656
			return REMAT_COST_INFINITE;
657
		}
658
		argremats++;
659

660
		costs += check_remat_conditions_costs(env, arg, reloader, parentcosts + costs);
661
662
		if(parentcosts + costs >= env->reload_cost + env->spill_cost)
			return REMAT_COST_INFINITE;
663
664
	}

665
	return costs;
666
667
}

668
/**
669
 * Re-materialize a node.
670
671
672
673
674
 *
 * @param senv      the spill environment
 * @param spilled   the node that was spilled
 * @param reloader  a irn that requires a reload
 */
675
676
677
static
ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader)
{
678
	int i, arity;
679
	ir_node *res;
680
	ir_node *bl;
681
682
	ir_node **ins;

683
684
685
686
687
688
	if(is_Block(reloader)) {
		bl = reloader;
	} else {
		bl = get_nodes_block(reloader);
	}

689
690
691
	ins = alloca(get_irn_arity(spilled) * sizeof(ins[0]));
	for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) {
		ir_node *arg = get_irn_n(spilled, i);
692

693
694
695
696
		if(is_value_available(env, arg, reloader)) {
			ins[i] = arg;
		} else {
			ins[i] = do_remat(env, arg, reloader);
697
698
699
700
#ifdef FIRM_STATISTICS
			/* don't count the recursive call as remat */
			env->remat_count--;
#endif
701
702
703
704
		}
	}

	/* create a copy of the node */
705
	res = new_ir_node(get_irn_dbg_info(spilled), env->irg, bl,
706
707
	                  get_irn_op(spilled), get_irn_mode(spilled),
	                  get_irn_arity(spilled), ins);
Daniel Grund's avatar
Daniel Grund committed
708
	copy_node_attr(spilled, res);
709
	new_backedge_info(res);
710

711
	DBG((dbg, LEVEL_1, "Insert remat %+F of %+F before reloader %+F\n", res, spilled, reloader));
712

713
714
715
716
717
718
719
720
	if (! is_Proj(res)) {
		/* insert in schedule */
		sched_reset(res);
		sched_add_before(reloader, res);
#ifdef FIRM_STATISTICS
		env->remat_count++;
#endif
	}
721
722
723
724

	return res;
}

Matthias Braun's avatar
Matthias Braun committed
725
double be_get_spill_costs(spill_env_t *env, ir_node *to_spill, ir_node *after)
726
{
Matthias Braun's avatar
Matthias Braun committed
727
728
	ir_node *block = get_nodes_block(after);
	double   freq  = get_block_execfreq(env->exec_freq, block);
729
	(void) to_spill;
Matthias Braun's avatar
Matthias Braun committed
730
731
732
733
734
735
736
737

	return env->spill_cost * freq;
}

double be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before)
{
	ir_node      *block = get_nodes_block(before);
	double        freq  = get_block_execfreq(env->exec_freq, block);
738

739
	if(be_do_remats) {
740
		/* is the node rematerializable? */
741
		int costs = check_remat_conditions_costs(env, to_spill, before, 0);
Matthias Braun's avatar
Matthias Braun committed
742
743
		if(costs < env->reload_cost)
			return costs * freq;
744
	}
745

Matthias Braun's avatar
Matthias Braun committed
746
	return env->reload_cost * freq;
747
748
}

Sebastian Hack's avatar
Sebastian Hack committed
749
750
751
752
753
int be_is_rematerializable(spill_env_t *env, const ir_node *to_remat, const ir_node *before)
{
	return check_remat_conditions_costs(env, to_remat, before, 0) < REMAT_COST_INFINITE;
}

Matthias Braun's avatar
Matthias Braun committed
754
double be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill,
755
756
                                ir_node *block, int pos)
{
757
	ir_node *before = get_block_insertion_point(block, pos);
758
759
760
	return be_get_reload_costs(env, to_spill, before);
}

761
762
763
764
765
766
767
768
/*
 *  ___                     _     ____      _                 _
 * |_ _|_ __  ___  ___ _ __| |_  |  _ \ ___| | ___   __ _  __| |___
 *  | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ |/ _ \ / _` |/ _` / __|
 *  | || | | \__ \  __/ |  | |_  |  _ <  __/ | (_) | (_| | (_| \__ \
 * |___|_| |_|___/\___|_|   \__| |_| \_\___|_|\___/ \__,_|\__,_|___/
 *
 */
769

770
771
772
void be_insert_spills_reloads(spill_env_t *env)
{
	const arch_env_t      *arch_env  = env->arch_env;
Matthias Braun's avatar
Matthias Braun committed
773
	const ir_exec_freq    *exec_freq = env->exec_freq;
774
775
776
	spill_info_t          *si;
	ir_nodeset_iterator_t  iter;
	ir_node               *node;
Matthias Braun's avatar
test    
Matthias Braun committed
777
778
779
780
781

	/* create all phi-ms first, this is needed so, that phis, hanging on
	   spilled phis work correctly */
	foreach_ir_nodeset(&env->mem_phis, node, iter) {
		spill_info_t *info = get_spillinfo(env, node);
Christian Würdig's avatar
Christian Würdig committed
782
		spill_node(env, info);
Matthias Braun's avatar
test    
Matthias Braun committed
783
	}
Sebastian Hack's avatar
Sebastian Hack committed
784
785

	/* process each spilled node */
786
	for (si = set_first(env->spills); si; si = set_next(env->spills)) {
Sebastian Hack's avatar
Sebastian Hack committed
787
		reloader_t *rld;
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
		ir_node  *to_spill        = si->to_spill;
		ir_mode  *mode            = get_irn_mode(to_spill);
		ir_node **copies          = NEW_ARR_F(ir_node*, 0);
		double    all_remat_costs = 0; /** costs when we would remat all nodes */
		int       force_remat     = 0;

		DBG((dbg, LEVEL_1, "\nhandling all reloaders of %+F:\n", to_spill));

		/* determine possibility of rematerialisations */
		if(be_do_remats) {
			for (rld = si->reloaders; rld != NULL; rld = rld->next) {
				double   freq;
				int      remat_cost;
				int      remat_cost_delta;
				ir_node *block;
				ir_node *reloader = rld->reloader;

				if(rld->rematted_node != NULL) {
					DBG((dbg, LEVEL_2, "\tforced remat %+F before %+F\n",
					     rld->rematted_node, reloader));
					continue;
				}
				if(rld->remat_cost_delta >= REMAT_COST_INFINITE) {
					DBG((dbg, LEVEL_2, "\treload before %+F is forbidden\n",
					     reloader));
					all_remat_costs = REMAT_COST_INFINITE;
					continue;
				}

				remat_cost  = check_remat_conditions_costs(env, to_spill,
				                                           reloader, 0);
				if(remat_cost >= REMAT_COST_INFINITE) {
					DBG((dbg, LEVEL_2, "\tremat before %+F not possible\n",
					     reloader));
					rld->remat_cost_delta = REMAT_COST_INFINITE;
					all_remat_costs       = REMAT_COST_INFINITE;
					continue;
				}

				remat_cost_delta      = remat_cost - env->reload_cost;
				rld->remat_cost_delta = remat_cost_delta;
Sebastian Hack's avatar
Sebastian Hack committed
829
				block                 = is_Block(reloader) ? reloader : get_nodes_block(reloader);
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
				freq                  = get_block_execfreq(exec_freq, block);
				all_remat_costs      += remat_cost_delta * freq;
				DBG((dbg, LEVEL_2, "\tremat costs delta before %+F: "
				     "%d (rel %f)\n", reloader, remat_cost_delta,
				     remat_cost_delta * freq));
			}
			if(all_remat_costs < REMAT_COST_INFINITE) {
				ir_node *block = get_nodes_block(to_spill);
				double   freq  = get_block_execfreq(exec_freq, block);
				/* we don't need the costs for the spill if we can remat
				   all reloaders */
				all_remat_costs -= env->spill_cost * freq;

				DBG((dbg, LEVEL_2, "\tspill costs %d (rel %f)\n",
				     env->spill_cost, env->spill_cost * freq));
			}
Sebastian Hack's avatar
Sebastian Hack committed
846

847
848
849
850
851
852
			if(all_remat_costs < 0) {
				DBG((dbg, LEVEL_1, "\nforcing remats of all reloaders (%f)\n",
				     all_remat_costs));
				force_remat = 1;
			}
		}
Christian Würdig's avatar
Christian Würdig committed
853

Sebastian Hack's avatar
Sebastian Hack committed
854
		/* go through all reloads for this spill */
855
		for (rld = si->reloaders; rld != NULL; rld = rld->next) {
Michael Beck's avatar
Michael Beck committed
856
			ir_node *copy; /* a reload is a "copy" of the original value */
857

858
			if (rld->rematted_node != NULL) {
859
860
				copy = rld->rematted_node;
				sched_add_before(rld->reloader, copy);
861
862
863
			} else if (be_do_remats &&
					(force_remat || rld->remat_cost_delta < 0)) {
				copy = do_remat(env, to_spill, rld->reloader);
864
			} else {
Matthias Braun's avatar
Matthias Braun committed
865
				/* make sure we have a spill */
866
				if (si->spill == NULL) {
867
868
					spill_node(env, si);
				}
869

870
				/* create a reload */
871
872
873
874
875
				copy = be_reload(arch_env, si->reload_cls, rld->reloader, mode,
				                 si->spill);
#ifdef FIRM_STATISTICS
				env->reload_count++;
#endif
876
			}
Sebastian Hack's avatar
Sebastian Hack committed
877

878
879
			DBG((dbg, LEVEL_1, " %+F of %+F before %+F\n",
			     copy, to_spill, rld->reloader));
880
			ARR_APP1(ir_node*, copies, copy);
Sebastian Hack's avatar
Sebastian Hack committed
881
882
		}

883
884
885
		/* if we had any reloads or remats, then we need to reconstruct the
		 * SSA form for the spilled value */
		if (ARR_LEN(copies) > 0) {
886
887
888
889
			be_ssa_construction_env_t senv;
			/* be_lv_t *lv = be_get_birg_liveness(env->birg); */

			be_ssa_construction_init(&senv, env->birg);
890
			be_ssa_construction_add_copy(&senv, to_spill);
891
			be_ssa_construction_add_copies(&senv, copies, ARR_LEN(copies));
892
			be_ssa_construction_fix_users(&senv, to_spill);
893
894
895
896
897

#if 0
			/* no need to enable this as long as we invalidate liveness
			   after this function... */
			be_ssa_construction_update_liveness_phis(&senv);
898
			be_liveness_update(to_spill);
899
900
901
902
903
904
			len = ARR_LEN(copies);
			for(i = 0; i < len; ++i) {
				be_liveness_update(lv, copies[i]);
			}
#endif
			be_ssa_construction_destroy(&senv);
Matthias Braun's avatar
Matthias Braun committed
905
		}
Sebastian Hack's avatar
Sebastian Hack committed
906

907
		DEL_ARR_F(copies);
908
909
		si->reloaders = NULL;
	}
910

Sebastian Hack's avatar
Sebastian Hack committed
911
912
913
914
	stat_ev_dbl("spill_spills", env->spill_count);
	stat_ev_dbl("spill_reloads", env->reload_count);
	stat_ev_dbl("spill_remats", env->remat_count);
	stat_ev_dbl("spill_spilled_phis", env->spilled_phi_count);
915

Michael Beck's avatar
Michael Beck committed
916
	/* Matze: In theory be_ssa_construction should take care of the liveness...
917
	 * try to disable this again in the future */
Sebastian Hack's avatar
Sebastian Hack committed
918
	be_liveness_invalidate(env->birg->lv);
919
920

	be_remove_dead_nodes_from_schedule(env->birg);
Daniel Grund's avatar
Daniel Grund committed
921
}
922
923
924
925
926
927
928

void be_init_spill(void)
{
	FIRM_DBG_REGISTER(dbg, "firm.be.spill");
}

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spill);