bespillutil.c 40.3 KB
Newer Older
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
4
5
6
7
8
9
 */

/**
 * @file
 * @brief       implementation of the spill/reload placement abstraction layer
 * @author      Daniel Grund, Sebastian Hack, Matthias Braun
10
 * @date        29.09.2005
11
12
13
14
15
16
 */
#include <stdlib.h>
#include <stdbool.h>

#include "array.h"
#include "bearch.h"
Matthias Braun's avatar
Matthias Braun committed
17
18
19
20
21
#include "bechordal_t.h"
#include "beirg.h"
#include "belive.h"
#include "bemodule.h"
#include "benode.h"
22
23
24
25
26
#include "besched.h"
#include "bespill.h"
#include "bespillutil.h"
#include "bessaconstr.h"
#include "be_t.h"
Matthias Braun's avatar
Matthias Braun committed
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include "beutil.h"
#include "debug.h"
#include "entity_t.h"
#include "execfreq.h"
#include "ident_t.h"
#include "irbackedge_t.h"
#include "ircons_t.h"
#include "iredges_t.h"
#include "irgmod.h"
#include "irgwalk.h"
#include "irnodehashmap.h"
#include "irnode_t.h"
#include "statev_t.h"
#include "type_t.h"
#include "util.h"
42

43
44
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
DEBUG_ONLY(static firm_dbg_module_t *dbg_constr;)
45
46
47
48
49
50
51
52

#define REMAT_COST_INFINITE  1000

typedef struct reloader_t reloader_t;
struct reloader_t {
	reloader_t *next;
	ir_node    *reloader;
	int         remat_cost_delta; /** costs needed for rematerialization,
Matthias Braun's avatar
Matthias Braun committed
53
	                                  compared to placing a reload */
54
55
56
57
58
59
60
61
62
63
64
};

typedef struct spill_t spill_t;
struct spill_t {
	spill_t *next;
	ir_node *after;  /**< spill has to be placed after this node (or earlier) */
	ir_node *spill;
};

typedef struct spill_info_t spill_info_t;
struct spill_info_t {
65
66
	ir_node      *to_spill;  /**< the value that should get spilled */
	reloader_t   *reloaders; /**< list of places where the value should get
Matthias Braun's avatar
Matthias Braun committed
67
	                              reloaded */
68
	spill_t      *spills;    /**< list of latest places where spill must be
Matthias Braun's avatar
Matthias Braun committed
69
	                              placed */
70
71
72
73
74
75
	spill_info_t *next;
	spill_info_t *next_mem_phi;
	double        spill_costs; /**< costs needed for spilling the value */
	bool          spilled_phi; /**< true when the whole Phi has been spilled and
	                                will be replaced with a PhiM. false if only
	                                the value of the Phi gets spilled */
76
77
78
79
80
};

struct spill_env_t {
	const arch_env_t *arch_env;
	ir_graph         *irg;
81
82
83
	ir_nodehashmap_t  spillmap;
	spill_info_t     *spills;
	spill_info_t     *mem_phis;
84
	struct obstack    obst;
Matthias Braun's avatar
Matthias Braun committed
85
86
	int               spill_cost;  /**< the cost of a single spill node */
	int               reload_cost; /**< the cost of a reload node */
87
88
89
90
91
92
93
94
95
	unsigned          spill_count;
	unsigned          reload_count;
	unsigned          remat_count;
	unsigned          spilled_phi_count;
};

/**
 * Returns spill info for a specific value (the value that is to be spilled)
 */
96
static spill_info_t *get_spillinfo(spill_env_t *env, ir_node *value)
97
{
98
99
100
101
102
103
104
105
106
107
	spill_info_t *info = ir_nodehashmap_get(spill_info_t, &env->spillmap,
	                                        value);
	if (info == NULL) {
		info = OALLOCZ(&env->obst, spill_info_t);
		info->to_spill    = value;
		info->spill_costs = -1;
		ir_nodehashmap_insert(&env->spillmap, value, info);

		info->next = env->spills;
		env->spills = info;
108
109
	}

110
	return info;
111
112
}

113
spill_env_t *be_new_spill_env(ir_graph *irg)
114
{
115
	const arch_env_t *arch_env = be_get_irg_arch_env(irg);
116

117
118
119
120
121
122
	spill_env_t *env = XMALLOCZ(spill_env_t);
	env->irg         = irg;
	env->arch_env    = arch_env;
	env->spill_cost  = arch_env->spill_cost;
	env->reload_cost = arch_env->reload_cost;
	ir_nodehashmap_init(&env->spillmap);
123
124
125
126
127
128
	obstack_init(&env->obst);
	return env;
}

void be_delete_spill_env(spill_env_t *env)
{
129
	ir_nodehashmap_destroy(&env->spillmap);
130
131
132
133
134
135
	obstack_free(&env->obst, NULL);
	free(env);
}

void be_add_spill(spill_env_t *env, ir_node *to_spill, ir_node *after)
{
136
	assert(!arch_irn_is(skip_Proj_const(to_spill), dont_spill));
137
138
139
140
141
142
	DB((dbg, LEVEL_1, "Add spill of %+F after %+F\n", to_spill, after));

	/* Just for safety make sure that we do not insert the spill in front of a phi */
	assert(!is_Phi(sched_next(after)));

	/* spills that are dominated by others are not needed */
Matthias Braun's avatar
Matthias Braun committed
143
144
145
	spill_info_t *spill_info = get_spillinfo(env, to_spill);
	for (spill_t *s = spill_info->spills, *last = NULL ; s != NULL;
	     s = s->next) {
146
		/* no need to add this spill if it is dominated by another */
Matthias Braun's avatar
Matthias Braun committed
147
		if (value_strictly_dominates(s->after, after)) {
148
149
150
151
			DB((dbg, LEVEL_1, "...dominated by %+F, not added\n", s->after));
			return;
		}
		/* remove spills that we dominate */
Matthias Braun's avatar
Matthias Braun committed
152
		if (value_strictly_dominates(after, s->after)) {
153
			DB((dbg, LEVEL_1, "...remove old spill at %+F\n", s->after));
154
			if (last != NULL) {
155
156
157
158
159
160
161
162
163
				last->next         = s->next;
			} else {
				spill_info->spills = s->next;
			}
		} else {
			last = s;
		}
	}

Matthias Braun's avatar
Matthias Braun committed
164
165
166
167
	spill_t *spill = OALLOC(&env->obst, spill_t);
	spill->after = after;
	spill->next  = spill_info->spills;
	spill->spill = NULL;
168
169
170
	spill_info->spills = spill;
}

Matthias Braun's avatar
Matthias Braun committed
171
void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before)
172
{
173
	assert(!arch_irn_is(skip_Proj_const(to_spill), dont_spill));
Matthias Braun's avatar
Matthias Braun committed
174
	assert(!be_is_Keep(before));
175

Matthias Braun's avatar
Matthias Braun committed
176
	spill_info_t *info = get_spillinfo(env, to_spill);
177
178
	if (is_Phi(to_spill)) {
		/* create spillinfos for the phi arguments */
179
		foreach_irn_in(to_spill, i, arg) {
180
181
182
183
184
			get_spillinfo(env, arg);
		}
	}

	/* put reload into list */
Matthias Braun's avatar
Matthias Braun committed
185
	reloader_t *rel       = OALLOC(&env->obst, reloader_t);
186
187
	rel->next             = info->reloaders;
	rel->reloader         = before;
Matthias Braun's avatar
Matthias Braun committed
188
	rel->remat_cost_delta = 0;
189

Matthias Braun's avatar
Matthias Braun committed
190
	info->reloaders = rel;
191

Matthias Braun's avatar
Matthias Braun committed
192
193
194
	DBG((dbg, LEVEL_1,
	     "creating spillinfo for %+F, will be reloaded before %+F\n",
	     to_spill, before));
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
}

ir_node *be_get_end_of_block_insertion_point(const ir_node *block)
{
	ir_node *last = sched_last(block);

	/* we might have keeps behind the jump... */
	while (be_is_Keep(last)) {
		last = sched_prev(last);
		assert(!sched_is_end(last));
	}

	assert(is_cfop(last));

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

/**
 * Returns the point at which you can insert a node that should be executed
 * before block @p block when coming from pred @p pos.
 */
static ir_node *get_block_insertion_point(ir_node *block, int pos)
{
	/* 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. */
222
	if (get_Block_n_cfgpreds(block) == 1) {
223
224
225
226
227
		assert(!is_Phi(sched_first(block)));
		return sched_first(block);
	}

	/* We have to reload the value in pred-block */
Matthias Braun's avatar
Matthias Braun committed
228
	ir_node *predblock = get_Block_cfgpred_block(block, pos);
229
230
231
232
	return be_get_end_of_block_insertion_point(predblock);
}

void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block,
Matthias Braun's avatar
Matthias Braun committed
233
                           int pos)
234
235
{
	ir_node *before = get_block_insertion_point(block, pos);
Matthias Braun's avatar
Matthias Braun committed
236
	be_add_reload(env, to_spill, before);
237
238
239
240
241
242
}

void be_spill_phi(spill_env_t *env, ir_node *node)
{
	assert(is_Phi(node));

Matthias Braun's avatar
Matthias Braun committed
243
	spill_info_t *info = get_spillinfo(env, node);
244
245
246
	info->spilled_phi  = true;
	info->next_mem_phi = env->mem_phis;
	env->mem_phis      = info;
247
248

	/* create spills for the phi arguments */
Matthias Braun's avatar
Matthias Braun committed
249
	ir_node *block = get_nodes_block(node);
250
	foreach_irn_in(node, i, arg) {
251
252
		/* some backends have virtual noreg/unknown nodes that are not scheduled
		 * and simply always available. */
Matthias Braun's avatar
Matthias Braun committed
253
		ir_node *insert;
254
		if (!sched_is_scheduled(arg)) {
255
256
257
258
			ir_node *pred_block = get_Block_cfgpred_block(block, i);
			insert = be_get_end_of_block_insertion_point(pred_block);
			insert = sched_prev(insert);
		} else {
259
			insert = be_move_after_schedule_first(arg);
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
		}
		be_add_spill(env, arg, insert);
	}
}

static void determine_spill_costs(spill_env_t *env, spill_info_t *spillinfo);

/**
 * 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
 */
static void spill_irn(spill_env_t *env, spill_info_t *spillinfo)
{
	/* determine_spill_costs must have been run before */
	assert(spillinfo->spill_costs >= 0);

	/* some backends have virtual noreg/unknown nodes that are not scheduled
	 * and simply always available. */
Matthias Braun's avatar
Matthias Braun committed
282
283
	ir_node       *to_spill = spillinfo->to_spill;
	const ir_node *insn     = skip_Proj_const(to_spill);
284
	if (!sched_is_scheduled(insn)) {
285
		/* override spillinfos or create a new one */
286
		ir_graph *irg = get_irn_irg(to_spill);
287
		spillinfo->spills->spill = get_irg_no_mem(irg);
288
289
290
291
292
		DB((dbg, LEVEL_1, "don't spill %+F use NoMem\n", to_spill));
		return;
	}

	DBG((dbg, LEVEL_1, "spilling %+F ... \n", to_spill));
Matthias Braun's avatar
Matthias Braun committed
293
294
	for (spill_t *spill = spillinfo->spills; spill != NULL;
	     spill = spill->next) {
295
		ir_node *const after = be_move_after_schedule_first(spill->after);
296
		spill->spill = arch_env_new_spill(env->arch_env, to_spill, after);
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
		DB((dbg, LEVEL_1, "\t%+F after %+F\n", spill->spill, after));
		env->spill_count++;
	}
	DBG((dbg, LEVEL_1, "\n"));
}

static void spill_node(spill_env_t *env, spill_info_t *spillinfo);

/**
 * 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
 */
static void spill_phi(spill_env_t *env, spill_info_t *spillinfo)
{
	assert(!get_opt_cse());
Matthias Braun's avatar
Matthias Braun committed
318
	ir_node *phi = spillinfo->to_spill;
319
320
321
	DBG((dbg, LEVEL_1, "spilling Phi %+F:\n", phi));

	/* build a new PhiM */
322
323
	int       const arity   = get_Phi_n_preds(phi);
	ir_node **const ins     = ALLOCAN(ir_node*, arity);
Matthias Braun's avatar
Matthias Braun committed
324
	ir_graph *const irg     = env->irg;
325
	ir_node  *const unknown = new_r_Unknown(irg, mode_M);
326
	for (int i = 0; i < arity; ++i) {
327
328
329
330
		ins[i] = unknown;
	}

	/* override or replace spills list... */
Matthias Braun's avatar
Matthias Braun committed
331
332
	ir_node *block = get_nodes_block(phi);
	spill_t *spill = OALLOC(&env->obst, spill_t);
333
	spill->after   = be_move_after_schedule_first(phi);
Matthias Braun's avatar
Matthias Braun committed
334
335
	spill->spill   = be_new_Phi(block, arity, ins, mode_M, arch_no_register_req);
	spill->next    = NULL;
Matthias Braun's avatar
Matthias Braun committed
336
	sched_add_after(block, spill->spill);
337
338
339
340

	spillinfo->spills = spill;
	env->spilled_phi_count++;

341
	foreach_irn_in(phi, i, arg) {
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
		spill_info_t *arg_info = get_spillinfo(env, arg);

		determine_spill_costs(env, arg_info);
		spill_node(env, arg_info);

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

/**
 * Spill a node.
 *
 * @param senv      the spill environment
 * @param to_spill  the node that should be spilled
 */
static void spill_node(spill_env_t *env, spill_info_t *spillinfo)
{
	/* node is already spilled */
362
	if (spillinfo->spills != NULL && spillinfo->spills->spill != NULL)
363
364
		return;

365
	if (spillinfo->spilled_phi) {
366
367
368
369
370
371
372
373
		spill_phi(env, spillinfo);
	} else {
		spill_irn(env, spillinfo);
	}
}

/**
 * Tests whether value @p arg is available before node @p reloader
Matthias Braun's avatar
Matthias Braun committed
374
 * @returns true if value is available
375
 */
Matthias Braun's avatar
Matthias Braun committed
376
static bool is_value_available(spill_env_t *env, const ir_node *arg)
377
{
378
	if (is_Unknown(arg) || is_NoMem(arg))
Matthias Braun's avatar
Matthias Braun committed
379
		return true;
380
	if (arch_irn_is(skip_Proj_const(arg), spill))
Matthias Braun's avatar
Matthias Braun committed
381
		return true;
382
	if (arg == get_irg_frame(env->irg))
Matthias Braun's avatar
Matthias Braun committed
383
		return true;
384
	if (get_irn_mode(arg) == mode_T)
Matthias Braun's avatar
Matthias Braun committed
385
386
		return false;
	/* "Ignore registers" are always available */
387
	if (arch_irn_is_ignore(arg))
Matthias Braun's avatar
Matthias Braun committed
388
		return true;
389

Matthias Braun's avatar
Matthias Braun committed
390
	return false;
391
392
393
394
395
396
397
398
399
400
401
402
403
}

/**
 * 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
 * >= REMAT_COST_INFINITE if remat is not possible.
 */
static int check_remat_conditions_costs(spill_env_t *env,
Matthias Braun's avatar
Matthias Braun committed
404
405
406
                                        const ir_node *spilled,
                                        const ir_node *reloader,
                                        int parentcosts)
407
{
408
	const ir_node *insn = skip_Proj_const(spilled);
409

410
	assert(!arch_irn_is(insn, spill));
411
	if (!arch_irn_is(insn, rematerializable))
412
413
		return REMAT_COST_INFINITE;

Matthias Braun's avatar
Matthias Braun committed
414
	int costs = arch_get_op_estimated_cost(insn);
415
	if (parentcosts + costs >= env->reload_cost + env->spill_cost)
416
		return REMAT_COST_INFINITE;
417

418
	/* never rematerialize a node which modifies the flags.
419
	 * (would be better to test whether the flags are actually live at point
420
421
	 * reloader...)
	 */
Matthias Braun's avatar
Matthias Braun committed
422
	if (arch_irn_is(insn, modify_flags))
423
424
		return REMAT_COST_INFINITE;

Matthias Braun's avatar
Matthias Braun committed
425
	int argremats = 0;
426
	foreach_irn_in(insn, i, arg) {
Matthias Braun's avatar
Matthias Braun committed
427
		if (is_value_available(env, arg))
428
429
430
			continue;

		/* we have to rematerialize the argument as well */
431
		++argremats;
432
		if (argremats > 1) {
433
			/* we only support rematerializing 1 argument at the moment,
434
			 * as multiple arguments could increase register pressure */
435
436
437
438
439
			return REMAT_COST_INFINITE;
		}

		costs += check_remat_conditions_costs(env, arg, reloader,
		                                      parentcosts + costs);
440
		if (parentcosts + costs >= env->reload_cost + env->spill_cost)
441
442
443
444
445
446
447
448
449
			return REMAT_COST_INFINITE;
	}

	return costs;
}

/**
 * Re-materialize a node.
 *
Michael Beck's avatar
Michael Beck committed
450
 * @param env       the spill environment
451
452
453
454
455
 * @param spilled   the node that was spilled
 * @param reloader  a irn that requires a reload
 */
static ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader)
{
Matthias Braun's avatar
Matthias Braun committed
456
	ir_node **ins = ALLOCAN(ir_node*, get_irn_arity(spilled));
457
	foreach_irn_in(spilled, i, arg) {
Matthias Braun's avatar
Matthias Braun committed
458
		if (is_value_available(env, arg)) {
459
460
461
462
463
464
465
			ins[i] = arg;
		} else {
			ins[i] = do_remat(env, arg, reloader);
		}
	}

	/* create a copy of the node */
466
467
	ir_node *const bl  = get_nodes_block(reloader);
	ir_node *const res = new_similar_node(spilled, bl, ins);
468
469
	arch_env_mark_remat(env->arch_env, res);

Matthias Braun's avatar
Matthias Braun committed
470
471
	DBG((dbg, LEVEL_1, "Insert remat %+F of %+F before reloader %+F\n", res,
	     spilled, reloader));
472

Christoph Mallon's avatar
Christoph Mallon committed
473
	if (!is_Proj(res))
474
475
476
477
478
479
480
		sched_add_before(reloader, res);

	return res;
}

double be_get_spill_costs(spill_env_t *env, ir_node *to_spill, ir_node *before)
{
Matthias Braun's avatar
Matthias Braun committed
481
	(void)to_spill;
482
	ir_node *block = get_nodes_block(before);
483
	double   freq  = get_block_execfreq(block);
484
485
486
	return env->spill_cost * freq;
}

Matthias Braun's avatar
Matthias Braun committed
487
488
unsigned be_get_reload_costs_no_weight(spill_env_t *env,
                                       const ir_node *to_spill,
489
490
                                       const ir_node *before)
{
491
	if (be_do_remats) {
492
493
		/* is the node rematerializable? */
		unsigned costs = check_remat_conditions_costs(env, to_spill, before, 0);
494
		if (costs < (unsigned) env->reload_cost)
495
496
497
498
499
500
501
502
			return costs;
	}

	return env->reload_cost;
}

double be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before)
{
503
504
	ir_node *block = get_nodes_block(before);
	double   freq  = get_block_execfreq(block);
505

506
	if (be_do_remats) {
507
508
		/* is the node rematerializable? */
		int costs = check_remat_conditions_costs(env, to_spill, before, 0);
509
		if (costs < env->reload_cost)
510
511
512
513
514
515
			return costs * freq;
	}

	return env->reload_cost * freq;
}

Matthias Braun's avatar
Matthias Braun committed
516
517
bool be_is_rematerializable(spill_env_t *env, const ir_node *to_remat,
                            const ir_node *before)
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
{
	return check_remat_conditions_costs(env, to_remat, before, 0) < REMAT_COST_INFINITE;
}

double be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill,
                                   ir_node *block, int pos)
{
	ir_node *before = get_block_insertion_point(block, pos);
	return be_get_reload_costs(env, to_spill, before);
}

/**
 * analyzes how to best spill a node and determine costs for that
 */
static void determine_spill_costs(spill_env_t *env, spill_info_t *spillinfo)
{
	/* already calculated? */
535
	if (spillinfo->spill_costs >= 0)
536
537
		return;

Matthias Braun's avatar
Matthias Braun committed
538
539
	ir_node       *to_spill = spillinfo->to_spill;
	const ir_node *insn     = skip_Proj_const(to_spill);
540
	assert(!arch_irn_is(insn, dont_spill));
541
	assert(!arch_irn_is(insn, reload));
542
543
544
545
546
547

	/* some backends have virtual noreg/unknown nodes that are not scheduled
	 * and simply always available.
	 * TODO: this is kinda hairy, the NoMem is correct for an Unknown as Phi
	 * predecessor (of a PhiM) but this test might match other things too...
	 */
548
	if (!sched_is_scheduled(insn)) {
549
		ir_graph *irg = get_irn_irg(to_spill);
550
		/* override spillinfos or create a new one */
551
		spill_t *spill = OALLOC(&env->obst, spill_t);
552
553
		spill->after = NULL;
		spill->next  = NULL;
554
		spill->spill = get_irg_no_mem(irg);
555
556
557
558
559
560
561
562

		spillinfo->spills      = spill;
		spillinfo->spill_costs = 0;

		DB((dbg, LEVEL_1, "don't spill %+F use NoMem\n", to_spill));
		return;
	}

Matthias Braun's avatar
Matthias Braun committed
563
564
	ir_node *spill_block    = get_nodes_block(insn);
	double   spill_execfreq = get_block_execfreq(spill_block);
565

566
	if (spillinfo->spilled_phi) {
567
568
569
570
571
572
		/* TODO calculate correct costs...
		 * (though we can't remat this node anyway so no big problem) */
		spillinfo->spill_costs = env->spill_cost * spill_execfreq;
		return;
	}

573
	if (spillinfo->spills != NULL) {
574
		/* calculate sum of execution frequencies of individual spills */
Matthias Braun's avatar
Matthias Braun committed
575
576
		double spills_execfreq = 0;
		for (spill_t *s = spillinfo->spills; s != NULL; s = s->next) {
577
			ir_node *spill_block = get_block(s->after);
Matthias Braun's avatar
Matthias Braun committed
578
			double   freq        = get_block_execfreq(spill_block);
579
580
581
582
583
584
585
586
587

			spills_execfreq += freq;
		}

		DB((dbg, LEVEL_1, "%+F: latespillcosts %f after def: %f\n", to_spill,
		    spills_execfreq * env->spill_cost,
		    spill_execfreq * env->spill_cost));

		/* multi-/latespill is advantageous -> return*/
588
		if (spills_execfreq < spill_execfreq) {
589
590
591
592
593
594
595
			DB((dbg, LEVEL_1, "use latespills for %+F\n", to_spill));
			spillinfo->spill_costs = spills_execfreq * env->spill_cost;
			return;
		}
	}

	/* override spillinfos or create a new one */
Matthias Braun's avatar
Matthias Braun committed
596
	spill_t *spill = OALLOC(&env->obst, spill_t);
597
	spill->after   = be_move_after_schedule_first(skip_Proj(to_spill));
Matthias Braun's avatar
Matthias Braun committed
598
599
	spill->next    = NULL;
	spill->spill   = NULL;
600
601
602
603
604
605
606
607
608
609
610
611
612
613

	spillinfo->spills      = spill;
	spillinfo->spill_costs = spill_execfreq * env->spill_cost;
	DB((dbg, LEVEL_1, "spill %+F after definition\n", to_spill));
}

void make_spill_locations_dominate_irn(spill_env_t *env, ir_node *irn)
{
	const spill_info_t *si = get_spillinfo(env, irn);
	if (si == NULL)
		return;

	/* Fill the bitset with the dominance pre-order numbers
	 * of the blocks the reloads are located in. */
Matthias Braun's avatar
Matthias Braun committed
614
615
616
617
618
619
	ir_node  *start_block = get_irg_start_block(get_irn_irg(irn));
	unsigned  n_blocks    = get_Block_dom_max_subtree_pre_num(start_block);
	bitset_t *reloads     = bitset_alloca(n_blocks);
	for (reloader_t *r = si->reloaders; r != NULL; r = r->next) {
		ir_node *block = get_nodes_block(r->reloader);
		bitset_set(reloads, get_Block_dom_tree_pre_num(block));
620
621
622
623
624
	}

	/* Now, cancel out all the blocks that are dominated by each spill.
	 * If the bitset is not empty after that, we have reloads that are
	 * not dominated by any spill. */
Matthias Braun's avatar
Matthias Braun committed
625
626
627
628
	for (spill_t *s = si->spills; s != NULL; s = s->next) {
		ir_node *block = get_nodes_block(s->after);
		unsigned start = get_Block_dom_tree_pre_num(block);
		unsigned end   = get_Block_dom_max_subtree_pre_num(block);
629
630
631
632
633
634
635
636
637
		bitset_clear_range(reloads, start, end);
	}

	if (!bitset_is_empty(reloads))
		be_add_spill(env, si->to_spill, si->to_spill);
}

void be_insert_spills_reloads(spill_env_t *env)
{
638
	be_timer_push(T_RA_SPILL_APPLY);
639
640
641

	/* create all phi-ms first, this is needed so, that phis, hanging on
	   spilled phis work correctly */
642
643
	for (spill_info_t *info = env->mem_phis; info != NULL;
	     info = info->next_mem_phi) {
644
645
646
647
		spill_node(env, info);
	}

	/* process each spilled node */
648
	for (spill_info_t *si = env->spills; si != NULL; si = si->next) {
649
650
651
		ir_node  *to_spill        = si->to_spill;
		ir_node **copies          = NEW_ARR_F(ir_node*, 0);
		double    all_remat_costs = 0; /** costs when we would remat all nodes */
652
		bool      force_remat     = false;
653
654
655
656
657
658

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

		determine_spill_costs(env, si);

		/* determine possibility of rematerialisations */
659
		if (be_do_remats) {
yb9976's avatar
yb9976 committed
660
661
			/* calculate cost savings for each individual value when it would
			   be rematerialised instead of reloaded */
Matthias Braun's avatar
Matthias Braun committed
662
663
			for (reloader_t *rld = si->reloaders; rld != NULL;
			     rld = rld->next) {
664
				ir_node *reloader = rld->reloader;
665
				if (rld->remat_cost_delta >= REMAT_COST_INFINITE) {
666
667
668
669
670
671
					DBG((dbg, LEVEL_2, "\treload before %+F is forbidden\n",
					     reloader));
					all_remat_costs = REMAT_COST_INFINITE;
					continue;
				}

Matthias Braun's avatar
Matthias Braun committed
672
673
				int remat_cost = check_remat_conditions_costs(env, to_spill,
				                                              reloader, 0);
674
				if (remat_cost >= REMAT_COST_INFINITE) {
675
676
677
678
679
680
681
					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;
				}

Matthias Braun's avatar
Matthias Braun committed
682
				int remat_cost_delta  = remat_cost - env->reload_cost;
683
				rld->remat_cost_delta = remat_cost_delta;
Matthias Braun's avatar
Matthias Braun committed
684
685
				ir_node *block        = get_block(reloader);
				double   freq         = get_block_execfreq(block);
686
687
688
689
690
				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));
			}
691
			if (all_remat_costs < REMAT_COST_INFINITE) {
692
693
694
695
696
697
698
				/* we don't need the costs for the spill if we can remat
				   all reloaders */
				all_remat_costs -= si->spill_costs;
				DBG((dbg, LEVEL_2, "\tspill costs %d (rel %f)\n",
				     env->spill_cost, si->spill_costs));
			}

699
			if (all_remat_costs < 0) {
Matthias Braun's avatar
Matthias Braun committed
700
				force_remat = true;
701
702
703
704
705
706
				DBG((dbg, LEVEL_1, "\nforcing remats of all reloaders (%f)\n",
				     all_remat_costs));
			}
		}

		/* go through all reloads for this spill */
Matthias Braun's avatar
Matthias Braun committed
707
		for (reloader_t *rld = si->reloaders; rld != NULL; rld = rld->next) {
708
			ir_node *copy; /* a reload is a "copy" of the original value */
709
			if (be_do_remats && (force_remat || rld->remat_cost_delta < 0)) {
710
				copy = do_remat(env, to_spill, rld->reloader);
Christoph Mallon's avatar
Christoph Mallon committed
711
				++env->remat_count;
712
713
714
715
716
717
718
			} else {
				/* make sure we have a spill */
				spill_node(env, si);

				/* create a reload, use the first spill for now SSA
				 * reconstruction for memory comes below */
				assert(si->spills != NULL);
719
720
				copy = arch_env_new_reload(env->arch_env, si->to_spill,
				                           si->spills->spill, rld->reloader);
721
722
723
724
725
726
727
728
729
730
731
732
				env->reload_count++;
			}

			DBG((dbg, LEVEL_1, " %+F of %+F before %+F\n",
			     copy, to_spill, rld->reloader));
			ARR_APP1(ir_node*, copies, copy);
		}

		/* if we had any reloads or remats, then we need to reconstruct the
		 * SSA form for the spilled value */
		if (ARR_LEN(copies) > 0) {
			be_ssa_construction_env_t senv;
733
			be_ssa_construction_init(&senv, env->irg);
734
735
736
737
738
739
740
741
			be_ssa_construction_add_copy(&senv, to_spill);
			be_ssa_construction_add_copies(&senv, copies, ARR_LEN(copies));
			be_ssa_construction_fix_users(&senv, to_spill);
			be_ssa_construction_destroy(&senv);
		}
		/* need to reconstruct SSA form if we had multiple spills */
		if (si->spills != NULL && si->spills->next != NULL) {
			be_ssa_construction_env_t senv;
742
			be_ssa_construction_init(&senv, env->irg);
Matthias Braun's avatar
Matthias Braun committed
743
744
745
			unsigned spill_count = 0;
			for (spill_t *spill = si->spills ; spill != NULL;
			     spill = spill->next) {
746
				/* maybe we rematerialized the value and need no spill */
747
				if (spill->spill == NULL)
748
749
					continue;
				be_ssa_construction_add_copy(&senv, spill->spill);
Matthias Braun's avatar
Matthias Braun committed
750
				++spill_count;
751
			}
752
			if (spill_count > 1) {
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
				/* all reloads are attached to the first spill, fix them now */
				be_ssa_construction_fix_users(&senv, si->spills->spill);
			}

			be_ssa_construction_destroy(&senv);
		}

		DEL_ARR_F(copies);
		si->reloaders = NULL;
	}

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

	/* Matze: In theory be_ssa_construction should take care of the liveness...
	 * try to disable this again in the future */
771
	be_invalidate_live_sets(env->irg);
772

773
	be_remove_dead_nodes_from_schedule(env->irg);
774

775
	be_timer_pop(T_RA_SPILL_APPLY);
776
777
}

778
779
780
781
782
783
784
785
786
787
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
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
static be_irg_t      *birg;
static be_lv_t       *lv;
static unsigned long  precol_copies;
static unsigned long  multi_precol_copies;
static unsigned long  constrained_livethrough_copies;

static void prepare_constr_insn(ir_node *const node)
{
	/* Insert a copy for constraint inputs attached to a value which can't
	 * fulfill the constraint
	 * (typical example: stack pointer as input to copyb)
	 * TODO: This really just checks precolored registers at the moment and
	 *       ignores the general case of not matching in/out constraints */
	foreach_irn_in(node, i, op) {
		const arch_register_req_t *const req
			= arch_get_irn_register_req_in(node, i);
		if (req->cls == NULL)
			continue;

		const arch_register_t *const reg = arch_get_irn_register(op);
		if (reg == NULL)
			continue;

		/* Precolored with an ignore register (which is not virtual). */
		if ((reg->type & arch_register_type_virtual) ||
		    rbitset_is_set(birg->allocatable_regs, reg->global_index))
			continue;

		if (!arch_register_req_is(req, limited))
			continue;
		if (rbitset_is_set(req->limited, reg->index))
			continue;

		ir_node *block = get_nodes_block(node);
		ir_node *copy  = be_new_Copy(block, op);
		sched_add_before(node, copy);
		set_irn_n(node, i, copy);
		++precol_copies;
		DBG((dbg_constr, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n",
		     copy, node, i));
	}

	/* insert copies for nodes that occur constrained more than once. */
	for (int i = 0, arity = get_irn_arity(node); i < arity; ++i) {
		const arch_register_req_t *const req
			= arch_get_irn_register_req_in(node, i);
		const arch_register_class_t *const cls = req->cls;
		if (cls == NULL)
			continue;
		if (!arch_register_req_is(req, limited))
			continue;

		ir_node *in = get_irn_n(node, i);
		const arch_register_req_t *const in_req
			= arch_get_irn_register_req(in);
		if (arch_register_req_is(in_req, ignore))
			continue;
		for (int i2 = i + 1; i2 < arity; ++i2) {
			const arch_register_req_t *const req2
				= arch_get_irn_register_req_in(node, i2);
			if (req2->cls != cls)
				continue;
			if (!arch_register_req_is(req2, limited))
				continue;

			ir_node *in2 = get_irn_n(node, i2);
			if (in2 != in)
				continue;

			/* if the constraint is the same, no copy is necessary
			 * TODO generalise to unequal but overlapping constraints */
			if (rbitsets_equal(req->limited, req2->limited, cls->n_regs))
				continue;

			ir_node *block = get_nodes_block(node);
			ir_node *copy  = be_new_Copy(block, in);
			sched_add_before(node, copy);
			set_irn_n(node, i2, copy);
			++multi_precol_copies;
			DBG((dbg_constr, LEVEL_3,
			     "inserting multiple constr copy %+F for %+F pos %d\n",
			     copy, node, i2));
		}
	}

	/* collect all registers occurring in out constraints. */
	unsigned *def_constr = NULL;
	be_foreach_value(node, value,
		const arch_register_req_t *const req = arch_get_irn_register_req(value);
		const arch_register_class_t *const cls = req->cls;
		if (cls == NULL)
			continue;
		if (!arch_register_req_is(req, limited))
			continue;
		if (def_constr == NULL) {
			const arch_env_t *const arch_env = birg->main_env->arch_env;
			def_constr = rbitset_alloca(arch_env->n_registers);
		}
		rbitset_foreach(req->limited, cls->n_regs, e) {
			const arch_register_t *reg = arch_register_for_index(cls, e);
			rbitset_set(def_constr, reg->global_index);
		}
	);
	/* no output constraints => we're good */
	if (def_constr == NULL)
		return;

	/* Insert copies for all constrained arguments living through the node and
	 * being constrained to a register which also occurs in out constraints. */
	for (int i = 0, arity = get_irn_arity(node); i < arity; ++i) {
		/* Check, if
		 * 1) the operand is constrained.
		 * 2) lives through the node.
		 * 3) is constrained to a register occurring in out constraints. */
		const arch_register_req_t *const req
			= arch_get_irn_register_req_in(node, i);
		const arch_register_class_t *const cls = req->cls;
		if (cls == NULL)
			continue;
		if (!arch_register_req_is(req, limited))
			continue;
		ir_node *in = get_irn_n(node, i);
		const arch_register_req_t *const in_req
			= arch_get_irn_register_req(in);
		if (arch_register_req_is(in_req, ignore))
			continue;
		/* Only create the copy if the operand is no copy.
		 * this is necessary since the assure constraints phase inserts
		 * Copies and Keeps for operands which must be different from the
		 * results. Additional copies here would destroy this. */
		if (be_is_Copy(in))
			continue;
		if (!be_value_live_after(in, node))
			continue;

		bool common_limits = false;
		rbitset_foreach(req->limited, cls->n_regs, e) {
			const arch_register_t *reg = arch_register_for_index(cls, e);
			if (rbitset_is_set(def_constr, reg->global_index)) {
				common_limits = true;
				break;
			}
		}
		if (!common_limits)
			continue;

		ir_node *block = get_nodes_block(node);
		ir_node *copy  = be_new_Copy(block, in);
		sched_add_before(node, copy);
		set_irn_n(node, i, copy);
		++constrained_livethrough_copies;
		DBG((dbg_constr, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n",
		     copy, node, i));
		be_liveness_update(lv, in);
	}
}

static void add_missing_copies_in_block(ir_node *block, void *data)
{
	(void)data;
	sched_foreach(block, node) {
		prepare_constr_insn(node);
	}
}

static bool has_irn_users(const ir_node *irn)
{
	return get_irn_out_edge_first_kind(irn, EDGE_KIND_NORMAL) != 0;
}

static ir_node *find_copy(ir_node *irn, ir_node *op)
{
Matthias Braun's avatar
Matthias Braun committed
950
	for (ir_node *cur_node = irn;;) {
951
		cur_node = sched_prev(cur_node);
Matthias Braun's avatar
Matthias Braun committed
952
		if (!be_is_Copy(cur_node))
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
			return NULL;
		if (be_get_Copy_op(cur_node) == op && arch_irn_is(cur_node, dont_spill))
			return cur_node;
	}
}

/** Environment for constraints. */
typedef struct {
	ir_nodehashmap_t op_set;
	struct obstack   obst;
} constraint_env_t;

/** Associates an ir_node with its copy and CopyKeep. */
typedef struct {
	ir_nodeset_t copies; /**< all non-spillable copies of this irn */
} op_copy_assoc_t;

static void gen_assure_different_pattern(ir_node *irn, ir_node *other_different, constraint_env_t *env)
{
	arch_register_req_t const *const req = arch_get_irn_register_req(other_different);
	if (arch_register_req_is(req, ignore) ||
			!mode_is_data(get_irn_mode(other_different))) {
		DB((dbg_constr, LEVEL_1, "ignore constraint for %+F because other_irn is ignore or not a data node\n", irn));
		return;
	}

979
980
	ir_nodehashmap_t *op_set = &env->op_set;
	ir_node          *block  = get_nodes_block(irn);
981
982
983
984
985
986
987

	/* Make a not spillable copy of the different node   */
	/* this is needed because the different irn could be */
	/* in block far far away                             */
	/* The copy is optimized later if not needed         */

	/* check if already exists such a copy in the schedule immediately before */
Matthias Braun's avatar
Matthias Braun committed
988
989
	ir_node *cpy = find_copy(skip_Proj(irn), other_different);
	if (cpy == NULL) {
990
		cpy = be_new_Copy(block, other_different);
991
		arch_add_irn_flags(cpy, arch_irn_flag_dont_spill);
992
993
994
995
996
997
998
		DB((dbg_constr, LEVEL_1, "created non-spillable %+F for value %+F\n", cpy, other_different));
	} else {
		DB((dbg_constr, LEVEL_1, "using already existing %+F for value %+F\n", cpy, other_different));
	}

	/* Add the Keep resp. CopyKeep and reroute the users */
	/* of the other_different irn in case of CopyKeep.   */
Matthias Braun's avatar
Matthias Braun committed
999
	ir_node *keep;
1000
	if (has_irn_users(other_different)) {
For faster browsing, not all history is shown. View entire blame