bespillremat.c 111 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
23
24
25
26
27
28
29
30
31
/** vim: set sw=4 ts=4:
 * @file   bespillremat.c
 * @date   2006-04-06
 * @author Adam M. Szalkowski & Sebastian Hack
 *
 * ILP based spilling & rematerialization
 *
 * Copyright (C) 2006 Universitaet Karlsruhe
 * Released under the GPL
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#ifdef WITH_ILP

#include <math.h>

#include "hashptr.h"
#include "debug.h"
#include "obst.h"
#include "set.h"
#include "list.h"
#include "pmap.h"

#include "irprintf.h"
#include "irgwalk.h"
#include "irdump_t.h"
#include "irnode_t.h"
#include "ircons_t.h"
#include "irloop_t.h"
Adam Szalkowski's avatar
Adam Szalkowski committed
32
#include "phiclass_t.h"
33
#include "iredges.h"
Adam Szalkowski's avatar
Adam Szalkowski committed
34
#include "execfreq.h"
35
#include "irvrfy.h"
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <lpp/lpp.h>
#include <lpp/lpp_net.h>
#include <lpp/lpp_cplex.h>
//#include <lc_pset.h>
#include <libcore/lc_bitset.h>

#include "be_t.h"
#include "belive_t.h"
#include "besched_t.h"
#include "beirgmod.h"
#include "bearch.h"
#include "benode_t.h"
#include "beutil.h"
#include "bespillremat.h"
#include "bespill.h"
Adam Szalkowski's avatar
Adam Szalkowski committed
52
#include "bepressurestat.h"
53
54
55

#include "bechordal_t.h"

56
57
//#define DUMP_SOLUTION
//#define DUMP_ILP
Adam Szalkowski's avatar
Adam Szalkowski committed
58
//#define KEEPALIVE /* keep alive all inserted remats and dump graph with remats */
59
60
#define COLLECT_REMATS /* enable rematerialization */
#define COLLECT_INVERSE_REMATS /* enable placement of inverse remats */
61
//#define ONLY_BRIGGS_REMATS /* only remats without parameters (or only with ignored params) */
62
63
#define REMAT_WHILE_LIVE /* only remat values that are live */
//#define NO_ENLARGE_L1V3N355 /* do not remat after the death of some operand */
Adam Szalkowski's avatar
Adam Szalkowski committed
64
//#define EXECFREQ_LOOPDEPH /* compute execution frequency from loop depth only */
Adam Szalkowski's avatar
Adam Szalkowski committed
65
#define MAY_DIE_AT_REMAT /* allow values to die after a pre remat */
66
#define NO_SINGLE_USE_REMATS /* do not repair schedule */
67
68
//#define KEEPALIVE_SPILLS
//#define KEEPALIVE_RELOADS
69
#define GOODWIN_REDUCTION
Adam Szalkowski's avatar
Adam Szalkowski committed
70
//#define NO_MEMCOPIES
Adam Szalkowski's avatar
Adam Szalkowski committed
71
//#define VERIFY_DOMINANCE
72
#define WITH_MEMOPERANDS
73
74

#define  SOLVE
75
//#define  SOLVE_LOCAL
76
77
78
#define LPP_SERVER "i44pc52"
#define LPP_SOLVER "cplex"

79
80
81
82
#define COST_LOAD        8
#define COST_MEMOPERAND  7
#define COST_STORE       50
#define COST_REMAT       1
83

Adam Szalkowski's avatar
Adam Szalkowski committed
84
85
#define ILP_TIMEOUT    300
#define MAX_PATHS      16
86
87
88
89
90
91
#define ILP_UNDEF		-1

typedef struct _spill_ilp_t {
	const arch_register_class_t  *cls;
	int                           n_regs;
	const be_chordal_env_t       *chordal_env;
Sebastian Hack's avatar
Sebastian Hack committed
92
	be_lv_t                      *lv;
93
94
95
96
	lpp_t                        *lpp;
	struct obstack               *obst;
	set                          *remat_info;
	pset                         *all_possible_remats;
97
	pset                         *inverse_ops;
98
99
100
101
#ifdef KEEPALIVE
	ir_node                      *keep;
#endif
	set                          *values; /**< for collecting all definitions of values before running ssa-construction */
102
	pset                         *spills;
103
	set                          *interferences;
104
	ir_node                      *m_unknown;
105
106
107
#ifdef WITH_MEMOPERANDS
	set                          *memoperands;
#endif
108
109
110
111
112
113
114
	DEBUG_ONLY(firm_dbg_module_t * dbg);
} spill_ilp_t;

typedef int ilp_var_t;
typedef int ilp_cst_t;

typedef struct _spill_bb_t {
115
116
	set      *ilp;
	set      *reloads;
117
118
119
} spill_bb_t;

typedef struct _remat_t {
Christian Würdig's avatar
Christian Würdig committed
120
121
	const ir_node        *op;      /**< for copy_irn */
	const ir_node        *value;   /**< the value which is being recomputed by this remat */
Adam Szalkowski's avatar
Adam Szalkowski committed
122
	const ir_node        *proj;    /**< not NULL if the above op produces a tuple */
Christian Würdig's avatar
Christian Würdig committed
123
	int                   cost;    /**< cost of this remat */
124
	int                   inverse; /**< nonzero if this is an inverse remat */
125
126
127
128
129
130
131
132
133
134
135
136
} remat_t;

/**
 * Data to be attached to each IR node. For remats this contains the ilp_var
 * for this remat and for normal ops this contains the ilp_vars for
 * reloading each operand
 */
typedef struct _op_t {
	int             is_remat;
	union {
		struct {
			ilp_var_t       ilp;
Adam Szalkowski's avatar
Adam Szalkowski committed
137
			const remat_t  *remat; /** the remat this op belongs to */
138
139
140
141
142
			int             pre; /** 1, if this is a pressure-increasing remat */
		} remat;
		struct {
			ilp_var_t       ilp;
			ir_node        *op; /** the operation this live range belongs to */
143
144
145
146
			union {
				ilp_var_t      *reloads;
				ilp_var_t      *copies;
			} args;
147
148
149
150
151
		} live_range;
	} attr;
} op_t;

typedef struct _defs_t {
Adam Szalkowski's avatar
Adam Szalkowski committed
152
153
154
	const ir_node   *value;
	ir_node         *spills;  /**< points to the first spill for this value (linked by link field) */
	ir_node         *remats;  /**< points to the first definition for this value (linked by link field) */
155
156
157
158
159
160
161
162
163
164
165
166
167
168
} defs_t;

typedef struct _remat_info_t {
	const ir_node       *irn; /**< the irn to which these remats belong */
	pset                *remats; /**< possible remats for this value */
	pset                *remats_by_operand; /**< remats with this value as operand */
} remat_info_t;

typedef struct _keyval_t {
	const void          *key;
	const void          *val;
} keyval_t;

typedef struct _spill_t {
Adam Szalkowski's avatar
Adam Szalkowski committed
169
170
171
172
173
174
	ir_node            *irn;
	ilp_var_t           reg_in;
	ilp_var_t           mem_in;
	ilp_var_t           reg_out;
	ilp_var_t           mem_out;
	ilp_var_t           spill;
175
176
} spill_t;

177
178
#ifdef WITH_MEMOPERANDS
typedef struct _memoperand_t {
Adam Szalkowski's avatar
Adam Szalkowski committed
179
	ir_node             *irn; /**< the irn */
180
181
182
183
184
	unsigned int         pos; /**< the position of the argument */
	ilp_var_t            ilp; /**< the ilp var for this memory operand */
} memoperand_t;
#endif

185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
static INLINE int
has_reg_class(const spill_ilp_t * si, const ir_node * irn)
{
	return chordal_has_class(si->chordal_env, irn);
}

#if 0
static int
cmp_remat(const void *a, const void *b)
{
	const keyval_t *p = a;
	const keyval_t *q = b;
	const remat_t  *r = p->val;
	const remat_t  *s = q->val;

	assert(r && s);

	return !(r == s || r->op == s->op);
}
#endif
static int
cmp_remat(const void *a, const void *b)
{
	const remat_t  *r = a;
	const remat_t  *s = a;

	return !(r == s || r->op == s->op);
}

static int
cmp_spill(const void *a, const void *b, size_t size)
{
	const spill_t *p = a;
	const spill_t *q = b;

//	return !(p->irn == q->irn && p->bb == q->bb);
	return !(p->irn == q->irn);
}

224
225
226
227
228
229
230
231
232
233
234
#ifdef WITH_MEMOPERANDS
static int
cmp_memoperands(const void *a, const void *b, size_t size)
{
	const memoperand_t *p = a;
	const memoperand_t *q = b;

	return !(p->irn == q->irn && p->pos == q->pos);
}
#endif

235
static keyval_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
236
set_find_keyval(set * set, const void * key)
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
{
	keyval_t     query;

	query.key = key;
	return set_find(set, &query, sizeof(query), HASH_PTR(key));
}

static keyval_t *
set_insert_keyval(set * set, void * key, void * val)
{
	keyval_t     query;

	query.key = key;
	query.val = val;
	return set_insert(set, &query, sizeof(query), HASH_PTR(key));
}

static defs_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
255
set_find_def(set * set, const ir_node * value)
256
257
258
259
260
261
262
263
{
	defs_t     query;

	query.value = value;
	return set_find(set, &query, sizeof(query), HASH_PTR(value));
}

static defs_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
264
set_insert_def(set * set, const ir_node * value)
265
266
267
268
269
270
271
272
273
{
	defs_t     query;

	query.value = value;
	query.spills = NULL;
	query.remats = NULL;
	return set_insert(set, &query, sizeof(query), HASH_PTR(value));
}

274
275
276
277
278
279
280
281
282
283
284
285
286
#ifdef WITH_MEMOPERANDS
static memoperand_t *
set_insert_memoperand(set * set, ir_node * irn, unsigned int pos, ilp_var_t ilp)
{
	memoperand_t     query;

	query.irn = irn;
	query.pos = pos;
	query.ilp = ilp;
	return set_insert(set, &query, sizeof(query), HASH_PTR(irn)+pos);
}

static memoperand_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
287
set_find_memoperand(set * set, const ir_node * irn, unsigned int pos)
288
289
290
{
	memoperand_t     query;

Adam Szalkowski's avatar
Adam Szalkowski committed
291
	query.irn = (ir_node*)irn;
292
293
294
295
296
297
	query.pos = pos;
	return set_find(set, &query, sizeof(query), HASH_PTR(irn)+pos);
}
#endif


298
static spill_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
299
set_find_spill(set * set, const ir_node * value)
300
301
302
{
	spill_t     query;

Adam Szalkowski's avatar
Adam Szalkowski committed
303
	query.irn = (ir_node*)value;
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
	return set_find(set, &query, sizeof(query), HASH_PTR(value));
}

#define pset_foreach(s,i) for((i)=pset_first((s)); (i); (i)=pset_next((s)))
#define set_foreach(s,i) for((i)=set_first((s)); (i); (i)=set_next((s)))
#define foreach_post_remat(s,i) for((i)=next_post_remat((s)); (i); (i)=next_post_remat((i)))
#define foreach_pre_remat(si,s,i) for((i)=next_pre_remat((si),(s)); (i); (i)=next_pre_remat((si),(i)))
#define	sched_foreach_op(s,i) for((i)=sched_next_op((s));!sched_is_end((i));(i)=sched_next_op((i)))

static int
cmp_remat_info(const void *a, const void *b, size_t size)
{
	const remat_info_t *p = a;
	const remat_info_t *q = b;

	return !(p->irn == q->irn);
}

static int
cmp_defs(const void *a, const void *b, size_t size)
{
	const defs_t *p = a;
	const defs_t *q = b;

	return !(p->value == q->value);
}

static int
cmp_keyval(const void *a, const void *b, size_t size)
{
	const keyval_t *p = a;
	const keyval_t *q = b;

	return !(p->key == q->key);
}

Sebastian Hack's avatar
Sebastian Hack committed
340
static double
341
execution_frequency(const spill_ilp_t *si, const ir_node * irn)
342
{
343
#define FUDGE 0.001
344
#ifndef EXECFREQ_LOOPDEPH
345
	return get_block_execfreq(si->chordal_env->exec_freq, get_block(irn)) + FUDGE;
346
347
348
349
350
351
#else
	if(is_Block(irn))
		return exp(get_loop_depth(get_irn_loop(irn)) * log(10)) + FUDGE;
	else
		return exp(get_loop_depth(get_irn_loop(get_nodes_block(irn))) * log(10)) + FUDGE;
#endif
352
353
}

354
355
356
357
358
359
360
361
362
363
364
365
static double
get_cost(const spill_ilp_t * si, const ir_node * irn)
{
	if(be_is_Spill(irn)) {
		return COST_STORE;
	} else if(be_is_Reload(irn)){
		return COST_LOAD;
	} else {
		return arch_get_op_estimated_cost(si->chordal_env->birg->main_env->arch_env, irn);
	}
}

366
367
368
369
370
371
/**
 * Checks, whether node and its operands have suitable reg classes
 */
static INLINE int
is_rematerializable(const spill_ilp_t * si, const ir_node * irn)
{
Adam Szalkowski's avatar
Adam Szalkowski committed
372
	int               n;
373
374
375
376
377
378
379
380
	const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
	int               remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;

#if 0
	if(!remat)
		ir_fprintf(stderr, "  Node %+F is not rematerializable\n", irn);
#endif

Adam Szalkowski's avatar
Adam Szalkowski committed
381
382
	for (n = get_irn_arity(irn)-1; n>=0 && remat; --n) {
		ir_node        *op = get_irn_n(irn, n);
383
384
385
386
387
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
		remat &= has_reg_class(si, op) || arch_irn_get_flags(arch_env, op) & arch_irn_flags_ignore || (get_irn_op(op) == op_NoMem);

//		if(!remat)
//			ir_fprintf(stderr, "  Argument %d (%+F) of Node %+F has wrong regclass\n", i, op, irn);
	}

	return remat;
}

/**
 * Try to create a remat from @p op with destination value @p dest_value
 */
static INLINE remat_t *
get_remat_from_op(spill_ilp_t * si, const ir_node * dest_value, const ir_node * op)
{
	remat_t  *remat = NULL;

//	if(!mode_is_datab(get_irn_mode(dest_value)))
//		return NULL;

	if(dest_value == op) {
		const ir_node *proj = NULL;

		if(is_Proj(dest_value)) {
			op = get_irn_n(op, 0);
			proj = dest_value;
		}

		if(!is_rematerializable(si, op))
			return NULL;

		remat = obstack_alloc(si->obst, sizeof(*remat));
		remat->op = op;
416
		remat->cost = get_cost(si, op);
417
418
		remat->value = dest_value;
		remat->proj = proj;
419
		remat->inverse = 0;
420
421
	} else {
		arch_inverse_t     inverse;
Adam Szalkowski's avatar
Adam Szalkowski committed
422
		int                n;
423
424

		/* get the index of the operand we want to retrieve by the inverse op */
Adam Szalkowski's avatar
Adam Szalkowski committed
425
426
		for (n = get_irn_arity(op)-1; n>=0; --n) {
			ir_node        *arg = get_irn_n(op, n);
427
428
429

			if(arg == dest_value) break;
		}
Adam Szalkowski's avatar
Adam Szalkowski committed
430
		if(n<0) return NULL;
431

Adam Szalkowski's avatar
Adam Szalkowski committed
432
		DBG((si->dbg, LEVEL_5, "\t  requesting inverse op for argument %d of op %+F\n", n, op));
433
434

		/* else ask the backend to give an inverse op */
Adam Szalkowski's avatar
Adam Szalkowski committed
435
		if(arch_get_inverse(si->chordal_env->birg->main_env->arch_env, op, n, &inverse, si->obst)) {
436
437
			int   i;

438
439
440
441
			DBG((si->dbg, LEVEL_4, "\t  backend gave us an inverse op with %d nodes and cost %d\n", inverse.n, inverse.costs));

			assert(inverse.n > 0 && "inverse op should have at least one node");

Adam Szalkowski's avatar
Adam Szalkowski committed
442
			for(i=inverse.n-1; i>=0; --i) {
443
444
445
				pset_insert_ptr(si->inverse_ops, inverse.nodes[i]);
			}

446
447
448
449
450
451
			if(inverse.n <= 2) {
				remat = obstack_alloc(si->obst, sizeof(*remat));
				remat->op = inverse.nodes[0];
				remat->cost = inverse.costs;
				remat->value = dest_value;
				remat->proj = (inverse.n==2)?inverse.nodes[1]:NULL;
452
				remat->inverse = 1;
453
454
455

				assert(is_Proj(remat->proj));
			} else {
456
				assert(0 && "I can not handle remats with more than 2 nodes");
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
			}
		}
	}

	if(remat) {
		if(remat->proj) {
			DBG((si->dbg, LEVEL_3, "\t >Found remat %+F for %+F from %+F with %+F\n", remat->op, dest_value, op, remat->proj));
		} else {
			DBG((si->dbg, LEVEL_3, "\t >Found remat %+F for %+F from %+F\n", remat->op, dest_value, op));
		}
	}
	return remat;
}


static INLINE void
add_remat(const spill_ilp_t * si, const remat_t * remat)
{
	remat_info_t    *remat_info,
                     query;
Adam Szalkowski's avatar
Adam Szalkowski committed
477
	int              n;
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492

	assert(remat->op);
	assert(remat->value);

	query.irn = remat->value;
	query.remats = NULL;
	query.remats_by_operand = NULL;
	remat_info = set_insert(si->remat_info, &query, sizeof(query), HASH_PTR(remat->value));

	if(remat_info->remats == NULL) {
		remat_info->remats = new_pset(cmp_remat, 4096);
	}
	pset_insert(remat_info->remats, remat, HASH_PTR(remat->op));

	/* insert the remat into the remats_be_operand set of each argument of the remat op */
Adam Szalkowski's avatar
Adam Szalkowski committed
493
494
	for (n = get_irn_arity(remat->op)-1; n>=0; --n) {
		ir_node        *arg = get_irn_n(remat->op, n);
495
496
497
498
499
500
501
502
503
504
505
506
507

		query.irn = arg;
		query.remats = NULL;
		query.remats_by_operand = NULL;
		remat_info = set_insert(si->remat_info, &query, sizeof(query), HASH_PTR(arg));

		if(remat_info->remats_by_operand == NULL) {
			remat_info->remats_by_operand = new_pset(cmp_remat, 4096);
		}
		pset_insert(remat_info->remats_by_operand, remat, HASH_PTR(remat->op));
	}
}

508
#ifdef NO_SINGLE_USE_REMATS
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
static int
get_irn_n_nonremat_edges(const spill_ilp_t * si, const ir_node * irn)
{
	const ir_edge_t   *edge = get_irn_out_edge_first(irn);
	int                i = 0;

	while(edge) {
		if(!pset_find_ptr(si->inverse_ops, edge->src)) {
			++i;
		}
		edge = get_irn_out_edge_next(irn, edge);
	}

	return i;
}
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
#endif

#ifdef ONLY_BRIGGS_REMATS
static int
get_irn_n_nonignore_args(const spill_ilp_t * si, const ir_node * irn)
{
	int n;
	unsigned int ret = 0;

	for(n=get_irn_arity(irn)-1; n>=0; --n) {
		if(has_reg_class(si, irn)) ++ret;
	}

	return ret;
}
#endif
540

541
542
543
static INLINE void
get_remats_from_op(spill_ilp_t * si, const ir_node * op)
{
Adam Szalkowski's avatar
Adam Szalkowski committed
544
	int      n;
545
546
	remat_t *remat;

547
	if( has_reg_class(si, op)
548
#ifdef NO_SINGLE_USE_REMATS
549
550
551
552
	&& (get_irn_n_nonremat_edges(si, op) > 1)
#endif
#ifdef ONLY_BRIGGS_REMATS
	&& (get_irn_n_nonignore_args(si, op) == 0)
553
#endif
554
	) {
555
556
557
558
559
560
		remat = get_remat_from_op(si, op, op);
		if(remat) {
			add_remat(si, remat);
		}
	}

561
#if defined(COLLECT_INVERSE_REMATS) && !defined(ONLY_BRIGGS_REMATS)
562
563
	/* repeat the whole stuff for each remat retrieved by get_remat_from_op(op, arg)
	   for each arg */
Adam Szalkowski's avatar
Adam Szalkowski committed
564
565
	for (n = get_irn_arity(op)-1; n>=0; --n) {
		ir_node        *arg = get_irn_n(op, n);
566
567
568
569
570
571
572
573
574

		if(has_reg_class(si, arg)) {
			/* try to get an inverse remat */
			remat = get_remat_from_op(si, arg, op);
			if(remat) {
				add_remat(si, remat);
			}
		}
	}
575
#endif
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598

}

static INLINE int
value_is_defined_before(const spill_ilp_t * si, const ir_node * pos, const ir_node * val)
{
	ir_node *block;
	ir_node *def_block = get_nodes_block(val);
	int      ret;

	if(val == pos)
		return 0;

	/* if pos is at end of a basic block */
	if(is_Block(pos)) {
		ret = (pos == def_block || block_dominates(def_block, pos));
//		ir_fprintf(stderr, "(def(bb)=%d) ", ret);
		return ret;
	}

	/* else if this is a normal operation */
	block = get_nodes_block(pos);
	if(block == def_block) {
599
600
		if(!sched_is_scheduled(val)) return 1;

601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
		ret = sched_comes_after(val, pos);
//		ir_fprintf(stderr, "(def(same block)=%d) ",ret);
		return ret;
	}

	ret = block_dominates(def_block, block);
//	ir_fprintf(stderr, "(def(other block)=%d) ", ret);
	return ret;
}

static INLINE ir_node *
sched_block_last_noncf(const spill_ilp_t * si, const ir_node * bb)
{
    return sched_skip((ir_node*)bb, 0, sched_skip_cf_predicator, (void *) si->chordal_env->birg->main_env->arch_env);
}

/**
 * Returns first non-Phi node of block @p bb
 */
static INLINE ir_node *
sched_block_first_nonphi(const ir_node * bb)
{
	return sched_skip((ir_node*)bb, 1, sched_skip_phi_predicator, NULL);
}

static int
sched_skip_proj_predicator(const ir_node * irn, void * data)
{
	return (is_Proj(irn));
}

static INLINE ir_node *
sched_next_nonproj(const ir_node * irn, int forward)
{
	return sched_skip((ir_node*)irn, forward, sched_skip_proj_predicator, NULL);
}

/**
 * Returns next operation node (non-Proj) after @p irn
 * or the basic block of this node
 */
static INLINE ir_node *
sched_next_op(const ir_node * irn)
{
	ir_node *next = sched_next(irn);

	if(is_Block(next))
		return next;

	return sched_next_nonproj(next, 1);
}

/**
 * Returns previous operation node (non-Proj) before @p irn
 * or the basic block of this node
 */
static INLINE ir_node *
sched_prev_op(const ir_node * irn)
{
	ir_node *prev = sched_prev(irn);

	if(is_Block(prev))
		return prev;

	return sched_next_nonproj(prev, 0);
}

static void
sched_put_after(ir_node * insert, ir_node * irn)
{
	if(is_Block(insert)) {
		insert = sched_block_first_nonphi(insert);
	} else {
		insert = sched_next_op(insert);
	}
	sched_add_before(insert, irn);
}

static void
sched_put_before(const spill_ilp_t * si, ir_node * insert, ir_node * irn)
{
  if(is_Block(insert)) {
	  insert = sched_block_last_noncf(si, insert);
  } else {
	  insert = sched_next_nonproj(insert, 0);
	  insert = sched_prev(insert);
  }
  sched_add_after(insert, irn);
}

/**
 * Tells you whether a @p remat can be placed before the irn @p pos
 */
static INLINE int
can_remat_before(const spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
{
	const ir_node   *op = remat->op;
	const ir_node   *prev;
Adam Szalkowski's avatar
Adam Szalkowski committed
699
	int        n,
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
			   res = 1;

	if(is_Block(pos)) {
		prev = sched_block_last_noncf(si, pos);
		prev = sched_next_nonproj(prev, 0);
	} else {
		prev = sched_prev_op(pos);
	}
	/* do not remat if the rematted value is defined immediately before this op */
	if(prev == remat->op) {
		return 0;
	}

#if 0
	/* this should be just fine, the following OP will be using this value, right? */

	/* only remat AFTER the real definition of a value (?) */
	if(!value_is_defined_before(si, pos, remat->value)) {
//		ir_fprintf(stderr, "error(not defined)");
		return 0;
	}
#endif

Adam Szalkowski's avatar
Adam Szalkowski committed
723
724
	for(n=get_irn_arity(op)-1; n>=0 && res; --n) {
		const ir_node   *arg = get_irn_n(op, n);
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784

#ifdef NO_ENLARGE_L1V3N355
		if(has_reg_class(si, arg) && live) {
			res &= pset_find_ptr(live, arg)?1:0;
		} else {
			res &= value_is_defined_before(si, pos, arg);
		}
#else
		res &= value_is_defined_before(si, pos, arg);
#endif
	}

	return res;
}

/**
 * Tells you whether a @p remat can be placed after the irn @p pos
 */
static INLINE int
can_remat_after(const spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
{
	if(is_Block(pos)) {
		pos = sched_block_first_nonphi(pos);
	} else {
		pos = sched_next_op(pos);
	}

	/* only remat AFTER the real definition of a value (?) */
	if(!value_is_defined_before(si, pos, remat->value)) {
		return 0;
	}

	return can_remat_before(si, remat, pos, live);
}

/**
 * Collect potetially rematerializable OPs
 */
static void
walker_remat_collector(ir_node * irn, void * data)
{
	spill_ilp_t    *si = data;

	if(!is_Block(irn) && !is_Phi(irn)) {
		DBG((si->dbg, LEVEL_4, "\t  Processing %+F\n", irn));
		get_remats_from_op(si, irn);
	}
}

/**
 * Inserts a copy of @p irn before @p pos
 */
static ir_node *
insert_copy_before(const spill_ilp_t * si, const ir_node * irn, ir_node * pos)
{
	ir_node     *bb;
	ir_node     *copy;

	bb = is_Block(pos)?pos:get_nodes_block(pos);
	copy = exact_copy(irn);
Adam Szalkowski's avatar
Adam Szalkowski committed
785
786

	_set_phi_class(copy, NULL);
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
	set_nodes_block(copy, bb);
	sched_put_before(si, pos, copy);

	return copy;
}

/**
 * Inserts a copy of @p irn after @p pos
 */
static ir_node *
insert_copy_after(const spill_ilp_t * si, const ir_node * irn, ir_node * pos)
{
	ir_node     *bb;
	ir_node     *copy;

	bb = is_Block(pos)?pos:get_nodes_block(pos);
	copy = exact_copy(irn);
Adam Szalkowski's avatar
Adam Szalkowski committed
804
805

	_set_phi_class(copy, NULL);
806
807
808
809
810
811
	set_nodes_block(copy, bb);
	sched_put_after(pos, copy);

	return copy;
}

Adam Szalkowski's avatar
Adam Szalkowski committed
812
static ir_node *
Adam Szalkowski's avatar
Adam Szalkowski committed
813
insert_remat_after(spill_ilp_t * si, const remat_t * remat, ir_node * pos, const pset * live)
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
{
	char     buf[256];

	if(can_remat_after(si, remat, pos, live)) {
		ir_node         *copy,
						*proj_copy;
		op_t            *op;

		DBG((si->dbg, LEVEL_3, "\t  >inserting remat %+F\n", remat->op));

		copy = insert_copy_after(si, remat->op, pos);

		ir_snprintf(buf, sizeof(buf), "remat2_%N_%N", copy, pos);
		op = obstack_alloc(si->obst, sizeof(*op));
		op->is_remat = 1;
		op->attr.remat.remat = remat;
		op->attr.remat.pre = 0;
831
		op->attr.remat.ilp = lpp_add_var(si->lpp, buf, lpp_binary, remat->cost*execution_frequency(si, pos));
832
833
834
835
836
837
838
839
840
841
842

		set_irn_link(copy, op);
		pset_insert_ptr(si->all_possible_remats, copy);
		if(remat->proj) {
			proj_copy = insert_copy_after(si, remat->proj, copy);
			set_irn_n(proj_copy, 0, copy);
			set_irn_link(proj_copy, op);
			pset_insert_ptr(si->all_possible_remats, proj_copy);
		} else {
			proj_copy = NULL;
		}
Adam Szalkowski's avatar
Adam Szalkowski committed
843
844

		return copy;
845
	}
Adam Szalkowski's avatar
Adam Szalkowski committed
846
847

	return NULL;
848
849
}

Adam Szalkowski's avatar
Adam Szalkowski committed
850
static ir_node *
Adam Szalkowski's avatar
Adam Szalkowski committed
851
insert_remat_before(spill_ilp_t * si, const remat_t * remat, ir_node * pos, const pset * live)
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
{
	char     buf[256];

	if(can_remat_before(si, remat, pos, live)) {
		ir_node         *copy,
						*proj_copy;
		op_t            *op;

		DBG((si->dbg, LEVEL_3, "\t  >inserting remat %+F\n", remat->op));

		copy = insert_copy_before(si, remat->op, pos);

		ir_snprintf(buf, sizeof(buf), "remat_%N_%N", copy, pos);
		op = obstack_alloc(si->obst, sizeof(*op));
		op->is_remat = 1;
		op->attr.remat.remat = remat;
		op->attr.remat.pre = 1;
869
		op->attr.remat.ilp = lpp_add_var(si->lpp, buf, lpp_binary, remat->cost*execution_frequency(si, pos));
870
871
872
873
874
875
876
877
878
879
880

		set_irn_link(copy, op);
		pset_insert_ptr(si->all_possible_remats, copy);
		if(remat->proj) {
			proj_copy = insert_copy_after(si, remat->proj, copy);
			set_irn_n(proj_copy, 0, copy);
			set_irn_link(proj_copy, op);
			pset_insert_ptr(si->all_possible_remats, proj_copy);
		} else {
			proj_copy = NULL;
		}
Adam Szalkowski's avatar
Adam Szalkowski committed
881
882

		return copy;
883
	}
Adam Szalkowski's avatar
Adam Szalkowski committed
884
885

	return NULL;
886
887
}

Adam Szalkowski's avatar
Adam Szalkowski committed
888
889
static int
get_block_n_succs(const ir_node *block) {
890
891
892
893
894
895
896
897
898
899
900
	const ir_edge_t *edge;

	assert(edges_activated(current_ir_graph));

	edge = get_block_succ_first(block);
	if (! edge)
		return 0;

	edge = get_block_succ_next(block, edge);
	return edge ? 2 : 1;
}
901

Adam Szalkowski's avatar
Adam Szalkowski committed
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
static int
is_merge_edge(const ir_node * bb)
{
#ifdef GOODWIN_REDUCTION
	return get_block_n_succs(bb) == 1;
#else
	return 1;
#endif
}

static int
is_diverge_edge(const ir_node * bb)
{
#ifdef GOODWIN_REDUCTION
	return get_Block_n_cfgpreds(bb) == 1;
#else
	return 1;
#endif
}

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
static void
walker_regclass_copy_insertor(ir_node * irn, void * data)
{
	spill_ilp_t    *si = data;

	if(is_Phi(irn) && has_reg_class(si, irn)) {
		int n;

		for(n=get_irn_arity(irn)-1; n>=0; --n) {
			ir_node  *phi_arg = get_irn_n(irn, n);
			ir_node  *bb = get_Block_cfgpred_block(get_nodes_block(irn), n);

			if(!has_reg_class(si, phi_arg)) {
				ir_node   *copy = be_new_Copy(si->cls, si->chordal_env->irg, bb, phi_arg);
				ir_node   *pos = sched_block_last_noncf(si, bb);
				op_t      *op = obstack_alloc(si->obst, sizeof(*op));

				DBG((si->dbg, LEVEL_2, "\t copy to my regclass for arg %+F of %+F\n", phi_arg, irn));
				sched_add_after(pos, copy);
				set_irn_n(irn, n, copy);

				op->is_remat = 0;
				op->attr.live_range.args.reloads = NULL;
				op->attr.live_range.ilp = ILP_UNDEF;
				set_irn_link(copy, op);
			}
		}
	}
}


953
954
955
956
957
958
959
960
961
962
/**
 * Insert (so far unused) remats into the irg to
 * recompute the potential liveness of all values
 */
static void
walker_remat_insertor(ir_node * bb, void * data)
{
	spill_ilp_t    *si = data;
	spill_bb_t     *spill_bb;
	ir_node        *irn;
Sebastian Hack's avatar
Sebastian Hack committed
963
	int             n, i;
964
965
966
967
	pset           *live = pset_new_ptr_default();

	DBG((si->dbg, LEVEL_3, "\t Entering %+F\n\n", bb));

Adam Szalkowski's avatar
Adam Szalkowski committed
968
969
	be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
		ir_node        *value = be_lv_get_irn(si->lv, bb, i);
970
971

		/* add remats at end of block */
Sebastian Hack's avatar
Sebastian Hack committed
972
		if (has_reg_class(si, value)) {
973
974
975
976
977
978
979
980
981
982
983
984
985
			pset_insert_ptr(live, value);
		}
	}

	spill_bb = obstack_alloc(si->obst, sizeof(*spill_bb));
	set_irn_link(bb, spill_bb);

	irn = sched_last(bb);
	while(!sched_is_end(irn)) {
		ir_node   *next;
		op_t      *op;
		pset      *args;
		ir_node   *arg;
Adam Szalkowski's avatar
Adam Szalkowski committed
986
		pset      *remat_args;
987
988
989
990
991
992
993
994
995
996
997
998
999
1000

		next = sched_prev(irn);

		DBG((si->dbg, LEVEL_5, "\t at %+F (next: %+F)\n", irn, next));

		if(is_Phi(irn) || is_Proj(irn)) {
			op_t      *op;

			if(has_reg_class(si, irn)) {
				pset_remove_ptr(live, irn);
			}

			op = obstack_alloc(si->obst, sizeof(*op));
			op->is_remat = 0;