bespillutil.c 41.4 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
42
#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 "panic.h"
#include "statev_t.h"
#include "type_t.h"
#include "util.h"
43

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

#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
54
	                                  compared to placing a reload */
55
56
57
58
59
60
61
62
63
64
65
};

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 {
66
67
	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
68
	                              reloaded */
69
	spill_t      *spills;    /**< list of latest places where spill must be
Matthias Braun's avatar
Matthias Braun committed
70
	                              placed */
71
72
73
74
75
76
	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 */
77
78
79
80
81
};

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

111
	return info;
112
113
}

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

118
119
120
121
122
123
	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);
124
125
126
127
128
129
	obstack_init(&env->obst);
	return env;
}

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

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

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

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

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

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

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

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

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

214
215
216
217
/**
 * determine final spill position: it should be after all phis, keep nodes
 * and behind nodes marked as prolog
 */
Matthias Braun's avatar
Matthias Braun committed
218
static ir_node *determine_spill_point(ir_node *const node)
219
{
Matthias Braun's avatar
Matthias Braun committed
220
	ir_node *n = skip_Proj(node);
221
	while (true) {
Matthias Braun's avatar
Matthias Braun committed
222
		ir_node *next = sched_next(n);
223
		if (!is_Phi(next) && !be_is_Keep(next) && !be_is_CopyKeep(next))
224
			break;
Matthias Braun's avatar
Matthias Braun committed
225
		n = next;
226
	}
Matthias Braun's avatar
Matthias Braun committed
227
	return n;
228
229
230
231
232
233
234
235
236
237
238
}

/**
 * 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. */
239
	if (get_Block_n_cfgpreds(block) == 1) {
240
241
242
243
244
		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
245
	ir_node *predblock = get_Block_cfgpred_block(block, pos);
246
247
248
249
	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
250
                           int pos)
251
252
{
	ir_node *before = get_block_insertion_point(block, pos);
Matthias Braun's avatar
Matthias Braun committed
253
	be_add_reload(env, to_spill, before);
254
255
256
257
258
259
}

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

Matthias Braun's avatar
Matthias Braun committed
260
	spill_info_t *info = get_spillinfo(env, node);
261
262
263
	info->spilled_phi  = true;
	info->next_mem_phi = env->mem_phis;
	env->mem_phis      = info;
264
265

	/* create spills for the phi arguments */
Matthias Braun's avatar
Matthias Braun committed
266
	ir_node *block = get_nodes_block(node);
267
	foreach_irn_in(node, i, arg) {
268
269
		/* some backends have virtual noreg/unknown nodes that are not scheduled
		 * and simply always available. */
Matthias Braun's avatar
Matthias Braun committed
270
		ir_node *insert;
271
		if (!sched_is_scheduled(arg)) {
272
273
274
275
			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 {
276
			insert = determine_spill_point(arg);
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
		}
		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
299
300
	ir_node       *to_spill = spillinfo->to_spill;
	const ir_node *insn     = skip_Proj_const(to_spill);
301
	if (!sched_is_scheduled(insn)) {
302
		/* override spillinfos or create a new one */
303
		ir_graph *irg = get_irn_irg(to_spill);
304
		spillinfo->spills->spill = get_irg_no_mem(irg);
305
306
307
308
309
		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
310
311
	for (spill_t *spill = spillinfo->spills; spill != NULL;
	     spill = spill->next) {
312
		ir_node *after = spill->after;
313
		after = determine_spill_point(after);
314

315
		spill->spill = arch_env_new_spill(env->arch_env, to_spill, after);
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
		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
337
	ir_node *phi = spillinfo->to_spill;
338
339
340
	DBG((dbg, LEVEL_1, "spilling Phi %+F:\n", phi));

	/* build a new PhiM */
341
342
	int       const arity   = get_Phi_n_preds(phi);
	ir_node **const ins     = ALLOCAN(ir_node*, arity);
Matthias Braun's avatar
Matthias Braun committed
343
	ir_graph *const irg     = env->irg;
344
	ir_node  *const unknown = new_r_Unknown(irg, mode_M);
345
	for (int i = 0; i < arity; ++i) {
346
347
348
349
		ins[i] = unknown;
	}

	/* override or replace spills list... */
Matthias Braun's avatar
Matthias Braun committed
350
351
352
353
354
	ir_node *block = get_nodes_block(phi);
	spill_t *spill = OALLOC(&env->obst, spill_t);
	spill->after   = determine_spill_point(phi);
	spill->spill   = be_new_Phi(block, arity, ins, mode_M, arch_no_register_req);
	spill->next    = NULL;
Matthias Braun's avatar
Matthias Braun committed
355
	sched_add_after(block, spill->spill);
356
357
358
359

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

360
	foreach_irn_in(phi, i, arg) {
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
		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 */
381
	if (spillinfo->spills != NULL && spillinfo->spills->spill != NULL)
382
383
		return;

384
	if (spillinfo->spilled_phi) {
385
386
387
388
389
390
391
392
		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
393
 * @returns true if value is available
394
 */
Matthias Braun's avatar
Matthias Braun committed
395
static bool is_value_available(spill_env_t *env, const ir_node *arg)
396
{
397
	if (is_Unknown(arg) || is_NoMem(arg))
Matthias Braun's avatar
Matthias Braun committed
398
		return true;
399
	if (arch_irn_is(skip_Proj_const(arg), spill))
Matthias Braun's avatar
Matthias Braun committed
400
		return true;
401
	if (arg == get_irg_frame(env->irg))
Matthias Braun's avatar
Matthias Braun committed
402
		return true;
403
	if (get_irn_mode(arg) == mode_T)
Matthias Braun's avatar
Matthias Braun committed
404
405
		return false;
	/* "Ignore registers" are always available */
406
	if (arch_irn_is_ignore(arg))
Matthias Braun's avatar
Matthias Braun committed
407
		return true;
408

Matthias Braun's avatar
Matthias Braun committed
409
	return false;
410
411
412
413
414
415
416
417
418
419
420
421
422
}

/**
 * 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
423
424
425
                                        const ir_node *spilled,
                                        const ir_node *reloader,
                                        int parentcosts)
426
{
427
	const ir_node *insn = skip_Proj_const(spilled);
428

429
	assert(!arch_irn_is(insn, spill));
430
	if (!arch_irn_is(insn, rematerializable))
431
432
		return REMAT_COST_INFINITE;

Matthias Braun's avatar
Matthias Braun committed
433
	int costs = arch_get_op_estimated_cost(insn);
434
	if (parentcosts + costs >= env->reload_cost + env->spill_cost)
435
		return REMAT_COST_INFINITE;
436

437
	/* never rematerialize a node which modifies the flags.
438
	 * (would be better to test whether the flags are actually live at point
439
440
	 * reloader...)
	 */
Matthias Braun's avatar
Matthias Braun committed
441
	if (arch_irn_is(insn, modify_flags))
442
443
		return REMAT_COST_INFINITE;

Matthias Braun's avatar
Matthias Braun committed
444
	int argremats = 0;
445
	foreach_irn_in(insn, i, arg) {
Matthias Braun's avatar
Matthias Braun committed
446
		if (is_value_available(env, arg))
447
448
449
			continue;

		/* we have to rematerialize the argument as well */
450
		++argremats;
451
		if (argremats > 1) {
452
			/* we only support rematerializing 1 argument at the moment,
453
			 * as multiple arguments could increase register pressure */
454
455
456
457
458
			return REMAT_COST_INFINITE;
		}

		costs += check_remat_conditions_costs(env, arg, reloader,
		                                      parentcosts + costs);
459
		if (parentcosts + costs >= env->reload_cost + env->spill_cost)
460
461
462
463
464
465
466
467
468
			return REMAT_COST_INFINITE;
	}

	return costs;
}

/**
 * Re-materialize a node.
 *
Michael Beck's avatar
Michael Beck committed
469
 * @param env       the spill environment
470
471
472
473
474
 * @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
475
	ir_node **ins = ALLOCAN(ir_node*, get_irn_arity(spilled));
476
	foreach_irn_in(spilled, i, arg) {
Matthias Braun's avatar
Matthias Braun committed
477
		if (is_value_available(env, arg)) {
478
479
480
481
482
483
484
			ins[i] = arg;
		} else {
			ins[i] = do_remat(env, arg, reloader);
		}
	}

	/* create a copy of the node */
485
486
	ir_node *const bl  = get_nodes_block(reloader);
	ir_node *const res = new_similar_node(spilled, bl, ins);
487
488
	arch_env_mark_remat(env->arch_env, res);

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

Christoph Mallon's avatar
Christoph Mallon committed
492
	if (!is_Proj(res))
493
494
495
496
497
498
499
		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
500
	(void)to_spill;
501
	ir_node *block = get_nodes_block(before);
502
	double   freq  = get_block_execfreq(block);
503
504
505
	return env->spill_cost * freq;
}

Matthias Braun's avatar
Matthias Braun committed
506
507
unsigned be_get_reload_costs_no_weight(spill_env_t *env,
                                       const ir_node *to_spill,
508
509
                                       const ir_node *before)
{
510
	if (be_do_remats) {
511
512
		/* is the node rematerializable? */
		unsigned costs = check_remat_conditions_costs(env, to_spill, before, 0);
513
		if (costs < (unsigned) env->reload_cost)
514
515
516
517
518
519
520
521
			return costs;
	}

	return env->reload_cost;
}

double be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before)
{
522
523
	ir_node *block = get_nodes_block(before);
	double   freq  = get_block_execfreq(block);
524

525
	if (be_do_remats) {
526
527
		/* is the node rematerializable? */
		int costs = check_remat_conditions_costs(env, to_spill, before, 0);
528
		if (costs < env->reload_cost)
529
530
531
532
533
534
			return costs * freq;
	}

	return env->reload_cost * freq;
}

Matthias Braun's avatar
Matthias Braun committed
535
536
bool be_is_rematerializable(spill_env_t *env, const ir_node *to_remat,
                            const ir_node *before)
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
{
	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? */
554
	if (spillinfo->spill_costs >= 0)
555
556
		return;

Matthias Braun's avatar
Matthias Braun committed
557
558
	ir_node       *to_spill = spillinfo->to_spill;
	const ir_node *insn     = skip_Proj_const(to_spill);
559
	assert(!arch_irn_is(insn, dont_spill));
560
	assert(!arch_irn_is(insn, reload));
561
562
563
564
565
566

	/* 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...
	 */
567
	if (!sched_is_scheduled(insn)) {
568
		ir_graph *irg = get_irn_irg(to_spill);
569
		/* override spillinfos or create a new one */
570
		spill_t *spill = OALLOC(&env->obst, spill_t);
571
572
		spill->after = NULL;
		spill->next  = NULL;
573
		spill->spill = get_irg_no_mem(irg);
574
575
576
577
578
579
580
581

		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
582
583
	ir_node *spill_block    = get_nodes_block(insn);
	double   spill_execfreq = get_block_execfreq(spill_block);
584

585
	if (spillinfo->spilled_phi) {
586
587
588
589
590
591
		/* 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;
	}

592
	if (spillinfo->spills != NULL) {
593
		/* calculate sum of execution frequencies of individual spills */
Matthias Braun's avatar
Matthias Braun committed
594
595
		double spills_execfreq = 0;
		for (spill_t *s = spillinfo->spills; s != NULL; s = s->next) {
596
			ir_node *spill_block = get_block(s->after);
Matthias Braun's avatar
Matthias Braun committed
597
			double   freq        = get_block_execfreq(spill_block);
598
599
600
601
602
603
604
605
606

			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*/
607
		if (spills_execfreq < spill_execfreq) {
608
609
610
611
612
613
614
			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
615
616
617
618
	spill_t *spill = OALLOC(&env->obst, spill_t);
	spill->after   = determine_spill_point(to_spill);
	spill->next    = NULL;
	spill->spill   = NULL;
619
620
621
622
623
624
625
626
627
628
629
630
631
632

	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
633
634
635
636
637
638
	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));
639
640
641
642
643
	}

	/* 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
644
645
646
647
	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);
648
649
650
651
652
653
654
655
656
		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)
{
657
	be_timer_push(T_RA_SPILL_APPLY);
658
659
660

	/* create all phi-ms first, this is needed so, that phis, hanging on
	   spilled phis work correctly */
661
662
	for (spill_info_t *info = env->mem_phis; info != NULL;
	     info = info->next_mem_phi) {
663
664
665
666
		spill_node(env, info);
	}

	/* process each spilled node */
667
	for (spill_info_t *si = env->spills; si != NULL; si = si->next) {
668
669
670
		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 */
671
		bool      force_remat     = false;
672
673
674
675
676
677

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

		determine_spill_costs(env, si);

		/* determine possibility of rematerialisations */
678
		if (be_do_remats) {
yb9976's avatar
yb9976 committed
679
680
			/* calculate cost savings for each individual value when it would
			   be rematerialised instead of reloaded */
Matthias Braun's avatar
Matthias Braun committed
681
682
			for (reloader_t *rld = si->reloaders; rld != NULL;
			     rld = rld->next) {
683
				ir_node *reloader = rld->reloader;
684
				if (rld->remat_cost_delta >= REMAT_COST_INFINITE) {
685
686
687
688
689
690
					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
691
692
				int remat_cost = check_remat_conditions_costs(env, to_spill,
				                                              reloader, 0);
693
				if (remat_cost >= REMAT_COST_INFINITE) {
694
695
696
697
698
699
700
					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
701
				int remat_cost_delta  = remat_cost - env->reload_cost;
702
				rld->remat_cost_delta = remat_cost_delta;
Matthias Braun's avatar
Matthias Braun committed
703
704
				ir_node *block        = get_block(reloader);
				double   freq         = get_block_execfreq(block);
705
706
707
708
709
				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));
			}
710
			if (all_remat_costs < REMAT_COST_INFINITE) {
711
712
713
714
715
716
717
				/* 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));
			}

718
			if (all_remat_costs < 0) {
Matthias Braun's avatar
Matthias Braun committed
719
				force_remat = true;
720
721
722
723
724
725
				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
726
		for (reloader_t *rld = si->reloaders; rld != NULL; rld = rld->next) {
727
			ir_node *copy; /* a reload is a "copy" of the original value */
728
			if (be_do_remats && (force_remat || rld->remat_cost_delta < 0)) {
729
				copy = do_remat(env, to_spill, rld->reloader);
Christoph Mallon's avatar
Christoph Mallon committed
730
				++env->remat_count;
731
732
733
734
735
736
737
			} 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);
738
739
				copy = arch_env_new_reload(env->arch_env, si->to_spill,
				                           si->spills->spill, rld->reloader);
740
741
742
743
744
745
746
747
748
749
750
751
				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;
752
			be_ssa_construction_init(&senv, env->irg);
753
754
755
756
757
758
759
760
			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;
761
			be_ssa_construction_init(&senv, env->irg);
Matthias Braun's avatar
Matthias Braun committed
762
763
764
			unsigned spill_count = 0;
			for (spill_t *spill = si->spills ; spill != NULL;
			     spill = spill->next) {
765
				/* maybe we rematerialized the value and need no spill */
766
				if (spill->spill == NULL)
767
768
					continue;
				be_ssa_construction_add_copy(&senv, spill->spill);
Matthias Braun's avatar
Matthias Braun committed
769
				++spill_count;
770
			}
771
			if (spill_count > 1) {
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
				/* 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 */
790
	be_invalidate_live_sets(env->irg);
791

792
	be_remove_dead_nodes_from_schedule(env->irg);
793

794
	be_timer_pop(T_RA_SPILL_APPLY);
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
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
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
969
	for (ir_node *cur_node = irn;;) {
970
		cur_node = sched_prev(cur_node);
Matthias Braun's avatar
Matthias Braun committed
971
		if (!be_is_Copy(cur_node))
972
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
			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 */
	const arch_register_class_t *cls;
} 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;
	}

Matthias Braun's avatar
Matthias Braun committed
999
1000
1001
	ir_nodehashmap_t            *op_set = &env->op_set;
	ir_node                     *block  = get_nodes_block(irn);
	const arch_register_class_t *cls    = req->cls;
1002
1003
1004
1005
1006
1007
1008

	/* 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
1009
1010
	ir_node *cpy = find_copy(skip_Proj(irn), other_different);
	if (cpy == NULL) {
1011
		cpy = be_new_Copy(block, other_different);
1012
		arch_add_irn_flags(cpy, arch_irn_flag_dont_spill);
1013
1014
1015
1016
1017
1018
1019
		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
1020
	ir_node *keep;
1021
1022
1023
	if (has_irn_users(other_different)) {
		keep = be_new_CopyKeep_single(block, cpy, irn);
	} else {
Matthias Braun's avatar
Matthias Braun committed
1024
1025
		ir_node *in[] = { irn, cpy };
		keep = be_new_Keep(block, ARRAY_SIZE(in), in);
1026
1027
1028
1029
1030
1031
	}

	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
1032
	if (!sched_is_scheduled(cpy))
1033
1034
1035
1036
		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
1037
1038
1039
	op_copy_assoc_t *entry
		= ir_nodehashmap_get(op_copy_assoc_t, op_set, other_different);
	if (entry == NULL) {
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
		entry      = OALLOC(&env->obst, op_copy_assoc_t);
		entry->cls = cls;
		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
1086
		for (unsigned i = 0; 1U << i <= other; ++i) {
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
			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
 * (or Projs of the same node), copying the same operand.
 */
static void melt_copykeeps(constraint_env_t *cenv)
{
	struct obstack obst;
	obstack_init(&obst);

	/* for all */
	ir_nodehashmap_entry_t    map_entry;
	ir_nodehashmap_iterator_t map_iter;
	foreach_ir_nodehashmap(&cenv->op_set, map_entry, map_iter) {
		op_copy_assoc_t *entry = (op_copy_assoc_t*)map_entry.data;

		/* collect all copykeeps */
		unsigned num_ck = 0;
		foreach_ir_nodeset(&entry->copies, cp, iter) {
			if (be_is_CopyKeep(cp)) {
				obstack_grow(&obst, &cp, sizeof(cp));
				++num_ck;
			}
		}

		/* compare each copykeep with all other copykeeps */
		ir_node **ck_arr = (ir_node **)obstack_finish(&obst);
		for (unsigned idx = 0; idx < num_ck; ++idx) {
			if (ck_arr[idx] == NULL)
				continue;
			unsigned n_melt     = 1;
			ir_node *ref        = ck_arr[idx];
			ir_node *ref_mode_T = skip_Proj(get_irn_n(ref, 1));
			obstack_grow(&obst, &ref, sizeof(ref));

			DB((dbg_constr, LEVEL_1, "Trying to melt %+F:\n", ref));

			/* check for copykeeps pointing to the same mode_T node as the reference copykeep */
			for (unsigned j = 0; j < num_ck; ++j) {
				if (j == idx)
					continue;
				ir_node *cur_ck = ck_arr[j];
				if (cur_ck == NULL || skip_Proj(get_irn_n(cur_ck, 1)) != ref_mode_T)
					continue;

				obstack_grow(&obst, &cur_ck, sizeof(cur_ck));
				ir_nodeset_remove(&entry->copies, cur_ck);
				DB((dbg_constr, LEVEL_1, "\t%+F\n", cur_ck));
				ck_arr[j] = NULL;
				++n_melt;
				sched_remove(cur_ck);
			}
			ck_arr[idx] = NULL;

			/* check, if we found some candidates for melting */
			if (n_melt == 1) {
				DB((dbg_constr, LEVEL_1, "\tno candidate found\n"));
				continue;
			}

			ir_nodeset_remove(&entry->copies, ref);
			sched_remove(ref);

			ir_node **melt_arr = (ir_node **)obstack_finish(&obst);
			/* melt all found copykeeps */
			ir_node **new_ck_in = ALLOCAN(ir_node*,n_melt);
			for (unsigned j = 0; j < n_melt; ++j) {
				new_ck_in[j] = get_irn_n(melt_arr[j], 1);

				/* now, we can kill the melted keep, except the */
				/* ref one, we still need some information      */
				if (melt_arr[j] != ref)
					kill_node(melt_arr[j]);
			}

			ir_node *const new_ck = be_new_CopyKeep(get_nodes_block(ref), be_get_CopyKeep_op(ref), n_melt, new_ck_in);

			ir_nodeset_insert(&entry->copies, new_ck);

			/* find scheduling point */
			ir_node *sched_pt = ref_mode_T;
			do {
				/* just walk along the schedule until a non-Keep/CopyKeep node is found */
				sched_pt = sched_next(sched_pt);
			} while (be_is_Keep(sched_pt) || be_is_CopyKeep(sched_pt));

			sched_add_before(sched_pt, new_ck);
			DB((dbg_constr, LEVEL_1, "created %+F, scheduled before %+F\n", new_ck, sched_pt));

			/* finally: kill the reference copykeep */
			kill_node(ref);
		}
		obstack_free(&obst, ck_arr);
	}
	obstack_free(&obst, NULL);
}

1209
1210
1211
1212
1213
1214
static ir_node *add_to_keep(ir_node *last_keep,
                            const arch_register_class_t *cls, ir_node *node)
{
	if (last_keep != NULL) {
		be_Keep_add_node(last_keep, cls, node);
	} else {
1215
1216
1217
		ir_node *const in[]  = { node };
		ir_node *const block = get_nodes_block(node);
		last_keep = be_new_Keep(block, ARRAY_SIZE(in), in);
1218

1219
		ir_node *const schedpoint = skip_Proj(node);
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
		if (sched_is_scheduled(schedpoint)) {
			sched_add_after(schedpoint, last_keep);
		}
	}
	return last_keep;
}

/**
 * Tests whether a node has a real user and is not just kept by the End or
 * Anchor node
 */
static bool has_real_user(const ir_node *node)
{
	foreach_out_edge(node, edge) {
		ir_node *user = get_edge_src_irn(edge);
		if (!is_End(user) && !is_Anchor(user))
			return true;
	}
	return false;
}

static void add_missing_keep_walker(ir_node *node, void *data)
{
	(void)data;
	ir_mode *mode = get_irn_mode(node);
	ir_node *last_keep;

	if (mode != mode_T) {
		if (!has_real_user(node)) {
			const arch_register_req_t   *req = arch_get_irn_register_req(node);
			const arch_register_class_t *cls = req->cls;
			if (cls == NULL
					|| (cls->flags & arch_register_class_flag_manual_ra)) {
				return;
			}

			add_to_keep(NULL, cls, node);
		}
		return;
	}

	unsigned n_outs = arch_get_irn_n_outs(node);
	if (n_outs <= 0)
		return;

	unsigned *const found_projs    = rbitset_alloca(n_outs);
	ir_node **const existing_projs = ALLOCANZ(ir_node*, n_outs);
	foreach_out_edge(node, edge) {
		ir_node *succ = get_edge_src_irn(edge);
		ir_mode *mode = get_irn_mode(succ);

		/* The node could be kept */
		if (is_End(succ) || is_Anchor(succ))
			continue;
		if (mode == mode_M || mode == mode_X)
			continue;
		unsigned pn = get_Proj_num(succ);
		existing_projs[pn] = succ;
		if (!has_real_user(succ))
			continue;

		assert(pn < n_outs);
		rbitset_set(found_projs, pn);
	}

	/* are keeps missing? */
	last_keep = NULL;
	for (unsigned i = 0; i < n_outs; ++i) {
		ir_node                     *value;
		const arch_register_req_t   *req;
		const arch_register_class_t *cls;

		if (rbitset_is_set(found_projs, i)) {
			continue;
		}

		req = arch_get_irn_register_req_out(node, i);
		cls = req->cls;
		if (cls == NULL || (cls->flags & arch_register_class_flag_manual_ra)) {
			continue;
		}

		value = existing_projs[i];
		if (value == NULL)
1304
			value = new_r_Proj(node, cls->mode, i);
1305
1306
1307
1308
		last_keep = add_to_keep(last_keep, cls, value);
	}
}

1309
1310
1311
1312
void be_spill_prepare_for_constraints(ir_graph *irg)
{
	FIRM_DBG_REGISTER(dbg_constr, "firm.be.lower.constr");

1313
1314
	irg_walk_graph(irg, add_missing_keep_walker, NULL, NULL);

1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
	constraint_env_t cenv;
	ir_nodehashmap_init(&cenv.op_set);
	obstack_init(&cenv.obst);

	irg_block_walk_graph(irg, NULL, assure_constraints_walker, &cenv);

	/* melt copykeeps, pointing to projs of */
	/* the same mode_T node and keeping the */
	/* same operand                         */
	melt_copykeeps(&cenv);

	/* for all */
	ir_nodehashmap_iterator_t map_iter;
	ir_nodehashmap_entry_t    map_entry;
	foreach_ir_nodehashmap(&cenv.op_set, map_entry, map_iter) {
Matthias Braun's avatar
Matthias Braun committed
1330
1331
1332
		op_copy_assoc_t *entry    = (op_copy_assoc_t*)map_entry.data;
		size_t           n_copies = ir_nodeset_size(&entry->copies);
		ir_node        **nodes    = ALLOCAN(ir_node*, n_copies);
1333
1334
1335
1336
1337

		/* put the node in an array */
		DBG((dbg_constr, LEVEL_1, "introduce copies for %+F ", map_entry.node));

		/* collect all copies */
Matthias Braun's avatar
Matthias Braun committed
1338
		size_t n = 0;
1339
1340
1341
1342
1343
1344
1345
1346
		foreach_ir_nodeset(&entry->copies, cp, iter) {
			nodes[n++] = cp;
			DB((dbg_constr, LEVEL_1, ", %+F ", cp));
		}

		DB((dbg_constr, LEVEL_1, "\n"));

		/* introduce the copies for the operand and its copies */
Matthias Braun's avatar
Matthias Braun committed
1347
		be_ssa_construction_env_t senv;
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
		be_ssa_construction_init(&senv, irg);
		be_ssa_construction_add_copy(&senv, map_entry.node);
		be_ssa_construction_add_copies(&senv, nodes, n);
		be_ssa_construction_fix_users(&senv, map_entry.node);
		be_ssa_construction_destroy(&senv);

		/* Could be that not all CopyKeeps are really needed, */
		/* so we transform unnecessary ones into Keeps.       */
		foreach_ir_nodeset(&entry->copies, cp, iter) {
			if (be_is_CopyKeep(cp) && get_irn_n_edges(cp) < 1) {
Matthias Braun's avatar
Matthias Braun committed
1358
1359
1360
				int      arity = get_irn_arity(cp);
				ir_node *block = get_nodes_block(cp);
				ir_node *keep  = be_new_Keep(block, arity, get_irn_in(cp) + 1);
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
				sched_replace(cp, keep);

				/* Set all ins (including the block) of the CopyKeep BAD to keep the verifier happy. */
				kill_node(cp);
			}
		}

		ir_nodeset_destroy(&entry->copies);
	}

	ir_nodehashmap_destroy(&cenv.op_set);
	obstack_free(&cenv.obst, NULL);
	be_invalidate_live_sets(irg);

1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
	/* part2: add missing copies */
	precol_copies                  = 0;
	multi_precol_copies            = 0;
	constrained_livethrough_copies = 0;
	be_assure_live_sets(irg);
	birg = be_birg_from_irg(irg);
	lv   = be_get_irg_liveness(irg);
	irg_block_walk_graph(irg, add_missing_copies_in_block, NULL, NULL);

	stat_ev_ull("ra_precol_copies", precol_copies);
	stat_ev_ull("ra_multi_precol_copies", multi_precol_copies);
	stat_ev_ull("ra_constrained_livethrough_copies",
	            constrained_livethrough_copies);
1388
1389
}

Matthias Braun's avatar
Matthias Braun committed
1390
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spill)
1391
1392
1393
1394
void be_init_spill(void)
{
	FIRM_DBG_REGISTER(dbg, "firm.be.spill");
}