bespillutil.c 37 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
};

struct spill_env_t {
	ir_graph         *irg;
80
81
82
	ir_nodehashmap_t  spillmap;
	spill_info_t     *spills;
	spill_info_t     *mem_phis;
83
	struct obstack    obst;
Matthias Braun's avatar
Matthias Braun committed
84
85
	int               spill_cost;  /**< the cost of a single spill node */
	int               reload_cost; /**< the cost of a reload node */
86
87
88
89
90
91
92
93
94
	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)
 */
95
static spill_info_t *get_spillinfo(spill_env_t *env, ir_node *value)
96
{
97
98
99
100
101
102
103
104
105
106
	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;
107
108
	}

109
	return info;
110
111
}

112
spill_env_t *be_new_spill_env(ir_graph *irg)
113
{
114
115
	spill_env_t *env = XMALLOCZ(spill_env_t);
	env->irg         = irg;
116
117
	env->spill_cost  = isa_if->spill_cost;
	env->reload_cost = isa_if->reload_cost;
118
	ir_nodehashmap_init(&env->spillmap);
119
120
121
122
123
124
	obstack_init(&env->obst);
	return env;
}

void be_delete_spill_env(spill_env_t *env)
{
125
	ir_nodehashmap_destroy(&env->spillmap);
126
127
128
129
130
131
	obstack_free(&env->obst, NULL);
	free(env);
}

void be_add_spill(spill_env_t *env, ir_node *to_spill, ir_node *after)
{
132
	assert(!arch_irn_is(skip_Proj_const(to_spill), dont_spill));
133
134
135
136
137
138
	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
139
140
141
	spill_info_t *spill_info = get_spillinfo(env, to_spill);
	for (spill_t *s = spill_info->spills, *last = NULL ; s != NULL;
	     s = s->next) {
142
		/* no need to add this spill if it is dominated by another */
Matthias Braun's avatar
Matthias Braun committed
143
		if (value_strictly_dominates(s->after, after)) {
144
145
146
147
			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
148
		if (value_strictly_dominates(after, s->after)) {
149
			DB((dbg, LEVEL_1, "...remove old spill at %+F\n", s->after));
150
			if (last != NULL) {
151
152
153
154
155
156
157
158
159
				last->next         = s->next;
			} else {
				spill_info->spills = s->next;
			}
		} else {
			last = s;
		}
	}

Matthias Braun's avatar
Matthias Braun committed
160
161
162
163
	spill_t *spill = OALLOC(&env->obst, spill_t);
	spill->after = after;
	spill->next  = spill_info->spills;
	spill->spill = NULL;
164
165
166
	spill_info->spills = spill;
}

Matthias Braun's avatar
Matthias Braun committed
167
void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before)
168
{
169
	assert(!arch_irn_is(skip_Proj_const(to_spill), dont_spill));
Matthias Braun's avatar
Matthias Braun committed
170
	assert(!be_is_Keep(before));
171

Matthias Braun's avatar
Matthias Braun committed
172
	spill_info_t *info = get_spillinfo(env, to_spill);
173
174

	/* put reload into list */
Matthias Braun's avatar
Matthias Braun committed
175
	reloader_t *rel       = OALLOC(&env->obst, reloader_t);
176
177
	rel->next             = info->reloaders;
	rel->reloader         = before;
Matthias Braun's avatar
Matthias Braun committed
178
	rel->remat_cost_delta = 0;
179

Matthias Braun's avatar
Matthias Braun committed
180
	info->reloaders = rel;
181

Matthias Braun's avatar
Matthias Braun committed
182
183
184
	DBG((dbg, LEVEL_1,
	     "creating spillinfo for %+F, will be reloaded before %+F\n",
	     to_spill, before));
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
}

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. */
212
	if (get_Block_n_cfgpreds(block) == 1) {
213
214
215
216
217
		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
218
	ir_node *predblock = get_Block_cfgpred_block(block, pos);
219
220
221
222
	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
223
                           int pos)
224
225
{
	ir_node *before = get_block_insertion_point(block, pos);
Matthias Braun's avatar
Matthias Braun committed
226
	be_add_reload(env, to_spill, before);
227
228
}

229
void be_spill_phi(spill_env_t *const env, ir_node *const phi)
230
{
231
	assert(is_Phi(phi));
232

233
	spill_info_t *info = get_spillinfo(env, phi);
234
235
236
	info->spilled_phi  = true;
	info->next_mem_phi = env->mem_phis;
	env->mem_phis      = info;
237
238

	/* create spills for the phi arguments */
239
	foreach_irn_in(phi, i, arg) {
240
		ir_node *const insert = be_move_after_schedule_first(arg);
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
		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);

260
	ir_node *const to_spill = spillinfo->to_spill;
261
	DBG((dbg, LEVEL_1, "spilling %+F ... \n", to_spill));
Matthias Braun's avatar
Matthias Braun committed
262
263
	for (spill_t *spill = spillinfo->spills; spill != NULL;
	     spill = spill->next) {
264
		ir_node *const after = be_move_after_schedule_first(spill->after);
265
		spill->spill = isa_if->new_spill(to_spill, after);
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
		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
287
	ir_node *phi = spillinfo->to_spill;
288
289
290
	DBG((dbg, LEVEL_1, "spilling Phi %+F:\n", phi));

	/* build a new PhiM */
291
292
293
	ir_node *const block = get_nodes_block(phi);
	ir_node *const phim  = be_new_Phi0(block, mode_M, arch_no_register_req);
	sched_add_after(block, phim);
294
295

	/* override or replace spills list... */
Matthias Braun's avatar
Matthias Braun committed
296
	spill_t *spill = OALLOC(&env->obst, spill_t);
297
298
299
	spill->after = be_move_after_schedule_first(phi);
	spill->spill = phim;
	spill->next  = NULL;
300
301
302
303

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

304
305
	unsigned  const arity = get_Phi_n_preds(phi);
	ir_node **const ins   = ALLOCAN(ir_node*, arity);
306
	foreach_irn_in(phi, i, arg) {
307
308
309
310
311
		spill_info_t *arg_info = get_spillinfo(env, arg);

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

312
		ins[i] = arg_info->spills->spill;
313
	}
314
315
	be_complete_Phi(phim, arity, ins);
	DBG((dbg, LEVEL_1, "... done spilling Phi %+F, created PhiM %+F\n", phi, phim));
316
317
318
319
320
321
322
323
324
325
326
}

/**
 * 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 */
327
	if (spillinfo->spills != NULL && spillinfo->spills->spill != NULL)
328
329
		return;

330
	if (spillinfo->spilled_phi) {
331
332
333
334
335
336
337
338
		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
339
 * @returns true if value is available
340
 */
Matthias Braun's avatar
Matthias Braun committed
341
static bool is_value_available(spill_env_t *env, const ir_node *arg)
342
{
343
	if (is_Unknown(arg) || is_NoMem(arg))
Matthias Braun's avatar
Matthias Braun committed
344
		return true;
345
	if (arch_irn_is(skip_Proj_const(arg), spill))
Matthias Braun's avatar
Matthias Braun committed
346
		return true;
347
	if (arg == get_irg_frame(env->irg))
Matthias Braun's avatar
Matthias Braun committed
348
		return true;
349
	if (get_irn_mode(arg) == mode_T)
Matthias Braun's avatar
Matthias Braun committed
350
351
		return false;
	/* "Ignore registers" are always available */
352
	if (arch_irn_is_ignore(arg))
Matthias Braun's avatar
Matthias Braun committed
353
		return true;
354

Matthias Braun's avatar
Matthias Braun committed
355
	return false;
356
357
358
359
360
361
362
363
364
365
366
367
368
}

/**
 * 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
369
370
371
                                        const ir_node *spilled,
                                        const ir_node *reloader,
                                        int parentcosts)
372
{
373
	const ir_node *insn = skip_Proj_const(spilled);
374

375
	assert(!arch_irn_is(insn, spill));
376
	if (!arch_irn_is(insn, rematerializable))
377
378
		return REMAT_COST_INFINITE;

Matthias Braun's avatar
Matthias Braun committed
379
	int costs = arch_get_op_estimated_cost(insn);
380
	if (parentcosts + costs >= env->reload_cost + env->spill_cost)
381
		return REMAT_COST_INFINITE;
382

383
	/* never rematerialize a node which modifies the flags.
384
	 * (would be better to test whether the flags are actually live at point
385
386
	 * reloader...)
	 */
Matthias Braun's avatar
Matthias Braun committed
387
	if (arch_irn_is(insn, modify_flags))
388
389
		return REMAT_COST_INFINITE;

Matthias Braun's avatar
Matthias Braun committed
390
	int argremats = 0;
391
	foreach_irn_in(insn, i, arg) {
Matthias Braun's avatar
Matthias Braun committed
392
		if (is_value_available(env, arg))
393
394
395
			continue;

		/* we have to rematerialize the argument as well */
396
		++argremats;
397
		if (argremats > 1) {
398
			/* we only support rematerializing 1 argument at the moment,
399
			 * as multiple arguments could increase register pressure */
400
401
402
403
404
			return REMAT_COST_INFINITE;
		}

		costs += check_remat_conditions_costs(env, arg, reloader,
		                                      parentcosts + costs);
405
		if (parentcosts + costs >= env->reload_cost + env->spill_cost)
406
407
408
409
410
411
412
413
414
			return REMAT_COST_INFINITE;
	}

	return costs;
}

/**
 * Re-materialize a node.
 *
Michael Beck's avatar
Michael Beck committed
415
 * @param env       the spill environment
416
417
418
419
420
 * @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
421
	ir_node **ins = ALLOCAN(ir_node*, get_irn_arity(spilled));
422
	foreach_irn_in(spilled, i, arg) {
Matthias Braun's avatar
Matthias Braun committed
423
		if (is_value_available(env, arg)) {
424
425
426
427
428
429
430
			ins[i] = arg;
		} else {
			ins[i] = do_remat(env, arg, reloader);
		}
	}

	/* create a copy of the node */
431
432
	ir_node *const bl  = get_nodes_block(reloader);
	ir_node *const res = new_similar_node(spilled, bl, ins);
433
434
	if (isa_if->mark_remat)
		isa_if->mark_remat(res);
435

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

Christoph Mallon's avatar
Christoph Mallon committed
439
	if (!is_Proj(res))
440
441
442
443
444
445
446
		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
447
	(void)to_spill;
448
	ir_node *block = get_nodes_block(before);
449
	double   freq  = get_block_execfreq(block);
450
451
452
	return env->spill_cost * freq;
}

Matthias Braun's avatar
Matthias Braun committed
453
454
unsigned be_get_reload_costs_no_weight(spill_env_t *env,
                                       const ir_node *to_spill,
455
456
                                       const ir_node *before)
{
457
	if (be_do_remats) {
458
459
		/* is the node rematerializable? */
		unsigned costs = check_remat_conditions_costs(env, to_spill, before, 0);
460
		if (costs < (unsigned) env->reload_cost)
461
462
463
464
465
466
467
468
			return costs;
	}

	return env->reload_cost;
}

double be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before)
{
469
470
	ir_node *block = get_nodes_block(before);
	double   freq  = get_block_execfreq(block);
471

472
	if (be_do_remats) {
473
474
		/* is the node rematerializable? */
		int costs = check_remat_conditions_costs(env, to_spill, before, 0);
475
		if (costs < env->reload_cost)
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
			return costs * freq;
	}

	return env->reload_cost * freq;
}

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? */
495
	if (spillinfo->spill_costs >= 0)
496
497
		return;

Matthias Braun's avatar
Matthias Braun committed
498
499
	ir_node       *to_spill = spillinfo->to_spill;
	const ir_node *insn     = skip_Proj_const(to_spill);
500
	assert(!arch_irn_is(insn, dont_spill));
501
	assert(!arch_irn_is(insn, reload));
502

Matthias Braun's avatar
Matthias Braun committed
503
504
	ir_node *spill_block    = get_nodes_block(insn);
	double   spill_execfreq = get_block_execfreq(spill_block);
505

506
	if (spillinfo->spilled_phi) {
507
508
509
510
511
512
		/* 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;
	}

513
	if (spillinfo->spills != NULL) {
514
		/* calculate sum of execution frequencies of individual spills */
Matthias Braun's avatar
Matthias Braun committed
515
516
		double spills_execfreq = 0;
		for (spill_t *s = spillinfo->spills; s != NULL; s = s->next) {
517
			ir_node *spill_block = get_block(s->after);
Matthias Braun's avatar
Matthias Braun committed
518
			double   freq        = get_block_execfreq(spill_block);
519
520
521
522
523
524
525
526
527

			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*/
528
		if (spills_execfreq < spill_execfreq) {
529
530
531
532
533
534
535
			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
536
	spill_t *spill = OALLOC(&env->obst, spill_t);
537
	spill->after   = be_move_after_schedule_first(skip_Proj(to_spill));
Matthias Braun's avatar
Matthias Braun committed
538
539
	spill->next    = NULL;
	spill->spill   = NULL;
540
541
542
543
544
545
546
547

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

void be_insert_spills_reloads(spill_env_t *env)
{
548
	be_timer_push(T_RA_SPILL_APPLY);
549
550
551

	/* create all phi-ms first, this is needed so, that phis, hanging on
	   spilled phis work correctly */
552
553
	for (spill_info_t *info = env->mem_phis; info != NULL;
	     info = info->next_mem_phi) {
554
555
556
557
		spill_node(env, info);
	}

	/* process each spilled node */
558
	for (spill_info_t *si = env->spills; si != NULL; si = si->next) {
559
560
561
		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 */
562
		bool      force_remat     = false;
563
564
565
566
567
568

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

		determine_spill_costs(env, si);

		/* determine possibility of rematerialisations */
569
		if (be_do_remats) {
yb9976's avatar
yb9976 committed
570
571
			/* calculate cost savings for each individual value when it would
			   be rematerialised instead of reloaded */
Matthias Braun's avatar
Matthias Braun committed
572
573
			for (reloader_t *rld = si->reloaders; rld != NULL;
			     rld = rld->next) {
574
				ir_node *reloader = rld->reloader;
575
				if (rld->remat_cost_delta >= REMAT_COST_INFINITE) {
576
577
578
579
580
581
					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
582
583
				int remat_cost = check_remat_conditions_costs(env, to_spill,
				                                              reloader, 0);
584
				if (remat_cost >= REMAT_COST_INFINITE) {
585
586
587
588
589
590
591
					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
592
				int remat_cost_delta  = remat_cost - env->reload_cost;
593
				rld->remat_cost_delta = remat_cost_delta;
Matthias Braun's avatar
Matthias Braun committed
594
595
				ir_node *block        = get_block(reloader);
				double   freq         = get_block_execfreq(block);
596
597
598
599
600
				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));
			}
601
			if (all_remat_costs < REMAT_COST_INFINITE) {
602
603
604
605
606
607
608
				/* 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));
			}

609
			if (all_remat_costs < 0) {
Matthias Braun's avatar
Matthias Braun committed
610
				force_remat = true;
611
612
613
614
615
616
				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
617
		for (reloader_t *rld = si->reloaders; rld != NULL; rld = rld->next) {
618
			ir_node *copy; /* a reload is a "copy" of the original value */
619
			if (be_do_remats && (force_remat || rld->remat_cost_delta < 0)) {
620
				copy = do_remat(env, to_spill, rld->reloader);
Christoph Mallon's avatar
Christoph Mallon committed
621
				++env->remat_count;
622
623
624
625
626
627
628
			} 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);
629
				copy = isa_if->new_reload(si->to_spill, si->spills->spill, rld->reloader);
630
631
632
633
634
635
636
637
638
639
640
641
				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;
642
			be_ssa_construction_init(&senv, env->irg);
643
644
645
646
647
648
649
650
			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;
651
			be_ssa_construction_init(&senv, env->irg);
Matthias Braun's avatar
Matthias Braun committed
652
653
654
			unsigned spill_count = 0;
			for (spill_t *spill = si->spills ; spill != NULL;
			     spill = spill->next) {
655
				/* maybe we rematerialized the value and need no spill */
656
				if (spill->spill == NULL)
657
658
					continue;
				be_ssa_construction_add_copy(&senv, spill->spill);
Matthias Braun's avatar
Matthias Braun committed
659
				++spill_count;
660
			}
661
			if (spill_count > 1) {
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
				/* 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 */
680
	be_invalidate_live_sets(env->irg);
681

682
	be_remove_dead_nodes_from_schedule(env->irg);
683

684
	be_timer_pop(T_RA_SPILL_APPLY);
685
686
}

687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
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;
781
782
		if (def_constr == NULL)
			def_constr = rbitset_alloca(isa_if->n_registers);
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
		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
857
	for (ir_node *cur_node = irn;;) {
858
		cur_node = sched_prev(cur_node);
Matthias Braun's avatar
Matthias Braun committed
859
		if (!be_is_Copy(cur_node))
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
			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;
	}

886
887
	ir_nodehashmap_t *op_set = &env->op_set;
	ir_node          *block  = get_nodes_block(irn);
888
889
890
891
892
893
894

	/* 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
895
896
	ir_node *cpy = find_copy(skip_Proj(irn), other_different);
	if (cpy == NULL) {
897
		cpy = be_new_Copy(block, other_different);
898
		arch_add_irn_flags(cpy, arch_irn_flag_dont_spill);
899
900
901
902
903
904
905
		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
906
	ir_node *keep;
907
	if (has_irn_users(other_different)) {
908
909
		ir_node *const in[] = { irn };
		keep = be_new_CopyKeep(block, cpy, ARRAY_SIZE(in), in);
910
	} else {
Matthias Braun's avatar
Matthias Braun committed
911
912
		ir_node *in[] = { irn, cpy };
		keep = be_new_Keep(block, ARRAY_SIZE(in), in);
913
914
915
916
917
918
	}

	DB((dbg_constr, LEVEL_1, "created %+F(%+F, %+F)\n\n", keep, irn, cpy));

	/* insert copy and keep into schedule */
	assert(sched_is_scheduled(irn) && "need schedule to assure constraints");
Matthias Braun's avatar
Matthias Braun committed
919
	if (!sched_is_scheduled(cpy))
920
921
922
923
		sched_add_before(skip_Proj(irn), cpy);
	sched_add_after(skip_Proj(irn), keep);

	/* insert the other different and its copies into the map */
Matthias Braun's avatar
Matthias Braun committed
924
925
926
	op_copy_assoc_t *entry
		= ir_nodehashmap_get(op_copy_assoc_t, op_set, other_different);
	if (entry == NULL) {
927
		entry = OALLOC(&env->obst, op_copy_assoc_t);
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
		ir_nodeset_init(&entry->copies);

		ir_nodehashmap_insert(op_set, other_different, entry);
	}

	/* insert copy */
	ir_nodeset_insert(&entry->copies, cpy);

	/* insert keep in case of CopyKeep */
	if (be_is_CopyKeep(keep))
		ir_nodeset_insert(&entry->copies, keep);
}

/**
 * Checks if node has a must_be_different constraint in output and adds a Keep
 * then to assure the constraint.
 *
 * @param irn          the node to check
 * @param skipped_irn  if irn is a Proj node, its predecessor, else irn
 * @param env          the constraint environment
 */
static void assure_different_constraints(ir_node *irn, ir_node *skipped_irn, constraint_env_t *env)
{
	const arch_register_req_t *req = arch_get_irn_register_req(irn);

	if (arch_register_req_is(req, must_be_different)) {
		const unsigned other = req->other_different;

		if (arch_register_req_is(req, should_be_same)) {
			const unsigned same = req->other_same;

			if (is_po2(other) && is_po2(same)) {
				int idx_other = ntz(other);
				int idx_same  = ntz(same);

				/*
				 * We can safely ignore a should_be_same x must_be_different y
				 * IFF both inputs are equal!
				 */
				if (get_irn_n(skipped_irn, idx_other) == get_irn_n(skipped_irn, idx_same)) {
					return;
				}
			}
		}
Matthias Braun's avatar
Matthias Braun committed
972
		for (unsigned i = 0; 1U << i <= other; ++i) {
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
			if (other & (1U << i)) {
				ir_node *different_from = get_irn_n(skipped_irn, i);
				gen_assure_different_pattern(irn, different_from, env);
			}
		}
	}
}

/**
 * Calls the functions to assure register constraints.
 *
 * @param block    The block to be checked
 * @param walk_env The walker environment
 */
static void assure_constraints_walker(ir_node *block, void *walk_env)
{
	constraint_env_t *env = (constraint_env_t*)walk_env;

	sched_foreach_reverse(block, irn) {
		be_foreach_value(irn, value,
			if (mode_is_data(get_irn_mode(value)))
				assure_different_constraints(value, irn, env);
		);
	}
}

/**
 * Melt all copykeeps pointing to the same node
For faster browsing, not all history is shown. View entire blame