bespillbelady.c 25.2 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Daniel Grund's avatar
Daniel Grund committed
6
/**
Christian Würdig's avatar
Christian Würdig committed
7
8
9
10
 * @file
 * @brief       Beladys spillalgorithm.
 * @author      Daniel Grund, Matthias Braun
 * @date        20.09.2005
Daniel Grund's avatar
Daniel Grund committed
11
 */
Matthias Braun's avatar
Matthias Braun committed
12
13
#include <stdbool.h>

Daniel Grund's avatar
Daniel Grund committed
14
15
16
17
#include "obst.h"
#include "irnode.h"
#include "irmode.h"
#include "irgwalk.h"
18
#include "irloop.h"
Daniel Grund's avatar
Daniel Grund committed
19
#include "iredges_t.h"
20
#include "ircons_t.h"
21
#include "irtools.h"
22
#include "statev_t.h"
23
#include "util.h"
Daniel Grund's avatar
Daniel Grund committed
24
25

#include "beutil.h"
26
#include "bearch.h"
Christian Würdig's avatar
Christian Würdig committed
27
#include "beuses.h"
28
#include "besched.h"
Matthias Braun's avatar
Matthias Braun committed
29
#include "belive.h"
30
#include "benode.h"
Sebastian Hack's avatar
Sebastian Hack committed
31
#include "bechordal_t.h"
32
#include "bespill.h"
33
#include "beloopana.h"
34
#include "beirg.h"
35
#include "bespillutil.h"
Christian Würdig's avatar
Christian Würdig committed
36
#include "bemodule.h"
Daniel Grund's avatar
Daniel Grund committed
37

38
39
40
41
42
43
44
#define DBG_SPILL     1
#define DBG_WSETS     2
#define DBG_FIX       4
#define DBG_DECIDE    8
#define DBG_START    16
#define DBG_SLOTS    32
#define DBG_TRACE    64
45
#define DBG_WORKSET 128
46
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
Daniel Grund's avatar
Daniel Grund committed
47

Matthias Braun's avatar
Matthias Braun committed
48
49
#define TIME_UNDEFINED 6666

50
51
52
/**
 * An association between a node and a point in time.
 */
53
54
55
typedef struct loc_t {
	ir_node          *node;
	unsigned          time;     /**< A use time (see beuses.h). */
56
	bool              spilled;  /**< value was already spilled on this path */
57
58
} loc_t;

59
typedef struct workset_t {
60
	unsigned len;     /**< current length */
Matthias Braun's avatar
Matthias Braun committed
61
	loc_t    vals[];  /**< array of the values/distances in this working set */
62
} workset_t;
Daniel Grund's avatar
Daniel Grund committed
63

64
65
66
67
static struct obstack               obst;
static const arch_register_class_t *cls;
static const be_lv_t               *lv;
static be_loopana_t                *loop_ana;
68
static unsigned                     n_regs;
69
70
71
72
static workset_t                   *ws;     /**< the main workset used while
	                                             processing a block. */
static be_uses_t                   *uses;   /**< env for the next-use magic */
static spill_env_t                 *senv;   /**< see bespill.h */
73
static ir_node                    **blocklist;
Matthias Braun's avatar
Matthias Braun committed
74
static workset_t                   *temp_workset;
Daniel Grund's avatar
Daniel Grund committed
75

76
77
78
static bool                         move_spills      = true;
static bool                         respectloopdepth = true;
static bool                         improve_known_preds = true;
79
80
81
82
83
84
/* factor to weight the different costs of reloading/rematerializing a node
   (see bespill.h be_get_reload_costs_no_weight) */
static int                          remat_bonus      = 10;

static const lc_opt_table_entry_t options[] = {
	LC_OPT_ENT_BOOL   ("movespills", "try to move spills out of loops", &move_spills),
85
86
	LC_OPT_ENT_BOOL   ("respectloopdepth", "outermost loop cutting", &respectloopdepth),
	LC_OPT_ENT_BOOL   ("improveknownpreds", "known preds cutting", &improve_known_preds),
87
88
89
90
	LC_OPT_ENT_INT    ("rematbonus", "give bonus to rematerialisable nodes", &remat_bonus),
	LC_OPT_LAST
};

Daniel Grund's avatar
Daniel Grund committed
91
92
93
/**
 * Alloc a new workset on obstack @p ob with maximum size @p max
 */
94
95
static workset_t *new_workset(void)
{
96
	return OALLOCFZ(&obst, workset_t, vals, n_regs);
Daniel Grund's avatar
Daniel Grund committed
97
98
}

99
/**
100
 * Alloc a new instance on obstack and make it equal to @param workset
101
 */
102
103
static workset_t *workset_clone(workset_t *workset)
{
104
105
	workset_t *res = OALLOCF(&obst, workset_t, vals, n_regs);
	memcpy(res, workset, sizeof(*res) + n_regs * sizeof(res->vals[0]));
Daniel Grund's avatar
Daniel Grund committed
106
107
108
	return res;
}

109
/**
110
 * Copy workset @param src to @param tgt
111
 */
112
113
114
115
static void workset_copy(workset_t *dest, const workset_t *src)
{
	size_t size = sizeof(*src) + n_regs * sizeof(src->vals[0]);
	memcpy(dest, src, size);
116
117
118
119
120
121
122
}

/**
 * Overwrites the current content array of @param ws with the
 * @param count locations given at memory @param locs.
 * Set the length of @param ws to count.
 */
123
124
static void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs)
{
125
	workset->len = count;
Christoph Mallon's avatar
Christoph Mallon committed
126
	MEMCPY(&workset->vals[0], locs, count);
127
}
128

Daniel Grund's avatar
Daniel Grund committed
129
130
131
132
/**
 * Inserts the value @p val into the workset, iff it is not
 * already contained. The workset must not be full.
 */
Matthias Braun's avatar
Matthias Braun committed
133
static void workset_insert(workset_t *workset, ir_node *val, bool spilled)
134
{
Daniel Grund's avatar
Daniel Grund committed
135
	/* check for current regclass */
136
	assert(arch_irn_consider_in_reg_alloc(cls, val));
Daniel Grund's avatar
Daniel Grund committed
137
138

	/* check if val is already contained */
Matthias Braun's avatar
Matthias Braun committed
139
140
	for (unsigned i = 0, len = workset->len; i < len; ++i) {
		loc_t *loc = &workset->vals[i];
141
		if (loc->node == val) {
Matthias Braun's avatar
Matthias Braun committed
142
			if (spilled)
Matthias Braun's avatar
Matthias Braun committed
143
				loc->spilled = true;
Daniel Grund's avatar
Daniel Grund committed
144
			return;
145
146
		}
	}
Daniel Grund's avatar
Daniel Grund committed
147
148

	/* insert val */
149
	assert(workset->len < n_regs && "Workset already full!");
Matthias Braun's avatar
Matthias Braun committed
150
151
152
153
	loc_t *loc   = &workset->vals[workset->len];
	loc->node    = val;
	loc->spilled = spilled;
	loc->time    = TIME_UNDEFINED;
154
	workset->len++;
Daniel Grund's avatar
Daniel Grund committed
155
156
157
158
159
}

/**
 * Removes all entries from this workset
 */
160
161
162
static void workset_clear(workset_t *workset)
{
	workset->len = 0;
163
}
Daniel Grund's avatar
Daniel Grund committed
164
165
166
167

/**
 * Removes the value @p val from the workset if present.
 */
168
static void workset_remove(workset_t *workset, ir_node *val)
169
{
Matthias Braun's avatar
Matthias Braun committed
170
	for (unsigned i = 0, len = workset->len; i < len; ++i) {
171
172
		if (workset->vals[i].node == val) {
			workset->vals[i] = workset->vals[--workset->len];
Daniel Grund's avatar
Daniel Grund committed
173
174
			return;
		}
175
	}
Daniel Grund's avatar
Daniel Grund committed
176
177
}

178
static const loc_t *workset_contains(const workset_t *ws, const ir_node *val)
179
{
Matthias Braun's avatar
Matthias Braun committed
180
	for (unsigned i = 0, len = ws->len; i < len; ++i) {
181
		if (ws->vals[i].node == val)
Matthias Braun's avatar
Matthias Braun committed
182
			return &ws->vals[i];
183
184
	}

Matthias Braun's avatar
Matthias Braun committed
185
	return NULL;
Daniel Grund's avatar
Daniel Grund committed
186
187
}

188
189
static int loc_compare(const void *a, const void *b)
{
Manuel Mohr's avatar
Manuel Mohr committed
190
191
192
193
194
195
196
197
198
199
200
	const loc_t   *p  = ((const loc_t*) a);
	const loc_t   *q  = ((const loc_t*) b);
	const unsigned pt = p->time;
	const unsigned qt = q->time;

	if (pt < qt)
		return -1;
	if (pt > qt)
		return 1;

	return get_irn_node_nr(p->node) - get_irn_node_nr(q->node);
201
202
203
204
}

static void workset_sort(workset_t *workset)
{
205
	QSORT(workset->vals, workset->len, loc_compare);
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
}

static inline unsigned workset_get_time(const workset_t *workset, unsigned idx)
{
	return workset->vals[idx].time;
}

static inline void workset_set_time(workset_t *workset, unsigned idx,
                                    unsigned time)
{
	workset->vals[idx].time = time;
}

static inline unsigned workset_get_length(const workset_t *workset)
{
	return workset->len;
}

static inline void workset_set_length(workset_t *workset, unsigned len)
{
	workset->len = len;
}

static inline ir_node *workset_get_val(const workset_t *workset, unsigned idx)
{
	return workset->vals[idx].node;
}

234
235
236
237
238
239
/**
 * Iterates over all values in the working set.
 * @p ws The workset to iterate
 * @p v  A variable to put the current value in
 * @p i  An integer for internal use
 */
240
#define workset_foreach(ws, v, i) \
Christoph Mallon's avatar
Christoph Mallon committed
241
	for (unsigned i = 0; i < ws->len ? v = ws->vals[i].node, 1 : 0; ++i)
Daniel Grund's avatar
Daniel Grund committed
242

243
typedef struct block_info_t {
244
245
	workset_t *start_workset;
	workset_t *end_workset;
246
247
} block_info_t;

Matthias Braun's avatar
Matthias Braun committed
248
static block_info_t *new_block_info(ir_node *block)
249
{
Matthias Braun's avatar
Matthias Braun committed
250
251
252
	block_info_t *info = OALLOCZ(&obst, block_info_t);
	set_irn_link(block, info);
	return info;
253
254
}

255
256
static inline block_info_t *get_block_info(const ir_node *block)
{
257
	return (block_info_t*)get_irn_link(block);
258
259
}

260
/**
261
 * @return The distance to the next use or 0 if irn has dont_spill flag set
262
 */
Matthias Braun's avatar
Matthias Braun committed
263
264
static unsigned get_distance(ir_node *from, const ir_node *def,
                             bool skip_from_uses)
Sebastian Hack's avatar
Sebastian Hack committed
265
{
266
	assert(!arch_irn_is_ignore(def));
267

Matthias Braun's avatar
Matthias Braun committed
268
269
	be_next_use_t use  = be_get_next_use(uses, from, def, skip_from_uses);
	unsigned      time = use.time;
270
	if (USES_IS_INFINITE(time))
271
272
		return USES_INFINITY;

273
	/* We have to keep nonspillable nodes in the workingset */
274
	if (arch_get_irn_flags(skip_Proj_const(def)) & arch_irn_flag_dont_spill)
275
		return 0;
Sebastian Hack's avatar
Sebastian Hack committed
276

277
278
	/* give some bonus to rematerialisable nodes */
	if (remat_bonus > 0) {
Matthias Braun's avatar
Matthias Braun committed
279
		unsigned costs = be_get_reload_costs_no_weight(senv, def, use.before);
280
		assert(costs * remat_bonus < 1000);
Matthias Braun's avatar
Matthias Braun committed
281
		time += 1000 - (costs * remat_bonus);
282
	}
283

284
	return time;
Sebastian Hack's avatar
Sebastian Hack committed
285
}
286

Daniel Grund's avatar
Daniel Grund committed
287
/**
Sebastian Hack's avatar
Sebastian Hack committed
288
 * Performs the actions necessary to grant the request that:
Daniel Grund's avatar
Daniel Grund committed
289
290
291
292
293
294
295
 * - new_vals can be held in registers
 * - as few as possible other values are disposed
 * - the worst values get disposed
 *
 * @p is_usage indicates that the values in new_vals are used (not defined)
 * In this case reloads must be performed
 */
Matthias Braun's avatar
Matthias Braun committed
296
297
static void displace(workset_t *const new_vals, bool const is_usage,
                     ir_node *const instr)
298
{
299
300
	ir_node **to_insert = ALLOCAN(ir_node*, n_regs);
	bool     *spilled   = ALLOCAN(bool,     n_regs);
301
302

	/* 1. Identify the number of needed slots and the values to reload */
Matthias Braun's avatar
Matthias Braun committed
303
	unsigned  demand = 0;
Matthias Braun's avatar
Matthias Braun committed
304
	ir_node  *val    = NULL;
305
	workset_foreach(new_vals, val, iter) {
Matthias Braun's avatar
Matthias Braun committed
306
307
		bool reloaded = false;

Matthias Braun's avatar
Matthias Braun committed
308
		if (!workset_contains(ws, val)) {
309
			DB((dbg, DBG_DECIDE, "    insert %+F\n", val));
310
			if (is_usage) {
311
				DB((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, instr));
Matthias Braun's avatar
Matthias Braun committed
312
				be_add_reload(senv, val, instr);
Matthias Braun's avatar
Matthias Braun committed
313
				reloaded = true;
314
			}
315
		} else {
316
			DB((dbg, DBG_DECIDE, "    %+F already in workset\n", val));
317
			assert(is_usage);
318
319
320
			/* remove the value from the current workset so it is not accidently
			 * spilled */
			workset_remove(ws, val);
321
		}
Matthias Braun's avatar
Matthias Braun committed
322
323
324
		spilled[demand]   = reloaded;
		to_insert[demand] = val;
		++demand;
Daniel Grund's avatar
Daniel Grund committed
325
326
	}

327
	/* 2. Make room for at least 'demand' slots */
Matthias Braun's avatar
Matthias Braun committed
328
329
330
	unsigned len           = workset_get_length(ws);
	int      spills_needed = len + demand - n_regs;
	assert(spills_needed <= (int)len);
Daniel Grund's avatar
Daniel Grund committed
331
332

	/* Only make more free room if we do not have enough */
333
	if (spills_needed > 0) {
334
		DB((dbg, DBG_DECIDE, "    disposing %d values\n", spills_needed));
335

336
		/* calculate current next-use distance for live values */
Matthias Braun's avatar
Matthias Braun committed
337
		for (unsigned i = 0; i < len; ++i) {
338
			ir_node  *val  = workset_get_val(ws, i);
339
			unsigned  dist = get_distance(instr, val, !is_usage);
340
341
			workset_set_time(ws, i, dist);
		}
Daniel Grund's avatar
Daniel Grund committed
342
343
344
345

		/* sort entries by increasing nextuse-distance*/
		workset_sort(ws);

Matthias Braun's avatar
Matthias Braun committed
346
		for (int i = len - spills_needed; i < (int)len; ++i) {
347
			ir_node *val = ws->vals[i].node;
Christian Würdig's avatar
Christian Würdig committed
348

349
			DB((dbg, DBG_DECIDE, "    disposing node %+F (%u)\n", val,
Matthias Braun's avatar
Matthias Braun committed
350
351
			    workset_get_time(ws, i)));

yb9976's avatar
yb9976 committed
352
			if (move_spills && !USES_IS_INFINITE(workset_get_time(ws, i))
Matthias Braun's avatar
Matthias Braun committed
353
354
355
356
357
			    && !ws->vals[i].spilled) {
				ir_node *after_pos = sched_prev(instr);
				DB((dbg, DBG_DECIDE, "Spill %+F after node %+F\n", val,
					after_pos));
				be_add_spill(senv, val, after_pos);
358
			}
Daniel Grund's avatar
Daniel Grund committed
359
360
361
		}

		/* kill the last 'demand' entries in the array */
362
		workset_set_length(ws, len - spills_needed);
Daniel Grund's avatar
Daniel Grund committed
363
364
	}

365
	/* 3. Insert the new values into the workset */
Matthias Braun's avatar
Matthias Braun committed
366
	for (unsigned i = 0; i < demand; ++i) {
367
		ir_node *val = to_insert[i];
Matthias Braun's avatar
Matthias Braun committed
368
		workset_insert(ws, val, spilled[i]);
369
	}
Daniel Grund's avatar
Daniel Grund committed
370
371
}

Matthias Braun's avatar
Matthias Braun committed
372
typedef enum available_t {
373
374
375
376
	AVAILABLE_EVERYWHERE,
	AVAILABLE_NOWHERE,
	AVAILABLE_PARTLY,
	AVAILABLE_UNKNOWN
Matthias Braun's avatar
Matthias Braun committed
377
} available_t;
378

Matthias Braun's avatar
Matthias Braun committed
379
380
381
382
static available_t available_in_all_preds(workset_t* const* pred_worksets,
                                          size_t n_pred_worksets,
                                          const ir_node *value,
                                          bool is_local_phi)
383
384
385
386
{
	assert(n_pred_worksets > 0);

	/* value available in all preds? */
Matthias Braun's avatar
Matthias Braun committed
387
388
389
390
	bool avail_everywhere = true;
	bool avail_nowhere    = true;
	for (size_t i = 0; i < n_pred_worksets; ++i) {
		const ir_node *l_value;
391
392
393
394
395
396
397
		if (is_local_phi) {
			assert(is_Phi(value));
			l_value = get_irn_n(value, i);
		} else {
			l_value = value;
		}

Matthias Braun's avatar
Matthias Braun committed
398
399
400
401
		bool             found     = false;
		const workset_t *p_workset = pred_worksets[i];
		for (int p_i = 0, p_len = workset_get_length(p_workset);
		     p_i < p_len; ++p_i) {
402
403
404
405
406
			const loc_t *p_l = &p_workset->vals[p_i];
			if (p_l->node != l_value)
				continue;

			found = true;
Matthias Braun's avatar
Matthias Braun committed
407
			avail_nowhere = false;
408
409
410
			break;
		}

Matthias Braun's avatar
Matthias Braun committed
411
		avail_everywhere &= found;
412
413
414
415
416
417
418
419
420
421
422
423
	}

	if (avail_everywhere) {
		assert(!avail_nowhere);
		return AVAILABLE_EVERYWHERE;
	} else if (avail_nowhere) {
		return AVAILABLE_NOWHERE;
	} else {
		return AVAILABLE_PARTLY;
	}
}

Matthias Braun's avatar
Matthias Braun committed
424
425
/**
 * Decides whether a specific node should be in the start workset or not
426
 */
427
static loc_t to_take_or_not_to_take(ir_node* first, ir_node *node,
428
                                    ir_loop *loop, unsigned available)
429
{
Matthias Braun's avatar
Matthias Braun committed
430
	loc_t loc;
Matthias Braun's avatar
Matthias Braun committed
431
432
433
	loc.time    = USES_INFINITY;
	loc.node    = node;
	loc.spilled = false;
434
435

	/* We have to keep nonspillable nodes in the workingset */
436
	if (arch_get_irn_flags(skip_Proj_const(node)) & arch_irn_flag_dont_spill) {
437
		loc.time = 0;
438
		DB((dbg, DBG_START, "    %+F taken (dontspill node)\n", node, loc.time));
439
440
441
		return loc;
	}

Matthias Braun's avatar
Matthias Braun committed
442
	be_next_use_t next_use = be_get_next_use(uses, first, node, false);
443
	if (USES_IS_INFINITE(next_use.time)) {
444
		/* the nodes marked as live in shouldn't be dead, so it must be a phi */
445
		assert(is_Phi(node));
446
		loc.time = USES_INFINITY;
447
		DB((dbg, DBG_START, "    %+F not taken (dead)\n", node));
448
449
450
451
		return loc;
	}

	loc.time = next_use.time;
452
453
454
455
456
	if (improve_known_preds) {
		if (available == AVAILABLE_EVERYWHERE) {
			DB((dbg, DBG_START, "    %+F taken (%u, live in all preds)\n",
			    node, loc.time));
			return loc;
457
		} else if (available == AVAILABLE_NOWHERE) {
458
459
460
461
462
			DB((dbg, DBG_START, "    %+F not taken (%u, live in no pred)\n",
			    node, loc.time));
			loc.time = USES_INFINITY;
			return loc;
		}
463
464
	}

465
	if (!respectloopdepth || next_use.outermost_loop >= get_loop_depth(loop)) {
Matthias Braun's avatar
Matthias Braun committed
466
467
		DB((dbg, DBG_START, "    %+F taken (%u, loop %d)\n", node, loc.time,
		    next_use.outermost_loop));
468
	} else {
469
		loc.time = USES_PENDING;
Matthias Braun's avatar
Matthias Braun committed
470
471
		DB((dbg, DBG_START, "    %+F delayed (outerdepth %d < loopdepth %d)\n",
		    node, next_use.outermost_loop, get_loop_depth(loop)));
472
	}
473

474
	return loc;
475
}
476

477
478
479
480
481
/**
 * Computes the start-workset for a block with multiple predecessors. We assume
 * that at least 1 of the predeccesors is a back-edge which means we're at the
 * beginning of a loop. We try to reload as much values as possible now so they
 * don't get reloaded inside the loop.
482
 */
483
static void decide_start_workset(ir_node *const block)
484
{
485
	/* check predecessors */
Matthias Braun's avatar
Matthias Braun committed
486
487
488
489
490
	int         n_cfgpreds      = get_Block_n_cfgpreds(block);
	workset_t **pred_worksets   = ALLOCAN(workset_t*, n_cfgpreds);
	bool        all_preds_known = true;
	for (int i = 0; i < n_cfgpreds; ++i) {
		ir_node      *pred_block = get_Block_cfgpred_block(block, i);
491
492
493
		block_info_t *pred_info  = get_block_info(pred_block);

		if (pred_info == NULL) {
Matthias Braun's avatar
Matthias Braun committed
494
			pred_worksets[i] = NULL;
495
			all_preds_known   = false;
496
		} else {
Matthias Braun's avatar
Matthias Braun committed
497
			pred_worksets[i] = pred_info->end_workset;
498
499
		}
	}
500

501
	/* Collect all values living at start of block */
Matthias Braun's avatar
Matthias Braun committed
502
503
	loc_t *starters = NEW_ARR_F(loc_t, 0);
	loc_t *delayed  = NEW_ARR_F(loc_t, 0);
504

505
	DB((dbg, DBG_START, "Living at start of %+F:\n", block));
Matthias Braun's avatar
Matthias Braun committed
506
	ir_node *first = sched_first(block);
507

508
	/* check all Phis first */
Matthias Braun's avatar
Matthias Braun committed
509
	ir_loop *loop = get_irn_loop(block);
510
	sched_foreach(block, node) {
Matthias Braun's avatar
Matthias Braun committed
511
		if (!is_Phi(node))
512
			break;
513
		if (!arch_irn_consider_in_reg_alloc(cls, node))
514
			continue;
515

Matthias Braun's avatar
Matthias Braun committed
516
		available_t available = AVAILABLE_UNKNOWN;
517
		if (all_preds_known) {
Matthias Braun's avatar
Matthias Braun committed
518
519
			available = available_in_all_preds(pred_worksets, n_cfgpreds,
			                                   node, true);
520
521
		}

Matthias Braun's avatar
Matthias Braun committed
522
523
		loc_t loc = to_take_or_not_to_take(first, node, loop, available);
		if (!USES_IS_INFINITE(loc.time)) {
Matthias Braun's avatar
Matthias Braun committed
524
			if (USES_IS_PENDING(loc.time))
525
				ARR_APP1(loc_t, delayed, loc);
526
			else
527
				ARR_APP1(loc_t, starters, loc);
528
529
		} else {
			be_spill_phi(senv, node);
530
		}
531
	}
532

533
	/* check all Live-Ins */
534
	be_lv_foreach_cls(lv, block, be_lv_state_in, cls, node) {
Matthias Braun's avatar
Matthias Braun committed
535
		available_t available = AVAILABLE_UNKNOWN;
536
		if (all_preds_known) {
Matthias Braun's avatar
Matthias Braun committed
537
538
			available = available_in_all_preds(pred_worksets, n_cfgpreds,
			                                   node, false);
539
540
		}

Matthias Braun's avatar
Matthias Braun committed
541
542
		loc_t loc = to_take_or_not_to_take(first, node, loop, available);
		if (!USES_IS_INFINITE(loc.time)) {
Matthias Braun's avatar
Matthias Braun committed
543
			if (USES_IS_PENDING(loc.time))
544
545
546
				ARR_APP1(loc_t, delayed, loc);
			else
				ARR_APP1(loc_t, starters, loc);
547
		}
548
	}
549

Matthias Braun's avatar
Matthias Braun committed
550
	unsigned pressure = be_get_loop_pressure(loop_ana, cls, loop);
551
	assert(ARR_LEN(delayed) <= pressure);
Matthias Braun's avatar
Matthias Braun committed
552
553
554
	int free_slots          = n_regs - ARR_LEN(starters);
	int free_pressure_slots = n_regs - (pressure - ARR_LEN(delayed));
	free_slots              = MIN(free_slots, free_pressure_slots);
555

556
557
558
	/* so far we only put nodes into the starters list that are used inside
	 * the loop. If register pressure in the loop is low then we can take some
	 * values and let them live through the loop */
559
560
	DB((dbg, DBG_START, "Loop pressure %d, taking %d delayed vals\n",
	    pressure, free_slots));
Matthias Braun's avatar
Matthias Braun committed
561
	if (free_slots > 0) {
562
		QSORT_ARR(delayed, loc_compare);
563

Matthias Braun's avatar
Matthias Braun committed
564
		for (size_t i = 0; i < ARR_LEN(delayed) && free_slots > 0; ++i) {
Matthias Braun's avatar
Matthias Braun committed
565
			loc_t *loc = & delayed[i];
Matthias Braun's avatar
again    
Matthias Braun committed
566
567
568
			if (!is_Phi(loc->node)) {
				/* don't use values which are dead in a known predecessors
				 * to not induce unnecessary reloads */
Matthias Braun's avatar
Matthias Braun committed
569
				for (int p = 0; p < n_cfgpreds; ++p) {
Matthias Braun's avatar
again    
Matthias Braun committed
570
571
572
573
574
575
576
577
578
579
580
581
					ir_node      *pred_block = get_Block_cfgpred_block(block, p);
					block_info_t *pred_info  = get_block_info(pred_block);

					if (pred_info == NULL)
						continue;

					if (!workset_contains(pred_info->end_workset, loc->node)) {
						DB((dbg, DBG_START,
							"    delayed %+F not live at pred %+F\n", loc->node,
							pred_block));
						goto skip_delayed;
					}
Matthias Braun's avatar
Matthias Braun committed
582
583
584
585
586
587
				}
			}

			DB((dbg, DBG_START, "    delayed %+F taken\n", loc->node));
			ARR_APP1(loc_t, starters, *loc);
			loc->node = NULL;
588
			--free_slots;
Matthias Braun's avatar
again    
Matthias Braun committed
589
590
		skip_delayed:
			;
591
		}
592
	}
593
594
595

	/* spill phis (the actual phis not just their values) that are in this block
	 * but not in the start workset */
Matthias Braun's avatar
Matthias Braun committed
596
	for (size_t i = 0, len = ARR_LEN(delayed); i < len; ++i) {
597
		ir_node *node = delayed[i].node;
598
		if (node == NULL || !is_Phi(node) || get_nodes_block(node) != block)
599
600
			continue;

601
		DB((dbg, DBG_START, "    spilling delayed phi %+F\n", node));
602
603
		be_spill_phi(senv, node);
	}
604
605
606
	DEL_ARR_F(delayed);

	/* Sort start values by first use */
607
	QSORT_ARR(starters, loc_compare);
608

609
	/* Copy the best ones from starters to start workset */
Matthias Braun's avatar
Matthias Braun committed
610
	unsigned ws_count = MIN((unsigned) ARR_LEN(starters), n_regs);
611
612
	workset_clear(ws);
	workset_bulk_fill(ws, ws_count, starters);
613

614
615
	/* spill phis (the actual phis not just their values) that are in this block
	 * but not in the start workset */
Matthias Braun's avatar
Matthias Braun committed
616
	for (size_t i = ws_count, len = ARR_LEN(starters); i < len; ++i) {
617
		ir_node *node = starters[i].node;
Matthias Braun's avatar
Matthias Braun committed
618
		if (!is_Phi(node) || get_nodes_block(node) != block)
619
			continue;
620

621
		DB((dbg, DBG_START, "    spilling phi %+F\n", node));
622
		be_spill_phi(senv, node);
623
624
	}
	DEL_ARR_F(starters);
625

Matthias Braun's avatar
Matthias Braun committed
626
	/* determine spill status of the values: If there's 1 pred block (which
Matthias Braun's avatar
Matthias Braun committed
627
628
	 * is no backedge) where the value is spilled then we must set it to
	 * spilled here. */
Matthias Braun's avatar
Matthias Braun committed
629
630
631
	for (unsigned i = 0; i < ws_count; ++i) {
		loc_t   *loc   = &ws->vals[i];
		ir_node *value = loc->node;
632

Matthias Braun's avatar
Matthias Braun committed
633
		/* phis from this block aren't spilled */
634
		if (get_nodes_block(value) == block) {
635
			assert(is_Phi(value));
Matthias Braun's avatar
Matthias Braun committed
636
			loc->spilled = false;
637
638
			continue;
		}
639

640
		/* determine if value was spilled on any predecessor */
Matthias Braun's avatar
Matthias Braun committed
641
642
		bool spilled = false;
		for (int n = 0; n < n_cfgpreds; ++n) {
643
			workset_t *pred_workset = pred_worksets[n];
644
645
646
			if (pred_workset == NULL)
				continue;

Matthias Braun's avatar
Matthias Braun committed
647
648
			for (unsigned p = 0, p_len = workset_get_length(pred_workset);
			     p < p_len; ++p) {
649
				loc_t *l = &pred_workset->vals[p];
Matthias Braun's avatar
Matthias Braun committed
650
651
652
				if (l->node != value)
					continue;

653
654
655
656
657
658
659
				if (l->spilled) {
					spilled = true;
				}
				break;
			}
		}

Matthias Braun's avatar
Matthias Braun committed
660
661
662
663
		loc->spilled = spilled;
	}
}

Daniel Grund's avatar
Daniel Grund committed
664
/**
665
 * For the given block @p block, decide for each values
Daniel Grund's avatar
Daniel Grund committed
666
667
668
 * whether it is used from a register or is reloaded
 * before the use.
 */
669
static void process_block(ir_node *block)
670
671
{
	/* no need to process a block twice */
672
	assert(get_block_info(block) == NULL);
673

674
	/* construct start workset */
Matthias Braun's avatar
Matthias Braun committed
675
	int arity = get_Block_n_cfgpreds(block);
676
	if (arity == 0) {
677
		/* no predecessor -> empty set */
678
		workset_clear(ws);
679
	} else if (arity == 1) {
680
		/* one predecessor, copy its end workset */
681
682
683
684
685
686
		ir_node      *pred_block = get_Block_cfgpred_block(block, 0);
		block_info_t *pred_info  = get_block_info(pred_block);

		assert(pred_info != NULL);
		workset_copy(ws, pred_info->end_workset);
	} else {
687
		/* multiple predecessors, do more advanced magic :) */
688
		decide_start_workset(block);
689
	}
690

691
692
	DB((dbg, DBG_DECIDE, "\n"));
	DB((dbg, DBG_DECIDE, "Decide for %+F\n", block));
Daniel Grund's avatar
Daniel Grund committed
693

694
	DB((dbg, DBG_WSETS, "Start workset for %+F:\n", block));
695
#ifdef DEBUG_libfirm
Matthias Braun's avatar
Matthias Braun committed
696
	ir_node *irn = NULL;
Matthias Braun's avatar
Matthias Braun committed
697
698
	workset_foreach(ws, irn, iter) {
		DB((dbg, DBG_WSETS, "  %+F (%u)\n", irn, workset_get_time(ws, iter)));
699
	}
700
#endif
701

Matthias Braun's avatar
Matthias Braun committed
702
	block_info_t *block_info = new_block_info(block);
703
	block_info->start_workset = workset_clone(ws);
Daniel Grund's avatar
Daniel Grund committed
704
705

	/* process the block from start to end */
706
	DB((dbg, DBG_WSETS, "Processing...\n"));
Matthias Braun's avatar
Matthias Braun committed
707
	workset_t *new_vals = temp_workset;
708

709
	sched_foreach(block, irn) {
710
		assert(workset_get_length(ws) <= n_regs);
Daniel Grund's avatar
Daniel Grund committed
711

712
		/* Phis are no real instr (see insert_starters()) */
Matthias Braun's avatar
Matthias Braun committed
713
		if (is_Phi(irn))
Daniel Grund's avatar
Daniel Grund committed
714
			continue;
715
		DB((dbg, DBG_DECIDE, "  ...%+F\n", irn));
Daniel Grund's avatar
Daniel Grund committed
716
717
718

		/* allocate all values _used_ by this instruction */
		workset_clear(new_vals);
719
		be_foreach_use(irn, cls, in_req_, in, in_req,
Matthias Braun's avatar
Matthias Braun committed
720
721
			/* (note that "spilled" is irrelevant here) */
			workset_insert(new_vals, in, false);
722
		);
Matthias Braun's avatar
Matthias Braun committed
723
		displace(new_vals, true, irn);
Daniel Grund's avatar
Daniel Grund committed
724
725
726

		/* allocate all values _defined_ by this instruction */
		workset_clear(new_vals);
727
728
		be_foreach_definition(irn, cls, value, req,
			assert(req->width == 1);
729
730
			workset_insert(new_vals, value, false);
		);
Matthias Braun's avatar
Matthias Braun committed
731
		displace(new_vals, false, irn);
Daniel Grund's avatar
Daniel Grund committed
732
733
734
	}

	/* Remember end-workset for this block */
735
	block_info->end_workset = workset_clone(ws);
736
	DB((dbg, DBG_WSETS, "End workset for %+F:\n", block));
737
#ifdef DEBUG_libfirm
Matthias Braun's avatar
Matthias Braun committed
738
739
	workset_foreach(ws, irn, iter) {
		DB((dbg, DBG_WSETS, "  %+F (%u)\n", irn, workset_get_time(ws, iter)));
740
	}
741
#endif
Daniel Grund's avatar
Daniel Grund committed
742
743
744
}

/**
Michael Beck's avatar
Michael Beck committed
745
 * 'decide' is block-local and makes assumptions
Daniel Grund's avatar
Daniel Grund committed
746
747
748
 * about the set of live-ins. Thus we must adapt the
 * live-outs to the live-ins at each block-border.
 */
749
750
static void fix_block_borders(ir_node *block, void *data)
{
751
	(void) data;
752
753
	DB((dbg, DBG_FIX, "\n"));
	DB((dbg, DBG_FIX, "Fixing %+F\n", block));
Daniel Grund's avatar
Daniel Grund committed
754
755

	/* process all pred blocks */
Matthias Braun's avatar
Matthias Braun committed
756
	workset_t *start_workset = get_block_info(block)->start_workset;
Matthias Braun's avatar
Matthias Braun committed
757
758
	for (int i = 0, n_cfgpreds = get_Block_n_cfgpreds(block); i < n_cfgpreds;
	     ++i) {
759
760
		ir_node   *pred = get_Block_cfgpred_block(block, i);
		workset_t *pred_end_workset = get_block_info(pred)->end_workset;
Daniel Grund's avatar
Daniel Grund committed
761

762
		DB((dbg, DBG_FIX, "  Pred %+F\n", pred));
Daniel Grund's avatar
Daniel Grund committed
763

764
		/* spill all values not used anymore */
Matthias Braun's avatar
Matthias Braun committed
765
		ir_node *node = NULL;
766
		workset_foreach(pred_end_workset, node, iter) {
Matthias Braun's avatar
Matthias Braun committed
767
			ir_node *n2    = NULL;
Matthias Braun's avatar
Matthias Braun committed
768
			bool     found = false;
769
			workset_foreach(start_workset, n2, iter2) {
770
				if (n2 == node) {
Matthias Braun's avatar
Matthias Braun committed
771
					found = true;
772
773
					break;
				}
Matthias Braun's avatar
Matthias Braun committed
774
				/* note that we do not look at phi inputs, because the values
775
776
777
778
				 * will be either live-end and need no spill or
				 * they have other users in which must be somewhere else in the
				 * workset */
			}
Daniel Grund's avatar
Daniel Grund committed
779

Matthias Braun's avatar
Matthias Braun committed
780
781
782
			if (found)
				continue;

783
			if (move_spills && be_is_live_in(lv, block, node)
Matthias Braun's avatar
Matthias Braun committed
784
785
					&& !pred_end_workset->vals[iter].spilled) {
				ir_node *insert_point;
Matthias Braun's avatar
Matthias Braun committed
786
				if (n_cfgpreds > 1) {
Matthias Braun's avatar
Matthias Braun committed
787
					insert_point = be_get_end_of_block_insertion_point(pred);
Matthias Braun's avatar
Matthias Braun committed
788
					insert_point = sched_prev(insert_point);
Matthias Braun's avatar
Matthias Braun committed
789
				} else {
Matthias Braun's avatar
Matthias Braun committed
790
					insert_point = block;
Matthias Braun's avatar
Matthias Braun committed
791
				}
Matthias Braun's avatar
Matthias Braun committed
792
				DB((dbg, DBG_SPILL, "Spill %+F after %+F\n", node,
793
				     insert_point));
794
				be_add_spill(senv, node, insert_point);
795
			}
796
		}
797

Matthias Braun's avatar
Matthias Braun committed
798
		/* reload missing values in predecessors, add missing spills */
799
		workset_foreach(start_workset, node, iter) {
Matthias Braun's avatar
Matthias Braun committed
800
			const loc_t *l = &start_workset->vals[iter];
Matthias Braun's avatar
Matthias Braun committed
801

802
803
			/* if node is a phi of the current block we reload
			 * the corresponding argument, else node itself */
804
			if (is_Phi(node) && get_nodes_block(node) == block) {
805
				node = get_irn_n(node, i);
Matthias Braun's avatar
Matthias Braun committed
806
				assert(!l->spilled);
Daniel Grund's avatar
Daniel Grund committed
807

808
				/* we might have unknowns as argument for the phi */
809
				if (!arch_irn_consider_in_reg_alloc(cls, node))
810
					continue;
811
			}
Daniel Grund's avatar
Daniel Grund committed
812

813
			/* check if node is in a register at end of pred */
Matthias Braun's avatar
Matthias Braun committed
814
			const loc_t *pred_loc =