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

/**
 * @file
 * @brief       Beladys spillalgorithm version 2.
23
 * @author      Sebastian Hack, Matthias Braun, Daniel Grund
Sebastian Hack's avatar
Sebastian Hack committed
24
 * @date        01.08.2007
25
 * @version     $Id$
Sebastian Hack's avatar
Sebastian Hack committed
26
27
28
29
30
31
32
33
 *
 * The main differences to the original Belady are:
 * - The workset is empty at the start of a block
 *   There is no attempt to fill it with variables which
 *   are not used in the block.
 * - There is a global pass which tries to use the remaining
 *   capacity of the blocks to let global variables live through
 *   them.
34
35
36
37
38
39
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <math.h>
Sebastian Hack's avatar
Sebastian Hack committed
40
#include <limits.h>
41
42
43

#include "obst.h"
#include "irnodeset.h"
Sebastian Hack's avatar
Sebastian Hack committed
44
#include "irbitset.h"
45
46
47
48
49
50
51
#include "irprintf_t.h"
#include "irgraph.h"
#include "irnode.h"
#include "irmode.h"
#include "irgwalk.h"
#include "irloop.h"
#include "iredges_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
52
#include "irphase_t.h"
53
54
55
#include "ircons_t.h"
#include "irprintf.h"
#include "execfreq.h"
56
#include "dfs_t.h"
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include "xmalloc.h"

#include "beutil.h"
#include "bearch_t.h"
#include "bespillbelady.h"
#include "besched_t.h"
#include "beirgmod.h"
#include "belive_t.h"
#include "benode_t.h"
#include "bechordal_t.h"
#include "bespilloptions.h"
#include "beloopana.h"
#include "beirg_t.h"
#include "bemodule.h"

Sebastian Hack's avatar
Sebastian Hack committed
72
73
74
75
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#include <libcore/lc_timing.h>

76
77
78
79
80
81
82
83
84
85
#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
#define DBG_WORKSET 128
#define DBG_GLOBAL  256

Sebastian Hack's avatar
Sebastian Hack committed
86
87
88
89
90
91
92
93
94
95
96
#define ALREADY_SPILLED_FACTOR 2

#define DEAD       UINT_MAX
#define LIVE_END   (DEAD-1)
#define REMAT_DIST (DEAD-2)

static int already_spilled_factor = 2;
static int remat_live_range_ext   = 1;
static int global_pass_enabled    = 1;

static const lc_opt_table_entry_t options[] = {
Sebastian Hack's avatar
Sebastian Hack committed
97
	LC_OPT_ENT_INT           ("asf",    "already spilled factor",                             &already_spilled_factor),
Sebastian Hack's avatar
Sebastian Hack committed
98
	LC_OPT_ENT_BOOL          ("remat",  "rematerializable ops get infinite long live ranges", &remat_live_range_ext),
Sebastian Hack's avatar
Sebastian Hack committed
99
	LC_OPT_ENT_BOOL          ("global", "enable/disable the global pass",                     &global_pass_enabled),
Sebastian Hack's avatar
Sebastian Hack committed
100
101
	LC_OPT_LAST
};
Sebastian Hack's avatar
Sebastian Hack committed
102

Sebastian Hack's avatar
Sebastian Hack committed
103
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
104
105
106
107
108
109

/**
 * An association between a node and a point in time.
 */
typedef struct _loc_t {
  ir_node *irn;        /**< A node. */
110
111
112
113
114
  unsigned time;       /**< A use time.
						 In the global pass this is used
						 as the version number and not as a time.
						 Only to save space...
						*/
115
116
117
118
119
120
121
122
123
} loc_t;

typedef struct _workset_t {
	int len;			/**< current length */
	loc_t vals[0];		/**< inlined array of the values/distances in this working set */
} workset_t;

typedef struct _belady_env_t {
	struct obstack ob;
Sebastian Hack's avatar
Sebastian Hack committed
124
	ir_graph *irg;
125
	const dfs_t *dfs;
126
127
128
129
130
131
132
133
134
135
	const arch_env_t *arch;
	const arch_register_class_t *cls;
	be_lv_t *lv;
	ir_exec_freq *ef;

	ir_node **blocks;   /**< Array of all blocks. */
	int n_blocks;       /**< Number of blocks in the graph. */
	int n_regs;			/**< number of regs in this reg-class */
	workset_t *ws;		/**< the main workset used while processing a block. ob-allocated */
	ir_node *instr;		/**< current instruction */
Sebastian Hack's avatar
Sebastian Hack committed
136
	int instr_nr;     	/**< current instruction number (relative to block start) */
137
138

	spill_env_t *senv;	/**< see bespill.h */
Sebastian Hack's avatar
Sebastian Hack committed
139
	bitset_t *spilled;  /**< bitset to keep all the irns which have already been spilled. */
140
141
142
143
144
145
146
} belady_env_t;


static int loc_compare(const void *a, const void *b)
{
	const loc_t *p = a;
	const loc_t *q = b;
Sebastian Hack's avatar
Sebastian Hack committed
147
	return (p->time > q->time) - (p->time < q->time);
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
}

static INLINE void workset_print(const workset_t *w)
{
	int i;

	for(i = 0; i < w->len; ++i) {
		ir_fprintf(stderr, "%+F %d\n", w->vals[i].irn, w->vals[i].time);
	}
}

/**
 * Alloc a new workset on obstack @p ob with maximum size @p max
 */
static INLINE workset_t *new_workset(belady_env_t *env, struct obstack *ob) {
	workset_t *res;
	size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
	res = obstack_alloc(ob, size);
	memset(res, 0, size);
	return res;
}

/**
 * Alloc a new instance on obstack and make it equal to @param ws
 */
static INLINE workset_t *workset_clone(belady_env_t *env, struct obstack *ob, workset_t *ws) {
	workset_t *res;
	size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
	res = obstack_alloc(ob, size);
	memcpy(res, ws, size);
	return res;
}

/**
 * Do NOT alloc anything. Make @param tgt equal to @param src.
 * returns @param tgt for convenience
 */
static INLINE workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset_t *src) {
	size_t size = sizeof(*src) + (env->n_regs)*sizeof(src->vals[0]);
	memcpy(tgt, src, size);
	return tgt;
}

/**
 * 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.
 */
static INLINE void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs) {
	workset->len = count;
	memcpy(&(workset->vals[0]), locs, count * sizeof(locs[0]));
}

/**
 * Inserts the value @p val into the workset, iff it is not
 * already contained. The workset must not be full.
 */
static INLINE void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val) {
	int i;
	/* check for current regclass */
	if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, val)) {
Sebastian Hack's avatar
Sebastian Hack committed
209
		// DBG((dbg, DBG_WORKSET, "Skipped %+F\n", val));
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
		return;
	}

	/* check if val is already contained */
	for(i=0; i<ws->len; ++i)
		if (ws->vals[i].irn == val)
			return;

	/* insert val */
	assert(ws->len < env->n_regs && "Workset already full!");
	ws->vals[ws->len++].irn = val;
}

/**
 * Removes all entries from this workset
 */
static INLINE void workset_clear(workset_t *ws) {
	ws->len = 0;
}

/**
 * Removes the value @p val from the workset if present.
 */
static INLINE void workset_remove(workset_t *ws, ir_node *val) {
	int i;
	for(i=0; i<ws->len; ++i) {
		if (ws->vals[i].irn == val) {
			ws->vals[i] = ws->vals[--ws->len];
			return;
		}
	}
}

static INLINE int workset_get_index(const workset_t *ws, const ir_node *val) {
	int i;
	for(i=0; i<ws->len; ++i) {
		if (ws->vals[i].irn == val)
			return i;
	}

	return -1;
}

/**
 * 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
 */
#define workset_foreach(ws, v, i)	for(i=0; \
										v=(i < ws->len) ? ws->vals[i].irn : NULL, i < ws->len; \
										++i)

#define workset_set_time(ws, i, t) (ws)->vals[i].time=t
#define workset_get_time(ws, i) (ws)->vals[i].time
#define workset_set_length(ws, length) (ws)->len = length
#define workset_get_length(ws) ((ws)->len)
#define workset_get_val(ws, i) ((ws)->vals[i].irn)
#define workset_sort(ws) qsort((ws)->vals, (ws)->len, sizeof((ws)->vals[0]), loc_compare);
#define workset_contains(ws, n) (workset_get_index(ws, n) >= 0)

Sebastian Hack's avatar
Sebastian Hack committed
271
272
typedef struct _bring_in_t bring_in_t;

273
274
typedef struct _block_info_t {
	belady_env_t *bel;
Sebastian Hack's avatar
Sebastian Hack committed
275
	ir_node *bl;
276
	int id;
277
278
279
	ir_phase next_uses;
	workset_t *ws_end;       /**< The end set after the local belady pass. */
	double exec_freq;        /**< The execution frequency of this block. */
280

281
	double reload_cost;      /**< Cost of a reload in this block. */
Sebastian Hack's avatar
Sebastian Hack committed
282
283
284
285
	ir_node *first_non_in;   /**< First node in block which is not a phi.  */
	ir_node *last_ins;       /**< The instruction before which end of
							   block reloads will be inserted. */

286
287
288
289
	int pressure;            /**< The amount of registers which remain free
				               in this block. This capacity can be used to let
				               global variables, transported into other blocks,
				               live through this block. */
290

291
292
293
294
	int front_pressure;      /**< The pressure right before the first
							   real (non-phi) node. At the beginning
							   of the global pass, this is 0. */
	struct list_head br_head; /**< List head for all bring_in variables. */
Sebastian Hack's avatar
Sebastian Hack committed
295

296
297
} block_info_t;

298
299
300
static INLINE void *new_block_info(belady_env_t *bel, int id)
{
	ir_node      *bl  = bel->blocks[id];
301
302
	block_info_t *res = obstack_alloc(&bel->ob, sizeof(*res));
	memset(res, 0, sizeof(res[0]));
Sebastian Hack's avatar
Sebastian Hack committed
303
304
	res->first_non_in = NULL;
	res->last_ins = NULL;
305
306
	res->bel = bel;
	res->bl  = bl;
307
	res->id  = id;
308
	res->exec_freq    = get_block_execfreq(bel->ef, bl);
Sebastian Hack's avatar
Sebastian Hack committed
309
	res->reload_cost  = bel->arch->isa->reload_cost * res->exec_freq;
310
	INIT_LIST_HEAD(&res->br_head);
311
312
313
314
315
316
317
	set_irn_link(bl, res);
	return res;
}

#define get_block_info(block)        ((block_info_t *)get_irn_link(block))
#define set_block_info(block, info)  set_irn_link(block, info)

Sebastian Hack's avatar
Sebastian Hack committed
318
319
320
321
322
323
324
325
static INLINE ir_node *block_info_get_last_ins(block_info_t *bi)
{
	if (!bi->last_ins)
		bi->last_ins = be_get_end_of_block_insertion_point(bi->bl);

	return bi->last_ins;
}

Sebastian Hack's avatar
Sebastian Hack committed
326
typedef struct _next_use_t {
Sebastian Hack's avatar
Sebastian Hack committed
327
328
329
330
	unsigned is_first_use : 1; /**< Indicate that this use is the first
								 in the block. Needed to identify
								 transport in values for the global
								 pass. */
Sebastian Hack's avatar
Sebastian Hack committed
331
	sched_timestep_t step;     /**< The time step of the use. */
Sebastian Hack's avatar
Sebastian Hack committed
332
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
333
334
	struct _next_use_t *next;  /**< The next use int this block
								 or NULL. */
Sebastian Hack's avatar
Sebastian Hack committed
335
336
337
} next_use_t;

static void *next_use_init(ir_phase *phase, ir_node *irn, void *old)
338
{
Sebastian Hack's avatar
Sebastian Hack committed
339
340
341
342
343
344
345
346
347
	(void) phase;
	(void) irn;
	(void) old;
	return NULL;
}

static void build_next_uses(block_info_t *bi)
{
	ir_node *irn;
348

Sebastian Hack's avatar
Sebastian Hack committed
349
350
	sched_renumber(bi->bl);

Sebastian Hack's avatar
Sebastian Hack committed
351
352
	phase_init(&bi->next_uses, "next uses", bi->bel->irg, PHASE_DEFAULT_GROWTH, next_use_init, NULL);
	sched_foreach_reverse(bi->bl, irn) {
Sebastian Hack's avatar
Sebastian Hack committed
353
		int i;
354

Sebastian Hack's avatar
Sebastian Hack committed
355
356
		if (is_Phi(irn))
			break;
357

Sebastian Hack's avatar
Sebastian Hack committed
358
359
360
361
		for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
			ir_node *op = get_irn_n(irn, i);
			next_use_t *curr = phase_get_irn_data(&bi->next_uses, op);
			next_use_t *use  = phase_alloc(&bi->next_uses, sizeof(use[0]));
362

Sebastian Hack's avatar
Sebastian Hack committed
363
			use->is_first_use = 1;
Sebastian Hack's avatar
Sebastian Hack committed
364
			use->step         = sched_get_time_step(irn);
Sebastian Hack's avatar
Sebastian Hack committed
365
			use->next         = curr;
Sebastian Hack's avatar
Sebastian Hack committed
366
			use->irn          = irn;
Sebastian Hack's avatar
Sebastian Hack committed
367

Sebastian Hack's avatar
Sebastian Hack committed
368
			if (curr) {
Sebastian Hack's avatar
Sebastian Hack committed
369
				curr->is_first_use = 0;
Sebastian Hack's avatar
Sebastian Hack committed
370
371
				assert(curr->step >= use->step);
			}
Sebastian Hack's avatar
Sebastian Hack committed
372

Sebastian Hack's avatar
Sebastian Hack committed
373
374
375
			phase_set_irn_data(&bi->next_uses, op, use);
		}
	}
376
377
}

Sebastian Hack's avatar
Sebastian Hack committed
378
379
380
381
382
383
384
385
386
387
#define get_current_use(bi, irn) 	 phase_get_irn_data(&(bi)->next_uses, (irn))

static INLINE void advance_current_use(block_info_t *bi, const ir_node *irn)
{
	next_use_t *use = get_current_use(bi, irn);

	assert(use);
	phase_set_irn_data(&bi->next_uses, irn, use->next);
}

Sebastian Hack's avatar
Sebastian Hack committed
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
static __attribute__((unused)) int block_freq_gt(const void *a, const void *b)
{
	const ir_node * const *p = a;
	const ir_node * const *q = b;
	block_info_t *pi = get_block_info(*p);
	block_info_t *qi = get_block_info(*q);
	double diff = qi->exec_freq - pi->exec_freq;
	return (diff > 0) - (diff < 0);
}

static int block_freq_dfs_gt(const void *a, const void *b)
{
	const ir_node * const *p = a;
	const ir_node * const *q = b;
	block_info_t *pi = get_block_info(*p);
	block_info_t *qi = get_block_info(*q);
	double diff;

	if ((pi->exec_freq > 1.0 && qi->exec_freq > 1.0)
			|| (pi->exec_freq <= 1.0 && qi->exec_freq <= 1.0)) {

		const dfs_t *dfs = pi->bel->dfs;
		int pp = dfs_get_post_num(dfs, pi->bl);
		int pq = dfs_get_post_num(dfs, qi->bl);
		return pq - pp;
	}

	diff = qi->exec_freq - pi->exec_freq;
	return (diff > 0) - (diff < 0);
}

419
420
421
422
423
424
425
426
427
428
429
/*
   ____       _               ___
  | __ ) _ __(_)_ __   __ _  |_ _|_ __
  |  _ \| '__| | '_ \ / _` |  | || '_ \
  | |_) | |  | | | | | (_| |  | || | | |
  |____/|_|  |_|_| |_|\__, | |___|_| |_|
                      |___/

  Data structures to represent bring in variables.
*/

Sebastian Hack's avatar
Sebastian Hack committed
430
431
struct _bring_in_t {
	ir_node *irn;              /**< The node to bring in. */
432
	block_info_t *bi;          /**< The block to which bring in should happen. */
Sebastian Hack's avatar
Sebastian Hack committed
433
434
435
436
437
	int pressure_so_far;       /**< The maximal pressure till the first use of irn in bl. */
	ir_node *first_use;        /**< The first user of irn in bl. */
	sched_timestep_t use_step; /**< Schedule sttep of the first use. */

	int is_remat : 1;          /**< Is rematerializable. */
438
	int sect_pressure;         /**< Offset to maximum pressure in block. */
Sebastian Hack's avatar
Sebastian Hack committed
439
440
441
	struct list_head list;
};

442
static INLINE bring_in_t *new_bring_in(block_info_t *bi, ir_node *irn, const next_use_t *use)
Sebastian Hack's avatar
Sebastian Hack committed
443
{
444
445
446
447
448
449
450
451
452
453
454
455
456
	bring_in_t *br    = obstack_alloc(&bi->bel->ob, sizeof(br[0]));

	br->irn             = irn;
	br->bi              = bi;
	br->first_use       = use->irn;
	br->use_step        = use->step;
	br->is_remat        = be_is_rematerializable(bi->bel->senv, irn, use->irn);
	br->pressure_so_far = bi->pressure;
	br->sect_pressure   = bi->front_pressure;

	INIT_LIST_HEAD(&br->list);
	list_add_tail(&br->list, &bi->br_head);
	return br;
Sebastian Hack's avatar
Sebastian Hack committed
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
}

static int bring_in_cmp(const void *a, const void *b)
{
	const bring_in_t *p = *(const bring_in_t * const *) a;
	const bring_in_t *q = *(const bring_in_t * const *) b;
	double fp, fq;

	/* if one of both is a remat node, it will be done after the other. */
	if (p->is_remat != q->is_remat)
		return p->is_remat - q->is_remat;

	/* in the same block, the one further in the front has to be processed first!
	 * Otherwise the front_pressure 'trick' is not exact. */
	if (p->bi == q->bi)
		return p->use_step - q->use_step;

	fp = p->bi->exec_freq;
	fq = q->bi->exec_freq;

	/* if both have the same frequency, inspect the frequency of the definition */
	if (fp == fq) {
		double fdp = get_block_info(get_nodes_block(p->irn))->exec_freq;
		double fdq = get_block_info(get_nodes_block(q->irn))->exec_freq;

		/* if the defs of both have the same freq, we go for reverse dfs post order. */
		if (fdp == fdq) {
			const dfs_t *dfs = p->bi->bel->dfs;
			int pp = dfs_get_post_num(dfs, p->bi->bl);
			int pq = dfs_get_post_num(dfs, q->bi->bl);
			return pq - pp;
		}

		return (fdq > fdp) - (fdq < fdp);
	}

	return (fq > fp) - (fq < fp);
}

static INLINE unsigned get_curr_distance(block_info_t *bi, const ir_node *irn, int is_usage)
{
	belady_env_t *env          = bi->bel;
	sched_timestep_t curr_step = sched_get_time_step(env->instr);
	next_use_t *use            = get_current_use(bi, irn);
	int flags                  = arch_irn_get_flags(env->arch, irn);
Sebastian Hack's avatar
Sebastian Hack committed
502
503
504
505
506
507
508
509
510
511
512

	assert(!(flags & arch_irn_flags_ignore));

	/* We have to keep nonspillable nodes in the workingset */
	if(flags & arch_irn_flags_dont_spill)
		return 0;

	if (!is_usage && use && use->step == curr_step)
		use = use->next;

	if (use) {
Sebastian Hack's avatar
Sebastian Hack committed
513
		unsigned res  = use->step - curr_step;
Sebastian Hack's avatar
Sebastian Hack committed
514

Sebastian Hack's avatar
Sebastian Hack committed
515
		assert(use->step >= curr_step);
Sebastian Hack's avatar
Sebastian Hack committed
516
517
518
519
520
521
522
523
524

		if (res != 0) {
			if (remat_live_range_ext && be_is_rematerializable(env->senv, irn, use->irn))
				res = REMAT_DIST;
			else if (bitset_contains_irn(env->spilled, irn))
				res *= already_spilled_factor;
		}

		return res;
Sebastian Hack's avatar
Sebastian Hack committed
525
526
527
528
	}

	return be_is_live_end(env->lv, bi->bl, irn) ? LIVE_END : DEAD;
}
Sebastian Hack's avatar
Sebastian Hack committed
529

Sebastian Hack's avatar
Sebastian Hack committed
530
static INLINE int is_local_phi(const ir_node *bl, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
531
532
533
534
{
	return is_Phi(irn) && get_nodes_block(irn) == bl;
}

535
536
/**
 * Check, if the value is something that is transported into a block.
Sebastian Hack's avatar
Sebastian Hack committed
537
 * That is, the value is defined elsewhere or defined by a Phi in the block.
538
539
540
541
 * @param env  The belady environment.
 * @param bl   The block in question.
 * @param irn  The node in question.
 * @return     1, if node is something transported into @p bl, 0 if not.
Sebastian Hack's avatar
Sebastian Hack committed
542
543
544
 * @note       The function will only give correct answers in the case
 *             where @p irn is unsed in the block @p bl which is always
 *             the case in our usage scenario.
545
 */
Sebastian Hack's avatar
Sebastian Hack committed
546
static INLINE int is_transport_in(const ir_node *bl, const ir_node *irn)
547
{
Sebastian Hack's avatar
Sebastian Hack committed
548
	return get_nodes_block(irn) != bl || is_Phi(irn);
549
550
551
552
553
554
555
556
557
558
559
560
}

/**
 * Performs the actions necessary to grant the request that:
 * - 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
 */
static void displace(block_info_t *bi, workset_t *new_vals, int is_usage) {
Sebastian Hack's avatar
Sebastian Hack committed
561
562
563
	belady_env_t *env       = bi->bel;
	workset_t    *ws        = env->ws;
	ir_node     **to_insert = alloca(env->n_regs * sizeof(to_insert[0]));
564

Sebastian Hack's avatar
Sebastian Hack committed
565
566
	int i, len, max_allowed, demand, iter;
	ir_node *val;
567
568
569
570
571
572
573
574
575

	/*
		1. Identify the number of needed slots and the values to reload
	*/
	demand = 0;
	workset_foreach(new_vals, val, iter) {
		/* mark value as used */

		if (! workset_contains(ws, val)) {
Sebastian Hack's avatar
Sebastian Hack committed
576
			DBG((dbg, DBG_DECIDE, "\t\tinsert %+F\n", val));
577
578
			to_insert[demand++] = val;
			if (is_usage) {
Sebastian Hack's avatar
Sebastian Hack committed
579
				next_use_t *use = get_current_use(bi, val);
580
581

				/*
Sebastian Hack's avatar
Sebastian Hack committed
582
583
584
585
				 * if we use a value which is transported in this block, i.e. a
				 * phi defined here or a live in, for the first time, we check
				 * if there is room for that guy to survive from the block's
				 * entrance to here or not.
586
				 */
Sebastian Hack's avatar
Sebastian Hack committed
587
				assert(use);
Sebastian Hack's avatar
Sebastian Hack committed
588
				assert(sched_get_time_step(env->instr) == (int) use->step);
Sebastian Hack's avatar
Sebastian Hack committed
589
				if (is_transport_in(bi->bl, val) && use->is_first_use) {
Sebastian Hack's avatar
Sebastian Hack committed
590
591
					bring_in_t *bri = new_bring_in(bi, val, use);
					bri->first_use = env->instr;
592
593
594
595
596

					/* reset the section pressure, since a new section starts. */
					bi->front_pressure = 0;

					DBG((dbg, DBG_DECIDE, "\t\tbring in node %+F, pressure %d:\n", val, bi->pressure));
Sebastian Hack's avatar
Sebastian Hack committed
597
					DBG((dbg, DBG_DECIDE, "\t\tno reload. must be considered at block start\n"));
598
599
				}

Sebastian Hack's avatar
Sebastian Hack committed
600
				else {
Sebastian Hack's avatar
Sebastian Hack committed
601
					bitset_add_irn(env->spilled, val);
Sebastian Hack's avatar
Sebastian Hack committed
602
					DBG((dbg, DBG_SPILL, "\t\tReload %+F before %+F\n", val, env->instr));
603
604
605
					be_add_reload(env->senv, val, env->instr, env->cls, 1);
				}
			}
606
		} else {
607
			assert(is_usage || "Defined value already in workset?!?");
Sebastian Hack's avatar
Sebastian Hack committed
608
			DBG((dbg, DBG_DECIDE, "\t\tskip %+F\n", val));
609
610
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
611
	DBG((dbg, DBG_DECIDE, "\t\tdemand = %d\n", demand));
612
613
614
615
616
617
618
619
620

	/*
		2. Make room for at least 'demand' slots
	*/
	len         = workset_get_length(ws);
	max_allowed = env->n_regs - demand;

	/* Only make more free room if we do not have enough */
	if (len > max_allowed) {
Sebastian Hack's avatar
Sebastian Hack committed
621
		DBG((dbg, DBG_DECIDE, "\t\tdisposing %d values\n", len - max_allowed));
Sebastian Hack's avatar
Sebastian Hack committed
622

623
624
		/* get current next-use distance */
		for (i = 0; i < ws->len; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
625
626
627
			ir_node *val  = workset_get_val(ws, i);
			unsigned dist = get_curr_distance(bi, val, is_usage);
			workset_set_time(ws, i, dist);
628
629
630
631
632
633
634
635
636
637
638
		}

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

		/* kill the last 'demand' entries in the array */
		workset_set_length(ws, max_allowed);
	}

	/*
		3. Insert the new values into the workset
Sebastian Hack's avatar
Sebastian Hack committed
639
640
641
		   Also, we update the pressure in the block info.
		   That is important for the global pass to decide
		   how many values can live through the block.
642
643
644
	*/
	for (i = 0; i < demand; ++i)
		workset_insert(env, env->ws, to_insert[i]);
Sebastian Hack's avatar
Sebastian Hack committed
645

646
647
648
	/* TODO: simplify this expression? */
	bi->pressure       = MAX(bi->pressure,       workset_get_length(env->ws));
	bi->front_pressure = MAX(bi->front_pressure, workset_get_length(env->ws));
649
650
651
652
653
654
655
}

/**
 * For the given block @p block, decide for each values
 * whether it is used from a register or is reloaded
 * before the use.
 */
656
657
658
static void belady(belady_env_t *env, int id) {
	block_info_t *block_info = new_block_info(env, id);
	const ir_node *block     = block_info->bl;
Sebastian Hack's avatar
Sebastian Hack committed
659

660
661
662
663
	workset_t *new_vals;
	ir_node *irn;
	int iter;

Sebastian Hack's avatar
Sebastian Hack committed
664
	DBG((dbg, DBG_WSETS, "Belady on %+F\n", block_info->bl));
665
	new_vals = new_workset(env, &env->ob);
Sebastian Hack's avatar
Sebastian Hack committed
666
667
668
	workset_clear(env->ws);

	/* build the next use information for this block. */
Sebastian Hack's avatar
Sebastian Hack committed
669
	build_next_uses(block_info);
670

Sebastian Hack's avatar
Sebastian Hack committed
671
672
673
674
	env->instr_nr = 0;
	block_info->first_non_in = NULL;

	/* process the block from start to end */
675
676
677
678
679
680
681
	sched_foreach(block, irn) {
		int i, arity;
		assert(workset_get_length(env->ws) <= env->n_regs && "Too much values in workset!");

		/* projs are handled with the tuple value.
		 * Phis are no real instr (see insert_starters())
		 * instr_nr does not increase */
682
		if (is_Proj(irn) || is_Phi(irn))
683
			continue;
Sebastian Hack's avatar
Sebastian Hack committed
684
		DBG((dbg, DBG_DECIDE, "\t%+F\n", irn));
685
686
687
688
689
690
691
692
693
694
695
696

		if (!block_info->first_non_in)
			block_info->first_non_in = irn;

		/* set instruction in the workset */
		env->instr = irn;

		/* allocate all values _used_ by this instruction */
		workset_clear(new_vals);
		for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) {
			workset_insert(env, new_vals, get_irn_n(irn, i));
		}
Sebastian Hack's avatar
Sebastian Hack committed
697
		DBG((dbg, DBG_DECIDE, "\t* uses\n"));
698
699
		displace(block_info, new_vals, 1);

Sebastian Hack's avatar
Sebastian Hack committed
700
701
702
703
704
705
706
707
		/*
		 * set all used variables to the next use in their next_use_t list
		 * Also, kill all dead variables from the workset. They are only
		 * augmenting the pressure. Note, that a variable is dead
		 * if it has no further use in this block and is *not* live end
		 */
		for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) {
			ir_node *op = get_irn_n(irn, i);
Sebastian Hack's avatar
Sebastian Hack committed
708
			next_use_t *use = get_current_use(block_info, op);
Sebastian Hack's avatar
Sebastian Hack committed
709
710
711
712
713

			assert(use);
			if (!use->next && !be_is_live_end(env->lv, block, op))
				workset_remove(env->ws, op);

Sebastian Hack's avatar
Sebastian Hack committed
714
			advance_current_use(block_info, op);
Sebastian Hack's avatar
Sebastian Hack committed
715
716
		}

717
718
719
720
721
722
723
724
725
726
727
728
		/* allocate all values _defined_ by this instruction */
		workset_clear(new_vals);
		if (get_irn_mode(irn) == mode_T) { /* special handling for tuples and projs */
			const ir_edge_t *edge;

			foreach_out_edge(irn, edge) {
				ir_node *proj = get_edge_src_irn(edge);
				workset_insert(env, new_vals, proj);
			}
		} else {
			workset_insert(env, new_vals, irn);
		}
Sebastian Hack's avatar
Sebastian Hack committed
729
		DBG((dbg, DBG_DECIDE, "\t* defs\n"));
730
731
732
733
734
		displace(block_info, new_vals, 0);

		env->instr_nr++;
	}

Sebastian Hack's avatar
Sebastian Hack committed
735
736
	phase_free(&block_info->next_uses);

737
738
739
740
741
	/* Remember end-workset for this block */
	block_info->ws_end = workset_clone(env, &env->ob, env->ws);
	DBG((dbg, DBG_WSETS, "End workset for %+F:\n", block));
	workset_foreach(block_info->ws_end, irn, iter)
		DBG((dbg, DBG_WSETS, "  %+F (%u)\n", irn, workset_get_time(block_info->ws_end, iter)));
Sebastian Hack's avatar
Sebastian Hack committed
742
	DBG((dbg, DBG_WSETS, "Max pressure in block: %d\n", block_info->pressure));
743
744
745

	/* now, initialize the front pressure to 0. */
	block_info->front_pressure = 0;
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
#define workset_set_version(ws, i, t) ((ws)->vals[(i)].time = (t))
#define workset_get_version(ws, i)    ((ws)->vals[(i)].time)

#define ver_oldest                        (0)
#define ver_youngest                      ((unsigned) -1)
#define ver_make_newer(v)                 ((v) + 1)
#define ver_is_older(v, w)                ((v) < (w))
#define ver_is_younger(v, w)              ((v) > (w))

enum {
	irn_act_none = 0,
	irn_act_reload,
	irn_act_live_through
};

typedef struct _block_state_t {
	struct _block_state_t *next;
	struct _block_state_t *next_intern;
	block_info_t *bi;
777
	int pressure;
778
	workset_t *end_state;
779
780
781
782
783
784
785
786
} block_state_t;

typedef struct _irn_action_t {
	struct _irn_action_t *next;
	ir_node *irn;
	const ir_node *bl;
	int act;
} irn_action_t;
787
788
789

typedef struct _global_end_state_t {
	belady_env_t *env;
Sebastian Hack's avatar
Sebastian Hack committed
790
	bitset_t *succ_phis;
791
	bitset_t *committed;
792
	struct obstack obst;
793
	void *reset_level;
794
	unsigned version;
795
796
797
798
799

	unsigned       *bs_tops_vers;
	block_state_t **bs_tops;
	block_state_t  *bs_top;
	irn_action_t   *ia_top;
800
801
} global_end_state_t;

Sebastian Hack's avatar
Sebastian Hack committed
802
typedef struct {
803
804
805
	void          *obst_level;
	block_state_t *bs_top;
	irn_action_t  *ia_top;
Sebastian Hack's avatar
Sebastian Hack committed
806
807
} rollback_info_t;

808
static INLINE block_state_t *get_block_state(global_end_state_t *ges, const block_info_t *bi)
Sebastian Hack's avatar
Sebastian Hack committed
809
{
810
811
812
	int id = bi->id;
	assert(!ver_is_younger(ges->bs_tops_vers[id], ges->version));
	return ver_is_older(ges->bs_tops_vers[id], ges->version) ? NULL : ges->bs_tops[bi->id];
Sebastian Hack's avatar
Sebastian Hack committed
813
814
}

815
static INLINE const workset_t *get_end_state(global_end_state_t *ges, block_info_t *bi)
Sebastian Hack's avatar
Sebastian Hack committed
816
{
817
818
	block_state_t *bs = get_block_state(ges, bi);
	return bs ? bs->end_state : bi->ws_end;
Sebastian Hack's avatar
Sebastian Hack committed
819
820
}

821
static block_state_t *new_block_state(global_end_state_t *ges, block_info_t *bi)
822
{
823
824
	block_state_t *bs = get_block_state(ges, bi);
	block_state_t *nw = obstack_alloc(&ges->obst, sizeof(nw[0]));
825

826
827
828
829
830
831
832
833
834
835
836
	nw->next_intern = bs;
	nw->next        = ges->bs_top;
	nw->bi          = bi;

	if (bs) {
		nw->pressure  = bs->pressure;
		nw->end_state = workset_clone(ges->env, &ges->obst, bs->end_state);
	}
	else {
		nw->pressure  = bi->pressure;
		nw->end_state = workset_clone(ges->env, &ges->obst, bi->ws_end);
837
838
	}

839
840
841
842
843
	ges->bs_top               = nw;
	ges->bs_tops[bi->id]      = nw;
	ges->bs_tops_vers[bi->id] = ges->version;
	return nw;
}
844

845
846
847
848
849
850
851
852
853
854
855
static irn_action_t *new_irn_action(global_end_state_t *ges, ir_node *irn, const ir_node *bl)
{
	irn_action_t *ia = obstack_alloc(&ges->obst, sizeof(ia[0]));

	ia->irn  = irn;
	ia->bl   = bl;
	ia->act  = irn_act_none;
	ia->next = ges->ia_top;
	ges->ia_top = ia;
	return ia;
}
856

857
858
859
860
861
862
863
864
static INLINE rollback_info_t trans_begin(global_end_state_t *ges)
{
	rollback_info_t rb;
	rb.obst_level = obstack_base(&ges->obst);
	rb.bs_top     = ges->bs_top;
	rb.ia_top     = ges->ia_top;
	return rb;
}
865

866
867
868
static INLINE void trans_rollback(global_end_state_t *ges, rollback_info_t *rb)
{
	block_state_t *bs;
869

870
871
872
873
	/* unwind all the stacks indiced with the block number */
	for (bs = ges->bs_top; bs != rb->bs_top; bs = bs->next) {
		unsigned id = bs->bi->id;
		ges->bs_tops[id] = bs->next_intern;
874
	}
875
876
877
878

	ges->ia_top = rb->ia_top;
	ges->bs_top = rb->bs_top;
	obstack_free(&ges->obst, rb->obst_level);
879
880
}

881

Sebastian Hack's avatar
Sebastian Hack committed
882
static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, double limit, int level);
883

Sebastian Hack's avatar
Sebastian Hack committed
884
static double can_make_available_at_end(global_end_state_t *ges, ir_node *bl, ir_node *irn, double limit, int level)
885
{
886
887
888
	block_info_t *bi     = get_block_info(bl);
	const workset_t *end = get_end_state(ges, bi);
	double res;
889
890
	int index;

891
	DBG((dbg, DBG_GLOBAL, "\t%2Dcan make avail %+F at end of %+F\n", level, irn, bl));
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

	/*
	 * to make the value available at end,
	 * we have several cases here.
	 *
	 * - we already visited that block.
	 * - If the value is in the final end set, return 0.
	 *   somebody else already allocated it there.
	 * - If not and the final end set is already full,
	 *   we cannot make the value available at the end
	 *   of this block. return INFINITY.
	 * - Else (value not in final end set and there is room):
	 *   1) The value is in a register at the end of the local Belady pass.
	 *      Allocate a slot in  the final end set and return 0.
	 *   2) The value is not in the Belady end set:
	 *      If the block's capacity is < k then check what it costs
	 *      to transport the value from upper blocks to this block.
	 *      Compare that against the reload cost in this block. If
	 *      cheaper, do the other thing. If not, reload it here.
	 */

	/* if the end set contains it already, it is in a reg and it costs nothing
	 * to load it to one. */
	index = workset_get_index(end, irn);
	if (index >= 0) {
917
		unsigned ver = workset_get_version(end, index);
Sebastian Hack's avatar
Sebastian Hack committed
918
		DBG((dbg, DBG_GLOBAL, "\t%2Dnode is in the end set and is %s fixed\n",
919
					level, ver_is_older(ver, ges->version) ? "already" : "not yet"));
920
921
922

		/*
		 * if the version is older, the value is already fixed
923
924
925
926
		 * and cannot be removed from the end set.
		 *
		 * If not, we will create a new block state for that block since
		 * we modify it by giving the end state a new version.
927
		 */
928
929
930
931
		if (ver_is_younger(ver, ges->version)) {
			block_state_t *bs = new_block_state(ges, bi);
			workset_set_version(bs->end_state, index, ges->version);
		}
932

933
		res = 0.0;
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
		goto end;
	}

	/*
	 * Now we have two options:
	 * 1) Reload the value at the end of the block.
	 *    Therefore, perhaps, we have to erase another one from the workset.
	 *    This may only be done if it has not been fixed.
	 *    Since fixed means that a previous pass has decided that that value
	 *    *has* to stay in the end set.
	 * 2) we can try, if the capacity of the block allows it, to let
	 *    the value live through the block and make it available at
	 *    the entrance.
	 *
	 * First, we test the local (reload in this block) alternative
	 * and compare against the other alternative.
	 * Of course, we chose the cheaper one.
	 */

	{
954
955
		int n_regs = bi->bel->n_regs;
		int len  = workset_get_length(end);
956
957
958
		int slot = -1;
		int i;

959
		res = HUGE_VAL;
960
961
962
963

		/*
		 * look if there is room in the end array
		 * for the variable. Note that this does not
964
		 * mean that the var can live through the block.
965
966
967
		 * There is just room at the *end*
		 */
		if (len < n_regs) {
968
			DBG((dbg, DBG_GLOBAL, "\t%2Dthe end set has %d free slots\n", level, n_regs - len));
969
			slot = len;
970
		} else {
971
972
973
			for (i = 0; i < len; ++i) {
				unsigned ver = workset_get_version(end, i);
				if (ver_is_younger(ver, ges->version))
974
					break;
975
			}
976
977

			if (i < len) {
Sebastian Hack's avatar
Sebastian Hack committed
978
				DBG((dbg, DBG_GLOBAL, "\t%2D%+F (slot %d) can be erased from the end set\n",
979
980
981
982
983
							level, end->vals[i].irn, i));
				slot = i;
			}
		}

984
985
986
987
		/*
		 * finally there is some room. we can at least reload the value.
		 * but we will try to let ot live through anyhow.
		 */
Sebastian Hack's avatar
Sebastian Hack committed
988
		if (slot >= 0) {
989
990
991
			irn_action_t *vs    = new_irn_action(ges, irn, bi->bl);
			block_state_t *bs   = new_block_state(ges, bi);
			workset_t *end      = bs->end_state;
Sebastian Hack's avatar
Sebastian Hack committed
992
993
			ir_node *ins_before = block_info_get_last_ins(bi);
			double reload_here  = be_get_reload_costs(bi->bel->senv, irn, ins_before);
994
			int pressure_ok     = bs->pressure < n_regs;
995

Sebastian Hack's avatar
Sebastian Hack committed
996
997
998
			if (reload_here < bi->reload_cost)
				reload_here = 0.0;

999
1000
			/*
			 * No matter what we do, the value will be in the end set
For faster browsing, not all history is shown. View entire blame